[mathematical logic] predicate logic (toe normal form | toe normal form conversion method | basic equivalence of predicate logic | name changing rules | predicate logic reasoning law)

One 、 The toe in paradigm

---

The formula

A

A

A There are the following forms :

Q

1

x

1

Q

2

x

2

⋯

Q

k

x

k

B

Q_1 x_1 Q_2 x_2 \cdots Q_kx_k B

Q1​x1​Q2​x2​⋯Qk​xk​B

said

A

A

A yes The toe in paradigm ; The toe in paradigm

A

A

A Related elements of explain :

quantifiers :

Q

i

Q_i

Qi​ It's a quantifier , Full name quantifier

∀

\forall

∀ , or There are quantifiers

∃

\exist

∃ ;

Guide arguments :

x

i

x_i

xi​ yes Guide arguments ;

B

B

B The formula :

B

B

B Is a predicate logic formula , There are no quantifiers ,

B

B

B in Can contain Ahead

x

1

,

x

2

,

⋯
 

,

x

k

x_1 , x_2 , \cdots , x_k

x1​,x2​,⋯,xk​ Guide arguments , also May not contain Some of these arguments ;

(

B

B

B Must not contain quantifiers )

Two 、 The method of toe in normal form transformation

---

Find a prefix normal form of predicate logic formula , Use Basic equivalence , or Name change rules ;

Basic equivalence : Reference blog 【 Mathematical logic 】 Predicate logic ( Basic equivalence of predicate logic | Eliminate quantifier equivalents | The quantifier negates the equivalent | The scope of quantifier is shrinking and expanding | The equivalent of quantifier distribution )

Name change rules : The formula

A

A

A in , In a quantifier domain , A constraint The emergence of Individual variables Corresponding Guide arguments

x

i

x_i

xi​ , Use the formula

A

A

A That didn't show up in Argument

x

j

x_j

xj​ Replace , The resulting formula

A

′

⇔

A

A' \Leftrightarrow A

A′⇔A ;

Such as :

∀

x

F

(

x

)

∨

∀

x

¬

G

(

x

,

y

)

\forall x F(x) \lor \forall x \lnot G(x, y)

∀xF(x)∨∀x¬G(x,y) If its toe in paradigm is required , There are two before and after

x

x

x , Here we use the name change rule , Replace one with something that has never appeared Guide arguments

z

z

z , Change the name to

∀

x

F

(

x

)

∨

∀

z

¬

G

(

z

,

y

)

\forall x F(x) \lor \forall z \lnot G(z, y)

∀xF(x)∨∀z¬G(z,y) ;

3、 ... and 、 Example of toe in paradigm

---

seek

∀

x

F

(

x

)

∨

¬

∃

x

G

(

x

,

y

)

\forall x F(x) \lor \lnot \exist x G(x, y)

∀xF(x)∨¬∃xG(x,y) The toe in paradigm ;

The above formula is not a toe in paradigm , Its quantifiers

∀

x

\forall x

∀x Our jurisdiction is

F

(

x

)

F(x)

F(x) , quantifiers

∃

x

\exist x

∃x Our jurisdiction is

G

(

x

,

y

)

G(x, y)

G(x,y) , Neither jurisdiction covers the complete formula ;

Use Equivalent calculus and Name change rules , Find the foreskin normal form ;

∀

x

F

(

x

)

∨

¬

∃

x

G

(

x

,

y

)

\forall x F(x) \lor \lnot \exist x G(x, y)

∀xF(x)∨¬∃xG(x,y)

Use The quantifier negates the equivalent , The first Negative connectives Move to the back of the quantifier , The equivalent formula used is

¬

∃

x

A

(

x

)

⇔

∀

x

¬

A

(

x

)

\lnot \exist x A(x) \Leftrightarrow \forall x \lnot A(x)

¬∃xA(x)⇔∀x¬A(x) ;

⇔

∀

x

F

(

x

)

∨

∀

x

¬

G

(

x

,

y

)

