第一二章數(shù)理邏輯課件

第一篇數(shù)理邏輯一、數(shù)理邏輯（符號邏輯，現(xiàn)代邏輯）1.定義:用數(shù)學方法來研究人類推理過程的一門數(shù)學學科.邏輯：客觀事物在主觀意識中的反映；邏輯學：研究思維形式及思維規(guī)律的科學，它分為辯證邏輯和形式邏輯；判斷：利用概念對事物是否具有某種屬性進行肯定或否定的回答；推理：由一組前提推出某重結論。2．特點符號化，形式化即把邏輯所涉及的“概念、判斷、推理”用符號來表示，依據(jù)推理規(guī)則和公里體系，并基于符號串形式的演算來描述推理的一般規(guī)律。3．數(shù)理邏輯的研究方法將自然語言符號化形成數(shù)學語言；（符號語言、形式語言）根據(jù)公理系統(tǒng)及推理規(guī)則進行邏輯推理。（數(shù)學演算）4.數(shù)理邏輯的應用及其發(fā)展人工智能（語音識別、機器人）形式語義學第一章命題邏輯

§1.1、命題和聯(lián)結詞一、命題proposition1、命題引入為避免自然語言的不確定性及二義性，引入目標語言和一些符號公式，用以表達語言中的判斷和推理，從而形成數(shù)理邏輯的形式符號體系，符號化的對象是目標語言；目標語言：即我們的研究對象，也就是要研究無二義性的語言的范圍，即具有明確是、非概念的陳述句，因為它是表達判斷的。2、命題定義能判斷其含義為真或假的陳述句，具有唯一的真值稱為命題；一個命題具有唯一一個“值”，稱為真值，他僅有真或假（不可兼）兩種，記為true和false，簡記為T/1和F/0。例1：亞洲比歐洲大。我正在說謊。（悖論，自相矛盾）生命是有限的，思想是無限的。起立！（非陳述句）你們聽到了嗎？（非陳述句）我在講課。別的星球上有生物。毛澤東姥姥去世那天，天空正在下雪。X=23、命題表示法命題標識符：用大寫英文字母表示。P：我是中國人。Q：離散數(shù)學不好學。4、命題常量和變元命題常量：表示確定命題的命題標識符；命題變元：只表示任意命題位置標志的命題標識符；因命題變元課表示任意命題，無所謂真假值，所以它不是命題；指派：當命題變元P用一特定命題取代時，P才能確定真值，稱為對P~；5、原子命題與復合命題原子命題atomic：不能再分解為更簡單陳述語句的命題；復合命題compound：由聯(lián)結詞、標點符號和原子命題復合構成的命題；二、常用邏輯聯(lián)結詞（5個）聯(lián)接詞的作用將原子命題聯(lián)接成復合命題；相當于是對陳述句中的關聯(lián)詞的符號化處理。1、否定(┐)定義：設P為一命題，P的否定是一個新的命題，記為；若P為T，則為F，若P為F，則為T。與自然語言的關系：相當于不、否、非等；┐P真值表如表1.1所示。注意：否定的意義僅是修改命題的內容，沒有構成復合命題，它是一元運算。p┐p0110

表1.1┐P真值表2、合取（∧）定義：兩命題P、Q的合取是一復合命題，記為。當且僅當P、Q同時為T時，為T，其他情況為F。P∧Q真值表如表1.2所示。與自然語言的關系：相當于與、并且、和等，常表示遞進、并列、轉折這樣的關系，但新的復合命題不一定有意義，這是數(shù)理邏輯命題與自然語言的區(qū)別。

P

QP∧

Q000010100111

表1.2P∧Q真值表3.析?。ā牛┒x：兩命題P、Q的析取是一復合命題，記為。當且僅當P、Q同時為F時，為F，其他情況為T；與自然語言的關系：相當于可兼或，但新的復合命題不一定有意義；p∨

