数理逻辑4-1 3 谓词逻辑-1

1、数理逻辑 Mathematical Logic,第一章 逻辑、集合和函数 Chapter 1 Logic、set and function,复习,逻辑等价 p q是永真式 基本的逻辑等价关系 恒等律、幂等律、支配律、双非律、吸收律、交换律、结合律、分配律、德摩根律、补余律 常用的逻辑等价关系 p(qr) q(pr) p(qr) (pq)r (pr)(qr) (pq)r,复习,对偶 换成，换成，T 换成F，F 换成T 范式 析取范式 合取范式 消去联结词和 把否定词内移到直接作用于命题上 重复使用分配律,pq (pq)(qp) (pq)(pq),复习,证明(pq)(pq)为永真式。 (pq)(p

2、q) (pq) (pq) ( p q ) (pq) 德摩根定律 ( p p )( qq) 结合律、交换律 T T T,复习,证明(p(qr)(qr) (pr) r (p(qr)(qr) (pr) (p(qr) (q p ) r ) ( pq)r) (q p ) r ) ( (p q ) r ) (q p ) r ) ( (p q ) (p q ) ) r T r r,复习,求(pq) (pq)的析取范式。 已知(pq) (pq)的合取范式为 (pq)(pq ) (pq) p ) (pq) q ) (pp) (qp) ) (pq) (qq) ) (F (qp) ) (pq) F) (q p )

3、(p q),复习,证明(p q) ( p (q r) ) (p q) (p r)为重言式。,1.3 谓词逻辑 Predicate Logic,一、引言,x+1=3是命题吗？ 当变量x未知时，不能判断该语句的真值，既不成真也不成假。 本节课将要讲解从这类语句产生命题的方式。,二、谓词,在命题逻辑中，其基本的组成单位是原子命题，并把它看作是不可再分解的； 但是，原子命题实际上还可以做进一步的分析，特别是一些原子命题间常常有一些共同的特征。（谓词逻辑）,“猫是动物。” “猫”：主词、主语（一般是客体） “是动物”：谓词（用来描述或判定客体性质、特征或客体之间关系的词项） “3大于2” 3和2都是客体

4、，而“大于”是谓词。,二、谓词,“张三是学生。” “李四是学生。” 在命题逻辑中，这是两个不同的命题，可以分别用p、q来表示。 共同点：都有主词和谓词，并且谓词都是“是学生”。 若用大写符号P表示“是学生”，需要将主词区分开。P（张三）、P（李四）。,二、谓词,引入变量x表示主词，P(x)就表示“x是学生”； P(x)称作谓词或命题函数； 一旦给变量x一个赋值，语句P(x)就成为了命题； 通常，小写字母表示命题，大写字母表示谓词。,二、谓词,例：令P(x)表示语句“x3”， P(4)和P(2)的真值是什么？ 例：令Q(x,y)表示语句“x=y+3”，命题Q(1,2)、 Q(3,0)的真值是什么

5、？ 二元谓词,二、谓词,涉及n个变量如x1,x2, ,xn的语句可以用P(x1,x2, ,xn)表示，P是n元谓词； 例：P(x,y)：“x位于y东南方” P(天津,北京) “天津位于北京的东南方” 例：Q(x,y,z)：“x+y=z” Q(1,2,3)：“1+2=3”,二、谓词,P(x,y,z)和P(x,z,y)是一样的，但是x,y,z一经约定，P(x,y,z)和P(x,z,y)就代表了两个不同的命题。 Q(x,y,z)：“x+y=z” Q(1,2,3)：“1+2=3” 真 Q(1,3,2)：“1+3=2” 假,二、谓词,逻辑联结词、的意义与命题逻辑中的解释完全类同。 例：用H(x,y)表示

6、“x比y长得高”。 H(张三，李四): “张三比李四长得高” H(张三，李四): “张三不比李四长得高” H(张三，李四)H(李四，张三)：“张三不比李四长得高并且李四不比张三长得高”，即“张三与李四一样高”。,二、谓词,个体词：在数理逻辑中，不使用主词这个词，习惯称为个体词。 P（张三）中的“张三”是个体词或称个体常项；P(x)中的x为个体变项或个体变元。,二、谓词,个体变元的变化范围称为个体域或论域，以D表示。 谓词可以抽象定义为：谓词是给定的个体域到集合T,F上的一个映射。如：P(x)，其中xD，而P(x)的取值为T或F。,二、谓词,论域对命题函数是否成为命题以及命题的真值有很大的影响。

