1、第四章,謂 詞 邏 輯,第4章 謂詞邏輯,例如(著名的蘇格拉底三段論) （1）所有的人都是要死的； （2）蘇格拉底是人。 （3）蘇格拉底是要死的。,命題邏輯能夠解決的問題是有局限性的。只能進行命題間關系的推理，無法解決與命題的結構和成分有關的推理問題。,蘇格拉底三段論,P：所有的人都是要死的； Q：蘇格拉底是人。 R：蘇格拉底是要死的。,可見，P，Q，R為不同的命題，無法體現(xiàn)三者相互之間的聯(lián)系。,問題在于這類推理中，各命題之間的邏輯關系不是體現(xiàn)在原子命題之間，而是體現(xiàn)在構成原子命題的內(nèi)部成分之間。對此，命題邏輯將無能為力。,本章內(nèi)容,4.1 本章學習要求,4.2 謂詞邏輯中的基本概念與表示,命

2、題是具有真假意義的陳述句，從語法上分析，一個陳述句由主語和謂語兩部分組成。,例如，“計算機是現(xiàn)代科學技術必不可少的工具”,例如 “陳華是電子科技大學的學生”； “張強是電子科技大學的學生”。,若：是電子科技大學的學生,-P(陳華) -P(張強),謂詞,更一般地， P(x)：x是電子科技大學的學生。,x：個體詞,P：謂詞,P(x):命題函數(shù),個體詞與謂詞,定義4.2.1 在原子命題中，可以獨立存在的客體（句子中的主語、賓語等），稱為個體詞(Individual)。而用以刻劃客體的性質或客體之間的關系即是謂詞(Predicate)。,單純的謂詞或單純的個體詞都無法構成一個完整的邏輯含義，只有將它們

3、結合起來時才能構成一個獨立的邏輯斷言。,例1 成都、北京、趙明、20060806班、計算機科學等等僅僅是簡單的個體常量；“是中國的首都”、“是計算機的基礎課程”等僅僅是簡單的謂詞，它們都不能構成完整的句子。,個體詞的分類,表示具體的或特定的個體詞稱為個體常量(Individual Constant)，一般個體詞常量用帶或不帶下標的小寫英文字母a, b, c，a1, b1, c1,等表示； 表示抽象的或泛指的個體詞稱為個體變量(Individual Variable)，一般用帶或不帶下標的小寫英文字母x, y, z, , x1, y1, z1, 等表示。,例子,例2 考察下列句子： （1）北京是

4、中國的首都； （2）離散數(shù)學是計算機的基礎課程； （3）劉翔是一個跨欄世界冠軍； （4）中國人是很聰明的。,個體域,定義4.2.2 個體詞的取值范圍稱為個體域(或論域) (Individual Field)，常用D表示； 宇宙間的所有個體域聚集在一起所構成的個體域稱為全總個體域(Universal Individual Field)。,n元謂詞,定義4.2.3 設D為非空的個體域，定義在Dn(表示n個個體都在個體域D上取值)上取值于0,1上的n元函數(shù)，稱為n元命題函數(shù)或n元謂詞(Propositional Function)，記為P(x1, x2, , xn)。此時，個體變量x1, x2, ,

5、 xn的定義域都為D，P(x1, x2, , xn)的值域為0, 1。,例4.2.1,設有如下命題，并用n元謂詞進行表示。 P：王童是一個三好學生； Q：李新華是李蘭的父親； R：張強與謝莉是好朋友； S：武漢位于北京和廣州之間。,S(x)：x是一個三好學生 a：王童 命題P可表示為：S(a),F(x, y)：x是y的父親 b：李新華 c：李蘭 命題Q可表示為：F(b, c),T(x, y)：x與y是好朋友 d：張強 e：謝莉 命題R可表示為：T(d, e),B(x,y,z)：x位于y和z之間 f：武漢 g：北京 h：廣州 命題S可表示為：B(f, g, h),結論,謂詞中個體詞的順序是十分重