q真值表如表1.4所示。p

qp∨

q000011101111表1.3P∨Q真值表注：自然語言中的“或”是具有二義性的。自然語言中“或”的含義可以是“可兼或”，也可以是“排斥或”，還可以是“大約數(shù)量”，但數(shù)理邏輯中的“或”即析取指的是“可兼或”例3：畢業(yè)后，去西藏或去新疆。（排斥或）張三是黨員或者是班長。（可兼或）我做了20道或30道數(shù)學題。（大約數(shù)量）

4.蘊涵（→）

設P、Q是任意兩個命題，復合命題“如果P，則Q”稱為P與Q的蘊涵式，記作：P→Q。P稱為蘊涵式的前件，Q稱為蘊涵式的后件，→稱為蘊涵聯(lián)結詞。→經常表示自然語言的假設關系。P→Q的真值表如表1.4所示。P

QP→

Q001011100111表1.4P→Q真值表例4：如果我們再一次忽視日本人和美國人的野心，那么我們將不在有未來。如果摒棄了民族平等，那么我們將遭遇戰(zhàn)爭。張三（男）對李四說：我如果是女孩那么我肯定嫁給你。（永真）注：自然語言中“如果…那么…”這樣的語句，當前件為假時，不管結論真假，整個語句的意義往往無法判斷，但條件命題中，當前件為假時，條件命題為真，稱為“善意的推定”。p

q001010100111表1.5與自然語言的關系：用于表達一種充分必要條件，相當于“當且僅當”；例5：萬物生長，當且僅當有陽光普照。P:萬物生長;Q:有陽光普照;三、語言的翻譯1、符號語言翻譯成自然語言例6：P：我愛祖國，Q：我愛人民，P∧Q：我不僅愛祖國并且也愛人民。例7：P：小王是班長，Q：小王是三好學生，P∨Q：小王是班長或三好學生。例8：P：好好學習，Q：考試及格，

P→Q:如果好好學習的話，那么考試肯定能及格。2、自然語言翻譯成符號語言注意：先找出原子命題，再確定聯(lián)結詞例9：“我愛祖國也愛人民”可以先分解為兩個原子命題；P：我愛祖國；Q：我愛人民。P∧Q例10：我們不能既唱歌又跳舞；P：我們唱歌；Q：我們跳舞。┐(P∧Q)例11：不是你沒寫信就是信在途中丟失了；P：你沒寫信；Q：信在途中丟失了。符號化見表1.6。注：在進行自然語言符號化時，能準確表達語意的聯(lián)結詞有時不易確定，可以利用真值表來幫助確定。PQ命題真值110101011000表1.6§1.2命題公式及其賦值

一、命題公式（合式公式）1、定義：命題公式（合式公式），即由命題變元和命題聯(lián)結詞按照特定的構造規(guī)則形成的串，稱為命題公式，其中的命題變元稱為命題公式的分量；單個命題變元本身是一個合式公式；如果A和B是合式公式，則A∧B,A∨B,A→B,都是合式公式；當且僅當能夠有限次地應用（1）,（2）,（3）所得到的包含命題變元、聯(lián)結詞和括號的符號串稱為合式公式。注意1、命題公式是沒有真假值的，僅當在一個公式中命題變元用確定的命題代入時，才得到一個命題。這個命題的真值，依賴于變換變元的那些命題的真值；2、為了簡化合式公式的書寫，作了兩點約定，其一是最外層括號可以省略，其二是合式公式中的聯(lián)結詞運算符優(yōu)先次序為：┐∧∨→3、命題公式正確書寫：括號配對，相鄰的兩個命題變元之間有二元聯(lián)結詞，二元聯(lián)結詞之間應該有命題變元。

