📂Set Theory

Contrapositive and Converse Propositions

Definition ¹

A proposition that is true for all logical possibilities is called a Tautology. A proposition that is false for all logical possibilities is called a Contradiction.

1. For $p$, $q$, if the conditional statement $p \to q$ is a tautology, it is called an Implication and represented as follows: $$ p \implies q $$
2. For $p$, $q$, if the biconditional statement $p \to q$ is a tautology, it is called Equivalence and represented as follows: $$ p \iff q $$

Explanation

The term contradiction is almost never used, and instead, the word contradiction is often used. Symbolically, tautology and contradiction are denoted as Tautology $t$, Contradiction $c$, respectively.

According to the truth table, $p$ might be true or false, but $p \lor \lnot p$ is always true. Considering the definition of a proposition, if $p$ is true or false, it logically means it’s true. Hence, a tautology is such a proposition that, disregarding the ‘fact’, just by its form, it can only be true.

People who are not interested in mathematics might think math is complex and difficult, but what one realizes as they study more is that mathematicians are desperately struggling not to ’think’. Humanity has far too many combinations of ‘words’, and it’s daunting to assess each and every one of them for correctness. Thus, for at least ’things that can be recognized just by their form’, they wish to exert only that much effort to grasp.

Implication means to include the meaning, which fits perfectly as a refined expression for Imply, but it’s extremely rare for Korean speakers to interpret Imply as implication.

Laws ¹

For any propositions $p$, $q$, $r$, the following hold:

• [1] Law of Addition: $$ p \implies p \lor q $$
• [2] Laws of Simplification: $$ p \land q \implies p \\ p \land q \implies q $$
• [3] Laws of Absorption: $$ p \land ( p \lor q) \iff p \\ p \lor ( p \land q ) \iff p $$
• [4] Law of Double Negation: $$ \lnot ( \lnot p) \iff p $$
• [5] Laws of Commutativity: $$ p \land q \iff q \land p \\ p \lor q \iff q \lor p $$
• [6] Laws of Idempotency: $$ p \land p \iff p \\ p \lor p \iff p $$
• [7] Laws of Associativity: $$ (p \land q) \land r \iff p \land (q \land r) \\ (p \lor q) \lor r \iff p \lor (q \lor r) $$
• [8] Laws of Distributivity: $$ p \land (q \lor r) \iff (p \land q) \lor (p \land r) \\ p \lor (q \land r) \iff (p \lor q) \land (p \lor r) $$

These laws should be as natural as breathing to humans engaging in logical thought, and for those in STEM fields, the special laws listed below should be second nature. The closer your major is to the formal sciences—computer science, statistics, mathematics—the sooner you should become familiar with them:

• [9] De Morgan’s Laws: $$ \lnot (p \land q) \iff \lnot p \lor \lnot q \\ \lnot(p \lor q) \iff \lnot p \land \lnot q $$
• [10] Contrapositive Law: $$ (p \to q) \iff (\lnot q \to \lnot p) $$
• [11] Reductio ad Absurdum: $$ (p \land \lnot q) \to c \iff p \to q $$
• [12] Syllogism: $$ (p \to q) \land (q \to r) \implies (p \to r) $$

English Notation

The English notations for the theorems introduced in this post are as follows:

• [1] Law of Addition
• [2] Laws of Simplification
• [3] Laws of Absorption
• [4] Law of Double Negation
• [5] Laws of Commutativity
• [6] Laws of Idempotency
• [7] Laws of Associativity
• [8] Laws of Distributivity
• [9] De Morgan’s Laws
• [10] Contrapositive Law
• [11] Reductio ad Absurdum
• [12] Syllogism

Especially, [11] Reductio ad Absurdum is also called the law of absurdity, and [12] Syllogism is also known as the Law of Transitivity.