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

B Ɂ h 1 ∨ ··· ∨ B Ɂ h,uh ∨ ¬ B Ɂ ' h,1 ∨ ··· ∨ ¬ B Ɂ ' h,vh ∨ B Ɂ hh (2.20)

Where Ɂ h,j , Ɂ ' h,n (1 ± h ± d, 1 ± j ± u h , 1 ± n ± v h ) and Ɂ hh, are all objective formulas.
Now, use expressions of the form of (2.20) to replace each occurrence of B Ɂ h,
and use expressions of the form of (2.19) to replace each occurrence of

i j , we

ϕ

will get a formula ɂ ' which is ɂќ -equivalent with ɂ and satisfies
rank( ɂ ')=rank( ɂ )+1. Finally, the proof can be completed by transforming the
formula ɂ ' into a conjunctive normal form.
We can also reach the following result according to the duality property:
Corollary 2.2

ɂ ∈ ќ B ,

(Theorem on Disjunctive normal form) For any formula

ɂќ -equivalent with some formula of the form ɂ 1 ∨ ɂ 2 ∨ ··· ∨ ɂ k , where

it is

ɂ i (1 ≤ i ≤ k) is of the form

each 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.

2.8.4 ◇◇◇◇ - mark and a kind of course of judging for stable expansion

Firstly we introduce the ◇ -mark. Let be a countable set of propositional letters,

and let 2 L be the set of all the assignments of

L

L .

Definition 2.23

ɂ ◇ ɂ

( ◇ -mark) For any basic formula , its

◇ -mark

is

inductively defined as follows:

∈ 2 L and (1) For any propositional letter p , ◇ p = { w | w w ( p )=1 };

(2) If ɂ = ¬ϕ , then ◇ ¬ϕ = ~ ◇ ϕ= 2 L - ◇ ϕ, where ~ is the complementary
operator on sets;

(3) If ɂ = ɂ 1 ∧ ɂ 2, then ◇ ɂ 1 ∧ ɂ 2 = ◇ ɂ 1 ŝ ◇ ɂ 2 , where ŝ is the the

intersection operator on sets;

(4) If ɂ = B ϕ, ◇ B ϕ = ◇ ϕ.

Lemma 2.3 Let ɂ and ϕ be objective formulas, then