Prove ((p→q)∧q) and q are equivalent using logic laws

Question

So far I have

((p→q)∧q)
≡ ((~p∨q)∧q)
≡ (~p∧q)∨(q∧q) $\; \; \; \; \;$(Distributive law)
≡ (~p∧q)∨q

But then I got stuck. And I'm not sure if what I've got so far is correct. Any help is greatly appreciated!

See this post: apply Distributivity to the RHS in the form: $(\lnot p∨q) ∧ (q ∨ \bot)$ to get: $q \lor (\lnot p \land \bot)$ — Mauro ALLEGRANZA, Oct 04 '23 at 08:18

score 0 · Answer 1 · answered Oct 04 '23 at 08:14

0

Use the Absorption laws $$a \land (a \lor b) \equiv a$$ $$a \lor (a \land b) \equiv a$$ We can easily verify this.

answered Oct 04 '23 at 08:14

Ajin Shaji Jose

752

See here for more info https://en.wikipedia.org/wiki/Absorption_law – Ajin Shaji Jose Oct 04 '23 at 08:15
Yes, but maybe the issue is how to prove it... If we rely on truth table, the original problem is easily solved. – Mauro ALLEGRANZA Oct 04 '23 at 08:17
1

@MauroALLEGRANZA the OP has to add more context. In standard courses, we are told to verify De Morgan's law, Absorption law, Double Negation law, Idempotent etc then use them freely. – Ajin Shaji Jose Oct 04 '23 at 08:21
I wonder if there is another law that I can use to solve this problem. We have not yet covered Absorption laws but we were still assigned this problem. – Biki Oct 04 '23 at 16:29
@Biki maybe there is a method. but next step is surely not Distributive law since that loops between $(\neg p \lor q) \land q$ and $(\neg p \land q) \lor q$ – Ajin Shaji Jose Oct 04 '23 at 18:51
i agree with @MauroALLEGRANZA. you have not proven anything by simply stating it is so via a derived rule – RyRy the Fly Guy Oct 05 '23 at 06:21

score 0 · Answer 2 · answered Oct 05 '23 at 05:27

I offer a proof of the syntactic equivalence $(p \to q) \wedge q \dashv \vdash q$ via natural deduction using only conditional proof and intro/elimination rules for conjunction:

$(p \to q) \wedge q \vdash q$

$ \begin{array}{11111} \{1\} & 1. & (p \to q) \wedge q & \text{premise} \\ \{1\} & 2. & q& \text{1 Conjunction Elimination} & \square\\ \end{array} $

$ q \vdash (p \to q) \wedge q$

$ \begin{array}{11111} \{1\} & 1. & q & \text{premise} \\ \{2\} & 2. & p & \text{Assumption for Conditional Proof} \\ \{1,2\} & 3. & p \wedge q & \text{1,2 Conjunction Introduction} \\ \{1,2\} & 4. & q& \text{3 Conjunction Elimination} \\ \{1\} & 5. & p \to q & \text{2,4 Conditional Proof} \\ \{1\} & 6. & (p \to q) \wedge q& \text{1,5 Conjunction Introduction} & \square \\ \end{array} $

Prove ((p→q)∧q) and q are equivalent using logic laws

2 Answers2