二、真值表truthtable1、命題公式的賦值（解釋）：設命題公式A(p1,p2…pn),其中p1,p2…pn為A中的命題變元，給p1,p2…pn各指派一個真值，稱對A的一次賦值（解釋）。如果指定的某組賦值使A的真值為1，則稱這組值為A的成真賦值，否則稱這組值為A的成假賦值。2、定義：在命題公式A(p1,p2…pn)中，對于分量（命題變元）指派真值的各種可能組合，就確定了這個命題公式的各種真值情況，將其匯列成表，就是命題公式的真值表；命題公式中變元真值指派組合數(shù)目決定于變元分量的個數(shù)，一般說，n個命題變元組成的命題公式共有2n種真值組合情況。例1P→Q┐P∨QPQP→Q┐P∨Q1111100001110011例2(┐P∨Q)∧(┐Q∨P)

(P∧Q)∨(┐P∨┐Q)PQ11111100000100000111(┐P∨Q)∧(┐Q∨P)

(P∧Q)∨(┐P∨┐Q)例3：(P∧Q)→P;┐(

P→(P∨Q))4、應用(1)等價式的證明，兩個命題公式等價iff對于分量的任一組真值指派對應的命題公式真值都相等。(2)命題公式類型的判斷1）重言式（永真式）：在命題公式A(p1,p2…pn)中，對命題公式A的所有命題變元賦值（2n次賦值），命題公式的真值都為1，則稱公式為重言式。2）矛盾式（永假式）：在命題公式A(p1,p2…pn)中，對命題公式A的所有變元賦值（2n次賦值），命題公式的真值都為0，則稱公式為矛盾式。3）如果A(p1,p2…pn)不是矛盾式，則A稱可滿足式。⑶主范式的求取，推理證明等?！?.3、基本等值式（等價式）一、等價式logicaleguivalence1、WffA和WffB等價定義給定兩個命題公式A和B，設p1,p2…pn為所有出現(xiàn)在A、B中的原子變元，若給定p1,p2…pn任一組真值指派，A、B的真值都相同，則稱A、B等價或邏輯相等記作。2、基本等價式(P15)3、等價式的證明1）真值表法若要證明命題公式A、B等價，先分別列出A、B的真值表，若A、B命題公式對應的真值表中的所有真值指派真值均相同，即可證明。PQP→Q┐P∨Q11111000011100012）推導法利用基本等值式，可以對命題公式中的某些子公式用與其等價的命題公式進行等價代換，進而對原公式進行變換，最終使兩命題公式變換為相同的命題公式。例1

P→(Q→R)Q→(P→R)左式P→（┐Q∨R）┐P∨(┐Q∨R)(┐P∨┐Q)∨R

(┐Q∨┐P)∨R

┐Q∨(┐P∨R)Q→(P→R)

例2P→(Q→R)(P∧Q)→R左式P→（┐Q∨R）┐P∨(┐Q∨R)(┐P∨┐Q)∨R┐(P∧Q)∨R

(P∧Q)→

R練習(P∨Q)→R(P→

R)∧(Q→

R)（PQ）（P∧Q)∨(┐P∧┐Q)4、命題公式化簡

例3((P→Q)(┐Q→┐P))∧R((P→Q)(P→Q))∧RT∧RR練習(P∧Q∧R)∨(┐P∧Q∧R)(p→(P∨Q))∨(P→R)§1.4析取范式與合取范式

