Propositional Logic

Exercise 2.c

Exercise

How many rows are there in the truth tables of

• $p \Rightarrow \neg p$
• $(p \land r \land t) \Leftrightarrow (q \land t)$

Answer

We know that in a proposition with $n$ propositional variables there are $2^n$ rows in the corresponding truth table. Therefore,

• In the first proposition $n=1$ ($p$), $2^n = 2^1 = 2$ rows
• In the second proposition $n=4$ ($p,r,t,q$), $2^n=2^4=16$ rows

Exercise 2.d

Exercise

Build the truth table of the following propositions

• $p \land \neg p$
• $(p \lor \neg q) \Rightarrow q$
• $(p\Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)$

Answer

• $$\begin{array}{c|c|c} p & \neg p & p \land \neg p \\ \hline \textbf{\color{green}T} & \textbf{\color{red}F} & \textbf{\color{red}F} \\ \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{red}F} \end{array}$$

• $$\begin{array}{c|c|c|c|c} p & q & \neg q & p \lor \neg q & (p \lor \neg q) \Rightarrow q \\ \hline \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{green}T} \\ \textbf{\color{green}T} & \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{red}F} \\ \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{green}T}\\ \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{red}F} \end{array}$$

• $$\begin{array}{c|c|c|c|c|c|c} p & q & p \Rightarrow q & \neg q & \neg p & \neg q \Rightarrow \neg p & (p\Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p) \\ \hline \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{green}T}\\ \textbf{\color{green}T} & \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{green}T}\\ \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T}\\ \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T} \end{array}$$

Exercise 3.a

Exercise

Show that $(\neg q \land (p \Rightarrow q)) \Rightarrow \neg p$ is a tautology

Proof

We first simplify via a couple of known equivalences

$$\begin{align*} (\neg q \land (p \Rightarrow q)) \Rightarrow \neg p &\equiv (\neg q \land (\neg p \lor q)) \Rightarrow \neg p & \text{(or formulation)} \\ &\equiv ((\neg q \land \neg p) \lor (\neg q \land q)) \Rightarrow \neg p & \text{(distributive law)}\\ &\equiv ((\neg q \land \neg p) \lor \textbf{\color{red}F}) \Rightarrow \neg p & \text{(negation law)} \\ &\equiv (\neg q \land \neg p) \Rightarrow \neg p & \text{(identity law)}\\ &\equiv \neg( q \lor p) \Rightarrow \neg p & \text{(De Morgan's)}\\ &\equiv p \Rightarrow ( q \lor p) & \text{(contrapositive)} \end{align*}$$

We build the truth table of this simplified expression

$$\begin{array}{c|c|c|c} p & q & q \lor p & p \Rightarrow (q \lor p) \\ \hline \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T} \\ \textbf{\color{green}T} & \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{green}T} \\ \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T}\\ \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{green}T} \end{array}$$

And thus the expression is a tautology.

Alternatively, we could have continued with the equivalences as follows

$$\begin{align*} p \Rightarrow ( q \lor p) &\equiv \neg p \lor ( q \lor p) & \text{(or formulation)}\\ &\equiv ( q \lor p) \lor \neg p & \text{(commutative law)}\\ &\equiv q \lor (p \lor \neg p) & \text{(associative law)}\\ &\equiv q \lor \textbf{\color{green}T} & \text{(negation law)}\\ &\equiv \textbf{\color{green}T} & \text{(domination law)}\\ \end{align*}$$

Exercise 4.a

Exercise

Show that $(p \land q) \Rightarrow (p \lor q)$ is a tautology

Proof

We proceed by building the truth table of the compound proposition

$$\begin{array}{c|c|c|c|c} p & q & p \land q & p \lor q & (p \land q) \Rightarrow (p \lor q)\\ \hline \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T} \\ \textbf{\color{green}T} & \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{green}T}\\ \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{green}T}\\ \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{green}T} \end{array}$$

And thus $(p \land q) \Rightarrow (p \lor q)$ is a tautology. Additionally, note that $(p \lor q) \Rightarrow (p \land q)$ and $(p \land q) \Leftrightarrow (p \lor q)$ are not tautologies (e.g. look at the second row of the truth table).

Exercise 4.b

Exercise

Show that $(\neg p \lor q) \Leftrightarrow (p \Rightarrow q)$ is a tautology

Proof

We proceed by building the truth table of the compound proposition

$$\begin{array}{c|c|c|c|c|c} p & q & \neg p & \neg p \lor q & p \Rightarrow q & (\neg p \lor q) \Leftrightarrow (p \Rightarrow q)\\ \hline \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T} \\ \textbf{\color{green}T} & \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{green}T}\\ \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T}\\ \textbf{\color{red}F} & \textbf{\color{red}F} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T} & \textbf{\color{green}T} \end{array}$$

And thus $(\neg p \lor q) \Leftrightarrow (p \Rightarrow q)$ is a tautology. Additionally, from the truth table we can see that $(\neg p \lor q) \Rightarrow (p \Rightarrow q)$ and $(\neg p \lor q) \Leftarrow (p \Rightarrow q)$ are also tautologies since, for both of them, only the cases $\textbf{\color{green}T} \Rightarrow \textbf{\color{green}T}$ and $\textbf{\color{red}F} \Rightarrow \textbf{\color{red}F}$ appear (see columns 4 and 5) in the corresponding truth tables.

The previous sentence is a general argument for the following theorem.

Theorem

Let $p$ and $q$ be propositions. If $p \Leftrightarrow q$ is a tautology, then $p\Rightarrow q$ and $q \Rightarrow p$ are also tautologies