一階謂詞邏輯CH4一階邏輯基本概念CH5一階邏輯等值演算與推理1內(nèi)容要點：謂詞和個體量詞一階邏輯公式置換規(guī)則一階邏輯等值式一階邏輯前束范式推理理論CH4CH4CH4CH5CH5CH5CH52023/6/1421.命題的表達例1.1：凡偶數(shù)都能被2整除，

6是偶數(shù)。所以，6能被2整除將它們命題符號化：

p：凡偶數(shù)都能被2整除

q：6是偶數(shù)

r：6能被2整除則推理的形式結構符號化為：

(p

q)

r由于上式不是重言式，所以不能由它判斷推理的正確性。為了克服命題邏輯的局限性，就應該將簡單命題再細分，分析出個體詞、謂詞和量詞，以期達到表達出個體與總體的內(nèi)在聯(lián)系和數(shù)量關系，這就是謂詞邏輯。2023/6/143(1)８是自然數(shù)。(2)21世紀末，人類將住在月球。

(3)x+y=y+x(4)只有x能被2整除，x才能被4整除。A.個體詞x,y的取值范圍：復數(shù)域a的取值范圍：整數(shù)域是指所研究對象中可以獨立存在的具體的或抽象的客體。表示具體或特定的客體的個體詞稱作個體常項；常用a,b,c,…表示。表示抽象或泛指的客體的個體詞稱作個體變項；常用x,y,z,…表示。個體變項的取值范圍為個體域，個體域可以是有窮集合，也可以是無窮集合。全總個體域：由宇宙間一切事物組成的域為全總個體域。

2023/6/144

a.小陳是大學生

b.小張生于蘇州

c.8=3*2x是大學生小陳-----個體；是大學生-----謂詞：是大學生刻劃了x的性質(zhì)x生于y生于-----謂詞：刻劃了x和y的關系x=y*z….=…..------謂詞：刻劃了x，y，z三元的關系

一、謂詞和個體B.謂詞2023/6/145B.謂詞(1)８是自然數(shù)。(2)21世紀末，人類將住在月球。

(3)x

與y

具有關系L(4)只有x能被2整除，x才能被4整除。謂詞：用來刻劃個體詞性質(zhì)及個體詞之間相互關系的詞表示具體性質(zhì)或關系的謂詞稱為謂詞常項謂詞變項：表示抽象的或泛指的性質(zhì)或關系的謂詞兩者都用大寫英文字母表示2023/6/146一般的用F(a)表示個體常項a具有性質(zhì)F（F是謂詞常項或謂詞變項），用F(x)表示個體變項x具有性質(zhì)F。而用F(a,b)表示個體常項a,b具有關系F，用F(x,y)表示個體變項x,y具有關系F。定義：一個大寫英文字母后邊有括號，括號內(nèi)是若干個客體變元，用以表示客體的屬性或者客體之間的關系，稱之為謂詞。如果括號內(nèi)有n個客體變元，稱該謂詞為n元謂詞。2023/6/147例如

S(x):表示x是大學生。一元謂詞

G(x,y)：表示x>y。二元謂詞

B(x,y,z)：表示x在y與z之間。三元謂詞一般地

P(x1,x2,…,xn)是n元謂詞。0元謂詞：有時將不帶個體變項的謂詞稱為0元謂詞，例如上面提到的F(a)，H(a,b)，P(a1,a2,…,an)等都是0元謂詞，當F,H,P為謂詞常項時，0元謂詞為命題。這樣，命題邏輯中的命題均可表示成0元謂詞，因而可以將命題看成是特殊的謂詞。2023/6/148(1)2是素數(shù)且是偶數(shù)

(2)如果2大于3，則2大于4

解：(1)設一元謂詞F(x)：x是素數(shù)；一元謂詞G(x)：x是偶數(shù)；a：2。則(1)中命題符號化為0元謂詞的合取式：F(a)G(a)。(2)

設二元謂詞L(x,y)：x大于y；a：2；b：3；c：4.L(a,b),L(a,c)是兩個0元謂詞，把(2)中命題符號化為L(a,b)

L(a,c)例題：將下列命題用0元謂詞符號化，并討論它們的真值。2023/6/149

x讀作‘對任意x’

xP(x)表示‘對一切x,P(x)為真’

┐x┐P(x)表示

‘并非對任意x,┐P(x)是真’

(1)全稱量詞xC.量詞2023/6/1410

x讀作‘至少有一x’，‘存在一x’x┐P(x)表示

‘存在一x，使┐P(x)為真’┐x┐P(x)表示

‘并非存在一個x，使┐

P(x)為真’(2)存在量詞xC.量詞2023/6/1411

在P(x)，P(x,y)前加上x或x，稱變元x被存在量化或全稱量化。

將謂詞F(x)變成命題有兩種方法。a.將x取定值例：F(x)表示‘x是質(zhì)數(shù)’，那么F(4)是命題（假）b.將謂詞量化

