How to write the truth table for a proposition and then determine its shortest possible equivalent expression?

Question

$$(r\leftrightarrow \neg p)\wedge p\wedge (q\rightarrow \neg (p\oplus q))$$

Steps I took:

I broke up the proposition into bits and pieces and assigned them to variables as such:

$a=(p\oplus q)$, $b=(q\rightarrow \neg a)$, $c=(r\leftrightarrow \neg p)$

I wrote up the following truth table:

After looking at the truth table, I came up with $(r\leftrightarrow \neg p)\wedge p$ as the shortest possible equivalent expression. However, I don't think this is the right answer. How do I go about figuring the shortest possible equivalent expression?

I put it into wolfram alpha and got that same answer, but my question is why? How can I arrive at that solution by myself? — Cherry_Developer, Oct 23 '15 at 20:51
check your table, see in which rows you have truth for both b,c and p. You will find that it only depends on r and p. — Loreno Heer, Oct 23 '15 at 20:52
I see that; however, this is only after it has been pointed out to me. How can I find this solution more easily? — Cherry_Developer, Oct 23 '15 at 20:55
I guess the easiest way is like you did, make a table and look at the rows where your formula holds. later you will study techniques which allow you to use easier ways to simplify logic formulas. — Loreno Heer, Oct 23 '15 at 20:57
So, at this point, I have to literally go through all the rows and columns to see where it will be the same truth values as my original expression? That sounds very inefficient. — Cherry_Developer, Oct 23 '15 at 20:59
Introduction to formal proofs, scratched the surface of truth tables, logical operators, and De Morgan's laws. — Cherry_Developer, Oct 23 '15 at 21:02
oh, sorry. I took time again to look at your table and I see you made some mistakes. this changes the result of course. check your values again for $a$ etc.. From deMorgan laws you can also directly manipulate your formula to get it into a more simple form, but it takes some practice. — Loreno Heer, Oct 23 '15 at 21:06
I will check in a moment, but it seems like my end result was correct. (I plugged the proposition into an online truth table generator.) — Cherry_Developer, Oct 23 '15 at 21:07

score 1 · Answer 1 · answered Oct 23 '15 at 21:15

1

$$(r\leftrightarrow \neg p)\wedge p\wedge (q\rightarrow \neg (p\oplus q))$$

is the same as

$$\neg r\wedge p\wedge (q\rightarrow \neg (p\oplus q))$$

because $$\neg p \wedge p$$ can not be true. This furthermore simplifies to

$$\neg r\wedge p$$

because we know $p$ must be true and therefore $$\neg (p\oplus q)$$ is the same as $$q.$$

answered Oct 23 '15 at 21:15

Loreno Heer

4,460

How did you get from $(r\leftrightarrow \neg p)$ to $p\wedge \neg r$ ? – Cherry_Developer Oct 23 '15 at 21:43

How to write the truth table for a proposition and then determine its shortest possible equivalent expression?

1 Answers1