📂Set Theory

Propositions and Connectives, Truth Tables

Definitions ¹

A proposition is a statement that is either true or false. A proposition has one of two truth values, true or false. Two propositions $p$, $q$ are said to be (logically) equivalent if they have the same truth value, and this is represented as $p \equiv q$. The following symbols are referred to as connectives and are methods for forming compound propositions:

1. Negation: $\lnot$
2. Conjunction: $\land$
3. Disjunction: $\lor$
4. Conditional: $\to$
5. Biconditional: $\leftrightarrow$

Truth Table

Typically, true is represented by $T$ and false by $F$. The above connectives have logical values according to their definitions. The truth values of propositions formed by applying connectives to propositions can conveniently be checked using a truth table:

Negation

If $p$ is true, then $\lnot p$ is false, and if $p$ is false, then $\lnot p$ is true.

• $\text{NOT}$ Gate

Conjunction

If both $p$ and $q$ are true, then $p \land q$ is also true; otherwise, it is false. Generally, in fields like computer science, $0$ is considered false, and any value other than $0$ is true. Considering two non-$0$ numbers $a$, $b$, $a \times b = ab \ne 0$ is true, but if either is $0$, then $a \times b = 0$ is false. Thus, in this sense, $\land$ is called a logical ‘and’.

• $\text{AND}$ Gate

Disjunction

If either $p$ or $q$ is true, then $p \lor q$ is true, and it is only false when both are false. Similar to conjunction, if $a + b = 0$, it is false, and otherwise, it is true, thus $\lor$ is called a logical ‘or’. Even if $b = -a \ne 0$, meaning both $a$ and $b$ are true but $a+b = 0$ is false, we shouldn’t nitpick. So, it’s not just ‘or’ but ’logical or’.

• $\text{OR}$ Gate

Conditional

If $p$ is true and $q$ is true, then $p \to q$ is also true. Note that unlike in natural language, if $p$ is false, regardless of what $q$ is, $p \to q$ is true. On the other hand, $p \to q \equiv \lnot p \lor q$, and this is easily proven through a truth table. Refer to the bottom of the document.

Biconditional

If both $p \to q$ and $q \to p$ are true, then $p \leftrightarrow q$. Mathematically, this is represented as $(p \to q) \land (q \to p) \equiv p \leftrightarrow q$. According to the truth table, $p \leftrightarrow q$ is true when $p$ and $q$ have the same truth value, that is, both are either true or false.

Theorem

Logical Equivalence of Conditionals

$$ p \to q \equiv \left( \lnot p \lor q \right) $$

Proof

By the definitions of negation and disjunction

■