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\)

Conditional equivalences

\[ \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} \]