Convert Boolean formula to one in 3CNF that is equisatisfiable F(v,w,x,y,z)=xΛ(y V ¬(x V z̄))Λ¬(v̅ Λ w Λ Λ y Λ z̄)).

Question:

Convert Boolean formula to one in 3CNF that is equisatisfiable

F(v,w,x,y,z)=xΛ(y V ¬(x V z̄))Λ¬(v̅ Λ w Λ Λ y Λ z̄)).

Summary:

Basically, a Boolean expression is said to be in 3CNF, if it is firstly in CNF and each clause in the CNF has 3 literals.

A 3CNF is said to be equisatisfiable iff:

Let us suppose F = given F (v, w, x, y, z)

And F’ is the 3CNF.

F’ is satisfiable iff f is satisfiable.

Then, F’ is an equisatisfiable 3CNF.

 

Explanation:

Given boolean formula:

F(v,w,x,y,z)=xΛ(y V ¬(x V z̄))Λ¬(v̅ Λ w Λ Λ y Λ z̄)).

1. ¬(v̅ Λ w Λ Λ y Λ z̄)=¬((v̅ Λ w Λ Λ y) Λ z̄)

=¬(v̅ Λ w Λ Λ y )V z

=¬(v̅ Λ w Λ )V V z

=v V w̅ V x V V z

 

F(v,w,x,y,z)=xΛ(y V ¬(x V z̄))Λ ( v V w̅ V x V V z)

=xΛ(y V (¬x V z̄))Λ ( v V w̅ V x V V z)

=xΛ(y V )Λ(y V z)Λ ( v V w̅ V x V V z)

Let Φ= F(v,w,x,y,z)

Let’s consider a clause with one literal

c=x

c≅Φ

 

To prove this,

We have to show Φ is satisfiable iff c is satisfiable.

x=1

⇒c is satisfiable.

⇒ Φ is satisfiable iff (x=1)

Therefore Φ is satisfiable iff c is satisfiable.

c≅Φ

Let’s consider a clause with two literals

c=yVz

Let y=1 and z=0

c=1V0=1

⇒c is satisfiable.

⇒ Φ is satisfiable iff (yVz=1)

Here, yVz=1.

Therefore, Φ is satisfiable iff c is satisfiable.

It is true for no. of literals=1 and literals=2
Hence, it is true for 3.
By Induction, it is true for 1, true for n=2, and true for n=2+1=3.

F(v,w,x,y,z)=xΛ(y V )Λ(y V z)Λ ( v Vw̅V x V V z)

Let v Vw̅V x =k

=xΛ(y V )Λ(y V z)Λ (kVVz)

=(xVy)(xV )( VyVz)( VyVz̄)(xVyVz)( VyVz)(kVVz)

=((xVyVz) Λ (xVyVz̄) Λ (xVVz) (xVVz̄) ( VyVz) (xVyVz̄) (kVVz).

 

Also, read Database Replication.