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.



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

| cite | improve this answer | |
  • 1
    $\begingroup$ Ah, that is the trick for removing $\bot$ from a disjunction. Nice. $\endgroup$ – James Feb 17 '16 at 18:26

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.