6、要的，不能隨意變更。如命題F(b, c)為“真”，但命題F(c, b)為“假”； 一元謂詞用以描述某一個個體的某種特性，而n元謂詞則用以描述n個個體之間的關系。 0元謂詞(不含個體詞的)實際上就是一般的命題；,結論（續(xù)）,具體命題的謂詞表示形式和n元命題函數(shù)(n元謂詞)是不同的，前者是有真值的，而后者不是命題，它的真值是不確定的。如上例中S(a)是有真值的，但S(x)卻沒有真值； 一個n元謂詞不是一個命題，但將n元謂詞中的個體變元都用個體域中具體的個體取代后，就成為一個命題。而且，個體變元在不同的個體域中取不同的值對是否成為命題及命題的真值有很大的影響。,4.2.2 量詞,例4.2.2 符號化

7、下述命題： （1）所有的老虎都要吃人； （2）每一個大學生都會說英語； （3）所有的人都長著黑頭發(fā)； （4）有一些人登上過月球； （5）有一些自然數(shù)是素數(shù)。,T(x)：x是素數(shù) 則有：有一些x，T(x) x自然數(shù),S(x)：x登上過月球 則有：有一些x，S(x) x人,R(x)：x長著黑頭發(fā) 則有：所有的x，R(x) x人,Q(x)：x會說英語 則有：每一個x，Q(x) x大學生,P(x)：x會吃人 則有：所有的x，P(x) x 老虎,量詞含義,有些x； 至少有一個x； 某一些x； 存在x； 等等。,所有的x； 任意的x； 一切的x； 每一個x； 等等。,全稱量詞與存在量詞,定義4.2.4 稱

8、(x)為全稱量詞（Universal Quantifier），(x)為存在量詞（Existential Quantifier），其中的x稱為作用變量（Function Variable）。一般將其量詞加在其謂詞之前，記為(x)F(x)，(x)F(x)。此時，F(xiàn)(x)稱為全稱量詞和存在量詞的轄域(Scope)。,（1）所有的老虎都要吃人； （2）每一個大學生都會說英語； （3）所有的人都長著黑頭發(fā)； （4）有一些人登上過月球； （5）有一些自然數(shù)是素數(shù)。,例4.2.2(續(xù)),(x)P(x) x 老虎 (x)Q(x) x大學生 (x)R(x) x人 (x)S(x) x人 (x)T(x) x自然數(shù)。

9、,不便之處,從書寫上十分不便，總要特別注明個體域； 在同一個比較復雜的句子中，對于不同命題函數(shù)中的個體可能屬于不同的個體域，此時無法清晰表達； 如例 (1)和(4)的合取 (x)P(x)(x)R(x),x人,x老虎,不便之處(續(xù)),若個體域的注明不清楚，將造成無法確定其真值。即對于同一個n元謂詞，不同的個體域有可能帶來不同的真值。 例如 對于語句“(x)(x+6 = 5)”可表示為：“有一些x，使得x+6 = 5”。該語句在下面兩種個體域下有不同的真值： （a）在實數(shù)范圍內(nèi)時，確有x=-1使得x+6 = 5，因此，(x)(x+6 = 5)為“真”； （b）在正整數(shù)范圍內(nèi)時，則找不到任何x，使得

10、x+6=5為“真”，所以，(x)(x+6=5)為“假”。,不便之處的根源,對了，都是因為需要特別標注每個謂詞的個體域所致！,特性謂詞,新的問題出現(xiàn)了，U(x)如何與(x)P(x)結合才符合邏輯呢？,謂詞邏輯符號化的兩條規(guī)則,統(tǒng)一個體域為全總個體域，而對每一個句子中個體變量的變化范圍用一元特性謂詞刻劃之。這種特性謂詞在加入到命題函數(shù)中時必定遵循如下原則：,（1）對于全稱量詞(x)，刻劃其對應個體域的特性謂詞作為蘊涵式之前件加入。,（2）對于存在量詞(x)，刻劃其對應個體域的特性謂詞作為合取式之合取項加入。,特性謂詞的例子,想想，為什么要這樣規(guī)定特性謂詞加入的原則呢？若不遵循會出現(xiàn)什么樣的問題？,

