# Laws of Algebra of Propositions Question (attempted, assistance required)

I'm trying to work out a class exercise and I've got myself stuck. Any help would be appreciated. Thank you.

I am to use use algebra of propositions to solve the following problem:

Show the below is true by the algebra of propositions:

(¬p ∨ q) ∧ (p ∨ ¬q) ≡ (p ∨ q) → (p ∧ q)

Here's what I have done so far:

Conditional and Biconditional: (¬p ∨ q) ∧ (p ∨ ¬q) ≡ (p → q) ∧ (q → p)

Current Conversion (No proof it is true yet): (p → q) ∧ (q → p) ≡ (p ∨ q) → (p ∧ q)

Conditional and Biconditional: (p → q) ∧ (q → p) ≡ p ↔ q

Current Conversion (No proof it is true yet): p ↔ q ≡ (p ∨ q) → (p ∧ q)

I have ran them through an online calculator for this type of thing and they are true but I cannot figure out the steps using the different Laws of Algebra of Propositions. If anyone could explain anything, I would be very grateful.

If you can use the following two equivalences:

$$p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$$

$$p \leftrightarrow q \equiv (p \land q) \lor (\neg p \lor \neg p)$$

Then you are indeed well on your way:

$$(\neg p \lor q) \land (p \lor \neg q) \text{ (Commutation)}$$

$$(\neg p \lor q) \land (\neg q \lor p) \text{ (Implication)}$$

$$(p \rightarrow q) \land (q \rightarrow p) \text{ (Equivalence)}$$

$$p \leftrightarrow q \equiv \text{ (Equivalence)}$$

$$(p \land q) \lor (\neg p \land \neg q) \text{ (DeMorgan)}$$

$$(p \land q) \lor \neg (p \lor q) \text{ (Commutation)}$$

$$\neg (p \land q) \lor (p \land q) \text{ (Implication)}$$

$$(p \land q) \to (p \land q)$$

However, if you don't have both of those equivalences regarding the biconditional, then you'll have to do it the hard way, and starting at the left will actually be a little easier to follow:

$$(p \lor q) \to (p \land q) \text{ (Implication)}$$

$$\neg (p \lor q) \lor (p \land q) \equiv \text{ (DeMorgan)}$$

$$(\neg p \land \neg q) \lor (p \land q) \equiv \text{ (Distribution)}$$

$$((\neg p \land \neg q) \lor p) \land ((\neg p \land \neg q)\lor q) \equiv \text{ (Distribution x 2)}$$

$$((\neg p \lor p) \land (\neg q \lor p)) \land ((\neg p \lor q) \land (\neg q \lor q)) \equiv \text{ (Commutation x 3)}$$

$$((p \lor \neg p) \land (p \lor \neg q)) \land ((\neg p \lor q) \land (q \lor \neg q)) \equiv \text{ (Complement x 2)}$$

$$(\top \land (p \lor \neg q)) \land ((\neg p \lor q) \land \top) \equiv \text{ (Identity x 2)}$$

$$(p \lor \neg q) \land (\neg p \lor q) \equiv \text{ (Commutation)}$$

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