I am trying to follow through the teacher's notes on transforming a formula to disjunctive normal form, but an example problem got me stuck. So the starting formula is this:
(X ⊃ Y ) ∨ ¬(¬Y ⊃ X ∨ ¬Z)
In the teacher's notation, ∧ is conjuntcion, ⊃ is implication, v is disjunction and ¬ is negation. As a first step, I use De Morgan's law, to remove the implications, which results in:
(¬X ∨ Y ) ∨ (¬Y ∧ ¬(X ∨ ¬Z))
Then I deal with the negations, so that they only apply to atomic formulas:
(¬X ∨ Y ) ∨ (¬Y ∧ ¬X ∧ Z)
I Write out the conjunction of disjunctions like this:
(¬X ∨ Y ∨ ¬Y ) ∧ (¬X ∨ Y ∨ ¬X) ∧ (¬X ∨ Y ∨ Z)
And then simplify by removing the first bracketed expression, which yields a tautolgy and removing the ¬X from the second one, as ¬X v ¬X = ¬X:
(¬X ∨ Y ) ∧ (¬X ∨ Y ∨ Z)
And, here comes the part, which got me stuck. In the teacher's lecture notes, after the very same construction process, the final, simplified result is
¬X ∨ Y
And I just can not wrap my head around how this simplification is made. It makes intuitive sense, that a disjunction of two tautologically equivalent formulas could be reduced to one of the formulas, but in this case I have written out the truth tables of (¬X ∨ Y) and (¬X ∨ Y ∨ Z) and they are not equivalent. Can somebody explain how this simplification comes to be? I just can not seem to figure it out myself... Also if somebody could provide some useful resource on the process of simplifying such formulas would be a great help, since our teacher's notes are very skimpy in explanations, and I could not find step-by-step examples on the internet yet. Thanks a lot in advance!
This is known as the absorption law: $$p\wedge(p\vee q) \equiv p$$
$$p\wedge(p\vee q)\equiv (p\vee F) \wedge (p\vee q) \equiv p\vee (F\wedge q) \equiv p\vee F\equiv p$$
It is also easily verified using the truth table.
Now think of $p$ as $\neg X\vee Y$ and $q$ as $Z$.