How can I find a DNF expression which is logically equivalent to x --> y?
DNF = disjunctive normal form
Meaning do DNF for anything that returns false, (thus it will return true for those values and false for the true values) then put a negation over the whole thing, (so it will have the correct truth values) then use DeMorgans to get it into the proper form.
For this one, that means that X^~Y is the DNF for the false, so we negate the whole thing:
And do DeMorgans
(~X v Y)
In a larger example, the answer is more obvious, ie say you have 3 variables xyz
And say the following start values return false: TTT, TTF, TFT
Then your DNF for the false looks like:
(X Y Z) v (X Y ~Z) v (X ~Y Z)
And the negation will cause it to return the correct truth values:
~[ (X Y Z) v (X Y ~Z) v (X ~Y Z) ]
And DeMorgans will distribute the negation and change the main ors to ands
~(X Y Z) ^ ~(X Y ~Z) ^ ~(X ~Y Z)
And now you need to distribute it to the individual components using DeMorgans (which also changes the ands to ors)
(~X v ~Y v ~Z) ^ (~X v ~Y v Z) ^ (~X v Y v ~Z)
I'd do it with Boolean Algebra, but I can't get all the bars to work right :/ sorry, hope you don't mind it done in logic.