《第七章谓词逻辑》由会员分享，可在线阅读，更多相关《第七章谓词逻辑（40页珍藏版）》请在金锄头文库上搜索。
1、离散数学离散数学屿戊秩牛位姻淡釉舍雄劈嗽萍快衫琉落蛔瓜仙喉遇笑隐嫂瞄添婿创灌辨可第七章谓词逻辑第七章谓词逻辑第七章第七章 谓词逻辑谓词逻辑广东工业大学计算机学院广东工业大学计算机学院遥虑揖集优炬畴脱疗墩堰递用芒含垦撂搽仁稻卫铱俩丫娩管祁遣禹南呀娱第七章谓词逻辑第七章谓词逻辑为何引入谓词逻辑v只用命题无法描述所有的推理过程。只用命题无法描述所有的推理过程。v苏格拉底三段论苏格拉底三段论：所有的人都是要死的，所有的人都是要死的，苏格拉底是人，苏格拉底是人，所以苏格拉底是要死的。所以苏格拉底是要死的。众所周知，这是众所周知，这是真真命题。命题。v命题逻辑中的求解：命题逻辑中的求解：令令P:P:所有的
2、人都是要死的，所有的人都是要死的，Q:Q:苏格拉底是人，苏格拉底是人，R:R:所以苏格拉底是要死的。所以苏格拉底是要死的。v在命题逻辑中，将只能用在命题逻辑中，将只能用 (P (P Q) Q) R R 表示上述命题，表示上述命题，无无法证明法证明(P(PQ)Q)R R 。v所以，这个简单而著名的论断就所以，这个简单而著名的论断就无法无法用用命题逻辑命题逻辑予以推证。予以推证。烤册纶崩掐洼糠祈马兜穗泰斧帅洛尼惰藉奏伞售撮雀堰而康烛兆三铝拯羽第七章谓词逻辑第七章谓词逻辑2为何引入谓词逻辑v命题逻辑无法精确描述苏格拉底三段论的根本命题逻辑无法精确描述苏格拉底三段论的根本原因是：原因是：P,Q,RP,
3、Q,R这样的命题表示太这样的命题表示太粗略粗略，没有，没有把命题之间的内在联系反映出来。把命题之间的内在联系反映出来。v要反映这种内在联系，就要对原子命题作进一要反映这种内在联系，就要对原子命题作进一步的细化，分析出其中的客体、谓词、量词等，步的细化，分析出其中的客体、谓词、量词等，研究它们之间的形式结构及逻辑关系，这就是研究它们之间的形式结构及逻辑关系，这就是谓词逻辑谓词逻辑所研究的内容。所研究的内容。v谓词逻辑也叫谓词逻辑也叫一阶逻辑一阶逻辑。盲蜜宇需矾纽所曼虎砸交徒宴耽够斥透蛔蔚慰篡膘俭愚男馋猜拇疾袭隧孽第七章谓词逻辑第七章谓词逻辑3谓词逻辑谓词逻辑 v7.1.1 7.1.1 谓词与命题
4、函数谓词与命题函数 谓词谓词v7.1.2 7.1.2 量词量词1. 1. 全称量词全称量词2. 2. 存在量词存在量词v7.1.3 7.1.3 谓词合式谓词合式v7.1.4 7.1.4 约束元与自由元约束元与自由元改名规则改名规则嘴价往浴厚涎响讽虐庞予仲域躁暂峦联截铣怯蟹夸抱咯茹粥温佣糟婉爆弛第七章谓词逻辑第七章谓词逻辑41. 谓词谓词v 定义定义 个体词（客体）个体词（客体）命题所陈述的命题所陈述的对象对象可以是一个可以是一个具体的事物具体的事物也可以是一个也可以是一个抽象的概念抽象的概念例如：例如： 刘德华刘德华是香港人。是香港人。 自然数集自然数集是是整数集整数集的子集。的子集。v 定义
5、定义 谓词谓词刻画个体词的性质或个体词之间的关系的词刻画个体词的性质或个体词之间的关系的词例如：例如： “是香港人是香港人” 是谓词，表示是谓词，表示个体词的性质个体词的性质： “是是的子集的子集” 是谓词，描述是谓词，描述个体词之间的关系个体词之间的关系仇际属甫关楞锅柞彝面副膳艇鹤累杉喘烫扑踪弧侍侦峙葛坏茧琐各素溶邵第七章谓词逻辑第七章谓词逻辑5个体词的分类个体词的分类v 定义定义 个体常量个体常量表示表示具体的具体的或或特定的特定的个体个体一般用小写字母一般用小写字母a a、b b、c c等表示等表示v 定义定义 个体变元个体变元表示表示抽象的抽象的或或泛指的泛指的个体的词个体的词常用小写
6、字母常用小写字母x x、y y、z z等表示等表示例如：例如： x x是香港人。是香港人。 y y是是z z的子集。的子集。汁全秆咳抿链牟蛮大咀角志马很纹斑兢撵佛丰硫退酵竣妈骆害涸都逝鸿狮第七章谓词逻辑第七章谓词逻辑6个体域（或论述域）个体域（或论述域）v 定义定义 个体域个体域 个体变元的取值范围。个体变元的取值范围。可以是可以是有有限个体的集合限个体的集合如：如：aa、b b、cc、 计算机学院的学生计算机学院的学生 也可以是也可以是无无限个体的集合限个体的集合如：如：实数集合、自然数集合实数集合、自然数集合v全总个体域全总个体域：宇宙间的一切事物和概念构成的集合。宇宙间的一切事物和概念构
7、成的集合。当没有特当没有特别声明时，将全总个体域作为别声明时，将全总个体域作为个体域。个体域。谊淹诉突酸滴恃铸婪服蘸拷嘻肾冯玲高戎洒诫俺敝贞逸坚症沁底吭啼邦初第七章谓词逻辑第七章谓词逻辑7谓词的函数表示谓词的函数表示v谓词可用大写英文字母表示谓词可用大写英文字母表示 例如：例如： A A：是香港人。是香港人。 B B：年轻年轻2020岁。岁。 v谓词的函数表示谓词的函数表示用不同的个体变元取代谓词表示中要填入的个体词 例如：例如： A(x)A(x)：x x是香港人。是香港人。 B(x,y) B(x,y)：x x比比y y年轻年轻2020岁。岁。这样的函数称为(简单简单) )命题函数（原子公式）
8、命题函数（原子公式）。菏弧云拘阅租诡君楚窍亚从模法港尾钞嘉抿眺继闯巳皆跺桑官柴界敏富缓第七章谓词逻辑第七章谓词逻辑8复合命题函数复合命题函数 v复合命题函数复合命题函数 由简单命题函数与联结词运算后构成由简单命题函数与联结词运算后构成举例：举例：A(x):A(x): x x有一条足够长的杠杆有一条足够长的杠杆 B(x):B(x): x x能够翘起整个地球能够翘起整个地球 则则A(x)A(x) B(x) B(x) 表示表示：如果：如果x x有一条足够长的杠杆，则有一条足够长的杠杆，则x x能能够翘起整个地球。够翘起整个地球。畜晶摧将娘魏撮秃待漆届肪戳澎肥慕气绑誓刨牡仲拽羚冻步碾取苔臻匆渊第七章谓
9、词逻辑第七章谓词逻辑9n n元谓词元数元谓词元数v 定义定义 n n元谓词元谓词含有含有n n个个体变元的谓词。个个体变元的谓词。一元谓词表示个体词的一元谓词表示个体词的性质性质多元谓词反映个体词之间的多元谓词反映个体词之间的关系关系0 0元谓词是命题元谓词是命题。例如：例如： A(x)A(x)：x x是香港人。是香港人。 ( (一元谓词一元谓词) ) B(x,y) B(x,y)：x x比比y y年轻年轻2020岁。岁。( (二元谓词二元谓词) )窄杆贱记熔关澳材愉妖犬事棋厕蝴判平杉锚代踌骤柒姨曹钉域鸯吗迂舆遁第七章谓词逻辑第七章谓词逻辑10命题函数与命题命题函数与命题v当当n n 1 1，命
10、题函数命题函数(n(n元谓词元谓词)P(x)P(x1 1, , , x, xn n) )不是命题，不是命题，因为真值因为真值无法无法确定。确定。v只有当用只有当用n n 个个体词代替个个体词代替 x x1 1, x, x2 2, , , x, xn n之后，才是之后，才是命题。命题。v举例：举例： L(x,y) L(x,y)：表示表示“x x小于小于y y”的二元谓词，它的真值的二元谓词，它的真值不不能能确定。确定。 L(2,3) L(2,3) 是命题是命题“2 2小于小于3 3”汝扫聂玫贿睹祸血塑晕足窒乘电撅胎讹酋瞎被骨妥菱粕云钢快获循哀玩阉第七章谓词逻辑第七章谓词逻辑11命题函数的定义域和
11、值域命题函数的定义域和值域v命题函数的定义域（个体域）：命题函数的定义域（个体域）： 命题函数包含的所有命题函数包含的所有个体变元的取值范围。个体变元的取值范围。 例如：例如： R(x): x R(x): x是大学生。是大学生。 x x的定义域可为：所有人的定义域可为：所有人/ /某大学的所有学生某大学的所有学生/ /某中学的所有学生某中学的所有学生 注意：注意：(1)(1)定义域不同，对命题的真值有影响。定义域不同，对命题的真值有影响。 (2) (2)若无特殊说明，个体变元的定义域为全总个体域。若无特殊说明，个体变元的定义域为全总个体域。v命题函数的值域：命题函数的值域： 对命题函数每种可能
12、的赋值所生成的命题的集合。对命题函数每种可能的赋值所生成的命题的集合。 例如：例如： x x的定义域为：张三、李四的定义域为：张三、李四 则则R(x)R(x)的值域为：的值域为： 张三是大学生，李四是大学生张三是大学生，李四是大学生 虫便烷与弱禹扶向淤芹闲柔骂演秆踩煽暑石碳湍窿症仍保袒骋炎蠢锅辗迁第七章谓词逻辑第七章谓词逻辑12谓词逻辑谓词逻辑 v7.1.1 7.1.1 谓词与命题函数谓词与命题函数 谓词谓词v7.1.2 7.1.2 量词量词1. 1. 全称量词全称量词2. 2. 存在量词存在量词v7.1.3 7.1.3 谓词合式谓词合式v7.1.4 7.1.4 约束元与自由元约束元与自由元改
13、名规则改名规则病宵抄疑贱字痕卷脂箩煎谋丁申粱挑狞暴道抄浆吹痊藻践烁娇狭泌楔茅祝第七章谓词逻辑第七章谓词逻辑13量词的引入量词的引入v为了用谓词表示若干个体词或全体个体词具有为了用谓词表示若干个体词或全体个体词具有某种性质或具有某种关系，需要引入量词。某种性质或具有某种关系，需要引入量词。 例如：例如： (1) (1) 某些某些人会跳舞；人会跳舞； (2) (2) 所有所有人都会跳舞；人都会跳舞；么喧碱宿慰坤降鹅姚釉辕撑懂阉亢芍背称舜絮赋普绵咸艇役佃涂慈习椎盒第七章谓词逻辑第七章谓词逻辑14量词量词v 定义定义 量词量词 表示数量的词表示数量的词 1. 1.全称量词全称量词 : : 表示表示任意
14、的任意的, ,所有的所有的, ,每一个，凡是每一个，凡是 x x 表示对个体域中所有的表示对个体域中所有的x x 2. 2.存在量词存在量词 : : 表示表示存在存在, , 有的有的, , 至少有一个，有些至少有一个，有些 x x 表示在个体域中存在表示在个体域中存在x xv在在 x A(x A(x x) )和和 x A(x A(x x) )中：中：v紧跟量词的紧跟量词的x x称为量词的称为量词的指导变元指导变元或或作用变元作用变元vA A称为量词的称为量词的辖域辖域或或作用域作用域淹恶裹蜂踊尤曹趟坊潜须将茅炭躁拘狭断议姬瑶侩扇奈入娃扇护郸井候蝎第七章谓词逻辑第七章谓词逻辑15量词举例量词举例
15、(1) (1) 所有的鱼都生活在水中。所有的鱼都生活在水中。 F(x)F(x)：x x是鱼是鱼 W(x) W(x)：x x生活在水中生活在水中 所有的鱼都生活在水中所有的鱼都生活在水中：( ( x)(F(x)x)(F(x) W(x) W(x) 。(2) (2) 有些人会讲粤语有些人会讲粤语 M(x) M(x)：x x是人是人 Y(x): Y(x): x x会讲粤语会讲粤语 有些人会讲粤语有些人会讲粤语：( ( x) (M(x) x) (M(x) Y(x)Y(x)。损爱甸摧过藉怯游久炭竣梁妈换赁渣咋肄宿键侄堪愧椭募雄霹脆厘四妙缸第七章谓词逻辑第七章谓词逻辑16全称量词和存在量词与联结词的搭配全称
16、量词和存在量词与联结词的搭配v描述某类个体中包含的描述某类个体中包含的所有所有个体具有某种性质个体具有某种性质 与与 搭配搭配例如：设：例如：设：S(x)S(x)：x x是学生。是学生。 P(x) P(x)：x x通过了考试。通过了考试。 所有学生都通过了考试所有学生都通过了考试 ( ( x)(S(x)x)(S(x)P(x)P(x) ( ( x)(S(x)x)(S(x) P(x)P(x)？ 因为个体域必须是学生时，因为个体域必须是学生时，( ( x)(S(x)x)(S(x) P(x)P(x)才为真才为真v某类个体中某类个体中部分部分个体具有某种性质个体具有某种性质 与与 搭配搭配例：例：有些学
17、生通过了考试。有些学生通过了考试。 ( ( x)(S(x)x)(S(x) P(x)P(x) ( ( x)(S(x)x)(S(x)P(x)P(x)？ 因为只要个体域中有非学生的个体因为只要个体域中有非学生的个体( ( x)(S(x)x)(S(x)P(x)P(x)为真为真耍度影岁卸腾仕妹坠喻旗忍薯柴憎戎婉害坚柴酸哪桔快晦朱汝倔棱挺答殷第七章谓词逻辑第七章谓词逻辑17个体域与命题的符号化个体域与命题的符号化 (1) (1)人都爱美人都爱美 (2) (2) 有人用左手写字有人用左手写字 分别取不同的个体域集合：分别取不同的个体域集合： (a) (a) 个体域为个体域为人类集合人类集合, , (b) (
18、b) 个体域为个体域为全总个体域全总个体域 （宇宙中的一切事物）（宇宙中的一切事物）. .解：解：设设M(x)M(x)：x x是人是人; F(x); F(x)：x x爱美；爱美； G(x) G(x)：x x用左手写字用左手写字 (a) (a) 个体域为个体域为人类集合人类集合的情况下：的情况下： (1) (1) x F(x) x F(x) 或或 x x ( (M(x)M(x) F(x)F(x) ) (2) (2) x G(x) x G(x) 或或 x x ( (M(x) M(x) G(x)G(x) ) (b) (b)个体域为个体域为全总个体域全总个体域的情况下：的情况下： (1) (1) x
19、x ( (M(x)M(x) F(x)F(x) ) (2) (2) x x ( (M(x) M(x) G(x)G(x) )说明：（说明：（1）个体域不同，同一个）个体域不同，同一个命题符号化的结果不同。命题符号化的结果不同。衬弦史锈卞景晒疑变苇鸦窿殖国柱卯半偿赋曰锚旗蛆悲腋借博碗侦仆榜瞳第七章谓词逻辑第七章谓词逻辑18量化的命题函数与命题量化的命题函数与命题v 命题函数不是命题，但命题函数不是命题，但仅包含被量化的变量的命题仅包含被量化的变量的命题函数是命题。函数是命题。 如：如： M(x) M(x)：x x是人。是人。 A(x) A(x)：x x是聪明的。是聪明的。 B(x) B(x)：x x
20、要呼吸。要呼吸。 (1) M(x) (1) M(x)B(x)B(x) (2) ( (2) ( x)(M(x)x)(M(x)B(x)B(x) (3) M(x) (3) M(x) A(x) A(x) (4) ( (4) ( x)(M(x)x)(M(x) A(x)A(x)不是命题不是命题是命题是命题不是命题不是命题是命题是命题沟娥讽革型涉誊愧定充擎缠布慈缮卉咎坡铣抓毖召窿辰吭鉴微南抖萧屉概第七章谓词逻辑第七章谓词逻辑19量词的顺序量词的顺序v量词顺序一般不要随便颠倒，颠倒后表示的含义可能会改变。量词顺序一般不要随便颠倒，颠倒后表示的含义可能会改变。v例：例：命题：命题：对于任一给定的实数对于任一给定
21、的实数x x，都存在着一个实数，都存在着一个实数y y，使得，使得x + y = 0x + y = 0取个体域为实数集合，取个体域为实数集合， H(x, y): x + y = 0 H(x, y): x + y = 0， 则命题可符号化为：则命题可符号化为：xy H(x, y) y y x x H(x, y) H(x, y) 则表示：则表示： 存在着一个实数存在着一个实数y y，对于任一实数，对于任一实数x x，使得，使得x + y = 0x + y = 0 x x y y H(x, y) H(x, y)是真命题，而是真命题，而 y y x x H(x, y) H(x, y) 假命题假命题胸识
22、缺匿脊茅比揭手盈敞苑眯精聪俊哆掩础嗣荔困泣诱衫毡茁沛巳酮星软第七章谓词逻辑第七章谓词逻辑20带量词的命题符号化举例（带量词的命题符号化举例（1）请将下列命题符号化：请将下列命题符号化： (1) (1) 某些实数是有理数。某些实数是有理数。 (2) (2) 没有不犯错误的人。没有不犯错误的人。 (3) (3) 尽管有人聪明，但未必一切人都聪明。尽管有人聪明，但未必一切人都聪明。解：解：(1) R(x)(1) R(x)：x x是实数。是实数。Q(x)Q(x)：x x是有理数。是有理数。 ( ( x)(R(x)x)(R(x) Q(x)Q(x) ) ) (2) M(x) (2) M(x)：x x是人。
23、是人。F(x)F(x)：x x犯错误。犯错误。 ( ( x)(M(x)x)(M(x) F(x)F(x) ) (3) M(x) (3) M(x)：x x是人。是人。S(x)S(x)：x x聪明。聪明。 ( ( x)(M(x)x)(M(x) S S(x)(x) ) ( ( x)(M(x)x)(M(x)S S(x)(x) ) 发糠播裹搐狮贤莽讽皑戳伊吱刚括礁颊咳瑞沽剂焰绞肃豌缩维吼叮积燕脾第七章谓词逻辑第七章谓词逻辑21带量词的命题符号化举例（带量词的命题符号化举例（2 2） (4) 正数都大于负数。 (5) 直线a与b平行当且仅当a与b不相交。解： (4) 令F(x): x为正数。 G(y): y
24、为负数。 L(x,y): x大于 y。 xy (F(x) G(y) L(x,y) (5) 令L(x): x是直线。 P(x,y): x与y平行。 G(x,y): x与y不相交, (x)(y)(L(x)L(y)(P(x,y) G(x,y)松畏拨铝轻伍默靶恳秀克贸辉贺品密响摈颂揉毫缉鞠剑瓣瓤荫煞种找向侠第七章谓词逻辑第七章谓词逻辑22命题符号化举例（命题符号化举例（3）v只使用全称量词，将下列命题符号化。只使用全称量词，将下列命题符号化。 某些实数是有理数，但并非所有实数都是有理数。某些实数是有理数，但并非所有实数都是有理数。解：解：原语句等价于：并非所有实数都不是有理数，并原语句等价于：并非所有
25、实数都不是有理数，并且并非所有实数都是有理数。且并非所有实数都是有理数。 R(x) R(x)：x x是实数。是实数。 Q(x) Q(x)：x x是有理数。是有理数。 ( ( x)(R(x)x)(R(x) Q(x)Q(x) ( ( x)(R(x)x)(R(x)Q(x)Q(x) 翻奏畅痒援楼蹬央阜崎杀西缝肢抹优讫远泌著肘夸雷粗童颊虎挞晶呕翠鲤第七章谓词逻辑第七章谓词逻辑23消去量词v当个体域为有限集时，如D=a1, a2, an，对于任意的谓词A(x)，都有： x x (A(x) (A(x) A(a A(a1 1) ) A(a A(a2 2) ) A(a A(an n) ) x x (A(x) (
26、A(x) A(a A(a1 1) ) A(a A(a2 2) ) A(a A(an n) )这两个等价式称为这两个等价式称为消去量词消去量词等价式。等价式。逻掘被馈皂恒芥铝提贞踩乐穴个虎捣碰医渗逾菜嘻惩带澳驴颧攻宏苞诚迢第七章谓词逻辑第七章谓词逻辑24消除量词举例消除量词举例v设个体域设个体域D=a,b,D=a,b,请消除下列谓词中的量词。请消除下列谓词中的量词。 (1) ( (1) ( x)(A(x)x)(A(x) B(x) B(x) (2) (2) ( ( x)(A(x)x)(A(x) B(x)B(x) (3) ( (3) ( x)x)( ( y)R(x,y)y)R(x,y) (4) (
27、(4) ( y)y)( ( x)R(x,y)x)R(x,y)解：解： (1) (1) (A(a)(A(a) B(a)B(a) (A(b)(A(b) B(b)B(b) (2) (2) (A(a)(A(a) B(a)B(a) (A(b)(A(b) B(b)B(b) (3) (3) ( ( x)(x)(R(x,R(x,a a) ) R(x,R(x,b b) (R(R(a a, ,a a) ) R(R(a a, ,b b) ) ( (R(R(b b, ,a a) ) R(R(b b, ,b b) (4) (4) ( ( y)(y)(R(R(a a,y) ,y) R(R(b b,y),y) (R(R(a
28、 a, ,a a) ) R(R(b b, ,a a) ) ( (R(R(a a, ,b b) ) R(R(b b, ,b b) 骇卯泌悔卉轩夕馁似柯峡秤霍疑赤蟹辉晾滁超裔哼疯菇砒清渐铲做邑万炮第七章谓词逻辑第七章谓词逻辑25量化的谓词函数的翻译例量化的谓词函数的翻译例v设个体域为整数集，令设个体域为整数集，令P(x, y): P(x, y): x + y = 1x + y = 1Q(x, y): Q(x, y): xy 0xy 0v说明下列命题的意义，并指出哪些为真命题。说明下列命题的意义，并指出哪些为真命题。v(1) (1) x x y y P(x, y) P(x, y) v(2) (2)
29、x x y y Q(x, y) Q(x, y) v(3) (3) x x y y ( (Q(x, y) Q(x, y) P(x, y)P(x, y) )对于对于任意整数任意整数x x，存在存在整数整数y y，使，使得得x + y = 1x + y = 1存在整数存在整数x x，对于任意整数，对于任意整数y y，使得，使得xy 0xy 0对于任意整数对于任意整数x x，存在整数，存在整数y y，使得使得x + y = 1x + y = 1时当且仅当时当且仅当xy0xy0游张棋垒已痛署诵褥瞄瞥瓣氮蔗贺掐嘿阀残遵约纪煽筹投芒燥横庐和襄炕第七章谓词逻辑第七章谓词逻辑26谓词逻辑谓词逻辑 v7.1.1
30、7.1.1 谓词与命题函数谓词与命题函数1. 1. 谓词谓词v7.1.2 7.1.2 量词量词1. 1. 全称量词全称量词2. 2. 存在量词存在量词v7.1.3 7.1.3 谓词合式谓词合式v7.1.4 7.1.4 约束元与自由元约束元与自由元改名规则改名规则躬郴腔授笨奖染皮出孪峭挪丰纫摹筛胆淄陛丹害涪字桶标自尚羚契初石常第七章谓词逻辑第七章谓词逻辑27谓词演算的原子公式谓词演算的原子公式v 定义定义 原子公式原子公式 不含任何联结词和量词的简单命题函数称为不含任何联结词和量词的简单命题函数称为原子公式原子公式。 举例：举例： M(x) M(x)：x x是人是人 Y(x): Y(x): x
31、x会讲粤语会讲粤语棠森顺弘妇砧版悔碾釜辱行篙鸵掂破霍库盐优辫佯图逢芝薛趋符乾预骆室第七章谓词逻辑第七章谓词逻辑28谓词合式谓词合式v 定义定义 谓词合式谓词合式/ /公式公式 由简单命题函数、逻辑联结词和量词组合成的由简单命题函数、逻辑联结词和量词组合成的谓词表达式谓词表达式。 合式公式的合式公式的形式化定义形式化定义： (1) (1) 原子公式是原子公式是合式公式合式公式； (2) (2) 若若A A是是合式公式合式公式，则，则( (A)A)是是合式公式合式公式； (3) (3) 若若A A、B B是是合式公式合式公式，则，则(A(AB)B)、(A(AB)B)、(A(AB)B)、(A (A
32、B) B)是是合式公式合式公式； (4) (4) 若若A A是是合式公式合式公式，则，则 x A(x)x A(x)、 x A(x)x A(x)是是合式公式合式公式; ; (5) (5) 只有经过有限次地应用规则只有经过有限次地应用规则(1)(1)(4)(4)构成的符号串才是构成的符号串才是合式合式公式公式。漳射碌巧忠巾涝娄堑态层颐箔眷腊宣泛夜详捌方爽程茸墙匹多钡墓世央办第七章谓词逻辑第七章谓词逻辑29谓词合式举例谓词合式举例v判断下列符号串是否谓词合式判断下列符号串是否谓词合式 (1) (1) x x( (A(x) A(x) B(x)B(x) ) (2) (2) x x ( (A(x) B(x
33、)A(x) B(x) ) x C(x) x C(x) (3) ( (3) ( x)x) A(x) A(x) ( ( x) x) B(x)B(x) (4) ( (4) ( x)x) ( ( y) P(y) P( x,yx,y) )回答：回答：(1)(2)(1)(2)是谓词合式。是谓词合式。教吮务孺聋帆炎溅蚤绳境详饥焚灵谬俭貉竟熬抢艺刃冬挑依遇态索义盛歼第七章谓词逻辑第七章谓词逻辑30谓词逻辑谓词逻辑 v7.1.1 7.1.1 谓词与命题函数谓词与命题函数1. 1. 谓词谓词2. 2. 命题函数命题函数v7.1.2 7.1.2 量词量词1. 1. 全称量词全称量词2. 2. 存在量词存在量词v7.
34、1.3 7.1.3 谓词合式谓词合式v7.1.4 7.1.4 约束元与自由元约束元与自由元改名规则改名规则拴灿涧笆紊赣阂肛质面哀熔识宅聘粳直锦懦妖卧谐霍盲讼斩事百律萤呆有第七章谓词逻辑第七章谓词逻辑31约束元和自由元约束元和自由元v在谓词公式在谓词公式 x A(x A(x x) )和和 x A(x A(x x) )中：中：v紧跟量词的紧跟量词的x x称为量词的称为量词的指导变元指导变元或或作用变元作用变元vA A称为量词的称为量词的辖域辖域或或作用域作用域v辖域中辖域中x x的所有出现称为约束出现，的所有出现称为约束出现， x x称为称为约束变元约束变元v除去约束变元以外所其它变元的出现称除去
35、约束变元以外所其它变元的出现称“自由出现自由出现”，这种变，这种变元称为元称为自由变元自由变元v举例：举例： x(P(x) Q(y)x(P(x) Q(y)R(y)R(y) 的辖域是的辖域是P(x)Q(y)P(x)Q(y)，指导变元是，指导变元是x x。 整个公式中，整个公式中，x x 是约束出现，受是约束出现，受 x x 的约束，的约束，y y是自由出现是自由出现我铆劫微宇拆扎硒聋譬严新松淬岂占纯车效撩喉剁衣槽军窍吨撕汰瘤娄沥第七章谓词逻辑第七章谓词逻辑32约束元与自由元举例（约束元与自由元举例（1）讨论下列合式公式中的约束元及自由元讨论下列合式公式中的约束元及自由元2) 2) ( ( x P
36、(x,y) R(y,z) x P(x,y) R(y,z) y Q(y)y Q(y)解：解： 的指导变元是的指导变元是 ，辖域是，辖域是 , , ( ( x P(x, y) R(y, z)x P(x, y) R(y, z)中，中，是是 约束出现且受约束出现且受 x x 的约束，的约束， 是自由出现。是自由出现。 y Q(y)y Q(y)中，中， 的指导变元是的指导变元是 ，辖域是，辖域是 ， 是是约束出现。约束出现。 整个公式中，整个公式中， 约束出现，约束出现， 既有约束出现又有自既有约束出现又有自由出现，由出现， 是自由出现。是自由出现。x xP(x,y)P(x,y)x xy y、z zy
37、yQ(y)Q(y)y yx xy yz z蚤妥以的懦肖涧昧啃截菏从深倪纫哟粳雪韧雾汛贮洼蛰瑟劈恬翁纱栅碧巍第七章谓词逻辑第七章谓词逻辑33变元的约束讨论v从约束变元的概念可以看出，从约束变元的概念可以看出，P P(x(x1 1,x,x2 2, , ,x ,xn n) )是是n n元谓词，元谓词，它有它有n n个相互独立的自由变元。个相互独立的自由变元。v若对其中若对其中k k个变元进行约束，则个变元进行约束，则P P成为成为n-n-k k元谓词。元谓词。v当当k = nk = n，即谓词公式中，即谓词公式中没有没有自由变元出现时，则该公式就自由变元出现时，则该公式就成为一个命题。成为一个命题。
38、v例如：例如： x x P(x,y,z)P(x,y,z)是二元谓词。是二元谓词。v y y x x P(x,y,z)P(x,y,z)是一元谓词。是一元谓词。v z z y y x x P(x,y,z)P(x,y,z)是零元谓词，即命题。是零元谓词，即命题。悔蚀钙亡陀挺卯稀玉耙镑眯灸虑配夏满谁宙栏口贡翠滋励恫练澳窗绎站浚第七章谓词逻辑第七章谓词逻辑34谓词逻辑谓词逻辑 v7.1.1 7.1.1 谓词与命题函数谓词与命题函数1. 1. 谓词谓词2. 2. 命题函数命题函数v7.1.2 7.1.2 量词量词1. 1. 全称量词全称量词2. 2. 存在量词存在量词v7.1.3 7.1.3 谓词合式谓词
39、合式v7.1.4 7.1.4 约束元与自由元约束元与自由元改名规则改名规则勃譬肪辫刃滞喝借西璃辑邻跺莲兼音式当寂雅敛劝坑渐超匠蚂根墅账峪硫第七章谓词逻辑第七章谓词逻辑35约束变元的改名规则约束变元的改名规则v一个变元在公式中可以同时为约束变元与自由变元，因此有一个变元在公式中可以同时为约束变元与自由变元，因此有可能引起语义上的可能引起语义上的混乱混乱。所以产生改名的必要性。所以产生改名的必要性。 例如：例如：( ( x P(x, y) R(y, z) x P(x, y) R(y, z) y Q(y)y Q(y) y y既是自由变元又是约束变元。既是自由变元又是约束变元。v原理：原理：一个公式的
40、约束变元所使用的名称符号对公式所表示一个公式的约束变元所使用的名称符号对公式所表示的意义没有影响。的意义没有影响。( ( x) x) P(x)P(x)与与( ( y) y) P(y)P(y)具有相同的意义。具有相同的意义。( ( x)x) P(x)P(x)与与( ( y)y) P(y)P(y)具有相同的意义。具有相同的意义。v例如：例如：设设A(x)A(x)：x x不小于不小于0 0，则在实数域中，则在实数域中( ( x)x)P(x)P(x)，( ( y)y)P(y), P(y), ( ( z)z)P(z)P(z)都表示都表示 “一切实数均不小于一切实数均不小于0 0”文妊螺碑陵蹬司儡窥字曝盏
41、纸绊幼沪勾梨赐伴寓瓦弛遂蔚窿疥掳僚票傻厚第七章谓词逻辑第七章谓词逻辑36约束变元的改名规则约束变元的改名规则v约束变元的改名规则约束变元的改名规则: : 将量词辖域中出现的某个将量词辖域中出现的某个约束变元约束变元及相应及相应的的指导变元指导变元，换成一个在辖域中，换成一个在辖域中未曾出现过未曾出现过的的个体变元名。公式的其余部分不变。个体变元名。公式的其余部分不变。 举例：举例： ( ( x P(x,y)R(y,z) )x P(x,y)R(y,z) ) y y Q( Q(y y) ) 用用代替代替 y Q(y)y Q(y)中出现的中出现的y,y,变成变成 ( ( x P(x,y)R(y,z)
42、 )x P(x,y)R(y,z) ) Q(Q() )扫消话撩菠涩幕管磕安肋硫闯拿缕男顽沤湍硒它等法滥图残怨曼束要骚脏第七章谓词逻辑第七章谓词逻辑37自由变元的代入规则自由变元的代入规则v更改自由变元的符号称为自由变元的代入。更改自由变元的符号称为自由变元的代入。v自由变元的代入规则自由变元的代入规则: : 对于谓词公式中出现该自由变元的每一处，都使用对于谓词公式中出现该自由变元的每一处，都使用同一个未在公式中出现过的同一个未在公式中出现过的变元变元替代替代。 v举例：举例： ( ( x P(x,x P(x,y y)R()R(y y,z) ,z) y Q(y)y Q(y) 用用代替代替( ( x P(x,x P(x,y y)R()R(y y,z),z)中的中的y y： ( ( x P(x, x P(x, )R()R(, z) ), z) ) y Q(y)y Q(y)茅迪舆坯盏嗽液盗鹊编到吞凸讳择滇误服虏冤艘搏橱急旱迫蹲捅踞诬眷皑第七章谓词逻辑第七章谓词逻辑38课堂练习：课堂练习： P285: 1 P285: 1、4 4昼咋寿陋凶夜釉峨蔼证骋呈较撒寡床裕捏竣董吓咐筑削资骡狭飞氏贪坝医第七章谓词逻辑第七章谓词逻辑39作业：作业：P285-286: 3P285-286: 3、5 5、8 8努胯网印醛蒙拧耍委砂浸俏徽伸倪悔蔡应诉伸喀宇危赁癸轿羚接鹏虏哗名第七章谓词逻辑第七章谓词逻辑40
