Prove each equivalence by using the rules for semantic equivalence

820 Views Asked by At

Having some issue with some logic - the examples I've been provided with arn't very helpful so I can have no idea where to start. The question is to prove;

           (p ∨ q) ∧ (q ⇒ p) ≡ p

but I have no idea where to start. Attached below are the rules I'm using.

 A ∧ A ≡ A, A ∨ A ≡ A                                         idempotence
 A ∧ B ≡ B ∧ A, A ∨ B ≡ B ∨ A                                 commutativity
 A ∧ (B ∧ C ) ≡ (A ∧ B) ∧ C , A ∨ (B ∨ C ) ≡ (A ∨ B) ∨ C      associativity
 A ∧ (A ∨ B) ≡ A, A ∨ (A ∧ B) ≡ A                             absorption
 A ∧ (B ∨ C ) ≡ (A ∧ B) ∨ (A ∧ C )                            distributivity
 A ∨ (B ∧ C ) ≡ (A ∨ B) ∧ (A ∨ C )                            distributivity
 A ∧ (¬A) ≡ false, A ∨ (¬A) ≡ true                            negation
 ¬(¬A) ≡ A                                                    double negation
 ¬(A ∧ B) ≡ (¬A) ∨ (¬B), ¬(A ∨ B) ≡ (¬A) ∧ (¬B)               de Morgan
 A ⇒ B ≡ (¬A) ∨ B                                             implication
 A ⇔ B ≡ (A ⇒ B) ∧ (B ⇒ A)                                  bi-implication

My first guess is to use the rule of implication first but to be honest, I have no idea where to start.

Would really appreciate any help anyone can provide.

Thanks.

2

There are 2 best solutions below

1
On BEST ANSWER

Another solution:

$(p \lor q) \land(q \rightarrow p)$

$(p \lor q) \land(\neg q \lor p)$, implication

$(p \lor q) \land (p \lor \neg q)$, commutativity

$p \lor (q \land \neg q)$, distributivity

$p \lor \text{false}$, negation

$p \lor (p \land \neg p)$, negation again

$p$, absorption

0
On

A general rule of thumb is always to simplity: Replace $\rightarrow$, push in $\neg$, distribute $\lor$ over $\land$ (and $\land$ over $\lor$)

I omit some parenthesis, all these are justified by associativity. I also distribute on both sides, which uses commutivity implicitly.

$(p \lor q) \land (q \rightarrow p)$

$(p \lor q) \land (\neg q \lor p)$, by implication

$((p \lor q) \land \neg q )\lor ((p \lor q)\land p)$, by distributivity

$(p \land \neg q) \lor (q \land \neg q) \lor (p \land p) \lor (q\land p)$, by distributivity again

$(p \land \neg q) \lor \text{false} \lor p \lor (q\land p)$, by negation and idempotence

$p$, by absorption and the rule $A \lor \text{false} = A$, which you should have.