1. ## DNF expression HELP!

How can I find a DNF expression which is logically equivalent to x --> y?

DNF = disjunctive normal form

2. Originally Posted by jzellt
How can I find a DNF expression which is logically equivalent to x --> y?

DNF = disjunctive normal form
Use truth tables:

x | y | x->y
------------
T | T | T
T | F | F
F | T | T
F | F | T

Think you can take it from here?

3. thanks...I just figured it out. Now, to find the CNF expression, do I just negate my DNF?

4. Originally Posted by jzellt
thanks...I just figured it out. Now, to find the CNF expression, do I just negate my DNF?
No, the way I learned to do it (may not work better for you) is to do a negated disjunctive form for anything that returns false.

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:

~(X^~Y)

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.