∼p∨(∼p∧q)≡∼p∧∼q , prove logical equivalence

3.1k Views Asked by At

Our teacher gave us this equivalence to prove in our final exam but almost all of us said that it was not provable and we did not solve it and now we asked him (The Teacher) and he says that it is provable. I was unable to prove it even by using truth table and he asked us to prove it by using the theorems for logical equivalence.

So now we have our grades at stake so please solve it so that I may know that either I'm wrong or the Teacher is!

The theorems are:

  1. Commutative laws: p∧q ≡ q∧p , p∨q ≡ q∨p

  2. Associative laws: (p∧q)∧r ≡ p∧(q∧r) , (p∨q)∨r ≡ p∨(q∨r)

  3. Distributive laws: p∧(q∨r) ≡ (p∧q)∨(p∧r), p∨(q∧r) ≡ (p∨q)∧(p∨r)

  4. Identity laws: p∧t ≡ p , p∨c ≡ p

  5. Negation laws: p∨∼p ≡ t , p∧∼p ≡ c

  6. Double negative law: ∼(∼p) ≡ p

  7. Idempotent laws: p∧p ≡ p , p∨p ≡ p

  8. Universal bound laws: p∨t≡t ,p∧c≡c

  9. De Morgan’s laws: ∼(p∧q) ≡ ∼p∨∼q ,∼(p∨q) ≡ ∼p∧∼q

  10. Absorption laws: p∨(p∧q) ≡ p ,p∧(p∨q) ≡ p

  11. Negations of t and c: ∼t ≡ c , ∼c ≡ t

4

There are 4 best solutions below

0
On BEST ANSWER

I'd say you're right. Using 10, $∼p∨(∼p∧q)≡∼p$, but $∼p \not \equiv ∼p∧q.$

0
On

If $p$ is false, the left side is true since it's an "or" with one term true (since $p$ false, (not p) is true). But suppose at the same time that $q$ is true. Then the right is false, since it's an "and" with one term false (since $q$ is true, (not q) is false). So it isn't an equivalence.

0
On

If $p$ is false and $q$ is true then $\neg p\wedge\neg q$ is false and $\neg p\vee(\neg p\wedge q)$ is true.

So there no logical equivalence.

0
On

Hint

Yes you are right. This is not an equivalence. In fact $$∼p∨(∼p∧q)≡∼p$$using a truth table.