一、析取范式1、析取范式iffA(A1∨

A2∨

…∨An），其中A1，

A2，

…，An都是由A中出現(xiàn)的命題變元不可兼或其否定由∧聯(lián)結詞組成的合取式。2、析取范式求法(P31)1）將命題公式中聯(lián)結詞轉換成┐∧∨。2）利用德摩根律把┐直接移入到每個命題變元之前。3）利用分配律或結合律將公式轉換成析取范式，并進行化簡。例1

(┐P∧R)∨┐(P→Q)(P∧

┐R)∨┐(┐P∨

Q)(P∧

┐R)∨

(P∧

┐Q)例2┐(P→R)∧(P∨┐Q)┐(┐P∨

R)∧(P∨┐Q)

(P∧┐R)∧(P∨┐Q)((P∧┐R)∧P)∨((P∧┐R)∧┐Q)

(P∧┐R)∨(P∧┐Q∧┐R)

二、合取范式1、合取范式iffA(A1∧

A2∧

…∧An），其中A1，

A2，

…，An都是由A中出現(xiàn)的命題變元不可兼或其否定由∨聯(lián)結詞組成析取式。2、合取范式求法(P31)1）將命題公式中聯(lián)結詞轉換成┐∧∨。2）利用德摩根律把┐直接移入每個命題變元之前。3）利用分配律或結合律將公式轉換成合取范式，并進行化簡。注：合取范式求法和析取范式求法相同。例3

(┐P→R)∨

(P∧┐Q)

(P∨R)∨(P∧┐Q)

(P∨R)∨(P∧┐Q)((P∨R)∨P)∧((P∨R)∨┐Q)

(P∨R

∨P)∧(P∨R∨┐Q)

(P∨R)∧(P∨┐Q∨R)

三、主析取范式1、相關概念1）小項（布爾合?。┰O命題公式為A(p1,p2…pn)，n個命題變元不可兼或其否定，并由合取聯(lián)結詞組成的符號串，即：每個命題變元不能與其否定同時出現(xiàn)，但必須出現(xiàn)且僅出現(xiàn)一次。2）小項（布爾合取）與合取式區(qū)別。3）小項性質：所有小項的吸取為永真，任意不同兩個小項的合取為永假。4）編碼表示:m111P∧Q∧Rm101P∧┐Q∧R2主析取范式定義iffA(A1∨

A2∨

…∨An），其中A1,

A2,

…,An是小項（布爾合?。?。求法

●真值表例4┐(P→R)∧(P∨┐Q)PQR(P→R)┐(P→R)(P∨┐Q)┐(P→R)∧(P∨┐Q)11110101100111101101010001110111000010100000110100001010主析取范式(P∧Q∧

┐R)∨(P∧

┐Q∧

┐R)2)推導法：先求析取范式，然后利用等價補項法求主析取范式，最后化簡。如上例┐(P→R)∧(P∨┐Q)┐(┐P∨

R)∧(P∨┐Q)

(P∧┐R)∧(P∨┐Q)((P∧┐R)∧P)∨((P∧┐R)∧┐Q)

(P∧┐R)∨(P∧┐R∧┐Q）((P∧┐R)∧(Q∨┐Q))∨(P∧┐Q∧┐R）((P∧┐R)∧Q)∨((P∧┐R)∧┐Q))∨(P∧┐Q∧┐R）

(P∧┐R∧Q)∨(P∧┐R∧┐Q)∨(P∧┐Q∧┐R）

(P∧Q∧┐R)∨(P∧┐Q∧┐R)m110∨m100

∑4,6

四、主合取范式1、相關概念1）大項（布爾析?。涸OA(p1，p2，…pn)，n個命題變元和其否定不可兼，由∧聯(lián)結詞組成的符號串，即：每個命題變元不能與其否定同時出現(xiàn)，但必須出現(xiàn)且僅出現(xiàn)一次。2）大項（布爾析?。┡c析取式區(qū)別。大項性質：所有大項的合取是永假，任意不同兩個大項析取是永真。4）編碼表示：M000=P∨Q∨R,M010=P∨┐Q∨R。2、主合取范式1）定義

iffA(A1∧

A2∧

…∧An）,其中A1,

A2…,An是大項（布爾析?。?）求法●真值表

上例┐(P→R)∧(P∨┐Q)PQR(P→R)┐(P→R)(P∨┐Q)┐(P→R)∧(P∨┐Q)11110101100111101101010001110111000010100000110100001010主合取范式：

(┐P∨┐Q∨┐R)∧(┐P∨Q∨┐R)∧(P∧

┐Q∧

┐R)∧(P∧

┐Q∧R)∧(P∧Q∧┐R)∧(P∧Q∧R)●推導法上例┐(P→R)∧(P∨┐Q)(P∧┐R)∧(P

∨┐Q)P∧┐R∧(P∨┐Q)(P∨(Q∧

┐Q))∧(┐R∨(P∧

┐P))∧((P∨┐Q)∨

(R∧

┐R))

(P∨Q)∧(P∨

┐Q)∧(P∨┐R)∧(┐P∨┐R)∧(P∨┐Q

∨R)∧(P∨┐Q∨┐R)(P∨Q∨R)∧(P∨Q∨┐R)∧(┐P∨

┐Q∨┐R)∧

(┐P∨Q∨┐R)∧(P∨┐Q∨R)∧(P∨┐Q∨┐R)M000∧M001∧M111∧M101∧M010∧M011

∏0,1,2,3,5,7五、編碼轉換法設命題公式為：A(p1，p2，…pn)，其主合取范式編碼集合為H1,主析取范式編碼集合為H2,則H1∪H2＝{0,1,…2n-1}=H,H1∩H2＝φ

,H1H,H2H,H1和H2為集合H的一個劃分。練習(P∧Q)∨┐(P→R)

(P→Q)→(P∧┐R)

(P→(Q∧R)∧(┐P→(┐Q∧┐R)§1.5、命題推理一、命題推理定義定義A→B為重言式iff,其中A是前提，B是A的有效結論，或B可由A邏輯的推出。對重言式定義推廣，令，則稱B是一組前提的有效結論，或B可由邏輯的推出，記作：。二、命題演算的公理化方法命題演算的公理化方法就是建立一個抽象更高概括性更強的形式化推理系統(tǒng)。1)字符表：命題變元、常用的5個聯(lián)結詞、括號和，。2)命題公式3)利用(1)基本等價式和蘊含式(P47):附加規(guī)則、化簡規(guī)則、假言推理、假言三段論、合取規(guī)則;(2)推理規(guī)則：P規(guī)則，T規(guī)則?！?.6、自然語言推理系統(tǒng)一、命題推理的方法 1、真值表法:A→B為重言式iff,寫出A→B的真值表，根據(jù)→的特殊性，有兩種判斷情況：A=1則B=1;B=0則A=0。例1：P→R,P∧QR∧QPQRP∧QP→RR∧Q1111111101001010101000000110110100100010100000102、證明法1)直接證明：利用PT規(guī)則和已知的等值式蘊含式，直接由前提推出結論。例2P→R,P∧QR∧Q(1)P∧QP(2)PT(1)(2)(3)P→RP(4)RT(2)(3)(4)(5)QT(1)(5)(6)

R∧QT(4)(5)(6)練習

P→QS∨RS→┐QR→┐Q┐P2)反證法：假設結論不成立，即結論的否定當做一個附加前提，最后推出矛盾。

例3P→Q,S∨R,S→┐Q,R→┐Q,┐P

(1)P

P(附加)(2)P→QP

(3)QT(1)(2)(3)(4)S→┐QP(5)Q→┐ST(4)(5)(6)┐ST

(3)(5)(6)(7)S∨RP(8)┐S→RT(7)(8)(9)RT(6)(8)(9)(10)R→┐QP(11)┐Q

T

(9)(10)(11)(12)Q∧┐QT

(3)(11)(12)練習P∨QP→RQ→S

┐S→R3)CP規(guī)則：僅限于結論中含有（可以轉換成）條件聯(lián)結詞，條件的前項當作一個附加前提題，最后推出條件的后項。例4P∨Q,P→R,Q→S,┐S→R(1)┐SP(附加前提)(2)Q→S

P(3)┐S→┐QT(2)(3)(4)┐QT(1)(3)(4)(5)P∨QP(6)┐Q→PT(5)(6)(7)PT(4)(6)(7)(8)P→RP(9)RT(7)(8)(9)練習A→(B→C),┐D∨A,BD→C用CP規(guī)則和直接證明方法P

→(Q

∨R)，┐S→┐Q,P∧┐SR用直接證明和反正法應用應用1一家航空公司，為了保證安全，用計算機復核飛行計劃。每臺計算機能給出飛行計劃正確或有誤得回答。由于計算機也可能發(fā)生故障，因此采用三臺計算機同時復核。由所給答案，再根據(jù)“少數(shù)服從多數(shù)”的原則作出判斷，試將結果用命題公式表示。解設C1,C2和C3分別表示三臺計算機的答案。S表示判斷結果，根據(jù)題意寫出真值表。C1C2C3S11111101101110000111010000000000

S

(C1∧C2∧C3)∨(C1∧C2∧┐C3)∨(C1∧┐C2∧C3)∨(┐C1∧C2

∧C3)應用2如果我上街了，我一定去新華書店。我沒上街，所以我沒去新華書店。推理是否正確。應用3一個公安人員審查一件盜竊案，根據(jù)如下查得的事實判斷真正的作案人。張三或李四盜竊了筆記本電腦；若張三做案，則作案時間不會是午夜之前；若是李四證詞是真的，則午夜時屋里有燈光；若李四證詞是假，則作案時間發(fā)生在午夜之前；午夜時午里燈滅了。結論李四第二章謂詞邏輯

§2.1、謂詞與客體一謂詞引入命題邏輯不足：解決不了牛頓三段論問題。例所有人都會死的，牛頓是人，所以牛頓會死的。P:人都要死的，Q:牛頓是人，R:牛頓會死的。P∧QR命題推理分析：無法揭示命題內部的結構和屬性；無法表達命題之間的邏輯關系和特征。因此需要功能更強的邏輯語言。二、謂詞與客體1、謂詞邏輯：由命題定義（反映判斷的陳述句）將命題分解成主語和謂語兩部分。2、客體（主語）1）客體變元：用小寫字母x,y等表示。2)客體常元：用小寫字母a,b等表示。3）客體域：客體變元的取值范圍。3、謂詞(謂語)用P（）表示。1)一元謂詞：P(x)描述客體的性質。例：張三是大學生。P(a)，a=張三2)多元謂詞：P(x,y)描述客體之間的關系。張三和李四是同學。P(a,b)，a=張三，b=李四4、命題函數(shù)：簡單命題函數(shù)和復合命題函數(shù)。命題函數(shù)不是命題，只有客體變元取特定值時才能是命題。三、量詞1、全稱量詞（）1）（）表示客體域內所有的客體。（）P(x)2）意義：3）特性謂詞當客體域用謂詞表示時則稱特性謂詞，在全稱量詞里特性謂詞以條件前項引入。例1：所有計算機學院的學生都是大學生。M(x)：計算機學院的學生，P(x)：x是大學生。()(M(x)→P(x))設客體域為計算機學院的學生，則翻譯為：()P(x)例2：所有人都會死的。M(x)：x是人，P(x)：x會死的。()(M(x)→P(x))設客體域是人，x會死的。（）P(x)：

