1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)$$

$\endgroup$

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.