Put the following Boolean expressions into 3-CNF

Question

Put the following Boolean expressions into 3-CNF

1) xy + ~xz

2) wxyz+u+v

3) wxy+~xuv

Summary

A 3CNF is a CNF, in which each clause has at most three literals.

• • The 3CNF for the expression xy + ~xz is:

(x + y + z).(~x + y + z).(x + ~y + z).(~x + y + ~z)

• • The 3CNF for the expression wxyz + u + v is:

(u + v + w).(u + v + x).(u + v + y).(u + v + z)

• • The 3CNF for the expression wxy + ~xuv is:

(~x + y + w).(~x + ~y + w).(~x + y + ~w).(u + w + v).(u + w + ~v).(u + x + v).(u + x + ~v).(u + y + v).(v + w + u).(v + w + ~u).(v + x + u).(v + w + ~u).(v + y + u).(v + y + ~u)

 

Explanation

Conversion of Boolean expressions to 3-CNF:

1) xy + ~xz                                                         A+BC=(A+B)(A+C) -> Distributive law

=(xy+∼x)(xy+z)

=(x+∼x)(y+∼x)(x+z)(y+z)

=1.(y+∼x)(x+z)(y+z)

=(∼x+y)(x+z)(y+z)

=(∼x+y+0)(x+0+z)(0+y+z)

=(∼x+y+z.∼z)(x+y.∼y+z)(x.∼x+y+z)

=(∼x+y+z)(∼x+y+∼z)(x+y+z)(x+∼y+z)(x+y+z)(∼x+y+z)

=(x+y+z)(∼x+y+z)(x+∼y+z)(∼x+y+∼z)

 

2) wxyz +u +v

Using Distributive law A+BC=(A+B)(A+C)

wxyz +u +v

=(u+v)+wxyz

=(u+v+w)(u+v+xyz)

=(u+v+w)(u+v+x)(u+v+yz)

=(u+v+w)(u+v+x)(u+v+y)(u+v+z)    ->3CNF

 

3) wxy+~xuv

Using Distributive law A+BC=(A+B)(A+C)

wxy+~xuv

=(wxy+∼x)(wxy+uv)

=(wxy+~x)(wxy+u)(wxy+v)

=(~x+wxy)(u+wxy)(v+wxy)

=(~x+w)(∼x+x)(∼x+y)(u+w)(u+x)(u+y)(v+w)(v+x)(v+y)

=(~x+w)(∼x+y)(u+w)(u+x)(u+y)(v+w)(v+x)(v+y)

=(~x+0+w)(∼x+y+0)(u+0+w)(u+x+0))(u+y+0)(v+0+w)(v+x+0)(v+y+0)

=(~x+y.∼y+w)(∼x+y+w.∼w)(u+v.∼v+w)(u+x+v.∼v)(u+y+v.∼v)(v+u.∼u+w)(v+x+u.∼u)(v+y+u.∼u)

=(~x+y+w)(~x+∼y+w)(∼x+y+w)(∼x+y+∼w)(u+v+w)(u+∼v+w)(u+x+∼v)(u+x+v)(v+u+w)(v+∼u+w)

(v+x+u)(v+x+∼u)(v+y+∼u)(v+y+u)(v+y+∼u)(v+y+u)

 

Also read, Find the hexadecimal expansion