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}