F (x, y, z) = (x+y+z) . (x.y+x' z) ' convert the following boolean function into conjunctive normal form.
Answers
Answer:
(a)
f(x1;…;xn)=x1∨⋯∨xn
(b)
You get the conjunctive normal form after successively applying the distributive property to the following:
f(x1;…;xn)=(¬x1∧⋯∧¬xn)⋁i∈{1,…,n}(¬x1∧⋯∧xi∧⋯∧¬xn)
When looking at the truth table of n variables, your function f(x1;…;xn) evaluates to 1 exactly when all of the variables are 0, or precisely one of them is 1. This makes for a total of n+1 rows in the table. And as you know, the table has 2n rows. Now there is a theorem which states that if an identity holds on B2 (two-element Boolean algebra), then it must hold on an arbitrary Boolean algebra. And there is another theorem which states that for every Boolean function f:{0,1}n→{0,1} on B2, there is a corresponding term g(x1;…;xn) such that g is equivalent to the canonical disjunctive normal form:
g(x1;…;xn)=⋁f(α1,…,αn)=1(xα11∧⋯∧xαnn)
α∈{0,1} and x0=¬x, x1=x.
This may seem confusing, but essentially it means that you're looking only at those rows in the table where f evaluates to 1, and then you make a canonical conjunction out of variables in that particular row. And in the end, you have the canonical disjunctive normal form by joining these with ∨.
For example, imagine you have a function f with three variables x,y,z, and this function evaluates to 1 at exactly three places, say when: x=0,y=0,z=0; x=0,y=1,z=1; x=1,y=0,z=0. Then our corresponding term becomes: f(x,y,z)=¬x¬y¬z∨¬xyz∨x¬y¬z.
This last theorem also works for making canonical conjunctive normal forms, because of the duality principle for Boolean algebras. But for your particular case this means you'd have 2n−(n+1) distinct conjuncts, and it's a bit trickier to represent in a concise form, because of the many possible cases where more than one variable is 1. But it is exactly what you'll get after successive application of the distributive property to the above canonical disjunctive normal form!
Step-by-step explanation:
hope this will help u