11、例如，符號化“所有的老虎都要吃人”這個命題,若P(x)：x會吃人 U(x)：x是老虎 則符號化的正確形式應該是 (x)(U(x)P(x) 它的含義是：“對于任意的x,如果x是老虎，則x會吃人”，符合原命題的邏輯含義。,若符號化為 (x)(U(x)P(x) 它的含義是：“對于任意的x,x是老虎，并且x會吃人”，與原命題“所有的老虎都要吃人”的邏輯含義不符。,例4.2.3,用謂詞邏輯符號化下述語句： (1) 天下烏鴉一般黑； (2) 沒有人登上過木星； (3) 在美國留學的學生未必都是亞洲人； (4) 每個實數(shù)都存在比它大的另外的實數(shù)； (5) 盡管有人很聰明，但未必一切人都聰明； (6) 對于任

12、意給定的0，必存在著0，使得對任意的x，只要|x-a|，就有|f(x)-f(a)|成立。,例4.2.3(續(xù)),（1）天下烏鴉一般黑 設 F(x)：x是烏鴉；G(x, y)：x與y一般黑，則： (x)(y)(F(x)F(y)G(x, y) 或者(x)(y)(F(x)F(y)G(x, y)； （2）沒有人登上過木星 設H(x)：x是人；M(x)：x登上過木星，則： (x)(H(x)M(x) 或者 (x)(H(x)M(x)；,例4.2.3(續(xù)),（3）在美國留學的學生未必都是亞洲人 設A(x)：x是亞洲人； H(x)：x是在美國留學的學生，則： (x)(H(x)A(x) 或者 (x)(H(x)A(x

13、)； （4）每個實數(shù)都存在比它大的另外的實數(shù) 設R(x)：x是實數(shù)；L(x, y)：x小于y，則： (x)(R(x)(y)(R(y)L(x, y)；,例4.2.3(續(xù)),（5）盡管有人很聰明，但未必一切人都聰明 設M(x)：x是人；C(x)：x很聰明，則： (x)(M(x)C(x)(x)(M(x)C(x)； （6）對于任意給定的0，必存在著0，使得對任意的x，只要|x-a|0)()(0)(x) (|x-a|)(|f(x)-f(a)|)。,4.2.3 謂詞的語言翻譯,特殊的，當個體域Dx0, x1, 是可數(shù)集合時，上述(x)G(x)、(x)G(x)的真值可表示為： (x)G(x)=G(x0)G(

14、x1). (x)G(x)=G(x0)G(x1).,個體域可數(shù)或有限,更特別的，當個體域Dx0, x1, xn是有限集合時，上述(x)G(x)、(x)G(x)的真值可以用與之等價的命題公式來進行表示。 (x)G(x)=G(x0)G(x1).G(xn) (x)G(x)=G(x0)G(x1).G(xn),例4.2.5,設P(x)：x是素數(shù)；I(x)：x是整數(shù)；Q(x, y)：x+y=0。用語句描述下述句子，并判斷其真假值。 （1）(x)(I(x)P(x)； （2）(x) (I(x)P(x)； （3）(x) (y)(I(x)I(y)Q(x, y)； （4）(x)(I(x)(y)(I(y)Q(x, y)

15、； （5）(x)(y)(I(x)(I(y)Q(x, y)。,“存在著整數(shù)x，使得對任意的整數(shù)y，都有x+y=0”， 真值為“假”。,“對任意的整數(shù)x，都存在著整數(shù)y，使得x+y=0” 真值為“真”；,“對任意的整數(shù)x，y，都有x+y=0”， 真值為“假”；,“存在一些整數(shù)x，x是素數(shù)”， 真值為“真”；,“對任意的整數(shù)x，x一定是素數(shù)”， 真值為“假”；,4.2.4 謂詞翻譯難點,一元謂詞用以描述某一個個體的某種特性，而n元謂詞則用以描述n個個體之間的關系； 如有多個量詞，則讀的順序按從左到右的順序；另外，量詞對變元的約束，往往與量詞的次序有關，不同的量詞次序，可以產(chǎn)生不同的真值，此時對多個量

16、詞同時出現(xiàn)時，不能隨意顛倒它們的順序，顛倒后會改變原有的含義。,謂詞翻譯難點（續(xù)）,根據(jù)命題的實際意義，選用全稱量詞或存在量詞。全稱量詞加入時，其刻劃個體域的特性謂詞將以蘊涵的前件加入，存在量詞加入時，其刻劃個體域的特性謂詞將以合取項加入； 有些命題在進行符號化時，由于語言敘述不同，可能翻譯不同，但它們表示的意思是相同的，即句子符號化形式可不止一種。,例4.2.4 將下列命題符號化 （1）兔子比烏龜跑得快； （2）有的兔子比所有烏龜跑得快； （3）并不是所有的兔子都比烏龜跑得快； （4）不存在跑得同樣快的兩只兔子。,(x) (y)(P(x)Q(y)R(x, y) 或者 (x)(y)(P(x)Q

17、(y)R(x, y),4.2.5 謂詞翻譯的應用,謂詞設定：P(x)：x是兔子；Q(x)：x是烏龜； R(x, y)：x比y跑得快； T(x, y)：x與y跑得同樣快。,(x)(P(x)(y)(Q(y)R(x, y),(x)(y)(P(x)P(y)T(x, y) 或者 (x)(y)(P(x)P(y) T(x, y),(x) (y)(P(x)Q(y)R(x, y),例4.2.5,符號化下述一組語句： 只要是需要室外活動的課，郝亮都喜歡；所有的公共體育課都是需要室外活動的課；籃球是一門公共體育課；郝亮喜歡籃球這門課。 解：設 O(x)：表示x是需要室外活動的課； L(x, y)：表示x喜歡y； S

18、 (x)：表示x是一門公共體育課； Hao：表示郝亮；Ball：表示籃球。,(x)(S(x)O(x),S(ball),L(Hao, Ball),(x)(O(x)L(Hao, x),4.3 謂詞合式公式與解釋,謂詞公式涉及如下四種符號： （1）常量符號：用帶或不帶下標的小寫英文字母a, b, c, , a1, b1, c1, 來表示。當個體域名稱集合D給出時，它可以是D中的某個元素； （2）變量符號：用帶或不帶下標的小寫英文字母x, y, z, ., x1, y1, z1,.來表示。當個體域名稱集合D給出時，它可以是D中的任意元素；,符號定義,（3）函數(shù)符號：用帶或不帶下標的小寫英文字母f, g

19、, h, ., f1, g1, h1, .來表示。當個體域名稱集合D給出時，n元函數(shù)符號f(x1, x2, , xn)可以是DnD的任意一個函數(shù)； （4）謂詞符號：用帶或不帶下標的大寫英文字母P, Q, R,., P1, Q1, R1.來表示。當個體域名稱集合D給出時，n元謂詞符號P(x1, x2, , xn)可以是Dn0，1的任意一個謂詞。,為何需要函數(shù)符號？,例如 符號化“周紅的父親是教授”： 設f(x)：x的父親； P(x)：x是教授； c：周紅 此時P(f(c)表示“周紅的父親是教授”這一命題。,函數(shù)的使用給謂詞邏輯中的個體詞 表示帶來了很大的方便,項與原子公式,定義4.3.2 若P(

20、x1,x2,xn)是n 元謂詞，t1，t2，tn是項，則稱P(t1,t2,tn)為原子謂詞公式(Atomic Propositional Formulae)，簡稱原子公式(Atomic Formulae)。,定義4.3.1 謂詞邏輯中的項(Term)，被遞歸地定義為： （1）任意的常量符號或任意的變量符號是項； （2）若f(x1, x2, , xn)是n 元函數(shù)符號，t1,t2, ,tn是項，則f(t1, t2, , tn)是項； （3）僅由有限次使用(1)，(2)產(chǎn)生的符號串才是項。,定義4.3.3,滿足下列條件的表達式，稱為合式公式(Well-Formed Formulae/Wff)，簡稱

21、公式(Formulae)。 （1）原子公式是合式公式； （2）若G，H是合式公式，則 (G)、(H)、(GH)、(GH)、(GH)、(GH) 也是合式公式； （3）若G是合式公式，x是個體變量，則 (x)G、(x)G 也是合式公式； （4）僅僅由(1)-(3)產(chǎn)生的表達式才是合式公式。,例子,(x)(y)(P(x, y)(Q(x, y)R(x, a, f(z)， (x)(P(x)(y)R(x, y)， (x)(P(x) R(x)。 等都是公式。 而 (x)P(x)R(x)(y)， (y)(x)(P(x,y)。 等則不是公式。,4.3.2 自由變元和約束變元,定義4.3.4 給定一個合適公式G，

22、若變元x出現(xiàn)在使用變元的量詞的轄域之內(nèi)，則稱變元x的出現(xiàn)為約束出現(xiàn)(Bound Occurrence)，此時的變元x稱為約束變元(Bound Variable)。若x的出現(xiàn)不是約束出現(xiàn)，則稱它為自由出現(xiàn)(Free Occurrence)，此時的變元x 稱為自由變元(Free Variable)。,量詞轄域的確定方法： （1）若量詞后有括號，則括號內(nèi)的子公式就是該量詞的轄域； （2）若量詞后無括號，則與量詞鄰接的子公式為該量詞的轄域。,例4.3.1,確定以下公式各量詞的轄域以及各個體變量為自由變元還是約束變元。 （1）(x)(P(x)(y)R(x, y)； （2）(x)P(x)Q(x, y)；

23、（3）(x)(y)(P(x, y)Q(y, z) (x)R(x,y)； （4）(x)(P(x)R(x)(y)Q(x, y)。,例4.3.1（續(xù)）,解 在(1)中，P(x)中x，R(x, y)的x，y都為約束變元。 在(2)中，所以P(x)中的x為約束變元，Q(x, y)中的x，y是自由變元。 在(3)中，P(y, z)、Q(x, y)中的x, y都為約束變元，R(x, y)中的x為約束變元，但y為自由變元。 在(4)中，P(x)，R(x)中的x為約束變元，Q(x, y)中的x為自由變元、y是約束變元。,變元混淆,（4）(x)(P(x)R(x)(y)Q(x, y),約束變元,自由變元,在一個公式

24、中，某一個變元的出現(xiàn)即可以是自由的，又可以是約束的，如(4)中的x。為了使得我們的研究更方便，而不致引起混淆，同時為了使其式子給大家以一目了然的結果，對于表示不同意思的個體變元，我們總是以不同的變量符號來表示之。,兩個規(guī)則,規(guī)則1(約束變元的改名規(guī)則)： （1）將量詞中出現(xiàn)的變元以及該量詞轄域中此變量之所有約束出現(xiàn)都用新的個體變元替換； （2）新的變元一定要有別于改名轄域中的所有其它變量。 規(guī)則2(自由變元的代入規(guī)則)： （1）將公式中出現(xiàn)該自由變元的每一處都用新的個體變元替換； （2）新變元不允許在原公式中以任何約束形式出現(xiàn),例4.3.2,（1）將公式(x)(P(x)Q(x, y)R(x,

25、y)中的約束變元x進行改名； （2）將公式(x)(P(x)Q(x, y)R(x, y)中的自由變元y進行代入。 解 利用規(guī)則1對x進行改名，則： (z)(P(z)Q(z, y)R(x, y) (z)(P(z)R(x, y)R(x, y) (y)(P(y)R(y, y)R(x, y),-對 -錯 -錯,利用規(guī)則2對y進行代入，則： (x)(P(x)Q(x, z)R(x, z) (x)(P(x)Q(x, z)R(x, y) (x)(P(x)Q(x, x)R(x, x),-對 -錯 -錯,改名規(guī)則和代入規(guī)則的關系,改名規(guī)則和代入規(guī)則之間的共同點都是不能改變原有的約束關系，而不同點是： （1）施行的對

26、象不同：改名規(guī)則是對約束變元施行，代入規(guī)則是對自由變元施行； （2）施行的范圍不同：改名規(guī)則可以只對公式中的一個量詞及其轄域內(nèi)施行，即只對公式的一個子公式施行；而代入規(guī)則必須對整個公式同一個自由變元的所有自由出現(xiàn)同時施行，即必須對整個公式施行；,改名規(guī)則和代入規(guī)則的關系（續(xù)）,（3）施行后的結果不同：改名后，公式含義不變，因為約束變元只改名為另一個個體變元，約束關系不改變，約束變元不能改名為個體常量；代入后，不僅可用另一個個體變元進行代入，并且也可用個體常量去代入，從而使公式由具有普遍意義變?yōu)閮H對該個體常量有意義，即公式的含義改變了。,閉式的定義,定義4.3.5 設G是任意一個公式，若G中無自

27、由出現(xiàn)的個體變元，則稱G為封閉的合適公式，簡稱閉式。 例如 (x)(P(x)(y)R(x, y) 是一個閉式。,閉式一定是命題。,4.3.3 謂詞合式公式的解釋,定義4.3.6 謂詞邏輯中公式G 的每一個解釋I(Explanation)由如下四部分組成： （1）非空的個體域集合D ； （2）G 中的每個常量符號，指定D 中的某個特定的元素； （3）G 中的每個n 元函數(shù)符號，指定Dn到D中的某個特定的函數(shù)； （4）G 中的每個n 元謂詞符號，指定Dn到0, 1中的某個特定的謂詞。,公式的解釋,例4.3.3 設有公式： (x)(P(x)Q(x)(x)P(x)(x)Q(x)， 在個體域D=a, b

28、上，構造兩個使公式分別為真和假的解釋。,思考一下，謂詞邏輯中的一個公式G可以像命題邏輯中的公式那樣列出真值表來研究它的真值情況么？,例4.3.3,解 1）構造解釋I1為 P(a) = 0，P(b) = 0，Q(a) = 1，Q(b) = 1， 則(P(a)Q(a)(P(b)Q(b)在此解釋I1下真值為1，(P(a)P(b)(Q(a)Q(b)在此解釋I1下真值為1，即I1使得等價聯(lián)結詞前面的(x)(P(x)Q(x)為真，同樣使得等價聯(lián)結詞后面的(x)P(x)(x)Q(x)為真，因此，這樣的解釋使得原公式的真值為真。,例4.3.3（續(xù)）,（2）構造解釋I2為 P(a) = 0，P(b) = 1，Q

29、(a) = 0，Q(b) = 1， 則(P(a)Q(a)(P(b)Q(b)在此解釋I2下真值為1，(P(a)P(b)(Q(a)Q(b)在此解釋I2下真值為0，即I2使得等價聯(lián)結詞前面的(x)(P(x)Q(x)為真，而使得等價聯(lián)結詞后面的(x)P(x)(x)Q(x)為假，因此，這樣的解釋使得公式(x)(P(x)Q(x)(x)P(x)(x)Q(x) 的真值為假。,例4.3.4,設有公式(x)(P(f(x)Q(x，f(a)。在如下給定的解釋下，判斷該公式的真值。 .個體域為D，； .a指定為：； .f()指定為：, f()指定為：； .P()指定為：1, P()指定為：0， Q(,)指定為：0， Q

30、(,)指定為：1， Q(,)指定為：1， Q(,)指定為：1。,例4.3.4（續(xù)）,解 因當x時，有： f()，P(f(x)P(f()P()1, f(a)f()， Q(x，f(a)Q(，f()Q(，)1。 所以：P(f()Q(,f(a)111， 即存在x,使得P(f()Q(，f(a)1， 即： (x)(P(f(x)Q(x，f(a)1。,4.3.4 謂詞合式公式的分類,例4.3.5 給出公式：P(a)(x)P(x)和(x)P(x)P(a)，判斷公式在給定的解釋下的真值。,解（1）對于公式P(a)(x)P(x)，對任何解釋I： （a）當P(a)取值為真時，(x)P(x)也必為真， 此時，P(a)(

31、x)P(x)的真值為真； （b）當P(a)取值為假時，(x)P(x)可為真，也 可為假，此時，P(a)(x)P(x)的真值為真；所以，P(a)(x)P(x)在任何情況下的真值恒為真。,例4.3.5（續(xù)）,（2）對于公式(x)P(x)P(a)，對任何的解釋I： （a）當(x)P(x)取值為真時，P(a)也必為真， 此時，(x)P(x)P(a)的真值為真； （b）當(x)P(x)取值為假時，P(a)可為真，也 可為假，此時，(x)P(x)P(a)的真值為 真。 所以，(x)P(x)P(a)在任何情況下的真值恒為真。,例4.3.6,判斷下列公式的真假。 （1）P(x, y)Q(x,y)P(x, y)

32、； （2）P(x, y)P(x, y)； （3）P(x, y)P(x, y)。,解 無論在何種結構中，無論對變元作何種賦值，公式(1)，(2)均取真值T，而公式(3)均取真值F。 從而(1)，(2)就是關于一切結構與一切賦值下恒取“T”值的謂詞公式，(3)就是關于一切結構與一切賦值下恒取“F”值的謂詞公式。,謂詞合式公式的分類,定義4.3.7 （1）公式G稱為有效公式，如果G在它所有的解釋I下都取值為“真”。 （2）公式G稱為矛盾公式，如果G在它所有的解釋I下都取值為“假”。 （3）公式G稱為可滿足公式，如果至少有一種解釋I使得G取值為“真”。,公式之間的關系,從上述定義可知三種特殊公式之間的

33、關系： （1）有效公式G的否定G為矛盾公式；矛盾公式G的否定G為有效公式。 （2）有效公式一定為可滿足公式。,謂詞邏輯的判定問題,若說謂詞邏輯是可判定的，就要求給出一個能行的方法，使得對任一公式都能判斷是否是有效的。所謂能行的方法，乃是一個機械方法，可一步一步做下去，并在有窮步內(nèi)實現(xiàn)判斷。,謂詞公式的可判定性,（1）謂詞邏輯是不可判定的； （2）只含有一元謂詞變項的公式是可判定的； （3）如下形式的公式： (x1)(x2)(xn)P(x1, x2, , xn)， (x1)(x2)(xn)P(x1, x2, ,xn)。 若P中無量詞和其它自由變元時，也是可判定的； （4）個體域有窮時的謂詞公式是

34、可判定的。,4.3.5 謂詞合式公式的基本等價關系,定義4.3.8 公式G，H稱為等價的(Equivalent)，記為G = H，如果公式G H是有效公式。,定義4.3.9 設(P1,P2,Pn)是命題演算中的命題公式，P1,P2,Pn是G中的命題變元，當用任意的謂詞公式Gi(1in)分別代入Pi后，得到的新謂詞公式(G1,G2,Gn)稱為原公式的代入實例。,定理4.3.1 永真（假）公式的任意一個代入實例必為有效（矛盾）公式。,定理4.3.2 設G1是G的子公式(即 G1是公式G的一部分)，H1是任意的謂詞公式，在G中凡出現(xiàn)G1處都以H1替換后得到新的謂詞公式H，若G1H1，則GH。,命題演

35、算中的24個基本的等價公式在謂詞演算中仍成立,謂詞演算中的有效公式,（1）E25：(x)G(x) = (y)G(y)； (改名規(guī)則) E26：(x)G(x) = (y)G(y)； （2）E27： (x)G(x) = (x)G(x)； E28：(x)G(x) = (x)G(x)； (量詞轉換律/量詞否定等值式) （3）E29：(x)(G(x)S) = (x)G(x)S； E30：(x)(G(x)S) = (x)G(x)S； E31：(x)(G(x)S) = (x)G(x)S； E32：(x)(G(x)S) = (x)G(x)S； (量詞轄域的擴張與收縮律),謂詞演算中的有效公式（續(xù)）,（4）E3

36、3：(x)(G(x)H(x) =(x)G(x)(x)H(x)； E34：(x)(G(x)H(x) =(x)G(x)(x)H(x)； (量詞分配律) （5）E35：(x)G(x)(x)H(x) =(x)(y)(G(x)H(y)； E36：(x)G(x)(x)H(x) =(x)(y)(G(x)H(y)；,例1,設P(x)：x今天來上課，個體域為計算機學院2006級全體同學的集合。則： 1.(x)P(x)表示所有同學今天都來上課了； (x)P(x)表示不是所有的同學今天來上課了； (x)P(x)表示今天有同學沒來上課。 所以， (x)P(x)=(x)P(x) 2. 類似的，(x)P(x)=(x)P(

37、x),例2,1.設G(x)：x勤奮學習；H(x)：x喜歡體育活動。 其中：個體域是大學里的學生。 則(x)(G(x)H(x)表示： 大學里的所有學生即勤奮學習又喜歡體育活動”； (x)G(x)(x)H(x)表示： “大學里的所有學生都勤奮學習且大學里所有的學生都喜歡體育活動”。 兩者意義是相同的。 即有： (x)(G(x)H(x)=(x)G(x)(x)H(x),例2（續(xù)）,2.設G(x)：x勤奮學習；H(x)：x喜歡體育活動。其中：個體域是大學里的學生。 則(x)(G(x)H(x)表示： “大學里有些學生勤奮學習或喜歡體育活動”； (x)G(x)(x)H(x)表示： “大學里有些學生勤奮學習或

38、大學里有些學生喜歡體育活動”。 兩者意義是相同的。 所以,(x)(G(x)H(x)(x)G(x)(x)H(x),4.3.6 謂詞合式公式難點,4.3.7 謂詞合式公式的應用,例4.3.7 利用謂詞之間的等價關系證明下列公式之間的關系：(x)P(x)Q(x)=(y)( P(y)Q(x),證明 (x)P(x)Q(x) = (x)P(x)Q(x) = (x)P(x)Q(x) = (y)P(y)Q(x) = (y)(P(y)Q(x) = (y)(P(y)Q(x),例4.3.8,判斷(x)P(x)Q(x)(x)P(x)(x)Q(x)是否為一個有效公式。,解 設個體域D=2, 4, 6, 8， P(x)：x能被2整除；Q(x)：x能被4整除。 可知(x)P(x) 真值為真，(x)Q(x) 真值為假。 1）自由變元x=4 原式真值=（1Q(4)（10）=0 故 (x)P(x)Q(4)(x)P(x)(x)Q(x)的真值為假。所以原式不是有效公式。,例4.3.8（續(xù)）,2）自由變元x=6 原式真值 =（1 Q(6)）（10）= 1 故(x)P(x)Q(6)(x)P(x)(x)Q(x)的真值為真。 綜上所述，個體域中有些個體使原式的真值為真，有些個體使原式的真值為假，因此，該公式