數(shù)理邏輯與集合論：4-1 謂詞邏輯的基本概念

1、請(qǐng)交作業(yè)2作業(yè)講評(píng)1P12：2(2)用自然語句敘述：今天今天不是不是既既很冷很冷又又下雪。下雪。今天今天不不很冷很冷或者或者不不下雪。下雪。若若今天很冷今天很冷則則正在下雪。正在下雪。今天今天不不很冷很冷或者或者正在下雪。正在下雪。今天今天不是不不是不很冷。很冷。今天今天不不很冷很冷當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)正在下雪。正在下雪。P12：3n對(duì)下列公式直觀敘述在什么樣的解釋下為真，并列寫出真值表來驗(yàn)證。(5) P(Q R) P Q R 只有只有P= =Q= =T 且且 R=F時(shí)時(shí) 上面兩個(gè)公式上面兩個(gè)公式 為假為假P13：5n形式化下列自然語言：(5)他個(gè)子高或者他個(gè)子矮而很胖。n設(shè)設(shè)P：他：他個(gè)子個(gè)子高

2、，高， Q：他很胖：他很胖P ( P Q) (7)如果水是清的，那么或者張三能見到池底或者他是個(gè)近視眼。n設(shè)設(shè)P：水是清的，：水是清的， Q：張三能見到池底，：張三能見到池底， R：張三是個(gè)近視眼：張三是個(gè)近視眼 P ( (QR)(Q R) P ( (Q R)不可兼或不可兼或P ( P Q) P37: 2n 分別由真值表的T和F來列到A、B、C的表達(dá)式n A = ( PQ) ( P Q) (PQ) = = P Qn B = ( PQ) (P Q) = = (P Q) ( (P Q )n C = PQ = (PQ) ( P Q) ( (P Q)PQAB CFFTTTFTTFFTFTFFTTFTF

3、P37: 3 PQ = (PQ)P Q = (P) Q = (PP)QP37: 3 P Q = (PQ)PQ = (P)Q = (PP)Q第2章 命題邏輯的等值和推理演算 2.1 等值定理2.2 等值公式2.3 命題公式與真值表的關(guān)系2.4 聯(lián)結(jié)詞的完備集2.5 對(duì)偶式2.6 范式2.7 推理形式2.8 基本的推理公式2.9 推理演算2.10 歸結(jié)推理法討論討論等值演算等值演算討論討論推理演算推理演算常用基本推理規(guī)則 (1) 前提引入規(guī)則前提引入規(guī)則(2) 結(jié)論引入規(guī)則結(jié)論引入規(guī)則(3) 代入規(guī)則代入規(guī)則(4) 置換規(guī)則置換規(guī)則(5)假言推理假言推理(分離規(guī)則分離規(guī)則) P (P Q) Q (

4、6) 附加規(guī)則附加規(guī)則 P P Q(7) 化簡(jiǎn)規(guī)則化簡(jiǎn)規(guī)則 P Q P (8) 拒取式規(guī)則拒取式規(guī)則 Q (PQ) (9) 假言三段論規(guī)則假言三段論規(guī)則 (PQ) (QR) PR(10) 析取三段論規(guī)則析取三段論規(guī)則 P (P Q) Q構(gòu)造證明法n 直接證明法 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：Bn 附加前提證明法欲證明欲證明 前提：前提：A1, A2, , Ak 結(jié)論：結(jié)論：CB等價(jià)地證明等價(jià)地證明 前提：前提：A1, A2, , Ak, C 結(jié)論：結(jié)論：B 在大城市球賽中，在大城市球賽中，如果如果北京隊(duì)第三北京隊(duì)第三，那么如果，那么如果上海隊(duì)第上海隊(duì)第二二，則，則天津隊(duì)第四

5、天津隊(duì)第四；沈陽隊(duì)不是第一沈陽隊(duì)不是第一或或北京隊(duì)第三北京隊(duì)第三，上海隊(duì)第上海隊(duì)第二二。從而知：如果。從而知：如果沈陽隊(duì)第一沈陽隊(duì)第一，那么，那么天津隊(duì)第四天津隊(duì)第四。 解：設(shè) P：北京隊(duì)第三：北京隊(duì)第三 Q：上海隊(duì)第二：上海隊(duì)第二 R：天津隊(duì)第四：天津隊(duì)第四 S：沈陽隊(duì)第一沈陽隊(duì)第一 前提：前提： P(QR)， SP, Q結(jié)論：結(jié)論： S R寫出對(duì)應(yīng)下面推理的證明 SP 前提前提 S P 置換置換 P(Q R) 前提前提 S(QR) 假言三段論假言三段論 S QR 置換置換 Q 前提前提 SR 析取三段論析取三段論 S R 置換置換2.10 歸結(jié)推理法（反證法）欲證明欲證明 前提：前提：A1

6、, A2, , Ak 結(jié)論：結(jié)論：B將 B 加入前提，若推出矛盾，則得證推理正確.理由理由: A1 A2 Ak B (A1 A2 Ak) B (A1 A2 Ak) ( B) (A1 A2 Ak B)括號(hào)內(nèi)為矛盾式當(dāng)且僅當(dāng)括號(hào)內(nèi)為矛盾式當(dāng)且僅當(dāng) (A1 A2 AkB)為為重言式重言式 .證明AB是重言式的歸結(jié)證明過程n建立子句集Sn將將AB化成合取范式，如化成合取范式，如 P (P R) ( PQ) ( P R) 的形式，進(jìn)而將所有句子構(gòu)成子句集合：的形式，進(jìn)而將所有句子構(gòu)成子句集合： S=P，P R， PR， P Rn對(duì)S作歸結(jié)n對(duì)對(duì)S的子句消去的子句消去互補(bǔ)對(duì)互補(bǔ)對(duì)： 子句：子句：P R，

7、P Q 作歸結(jié)，得作歸結(jié)，得歸結(jié)式：歸結(jié)式：R Q 并將此歸結(jié)式仍放入并將此歸結(jié)式仍放入S中，重復(fù)此過程中，重復(fù)此過程n直至歸結(jié)出矛盾式，證明結(jié)束。前提： (P Q) R, RS, S, P結(jié)論結(jié)論： Q歸結(jié)推理法 舉例證明證明: Q 結(jié)論否定引入 RS 前提引入前提引入 R S 置換置換 S 前提引入前提引入 R 歸結(jié)歸結(jié) (P Q) R 前提引入前提引入 (P Q) 歸結(jié)歸結(jié) PQ 置換置換 P 歸結(jié)歸結(jié) P 前提引入前提引入 歸結(jié)歸結(jié)第4章 謂詞邏輯的基本概念 4.1 謂詞和個(gè)體詞4.2 函數(shù)和謂詞4.3 合式公式4.4 自然語句的形式化4.5 有限域下公式(x)P(x)、(x)P(x)

8、 的表示法4.6 公式的普遍有效性和判定問題引例1n 在命題邏輯中最基本的研究對(duì)象是原子命題n原子命題原子命題是不能再分割的是不能再分割的, ,兩個(gè)原子命題之間沒有任何兩個(gè)原子命題之間沒有任何內(nèi)在的聯(lián)系，如：內(nèi)在的聯(lián)系，如：n前提：前提：“金屬都是導(dǎo)電體。金屬都是導(dǎo)電體?！?p “銅是金屬。銅是金屬?！?q 結(jié)論：結(jié)論： “銅是導(dǎo)電體。銅是導(dǎo)電體?！?rn這是這是“古典三段論古典三段論”，卻不能用命題邏輯正確表現(xiàn)出，卻不能用命題邏輯正確表現(xiàn)出來。來。n這種研究方法顯然不足以刻劃世間萬物的千變?nèi)f化的這種研究方法顯然不足以刻劃世間萬物的千變?nèi)f化的邏輯關(guān)系。邏輯關(guān)系。 p q r引例2謂詞演算謂詞演

9、算(一階謂詞演算）是命題演算的擴(kuò)充和發(fā)展一階謂詞演算是重要的符號(hào)邏輯系統(tǒng)是重要的符號(hào)邏輯系統(tǒng)它是它是程序設(shè)計(jì)理論程序設(shè)計(jì)理論、語義形式化語義形式化及及程序邏輯程序邏輯研究研究的重要基礎(chǔ)，是的重要基礎(chǔ)，是程序驗(yàn)證程序驗(yàn)證、程序分析、程序分析、綜合及自動(dòng)生成綜合及自動(dòng)生成、定理證明定理證明和和知識(shí)表示知識(shí)表示的有的有力工具力工具。4.1 謂詞和個(gè)體詞n在謂詞演算中，將原子命題分解為謂詞和個(gè)體兩部分。 如： 張三張三是是。n個(gè)體個(gè)體n 可以獨(dú)立存在的東西，它可以是一個(gè)具體的事可以獨(dú)立存在的東西，它可以是一個(gè)具體的事物，也可以是一個(gè)抽象的概念。物，也可以是一個(gè)抽象的概念。n謂詞謂詞 用于刻劃個(gè)體的性質(zhì)

10、和個(gè)體之間的關(guān)系用于刻劃個(gè)體的性質(zhì)和個(gè)體之間的關(guān)系 個(gè)體個(gè)體謂詞謂詞個(gè)體n 考察下面的三個(gè)原子命題： 李玲李玲是共青團(tuán)員。是共青團(tuán)員。 張華張華比比李紅李紅高。高。 小高小高坐在坐在小王小王和和小劉小劉的中間。的中間。n 個(gè)體的分類n個(gè)體常項(xiàng)個(gè)體常項(xiàng)：表示具體或特定個(gè)體的標(biāo)識(shí)符表示具體或特定個(gè)體的標(biāo)識(shí)符n 如如 a：李玲，：李玲，b：張華，：張華，c：李紅，：李紅，d：小高，：小高，e：小王，：小王，f：小劉：小劉n個(gè)體變項(xiàng)個(gè)體變項(xiàng)：表示任意個(gè)體或泛指某類個(gè)體的標(biāo)識(shí)符表示任意個(gè)體或泛指某類個(gè)體的標(biāo)識(shí)符n如：偶數(shù)、生物，如：偶數(shù)、生物，用用x, y, z表示表示n 個(gè)體域個(gè)體域D 個(gè)體變項(xiàng)的變化

11、范圍n有限個(gè)體域：有限個(gè)體域：如如a, b, c, 1, 2n無限個(gè)體域：無限個(gè)體域：如如 N, Z, R, n全總個(gè)體域全總個(gè)體域: 宇宙間一切事物組成（宇宙間一切事物組成（默認(rèn)的個(gè)體域默認(rèn)的個(gè)體域）謂詞n 考察下面的三個(gè)原子命題： 李玲李玲是共青團(tuán)員是共青團(tuán)員。 張華張華比比李紅李紅高高。 小高小高坐在坐在小王小王和和小劉小劉的中間的中間。n 謂詞:用于刻劃個(gè)體性質(zhì)或各個(gè)個(gè)體的關(guān)系，常用大寫英文字母表示。 n謂詞常項(xiàng)謂詞常項(xiàng)：n如：如：F: 是人是人，則，則 F(a)：a是人是人n謂詞變項(xiàng)謂詞變項(xiàng)：n如：如：F: 具有性質(zhì)具有性質(zhì)F，則，則F(x)：x具有性質(zhì)具有性質(zhì)Fn如：可用如：可用F

12、，G，H表示上面三個(gè)命題中謂詞：表示上面三個(gè)命題中謂詞： F：是共青團(tuán)員。是共青團(tuán)員。 G：比比高。高。 H：坐在坐在和和的中間的中間。 謂詞n 考察下面的三個(gè)原子命題： 李玲李玲是共青團(tuán)員是共青團(tuán)員。 張華張華比比李紅李紅高高。 小高小高坐在坐在小王小王和和小劉小劉的中間的中間。n 如：可用F，G，H表示上面三個(gè)命題中謂詞： F：是共青團(tuán)員。是共青團(tuán)員。 G：比比高。高。 H：坐在坐在和和的中間的中間。n 謂詞的分類 n 一元謂詞一元謂詞: 刻劃一個(gè)個(gè)體的性質(zhì)，如謂詞刻劃一個(gè)個(gè)體的性質(zhì)，如謂詞F(x)n 多元謂詞多元謂詞: 刻劃兩個(gè)或以上個(gè)體間的關(guān)系，刻劃兩個(gè)或以上個(gè)體間的關(guān)系，n 如如 L

13、(x,y)：x與與y有關(guān)系有關(guān)系L，L(x,y)：x y，n如謂詞如謂詞G(x,y)、H(x,y,z)n0元謂詞元謂詞: 不含個(gè)體變項(xiàng)的謂詞不含個(gè)體變項(xiàng)的謂詞, 即命題常項(xiàng)或命題即命題常項(xiàng)或命題變項(xiàng)變項(xiàng) F(a)G(b,c)H(d,e,f )a：李玲，：李玲，b：張華，：張華，c：李紅，：李紅，d：小高，：小高，e：小王，：小王，f： 小劉小劉n函數(shù)n它是某個(gè)體域到另一個(gè)體域的映射，由一個(gè)謂詞它是某個(gè)體域到另一個(gè)體域的映射，由一個(gè)謂詞字母和字母和n個(gè)個(gè)體變項(xiàng)組成的表達(dá)式：個(gè)個(gè)體變項(xiàng)組成的表達(dá)式：F(x, y, , z)n注意：n F(x, y, , z)不是命題，它的真值無法確定，要不是命題，

14、它的真值無法確定，要想使它成為命題，必須指定某一謂詞常項(xiàng)代替想使它成為命題，必須指定某一謂詞常項(xiàng)代替F，同時(shí)還要用同時(shí)還要用n個(gè)個(gè)體常項(xiàng)代替?zhèn)€個(gè)體常項(xiàng)代替n個(gè)個(gè)體變項(xiàng)。個(gè)個(gè)體變項(xiàng)。n 如：如：L(x, y) 是一個(gè)二元謂詞，它不是命題。是一個(gè)二元謂詞，它不是命題。n當(dāng)令當(dāng)令L表示表示“小于小于”之后，之后，L(x, y) 還不是命題。還不是命題。n當(dāng)令當(dāng)令a=2，b=3時(shí)，時(shí)， L(a, b) 才是命題，并且是真命題。才是命題，并且是真命題。n當(dāng)令當(dāng)令c=2，d=1時(shí)，時(shí)， L(c, d) 為假命題。為假命題。4.2 函數(shù)和量詞 將下列命題用謂詞符號(hào)化 (1) 如果23，則33，q：3y， G

15、(x,y)：xy,n命題符號(hào)化為命題符號(hào)化為 F(2,3) G(3,4)(2) 2是素?cái)?shù)且是偶數(shù)。n在命題邏輯中在命題邏輯中, 設(shè)設(shè) p: 2是素?cái)?shù)是素?cái)?shù), q: 2是偶數(shù)是偶數(shù) n命題符號(hào)化為：命題符號(hào)化為： p q, 這是真命題這是真命題n在一階邏輯中在一階邏輯中, 設(shè)設(shè)F(x)：x是素?cái)?shù)。是素?cái)?shù)。 G(x)：x是偶數(shù)。是偶數(shù)。 a：2，n命題命題符號(hào)化為：符號(hào)化為： F(a) G(a) 將下列命題用謂詞符號(hào)化(3)如果張明比李民高，李民比趙亮高，則張明比趙亮高。 解：在命題邏輯中， 設(shè)：p：張明比李民高，q：李民：李民比趙亮高 r：張明比趙亮高 則命題符號(hào)為則命題符號(hào)為： p q r在一

