1、离 散 数 学 第十五章一 阶 逻 辑1离 散 数 学 逻辑学中的三段论1 凡有理数都是实数2 1/3是有理数3 1/3是实数在命题逻辑中无法表示其推理过程因为如果我们用 P,Q,R分别表示命题 1， 2， 3则 , 按照三段论法， P Q R 可表示上述推理这就是命题逻辑的局限性三段论的论断显然正确，但在命题逻辑中 P QR并不是重言式。取 P=1， Q=1， R=0，就可弄假 P QR故其不能正确反映三段论的推理过程2离 散 数 学 原 因q 在命题逻辑中无法将所有命题之间的内在联系反映出来。命题逻辑中描述的三段论，即 P QR ，使 R是与命题 P、 Q无关的独立命题。但实际上 R是与命
2、题 P、 Q有关的，只是这种关系在命题逻辑中得不到反映。q 要反映这种内在联系 ,就要对简单命题作进一步分析 ,分析出其中的个体词 ,谓词 ,量词 ,研究它们的形式结构及逻辑关系 ,总结出正确的推理形式和规则 ,这就是一阶逻辑所研究的内容 .一阶逻辑也称谓词逻辑 .3离 散 数 学 15.1 谓词与量词研究对象的全体所构成的集合 .又称个体域。一阶逻辑中论域中的元素 .又称个体词。定义 15.1.1 设 D是非空个体集合。定义在 Dn上取值于 0,1 上的 n元函数称为 n元命题函数或 n元谓词。其中 Dn表示 D的 n次笛卡尔积 .1.论域：2.个体：令 P(x)表示 x为质数，则 P(x)
3、为一元谓词。令 H(x， y)表示 “x高于 y”。则 H(x， y)为二元谓词。将 x代以个体 “张三 ”， y代以个体 “李四 ”，则 H(张三 ,李四 )就是命题 “张三高于李四 ”。 注意：P(x.y)与 H(x,y)为命题函数 .而 P(2)与 H(张三 ,李四 )才是命题。例子：3.量词 : 在命题中表示数量的词 .分两类 .即存在与全称量词 .4离 散 数 学 概念的讨论 谓词是用来刻划个体的性质或个体之间的关系的。v谓词如有 n个变元则称为 n元谓词 . n元谓词反映了n元关系 .v变元在谓词中的次序直接影响了谓词的取值 .如 :谓词 P(x,y)为 “x比 y高 ”.而张三为
4、 170cm,李四为 180cm.则 :P(李四 ,张三 )为真命题 .P(张三 ,李四 )为假命题 .v个体是可以独立存在的实体 ,它既可以是一个具体的事物 ,也可以是一个抽象的概念用个体 ,谓词表示命题的例子 :5离 散 数 学 例子 : 1,武汉位于重庆与上海之间 .解 :个体 a,b,c分别表示武汉 ,重庆和上海 ,谓词 P(x,y,z)表示 x位于 y与 z之间 ,则命题表示为 P(a,b,c).2,如果王英坐在李洪的后面 ,则王英比李红高 .令 a:王英 ;b:李红 ;P(x,y):x坐在 y的后面 ;G(x,y):x比 y高 .则命题表示为 P(a,b)G(a,b).6离 散 数
5、 学 三段论基于谓词的符号化：A(x):x是有理数， B(x):x是实数，则三段论可表示为：P： A(x) B(x) Q： A(1/3) R： B(1/3). P (A(x)B(x) ( A(x) B(x)A(x) B(x)这样， P译为 “所有有理数都不是实数 ” 矛 盾 原 因仅引进谓词还不足以确切地刻画命题，例如 :日常生活中，上述命题 P为 : “凡有理数都是实数 ”。而命题 P的否定 P,应理解成， “有些有理数不是实数 ”但是7离 散 数 学 原因：命题 P的确切意思为： “对任意 x， 如果 x是有理数，则 x是实数 ”。但是，A(x)B(x)中并没有确切表达出 “对任意x”这个
6、意思。这说明， A(x)B(x)还不是一个命题。因此，在一阶逻辑中，除了引进谓词外，还需要引进语句 “对任意 x”， 以及与之对偶的语句 “存在一个 x”。8离 散 数 学 定义 15.1.2：当且仅当对任意 x D， G(x)均为真。当且仅当存在一个 x0 D,使 G(x0)为假。当且仅当存在一个 x0 D ，使 G(x0) 为真； 当且仅当对任意 x D ， G(x)均为假。语句 “对任意 x”称为全称量词，记为 :语句 “存在一个 x”称为存在量词，记为 :设 G（ x） 是一个一元谓词， D是论域。其 真值规定为 :其真值规定如下：9离 散 数 学 两个重要的式子：则，三段论法中的命题 P 及 P可 符号化如下：此时， P确实是命题 “凡有理数都是实数 ”的否定。 当论域 D为有限集时，如 D= a1,a2 ,a n，对于任意一元谓词 G(X)， 都有即消去了量词，化成了命题逻辑中等值的命题公式。注意：x(A(x) B (x)至 P24 10
