离散数学第二章课件

第二章

一阶逻辑

本章内容 命题符号化 合式公式 永真公式 范式 推理理论

2006-03-01 2006-03-

第二章 一阶逻辑

本章与前一章的区别在前一章的命题逻辑中， 在前一章的命题逻辑中，仅把命题分析到简 单命题为止， 单命题为止，只研究简单命题之间的逻辑关 系和推理关系。而不管简单命题内部的结构 系和推理关系。而不管简单命题内部的结构 如何。从而导致某些推理上的错误。 如何。从而导致某些推理上的错误。 本章将深入到命题的内部结构， 本章将深入到命题的内部结构，研究其内部的 形式结构和逻辑关系， 形式结构和逻辑关系，总结出正确的推理形式 和规则。 和规则。2006-03-01 2006-03- 第二章 一阶逻辑 2

2.1一、基本概念

命题符号化

个体：可独立存在的事物称为个体 ⒈ 个体：可独立存在的事物称为个体 ——用小 用小 写字母表示. 写字母表示. 个体词：用来表示个体的符号称为个体词。 ⒉ 个体词：用来表示个体的符号称为个体词。 个体常元： ⒊ 个体常元：若一个个体词表示一个特定的个 体，则称之为个体常元。习惯上 则称之为个体常元。 用小写的a、 、 等表示 等表示。 用小写的 、b、c等表示。2006-03-01 2006-03- 第二章 一阶逻辑 3

个体变元：若一个个体词泛指任何一个个体， ⒋ 个体变元：若一个个体词泛指任何一个个体， 则称之为个体变元。 则称之为个体变元。习惯上用小 写的x 写的x、y、z等表示。 等表示。 个体域(论域): ):个体变元的取值范围称为 ⒌ 个体域(论域):个体变元的取值范围称为 个体域。 个体域。

2006-03-01 2006-03-

第二章 一阶逻辑

举例： 考虑下列句子： 举例： 考虑下列句子： ⑴ 苏格拉底是人 大于或等于3 ⑶ x大于或等于3 ⑵ 2是质数 ⑷ 布什是美国总统

其中， 苏格拉底’ 其中，‘苏格拉底’、2、x、布什都是个体词，且 布什都是个体词， 除 了x外都是个体常元. X为个体变元 外都是个体常元. X为个体变元 对上述个体变元进行符号化时，可用a表示‘ 对上述个体变元进行符号化时，可用a表示‘苏格 拉底’ 拉底’,用b表示2,用c表示‘布什’等 表示2 表示‘布什’2006-03-01 2006-03- 第二章 一阶逻辑 5

谓词： ⒍ 谓词：定义： 定义：表示个体的性质或个体之间联系 的词称为谓词。 的词称为谓词。 表示方法：常用大写字母P、Q、R等表示. 表示方法：常用大写字母P 等表示. 谓词的元数： 谓词的元数：表示一个个体的谓词称为 一元谓词； 一元谓词；2006-03-01 2006-03- 第二章 一阶逻辑 6

例3:⑶ 唐宗宋祖稍逊风骚 个体

词“唐太宗” 个体词“唐太宗”、“宋太祖”分别用 宋太祖” 表示; a、b 表示; 稍逊风骚” 表示， 谓词 “…稍逊风骚” 用 P 表示，用于 稍逊风骚 一个个体的性质，是一元谓词。 刻画 一个个体的性质，是一元谓词。 则这个命题表示成： 则这个命题表示成： P(a)∧P(b)2006-03-01 2006-03- 第二章 一阶逻辑 7

例4:⑷ x<y 个体词 x、y. 谓词 “…比…小” 用 P 表示，用于刻画 表示， 比 小 两个个体间的关系。是二元谓词。 两个个体间的关系。是二元谓词。 则这个命题表示成： (x,y)。 则这个命题表示成： P(x,y)。

2006-03-01 2006-03-

第二章 一阶逻辑

⒎ 量词⑴定义：在一个命题中，不仅有个体词、谓 定义：在一个命题中，不仅有个体词、 还有表达个体数量的词， 词，还有表达个体数量的词，称之 为量词。 为量词。 ⑵全称量词与存在量词

