A proposition is a declarative expression that can either be true or false. It is formed from one or more statements, which capture a logical expression that may be reasoned about symbolically.
By convention \(p\), \(q\), \(r\), \(s\), or \(t\) are used to denote statements within an expression.
| Symbol | Term | Truth Table | Description |
|---|---|---|---|
| \(\lnot\) | NOT, negation | \(\begin{matrix} \lnot & \\ 0 & 1 \\ 1 & 0 \end{matrix}\) | \(\lnot p\) is true if \(p\) is false |
| \(\land\) | AND, conjunction | \(\begin{matrix} \land & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{matrix}\) | \(p \land q\) is tue when both are true |
| \(\lor\) | OR, disjuntion | \(\begin{matrix} \lor & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{matrix}\) | \(p \lor q\) is true if at least one is true |
| \(\rightarrow\) | IF…THEN, implication | \(\begin{matrix} \rightarrow & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix}\) | \(p \rightarrow q\) is true only if \(p\) is false or \(q\) is true |
| \(\leftrightarrow\) | IF and only IF, biconditional | \(\begin{matrix} \leftrightarrow & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{matrix}\) | \(p \leftrightarrow q\) is true if both \(p\) and \(q\) are true or both are false |
| \(\oplus\) | XOR, exclusive disjunction | \(\begin{matrix} \oplus & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix}\) | \(p \oplus q\) is true if either \(p\) or \(q\) are true, but not both |
| Symbol | Term | Description |
|---|---|---|
| \(\top\) | tautology | always true, for example \(p \lor \lnot p\) |
| \(\bot\) | contradiction | always false, for example \(p \land \lnot p\) |
| Name | Disjunction | Conjunction |
|---|---|---|
| idempotent | \(p \lor p \equiv p\) | \(p \land p \equiv p\) |
| commutative | \(p \lor q \equiv q \lor p\) | \(p \land q \equiv q \land p\) |
| associative | \((p \lor q) \lor r \equiv p \lor (q \lor r)\) | \((p \land q) \land r \equiv p \land (q \land r)\) |
| distributive | \(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\) | \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\) |
| identity | \(p \lor \bot \equiv p\) | \(p \land \top \equiv p\) |
| domination | \(p \lor \top \equiv \top\) | \(p \land \bot \equiv \bot\) |
| De Morgan’s laws | \(\lnot (p \lor q) \equiv \lnot p \land \lnot q\) | \(\lnot (p \land q) \equiv \lnot p \lor \lnot q\) |
| absorptative | \(p \lor (p \land q) \equiv p\) | \(p \land (p \lor q) \equiv p\) |
| negation | \(p \lor \lnot p \equiv \top\) | \(p \land \lnot p \equiv \bot\) |
| double negation | \(\lnot \lnot p \equiv p\) |
\[ \begin{align} p \rightarrow q &\equiv \lnot p \lor q \\[8pt] p \rightarrow q &\equiv \lnot q \rightarrow \lnot p \\[8pt] p \lor q &\equiv \lnot p \rightarrow q \\[8pt] p \land q &\equiv \lnot (p \rightarrow \lnot q) \\[8pt] \lnot(p \rightarrow q) &\equiv p \land \lnot q \\[8pt] (p \rightarrow q) \land (p \rightarrow r) &\equiv p \rightarrow (q \land r) \\[8pt] (p \rightarrow r) \land (q \rightarrow r) &\equiv (p \lor q) \rightarrow r \\[8pt] (p \rightarrow q) \lor (q \rightarrow r) &\equiv p \rightarrow (q \lor r) \\[8pt] (p \rightarrow r) \lor (q \rightarrow r) &\equiv (p \land q) \rightarrow r \end{align} \]