3

I have

$F(p, q) = (p \land q) \lor (\lnot p \land q)$

and i need to prove that

$\lnot F(\lnot p, \lnot q) \Leftrightarrow F(p, q)$

is not tautology.

I made truth table for $F(p, q)$ and it looks like this:

$$ \begin{array}{c||c||c} p & q & F(p,q)\\ \hline \top & \top & \top\\ \hline \top & \bot & \bot\\ \hline \bot & \top &\top\\ \hline \bot & \bot &\top\\ \end{array} $$

After simplifying $\lnot F(\lnot p, \lnot q)$ i got

$\lnot F(\lnot p, \lnot q) = (p \lor q) \land (\lnot p \lor q)$ .

Now, I am not sure how to make truth table for this and how to compare these two.

fisherman
  • 33

2 Answers2

1

Try filling in the rest of this truth table:

\begin{array}{c|c|c|c|c|c} p & q & F(p,q) & \lnot p &\lnot q& F(\lnot p,\lnot q)&\lnot F(\lnot p,\lnot q)\\ \hline \top & \top & \top & \bot & \bot \\ \hline \top & \bot & \bot\\ \hline \bot & \top &\top\\ \hline \bot & \bot &\bot\\ \end{array}

You can easily find the values of $F(\lnot p,\lnot q)$ by using the first three columns of the table. For example, on the first line of the table $\lnot p = \bot$ and $\lnot q = \bot$, and you find the value of $F(\bot,\bot)$ on the last line of the table.

I find that if there is any amount of complication in the logical expressions, it almost always makes truth-table problems much easier if I insert auxiliary columns like this to show the intermediate steps of the calculations. Of course you still want to compare only the columns for $F(p, q)$ and $\lnot F(\lnot p,\lnot q)$ in the end.

As you may discover, there is really no need to "simplify" $\lnot F(\lnot p,\lnot q)$ if you use the truth-table entries you already discovered for $F(p, q)$ in this manner.

Edit: As pointed out by Mauro ALLEGRANZA, the entry for $F(p,q)$ on the last line was incorrect in the truth table originally presented in this answer (as well as in the truth table in the original question, from which that entry was copied). This does not invalidate the method described in this answer, but it does have an effect on the values that result on the second line of the table.

David K
  • 98,388
  • It is more elegant that way, but I somehow get different results for $\lnot F(\lnot p, \lnot q)$ column using that method. – fisherman Oct 01 '15 at 18:01
  • When I fill @mrp table $\lnot F(\lnot p, \lnot q)$ column is different. – fisherman Oct 01 '15 at 18:18
  • Again, adding columns for intermediate results can help. Try making columns for $\lnot p$, $\lnot p \lor q$, and $p \lor q$ in the other table and see if the conjunction of those last two columns is what you have in the column for $\lnot F(\lnot p, \lnot q)$. The full formula for $\lnot F(\lnot p, \lnot q)$ is a lot to try to evaluate all at once, and errors are likely to occur. – David K Oct 01 '15 at 18:36
  • For $⊥,⊥$ : $F(p,q)=(p∧q)∨(¬p∧q)$ is $(⊥∧⊥)∨(⊤∧⊥)≡(⊥∨⊥)≡⊥$. – Mauro ALLEGRANZA Oct 01 '15 at 19:41
  • @MauroALLEGRANZA Thanks for noticing. I had just copied the values from the original question without checking. I have corrected this in my copy of the table. This also raises doubt about what result is desired: are we supposed to prove that the formula in the question is not a tautology (as the question is written), or that it is a tautology, or simply determine whether it is a tautology? – David K Oct 01 '15 at 22:33
  • @DavidK From textbook: "If $F(p, q) = (p \land q) \lor (\lnot p \land q)$ ,prove that $F(p, q) \Leftrightarrow \lnot F( \lnot p, \lnot q)$ is not tautology." It is probably typo. :) – fisherman Oct 06 '15 at 13:56
  • @fisherman Yes, that seems to be the most likely explanation. There are sometimes small errors like this in textbooks. I stumbled over one of these myself just a few days ago. – David K Oct 06 '15 at 22:49
0

You found out that $\neg F(\neg p, \neg q) = (p \lor q) \land (\neg p \lor q)$, so now simply extend your truth table:

$$ \begin{array}{c||c||c||c} p & q & F(p, q) = (p \land q) \lor (\lnot p \land q) & \neg F(\neg p, \neg q) = (p \lor q) \land (\neg p \lor q)\\ \hline \top & \top & \top & ?\\ \hline \top & \bot & \bot & ?\\ \hline \bot & \top &\top & ?\\ \hline \bot & \bot &\top & ?\\ \end{array} $$

If the two columns $F(p,q)$ and $\neg F(\neg p, \neg q)$ have the same entries, then $F(p,q) \iff \neg F (\neg p, \neg q)$ is a tautology, otherwise it is not.

mrp
  • 5,086