1

What I am given:

[(p∧r)∧(p→ q)]→q

What I did:

⇔ [(p∧r)∧( ¬p V q)] → q: Implication

⇔ ¬ [(p∧r)∧( ¬p V q)] V q: Implication

⇔ ¬ (p∧r) V ¬ ( ¬p V q) V q: De Morgan

⇔ (¬p V ¬r) V (¬ ¬p ∧ ¬q) V q: De Morgan

⇔(¬p V ¬r) V (p ∧ ¬q) V q: Double Negation

⇔(¬p V ¬r) V (q V p) ∧ (q V ¬q): Distributive

⇔(¬p V ¬r) V (q V p) ∧ T: Tautology

⇔(¬p V ¬r) V (q V p): Identity

⇔(¬p V p) V (q V r): Associative

⇔T V (q V r): Tautology

⇔ T Domination law

I do not think this is right. Can someone provide insight?

Thanks

Zevias
  • 109

1 Answers1

0

Your working is completely correct. A slightly more intuitive way to go about it is to try and make the expression false and arrive at an impossibility.

The outer operator is an implication, so if this is false then $q$ must be false and $(p\land r)\land(p\to q)$ must be true, which in turn means that $p,r,p\to q$ must all be true. But then assigning $p,r$ as true means $p\to q$ is false, a contradiction. So the whole expression is a tautology.

As for the bonus question, $p\mid p$ (NAND) is equal to $\neg p$. This can be seen by truth table.

Parcly Taxel
  • 103,344
  • That is fantastic to hear! I really appreciate it. What throws me off are the parenthesis. I am so used to algebra and calculus where parenthesis means you can only work inside them before moving on. This is not the case in discrete math, right? – Zevias May 28 '19 at 18:34
  • @Zevias Since you are new, I'd like you to upvote and accept my answer. You will see a tick to the left; click it and it should turn green. – Parcly Taxel May 28 '19 at 18:35
  • I ticked the green check. I upvote you but it says it won't be publicly displayed since I have less than 15 rep – Zevias May 28 '19 at 18:36
  • @Zevias It's OK... ask more good questions. The reputation will come with that. – Parcly Taxel May 28 '19 at 18:37
  • SO parenthesis and order of operations is not the same in discrete math? For example, when I first started proving [(p∧r)∧(p→ q)]→q, I thought I had to only work on the left side before utilizing the right handed q. But once I apply implication, I can work with any side in any order? – Zevias May 28 '19 at 19:57
  • @Zevias I am treating $\to$ as an operator, not like $=$. There is still an order of operations in Boolean expressions, but they are not as well-defined when it comes to implication, and so it is advisable to bracket around $\land$ and $\lor$. – Parcly Taxel May 28 '19 at 19:59