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!
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 :