3
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ @SBareS Sorry about that, fixed it $\endgroup$ – Samir Chahine Aug 1 '16 at 13:08
  • $\begingroup$ (yes, q or not q and p, so just q or p), so I can do that? Simplify until a truth table is doable? @MPW $\endgroup$ – Samir Chahine Aug 1 '16 at 13:23
  • 1
    $\begingroup$ Sorry, I deleted that comment and turned it into an answer. Yes, you can always replace anything by something equivalent to it. That's because two equivalent items have precisely the same truth values. At least, that's how I would approach it. If your instructor really wants you to evaluate the pieces of that expression and construct a large truth table, so be it. $\endgroup$ – MPW Aug 1 '16 at 13:25
  • $\begingroup$ That expression most certainly does not have an «extremely long» truth table by any reasonable standards... $\endgroup$ – Mariano Suárez-Álvarez Aug 1 '16 at 20:52
  • 1
    $\begingroup$ This question had clarity, used latex, and the questioner was very responsive to posts and comments to his question. This question deserves to be upvoted. $\endgroup$ – DanielV Aug 1 '16 at 23:44
6
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ This is an amazing answer, but I'm just trying to get my head around it. Why is the first operator evaluated the $\neg$ in the $\neg p$ ?, wouldn't it be the first $\vee$ ? Could you please explain how you're deciding which operators go first? Also, when you say fill in the operators, am I filling in .. say $\neg$ as if it were actually | $\neg p$ |? And for $\vee$, is that the same as | $p \vee q$ | ? If this is the case then I understand how to do the rest. Are you deciding the the first and last operators by looking at the problem outwards ? Because that would make sense $\endgroup$ – Samir Chahine Aug 1 '16 at 22:24
  • $\begingroup$ @SamirChahine I'm assuming $\lnot p \lor q$ is meant to mean $(\lnot p) \lor q$, so the $\lnot$ is evaluated before the $\lor$. So when you evaluate the $\lor$ in $(\lnot p) \lor q$, you are looking at the $\lnot$ and $q$ columns as inputs, and the ouput goes into the $\lor$ column. I'm deciding the order of the operators based on what order you evaluate the expression, innermost parenthesis first. Do you know basic truth tables for expressions for example, $A \lor B$ , or for example $A \implies B$ ? $\endgroup$ – DanielV Aug 1 '16 at 22:34
  • $\begingroup$ Okay, thanks for clearing that up. Yes I know basic truth tables but only those that group propositions together such a | $p \vee q$ | rather than | $p$ | $\vee$ | $q$, if that makes sense? Which is why these sorts of truth tables confuse me $\endgroup$ – Samir Chahine Aug 1 '16 at 22:48
  • $\begingroup$ If you tell me the 4 values (top to bottom) that you get for the $\implies$ column, then I will tell you if it is correct. It might help if you explain how you get those values. $\endgroup$ – DanielV Aug 1 '16 at 22:55
  • 1
    $\begingroup$ @SamirChahine You are correct that it is a tautology. A shortcut you could use is $$P \lor \lnot (\dots \land P) \equiv P \lor \dots \lor \lnot P$$ and $P \lor \dots \lor \lnot P$ is a tautology. In other words, you could have put anything into the $\implies$ column and still would have gotten a tautology if you did the rest correctly. $\endgroup$ – DanielV Aug 2 '16 at 2:38
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.