C 4 5 Let us consider an example of how to obtain the CNF of a Boolean expression Example 5 Obtain the CNF of the Boolean expression X X1 X2 X3 x1 AX2 x X3 Solution We have x A X2 x V x2 x V x VO x V x V x3 x3 x V x2 V x3 A x V x2 V x3 Similarly you can check that x A x3 x1 V x2 V x3 A x V x2 V x3 Thus the required CNF of the expression X X X2 X3 given here is x V x2 V x3 A x V x2 V x3 A x1 V x2 V x3 A x1 V x2 V x3 Try the following exercise now E3 Obtain the CNF of the Boolean expression X X1 X2 X3 x x V x A x3 As we have said earlier in the context of simplifying circuits we need to reduce Boolean expressions to simpler ones Simple means that the expression has fewer connectives and all the literals involved are distinct We illustrate this technique now Solution a Here we can write xi A x2 A xi A x 2 Example 6 Reduce the following Boolean expressions to a simpler form a X X1 X2 x AX2 x1 x b X X1 X2 X3 x AX V x1 Ax2 AX3 V X1 X3 xi A x2 x1 Ax2 x1 X2 X2 X1 A X2 A x x A O 0 b We can write xi A x2 V x1 A x2 A x3 V x1 A X3 X1 x V x2 AX3 x1 AX3 X1 x V x x2 V x3 x1 AX3 x1 IA x2 V x3 A X1 AX3 De Morgan s Law Identity law Complementation law Distributive law Thus in its simplified form the expression given in a above is O i e a null expression X1 A X2 V X3 X1 AX3 x1 AX2 V x1 AX3 X1 AX3 AD X1 A x2 AX3 V X3 x1 AX3 x1 A X2 AX3 V x1 X3 Complementation la Identity law Distributive law x1 AX2 A XI A X3 V x1 A X3 A X1 A x3 Distributive law Idemp assoc law Distributive law Associative law Absorption law Associative law Complementation law Identity law Distributive law Distributive law Absorption law Thus the simplified form of the expression given in b is x Ax3