数理逻辑与集合论：4-1 谓词逻辑的基本概念

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是人。是人