数理逻辑08.ppt

《数理逻辑08.ppt》由会员分享，可在线阅读，更多相关《数理逻辑08.ppt（96页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数理逻辑数理逻辑 n数理逻辑：用数学的方法研究逻辑问题。数理逻辑：用数学的方法研究逻辑问题。n逻辑演算：命题逻辑演算、谓词逻辑演算。逻辑演算：命题逻辑演算、谓词逻辑演算。n公理集合论公理集合论n证明论证明论n模型论模型论n递归论递归论 1.1 1.1 命题命题 n命题：可以区分真假的陈述句。命题：可以区分真假的陈述句。n今天是星期一。今天是星期一。n南京是江苏的省会。南京是江苏的省会。n今天天气真好啊！今天天气真好啊！n禁止抽烟！禁止抽烟！n你有笔吗？你有笔吗？1.2 1.2 联结词与真值表联结词与真值表 n原子命题：不能再分解的命题。原子命题：不能再分解的命题。n今天是星期一。今天是星期一。

2、n南京是江苏的省会。南京是江苏的省会。n他在跑步或打球。他在跑步或打球。1.2 1.2 联结词与真值表联结词与真值表 n否定否定(非）：非）：含义：不含义：不n如果如果p p表示表示“今天是星期一今天是星期一”，则则p p表示表示“今天不是星期一今天不是星期一”。pp01101.2 1.2 联结词与真值表联结词与真值表 n合取词：合取词：含义：并且含义：并且 n如果如果p p表示表示“今天是星期一今天是星期一”，q q表示表示“今天是晴天今天是晴天”，则则pqpq表表示示“今今天天是是星星期期一一并并且且今今天天是是晴晴天天”。pqpq0000101001111.2 1.2 联结词与真值表联结

3、词与真值表 n析取词：析取词：含义：或者含义：或者 n如如果果p p表表示示“小小王王在在跑跑步步”，q q表表示示“小小李李在在打打球球”，则则pqpq表表示示“小小王王在在跑跑步步或或者者小小李李在打球在打球”。pqpq0000111011111.2 1.2 联结词与真值表联结词与真值表 n不不可可兼兼或或:小小王王现现在在在在操操场场或或者者教教室室，用用r r表表示示。p p表表示示“小小王王在在操操场场”，q q表表示示“小小王王在在教室教室”np pq q并没有完全刻划上述命并没有完全刻划上述命题题,r r应该为应该为：(p pq)q)(p(pq)q)pqr000011101110

4、1.2 1.2 联结词与真值表联结词与真值表 n蕴含词：蕴含词：含义：如果含义：如果.那么那么.n如如果果p p表表示示“我我有有空空”，q q表表示示“我我去去图图书书馆馆”，则则p pq q表表示示“如如果果我我有有空空,那那么么我我就就去去图图书馆书馆”。pqpq0010111001111.2 1.2 联结词与真值表联结词与真值表 n蕴含怪论：蕴含怪论：n如果今天是星期一，那么南航位于北京。如果今天是星期一，那么南航位于北京。pqpq0010111001111.2 1.2 联结词与真值表联结词与真值表 n等值词等值词：含义：当且仅当，同真假，同或含义：当且仅当，同真假，同或 n如如果果p

5、 p表表示示“今今天天天天气气好好”，q q表表示示“小小李李上上街街去去”，则则p pq q表表示示“当当且且仅仅当当今今天天天天气气好好，小李上街去小李上街去”。pqpq0010101001111.2 1.2 联结词与真值表联结词与真值表 n联结词的优先顺序：联结词的优先顺序：、n用命题符号及联结词来表示下列命题：用命题符号及联结词来表示下列命题：p p：今天下雨。今天下雨。q q：我进城去。我进城去。r r：我有时间。我有时间。n如如果果今今天天不不下下雨雨，并并且且我我有有时时间间，我我就就进城去。进城去。n如果今天下雨，我就不进城去。如果今天下雨，我就不进城去。n只有当今天不下雨，我

6、才进城去。只有当今天不下雨，我才进城去。1.2 1.2 联结词与真值表联结词与真值表 n解解释释：对对命命题题逻逻辑辑公公式式中中的的每每个个命命题题符符号号指指定真假值，称之为该公式的一个解释。定真假值，称之为该公式的一个解释。pqpq1001111.2 1.2 联结词与真值表联结词与真值表 n永永真真式式：如如果果一一个个公公式式在在所所有有解解释释下下取取值值都都为真，称之为永真式。为真，称之为永真式。n永永假假式式：如如果果一一个个公公式式在在所所有有解解释释下下取取值值都都为假，称之为永假式。为假，称之为永假式。pppp011101pppp0101001.2 1.2 联结词与真值表联

