Practical 7
In[1]:= f[x_ , y _, z_] := (x ∧ y) ∨ (y ∧ z) ∨ (z ∧ x)
g[x_ , y _] := ! (((! x ∨ y) ∧ x) ∨ ! ! ! y) ∨ (x ∧ y) ∨ (x ∧ ! y)
h[x_ , y _, z_] := (x ∧ (! (y ∨ z))) ∨ ((x ∧ y) ∨ ! z) ∧ x
Find the following :-
1. Dual of a given Boolean polynomial/ expression
In[4]:= dual[expr_] := expr /. {And → Or, Or → And, True → False, False → True}
Verification :-
In[5]:= dual[f[x, y, z]]
% // Simplify
Out[5]= (x || y) && (y || z) && (z || x)
Out[6]= (x && (y || z)) || (y && z)
In[8]:= dual[g[x, y]]
% // Simplify
Out[8]= ! (((! x && y) || x) && ! y) && (x || y) && (x || ! y)
Out[9]= x && y
In[10]:= dual[h[x, y, z]]
% // Simplify
Out[10]=
(x || ! (y && z)) && (((x || y) && ! z) || x)
Out[11]=
x || (y && ! z)
2 . Whether or not two given Boolean polynomial are equivalent:
In[12]:= j[x_ , y _, z_] := (x ∧ (y ∨ z)) ∨ (y ∧ z)
In[13]:= BooleBooleanTablep, q, r, j[p, q, r], {p, q, r} // TableForm
Out[13]//TableForm=
1 1 1 1
1 1 0 1
1 0 1 1
1 0 0 0
0 1 1 1
0 1 0 0
0 0 1 0
0 0 0 0
2
Conclusion : We can see that Boolean Polynomial function table of f and j are same. Hence, they are
Equivalent.
However all other pair of function are not equivalent .
3. Disjunctive normal form ( Conjunctive normal form ) form a given Boolean
expression.
DNF→ Sum of products
CNF→ Products of sums
In[14]:= j[x_ , y _, z_] := (x ∧ (y ∨ z)) ∨ (y ∧ z)
In[15]:= BooleanConvert[j[x, y, z], "DNF"]
Out[15]=
(x && y) || (x && z) || (y && z)
In[16]:= BooleanConvert[k[x, y, z], "DNF"]
Out[16]=
k[x, y, z]
In[17]:= BooleanConvert[f[x, y, z], "DNF"]
BooleanConvert[g[x, y], "DNF"]
BooleanConvert[h[x, y, z], "DNF"]
Out[17]=
(x && y) || (x && z) || (y && z)
Out[18]=
x || y
Out[19]=
(x && y) || (x && ! z)
In[34]:= BooleanConvert[f[x, y, z], "CNF"]
BooleanConvert[g[x, y], "CNF"]
BooleanConvert[h[x, y, z], "CNF"]
BooleanConvert[j[x, y, z], "CNF"]
BooleanConvert[k[x, y, z], "CNF"]
Out[34]=
(x || y) && (x || z) && (y || z)
Out[35]=
x || y
Out[36]=
x && (y || ! z)
Out[37]=
(x || y) && (x || z) && (y || z)
Out[38]=
k[x, y, z]
4. DNF(CNF) when the given Boolean Polynomial function is expressed by a table
3
of values.
a) x|y|z F(x,y,x)
1|1|1|0
1|1|0|1
1|0|1|0
1|0|0|1
0|1|1|0
0|1|0|1
0|0|1|1
0|0|0|0
In[30]:= BooleanFunction[
{{1, 1, 0} → 1, {1, 0, 0} → 1, {0, 1, 0} → 1, {0, 0, 1} → 1, {_ , _ , _} → 0}, {x, y, z}, "CNF"]
BooleanFunction[
{{1, 1, 0} → 1, {1, 0, 0} → 1, {0, 1, 0} → 1, {0, 0, 1} → 1, {_ , _ , _} → 0}, {x, y, z}, "DNF"]
Out[30]=
(! x || ! z) && (x || y || z) && (! y || ! z)
Out[31]=
(x && ! z) || (! x && ! y && z) || (y && ! z)
b) x|y|z G(x,y,x)
1|1|1|0
1|1|0|0
1|0|1|0
1|0|0|1
0|1|1|1
0|1|0|0
0|0|1|0
0|0|0|1
In[32]:= BooleanFunction[{{1, 0, 0} → 1, {0, 1, 1} → 1, {0, 0, 0} → 1, {_ , _ , _} → 0}, {x, y, z}, "CNF"]
BooleanFunction[{{1, 0, 0} → 1, {0, 1, 1} → 1, {0, 0, 0} → 1, {_ , _ , _} → 0}, {x, y, z}, "DNF"]
Out[32]=
(! x || ! y) && (! y || z) && (y || ! z)
Out[33]=
(! x && y && z) || (! y && ! z)