16、階邏輯中， 設(shè) H(x, y)：x比y高。 a：張明； b：李民；c：趙亮， 則命題符號(hào)化為：則命題符號(hào)化為： H(a, b) H(b, c) H(a, c)4.2.2 量詞n引入量詞表示個(gè)體域中所有個(gè)體或部分個(gè)體具有某種性質(zhì)。n全稱量詞全稱量詞 : 表示任意的表示任意的, 所有的所有的, 一切的等一切的等n如如: x 表示對(duì)個(gè)體域中所有的表示對(duì)個(gè)體域中所有的x xF(x) 表示個(gè)體域里的所有個(gè)體都有性質(zhì)表示個(gè)體域里的所有個(gè)體都有性質(zhì)Fn存在量詞存在量詞 : 表示存在表示存在, 有的有的, 至少有一個(gè)等至少有一個(gè)等n如如: x 表示在個(gè)體域中存在表示在個(gè)體域中存在x xF(x)表示存在著個(gè)體域中的個(gè)體具有性質(zhì)表示存在著個(gè)體域中的個(gè)體具有性質(zhì)F第一種情況考慮個(gè)體域D為人類集合。(1) 符號(hào)化為：符號(hào)化為： xF(x) ， 其中其中F(x) ：x。這個(gè)命題是真命題。這個(gè)命題是真命題。 (2) 符號(hào)化為符號(hào)化為 xF(x)， 其中其中F(x) ：x。這個(gè)命題也是真命題。這個(gè)命題也是真命題。在一階邏輯中將下面命題符號(hào)化第二種情況，考慮個(gè)體域D為全總個(gè)體域。引出一個(gè)新的謂詞，將人分離出來引出一個(gè)新的謂詞，將人分離出來: : M(x)：x是人。是人