2
$\begingroup$

Here I have a proposition:

((¬p ∨ x) ∧ (p ∨ y)) → (x ∨ y)

To prove whether a tautology or contradiction or neither.

≡ ¬[((¬p ∨ x) ∧ (p ∨ y))] ∨ (x ∨ y) implication equivalence

≡ (¬(¬p ∨ x) ∨ ¬(p ∨ y)) ∨ (x ∨ y) DeMorgans

≡ ((p ∧ ¬x) ∨ (¬p ∧ ¬y)) ∨ (x ∨ y) DeMorgans

From here I'm not sure what to go on with. Have I made a mistake? Was that Distributive law an illegal move?

$\endgroup$
1
  • 1
    $\begingroup$ You did make a mistake when applying the De Morgan's laws for the second time (you didn't change $\lor$ to $\land$). $\endgroup$
    – dtldarek
    Sep 14, 2013 at 22:52

1 Answer 1

2
$\begingroup$

Moving from your second step to your third step, we need to correctly apply DeMorgan's:

$$\begin{align} &\equiv (\lnot (\lnot p \lor x) \lor \lnot(p \lor y)) \lor (x \lor y) \tag{2}\\ \\ &\equiv (p \land \lnot x) \lor (\lnot p \land \lnot y) \lor (x \lor y)\\ \\ \tag{3}\end{align}$$

Now we can apply the distributive law to the first two parenthetical clauses, and then again in line $(5)$:

$$\begin{align} &\equiv [(p \lor (\lnot p \land \lnot y)) \land (\lnot x \lor (\lnot p \land \lnot y))] \lor (x \lor y)\tag{4} \\ \\ & \equiv [(p\lor \lnot p) \land (p \lor \lnot y) \land (\lnot x \lor \lnot p) \land (\lnot x \lor \lnot y)]\lor (x \lor y)\tag{5}\\ \\ \end{align} $$

See what you can do from here! Check back if you run into more trouble, and comment below if you need to.

$\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.