例：1).xF(x)F(x)：任意的x是質(zhì)數(shù)

2).y(y<y+1)3).y(y<y+1)

量詞的作用C.量詞2023/6/1412(1)分析命題中表示性質(zhì)和關系的謂詞，分別符號化為一元和n（n

2）元謂詞。

(2)根據(jù)命題的實際意義選用全稱量詞或存在量詞。

(3)在不同的個體域中，命題符號化的形式可能不一樣。如果事先沒有給出個體域，都應以全總個體域為個體域。

(4)多個量詞同時出現(xiàn)時，不能隨意顛倒它們的順序，顛倒后會改變原命題的含義。在使用量詞時，應注意以下幾點：2023/6/1413(5)當個體域為有限集時，如D={a1,a2,…,an}，由量詞的意義可以看出，對于任意的謂詞A(x)，都有①

xA(x)A(a1)

A(a2)…

A(an)②xA(x)A(a1)

A(a2)…

A(an)這實際上是將謂詞邏輯中命題公式轉化為命題邏輯中的命題公式問題。2023/6/1414

1.設個體域為D={0,1,2,……,10},將下列命題符號化：

(1)D中所有元素都是整數(shù)；

(2)D中有的元素是偶數(shù)；

(3)D中所有的偶數(shù)都能被2整除；

(4)D中有的偶數(shù)是4的倍數(shù)。

D.舉例?xF(x),其中F(x)：x是整數(shù)?xG(x),其中G(x)：x是偶數(shù)?x(G(x)H(x)),其中G(x):x是偶數(shù);H(x):x能被2整除?x(G(x)∧R(x)),其中G(x):x是偶數(shù);R(x):x是4的倍數(shù)2023/6/14152.設個體域為D={x|x為人}，將下列命題符號化：(1)人都生活在地球上；(2)有的人長著黑頭發(fā)；(3)中國人都用筷子吃飯；(4)有的中國人不住在中國；

D.舉例?xF(x),其中F(x)：x生活在地球上?xG(x),其中G(x)：x長著黑頭發(fā)?x(H(x)I(x)),其中H(x):x是中國人；I(x)：x用筷子吃飯?x(H(x)∧R(x)),其中H(x):x是中國人；R(x):x住在中國2023/6/1416D.舉例3.用量詞、謂詞來表述命題。

(1)凡是人都是要死的。

(2)某些實數(shù)是有理數(shù)。

?x(F(x)H(x)),其中F(x):x是人；H(x):ｘ是要死的；?x(G(x)∧Q(x)),其中G(x):x是實數(shù)；H(x):ｘ是有理數(shù)；2023/6/14174.

在個體域限制為（a）和（b）條件時，將下列命題符號化：（1）對于任意的x，均有x2－3x＋2＝(x－1)(x-2)（2）存在x，使得x＋5＝3其中：（a）個體域D1＝N（N為自然數(shù)集合）（b）個體域D2＝R（R為實數(shù)集合）解：(a)令F(x)：x2－3x＋2＝(x－1)(x-2)，G(x)：x＋5＝3。命題（1）的符號化形式為

xF(x)(*)命題（2）的符號化形式為

xG(x)(**)顯然（1）為真命題，而（2）為假命題。(b)在D2內(nèi)，（1）與（2）的符號化形式還是(*)和(**)式，（1）仍然為真命題，而此時（2）也為真命題。18謂詞邏輯中命題符號化一般遵循的原則：(1)名詞：專有名詞多譯為個體常元，如“地球”等；普通名詞一般譯為謂詞，如“自然數(shù)”；(2)代詞：無論是人稱代詞，如“你”，“我”，“他”等，還是指示代詞，如“這個”，“那個”等多譯為個體常元；(3)形容詞：多譯為謂詞；(4)動詞：多譯為謂詞；(5)數(shù)量詞：表示全體概念的數(shù)量詞，如“每個”、“任何”、“所有”等譯為全稱量詞，表示部分概念的數(shù)量詞，如“有”、“存在”、“若干”、“有些”等，譯為存在量詞；(6)副詞和前置詞與其它詞類合并，不再進行單獨分析；(7)連詞一般譯為邏輯聯(lián)結詞。2023/6/1419定義：不出現(xiàn)命題聯(lián)結詞和量詞的謂詞命名式

P(X1,X2…Xn)稱為謂詞演算的原子公式。A.原子公式2.謂詞合式公式前面例子中的1元謂詞F(x)，G(x)，2元謂詞H(x,y)，L(x,y)等都是原子公式。

2023/6/1420謂詞合式公式簡稱謂詞公式定義:1)原子公式是謂詞合式公式

2)若A，B是謂詞合式公式，則

(┐A)，(AB)，(AB)，(A→B)，(AB)，(XA)和(XA)是謂詞合式公式

