Proof of Duality (cont’d)
Definitions
- If E is an expression, let ED be the dual of D.
- ie: f( A, B, C, …, 0, 1, +, • )D = f( A, B, C, …, 1, 0, •, + )
- If E is an expression, let EID be ED, but with all the variables inverted.
- ie: f( A, B, C, …, 0, 1, +, • )ID = f( A’, B’, C’, …, 1, 0, •, + )
Example:
- (A + 1)D = A . 0, however (A + 1)ID = A’ . 0
- (A + B)D = A . B, however (A + B)ID = A’ . B’
What is EID?
- Let’s take an example: (A + B)ID = A’ . B’ = (A + B)’ (By DeMorgan’s)
- So, it would look like EID is just E’… Well, that’s true, and this is called the generalized version of DeMorgan’s (proof is by induction, we won’t do it):
- f( A, B, C, …, 0, 1, +, • )’ = f( A’, B’, C’, …, 1, 0, •, + )