全称量词： 全称量词：用 表示，对应于自然语言中的 表示， “凡是”、“所有”、“任意”、 凡是” 所有” 任意” “一切“ 一切“2006-03-01 2006-03- 第二章 一阶逻辑 9

存在量词：用 表示，对应于自然语言中的 存在量词： 对应于自然语言中的 有些” “存在”、 “有些”、“至少有一 存在” 个” 等词. 等词 存在唯一量词： 存在唯一量词：用 !表示，对应于自然语言 表示， 中的“恰有一个” 中的“恰有一个”、“存在唯一”、 存在唯一” “有且仅有一个”. 有且仅有一个”2006-03-01 2006-03- 第二章 一阶逻辑 10

例1:任何自然数不是奇数就是偶数。 任何自然数不是奇数就是偶数。 ):x是自然数。 设：N(x):x是自然数。 是奇数。 O(x) :x是奇数。 特性谓词 是偶数。 E(x) :x是偶数。 ):x能被2整除。 D(x):x能被2整除。 当个体域为全总个体域 全总个体域时 当个体域为全总个体域时，那么符号化的 结果是： 结果是： O( x(N(x) → O(x)∨ E(x)) 当个体域为自然数 自然数时 那么符号化的结果是： 当个体域为自然数时 ，那么符号化的结果是： x(O(x)∨E(x))2006-03-01 2006-03- 第二章 一阶逻辑 11

例2:有些有理数不是整数。 有些有理数不是整数。 设：I(x):x是整数。 ):x是整数。 ):x是有理数。 Q(x):x是有理数。 当个体域为全总个体域时， 当个体域为全总个体域时，那么符号化的 结果是： 结果是： x(Q(x)∧ ¬ I(x)) 那么符号化的结果是： 当个体域为有理数时 ，那么符号化的结果是： x (¬ I(x))2006-03-01 2006-03- 第二章 一阶逻辑 12

例3:存在唯一的偶质数。 存在唯一的偶质数。 设：P(x):x是质数。 )

:x是质数。 ):x是偶数。 O(x):x是偶数。 全总个体域时 符号化的结果是： 当个体域为全总个体域 当个体域为全总个体域时，符号化的结果是： !x(P(x)∧O(x)) 当个体域为质数时，符号化的结果是： 当个体域为质数时，符号化的结果是： !x (O(x)) 当个体域为偶数时，符号化的结果是： 当个体域为偶数时，符号化的结果是： !x (P(x))2006-03-01 2006-03- 第二章 一阶逻辑 13

⒏全总个体域 将命题符号化时， 将命题符号化时，个体域的指定与否是很重 要的。 要的。 对于事先未指定个体域的个体变元， 对于事先未指定个体域的个体变元，则认为 它的个体域为一切事物的集合，称为全总 它的个体域为一切事物的集合，称为全总 个体域。 个体域。 ⒐ 特性谓词 在命题符号化后 ，把那些限定个体变元的取 值范围的词称为特性谓词 特性谓词。 值范围的词称为特性谓词。

2006-03-01 2006-03-

第二章 一阶逻辑

⒑ 符号化时的一些规则 若是全称量词，那么其特性谓词是作为蕴含 若是全称量词，那么其特性谓词是作为蕴含 全称量词 出现的； 式的前件出现的 式的前件出现的； 若是存在量词，则特性谓词是作为合取式的 若是存在量词，则特性谓词是作为合取式的 存在量词 一个分量出现的 出现的。 一个分量出现的。

2006-03-01 2006-03-

第二章 一阶逻辑

例如： 人总是要死的。 例如：把 “人总是要死的。” 符号化 (x): 是人； (x): 是要死的。 解：设 A(x):x 是人； B(x):x是要死的。 若在全总个体域中讨论该问题时 人总是要死的”符号化为： 则“人总是要死的”符号化为： x ( A(x) → B(x) ) 理解为： 只要是人，总是要死的。 理解为：对所有的 x,只要是人，总是要死的。

2006-03-01 2006-03-

第二章 一阶逻辑