7、结词与真值表 n同同真真假假式式：如如果果两两个个公公式式在在所所有有解解释释下下的的真真假值都相同，称这两个公式是同真假式。假值都相同，称这两个公式是同真假式。pqpq001011100111pqpq0010111001111.2 1.2 联结词与真值表联结词与真值表 n一些同真假式一些同真假式n交换律：交换律：p pq q 与与 q qp pn结合律：结合律：p p(q qr)r)与与 (p pq)q)r rn德摩根律：德摩根律：(q qr)r)与与 q qr rn吸收律：吸收律：p p(p pq)q)与与 p pn逆否律：逆否律：p pq q 与与 q qp pnp pq q 与与p p

8、q qnp pq q 与与(p pq)q)(q qp)p)n(p pq)q)与与 p pq q命题逻辑自然推理系统命题逻辑自然推理系统P PN N nP PN N中的符号：中的符号：n命题变元：命题变元：p,q,r,pp,q,r,pi i,q qi i,r ri in联结词：联结词：、n辅助符号：辅助符号：(，)命题逻辑自然推理系统命题逻辑自然推理系统P PN N nP PN N中的合式公式：中的合式公式：n单个命题变元是单个命题变元是合式公式合式公式n如如果果A,BA,B是是合合式式公公式式，则则A,(AA,(AB),B),(A(AB),(AB),(AB),(AB),(AB)B)也是合式公式

9、。也是合式公式。n只只有有通通过过在在有有限限步步内内得得到到的的符符号号串串才是合式公式。才是合式公式。n可以按优先级可以按优先级、省略括号省略括号n判断下列符号串是否为合式公式判断下列符号串是否为合式公式p pq,q,pqpq,p,pq,pq,pq,q,ppq q 命题逻辑自然推理系统命题逻辑自然推理系统P PN N n一些约定：一些约定：nA A，B B，A Ai i，B Bi i表示合式公式。表示合式公式。n，i i，i i 表示合式公式的集合。表示合式公式的集合。n A A 表表示示可可以以变变形形为为A A。(或或者者说说可可以推出以推出A A。)n A A，B B 表示表示 A

10、A并且并且 B B。n A A 表示表示 A An A A表示表示 并且并且 AA注注：以以上上各各符符号号不不在在P PN N中中，是是元元语语言言，而而不不是对象语言。是对象语言。命题逻辑自然推理系统命题逻辑自然推理系统P PN N n系统系统P PN N的推理规则：的推理规则：1.1.A A1 1，A A2 2 .A .An n A Ai i(i=1,2,.,n)(i=1,2,.,n)()2.2.如果如果()且且 A A，则则AA()()(传递律传递律)3.3.如果如果A A，则则,A A (0 0)(单调律单调律)4.4.如果如果,AB,B,AB,B，则则A A()()(反证律反证律)

