A proposition is a declarative sentence that can either be true or false.


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


Symbol Term Description
\(\forall\) universal \((\forall x)P(x)\) symbolises the predicate \(P(x)\) is true for every value in the universe of discourse
\(\exists\) existential \((\exists x)P(x)\) the predicate \(P\) holds for at least one \(x\)


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