Truth tables for extremely long expressions

Question

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?

Answer 1

$$ \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).

Answer 2

Hint: I would rewrite the expression to make it easier to evaluate. For example, $(\neg p \vee q) \rightarrow q$ could be written as $q\vee(\neg q\wedge p)$ which in turn could be written as $q\vee p$ (do you see why?).

You can continue to make similar simplifications.

Answer 3

Since there are only two variables in your expression, you will only need to evaluate it four times. Using the method you described, you can evaluate the expression outwards one step at a time using the following columns:

$p\ |\ q\ |\ \lnot p\lor q\ |\ \left(\lnot p\lor q\right)\rightarrow q\ |\ \left(\left(\lnot p\lor q\right)\rightarrow q\right)\land p\ |\ p \lor \left(\lnot\left(\left(\left(\lnot p\lor q\right)\rightarrow q\right)\land p\right)\right)$

Really, the only thing of interest is the last column, the others are merely intermediate steps. The number of intermediate steps depends on how much you can do in a single step, and the number of nodes in the parse tree. The latter only grows linearly with the length of the expression.

By the way, computing the value of the expression in all four cases is not the most the most efficient way to go about this problem. Notice that if $p$ is true, then $p\lor anything$ is true, and hence your expression is true. Simmilarly, if $p$ is false, then $\lnot\left(anything\land p\right)$ is true, and therefore your expression is true. Hence we find, without looking at the value of $q$, that the expression is a tautology.