Question 1 of 12

Question 1

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Two compound propositions built from primitive statements $p,q,r$ using $\to$, $\land$, $\lor$.

Find. (a) Whether $[p\to(q\to r)]\to[(p\to q)\to(p\to r)]$ is a tautology. (b) Whether $(p\lor q)\to[q\to(p\land q)]$ is a tautology.

Approach. A compound statement in $n$ primitive variables is a tautology exactly when its truth table has "T" in every one of the $2^n$ rows, so build each table directly.

1. a) Build the truth table for the 3-variable statement. Write $A=[p\to(q\to r)]$ and $B=[(p\to q)\to(p\to r)]$; the statement is $A\to B$.

   Part (a) truth table

   $p$	$q$	$r$	$q\to r$	$A=p\to(q\to r)$	$p\to q$	$p\to r$	$B$	$A\to B$
   T	T	T	T	T	T	T	T	T
   T	T	F	F	F	T	F	F	T
   T	F	T	T	T	F	T	T	T
   T	F	F	T	T	F	F	T	T
   F	T	T	T	T	T	T	T	T
   F	T	F	F	T	T	T	T	T
   F	F	T	T	T	T	T	T	T
   F	F	F	T	T	T	T	T	T

   Every row of the final column is T, so $\boxed{A\to B \text{ is a tautology}}$.
2. b) Build the truth table for the 2-variable statement. Write $C=p\lor q$ and $D=q\to(p\land q)$; the statement is $C\to D$.

   Part (b) truth table

   $p$	$q$	$C=p\lor q$	$p\land q$	$D=q\to(p\land q)$	$C\to D$
   T	T	T	T	T	T
   T	F	T	F	T	T
   F	T	T	F	F	F
   F	F	F	F	T	T

   Row $p=F,q=T$ gives $C\to D = F$, so the statement is $\boxed{\text{not a tautology}}$: with $p$ false and $q$ true, $p\lor q$ is true but $q\to(p\land q)$ is false (since $p\land q$ is false), so the whole conditional is false.