One of the questions from my text book says to
Write the truth table for the expression:
$$
p \vee ( \neg (((\neg p \vee q) \rightarrow q) \land p ))
$$
and state whether it is a tautology, contradiction or neither.
Please do not think I am asking you to do my work for me, but I don't understand how such a large expression can have a truth table that wouldn't take extremely long to write?
I understand how to write truth tables for smaller expressions such us
$$
p \rightarrow \neg ( p \land q )
$$
Where the columns would look like this:
| $p$ | $q$ | $p \land q$ | $\neg (p \land q)$ | $p \rightarrow \neg (p \land q)$
And then I can fill p and q with T, T, F, F and T, F, T, F respectively and work out the values for the rest.
Regardless of being a much smaller expression, it still has 5 columns, and I was wondering if there was a better way to write the truth tables for larger expressions?
Best Answer
$$ \newcommand{\T} {\color{blue}{\text{T}}} \newcommand{\F} {\color{red}{\text{F}}} \newcommand{\?} {\color{green}{\text{?}}}$$
This is one way of writing truth tables that comes out pretty nice. Start by writing out the 4 cases for $p$ and $q$:
$$\begin{array} {cccccccccccc} % p &\lor &\lnot &(((&\lnot &p &\lor &q) &\implies &q) &\land & p) \\ % \T & & && & \T & & \T & & \T & & \T \\ % \T & & && & \T & & \F & & \F & & \T \\ % \F & & && & \F & & \T & & \T & & \F \\ % \F & & && & \F & & \F & & \F & & \F \\ % \end{array}$$
Then start filling in the table 1 operator at a time, starting with the first operator evaluated, the $\lnot$ in the $\lnot p$:
$$\begin{array} {cccc|c|ccccccc} % p &\lor &\lnot &(((&\lnot &p &\lor &q) &\implies &q) &\land & p) \\ % \T & & && \F & \T & & \T & & \T & & \T \\ % \T & & && \F & \T & & \F & & \F & & \T \\ % \F & & && \T & \F & & \T & & \T & & \F \\ % \F & & && \T & \F & & \F & & \F & & \F \\ % \end{array}$$
Then the value of the $\lor$ in $\lnot p \lor q$, using the values in the $\lnot$ column and the $q$ column:
$$\begin{array} {cccccc|c|ccccc} % p &\lor &\lnot &(((&\lnot &p &\lor &q) &\implies &q) &\land & p) \\ % \T & & && \F & \T & \T & \T & & \T & & \T \\ % \T & & && \F & \T & \F & \F & & \F & & \T \\ % \F & & && \T & \F & \T & \T & & \T & & \F \\ % \F & & && \T & \F & \T & \F & & \F & & \F \\ % \end{array}$$
Continue filling in for $\implies$ next, then $\land$, then $\lnot$, then $\lor$:
$$\begin{array} {c|c|cccccccccc} % p &\lor &\lnot &(((&\lnot &p &\lor &q) &\implies &q) &\land & p) \\ % \T & \? & \? && \F & \T & \T & \T & \? & \T & \? & \T \\ % \T & \? & \? && \F & \T & \F & \F & \? & \F & \? & \T \\ % \F & \? & \? && \T & \F & \T & \T & \? & \T & \? & \F \\ % \F & \? & \? && \T & \F & \T & \F & \? & \F & \? & \F \\ % \end{array}$$
If all the values in the final column are true, then the statement is a tautology. If all the values in the final column are false, then it is a contradiction. Otherwise, it could be either (depends on the values of $p$ and $q$, not quite right to say neither).