离散数学之谓词逻辑

《离散数学之谓词逻辑》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.1　谓词的概念与表示命题逻辑的局限性：下列推理：凡是人都是要死的。苏格拉底是人。苏格拉底是要死的。众所周知，这是真命题。但在命题逻辑中(P∧Q)R，难证其为重言式。原因：命题逻辑不考虑命题之间的内在联系和数量关系。办法：将命题再次细分。2.1　谓词的概念与表示谓词在反映判断的句子中，用以刻划客体的性质或关系的即是谓词。例：(1)3是有理数。　(2)x是无理数。(3)阿杜与阿寺同岁。(4)x与y有关系L。其中，“是有理数”、“是无理数”、“与…同岁”、“…与…有关系L”均为谓词。前两个是指明客体性质的谓词，后两个是指

2、明两个客体之间关系的谓词。2.1　谓词的概念与表示将上述谓词分别记作大写字母F、G、H、L，用小写字母表示客体名称，则上述可表示为：(1)F(3)　　　　(2)G(x)(3)H(a,b)　　a:阿杜b:阿寺(4)L(x,y)谓词填式单独一个谓词不是完整的命题，把谓词字母后填以客体所得的式子称为谓词填式。2.1　谓词的概念与表示n元谓词由n个客体插入到固定位置上的谓词填式。例如：A(b)称作一元谓词，B(a,b)称作二元谓词，L(a,b,c)称作三元谓词，P(x1,x2,…,xn)称作n元谓词。注意：代表客体名称的字母，它

3、在多元谓词中出现的次序是固定的，与事先约定的次序有关，如L(a,b,c)和L(b,c,a)代表两个不同的命题。2.2　命题函数与量词例：H是谓词“能够到达山顶”，t表示老虎，c表示汽车，z表示张三，那么H(t),H(c),H(z)表示三个不同的命题，但它们有一个共同的形式H(x)，当x分别取t,c,z时。L(x,y)表示“x小于y”，那么L(2,3)表示了一个真命题“2小于3”，而L(5,1)表示假命题“5小于1”。可以看出，L(x,y)本身不是一个命题，只有当变元x,y取特定的客体时，才是一个命题。2.2　命题函数与量

4、词简单命题函数由一个谓词，一些客体变元组成的表达式称为简单命题函数。n元谓词就是有n个客体变元的命题函数。不带任何客体变元的谓词称为0元谓词。复合命题函数由一个或n个简单命题函数以及逻辑联结词组合而成的表达式称复合命题函数。2.2　命题函数与量词命题函数不是一个命题，只有客体变元取特定名称时，才能成为一个命题。但客体变元在哪些范围内取特定的值，对是否成为命题及命题的真值极有影响。例：R(x)表示“x是大学生”，如果x的讨论范围是某大学里班级中的学生，则R(x)是永真式。如果x的讨论范围是某中学里班级中的学生，则R(x)是

5、永假式。如果x的讨论范围为一剧场中的观众，那么对某些观众，R(x)为真，对另一些观众，R(x)为假。2.2　命题函数与量词个体可以独立存在的具体的或抽象的客体。个体常量：具体的或特定的，一般用a,b,c,…表示。个体变元：抽象的或泛指的，一般用x,y,z,…表示。个体域个体变元的论述范围。全总个体域把各种个体域综合在一起作为论述范围的域。2.2　命题函数与量词量词用来表示个体常量或变元之间数量关系的词。量词分为两种：全称量词　表示“一切”,“所有”,“凡”,“每一个”,“任意”等意的词称为全称量词，记作。如：x表示个

6、体域内所有的x。存在量词　表示“某个”,“对于一些”,“存在一些”,“至少有一个”等意的词称为存在量词，记作。如：y表示个体域内存在一些y。2.2　命题函数与量词例：用谓词表达式写出下列命题。(1)凡是人都呼吸。(2)有的人是左撇子。解：令F(x)：x呼吸。G(x)：x是左撇子。当个体域为人类集合时：(1)xF(x)(2)xG(x)当个体域为全总个体域时：令M(x)：x是人。(1)x(M(x)F(x))(2)x(M(x)∧G(x))2.2　命题函数与量词约定：以后如不指定个体域，默认为全总个体域。特性谓词　

7、在讨论带有量词的命题函数时，必须确定其个体域。当使用全总个体域时，对客体变元的变化范围限制的词，称作特性谓词。如上例中，M(x)为F(x)和G(x)的特性谓词，它限定了变元x的范围。一般，对全称量词，特性谓词常作条件的前件；对存在量词，特性谓词常作合取项。2.2　命题函数与量词例：将下列命题符号化，并讨论其真值。(1)所有的人都长头发。解:令M(x):x是人。F(x):x长头发。则x(M(x)F(x))真值为0(2)有的人吸烟。解:令M(x):x是人。S(x):x吸烟。则x(M(x)∧S(x))真值为12.2　命题

8、函数与量词(3)没有人登上过木星。解:令M(x):x是人。D(x):x登上过木星。则x(M(x)∧D(x))真值为1(4)清华大学的学生未必都是高素质的。解:令Q(x):x是清华大学的学生。H(x):x是高素质的。则x(Q(x)H(x))真值为1或x(Q(x)∧H(x))可见，有些命题的符号化形式不止一