11、5.5.A AB B，ABAB(-)-)6.6.如果如果,AB,AB，则则AAB B(+)+)注意区分符号注意区分符号、和和(书上用）。书上用）。命题逻辑自然推理系统命题逻辑自然推理系统P PN N 7.ABA7.ABA，B B （-）8.8.A A，BABBAB（+）9.9.如果如果ACAC且且BCBC，则则ABC ABC （-）10.10.AABAAB，BA BA （+）11.11.A AB B，ABAB 以及以及 A AB,BA B,BA （-）12.12.如果如果,AB,AB且且,BA,BA，则则 AAB B（+）命题逻辑自然推理系统命题逻辑自然推理系统P PN N n系统系统P PN

12、 N的证明：的证明：AA的一个证明指下述的序列的一个证明指下述的序列1 1AA1 1，2 2AA2 2，.n nAAn n，其中其中nn nAAn n就是就是AAni iAAi i是是由由前前面面的的推推理理形形式式及及推推理理规规则则得得到。到。P PN N系统的展开系统的展开 pf:1.pf:1.AAAA()nTh2:Th2:A BA BA A（肯定后件律）肯定后件律）pf:pf:1.1.A,B AA,B A()2.2.A BA BA A(1,(1,+)+)nTh1:Th1:AAAAP PN N系统的展开系统的展开 1.1.A AB B，B BC,C,A AA AB B2.2.A AB B

13、，B BC,C,A AA A3.3.A AB,B,A BA B4.4.A AB B，B BC,C,A BA B5.5.A AB B，B BC,C,A BA BC C6.6.B BC,C,B B C C7.7.A AB B，B BC,C,A A C C8.8.A AB B，B BC AC AC C pf:pf:()()(-)-)(1,2,3,(1,2,3,)()(-)-)(4,5,6,(4,5,6,)(7,(7,+)+)nTh3:Th3:A AB B，B BC AC AC C （传递传递律）律）P PN N系统的展开系统的展开 1.1.A,A,B AA,A,B A2.2.A,A,B AA,A,B

14、 A3.3.A,A,B A,A,B A,AA,A4.4.A,A BA,A Bpf:pf:()()(合并合并)(3,(3,)nTh4:Th4:作业作业 nTh6:Th6:作业作业 nTh7:Th7:作业作业nTh5:Th5:A A，A BA B （矛盾推出一切）矛盾推出一切）P PN N系统的展开系统的展开 1.1.A,A,A A A,A,A A2.2.A AA A:()(1(1,)1.1.A A,A,A AA2.2.A AA A3.3.A A,A,A A A4.4.A A,A,A A A5.5.AA A A:()(1(1,Th8,Th8)(1,2,(1,2,)()(3,4,(3,4,)nTh8

15、:Th8:AAAA （传递传递律）律）P PN N系统的展开系统的展开 1.1.,A A,A A2.2.A AA A3.3.,A A,A A4.4.,A,A 5.5.,A B,B,A B,B6.6.,A B,B,A B,B7.7.A Apf:pf:()(-)(1,2,(1,2,)()(已知已知)(3,4,5,(3,4,5,)(6,(6,)nTh9:Th9:如果如果,AB,B,AB,B,则则 A(+,A(+,归缪归缪律律)P PN N系统的展开系统的展开 1.1.A1 A1 2.2.A2.A23.3.A3.A34.4.B1B15.5.B2B26.6.B3B37.7.B4B48.8.B5B5 (已

16、知或假设已知或假设)(已知或假设已知或假设)(已知或假设已知或假设)A1,A2,A3 A1,A2,A3 B1B1A1,A2,A3 A1,A2,A3 B2B2A1,A2 A1,A2 B3B3A1,A2 A1,A2 B4B4A1 A1 B5B5n斜形证明：斜形证明：P PN N系统的展开系统的展开 nTh2:Th2:A BA BA A（肯定后件律）肯定后件律）n斜形证明：斜形证明：1.1.A (A (已知已知)2.2.A A()1.1.A (A (已知已知)2.2.B B(H)H)假设假设3.3.A A ()4.4.B BA (2,3,A (2,3,+)+)nTh1:Th1:AAAAP PN N系

17、统的展开系统的展开 1.1.A AB B (已知已知)2.2.B BC (C (已知已知)3.3.A (H).A (H)4.4.A .AB B()5.5.B .B (3,4,(3,4,-)-)6.6.B .BC C()7.7.C .C (5,6,(5,6,-)-)8.8.A AC C (3,7,(3,7,+)+)A AB,BB,BC,A AC,A AB BA AB,BB,BC,A BC,A BA AB,BB,BC,A BC,A BC CA AB,BB,BC,A C,A C CA AB,BB,BC AC AC CnTh3:Th3:A AB B，B BC AC AC C （传递传递律）律）P PN

18、 N系统的展开系统的展开 1.1.(已知已知)2.2.A.A(H)(H)3.3.4.4.5.5.6.6.B B7.7.A AB B (2,6,(2,6,+)+),A B,A B A AB(B(+)+)n斜形证明：斜形证明：+P PN N系统的展开系统的展开 1.1.A A（B BC C）(已知已知)2.2.A AB (B (已知已知)3.3.A .A (H)H)4.4.B BC(1,3,C(1,3,-)-)5.5.B B (2,3,(2,3,-)-)6.6.C C (4,5,(4,5,-)-)7.7.A AC C (3,6,(3,6,+)+)A A(B(BC),ABC),ABC CA,AA,A

19、B BB BB,BB,BC CC CA A(B(BC),AC),AB,ABB,ABC CA A(B(BC),AC),AB,ABB,ABA A(B(BC),AC),AB,ACB,ACA A(B(BC),AC),AB AB AC CnTh4:Th4:A A（B BC C），），A ABABAC C P PN N系统的展开系统的展开 1.1.A (A (已知已知)2.2.A (A (已知已知)3.3.B .B(H)H)假设假设4.4.A .A()5.5.A A ()6.6.B B (3,4,5,(3,4,5,)A,A,B AA,A,B AA,A,B AA,A,B AA,A BA,A BnTh5:Th

20、5:A A，A BA B （矛盾推出一切）矛盾推出一切）P PN N系统的展开系统的展开 1.1.A (A (已知已知)2.2.A .A (已知已知)3.3.B.B (Th5)Th5)4.4.A AB B (3,6,(3,6,+)+)A,A B (A,A B (Th5)Th5)A AA AB(1,B(1,+)+)nTh6:Th6:A AA AB B P PN N系统的展开系统的展开 1.1.A (A (已知已知)2.2.A (.A (已知已知)3.3.B.B (Th5)Th5)4.4.AAB B (3,6,(3,6,+)+)A,A B (A,A B (Th5)Th5)A AA AB (1,B

21、(1,+)+)nTh7:Th7:A AA AB B P PN N系统的展开系统的展开 1.1.(已知已知)2.2.AA(H)(H)3.3.4.4.B .B 5.5.6.6.B.B7.7.A (2,4,6,A (2,4,6,),A A B B,A A B B A(A()n斜形证明：斜形证明：P PN N系统的展开系统的展开 nTh8:Th8:AAAA （传递传递律）律）:1.1.A (A (已知已知)2.2.A (A (H)H)3.3.A (A ()4.4.A (1,2,3,A (1,2,3,)1.1.A (A (已知已知)2.2.A (A (H)H)3.3.A (2,Th8,A (2,Th8,

22、)4.4.A A ()5.5.AA (2,3,4,(2,3,4,)P PN N系统的展开系统的展开 nTh10:Th10:A AB B，B AB A 1.1.A AB (B (已知已知)2.2.B (.B (已知已知)3.3.A.A (H)H)4.4.B.B (1,3,1,3,-)-)5.5.A .A (2,3,4,(2,3,4,+)+)P PN N系统的展开系统的展开 nTh11:Th11:A AB BB BAA 1.1.A AB (B (已知已知)2.2.B (.B (H)H)3.3.A .A (1,2,TH10 (1,2,TH10)4.4.BBA (A (2,3,2,3,+)+)1.1.

23、A AB (B (已知已知)2.2.B (H).B (H)3.3.A.A (H)H)4.4.B.B (1,3,(1,3,-)-)5.5.A (2,3,4,+).A (2,3,4,+)6.6.BBA (A (2,5,2,5,+)+)P PN N系统的展开系统的展开 nTh12:Th12:AABB，BABA 1.1.AAB (B (已知已知)2.2.B (.B (已知已知)3.3.A.A (H)H)4.4.B.B(1,3,1,3,-)-)5.5.A .A (2,3,4,(2,3,4,)P PN N系统的展开系统的展开 nTh13:Th13:AAB BB BA A 1.1.AAB (B (已知已知)

24、2.2.B (.B (H)H)3.3.A .A (1,2,TH12 (1,2,TH12)A)ABB，BABA4.4.B BA (A (2,3,2,3,+)+)P PN N系统的展开系统的展开 nTh14:Th14:A ABB，B AB A 1.1.A AB (B (已知已知)2.2.B (.B (已知已知)3.3.A.A (H)H)4.4.B.B (1,3,1,3,-)-)5.5.A .A (2,3,4,(2,3,4,+)+)P PN N系统的展开系统的展开 nTh15:Th15:A AB BB BAA 1.1.A AB (B (已知已知)2.2.B (.B (H)H)3.3.A .A (1,

25、2,TH14 (1,2,TH14)4.4.B BA (A (2,3,2,3,+)+)P PN N系统的展开系统的展开 nTh16:Th16:AAB B，B AB A 1.1.AAB (B (已知已知)2.2.B (.B (已知已知)3.3.A.A (H)H)4.4.B.B (1,3,1,3,-)-)5.5.A .A (2,3,4,(2,3,4,)P PN N系统的展开系统的展开 nTh17:Th17:AAB BB BA A 1.1.AAB (B (已知已知)2.2.B (.B (H)H)3.3.A .A (1,2,TH16 (1,2,TH16)4.4.BBA (A (2,3,2,3,+)+)P

26、 PN N系统的展开系统的展开 nTh18:Th18:AAA AA A 1.1.AAA (A (已知已知)2.2.A (.A (H)H)3.3.A .A (1,2,(1,2,-)4.4.A (A (2,3,2,3,)P PN N系统的展开系统的展开 nTh19:Th19:A AA AA A 1.1.A AA (A (已知已知)2.2.A (.A (H)H)3.3.A .A (1,2,(1,2,-)4.4.A (A (2,3,2,3,+)+)P PN N系统的展开系统的展开 nTh20:Th20:A AB B，A AB AB A 1.1.A AB (B (已知已知)2.2.A.AB (B (已知

27、已知)3.3.A.A (H)(H)4.4.B.B (1,3,1,3,-)5.5.B.B (2,3,2,3,-)6.6.A A (3,4,5,(3,4,5,+)+)P PN N系统的展开系统的展开 nTh21:Th21:A AB B，AAB BB B 1.1.A AB (B (已知已知)2.2.A.AB (B (已知已知)3.3.B.B (H)(H)4.4.A.A (1,3,1,3,Th10)Th10)5.5.A.A (2,3,2,3,Th16)Th16)6.6.B B (3,4,5,(3,4,5,)P PN N系统的展开系统的展开 nTh22:Th22:(A(AB)A,BB)A,B 1.1.(

28、A(AB)(B)(已知已知)2.2.A (.A (H)H)3.3.A.AB B (否定前件律否定前件律)4.4.A A (1,2,3,1,2,3,)1.1.(A(AB)(B)(已知已知)2.2.B (.B (H)H)3.3.A.AB B (肯定后件律肯定后件律)4.4.BB (1,2,3,1,2,3,)P PN N系统的展开系统的展开 nTh23:Th23:n如如果果，ACAC且且，BCBC，则则，ABCABC(-)(-)如果如果ACAC且且BCBC，则则ABC ABC （-）P PN N系统的展开系统的展开 nTh24:Th24:ABBAABBA 1.1.AB (AB (已知已知)2.2.A

29、 (1,A (1,-)-)3.3.B B (1,1,-)4.4.BABA (2,3,2,3,+)1.1.BA (BA (已知已知)2.2.A (1,A (1,-)-)3.3.B B (1,1,-)4.4.ABAB (2,3,2,3,+)P PN N系统的展开系统的展开 nTh24:Th24:(AB)CA(BC)(AB)CA(BC)1.1.(AB)C(AB)C(已知已知)2.2.AB (1,AB (1,-)-)3.3.C (1,C (1,-)-)4.4.B B (2,2,-)5.5.A A (2,2,-)6.6.BCBC (4,3,4,3,+)7.7.A(BC)A(BC)(5,6,5,6,+)P

30、 PN N系统的展开系统的展开 nTh24:Th24:AB(AAB(AB)B)1.1.AB (AB (已知已知)2.2.A,B (1,A,B (1,-)-)3.3.A.AB (HB (H)4.4.B B (1,3,1,3,-)5.5.(A(AB)B)(4,2,3,4,2,3,+)1.1.(A(AB)(B)(已知已知)2.2.A (1,TH22)A (1,TH22)3.3.B (1,TH22)B (1,TH22)4.4.B (-)B (-)5.5.AB (2,4,AB (2,4,+)+)nP PN N的可靠性：的可靠性：n如果如果A A，则则A A是永真式。是永真式。nP PN N的完备性：的完

31、备性：n如果如果A A是永真式是永真式，则则A A。命题逻辑的命题逻辑的可靠性与完备性可靠性与完备性 命题逻辑的命题逻辑的可靠性与完备性可靠性与完备性 n证明证明P PN N中的公式中的公式A A是永真式是永真式：1 1 证明证明A A。（。（可用斜形证明）可用斜形证明）2 2 用真值表验证。用真值表验证。n证明证明P PN N中的公式中的公式A A不是永真式不是永真式：用真值表验证用真值表验证。第三章第三章 谓词与量词谓词与量词 n命题逻辑的局限性：命题逻辑的局限性：n所有的整数都是有理数。所有的整数都是有理数。p pn2 2是整数。是整数。q qn2 2是有理数。是有理数。r rn在命题逻

32、辑中，分别用在命题逻辑中，分别用p,q,rp,q,r来表示上述命题。来表示上述命题。n一方面，我们希望有一方面，我们希望有p,q rp,q rn另一方面，在另一方面，在P PN N中中p,q rp,q r不成立。不成立。第三章第三章 谓词与量词谓词与量词 n命题的分解：命题的分解：n所有的整数都是有理数。所有的整数都是有理数。n x(P(x)x(P(x)Q(x)Q(x)第三章第三章 谓词与量词谓词与量词 n命题的分解：命题的分解：n所有的整数都是有理数。所有的整数都是有理数。x(P(x)x(P(x)Q(x)Q(x)n2 2是整数。是整数。P(2)P(2)n2 2是有理数。是有理数。Q(2)Q(

33、2)n在谓词逻辑推理系统中有在谓词逻辑推理系统中有n x(P(x)x(P(x)Q(x)Q(x)，P(2)Q(2)P(2)Q(2)第三章第三章 谓词与量词谓词与量词 n谓词谓词：表示个体的性质或个体之间的关系。：表示个体的性质或个体之间的关系。n一元谓词：一元谓词：P(x):P(x):可以表示可以表示x x是整数。是整数。n二元谓词：二元谓词：P(x,y):P(x,y):可以表示可以表示xyxy。n三元谓词：三元谓词：P(x,y,z):P(x,y,z):可以表示可以表示xyzxyz。第三章第三章 谓词与量词谓词与量词 n量词量词：n：所有，每一。所有，每一。(All,Any)All,Any)n：

34、存在。存在。(Exist)Exist)n量词的辖域：量词所管辖的公式。量词的辖域：量词所管辖的公式。x(P(x,y)x(P(x,y)yQyQ(x,y)(x,y)x x yQyQ(x,y)(x,y)x(x(P(x,y)P(x,y)yQyQ(x,y)(x,y)x x yQyQ(x,y)(x,y)x(P(x,y)x(P(x,y)y yQ Q(x,y)(x,y)x x yQyQ(x,y)(x,y)x(P(x,y)x(P(x,y)yQyQ(x,y)(x,y)x x yQyQ(x,y)(x,y)x(P(x,y)x(P(x,y)yQyQ(x,y)(x,y)x x y yQ Q(x,y)(x,y)第三章第三章

35、 谓词与量词谓词与量词 n约束变元与自由变元：约束变元与自由变元：如如果果x x出出现现在在 x x或或 x x的的辖辖域域中中，则则称称该该x x是是约约束束出现出现，否则称，否则称该该x x为为自由出现自由出现。xPxP(x,y)(x,y)yQyQ(x,y)(x,y)x x yRyR(x,y)(x,y)自由出现约束出现第三章第三章 谓词与量词谓词与量词 n个体常元个体常元：表示固定的个体。：表示固定的个体。na a：表示小王。表示小王。nP(x):xP(x):x是教师。是教师。nP(a):P(a):小王是教师。小王是教师。n函数符号函数符号：表示个体域上的：表示个体域上的n n元函数。元函

36、数。P(x):xP(x):x是教师。是教师。f(x):xf(x):x的父亲。的父亲。P(f(x):xP(f(x):x的父亲是教师。的父亲是教师。第三章第三章 谓词与量词谓词与量词 n用符号来表示下述命题：用符号来表示下述命题：P(x):xP(x):x是素数。是素数。Q(x):xQ(x):x是偶数。是偶数。R(x,y):xyR(x,y):xy。E(x,y):x=yE(x,y):x=y。1.1.有的数既是素数又是偶数。有的数既是素数又是偶数。2.2.任何大于任何大于2 2的素数都不是偶数。的素数都不是偶数。3.3.无论无论x x是多大的素数，还有比是多大的素数，还有比x x更大的素数。更大的素数。

37、4.4.没有比没有比2 2大的偶数是素数。大的偶数是素数。5.5.没有最大的素数。没有最大的素数。6.6.有且只有一个偶数是素数。有且只有一个偶数是素数。第三章第三章 谓词与量词谓词与量词 n命题分解后引进的符号：命题分解后引进的符号：n个体常元个体常元n个体变元（包含约束出现的和自由出现的）个体变元（包含约束出现的和自由出现的）n函数符号函数符号n谓词符号谓词符号n量词量词第三章第三章 谓词与量词谓词与量词 n谓词逻辑公式的解释（模型）：谓词逻辑公式的解释（模型）：n指定一个集合作为论域。指定一个集合作为论域。n将每个常元指定为论域中的一个元素。将每个常元指定为论域中的一个元素。n将将n n

38、元函数符号指定为论域上的元函数符号指定为论域上的n n元函数。元函数。n将将n n元谓词符号指定为论域上的元谓词符号指定为论域上的n n元关系。元关系。n将将自自由由出出现现的的变变元元指指定定为为论论域域中中的的一一个个元元素。素。第三章第三章 谓词与量词谓词与量词n谓词逻辑公式的解释谓词逻辑公式的解释：n xP(x)xP(x)n论域：论域：1,2,3,4,P(x):x0n x(P(x)x(P(x)Q(x)Q(x)n论域：论域：1,2,3,4,P(x):x是整数，是整数，Q(x)：x是有理数是有理数第三章第三章 谓词与量词谓词与量词n谓词逻辑公式的真假值谓词逻辑公式的真假值对于有限论域对于有

39、限论域U U=a a1 1.a.an n x xB B(x)x)为真为真 iff B(aiff B(a1 1)为真为真且且B B(a(a2 2)为真为真.B(aB(an n)为真为真iff iff B(aB(a1 1)B(aB(a2 2).B(aB(an n)为真为真 x xB B(x)x)为真为真 iff B(aiff B(a1 1)为真为真或或B(aB(a2 2)为真为真.B(aB(an n)为真为真iff iff B(aB(a1 1)B(aB(a2 2).B(aB(an n)为真为真第三章第三章 谓词与量词谓词与量词n谓词逻辑公式的真假值谓词逻辑公式的真假值：n xP(x)xP(x)n论

40、域：论域：1,2,3,4,P(x):x0n x(P(x)x(P(x)Q(x)Q(x)n论域：论域：1,2,3,4,P(x):x是整数，是整数，Q(x)：x是有理数是有理数第三章第三章 谓词与量词谓词与量词 n永永真真式式：如如果果一一个个公公式式在在所所有有解解释释下下取取值值都都为真，称之为永真式。为真，称之为永真式。n x(R(x)x(R(x)R(x)R(x)n永永假假式式：如如果果一一个个公公式式在在所所有有解解释释下下取取值值都都为假，称之为永假式。为假，称之为永假式。n x(R(x)x(R(x)R(x)R(x)第三章第三章 谓词与量词谓词与量词 n同同真真假假式式：如如果果两两个个公

41、公式式在在所所有有解解释释下下的的真真假值都相同，称这两个公式是同真假式。假值都相同，称这两个公式是同真假式。n一些同真假式一些同真假式n xAxA(x)(x)与与 xA(x)xA(x)n xAxA(x)(x)与与 xA(x)xA(x)n xAxA(x)(x)xBxB(x)(x)与与 x(A(x)B(x)x(A(x)B(x)n xAxA(x)(x)xBxB(x)(x)与与 x(A(x)B(x)x(A(x)B(x)4.1 4.1 谓词逻辑自然推理系统谓词逻辑自然推理系统F FN N nF FN N中的符号：中的符号：n个体词：个体词：a,b,c,a,b,c,a ai i,b,bi i,c ci

42、in谓词：谓词：F,G,H,F,G,H,F Fi i,G Gi i,H,Hi in约束变元：约束变元：x,y,z,x,y,z,x xi i,y yi i,z zi in量词：量词：，n联结词：联结词：、n辅助符号：辅助符号：(，)4.1 4.1 谓词逻辑自然推理系统谓词逻辑自然推理系统F FN N nF FN N中的合式公式：中的合式公式：n如如果果A A是是n n元元谓谓词词符符号号，a a1 1,a,a2 2.a.an n是是个个体体词词，则则A A(a(a1 1,a,a2 2.a.an n)是是合式公式合式公式n如如果果A,BA,B是是合合式式公公式式，则则(A),(AA),(AB),B

43、),(A(AB),(AB),(AB),(AB),(AB)B)也是合式公式。也是合式公式。nA(a)A(a)是是合合式式公公式式，a a在在其其中中出出现现，x x不不在在其其中中出现，则出现，则 xAxA(x)(x)与与 xAxA(x)(x)是合式公式是合式公式只有通过只有通过在有限步内得到的才是合式公式。在有限步内得到的才是合式公式。n判断下列符号串是否为合式公式判断下列符号串是否为合式公式 P(x),P(x),xxQ(x),Q(x),xFxF(x,a)(x,a)4.1 4.1 谓词逻辑自然推理系统谓词逻辑自然推理系统F FN N n系统系统F FN N的推理规则：的推理规则：1.1.A A

44、1 1，A A2 2 .A .An n A Ai i(i=1,2,.,n)(i=1,2,.,n)()2.2.如果如果()且且 A A，则则AA()()(传递律传递律)3.3.如果如果A A，则则,A A (0 0)(单调律单调律)4.4.如果如果,AB,B,AB,B，则则A A()()(反证律反证律)5.5.A AB B，ABAB(-)-)6.6.如果如果,AB,AB，则则AAB B(+)+)4.1 4.1 谓词逻辑自然推理系统谓词逻辑自然推理系统F FN N n系统系统F FN N的推理规则：的推理规则：7.7.ABAABA，B B （-）8.8.A A，BABBAB（+）9.9.如果如果A

45、CAC且且BCBC，则则ABC ABC （-）10.10.AABAAB，BA BA （+）11.11.A AB B，ABAB 以及以及 A AB,BA B,BA （-）12.12.如果如果,AB,AB且且,BA,BA，则则 AAB B（+）4.1 4.1 谓词逻辑自然推理系统谓词逻辑自然推理系统F FN N n系统系统F FN N的推理规则：的推理规则：13 13 xAxA(x)A(a)(x)A(a)（-）（）（消去律）消去律）14 14 如果如果A(a)A(a)且且a a不在不在中出现，则中出现，则 xAxA(x)(x)（+）（引入律）引入律）1515 ,A(a)B,A(a)B 且且a a不

46、在不在和和B B中出现，则中出现，则,xAxA(x)B (x)B （-）（消去消去律）律）16 16 A(a)A(a)xAxA(x),A(x)(x),A(x)是是由由A(a)A(a)中中的的a a的的部部分分出现替换为出现替换为x x而得而得 (+)+)（引入律）引入律）4.1 4.1 谓词逻辑自然推理系统谓词逻辑自然推理系统F FN N n系统系统F FN N的推理规则：的推理规则：14 14 如如 果果 A(a)A(a)且且 a a不不 在在 中中 出出 现现，则则 xAxA(x)(x)（+）（引入律）引入律）n=p,p:=p,p:今天学校放假。今天学校放假。a:a:小王小王A(a):A(

47、a):小王没到学校上课。小王没到学校上课。如果如果pA(a)pA(a)，则则pp xAxA(x)(x)n=p(a),p(a):=p(a),p(a):小王今天生病。小王今天生病。A(a):A(a):小王没到学校上课。小王没到学校上课。如果如果p(a)A(a)p(a)A(a)，则不一定有则不一定有p(a)p(a)xAxA(x)(x)4.1 4.1 谓词逻辑自然推理系统谓词逻辑自然推理系统F FN N n系统系统F FN N的推理规则：的推理规则：1515 ,A(a)B,A(a)B 且且a a不在不在和和B B中出现，则中出现，则,xAxA(x)B (x)B （-）（消去消去律）律）n=,A(a):

48、,A(a):小王没到学校上课。小王没到学校上课。B:B:今天没有全部出勤今天没有全部出勤。如果如果A(a)BA(a)B，则则 xAxA(x)B(x)B n=,A(a):,A(a):小王没到学校上课。小王没到学校上课。B(a):B(a):今天小王生病。今天小王生病。如果如果A(a)B(a)A(a)B(a)，则不一定有则不一定有 xAxA(x)B(a)(x)B(a)4.1 4.1 谓词逻辑自然推理系统谓词逻辑自然推理系统F FN N 1.1.2.2.3.3.4.4.A(a)A(a)取取a a 1 15.5.xAxA(x)(4,(x)(4,+)1.1.2.2.A(a)(H A(a)(H)取取a a

49、1 1 3.3.xAxA(x)(4,(x)(4,+)n系统系统F FN N的推理规则：的推理规则：14 14 如果如果A(a)A(a)且且a a不在不在中出现中出现，则，则 xAxA(x)(x)（+）（引入引入律）律）4.1 4.1 谓词逻辑自然推理系统谓词逻辑自然推理系统F FN N 1.1.xAxA(x)(x)(已知）已知）2.2.A(a)(1,A(a)(1,-)n系统系统F FN N的推理规则：的推理规则：1515 ,A(a)B,A(a)B 且且a a不在不在和和B B中出现，则中出现，则,xAxA(x)B (x)B （-）（消消去律）去律）4.1 4.1 谓词逻辑自然推理系统谓词逻辑自

50、然推理系统F FN N 1.1.2.2.A(a)(H A(a)(H)取取a a 1,41,43.3.4.4.B B5.5.xAxA(x)(x)(已知已知)6.6.B.B (2,4,(2,4,-)1.1.2.2.xAxA(x)(x)(已知已知)3.3.A(a)(H A(a)(H)取取a a 1,41,4 4.4.5.5.B B6.6.B B (2,4,(2,4,-)n系统系统F FN N的推理规则：的推理规则：1515 ,A(a)B,A(a)B 且且a a不在不在和和B B中出现，则中出现，则,xAxA(x)B (x)B （-）（消消去律）去律）4.2 4.2 F FN N系统的展开系统的展开