《一阶谓词逻辑PPT精品文档》由会员分享,可在线阅读,更多相关《一阶谓词逻辑PPT精品文档(76页珍藏版)》请在金锄头文库上搜索。
1、第二讲第二讲 一阶一阶/谓词逻辑谓词逻辑在在在在LsLs中中中中,把把把把命命命命题题题题分分分分解解解解到到到到原原原原子子子子命命命命题题题题为为为为止止止止,认认认认为为为为原原原原子子子子命命命命题题题题是是是是不不不不能能能能再再再再分分分分解解解解的的的的,仅仅仅仅仅仅仅仅研研研研究究究究以以以以原原原原子子子子命命命命题题题题为为为为基基基基本本本本单单单单位位位位的的的的复复复复合合合合命命命命题题题题之之之之间间间间的的的的逻逻逻逻辑辑辑辑关关关关系系系系和和和和推推推推理理理理。这这这这样样样样,有有有有些些些些推推推推理理理理用用用用命命命命题题题题逻逻逻逻辑辑辑辑就就就
2、就难难难难以以以以确确确确切切切切地地地地表表表表示示示示出出出出来来来来。例例例例如如如如,著著著著名名名名的的的的亚亚亚亚里里里里士士士士多多多多德德德德三三三三段段段段论论论论苏格拉底推理:苏格拉底推理:苏格拉底推理:苏格拉底推理:退出退出所有的人都是要死的,所有的人都是要死的,所有的人都是要死的,所有的人都是要死的,苏格拉底是人,苏格拉底是人,苏格拉底是人,苏格拉底是人,所以苏格拉底是要死的。所以苏格拉底是要死的。所以苏格拉底是要死的。所以苏格拉底是要死的。根据常识,认为这个推理是正确的。但是,根据常识,认为这个推理是正确的。但是,根据常识,认为这个推理是正确的。但是,根据常识,认为这
3、个推理是正确的。但是,若用若用若用若用LsLs来表示,设来表示,设来表示,设来表示,设P P、Q Q和和和和R R分别表示这三个原分别表示这三个原分别表示这三个原分别表示这三个原子命题,则有子命题,则有子命题,则有子命题,则有P P,Q QR R然然然然而而而而,( (P PQ Q)R R并并并并不不不不是是是是永永永永真真真真式式式式,故故故故上上上上述述述述推推推推理理理理形形形形式式式式又又又又是是是是错错错错误误误误的的的的。一一一一个个个个推推推推理理理理,得得得得出出出出矛矛矛矛盾盾盾盾的的的的结结结结论论论论,问问问问题题题题在在在在哪哪哪哪里里里里呢呢呢呢? ? 问问问问题题题
4、题就就就就在在在在于于于于这这这这类类类类推推推推理理理理中中中中,各各各各命命命命题题题题之之之之间间间间的的的的逻逻逻逻辑辑辑辑关关关关系系系系不不不不是是是是体体体体现现现现在在在在原原原原子子子子命命命命题题题题之之之之间间间间,而而而而是是是是体体体体现现现现在在在在构构构构成成成成原原原原子子子子命命命命题题题题的的的的内内内内部部部部成成成成分分分分之之之之间间间间,即即即即体体体体现现现现在在在在命命命命题题题题结结结结构构构构的的的的更更更更深深深深层层层层次次次次上上上上。对对对对此此此此,LsLs是是是是无无无无能能能能为为为为力力力力的的的的。所所所所以以以以,在在在在
5、研研研研究究究究某某某某些些些些推推推推理理理理时时时时,有有有有必必必必要要要要对对对对原原原原子子子子命命命命题题题题作作作作进进进进一一一一步步步步分分分分析析析析,分分分分析析析析出出出出其其其其中中中中的的的的个个个个体体体体词词词词,谓谓谓谓词词词词和和和和量量量量词词词词,研研研研究究究究它它它它们们们们的的的的形形形形式式式式结结结结构构构构的的的的逻逻逻逻辑辑辑辑关关关关系系系系、正正正正确确确确的的的的推推推推理理理理形形形形式式式式和和和和规规规规则则则则,这这这这些些些些正正正正是是是是谓谓谓谓词逻辑(简称为词逻辑(简称为词逻辑(简称为词逻辑(简称为LpLp)的基本内容
6、。)的基本内容。)的基本内容。)的基本内容。2.1 个体、谓词和量词个体、谓词和量词2.2 谓词公式与翻译谓词公式与翻译2.3 约束变元与自由变元约束变元与自由变元2.4 公式解释与类型公式解释与类型2.5 等价式与蕴涵式等价式与蕴涵式2.6 谓词公式范式谓词公式范式2.7 谓词逻辑的推理理论谓词逻辑的推理理论2.1 个体、谓词和量词个体、谓词和量词在在在在LpLp中中中中,命命命命题题题题是是是是具具具具有有有有真真真真假假假假意意意意义义义义的的的的陈陈陈陈述述述述句句句句。从从从从语语语语法法法法上上上上分分分分析析析析,一一一一个个个个陈陈陈陈述述述述句句句句由由由由主主主主语语语语和
7、和和和谓谓谓谓语语语语两两两两部部部部分分分分组组组组成成成成。在在在在LpLp中中中中,为为为为揭揭揭揭示示示示命命命命题题题题内内内内部部部部结结结结构构构构及及及及其其其其不不不不同同同同命命命命题题题题的的的的内内内内部部部部结结结结构构构构关关关关系系系系,就就就就按按按按照照照照这这这这两两两两部部部部分分分分对对对对命命命命题题题题进进进进行行行行分分分分析析析析,并并并并且且且且把把把把主主主主语语语语称称称称为为为为个个个个体体体体或或或或客客客客体体体体,把把把把谓语称为谓词。谓语称为谓词。谓语称为谓词。谓语称为谓词。.个体、谓词和命题的谓词形式个体、谓词和命题的谓词形式定
8、义定义定义定义2.1.12.1.1 在原子命题中,所描述的对象称在原子命题中,所描述的对象称在原子命题中,所描述的对象称在原子命题中,所描述的对象称为个体;用以描述个体的性质或个体间关系的为个体;用以描述个体的性质或个体间关系的为个体;用以描述个体的性质或个体间关系的为个体;用以描述个体的性质或个体间关系的部分,称为谓词。部分,称为谓词。部分,称为谓词。部分,称为谓词。个体,是指可以独立存在的事物,它可以个体,是指可以独立存在的事物,它可以个体,是指可以独立存在的事物,它可以个体,是指可以独立存在的事物,它可以是具体的,也可以是抽象的,如张明,计算机,是具体的,也可以是抽象的,如张明,计算机,
9、是具体的,也可以是抽象的,如张明,计算机,是具体的,也可以是抽象的,如张明,计算机,精神等。表示特定的个体,称为个体常元,以精神等。表示特定的个体,称为个体常元,以精神等。表示特定的个体,称为个体常元,以精神等。表示特定的个体,称为个体常元,以a a,b b,c c或带下标的或带下标的或带下标的或带下标的a ai i,b bi i,c ci i表示;表示不表示;表示不表示;表示不表示;表示不确定的个体,称为个体变元,以确定的个体,称为个体变元,以确定的个体,称为个体变元,以确定的个体,称为个体变元,以x x,y y,z z或或或或x xi i,y yi i,z zi i表示。表示。表示。表示。
10、谓词,当与一个个体相联系时,它刻划了个体性谓词,当与一个个体相联系时,它刻划了个体性谓词,当与一个个体相联系时,它刻划了个体性谓词,当与一个个体相联系时,它刻划了个体性质;当与两个或两个以上个体相联系时,它刻划了个体质;当与两个或两个以上个体相联系时,它刻划了个体质;当与两个或两个以上个体相联系时,它刻划了个体质;当与两个或两个以上个体相联系时,它刻划了个体之间的关系。表示特定谓词,称为谓词常元,表示不确之间的关系。表示特定谓词,称为谓词常元,表示不确之间的关系。表示特定谓词,称为谓词常元,表示不确之间的关系。表示特定谓词,称为谓词常元,表示不确定的谓词,称为谓词变元,都用大写英文字母,如定的
11、谓词,称为谓词变元,都用大写英文字母,如定的谓词,称为谓词变元,都用大写英文字母,如定的谓词,称为谓词变元,都用大写英文字母,如P P,Q Q,R R,或其带上、下标来表示。,或其带上、下标来表示。,或其带上、下标来表示。,或其带上、下标来表示。例如,在命题例如,在命题例如,在命题例如,在命题“ “张明是位大学生张明是位大学生张明是位大学生张明是位大学生” ”中,中,中,中,“ “张明张明张明张明” ”是个是个是个是个体,体,体,体,“ “是位大学生是位大学生是位大学生是位大学生” ”是谓词,它刻划了是谓词,它刻划了是谓词,它刻划了是谓词,它刻划了“ “张明张明张明张明” ”的性质。设的性质。
12、设的性质。设的性质。设S S:是位大学生,:是位大学生,:是位大学生,:是位大学生,c c:张明,则:张明,则:张明,则:张明,则“ “张明是位大学生张明是位大学生张明是位大学生张明是位大学生” ”可表示可表示可表示可表示为为为为S S( (c c) ),或者写成,或者写成,或者写成,或者写成S S( (c c) ):张明是位大学生。:张明是位大学生。:张明是位大学生。:张明是位大学生。又如,在命题又如,在命题又如,在命题又如,在命题“ “武汉位于北京和广州之间武汉位于北京和广州之间武汉位于北京和广州之间武汉位于北京和广州之间” ”中,武中,武中,武中,武汉、北京和广州是三个个体,而汉、北京和
13、广州是三个个体,而汉、北京和广州是三个个体,而汉、北京和广州是三个个体,而“位于位于位于位于和和和和之间之间之间之间” ”是是是是谓词,它刻划了武汉、北京和广州之间的关系。设谓词,它刻划了武汉、北京和广州之间的关系。设谓词,它刻划了武汉、北京和广州之间的关系。设谓词,它刻划了武汉、北京和广州之间的关系。设P P:位于位于位于位于和和和和之间,之间,之间,之间,a a:武汉,:武汉,:武汉,:武汉,b b:北京,:北京,:北京,:北京,c c:广州,则:广州,则:广州,则:广州,则P P( (a a,b b,c c) ):武汉位于北京和广州之间。:武汉位于北京和广州之间。:武汉位于北京和广州之间
14、。:武汉位于北京和广州之间。定义定义定义定义2.1.22.1.2 一个原子命题用一个谓词一个原子命题用一个谓词一个原子命题用一个谓词一个原子命题用一个谓词( (如如如如P P) )和和和和n n个有次序的个体常元个有次序的个体常元个有次序的个体常元个有次序的个体常元( (如如如如a a1 1,a a2 2,a an n) )表示表示表示表示成成成成P P( (a a1 1,a a2 2,a an n) ),称它为该原子命题的谓词,称它为该原子命题的谓词,称它为该原子命题的谓词,称它为该原子命题的谓词形式或命题的谓词形式。形式或命题的谓词形式。形式或命题的谓词形式。形式或命题的谓词形式。应注意的
15、是,命题的谓词形式中的个体出应注意的是,命题的谓词形式中的个体出应注意的是,命题的谓词形式中的个体出应注意的是,命题的谓词形式中的个体出现的次序影响命题的真值,不是随意变动,否现的次序影响命题的真值,不是随意变动,否现的次序影响命题的真值,不是随意变动,否现的次序影响命题的真值,不是随意变动,否则真值会有变化。如上述例子中,则真值会有变化。如上述例子中,则真值会有变化。如上述例子中,则真值会有变化。如上述例子中,P P( (b b, ,a a, ,c c) )是假。是假。是假。是假。.原子谓词公式原子谓词公式原子命题的谓词形式还可以进一步加以抽原子命题的谓词形式还可以进一步加以抽原子命题的谓词
16、形式还可以进一步加以抽原子命题的谓词形式还可以进一步加以抽象,比如在谓词右侧的圆括号内的象,比如在谓词右侧的圆括号内的象,比如在谓词右侧的圆括号内的象,比如在谓词右侧的圆括号内的n n个个体常元个个体常元个个体常元个个体常元被替换成个体变元,如被替换成个体变元,如被替换成个体变元,如被替换成个体变元,如x x1 1, ,x x2 2,x xn n,这样便得了,这样便得了,这样便得了,这样便得了一种关于命题结构的新表达形式,称之为一种关于命题结构的新表达形式,称之为一种关于命题结构的新表达形式,称之为一种关于命题结构的新表达形式,称之为n n元原元原元原元原子谓词。子谓词。子谓词。子谓词。定义定
17、义定义定义2.1.32.1.3 由一个谓词由一个谓词由一个谓词由一个谓词( (如如如如P P) )和和和和n n个体变元个体变元个体变元个体变元( (如如如如x x1 1,x x2 2,x xn n) )组成的组成的组成的组成的P P( (x x1 1,x x2 2,x xn n) ),称它,称它,称它,称它为为为为n n元原子谓词或元原子谓词或元原子谓词或元原子谓词或n n元命题函数,简称元命题函数,简称元命题函数,简称元命题函数,简称n n元谓词。元谓词。元谓词。元谓词。而个体变元的论述范围,称为个体域或论域。而个体变元的论述范围,称为个体域或论域。而个体变元的论述范围,称为个体域或论域。
18、而个体变元的论述范围,称为个体域或论域。当当当当n n=1=1时,称一元谓词;当时,称一元谓词;当时,称一元谓词;当时,称一元谓词;当n n=2=2时,称为二时,称为二时,称为二时,称为二元谓词,元谓词,元谓词,元谓词,。特别地,当。特别地,当。特别地,当。特别地,当n n=0=0,称为零元谓词。,称为零元谓词。,称为零元谓词。,称为零元谓词。零元谓词是命题,这样命题与谓词就得到了统零元谓词是命题,这样命题与谓词就得到了统零元谓词是命题,这样命题与谓词就得到了统零元谓词是命题,这样命题与谓词就得到了统一。一。一。一。n n元谓词不是命题,只有其中的个体变元用特定个元谓词不是命题,只有其中的个体
19、变元用特定个元谓词不是命题,只有其中的个体变元用特定个元谓词不是命题,只有其中的个体变元用特定个体或个体常元替代时,才能成为一个命题。但个体变元体或个体常元替代时,才能成为一个命题。但个体变元体或个体常元替代时,才能成为一个命题。但个体变元体或个体常元替代时,才能成为一个命题。但个体变元在哪些论域取特定的值,对命题的真值极有影响。在哪些论域取特定的值,对命题的真值极有影响。在哪些论域取特定的值,对命题的真值极有影响。在哪些论域取特定的值,对命题的真值极有影响。例如,令例如,令例如,令例如,令S S( (x x) ):x x是大学生。若是大学生。若是大学生。若是大学生。若x x的论域为某大学的的
20、论域为某大学的的论域为某大学的的论域为某大学的计算机系中的全体同学,则计算机系中的全体同学,则计算机系中的全体同学,则计算机系中的全体同学,则S S( (x x) )是真的;若是真的;若是真的;若是真的;若x x的论域是某的论域是某的论域是某的论域是某中学的全体学生,则中学的全体学生,则中学的全体学生,则中学的全体学生,则S S( (x x) )是假的;若是假的;若是假的;若是假的;若x x的论域是某剧场中的论域是某剧场中的论域是某剧场中的论域是某剧场中的观众,且观众中有大学生也有非大学生的其它观众,的观众,且观众中有大学生也有非大学生的其它观众,的观众,且观众中有大学生也有非大学生的其它观众
21、,的观众,且观众中有大学生也有非大学生的其它观众,则则则则S S( (x x) )是真值是不确定的。是真值是不确定的。是真值是不确定的。是真值是不确定的。通常,把一个通常,把一个通常,把一个通常,把一个n n元谓词中的每个个体的论域元谓词中的每个个体的论域元谓词中的每个个体的论域元谓词中的每个个体的论域综合在一起作为它的论域,称为综合在一起作为它的论域,称为综合在一起作为它的论域,称为综合在一起作为它的论域,称为n n元谓词的全总元谓词的全总元谓词的全总元谓词的全总论域。定义了全总论域,为深入研究命题提供论域。定义了全总论域,为深入研究命题提供论域。定义了全总论域,为深入研究命题提供论域。定义
22、了全总论域,为深入研究命题提供了方便。当一个命题没有指明论域时,一般都了方便。当一个命题没有指明论域时,一般都了方便。当一个命题没有指明论域时,一般都了方便。当一个命题没有指明论域时,一般都从全总论域作为其论域。而这时又常常要采用从全总论域作为其论域。而这时又常常要采用从全总论域作为其论域。而这时又常常要采用从全总论域作为其论域。而这时又常常要采用一个谓词如一个谓词如一个谓词如一个谓词如P P( (x x) )来限制个体变元来限制个体变元来限制个体变元来限制个体变元x x的取值范围,的取值范围,的取值范围,的取值范围,并把并把并把并把P P( (x x) )称为特性谓词。称为特性谓词。称为特性
23、谓词。称为特性谓词。.量词量词利用利用利用利用n n元谓词和它的论域概念,有时还是不元谓词和它的论域概念,有时还是不元谓词和它的论域概念,有时还是不元谓词和它的论域概念,有时还是不能用符号来很准确地表达某些命题,例如能用符号来很准确地表达某些命题,例如能用符号来很准确地表达某些命题,例如能用符号来很准确地表达某些命题,例如S S( (x x) )表表表表示示示示x x是大学生,而是大学生,而是大学生,而是大学生,而x x的个体域为某单位的职工,的个体域为某单位的职工,的个体域为某单位的职工,的个体域为某单位的职工,那么那么那么那么S S( (x x) )可表示某单位职工都是大学生,也可表可表示
24、某单位职工都是大学生,也可表可表示某单位职工都是大学生,也可表可表示某单位职工都是大学生,也可表示某单位有一些职工是大学生,为了避免理解示某单位有一些职工是大学生,为了避免理解示某单位有一些职工是大学生,为了避免理解示某单位有一些职工是大学生,为了避免理解上的歧义,在上的歧义,在上的歧义,在上的歧义,在LpLp中,需要引入用以刻划中,需要引入用以刻划中,需要引入用以刻划中,需要引入用以刻划“ “所有的所有的所有的所有的” ”、“ “存在一些存在一些存在一些存在一些” ”等表示不同数量的词,即量词,等表示不同数量的词,即量词,等表示不同数量的词,即量词,等表示不同数量的词,即量词,其定义如下:其
25、定义如下:其定义如下:其定义如下:定义定义定义定义2.1.42.1.4 符号符号符号符号 称为全称量词符,用来称为全称量词符,用来称为全称量词符,用来称为全称量词符,用来表达表达表达表达“ “对所有的对所有的对所有的对所有的” ”、“ “每一个每一个每一个每一个” ”、“ “对任何一个对任何一个对任何一个对任何一个” ”、“ “一切一切一切一切” ”等词语;等词语;等词语;等词语; x x称为全称量词,称称为全称量词,称称为全称量词,称称为全称量词,称x x为指导变为指导变为指导变为指导变元。元。元。元。符号符号符号符号 称为存在量词符,用来表达称为存在量词符,用来表达称为存在量词符,用来表达
26、称为存在量词符,用来表达“ “存在存在存在存在一些一些一些一些” ”、“ “至少有一个至少有一个至少有一个至少有一个” ”、“ “对于一些对于一些对于一些对于一些” ”、“ “某个某个某个某个” ”等等等等词语;词语;词语;词语; x x称为存在量词,称为存在量词,称为存在量词,称为存在量词,x x称为指导变元。称为指导变元。称为指导变元。称为指导变元。* *符号符号符号符号 ! !称为存在唯一量词符,用来表达称为存在唯一量词符,用来表达称为存在唯一量词符,用来表达称为存在唯一量词符,用来表达“ “恰有恰有恰有恰有一个一个一个一个” ”、“ “存在唯一存在唯一存在唯一存在唯一” ”等词语;等词
27、语;等词语;等词语; ! !x x称为存在唯一量词,称称为存在唯一量词,称称为存在唯一量词,称称为存在唯一量词,称x x为指导变元。为指导变元。为指导变元。为指导变元。全称量词、存在量词、存在唯一量词统称量词。全称量词、存在量词、存在唯一量词统称量词。全称量词、存在量词、存在唯一量词统称量词。全称量词、存在量词、存在唯一量词统称量词。量词记号是由逻辑学家量词记号是由逻辑学家量词记号是由逻辑学家量词记号是由逻辑学家F Frayray引入的,有了量词之后,用引入的,有了量词之后,用引入的,有了量词之后,用引入的,有了量词之后,用逻辑符号表示命题的能力大大加强了。逻辑符号表示命题的能力大大加强了。逻
28、辑符号表示命题的能力大大加强了。逻辑符号表示命题的能力大大加强了。例例例例 试用量词、谓词表示下列命题:试用量词、谓词表示下列命题:试用量词、谓词表示下列命题:试用量词、谓词表示下列命题: 所有大学生都热爱祖国;所有大学生都热爱祖国;所有大学生都热爱祖国;所有大学生都热爱祖国; 每个自然数都是实数;每个自然数都是实数;每个自然数都是实数;每个自然数都是实数; 一些大学生有远大理想;一些大学生有远大理想;一些大学生有远大理想;一些大学生有远大理想; 有的自然数是素数。有的自然数是素数。有的自然数是素数。有的自然数是素数。解解解解 令令令令S S( (x x) ):x x是大学生,是大学生,是大学
29、生,是大学生,L L( (x x) ):x x热爱祖国,热爱祖国,热爱祖国,热爱祖国,N N( (x x) ):x x是自然数,是自然数,是自然数,是自然数,R R( (x x) ):x x是实数,是实数,是实数,是实数,I I( (x x) ):x x有远有远有远有远大理想,大理想,大理想,大理想,P P( (x x) ):x x是素数。是素数。是素数。是素数。则例中各命题分别表示为:则例中各命题分别表示为:则例中各命题分别表示为:则例中各命题分别表示为:( ( x x)( )(S S( (x x) )L L( (x x) ) ( ( x x)( )(N N( (x x) )R R( (x
30、x) )( ( x x)( )(S S( (x x) ) I I( (x x) ) ( ( x x)( )(N N( (x x) ) P P( (x x) )在该例的解答中,由于命题中没有指明个体域,在该例的解答中,由于命题中没有指明个体域,在该例的解答中,由于命题中没有指明个体域,在该例的解答中,由于命题中没有指明个体域,这便意味着各命题是在全总论域中讨论,因而都使用了这便意味着各命题是在全总论域中讨论,因而都使用了这便意味着各命题是在全总论域中讨论,因而都使用了这便意味着各命题是在全总论域中讨论,因而都使用了特性谓词,如特性谓词,如特性谓词,如特性谓词,如S S( (x x) )、N N(
31、 (x x) )。而且还可以看出,。而且还可以看出,。而且还可以看出,。而且还可以看出,量词与特量词与特量词与特量词与特性谓词的搭配还有一定规律性谓词的搭配还有一定规律性谓词的搭配还有一定规律性谓词的搭配还有一定规律,即全称量词后跟一个条件,即全称量词后跟一个条件,即全称量词后跟一个条件,即全称量词后跟一个条件式,而特性谓词作为其前件出现;存在量词后跟一个合式,而特性谓词作为其前件出现;存在量词后跟一个合式,而特性谓词作为其前件出现;存在量词后跟一个合式,而特性谓词作为其前件出现;存在量词后跟一个合取式,特性谓词作为一个合取项出现。取式,特性谓词作为一个合取项出现。取式,特性谓词作为一个合取项
32、出现。取式,特性谓词作为一个合取项出现。如果在解答时,指明了个体域,便不用特如果在解答时,指明了个体域,便不用特如果在解答时,指明了个体域,便不用特如果在解答时,指明了个体域,便不用特性谓词,例如在性谓词,例如在性谓词,例如在性谓词,例如在、中令个体域为全体大学中令个体域为全体大学中令个体域为全体大学中令个体域为全体大学生,生,生,生,和和和和中的个体域为全部自然数,则可符中的个体域为全部自然数,则可符中的个体域为全部自然数,则可符中的个体域为全部自然数,则可符号化为:号化为:号化为:号化为:( ( x x) )L L( (x x) ) ( ( x x) )R R( (x x) )( ( x
33、x) )I I( (x x) ) ( ( x x) )P P( (x x) )谓词前加上了量词,称为谓词的量化。若谓词前加上了量词,称为谓词的量化。若谓词前加上了量词,称为谓词的量化。若谓词前加上了量词,称为谓词的量化。若一个谓词中所有个体变元都量化了,则该谓词一个谓词中所有个体变元都量化了,则该谓词一个谓词中所有个体变元都量化了,则该谓词一个谓词中所有个体变元都量化了,则该谓词就变成了命题。这是因为在谓词被量化后,可就变成了命题。这是因为在谓词被量化后,可就变成了命题。这是因为在谓词被量化后,可就变成了命题。这是因为在谓词被量化后,可以在整个个体域中考虑命题的真值了。这如同以在整个个体域中考
34、虑命题的真值了。这如同以在整个个体域中考虑命题的真值了。这如同以在整个个体域中考虑命题的真值了。这如同数学中的函数数学中的函数数学中的函数数学中的函数f f( (x x) ),的值是不确定的,的值是不确定的,的值是不确定的,的值是不确定的,但但但但 可确定其值。可确定其值。可确定其值。可确定其值。2.2 谓词公式与翻译谓词公式与翻译.谓词公式谓词公式为为为为了了了了方方方方便便便便处处处处理理理理数数数数学学学学和和和和计计计计算算算算机机机机科科科科学学学学的的的的逻逻逻逻辑辑辑辑问问问问题及谓词表示的直觉清晰性,将引进项的概念。题及谓词表示的直觉清晰性,将引进项的概念。题及谓词表示的直觉清
35、晰性,将引进项的概念。题及谓词表示的直觉清晰性,将引进项的概念。定义定义定义定义2.2.12.2.1 项由下列规则形成:项由下列规则形成:项由下列规则形成:项由下列规则形成: 个体常元和个体变元是项;个体常元和个体变元是项;个体常元和个体变元是项;个体常元和个体变元是项; 若若若若f f是是是是n n元元元元函函函函数数数数,且且且且t t1 1,t t2 2,t tn n是是是是项项项项,则则则则f f( (t t1 1,t t2 2,t tn n) )是项;是项;是项;是项; 所有项都由所有项都由所有项都由所有项都由和和和和生成。生成。生成。生成。有了项的定义,函数的概念就可用来表示个体常
36、有了项的定义,函数的概念就可用来表示个体常有了项的定义,函数的概念就可用来表示个体常有了项的定义,函数的概念就可用来表示个体常元和个体变元。元和个体变元。元和个体变元。元和个体变元。例如,令例如,令例如,令例如,令f f( (x x, ,y y) )表示表示表示表示x x+ +y y,谓词,谓词,谓词,谓词N N( (x x) )表示表示表示表示x x是自然数,是自然数,是自然数,是自然数,那么那么那么那么f f(2,3)(2,3)表示个体自然数表示个体自然数表示个体自然数表示个体自然数5 5,而,而,而,而N N( (f f(2,3)(2,3)表示表示表示表示5 5是自然数。是自然数。是自然
37、数。是自然数。这里函数是就广义而言的。这里函数是就广义而言的。这里函数是就广义而言的。这里函数是就广义而言的。例如例如例如例如P P( (x x): ):x x是教授,是教授,是教授,是教授,f f( (x x): ):x x的父亲,的父亲,的父亲,的父亲,c c: :张强,那么张强,那么张强,那么张强,那么P P( (f f( (c c) )便是表示便是表示便是表示便是表示“ “张强的父亲是教授张强的父亲是教授张强的父亲是教授张强的父亲是教授” ”这一命题。这一命题。这一命题。这一命题。函数的使用给谓词表示带来很大方便。函数的使用给谓词表示带来很大方便。函数的使用给谓词表示带来很大方便。函数
38、的使用给谓词表示带来很大方便。例如,用谓词表示命题:例如,用谓词表示命题:例如,用谓词表示命题:例如,用谓词表示命题:“ “对任意整数对任意整数对任意整数对任意整数x x,x x2 2- -1=(1=(x x+1)(+1)(x x-1)-1)是恒等式是恒等式是恒等式是恒等式” ”。解:令解:令解:令解:令I I( (x x): ):x x是整数,是整数,是整数,是整数,f f( (x x)=)=x x2 2-1-1,g g( (x x)=()=(x x+1)(+1)(x x-1)-1),E E( (x x, ,y y): ):x x= =y y,则该命题可表示成:,则该命题可表示成:,则该命题
39、可表示成:,则该命题可表示成:( ( x x)( )(I I( (x x) )E E( (f f( (x x), ),g g( (x x)。定义定义定义定义2.2.22.2.2 若若若若P P( (x x1 1,x x2 2,x xn n) )是是是是n n元谓词,元谓词,元谓词,元谓词,t t1 1,t t2 2,t tn n是项,则称是项,则称是项,则称是项,则称P P( (t t1 1,t t2 2,t tn n) )为为为为LsLs中原子谓词公式,简称原子公式。中原子谓词公式,简称原子公式。中原子谓词公式,简称原子公式。中原子谓词公式,简称原子公式。下面,由原子公式出发,给出下面,由原
40、子公式出发,给出下面,由原子公式出发,给出下面,由原子公式出发,给出LpLp中的合式中的合式中的合式中的合式谓词公式的归纳定义。谓词公式的归纳定义。谓词公式的归纳定义。谓词公式的归纳定义。定义定义定义定义2.2.32.2.3 合式谓词公式当且仅当由下列规合式谓词公式当且仅当由下列规合式谓词公式当且仅当由下列规合式谓词公式当且仅当由下列规则形成的符号串则形成的符号串则形成的符号串则形成的符号串 原子公式是合式谓词公式;原子公式是合式谓词公式;原子公式是合式谓词公式;原子公式是合式谓词公式; 若若若若A A是合式谓词公式,则是合式谓词公式,则是合式谓词公式,则是合式谓词公式,则( ( A A) )
41、是合式谓是合式谓是合式谓是合式谓词公式;词公式;词公式;词公式; 若若若若A A,B B是合式谓词公式,则是合式谓词公式,则是合式谓词公式,则是合式谓词公式,则( (A AB B) ),( (A AB B) ),( (A AB B) )和和和和( (A AB B) )都是合式谓词公式;都是合式谓词公式;都是合式谓词公式;都是合式谓词公式; 若若若若A A是合式谓词公式,是合式谓词公式,是合式谓词公式,是合式谓词公式,x x是个体变元,则是个体变元,则是个体变元,则是个体变元,则( ( x x) )A A、( ( x x) )A A都是合式谓词公式;都是合式谓词公式;都是合式谓词公式;都是合式谓
42、词公式; 仅有有限项次使用仅有有限项次使用仅有有限项次使用仅有有限项次使用、和和和和形成形成形成形成的才是合式谓词公式。的才是合式谓词公式。的才是合式谓词公式。的才是合式谓词公式。. .谓词逻辑的翻译谓词逻辑的翻译谓词逻辑的翻译谓词逻辑的翻译把把把把一一一一个个个个文文文文字字字字叙叙叙叙述述述述的的的的命命命命题题题题,用用用用谓谓谓谓词词词词公公公公式式式式表表表表示示示示出出出出来来来来,称称称称为为为为谓谓谓谓词词词词逻逻逻逻辑辑辑辑的的的的翻翻翻翻译译译译或或或或符符符符号号号号化化化化;反反反反之之之之亦亦亦亦然然然然。一一一一般般般般说说说说来来来来,符号化的步骤如下:符号化的步
43、骤如下:符号化的步骤如下:符号化的步骤如下:正正正正确确确确理理理理解解解解给给给给定定定定命命命命题题题题。必必必必要要要要时时时时把把把把命命命命题题题题改改改改叙叙叙叙(换换换换句句句句话话话话说说说说),使使使使其其其其中中中中每每每每个个个个原原原原子子子子命命命命题题题题、原原原原子子子子命命命命题题题题之之之之间间间间的的的的关关关关系系系系能能能能明显表达出来。明显表达出来。明显表达出来。明显表达出来。把每个原子命题分解成个体、谓词和量把每个原子命题分解成个体、谓词和量把每个原子命题分解成个体、谓词和量把每个原子命题分解成个体、谓词和量词;在全总论域讨论时,要给出特性谓词。词;
44、在全总论域讨论时,要给出特性谓词。词;在全总论域讨论时,要给出特性谓词。词;在全总论域讨论时,要给出特性谓词。找出恰当量词。应注意全称量词找出恰当量词。应注意全称量词找出恰当量词。应注意全称量词找出恰当量词。应注意全称量词( ( x x) )后后后后跟条件式,存在量词跟条件式,存在量词跟条件式,存在量词跟条件式,存在量词( ( x x) )后跟合取式。后跟合取式。后跟合取式。后跟合取式。用恰当的联结词把给定命题表示出来。用恰当的联结词把给定命题表示出来。用恰当的联结词把给定命题表示出来。用恰当的联结词把给定命题表示出来。例例例例 将命题将命题将命题将命题“ “没有最大的自然数没有最大的自然数没
45、有最大的自然数没有最大的自然数” ”符号化。符号化。符号化。符号化。解解解解: 命命命命题题题题中中中中“ “没没没没有有有有最最最最大大大大的的的的” ”显显显显然然然然是是是是对对对对所所所所有有有有的的的的自自自自然然然然数数数数而而而而言言言言,所所所所以以以以可可可可理理理理解解解解为为为为“ “对对对对所所所所有有有有的的的的x x,如如如如果果果果x x是是是是自自自自然然然然数数数数,则则则则一定还有比一定还有比一定还有比一定还有比x x大的自然数大的自然数大的自然数大的自然数” ”;再再再再具具具具体体体体点点点点,即即即即“ “对对对对所所所所有有有有的的的的x x如如如如
46、果果果果x x是是是是自自自自然然然然数数数数,则则则则一一一一定定定定存在存在存在存在y y,y y也是自然数,并且也是自然数,并且也是自然数,并且也是自然数,并且y y比比比比x x大大大大” ”。令令令令N N( (x x): ): x x是是是是自自自自然然然然数数数数,G G( (x x, ,y y): ): x x大大大大于于于于y y,则则则则原原原原命命命命题题题题表表表表示为:示为:示为:示为:( ( x x)( )(N N( (x x) )( ( y y)( )(N N( (y y) ) G G( (y y, ,x x)。例例例例 将语句将语句将语句将语句“ “今天有雨雪,
47、有些人会跌跤今天有雨雪,有些人会跌跤今天有雨雪,有些人会跌跤今天有雨雪,有些人会跌跤” ”符号化。符号化。符号化。符号化。解:解:解:解: 本语句可理解为本语句可理解为本语句可理解为本语句可理解为“ “若今天下雨又下雪,则存若今天下雨又下雪,则存若今天下雨又下雪,则存若今天下雨又下雪,则存在在在在x x,x x是人且是人且是人且是人且x x会跌跤会跌跤会跌跤会跌跤” ”。令令令令R R: : 今天下雨,今天下雨,今天下雨,今天下雨,S S: : 今天下雪,今天下雪,今天下雪,今天下雪,MM( (x x): ): x x是人,是人,是人,是人,F F( (x x): ): x x会跌跤,则本语句
48、可表示为:会跌跤,则本语句可表示为:会跌跤,则本语句可表示为:会跌跤,则本语句可表示为:R R S S( ( x x)( )(MM( (x x) ) F F( (x x) )。由于人们对命题的文字叙述含意理解的不同,强由于人们对命题的文字叙述含意理解的不同,强由于人们对命题的文字叙述含意理解的不同,强由于人们对命题的文字叙述含意理解的不同,强调的重点不同,会影响到命题符号化的形式不同。调的重点不同,会影响到命题符号化的形式不同。调的重点不同,会影响到命题符号化的形式不同。调的重点不同,会影响到命题符号化的形式不同。2.3 约束变元与自由变元约束变元与自由变元定定定定义义义义2.3.12.3.1
49、 给给给给定定定定一一一一个个个个谓谓谓谓词词词词公公公公式式式式A A,其其其其中中中中有有有有一一一一部部部部分分分分公公公公式式式式形形形形如如如如( ( x x) )B B( (x x) )或或或或( ( x x) )B B( (x x) ),则则则则称称称称它它它它为为为为A A的的的的x x约约约约束束束束部部部部分分分分,称称称称B B( (x x) )为为为为相相相相应应应应量量量量词词词词的的的的作作作作用用用用域域域域或或或或辖辖辖辖域域域域。在在在在辖辖辖辖域域域域中中中中,x x的的的的所所所所有有有有出出出出现现现现称称称称为为为为约约约约束束束束出出出出现现现现,x
50、 x称称称称为为为为约约约约束束束束变变变变元元元元;B B中中中中不不不不是是是是约约约约束束束束出出出出现现现现的的的的其其其其它它它它个个个个体体体体变变变变元元元元的的的的出出出出现现现现称称称称为为为为自自自自由由由由出出出出现现现现,这这这这些些些些个个个个体体体体变变变变元元元元称称称称自自自自由变元。由变元。由变元。由变元。对于给定的谓词公式,能够准确地判定它对于给定的谓词公式,能够准确地判定它对于给定的谓词公式,能够准确地判定它对于给定的谓词公式,能够准确地判定它的辖域、约束变元和自由变元是很重要的。的辖域、约束变元和自由变元是很重要的。的辖域、约束变元和自由变元是很重要的。
51、的辖域、约束变元和自由变元是很重要的。通常,一个量词的辖域是某公式通常,一个量词的辖域是某公式通常,一个量词的辖域是某公式通常,一个量词的辖域是某公式A A的一部分的一部分的一部分的一部分,称为,称为,称为,称为A A的子公式。因此,确定一个量词的辖域的子公式。因此,确定一个量词的辖域的子公式。因此,确定一个量词的辖域的子公式。因此,确定一个量词的辖域即是找出位于该量词之后的相邻接的子公式,即是找出位于该量词之后的相邻接的子公式,即是找出位于该量词之后的相邻接的子公式,即是找出位于该量词之后的相邻接的子公式,具体地讲:具体地讲:具体地讲:具体地讲:若量词后有括号,则括号内的子公式就若量词后有括
52、号,则括号内的子公式就若量词后有括号,则括号内的子公式就若量词后有括号,则括号内的子公式就是该量词的辖域;是该量词的辖域;是该量词的辖域;是该量词的辖域;若量词后无括号,则与量词邻接的子公若量词后无括号,则与量词邻接的子公若量词后无括号,则与量词邻接的子公若量词后无括号,则与量词邻接的子公式为该量词的辖域。式为该量词的辖域。式为该量词的辖域。式为该量词的辖域。判定给定公式判定给定公式判定给定公式判定给定公式A A中个体变元是约束变元还是中个体变元是约束变元还是中个体变元是约束变元还是中个体变元是约束变元还是自由变元,关键是要看它在自由变元,关键是要看它在自由变元,关键是要看它在自由变元,关键是
53、要看它在A A中是约束出现,还中是约束出现,还中是约束出现,还中是约束出现,还是自由出现。是自由出现。是自由出现。是自由出现。今今今今后后后后常常常常用用用用元元元元语语语语言言言言符符符符号号号号A A( (x x) )表表表表示示示示x x是是是是其其其其中中中中的的的的一一一一个个个个个个个个体体体体变变变变元元元元自自自自由由由由出出出出现现现现的的的的任任任任意意意意公公公公式式式式,如如如如A A( (x x) )可可可可为为为为P P( (x x) )Q Q( (x x) ),P P( (x x) ) ( ( y y) )Q Q( (x x, ,y y) )等等等等。一一一一旦旦
54、旦旦在在在在A A( (x x) )前前前前加加加加上上上上量量量量词词词词( ( x x) )或或或或( ( x x) ),即即即即得得得得公公公公式式式式( ( x x) )A A( (x x), ),或或或或( ( x x) )A A( (x x) )。这这这这时时时时,x x即即即即是是是是约约约约束束束束出出出出现现现现了了了了。类类类类似似似似地,用地,用地,用地,用A A( (x x, ,y y) )表示表示表示表示x x和和和和y y是自由出现的公式。是自由出现的公式。是自由出现的公式。是自由出现的公式。定义定义定义定义2.3.22.3.2 设设设设A A为任意一个公式,若为任
55、意一个公式,若为任意一个公式,若为任意一个公式,若A A中无自由出中无自由出中无自由出中无自由出现的个体变元,则称现的个体变元,则称现的个体变元,则称现的个体变元,则称A A为封闭的合式公式,简称闭式。为封闭的合式公式,简称闭式。为封闭的合式公式,简称闭式。为封闭的合式公式,简称闭式。由闭式定义可知,闭式中所有个体变元均为约束由闭式定义可知,闭式中所有个体变元均为约束由闭式定义可知,闭式中所有个体变元均为约束由闭式定义可知,闭式中所有个体变元均为约束出现。出现。出现。出现。例如,例如,例如,例如,( ( x x)( )(P P( (x x) )Q Q( (x x) )和和和和( ( x x)(
56、 )( y y)( )(P P( (x x) ) Q Q( (x x, ,y y) )是闭式,而是闭式,而是闭式,而是闭式,而( ( x x)( )(P P( (x x) )Q Q( (x x, ,y y) )和和和和( ( y y)( )( z z) )L L( (x x, ,y y, ,z z) )不是闭式。不是闭式。不是闭式。不是闭式。从下面讨论可以看出,在一公式中,有的个体变从下面讨论可以看出,在一公式中,有的个体变从下面讨论可以看出,在一公式中,有的个体变从下面讨论可以看出,在一公式中,有的个体变元既可以是约束出现,又可以是自由出现,这就容易产元既可以是约束出现,又可以是自由出现,这
57、就容易产元既可以是约束出现,又可以是自由出现,这就容易产元既可以是约束出现,又可以是自由出现,这就容易产生混淆。为了避免混淆,采用下面两个规则:生混淆。为了避免混淆,采用下面两个规则:生混淆。为了避免混淆,采用下面两个规则:生混淆。为了避免混淆,采用下面两个规则:约束变元换名规则,将量词辖域中某个约束出约束变元换名规则,将量词辖域中某个约束出约束变元换名规则,将量词辖域中某个约束出约束变元换名规则,将量词辖域中某个约束出现的个体变元及相应指导变元,改成本辖域中未曾出现现的个体变元及相应指导变元,改成本辖域中未曾出现现的个体变元及相应指导变元,改成本辖域中未曾出现现的个体变元及相应指导变元,改成
58、本辖域中未曾出现过的个体变元,其余不变。过的个体变元,其余不变。过的个体变元,其余不变。过的个体变元,其余不变。自由变元代替规则,对某自由出现的个体变元自由变元代替规则,对某自由出现的个体变元自由变元代替规则,对某自由出现的个体变元自由变元代替规则,对某自由出现的个体变元可用个体常元或与原子公式中所有个体变元不同的个体可用个体常元或与原子公式中所有个体变元不同的个体可用个体常元或与原子公式中所有个体变元不同的个体可用个体常元或与原子公式中所有个体变元不同的个体变元去代替,且处处代替。变元去代替,且处处代替。变元去代替,且处处代替。变元去代替,且处处代替。换换换换名名名名规规规规则则则则与与与与
59、代代代代替替替替规规规规则则则则的的的的共共共共同同同同点点点点都都都都是是是是不不不不能能能能改改改改变变变变约约约约束束束束关系,而不同点是:关系,而不同点是:关系,而不同点是:关系,而不同点是: 施施施施行行行行的的的的对对对对象象象象不不不不同同同同。换换换换名名名名是是是是对对对对约约约约束束束束变变变变元元元元施施施施行行行行,代代代代替是对自由变元施行。替是对自由变元施行。替是对自由变元施行。替是对自由变元施行。 施施施施行行行行的的的的范范范范围围围围不不不不同同同同。换换换换名名名名可可可可以以以以只只只只对对对对公公公公式式式式中中中中一一一一个个个个量量量量词词词词及及及
60、及其其其其辖辖辖辖域域域域内内内内施施施施行行行行,即即即即只只只只对对对对公公公公式式式式的的的的一一一一个个个个子子子子公公公公式式式式施施施施行行行行;而而而而代代代代替替替替必必必必须须须须对对对对整整整整个个个个公公公公式式式式同同同同一一一一个个个个自自自自由由由由变变变变元元元元的的的的所所所所有有有有自自自自由由由由出出出出现现现现同同同同时施行,即必须对整个公式施行。时施行,即必须对整个公式施行。时施行,即必须对整个公式施行。时施行,即必须对整个公式施行。例:例:例:例: x x y y ( ( R R( (x x, ,y y) ) L L( (y y, ,z z) ) )
61、) xHxH( (x x, ,y y) )换换换换 名名名名 和和和和 代代代代 替替替替 为为为为 : x x y y ( ( R R( (x x, ,y y) ) L L( (y y, ,z z) ) ) ) tHtH( (t t, ,w w) ) 施行后的结果不同。换名后,公式含义不变,施行后的结果不同。换名后,公式含义不变,施行后的结果不同。换名后,公式含义不变,施行后的结果不同。换名后,公式含义不变,因为约束变元只改名为另一个个体变元,约束关系不改因为约束变元只改名为另一个个体变元,约束关系不改因为约束变元只改名为另一个个体变元,约束关系不改因为约束变元只改名为另一个个体变元,约束关
62、系不改变。约束变元不能改名为个体常元;代替,不仅可用另变。约束变元不能改名为个体常元;代替,不仅可用另变。约束变元不能改名为个体常元;代替,不仅可用另变。约束变元不能改名为个体常元;代替,不仅可用另一个个体变元进行代替,并且也可用个体常元去代替,一个个体变元进行代替,并且也可用个体常元去代替,一个个体变元进行代替,并且也可用个体常元去代替,一个个体变元进行代替,并且也可用个体常元去代替,从而使公式由具有普遍意义变为仅对该个体常元有意义,从而使公式由具有普遍意义变为仅对该个体常元有意义,从而使公式由具有普遍意义变为仅对该个体常元有意义,从而使公式由具有普遍意义变为仅对该个体常元有意义,即公式的含
63、义改变了。即公式的含义改变了。即公式的含义改变了。即公式的含义改变了。2.4 公式解释与类型公式解释与类型1公式解释公式解释一一一一般般般般情情情情况况况况下下下下,LpLp中中中中的的的的公公公公式式式式含含含含有有有有:个个个个体体体体常常常常元元元元、个个个个体体体体变变变变元元元元(约约约约束束束束变变变变元元元元或或或或自自自自由由由由变变变变元元元元)、函函函函数数数数变变变变元元元元、为为为为谓谓谓谓词词词词变变变变元元元元等等等等,对对对对各各各各种种种种变变变变元元元元用用用用指指指指定定定定的的的的特特特特殊殊殊殊常常常常元元元元去去去去代代代代替替替替,就就就就构构构构成
64、成成成了了了了一一一一个个个个公公公公式式式式的的的的解解解解释释释释。当当当当然然然然在在在在给给给给定定定定的的的的解解解解释释释释下下下下,可可可可以以以以对对对对多多多多个个个个公公公公式式式式进进进进行行行行解解解解释释释释。下下下下面面面面给出解释的一般定义。给出解释的一般定义。给出解释的一般定义。给出解释的一般定义。定义定义定义定义2.4.12.4.1 一个解释一个解释一个解释一个解释I I由下面由下面由下面由下面4 4部分组成:部分组成:部分组成:部分组成: 非空个体域非空个体域非空个体域非空个体域D DI I。 D DI I中部分特定元素中部分特定元素中部分特定元素中部分特定
65、元素a a ,b b ,。 D DI I上的特定一些函数上的特定一些函数上的特定一些函数上的特定一些函数f f ,g g ,。 D DI I上特定谓词:上特定谓词:上特定谓词:上特定谓词:P P ,Q Q ,。在一个具体解释中,个体常元、函数符号、在一个具体解释中,个体常元、函数符号、在一个具体解释中,个体常元、函数符号、在一个具体解释中,个体常元、函数符号、谓词符号的数量一般是有限的,并且其解释一谓词符号的数量一般是有限的,并且其解释一谓词符号的数量一般是有限的,并且其解释一谓词符号的数量一般是有限的,并且其解释一旦确定下来就不再改变,只是个体变元的值在旦确定下来就不再改变,只是个体变元的值
66、在旦确定下来就不再改变,只是个体变元的值在旦确定下来就不再改变,只是个体变元的值在个体域个体域个体域个体域D DI I内变化,量词符内变化,量词符内变化,量词符内变化,量词符 或或或或 仅作用于仅作用于仅作用于仅作用于D DI I中的中的中的中的元素。元素。元素。元素。2公式类型公式类型定定定定义义义义2.4.22.4.2 若若若若一一一一公公公公式式式式在在在在任任任任何何何何解解解解释释释释下下下下都都都都是是是是真的,称该公式为逻辑有效的,或永真的。真的,称该公式为逻辑有效的,或永真的。真的,称该公式为逻辑有效的,或永真的。真的,称该公式为逻辑有效的,或永真的。 若若若若一一一一公公公公
67、式式式式在在在在任任任任何何何何解解解解释释释释下下下下都都都都是是是是假假假假的的的的,称称称称该该该该公式为矛盾式,或永假式。公式为矛盾式,或永假式。公式为矛盾式,或永假式。公式为矛盾式,或永假式。 若若若若一一一一公公公公式式式式至至至至少少少少存存存存在在在在一一一一个个个个解解解解释释释释使使使使其其其其为为为为真真真真,称该公式为可满足式。称该公式为可满足式。称该公式为可满足式。称该公式为可满足式。从定义可知,逻辑有效式为可满足式,反从定义可知,逻辑有效式为可满足式,反从定义可知,逻辑有效式为可满足式,反从定义可知,逻辑有效式为可满足式,反之未必成立。之未必成立。之未必成立。之未必
68、成立。与命题公式中分类一样,谓词公式也分为与命题公式中分类一样,谓词公式也分为与命题公式中分类一样,谓词公式也分为与命题公式中分类一样,谓词公式也分为三种类型,即逻辑有效式(或重言式)、矛盾三种类型,即逻辑有效式(或重言式)、矛盾三种类型,即逻辑有效式(或重言式)、矛盾三种类型,即逻辑有效式(或重言式)、矛盾式(或永假式)和可满足式。式(或永假式)和可满足式。式(或永假式)和可满足式。式(或永假式)和可满足式。由于谓词公式的复杂性和解释的多样性,至今还没有由于谓词公式的复杂性和解释的多样性,至今还没有由于谓词公式的复杂性和解释的多样性,至今还没有由于谓词公式的复杂性和解释的多样性,至今还没有一
69、个可行的算法判定任何公式的类型。早在一个可行的算法判定任何公式的类型。早在一个可行的算法判定任何公式的类型。早在一个可行的算法判定任何公式的类型。早在19361936年,年,年,年,ChurenChuren和和和和TuringTuring各自独立地证明了:对于各自独立地证明了:对于各自独立地证明了:对于各自独立地证明了:对于LpLp,其判定问题,其判定问题,其判定问题,其判定问题是不可解的。但是,是不可解的。但是,是不可解的。但是,是不可解的。但是,LpLp是个半个可判定的,即若是个半个可判定的,即若是个半个可判定的,即若是个半个可判定的,即若LpLp中公式中公式中公式中公式是重言式,则存在算
70、法在有限步骤内能验证它。当然,对是重言式,则存在算法在有限步骤内能验证它。当然,对是重言式,则存在算法在有限步骤内能验证它。当然,对是重言式,则存在算法在有限步骤内能验证它。当然,对于一些较为简单的公式,或某些特殊公式,还是可以判定于一些较为简单的公式,或某些特殊公式,还是可以判定于一些较为简单的公式,或某些特殊公式,还是可以判定于一些较为简单的公式,或某些特殊公式,还是可以判定其类型的。其类型的。其类型的。其类型的。例如,如果一个谓词公式是命题公式中的重言式的代例如,如果一个谓词公式是命题公式中的重言式的代例如,如果一个谓词公式是命题公式中的重言式的代例如,如果一个谓词公式是命题公式中的重言
71、式的代换实例,则这个谓词公式是换实例,则这个谓词公式是换实例,则这个谓词公式是换实例,则这个谓词公式是逻辑有效式(或重言式)。逻辑有效式(或重言式)。逻辑有效式(或重言式)。逻辑有效式(或重言式)。见教材见教材见教材见教材P44 P44 P44 P44 例例例例2 2 2 2.9 .92.5 等价式与蕴涵式等价式与蕴涵式1等价式等价式定定定定义义义义2.5.12.5.1 设设设设A A、B B为为为为任任任任意意意意两两两两个个个个公公公公式式式式,若若若若A AB B为为为为逻逻逻逻辑辑辑辑有有有有效效效效的的的的,则则则则称称称称A A与与与与B B是是是是等等等等价价价价的的的的,记记记
72、记为为为为A AB B,称,称,称,称A AB B为等价式。为等价式。为等价式。为等价式。由由由由于于于于重重重重言言言言式式式式( (永永永永真真真真式式式式) )都都都都是是是是逻逻逻逻辑辑辑辑有有有有效效效效的的的的,可可可可见见见见1.31.3节节节节中中中中的的的的命命命命题题题题定定定定律律律律(基基基基本本本本等等等等价价价价式式式式)都都都都是是是是Lp Lp 等等等等价价价价式。式。式。式。此外,还有一置换规则:此外,还有一置换规则:此外,还有一置换规则:此外,还有一置换规则:设设设设 ( (A A) )是含有是含有是含有是含有A A出现的公式,出现的公式,出现的公式,出现的
73、公式, ( (B B) )是用公式是用公式是用公式是用公式B B替换若干个公式替换若干个公式替换若干个公式替换若干个公式A A的结果。若的结果。若的结果。若的结果。若A AB B,则,则,则,则 ( (A A) ) ( (B B) )。显然,若显然,若显然,若显然,若 ( (A A) )为重言式,则为重言式,则为重言式,则为重言式,则 ( (B B) )也是重言也是重言也是重言也是重言式。式。式。式。下面给出涉及量词的一些等值式。下面给出涉及量词的一些等值式。下面给出涉及量词的一些等值式。下面给出涉及量词的一些等值式。(1) (1) 量词否定等值式(量词可互相转化):量词否定等值式(量词可互相
74、转化):量词否定等值式(量词可互相转化):量词否定等值式(量词可互相转化):( (a a) ) ( ( x x) )A A( ( x x) ) A A( (b b) ) ( ( x x) )A A( ( x x) ) A A这两个等值式,可用量词的定义给予说明。这两个等值式,可用量词的定义给予说明。这两个等值式,可用量词的定义给予说明。这两个等值式,可用量词的定义给予说明。由于由于由于由于“ “并非对一切并非对一切并非对一切并非对一切x x,A A为真为真为真为真” ”等价于等价于等价于等价于“ “存在一些存在一些存在一些存在一些x x, A A为真为真为真为真” ”,故,故,故,故( (a
75、a) )成立。成立。成立。成立。由于由于由于由于“ “不存在一些不存在一些不存在一些不存在一些x x,A A为真为真为真为真” ”等价于等价于等价于等价于“ “对一切对一切对一切对一切x x, A A为真为真为真为真” ”,所以,所以,所以,所以( (b b) )成立。成立。成立。成立。这两个等值式的意义是:否定联结词可通过量词这两个等值式的意义是:否定联结词可通过量词这两个等值式的意义是:否定联结词可通过量词这两个等值式的意义是:否定联结词可通过量词深入到辖域中。对比这两个式子,容易看出,将深入到辖域中。对比这两个式子,容易看出,将深入到辖域中。对比这两个式子,容易看出,将深入到辖域中。对比
76、这两个式子,容易看出,将( ( x x) )与与与与( ( x x) )两者互换,可从一个式子得到另一个式子,这两者互换,可从一个式子得到另一个式子,这两者互换,可从一个式子得到另一个式子,这两者互换,可从一个式子得到另一个式子,这表明表明表明表明( ( x x) )与与与与( ( x x) )具有对偶性。另外,由于这两个公式具有对偶性。另外,由于这两个公式具有对偶性。另外,由于这两个公式具有对偶性。另外,由于这两个公式成立也表明了,两个量词是不独立的,可以互相表示,成立也表明了,两个量词是不独立的,可以互相表示,成立也表明了,两个量词是不独立的,可以互相表示,成立也表明了,两个量词是不独立的
77、,可以互相表示,所以只有一个量词就够了。所以只有一个量词就够了。所以只有一个量词就够了。所以只有一个量词就够了。对于多重量词前置对于多重量词前置对于多重量词前置对于多重量词前置“ “ ” ”,可反复应用上面结果,逐,可反复应用上面结果,逐,可反复应用上面结果,逐,可反复应用上面结果,逐次右移次右移次右移次右移 。例如,。例如,。例如,。例如, ( ( x x)( )( y y)( )( z z) )P P( (x x, ,y y, ,z z) )( ( x x)( )( y y)( )( z z) ) P P( (x x, ,y y, ,z z) )(2 2) 量词辖域缩小或扩大等值式量词辖域
78、缩小或扩大等值式量词辖域缩小或扩大等值式量词辖域缩小或扩大等值式设设设设B B是不含是不含是不含是不含x x自由出现,自由出现,自由出现,自由出现,A A( (x x) )为有为有为有为有x x自由出现的任意自由出现的任意自由出现的任意自由出现的任意公式,则有:公式,则有:公式,则有:公式,则有:( (a a) () ( x x)( )(A A( (x x) )B B) )( ( x x) )A A( (x x) )B B ( (b b) () ( x x)( )(A A( (x x) )B B) )( ( x x) )A A( (x x) )B B( (c c) () ( x x)( )(A
79、 A( (x x)B B) )( ( x x) )A A( (x x)B B( (d d) () ( x x)( )(B BA A( (x x) )B B( x x) )A A( (x x) )( (e e) () ( x x)( )(A A( (x x) )B B) )( ( x x) )A A( (x x) )B B( (f f) () ( x x)( )(A A( (x x) )B B) )( ( x x) )A A( (x x) )B B ( (g g) () ( x x)( )(A A( (x x)B B) )( ( x x) )A A( (x x)B B( (h h) () ( x
80、 x)( )(B BA A( (x x) )B B( x x) )A A( (x x) )。运用运用运用运用( (c c) ) 、 ( (g g) )时要小心!时要小心!时要小心!时要小心! (3) (3) 量词分配律等值式:量词分配律等值式:量词分配律等值式:量词分配律等值式:( (a a) () ( x x)( )(A A( (x x) )B B( (x x) )( ( x x) )A A( (x x) )( ( x x) )B B( (x x) )( (b b) () ( x x)( )(A A( (x x) )B B( (x x) )( ( x x) )A A( (x x) )( (
81、x x) )B B( (x x) )其中,其中,其中,其中,A A( (x x) ),B B( (x x) )为有为有为有为有x x自由出现的任何公式。自由出现的任何公式。自由出现的任何公式。自由出现的任何公式。(4) (4) 多重量词等值式多重量词等值式多重量词等值式多重量词等值式( (a a) () ( x x)( )( y y) )A A( (x x, ,y y) )( ( y y)( )( x x) )A A( (x x, ,y y) )( (b b) () ( x x)( )( y y) )A A( (x x, ,y y) )( ( y y)( )( x x) )A A( (x x,
82、 ,y y) )其中其中其中其中A A( (x x, ,y y) )为含有为含有为含有为含有x x, y y自由出现的任意公式。自由出现的任意公式。自由出现的任意公式。自由出现的任意公式。2. 2. 蕴涵式蕴涵式蕴涵式蕴涵式由由由由于于于于LsLs中中中中蕴蕴蕴蕴涵涵涵涵式式式式(或或或或永永永永真真真真条条条条件件件件式式式式)在在在在LpLp中中中中都都都都是是是是逻逻逻逻辑辑辑辑有有有有效效效效的的的的,而而而而且且且且使使使使用用用用代代代代入入入入规规规规则则则则得得得得到到到到蕴蕴蕴蕴涵涵涵涵式式式式也也也也都都都都是是是是LpLp中中中中逻逻逻逻辑有效的。辑有效的。辑有效的。辑有
83、效的。例例例例如如如如:( ( x x) )P P( (x x) )( ( x x) )P P( (x x) )( ( y y) )Q Q( (y y) ) 附加附加附加附加( ( x x) )P P( (x x)Q Q( (x x, ,y y) )( ( x x) )P P( (x x) ) Q Q( (x x, ,y y) ) 假言推理假言推理假言推理假言推理下面将给出下面将给出下面将给出下面将给出LpLp中的一些蕴涵式。中的一些蕴涵式。中的一些蕴涵式。中的一些蕴涵式。(1) (1) ( (a a)( )( x x) )A A( (x x) )( ( x x) )B B( (x x) )(
84、 ( x x)( )(A A( (x x) )B B( (x x) )( (b b) ) ( ( x x)( )(A A( (x x) )B B( (x x) )( ( x x) )A A( (x x) )( ( x x) )B B( (x x) )( (c c) ) ( ( x x)( )(A A( (x x)B B( (x x) )( ( x x) )A A( (x x)()( x x) )B B( (x x) )( (d d) ) ( ( x x)( )(A A( (x x)B B( (x x) )( ( x x) )A A( (x x)()( x x) )B B( (x x) )其中,
85、其中,其中,其中,A A( (x x) )和和和和B B( (x x) )为含有为含有为含有为含有x x自由出现的任意自由出现的任意自由出现的任意自由出现的任意公式。公式。公式。公式。2.6 谓词公式范式谓词公式范式.前束范式前束范式定定定定义义义义2.9.12.9.1 一一一一个个个个合合合合式式式式公公公公式式式式称称称称为为为为前前前前束束束束范范范范式式式式,如如如如果它有如下形式:果它有如下形式:果它有如下形式:果它有如下形式:( (Q Q1 1x x1 1)( )(Q Q2 2x x2 2)()(Q Qk kx xk k) )B B其其其其中中中中Q Qi i(1(1i i k k
86、) )为为为为 或或或或 ,B B为为为为不不不不含含含含有有有有量量量量词词词词的的的的公式。称公式。称公式。称公式。称Q Q1 1x x1 1Q Q2 2x x2 2Q Qk kx xk k为公式的首标。为公式的首标。为公式的首标。为公式的首标。特特特特别别别别地地地地,若若若若中中中中无无无无量量量量词词词词,则则则则也也也也看看看看作作作作是是是是前前前前束范式。束范式。束范式。束范式。可见,前束范式的特点是,所有量词均非否定地可见,前束范式的特点是,所有量词均非否定地可见,前束范式的特点是,所有量词均非否定地可见,前束范式的特点是,所有量词均非否定地出现在公式最前面,且它的辖域一直延
87、伸到公式之末。出现在公式最前面,且它的辖域一直延伸到公式之末。出现在公式最前面,且它的辖域一直延伸到公式之末。出现在公式最前面,且它的辖域一直延伸到公式之末。例如,例如,例如,例如,( ( x x)( )( y y)( )(P P( (x x, ,y y) )Q Q( (y y, ,z z), ), R R( (x x, ,y y) )等都是前等都是前等都是前等都是前束范式,而束范式,而束范式,而束范式,而( ( x x) )P P( (x x) ) ( ( y y) )Q Q( (y y) ),( ( x x)( )(P P( (x x) )( ( y y) )Q Q( (x x, ,y y
88、) )不是前束范式。不是前束范式。不是前束范式。不是前束范式。定理定理定理定理2.6.12.6.1 ( (前束范式存在定理前束范式存在定理前束范式存在定理前束范式存在定理) ) Lp Lp中任意公式中任意公式中任意公式中任意公式A A都都都都有有有有与之等价与之等价与之等价与之等价的前束范式。的前束范式。的前束范式。的前束范式。本教材转化前束范式原则:能不换名就不换!本教材转化前束范式原则:能不换名就不换!本教材转化前束范式原则:能不换名就不换!本教材转化前束范式原则:能不换名就不换!见教材见教材见教材见教材P47 P47 例例例例2 2 2 2.11.11求公式的前束范式求公式的前束范式(1
89、 1 1 1) x x( (F F( (x x)G G( (x x) ) x H x H ( (x, yx, y) )(2 2) ( ( x Fx F( (x, yx, y) ) y Gy G( (y y) ) ) ) x H x H ( (x, yx, y) )( (例例例例2 2 2 2.20, .20, 例例例例2 2 2 2.11(5).11(5)2.7 谓词逻辑的推理理论谓词逻辑的推理理论LpLp是是是是LsLs的的的的进进进进一一一一步步步步深深深深化化化化和和和和发发发发展展展展,因因因因此此此此LsLs的的的的推推推推理理理理理理理理论论论论在在在在LpLp中中中中几几几几乎乎
90、乎乎可可可可以以以以完完完完全全全全照照照照搬搬搬搬,只只只只不不不不过过过过这这这这时时时时涉涉涉涉及及及及的的的的公公公公式式式式是是是是LpLp的的的的公公公公式式式式罢罢罢罢了了了了。在在在在LpLp中中中中,某某某某些些些些前前前前提提提提和和和和结结结结论论论论可可可可能能能能受受受受到到到到量量量量词词词词的的的的约约约约束束束束,为为为为确确确确立立立立前前前前提提提提和和和和结结结结论论论论之之之之间间间间的的的的内内内内部部部部联联联联系系系系,有有有有必必必必要要要要消消消消去去去去量量量量词词词词和和和和添添添添加加加加量量量量词词词词,因因因因此此此此正正正正确确确确
91、理理理理解解解解和和和和运运运运用用用用有有有有关关关关量量量量词词词词消消消消去去去去和和和和添添添添加规则是加规则是加规则是加规则是LpLp推理理论中十分重要的关键所在推理理论中十分重要的关键所在推理理论中十分重要的关键所在推理理论中十分重要的关键所在。在一阶逻辑中,推理的形式结构仍为:在一阶逻辑中,推理的形式结构仍为:在一阶逻辑中,推理的形式结构仍为:在一阶逻辑中,推理的形式结构仍为:若若若若( (HH1 1HH2 2HHn n)C C是逻辑有效式,则是逻辑有效式,则是逻辑有效式,则是逻辑有效式,则称称称称C C是是是是HH1 1,HH2 2,HHn n的逻辑结论,记为的逻辑结论,记为的
92、逻辑结论,记为的逻辑结论,记为 ( (HH1 1HH2 2HHn n) )C C除命题逻辑的除命题逻辑的除命题逻辑的除命题逻辑的1111条规则外,加上前面证明的:条规则外,加上前面证明的:条规则外,加上前面证明的:条规则外,加上前面证明的:( (a a)( )( x x) )A A( (x x) )( ( x x) )B B( (x x) )( ( x x)( )(A A( (x x) )B B( (x x) )( (b b) ) ( ( x x)( )(A A( (x x) )B B( (x x) )( ( x x) )A A( (x x) )( ( x x) )B B( (x x) )(
93、(c c) () ( x x)( )(A A( (x x)B B( (x x) )( ( x x) )A A( (x x)()( x x) )B B( (x x) )( (d d) () ( x x)( )(A A( (x x)B B( (x x) )( ( x x) )A A( (x x)()( x x) )B B( (x x) ).有关量词消去和产生规则有关量词消去和产生规则还要用到以下还要用到以下还要用到以下还要用到以下4 4条推理规则条推理规则条推理规则条推理规则注意:其中注意:其中注意:其中注意:其中A A B B不一定表示不一定表示不一定表示不一定表示A BA B是逻是逻是逻是逻辑
94、有效式,而只表示在一定条件下,当辑有效式,而只表示在一定条件下,当辑有效式,而只表示在一定条件下,当辑有效式,而只表示在一定条件下,当A A为真时,为真时,为真时,为真时,B B也为真的推理关系。也为真的推理关系。也为真的推理关系。也为真的推理关系。(1)全称量词消去规则全称量词消去规则(2)(简称简称UI或或US规则,规则, - -)有两种形式:有两种形式:有两种形式:有两种形式:( ( x x) )A A( (x x) )A A( (c c) ) ( ( x x) )A A( (x x) )A A( (y y) ) 成立充分条件是:成立充分条件是:成立充分条件是:成立充分条件是: c c为
95、论域中任意个体常为论域中任意个体常为论域中任意个体常为论域中任意个体常项,项,项,项, y y为论域中任一个体为论域中任一个体为论域中任一个体为论域中任一个体 ; x x 在在在在A A( (x x) )中是中是中是中是自由出自由出自由出自由出现的;现的;现的;现的; y y为任意的不在为任意的不在为任意的不在为任意的不在A A( (x x) )中约束出现的个体变中约束出现的个体变中约束出现的个体变中约束出现的个体变项。项。项。项。(2) 存在量词消去规则存在量词消去规则 (简称简称EI或或ES规则,规则, - -) ( ( x x) )A A( (x x) )A A( (c c) ) 成成成
96、成立立立立充充充充分分分分条条条条件件件件是是是是:c c是是是是使使使使A A为为为为真真真真的的的的特特特特定定定定个个个个体体体体常常常常项项项项; c c不不不不曾曾曾曾在在在在A A( (x x) )中中中中出出出出现现现现过过过过; 若若若若A A( (x x) )中中中中有有有有其其其其它自由变项时,不能应用本规则。它自由变项时,不能应用本规则。它自由变项时,不能应用本规则。它自由变项时,不能应用本规则。(3) (3) 全称量词产生规则全称量词产生规则全称量词产生规则全称量词产生规则 ( (简称简称简称简称UGUG规则,规则,规则,规则, + + + +) ) A A( (y y
97、) )( ( x x) )A A( (x x) )成成成成立立立立条条条条件件件件: y y在在在在A A( (y y) )中中中中自自自自由由由由出出出出现现现现,且且且且y y取取取取任任任任何何何何值值值值时时时时A A均均均均为为为为真真真真;取取取取代代代代y y的的的的x x不不不不能能能能在在在在A A( (y y) )中中中中约约约约束束束束出出出出现现现现; A A( (y y) )中中中中含含含含有有有有个个个个体体体体常常常常项项项项时时时时,要要要要小小小小心心心心使使使使用。用。用。用。(4) 存在量词产生规则存在量词产生规则 (简称简称EG规则,规则, + +) A
98、 A( (c c) )( ( x x) )A A( (x x) ) 成立充分条件:成立充分条件:成立充分条件:成立充分条件: c c是特定的个体常项;是特定的个体常项;是特定的个体常项;是特定的个体常项; 取代取代取代取代c c的个体变元的个体变元的个体变元的个体变元x x不能已在不能已在不能已在不能已在A A( (c c) )中出现过。中出现过。中出现过。中出现过。错在哪里(错在哪里(P53 例例2.18)?)?(1 1) x x( (F F( (x x)G G( (x x) P) P(2 2) F F( (y y)G G( (y y) ) (1 1)UIUI(3 3) x Fx F( (x
99、 x) P) P(4 4) F F( (y y) ) (3 3)EIEI(5 5) G G( (y y) ) (2 2)()()()(4 4)假言推理)假言推理)假言推理)假言推理(6 6) x Gx G( (x x) ) (5 5)UGUG错在哪里(错在哪里(P53 例例2.18) ?(1 1) x x y Fy F( (x, yx, y) P) P(2 2) y Fy F( (z, yz, y) ) (1 1)UIUI(3 3) F F( (z, cz, c) ) (2 2)EIEI(4 4) x Fx F( (x, cx, c) ) (3 3)UGUG(5 5) y y x Fx F(
100、(x, yx, y) ) (4 4)EGEG错在哪里(错在哪里(P57 习题习题2.16) ?(1 1) x Fx F( (x x)G G( (x x) ) 前提引入前提引入前提引入前提引入 F F( (y y)G G( (y y) ) UI UI(2 2) x x ( ( F F( (x x) ) G G( (x x) ) ) ) 前提引入前提引入前提引入前提引入 F F(a) (a) G G(b) (b) UI UI(3 3) F F( (x x)G G( (x x) ) 前提引入前提引入前提引入前提引入 y (Fy (F( (y y)G G( (y y) ) EG EG(4 4) F F
101、( (x x)G G( (c c) ) 前提引入前提引入前提引入前提引入 x (Fx (F( (x x)G G( (x x) ) EG EG(5 5) F F(a)(a)G G(b) (b) 前提引入前提引入前提引入前提引入 x (Fx (F( (x x)G G( (x x) ) EG EG错在哪里(错在哪里(P57 习题习题2.16) ?(6)(6) x (Fx (F( (x x) ) G G( (x x) ) 前提引入前提引入前提引入前提引入 y y y y (H (H(y) (y) R R(y) (y) 前提引入前提引入前提引入前提引入 F F(c) (c) G G(c) (c) EIE
102、IEIEI F F(c) (c) 化简化简化简化简 HH(c) (c) R R(c) (c) EIEIEIEI HH(c) (c) 化简化简化简化简 F F(c) (c) HH(c) (c) 合取合取合取合取 x (Fx (F( (x x) ) HH( (x x) ) ) ) EGEGEGEG注意!注意!一定对前束范式消量词,对不一定对前束范式消量词,对不是前束范式的公式,一定要先化成是前束范式的公式,一定要先化成前束范式再消量词。前束范式再消量词。Lp中推理实例中推理实例LpLp的推理方法是的推理方法是的推理方法是的推理方法是LsLs推理方法的扩展,因此推理方法的扩展,因此推理方法的扩展,因
103、此推理方法的扩展,因此在在在在LpLp中利用的推理规则也是中利用的推理规则也是中利用的推理规则也是中利用的推理规则也是T T规则、规则、规则、规则、P P规则和规则和规则和规则和CPCP规则,还有已知的等值式,蕴涵式以及有关量规则,还有已知的等值式,蕴涵式以及有关量规则,还有已知的等值式,蕴涵式以及有关量规则,还有已知的等值式,蕴涵式以及有关量词的消去和产生规则。使用的推理方法是直接词的消去和产生规则。使用的推理方法是直接词的消去和产生规则。使用的推理方法是直接词的消去和产生规则。使用的推理方法是直接构造法和间接证法。构造法和间接证法。构造法和间接证法。构造法和间接证法。例例例例 试证明下面苏
104、格拉底论证:试证明下面苏格拉底论证:试证明下面苏格拉底论证:试证明下面苏格拉底论证:所有人都是要死的,所有人都是要死的,所有人都是要死的,所有人都是要死的,苏格拉底是人,苏格拉底是人,苏格拉底是人,苏格拉底是人,因此,苏格拉底是要死的。因此,苏格拉底是要死的。因此,苏格拉底是要死的。因此,苏格拉底是要死的。证明证明证明证明 令令令令MM( (x x): ):x x是人,是人,是人,是人,D D( (x x): ):x x是要死的,是要死的,是要死的,是要死的, s s: :苏格拉底,苏格拉底,苏格拉底,苏格拉底,原题可符号化为:原题可符号化为:原题可符号化为:原题可符号化为: ( ( x x)
105、( )(MM( (x x) )D D( (x x) ),MM( (s s) )D D( (s s) )推证如下:推证如下:推证如下:推证如下: (1 1) ( ( x x)( )(MM( (x x) )D D( (x x) ) 前提引入前提引入前提引入前提引入 (2 2) MM( (s s) )D D( (s s) (1) (1)UIUI (3 3) MM( (s s) ) 前提引入前提引入前提引入前提引入 (4 4) D D( (s s) (2)(3) (2)(3)假言推理假言推理假言推理假言推理例例 证明永真式证明永真式 x(A(x) B(x) ) ( x A(x) x B(x) )例例
106、构造推理构造推理前提:前提: x P(x) x(P(x) Q(x) R(x) x P(x)结论:结论: x y(R(x) R(y)例例 证明结论是否有效证明结论是否有效有的病人喜欢所有的医生,没有一有的病人喜欢所有的医生,没有一个病人喜欢某一庸医,所以没有医生是个病人喜欢某一庸医,所以没有医生是庸医。庸医。改做习题改做习题2.23每个喜欢步行的人都不喜欢坐汽车。每个每个喜欢步行的人都不喜欢坐汽车。每个每个喜欢步行的人都不喜欢坐汽车。每个每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人人或者喜欢坐汽车或者喜欢骑自行车。有的人人或者喜欢坐汽车或者喜欢骑自行车。有的人人或
107、者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。不喜欢骑自行车。因而有的人不喜欢步行。不喜欢骑自行车。因而有的人不喜欢步行。不喜欢骑自行车。因而有的人不喜欢步行。(个体域为全总域个体域为全总域个体域为全总域个体域为全总域)定义:定义:定义:定义: F F( (x x) ): x x喜欢步行;喜欢步行;喜欢步行;喜欢步行;G (G (x x) ):x x喜欢坐喜欢坐喜欢坐喜欢坐汽车;汽车;汽车;汽车; H ( H (x x) ): x x 喜欢骑自行车;喜欢骑自行车;喜欢骑自行车;喜欢骑自行车;M (M (x x) ): x x是人是人是人是人 数理逻辑知识点数理逻辑知
108、识点一、命题逻辑:一、命题逻辑:一、命题逻辑:一、命题逻辑:掌握技能掌握技能掌握技能掌握技能:自然语言符号化,命题公式化:自然语言符号化,命题公式化:自然语言符号化,命题公式化:自然语言符号化,命题公式化简简简简/ /等值演算,命题公式判定(真值表法、等值等值演算,命题公式判定(真值表法、等值等值演算,命题公式判定(真值表法、等值等值演算,命题公式判定(真值表法、等值演算、范式法),构造推理演算、范式法),构造推理演算、范式法),构造推理演算、范式法),构造推理/ /永真式证明。永真式证明。永真式证明。永真式证明。概念辨析概念辨析概念辨析概念辨析:命题,真值,真值表,赋值:命题,真值,真值表,
109、赋值:命题,真值,真值表,赋值:命题,真值,真值表,赋值/ /解解解解释释释释/ /指派,合式公式,永真指派,合式公式,永真指派,合式公式,永真指派,合式公式,永真/ /重言式,永假重言式,永假重言式,永假重言式,永假/ /矛盾矛盾矛盾矛盾式,可满足式,对偶式,极小全功能联接词组式,可满足式,对偶式,极小全功能联接词组式,可满足式,对偶式,极小全功能联接词组式,可满足式,对偶式,极小全功能联接词组/ /集合,极大项,极小项,有效结论。集合,极大项,极小项,有效结论。集合,极大项,极小项,有效结论。集合,极大项,极小项,有效结论。记忆记忆记忆记忆:基本的等值式,基本的推理规则。:基本的等值式,基
110、本的推理规则。:基本的等值式,基本的推理规则。:基本的等值式,基本的推理规则。二、一阶逻辑:二、一阶逻辑:二、一阶逻辑:二、一阶逻辑:掌握技能掌握技能掌握技能掌握技能:自然语言符号化,构造解释求:自然语言符号化,构造解释求:自然语言符号化,构造解释求:自然语言符号化,构造解释求谓词公式的值,谓词公式判定(利用命题逻辑谓词公式的值,谓词公式判定(利用命题逻辑谓词公式的值,谓词公式判定(利用命题逻辑谓词公式的值,谓词公式判定(利用命题逻辑中重言式的代换实例),求前束范式,构造推中重言式的代换实例),求前束范式,构造推中重言式的代换实例),求前束范式,构造推中重言式的代换实例),求前束范式,构造推理
111、。理。理。理。概念辨析概念辨析概念辨析概念辨析:谓词,个体,量词,个体域:谓词,个体,量词,个体域:谓词,个体,量词,个体域:谓词,个体,量词,个体域/ /论论论论域域域域/ /全总域,项,合式公式,解释,辖域,自由全总域,项,合式公式,解释,辖域,自由全总域,项,合式公式,解释,辖域,自由全总域,项,合式公式,解释,辖域,自由变项变项变项变项/ /元,约束变项元,约束变项元,约束变项元,约束变项/ /元,换名,代替。元,换名,代替。元,换名,代替。元,换名,代替。记忆记忆记忆记忆:量词转换等值式,量词辖域扩充:量词转换等值式,量词辖域扩充:量词转换等值式,量词辖域扩充:量词转换等值式,量词辖域扩充/ /收收收收缩的等值式、重言蕴涵式,量词的添加缩的等值式、重言蕴涵式,量词的添加缩的等值式、重言蕴涵式,量词的添加缩的等值式、重言蕴涵式,量词的添加/ /消去规消去规消去规消去规则。则。则。则。