1 (137)

Prévia do material em texto

Step 1 of 3 4.028E To prove the DeMorgan's theorems using finite induction, we need to solve by two steps. First step is basis step, considering n=2 and proving the theorem using axioms. The axioms are given by as follows: A2=X=0, then X'=1 X=1, then X'=0 Second step is induction step, assuming the theorem is true for n variable and proving the same for n+1 variable. For this step switching theorems are used. Switching theorems are given as follows: T2=X+1=1 T3=X+X=X T5=X+X'=1 T6=X+Y=Y+X Step of 3 The DeMorgan's theorem is as follows: Basis Step: Considering n=2 then DeMorgan's theorem is written as follows: Proof for the above equations using perfect induction method: X2 X2' 00111 1 01101 1 10011 1 11000 0 Table 1: Perfect induction method for theorem Thus the theorem is proved using perfect induction method. Then for second one is given by as follows: X2 X2' 00111 1 01100 0 10010 0 11000 0 Table 2: Perfect induction method for theorem Thus the theorem is proved using perfect induction method. Step 3 of 3 The second step is induction step, assuming the theorem is true for n variable and proving the same for n+1 variable. Thus for n+1 variable, the DeMorgan's theorem is written by Proof for n+1 variable is given by, (Since theorem is proved for two variable) (Since assumed that theorem is true for variable) For second one, (Since theorem is proved for two variable) (Since assumed that theorem is true for n variable) Thus the DeMorgan's theorem is proved by finite induction method.