Propositional Logic Exercise

106 Views Asked by At

I need your help in solving an exercise in propositional logic:

I am trying to prove that this :

(Y ∧ ¬Z) ∨ ((X ∨ Y) ∧ (¬Y ∨ X))

is equivalent to this (according to the solution of the exercise)

(X ∨ ¬Z) ∧ (X ∨ Y)

What I did so far:

(Y ∧ ¬Z) ∨ ((X ∨ Y) ∧ (¬Y ∨ X)) ≡ (Y ∧ ¬Z) ∨ (( X ∧ (¬Y ∨ X)) ∨ ( Y ∧ (¬Y ∨ X))
 ≡ (Y ∧ ¬Z) ∨ (( X ∧ ¬Y) ∨ (X ∧ X) ∨ (Y ∧ ¬Y) ∨ (Y ∧ X))
 ≡ (Y ∧ ¬Z) ∨ ( X ∧ ¬Y) ∨ X ∨ (Y ∧ X)
 ≡ (Y ∧ ¬Z) ∨ X ∨ ( X ∧ ¬Y) ∨ (Y ∧ X)
 ≡ ((X ∨ Y) ∧ (X ∨ ¬Z)) ∨ ( X ∧ ¬Y) ∨ (Y ∧ X)

Now this part what I am having issues with, I could apply the distributive law again, but I don't see how this part will turn False at some point. :

( X ∧ ¬Y) ∨ (Y ∧ X) ≡ ( X ∨ (Y ∧ X)) ∧ ( ¬Y ∨ (Y ∧ X))
                    ≡ (X ∨ Y) ∧ (X ∨ X) ∧ (¬Y ∨ Y) ∧ (¬Y ∨ X)
                    ≡ (X ∨ Y) ∧ X ∧ Y ∧ (¬Y ∨ X)

Thank you for your time and help!

1

There are 1 best solutions below

5
On BEST ANSWER

We have to apply Distributivity to $(X ∨ Y) ∧ (¬Y ∨ X)$ to get : $X ∨ (Y ∧ ¬Y)$.

And $(Y ∧ ¬Y) \equiv \text F$ and $X ∨ \text F \equiv X$.

Thus, starting from the original formula :

$$[(Y ∧ ¬Z) ∨ ((X ∨ Y) ∧ (¬Y ∨ X))] \equiv [(Y ∧ ¬Z) ∨ (X ∨ (Y ∧ ¬Y))] \equiv$$

$$[(Y ∧ ¬Z) ∨ (X ∨ \text F)] \equiv [(Y ∧ ¬Z) ∨ X].$$