7、 例：设Q(x,y)表示“x比y重”，当x，y指人或物时，它是一个命题，但若x，y指实数时，它就不是一个命题。 例：R(x)表示“x是大学生”，如果x的论域是在座的全体学生，则R(x)是永真式；如果x的讨论范围学府中学的学生，那么R(x)是矛盾；如果x论域为一个电影院里所有观众，那么对某些观众R(x)为真，对另外一些观众，R(x)为假。,二、谓词,例：(P(x,y)P(y,z)P(x,z) P(x,y)表示“x小于y”，x,y,z在实数域中取值：“如果x小于y并且y小于z，那么x小于z”，永真式。 P(x,y)表示“x为y的儿子”，x,y,z都指人：“若x为y的儿子并且y为z的儿子，那么x是z

8、的儿子”，矛盾。 P(x,y)表示“x距离y10米”，x,y,z表示房子：“若x距离y10米并且y距离z10米，那么x距离z10米”，根据x,y,z的具体位置而定，可能为T，也可能为F。,二、谓词,命题函数在计算机程序中会经常用到： if x0 then x:=x+1 伪码，提供的是在算法的一般语言描述和它的程序语言实现之间的中间一步。 以算法的伪码描述为起点可以用任何一个计算机语言产生计算机程序。,二、谓词, 三、量词,对命题函数的变量赋值，可以将其转化成命题并得到真值；另外一种重要的方式也可以从命题函数得到命题，这就是量化。 例：S(x)表示“x是大学生”，x的论域是某单位的职工，那么S(

9、x)可以表示某单位职工都是大学生，也可以表示某单位存在一些职工是大学生。 为了避免理解上的混乱，因此引入量词。,全称量词 存在量词 定义：P(x)的全称量化是命题“P(x)对x在其论域的所有值为真”。记作：xP(x)。其中 称为全称量词。 “对所有x，P(x)” “对每个x，P(x)”,三、量词,例：“所有的人都是要呼吸的” 用P(x)表示“x是要呼吸的” xP(x)，其中论域为所有的人。 例：“生物数学教研室的老师都具有硕士学历” 用P(x)表示“x具有硕士学历” xP(x)，其中论域为生物数学教研室的老师 P24-例6、例7,三、量词,例：“本班每个学生都学过微积分” 用P(x)表示“x学

10、过微积分” xP(x)，其中论域由本班学生组成。 如果论域是所有学生的集合 用S(x)表示“x属于本班” x(S(x)P(x),三、量词,当论域中的所有元素可以一一列出时，如x1,x2, ,xn，量化语句xP(x)与合取 P(x1) P(x2) P(xn)是一回事。 例：若论域是不超过4的正整数，P(x)是语句“x210”，xP(x)的真值是什么？ 求P(1) P(2) P(3) P(4) 的真值 当且仅当P(1),P(2),P(3),P(4) 至少有一个为真时为真 P(4)为真，xP(x)为真。,三、量词,三、量词,在决定量化语句的真值时，借助循环与搜索来思考是有益的（当论域有无穷多值时不适

11、用）。 for i:=1 to n begin if P(xi)=F then begin I=F break (退出) end else I=T end,三、量词,把复杂的表达式翻译成文字语句有助于对其含义的理解。 x(C(x) y (C(y) F(x,y) C(x)：“x有台计算机” F(x,y)：“x和y是朋友” 论域是学校的全体学生的集合。 P26 例13、例14,三、量词,四、自然语句的形式化,“所有的有理数都是实数”的形式化 其意思是：对任一事物而言，如果它是有理数，那么它就是是实数。 论域：有理数的集合 论域：一切事物的集合。 P(x)：x是有理数； Q(x)：x是实数。,“所有

12、的有理数都是实数”的形式化 x(P(x)Q(x) x(P(x)Q(x) ？ 其意思是：对所有x，x是有理数并且是实数。 若x是非有理数（如无理数）的时候，x(P(x)Q(x) 为假 “所有的都是”，这类语句的形式描述只能使用而不能使用 。,四、自然语句的形式化,“有的实数是有理数”的形式化 其意思是：存在一事物，它是实数，并且它是有理数。 论域：实数的集合 论域：一切事物的集合。 P(x)：x是有理数； Q(x)：x是实数。,四、自然语句的形式化,“有的实数是有理数”的形式化 x(Q(x)P(x) x(Q(x)P(x) ？ 不符合人们的常规理解了，因为凡对于不是实数的事物，该命题都为T，这是不

13、对的。 “有的是”，通常使用，而不使用 。,四、自然语句的形式化,“没有无理数是有理数”的形式化 其意思是：对任一x而言，如果x是无理数，那么x不是有理数。 论域：一切事物的集合。 P(x)：x是无理数； Q(x)：x是有理数。,四、自然语句的形式化,“没有无理数是有理数”的形式化 (x)(P(x)Q(x) x(P(x)Q(x) x(Q(x)P(x),四、自然语句的形式化,“有的实数不是有理数”的形式化 其意思是：有的x，它是实数而且不是有理数。 论域：一切事物的集合。 P(x)：x是实数； Q(x)：x是有理数。 x(P(x)Q(x),四、自然语句的形式化,自然数集的形式描述 论域是自然数集

14、，来形式化语句： 1）对每个数，有且仅有一个相继后元； 2）没有这样的数，0是其相继后元； 3）对除0之外的数，有且仅有一个相继前元。 这三句话可以作为建立自然数集合的公理。,四、自然语句的形式化,自然数集的形式描述 引入谓词E(x,y)表示x=y； f(x)表示个体x的相继后元，f(x)=x+1; g(x)表示个体x的相继前元，g(x)=x-1; 特别需要注意唯一性的描述：如果有两个，则它们必相等。即若对每个x都存在y，y是x的相继后元，且对任一z，如果它也是x的相继后元，则y, z必相等。,四、自然语句的形式化,自然数集的形式描述 (x)(y)(E(y,f(x)(z)(E(z,f(x)E(y,z) 语句2：(x)E(0,f(x) 语句3，注意“除0之外”的描述，可以理解为“如果x不等于0，则”的形式： (x)(E(x,0)(y)(E(y,g(x) (z)(E(z,g(x) E(y,z),四、自然语句的形式化,“至少有一偶数是素数”与“至少有一个偶数并且至少有一个素数”的形式化 P(x)：x是偶数； Q(x)：x是素数。 (x)(P(x)Q(x) (x)P(x)(x)Q(x) 不等价,四、自然语句的形式化,“一切事物它或是生物或是非生物”与“或者一切事物都是生物，或者一切事物都是非生物”的形式化 P(x)：