A proposition is a statement that is either true or false. We can combine one or more propositions to create more complicated propositions using conjunctions. Those conjunctions include:

1. Negation: $\neg p$, meaning not $p$.
2. Inclusive Or: $p\vee q$, meaning $p$ or $q$ (could be both).
3. And: $p\wedge q$, meaning $p$ and $q$.
4. Exclusive Or: $p\oplus q$, meaning either $p$ or $q$.
5. Implies: $p\Longrightarrow q$, meaning if $p$ then $q$ ($p$ implies $q$). $p$ and $q$ are called the hypothesis and the conclusion, respectively.
6. Equivalence: $p\Longleftrightarrow q$, meaning $p$ if and only if $q$. $p\Longleftrightarrow q$ is shorthand for $(p\Longrightarrow q)\wedge(p\Longleftarrow q)$.

Definition. A propositional formula is defined by the following.

PF1. Any propositional variable (such as $p$ and $q$) is a formula.

PF2. If $\alpha$ and $\beta$ are formulas, so are

1. $\alpha\vee\beta$
2. $\alpha\wedge\beta$
3. $\neg\alpha$

For example $\neg(p\vee q)$ is a formula.

Truth Tables

The truth value of a formula can be found by its truth table. A formula is said to be satisfiable if at least one truth assignment satisfies it. A formula is called a tautology if every truth assignment satisfies it. A formula is said to be unsatisfiable if no truth assignment satisfies it.

Here are some examples.

1. The truth table of $\neg p$ $$\begin{array}{|c|c|}\hline p & \neg p\\\hline T & F\\\hline F & T\\\hline\end{array}$$
2. The truth table of $p\wedge q$ $$\begin{array}{|c|c|c|}\hline p & q & p\wedge q\\\hline T & T & T\\\hline T & F & F\\\hline F & T & F\\\hline F & F & F\\\hline\end{array}$$
3. The truth table of $p\wedge\neg p$. $$\begin{array}{|c|c|c|}\hline p & \neg p & p\wedge\neg p\\\hline T & F & F\\\hline F & T & F\\\hline\end{array}$$ $p\wedge\neg p$ is unsatisfiable.
4. The truth table of $p\vee q$ $$\begin{array}{|c|c|c|}\hline p & q & p\vee q\\\hline T & T & T\\\hline T & F & T\\\hline F & T & T\\\hline F & F & F\\\hline\end{array}$$
5. The truth table of $p\vee\neg p$. $$\begin{array}{|c|c|c|}\hline p & \neg p & p\vee\neg p\\\hline T & F & T\\\hline F & T & T\\\hline\end{array}$$ $p\vee\neg p$ is a tautology.
6. The truth table of $p\oplus q$ $$\begin{array}{|c|c|c|}\hline p & q & p\oplus q\\\hline T & T & F\\\hline T & F & T\\\hline F & T & T\\\hline F & F & F\\\hline\end{array}$$
7. The truth table of $p\Longrightarrow q$ $$\begin{array}{|c|c|c|}\hline p & q & p\Longrightarrow q\\\hline T & T & T\\\hline T & F & F\\\hline F & T & T\\\hline F & F & T\\\hline\end{array}$$ It must be puzzling for readers as to why a false hypothesis can imply anything. Remember that we are doing propositional logic and any statement of our concern should be either true or false. So it comes down to the decision on what truth value to assign to a conditional statement with false hypothesis. If we were to assign the truth value F, all hell will break loose. Here is why. Consider the conditional statement “if $p$ then $\neg p$” and assume that $p$ is false. That must mean $\neg p$ is true since $p$ is a proposition. However, we decided to assign the truth value $F$ to the conditional statement hence $\neg p$ must also be false. This is a contradiction! To avoid this sort of disastrous contradiction, we should assign the truth value T to a conditional statement with false hypothesis. We claimed without a proof that the empty set is a subset of every set here. The statement “$x\in\emptyset\Longrightarrow x\in A$” is always true because the hypothesis $x\in\emptyset$ is false. Hence $\emptyset\subseteq A$ for any set $A$.
8. The truth value of $p\Longleftrightarrow q$. $$\begin{array}{|c|c|c|c|c|}\hline p & q & p\Longrightarrow q & p\Longleftarrow q & p\Longleftrightarrow q\\\hline T & T & T & T & T\\\hline T & F & F & T & F\\\hline F & T & T & F & F\\\hline F & F & T & T & T\\\hline\end{array}$$
9. The truth value of $p\wedge q\Longrightarrow r$. $$\begin{array}{|c|c|c|c|c|}\hline p & q & r & p\wedge q & p\wedge q\Longrightarrow r\\\hline T & T & T & T & T\\\hline T & T & F & T & F\\\hline T & F & T & F & F\\\hline T & F & F & F & T\\\hline F & T & T & F & T\\\hline F & T & F & F & T\\\hline F & F & T & F & T\\\hline F & F & F & F & T\\\hline\end{array}$$

When two fomulae $\alpha$ and $\beta$ have the same truth table, we say $\alpha$ is logically equivalent to $\beta$ and write $\alpha\equiv\beta$.

Theorem. $p\Longrightarrow q\equiv\neg p\vee q$.

Proof. $$\begin{array}{|c|c|c|c|c|}\hline p & q & p\Longrightarrow q & \neg p & \neg p\vee q\\\hline T & T & T & F & T\\\hline T & F & F & F & F\\\hline F & T & T & T & T\\\hline F & F & T & T & T\\\hline\end{array}$$

Theorem. $p\oplus q\equiv(p\wedge\neg q)\vee(\neg p\wedge q)$.

Proof. Left to readers as an exercise.

$\vee$ and $\wedge$ can be considered as operations on formulae and the following laws hold:

Commutative Laws. For any formulae $\alpha$ and $\beta$, \begin{align*}\mbox{(CL1)}\ \alpha\vee\beta&\equiv\beta\vee\alpha\\\mbox{(CL2)}\ \alpha\wedge\beta&\equiv\beta\wedge\alpha\end{align*}

Associative Laws. For any formulae $\alpha$, $\beta$ and $\gamma$, \begin{align*}\mbox{(AL1)}\ (\alpha\vee\beta)\vee\gamma&\equiv\alpha\vee(\beta\vee\gamma)\\\mbox{(AL2)}\ (\alpha\wedge\beta)\wedge\gamma&\equiv\alpha\wedge(\beta\wedge\gamma)\end{align*}

Distributive Laws. For any formulae $\alpha$, $\beta$ and $\gamma$, \begin{align*}\mbox{(DL1)}\ \alpha\vee(\beta\wedge\gamma)&\equiv(\alpha\vee\beta)\wedge(\alpha\vee\gamma)\\\mbox{(DL2)}\ \alpha\wedge(\beta\vee\gamma)&\equiv(\alpha\wedge\beta)\vee(\alpha\wedge\gamma)\end{align*}

These laws can be used to show two formulae are logically equivalent without using truth table. Proof by a truth table can be really cumbersome when concerned formulae are complicated.

References.

[1] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019