\Leftrightarrow \forall x F(x) \lor \forall x \lnot G(x, y)

⇔∀xF(x)∨∀x¬G(x,y)

Use Name change rules , Put the second

∀

x

¬

G

(

x

,

y

)

\forall x \lnot G(x, y)

∀x¬G(x,y) Medium

x

x

x Switch to

z

z

z ;

⇔

∀

x

F

(

x

)

∨

∀

z

¬

G

(

z

,

y

)

\Leftrightarrow \forall x F(x) \lor \forall z \lnot G(z, y)

⇔∀xF(x)∨∀z¬G(z,y)

Use Equivalent formula of scope expansion , take

∀

x

\forall x

∀x Scope expansion , The equivalent formula used is

∀

x

(

A

(

x

)

∨

B

)

⇔

∀

x

A

(

x

)

∨

B

\forall x ( A(x) \lor B ) \Leftrightarrow \forall x A(x) \lor B

∀x(A(x)∨B)⇔∀xA(x)∨B

⇔

∀

x

(

F

(

x

)

∨

∀

z

¬

G

(

z

,

y

)

)

\Leftrightarrow \forall x ( F(x) \lor \forall z \lnot G(z, y) )

⇔∀x(F(x)∨∀z¬G(z,y))

Again using Equivalent formula of scope expansion , take

∀

z

\forall z

∀z Scope expansion , The equivalent formula used is

∀

x

(

A

(

x

)

∨

B

)

⇔

∀

x

A

(

x

)

∨

B

\forall x ( A(x) \lor B ) \Leftrightarrow \forall x A(x) \lor B

∀x(A(x)∨B)⇔∀xA(x)∨B

⇔

∀

x

∀

z

(

F

(

x

)

∨

¬

G

(

z

,

y

)

)

\Leftrightarrow \forall x \forall z ( F(x) \lor \lnot G(z, y) )

⇔∀x∀z(F(x)∨¬G(z,y))

At this time, it is the toe in paradigm ;

Use Propositional logic Equivalent formula Medium Implication equivalence

⇔

∀

x

∀

z

(

G

(

z

,

y

)

→

F

(

x

)

)

\Leftrightarrow \forall x \forall z ( G(z, y) \to F(x) )

⇔∀x∀z(G(z,y)→F(x))

Four 、 Predicate logic inference law

---

The following reasoning law is one-way , From the left, we can infer the right , You can't infer from the right to the left ; ( Not equivalent )

①

∀

x

A

(

x

)

∨

∀

x

B

(

x

)

⇒

∀

x

(

A

(

x

)

∨

B

(

x

)

)

\rm \forall x A(x) \lor \forall x B(x) \Rightarrow \forall x ( A(x) \lor B(x) )

∀xA(x)∨∀xB(x)⇒∀x(A(x)∨B(x))

Corresponding Full name quantifier Distribution rate , In the equation Only applicable to Conjunctions , Because of the above Disjunction time , From right to left It's wrong. , You can only reason from left to right ;

②

∃

x

(

A

(

x

)

∧

B

(

x

)

)

⇒

∃

x

A

(

x

)

∧

∃

x

B

(

x

)

\rm \exist x ( A(x) \land B(x) ) \Rightarrow \exist x A(x) \land \exist x B(x)

∃x(A(x)∧B(x))⇒∃xA(x)∧∃xB(x)

③

∀

x

(

A

(

x

)

→

B

(

x

)

)

⇒

∀

x

A

(

x

)

→

∀

x

B

(

x

)

\rm \forall x ( A(x) \to B(x) ) \Rightarrow \forall x A(x) \to \forall x B(x)

∀x(A(x)→B(x))⇒∀xA(x)→∀xB(x)

④

∀

x

(

A

(

x

)

→

B

(

x

)

)

⇒

∃

x

A

(

x

)

→

∃

x

B

(

x

)

\rm \forall x ( A(x) \to B(x) ) \Rightarrow \exist x A(x) \to \exist x B(x)

∀x(A(x)→B(x))⇒∃xA(x)→∃xB(x)