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

2、，高， Q：他很胖：他很胖P ( P Q) (7)如果水是清的，那么或者張三能見到池底或者他是個近視眼。n設設P：水是清的，：水是清的， Q：張三能見到池底，：張三能見到池底， R：張三是個近視眼：張三是個近視眼 P ( (QR)(Q R) P ( (Q R)不可兼或不可兼或P ( P Q) P37: 2n 分別由真值表的T和F來列到A、B、C的表達式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 命題公式與真值表的關系2.4 聯結詞的完備集2.5 對偶式2.6 范式2.7 推理形式2.8 基本的推理公式2.9 推理演算2.10 歸結推理法討論討論等值演算等值演算討論討論推理演算推理演算常用基本推理規則 (1) 前提引入規則前提引入規則(2) 結論引入規則結論引入規則(3) 代入規則代入規則(4) 置換規則置換規則(5)假言推理假言推理(分離規則分離規則) P (P Q) Q (

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

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

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

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

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

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

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

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

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

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

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

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

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