2、存在量詞()1)()表示客體域內部分客體。()P(x)2)3)特性謂詞以引入。例3：有些計算機學院的學生喜歡唱歌。M(x)：計算機學院的學生，P(x)：x喜歡唱歌。

設客體域為計算機學院的學生。()P(x)例4：有些人不怕死。M(x)：x是人，P(x)：x不怕死。設客體域為人，則翻譯為：()P(x)

3、量詞的作用域(轄域)1）指導變元/作用變元：量詞后面緊跟的變元。2）約束變元與自由變元3）約束變元改名規(guī)則對于約束變元可以換名，其更改的變元名稱范圍是量詞中的指導變元，及該量詞作用域中所出現(xiàn)的該變元，在公式的其余部分不變。換名時不能引起新的重名。4）自由變元代入規(guī)則對于謂詞公式中的自由變元，可以做代入，代入時需對公式中出現(xiàn)該自由變元的每一處進行。用以代入的變元與原公式中所有變元的名稱不能相同。例5

2.2、謂詞公式與翻譯一、謂詞翻譯1、公式翻譯成自然語言2、自然語言符號化1)確定謂詞（一元，二元）；2）選擇量詞，注意量詞順序不能隨意顛倒；3）若客體域以特性謂詞形式給出，注意特性謂詞引入方式；4）由于謂詞刻畫程度不一樣，翻譯結果不唯一。例1：所有人都會犯錯誤。M(x)：x是人，P(x)：x犯錯誤例2：并不是所有人都會犯錯誤。M(x)：x是人，P(x)：x犯錯誤。例3：有些人會犯錯誤。M(x)：x是人，P(x)：x犯錯誤。例4：沒有人會犯錯誤。M(x)：x是人，P(x)：x犯錯誤。例5：有些人不犯錯誤。M(x)：x是人，P(x)：x犯錯誤。例6：所有人都不會犯錯誤?？偨Y：例4和例6不僅語義等價而且公式也等價。例2和例5不僅語義等價而且公式也等價。例7：有些女孩比所有男孩都聰明。M(x)：x是女孩，P(x)：x是男孩，R(x，y):x比y聰明。

