Confused about logical statement simplification

Question

We are trying to solve an assignment where we have to simplify a logical statement. Can anyone explain what is going on this step? $$(\neg P\lor \neg Q)\land (\neg P\lor Q) \equiv \neg P\lor(\neg Q\land Q)$$

How do we get from $(\neg P\lor \neg Q)\land(\neg P \lor Q)$ to $\neg P\lor(\neg Q\land Q)$? What simplification rule is being used here?

Use Distributivity. – Mauro ALLEGRANZA Sep 12 '18 at 12:55 — Mauro ALLEGRANZA, Sep 12 '18 at 12:55

score 1 · Answer 1 · answered Sep 12 '18 at 12:54

1

This is distributivity of disjunction over conjunction: $A \vee (B \wedge C)$ is equivalent to $(A \vee B) \wedge (A \vee C)$.

answered Sep 12 '18 at 12:54

Daniel Mroz

2,346

score 1 · Accepted Answer · answered Sep 12 '18 at 12:55

1

This follows from the Distributive law.

We have $$(P\land (Q\lor R)) \equiv (P\land Q)\lor (P\land R)$$ $$(P\lor (Q\land R)) \equiv (P\lor Q)\land (P\lor R)$$

answered Sep 12 '18 at 12:55

GoodDeeds

11,185
3
22
42

Confused about logical statement simplification

2 Answers2