|
Administrator
|
To go from one to the other using Boolean algebra alone is not very obvious.
IF you believe DeMorgan's theorems, then it is a one-liner since those theorems are
(A)(B) = !((!A)+(!B))
A+B = ~((~A)(~B))
But if you aren't at the point of being able to accept DeMorgan's theorems then you can't just use the second one and call it a day.
Probably the most productive approach is to take a step aside and looking into some of the proofs of DeMorgan's theorems and find one that makes sense to you. At that point, you CAN use the one-liner and call it a day.
One of the classic proofs goes something like this.
Given a Boolean function, f(x,y), then if we can find another Boolean function, g(x,), such that g(x,y) = ~f(x,y) for all possible values of x and y, then if we AND the two function together we will always get
f(x,y) AND g(x,y) = FALSE
But we could also get this result if g(x,y) happens to simply always be false.
However, if we OR the two together as well, we will always get
f(x,y) OR g(x,y) = TRUE
The only way was can always satisfy both of these requirements is if g(x) is always exactly the opposite of f(x,y).
So now we can postulate that
f(x,y) = x + y
g(x,y) = ~f(x,y) = ~(x + y) ?=? (~x)(~y)
and then proceed to show that, sure enough
f(x,y)·g(x,y) = 0
f(x,y)+g(x,y) = 1
identically (i.e., regardless of what x and/or y happen to be).
|
Locked
