home

Propositions

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

Notation

By convention \(p\), \(q\), \(r\), \(s\), or \(t\) are used to denote statements within an expression.

Connectives

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

Constants

Symbol Term Description
\(\top\) tautology always true, for example \(p \lor \lnot p\)
\(\bot\) contradiction always false, for example \(p \land \lnot p\)

Quantifiers

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

Laws

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