离散数学第三章 谓词演算基础-函数与量词.ppt

《离散数学第三章 谓词演算基础-函数与量词.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章谓词演算基础3.1谓词与个体3.2函数与量词3.2.1函数项3.2.2量词3.3自由变元和约束变元3.4永真性和可满足性3.5唯一性量词与摹状词复习：项的概念例考察谓词WRITE(x,y)表示x写了y的谓词填式：WRITE(Shakespeare，Hamlet)WRITE(Shakespeare，y)莎士比亚的儿子写了哈姆雷特WRITE(son(Shakespeare)，Hamlet)变量符号函数！实体函数项——以个体为定义域、以个体为值域的函数。约定用f，g，h等表示抽象的函数项。项：包括实

2、体、变量符号和函数符号等,是构成原子公式的一部分(原子公式的定义详见§3.3第28页第-5行)例John’smotherismarriedtohisfather解：记M(e1，e2)表示e1ismarriedtoe2；f(e)表示e的father；m(e)表示e的mother。则原话可以翻译为：M(m(John)，f(John))量词计算机学院学生都是江苏人。计算机学院学生有江苏人。计算机学院教师都有学士学位。计算机学院有些教师没有学士学位。所有人有一些计算机系人（包括教师与学生）全总个体域、量词(

3、1)约定变量符号即个体变元x取值于全总个体域U；(2)用谓词来限定x的取值范围；(3)引进全称量词x表示“所有的x”、“一切x”等，存在量词x表示“存在一些x”、“有一些x”等概念；(4)规定一般情况下紧跟在全称量词x之后的主联结词为“”，紧跟在存在量词x之后的主联结词为“”。试译：计算机学院的有些老师是青年教师。解：设C(e)表示e为计算机学院的人；T(e)表示e为教师;Y(e)表示e为青年.则原句译为：x(C(x)T(x)Y(x))此例中：x就取值于全总个体域U，谓词C(e)限

4、定x取值范围。例1某些人对某些食物过敏。解：设A(e)表示e为人；B(e)表示e为食物；C(e1，e2)表示e1对e2过敏。则原句译为：x(A(x)y(B(y)C(x，y)))例2金子闪光，但闪光的并非全是金子。解：设G(e)表示e为金子；S(e)表示e闪光。则原句译为：x(G(x)S(x))x(S(x)G(x))或x(G(x)S(x))x(S(x)G(x))例3Ifaprogramcannotbetoldafact，thenitcannotlearnthatfact

5、.解：设P(e)表示e为program;F(e)表示e为fact;T(e1，e2)表示e1canbetolde2;L(e1，e2)表示e1canlearne2;则原句译为：xy((P(x)F(y)T(x，y))L(x，y))例4并非“人不为己，天诛地灭”。解：设P(e)表示e为人；A(e1，e2)表示e1为e2；B(e1，e2)表示e1诛e2；C(e1，e2)表示e1灭e2；a表示天；b表示地；则原句译为：x((P(x)A(x,x))(B(a,x)C(b,x)))例5任何人

6、均会犯错误。解：设P(e)表示e为人；M(e)表示e为错误；D(e1，e2)表示e1犯e2。则原句译为：x(P(x)y(M(y)D(x，y)))例6己所不欲勿施于人。解：设P(e)表示e为人；T(e)表示e为东西；W(e1，e2)表示e1要e2；S(e1，e2，e3)表示e1施e2给e3。则原句译为：xy((P(x)T(y)W(x,y))z(P(z)S(x,y,z)))例所有的正数均可开方。解：若个体域为全体正实数R+，S(X)：X可以开方，则命题符号化为：xS(x)(i

7、i)若个体域为全体实数集R，G(x，y)：x>y，则命题符号化为：x((G(x，0)S(x))(iii)若D为全总个体域,R(x):x是实数，则符号化为：x((R(x)∧G(x，0))S(x))例没有最大的自然数。解：这句话可以理解为“对所有x，若x是自然数，则存在y，y也是自然数，且y>x”。引入N(x):x是自然数，G(x,y):x>y,则符号化为：x(N(x)y(N(y)∧G(y,x))也可以理解为“下句话是不对的‘存在一个x，x是自然数且对一切自然数y，x均大于y’”，符号化为

8、x(N(x)∧y(N(y)G(x,y))设B(x):x是最大的，N(x):x是自然数。则命题可以表示为：x(B(x)∧N(x))✘第三章谓词演算基础3.1谓词与个体3.2函数与量词3.2.1函数项3.2.2量词3.3自由变元和约束变元3.4永真性和可满足性3.5唯一性量词与摹状词