involving exactly k variables For instance the Boolean
Last updated: 10/12/2023
involving exactly k variables For instance the Boolean expression in 2 variables X x1 x2 x Ax V xi x V x A X2 is in DNF because it is a join of three minterms namely x Ax2 x1 Ax2 and x A x2 where each one of these involves exactly two variables Observe that each minterm in a DNF should involve all the k variables in the expression X x1 x2 xk k 2 For instance the Boolean expression X X1 X2 X3 x A x2 V x A X2 A X3 is not in DNF because x A x2 is not a minterm of all the three variables However since we can write x Ax x AX2 AI and so the expression X x1 x2 X3 with this change for x A x2 is in the disjunctive normal form Indeed using similar techniques any Boolean expression 0 can be written in disjunctive normal form Let us work out an example to illustrate this technique Example 4 Obtain a disjunctive normal form for the expression X X1 X2 X3 x1 AX V XI AX3 Solution We can write x x2 x x I Also x A x2 A X3 V x3 x x x3 V x AX2 x3 X1 X3 x A x A x3 V x3 x A X A x3 V x A X2 A x3 by Identity law by Complementation law by Distributive law X A X3 A I x1 A X3 A x2 V x k Why don t you try an exercise now Identity law Complementation law Distributive law x1 A X3 A x2 V x1 A X3 AX2 by Distributive law x1 A X2 A x3 V x1 A X2 A x3 by commutativity of A Hence the required disjunctive normal form of the given expression X X1 X2 X3 in three variables is given by x A X2 A x3 V x A x2 A x3 V x1 A X2 A X3 V x A X A X3 by Identity law by Complementation law E2 Obtain the disjunctive normal form of the Boolean expression X X1 X2 X3 x V x V x A Xa The conjunctive normal form is another important type of expression which is analogous to the concept of DNF Definition A Boolean expression in k variables is said to be in conjunctive normal form CNF in short if it is a meet of maxterms each of which involves all the k variables For instance the Boolean expression X X1 X2 X3 x V x2 V x3 x V x2 V x3 x V x2 V x3 is in CNF because it is the meet of maxterms x1 Vx2 Vx3 xVx2 Vx3 and x V x2 V x3 Note that all 3 variables are involved in each maxterm Boolean Al