例8：所有學生都喜歡某些明星。M(x)：x是學生，P(x)：x是明星，R(x，y):x喜歡y。例9：存在唯一一個自然數(shù)x,滿足x+5=7N(x):x是自然數(shù),P(x):x+5=7,G(x,y):x=y設客體域為N練習自然語言符號化所有有理數(shù)都是實數(shù)，某些有理數(shù)是整數(shù)，因此某些實數(shù)是整數(shù)。任何人如果喜歡步行，他就不喜歡乘汽車，每一個人或者喜歡乘汽車或者喜歡騎自行車。有的人不愛騎自行車，因而有的人不愛步行。每個大學生不是文科生就是理工科學生，有的大學生是優(yōu)等生，小張不是理工科學生，因而如果小張是大學生，他就是文科學生。有的兔子比所有烏龜跑得快。并不是所有的兔子都比烏龜跑得快?！?.3謂詞公式與解釋一、謂詞的合式公式（合式公式）⑴原子公式（n元謂詞公式）是合式公式；⑵若A是謂詞公式，則┐A也是合式公式；⑶若A、B是謂詞公式，則A∧B,A∨B,A→B,AB也是合式公式；⑷若A是謂詞公式，則A,A也是合式公式;(5)只有經過有限次地應用規(guī)則(1)、(2)、(3)和(4)所得到的公式是合式公式。以后簡稱謂詞公式。二、謂詞公式解釋1、基本概念封閉公式謂詞公式中不含自由變元，簡稱閉式。對謂詞公式變項用確定謂詞代替（等值代換）即對謂詞公式解釋。謂詞公式類型：永真式（重言式），永假式（矛盾式），可滿足式2、謂詞公式解釋非空個體域D；D中一部分特定元素(用來解釋個體常項)；D上一些特定函數(shù)(用來解釋出現(xiàn)的函數(shù)變項)；D上一些特定謂詞(用來解釋謂詞變項)。例1D={2,3};a=2;f(2)=3,f(3)=2;F(2)=0,F(3)=1G(2,3)=G(3,2)=1,G(2,2)=G(3,3)=0(1)(F(x)∨G(x,a))(F(3)∨G(3,2))∧(F(2)∨G(2,2))(1∨1)∧(0∨0)1∧00(2)(F(f(x))∧G(x,f(x)))(F(f(2))∧G(2,f(2)))∨(F(f(3))∧