Logic Foundation of Artificial Intelligence - Advanced Artificial Intelligence - page 67

↔

Lemma 2.2 ż B ( B ( ɂ 1 ) ∨ ··· ∨ B ( ɂ s ) ∨ ¬ B ( ϕ 1 ) ∨ ···¬ B ( ϕ t ) ∨ ϕ )

( B ( ɂ 1 ) ∨ ··· ∨ B ( ɂ s ) ∨ ¬ B ( ϕ 1 ) ∨ ··· ¬ B ( ϕ t ) ∨ B( ϕ )).

Theorem 2.8 (Theorem on Conjunctive normal form) For any formula ɂ ∈ ќ B ,

it is ϕ ќ -equivalent with some formula of the form ɂ ɂ ɂ

k , where 1 ∧ 2 ∧ ··· ∧

each ɂ i (1 ≤ i ≤ k) is of the form B ϕ i,1 ∨ ··· ∨ B ϕ i,mi ∨ ¬ B ϕ i,1 ∨ ··· ∨ ¬ B ϕ i,ni

ii with

i,j , i,n , (1 ≤ i ≤ k, 1 ≤ j ≤ m i , 1 ≤ n ≤ n i ) and

ɂ

ii objective

∨ ϕ

ϕ ϕ

formulas.

Proof. By indunction on the value of rank( ). If rank( ) = 1, then the result is
obvious according to Theorem 2.6.
Suppose rank( )=N and suppose the result hods for any formula ϕ with

rank( ϕ )<N. Then, according to Theorem 2.6 we have

= 1 ∨ 2 ∨ ··· ∨ k ,

where each i (1 i k) is of the form

i i i i

ni ∧ ii. B ϕ 1 ∧ ··· ∧ B ϕ mi ∧ ¬B ϕ 1 ∧ ··· ∧ ¬B ϕ

According to the induction hypothesis we have
rank( ϕ

i i

t ) N-1, and rank( ii ) = 0.

j ) N-1 rank( ϕ

i i

Therefore, both ϕ t can be equivalently transformed into formulas

whose rank value are less or equivalent to 1. Without lose of generality we let
ϕ

j and

ϕ

i j be a formula of the form

Ɂ 1 ∧ ··· ∧ d ,

where each h (1 h d) is of the form

B h 1 ∨ ··· ∨ B h,uh ∨ ¬ B ' h,1 ∨ ··· ∨ ¬ B ' h,vh ∨ hh

and h,j , ' h,n (1 h d, 1 j u h , 1 n v h ), hh, are all objective formulas.

i j is equivalent to

According to the semantic definition, the formula B ϕ

B ( 1 ) ∧ ··· ∧ B ( d ) (2.19)

Furthermore, according to Lemma 2.2, each B( h ) is equivalent to