3)只有有限次應用步驟1)和2)構成的公式才是謂詞合式公式注：由定義知，命題公式也是謂詞公式例：XR(X)┐(XR(X))(XR(X)→XS(X))┐(XR(X)XS(X))A(BC)命題公式均是謂詞公式

B.謂詞合式公式2023/6/1421定義:量詞的轄域是鄰接量詞之后的最小子公式，故除非轄域是個原子公式，否則應在該子公式的兩端有括號。例：XP(X)→Q(X)

X的轄域是P(X)X(P(X,Y)→Q(X，Y))P(Y,Z)

X的轄域是P(X，Y)→Q(X，Y)

(1)量詞的轄域

C.自由變元與約束變元2023/6/1422定義：在量詞X，X轄域內(nèi)變元X的一切出現(xiàn)叫約束出現(xiàn)，稱這樣的X為約束變元。

變元的非約束出現(xiàn)稱為自由出現(xiàn),稱這樣的變元為自由變元。例：指出下列謂詞公式中的自由變元和約束變元，并指明量詞的轄域X(P(X)R(X))→XP(X)Q(X)

解：表達式中的X(P(X)R(X))中X的轄域是P(X)R(X),其中的X是約束出現(xiàn)

Q(X)中的X是自由變元

2023/6/1423例：指出下列謂詞公式中的自由變元和約束變元。并指明量詞的轄域(2)X(P(X，Y)→YR(X，Y))

解：其中的P(X，Y)中的Y是自由變元，X是約束變元，

R(X，Y)中的X，Y是約束變元。

注：在一個公式中，一個變元既可以約束出現(xiàn)，又可以自由出現(xiàn)。為避免混淆可用改名規(guī)則對變元改名。2023/6/1424(1)若要改名，則該變元在量詞及該量詞的轄域中的所有出現(xiàn)須一起更改。(2)改名時所選用變元必須是量詞轄域內(nèi)未出現(xiàn)的，最好是公式中未出現(xiàn)的。注：對自由變元換名，可稱為代入D.約束變元改名規(guī)則2023/6/1425例1：X(P(X，Y)→YR(X，Y))可改為

X(P(X，Y)→ZR(X，Z))例2：XP(X)Q(X)可改為YP(Y)Q(X)例3：X(A(X)B(X，Y))C(X)D(W)可改為：X(A(X)B(X，Y))C(Z)D(W)注意：Z(A(Z)B(Z，Y))C(X)D(W)不可改為：Y(A(Y)B(Y，Y))C(X)D(W)

2023/6/1426E.閉公式定義：設A是任意的公式，若A中不含自由出現(xiàn)的個體變項，則稱A為封閉的公式，簡稱閉式。例如，x(F(x)

G(x))，

x

y(F(x)

G(x,y))都是閉式，而x(F(x)

G(x,y))，

zyL(x,y,z))都不是閉式。

要想使含有r(r≥1)個自由出現(xiàn)個體變項的公式變成閉式，至少要加上r個量詞

2023/6/1427例題：在一階邏輯中將簡單的數(shù)學命題符號化1.設個體域為整數(shù)集合Z，將下列問題符號化：(1)對于任意的x和y，存在著z，使得x+y=z;(2)存在著x，對于任意的y和z，均有y-z=x是不成立的。(3)設y=f(x)在x=x0處連續(xù)，將下面命題符號化。任給Z>0

，存在d

>0,使得當|x-x0|<d時，均有|f(x)-f(x0)|<Z.

?x?y?z(x+y=z)

(?x?y?z(x2+y2=z2)

?Z>0?d>0(|x-x0|<d|f(x)-f(x0)|<Z)2023/6/1428謂詞公式的解釋：定義一個解釋I由下面4部分組成：（1）非空個體域D；（2）D中一些特定元素的集合（3）D上特定函數(shù)集合（4）D上特定謂詞的集合

2023/6/1429在I下，下列哪些公式為真？哪些為假？哪些的真值還不能確定？(1)F(f(x,y),g(x,y))在I下，被解釋成“x+y=x˙y”,這不是命題(2)F(f(x,a),y)F(g(x,y),z)在I下，被解釋成“(x+0=y)(x˙y=z)”,這不是命題(3)F(g(x,y),g(y,z))在I下，被解釋成“x˙y≠y˙z”,這不是命題(4)?xF(g(x,y),z)在I下，被解釋成“?x(x˙y≠z)”,這不是命題(5)?xF(g(x,a),x)F(x,y)在I下，被解釋成“?x((x˙0=x)

(x=y))”,由于蘊含式前件為假，所以被解釋的公式為真。(6)?xF(g(x,a),x)在I下，被解釋成“?x(x˙0=x)”,這不是命題(7)?x?yF(f(x,a),y)F(f(y,a),x)在I下，被解釋成“?x?y((x+0=y)

(y+0=x))”,這是真命題(8)?x?y?zF(f(x,y),z)在I下，被解釋成“?