《第三章谓词演算基础》由会员分享,可在线阅读,更多相关《第三章谓词演算基础(23页珍藏版)》请在金锄头文库上搜索。
1、第三章 谓词演算基础3.1 谓词与个体谓词与个体3.2 函数与量词函数与量词 3.2.1 函数项函数项 3.2.2 量词量词3.3 自由变元和约束变元自由变元和约束变元 3.4 永真性和可满足性永真性和可满足性3.5 唯一性量词与摹状词唯一性量词与摹状词薄甲悲云诛熔狗挝厦逾婪憨烦崔澎虏里挣命沧钵肺她掣丑摔借鹅投匡狈野第三章谓词演算基础第三章谓词演算基础 项的概念项的概念例例考察谓词考察谓词WRITE(x,y)表示表示x写了写了yuWRITE(Shakespeare,Hamlet)uWRITE(Shakespeare,y)uWRITE(son(Shakespeare),Hamlet)莎士比亚的儿
2、子写了哈姆雷特莎士比亚的儿子写了哈姆雷特变量符号函数!实体渴概获阻冀衫彪来打妻瓷艳谁豆堑彭福锤镶侄芋庭错矽斜贪蚀冰仍贪随俯第三章谓词演算基础第三章谓词演算基础函数项函数项约定用约定用f,g,h等表示抽象的函数项。等表示抽象的函数项。以个体为定义域、以个体为值域的函数以个体为定义域、以个体为值域的函数包括实体、变量符号和函数符号包括实体、变量符号和函数符号项项晤储睡寥粤细屉膨径寥哪怠庄煞诅女受唤绥亨图嚎领鬼帮咸茧桥爽毖某连第三章谓词演算基础第三章谓词演算基础例例 Johns mother is married to his father解:解:记记M(e1,e2)表示表示e1ismarriedt
3、oe2;f(e)表示表示e的的father;m(e)表示表示e的的mother。则原话可以翻译为:则原话可以翻译为:M(m(John),f(John)宪千亩粉骤舜错票灶拱皑洋蝉芍嚏对噎澎副缄时挠茨厚岂青趾翠镶摆融源第三章谓词演算基础第三章谓词演算基础 3.2.2 量词量词l计算机学院学生都是江苏人。计算机学院学生都是江苏人。l计算机学院学生有江苏人。计算机学院学生有江苏人。l计算机学院教师都有学士学位。计算机学院教师都有学士学位。l计算机学院有些教师没有学士学位。计算机学院有些教师没有学士学位。所有人所有人有一些有一些计算机系人(包括教师与学生)计算机系人(包括教师与学生)乾烬婚昼乃娘墙芜砷膀
4、段琴绊耙躲顶杭正被脐语堆位滴樟纂扦搏沛痔紊琼第三章谓词演算基础第三章谓词演算基础全总个体域、全总个体域、量词量词(1) 约定变量符号即个体变元约定变量符号即个体变元x取值于全总个体域取值于全总个体域U;(2) 用谓词来限定用谓词来限定x的取值范围;的取值范围;(3) 引进引进 全称量词全称量词 x “所有的所有的x”、“一切一切x”等概念等概念 存在量词存在量词 x “存在一些存在一些x”、“有一些有一些x”等概念等概念(4) 规定一般情况下规定一般情况下紧跟在全称量词紧跟在全称量词 x之后的主联结词为之后的主联结词为“”,紧跟在存在量词紧跟在存在量词 x之后的主联结词为之后的主联结词为“ ”
5、。惶苹娟陕贩志姬焰搜庆炭路诡两极疤孤辜甜疮誊闪插贤臃戏殃锄翱庇娇报第三章谓词演算基础第三章谓词演算基础例例 计算机学院的有些老师是青年教师计算机学院的有些老师是青年教师解:解:设设C(e)表示表示e为计算机学院的人;为计算机学院的人;T(e)表示表示e为教师为教师; Y(e)表示表示e为青年为青年.则原句译为:则原句译为: x(C(x) T(x) Y(x)此例中:此例中:x就取值于全总个体域就取值于全总个体域U,谓词谓词C(x)限定限定x取值范围。取值范围。赶阐言帮可畅双堆秉困介人杭黄凶衅侵醋暑陕根讶獭呼队穆渣嗡盂逃黑表第三章谓词演算基础第三章谓词演算基础例例 个体域个体域I为为人类集合人类集
6、合,将下列命题符号化将下列命题符号化: (1)凡人都呼吸。凡人都呼吸。(2)有的人用左手写字。有的人用左手写字。解解 (1) (1) 令令F(x):xF(x):x呼吸呼吸. . 则可以翻译为则可以翻译为 x xF(x)F(x)解解 (2) (2) 令令G(x):xG(x):x用左手写字用左手写字. . 则可以翻译为则可以翻译为 x xG(x)G(x) 柔墨渍掖渐雅沾喂扒购程泌朽摔氮蹿裕孝茂幼私彬的泥沂酿块彤隔季禹撤第三章谓词演算基础第三章谓词演算基础例例 个体域个体域I为全总个体域为全总个体域,将下列命题符号化将下列命题符号化: (1)凡人都呼吸。凡人都呼吸。(2)有的人用左手写字。有的人用左
7、手写字。解解 (1) (1) 令令F(x):xF(x):x呼吸呼吸; ; P(x): x P(x): x为人为人. . 则可以翻译为则可以翻译为 x x(P(x)(P(x)F(x)F(x)解解 (2) (2) 令令G(x):xG(x):x用左手写字用左手写字; ; P(x): x P(x): x为人为人. . 则可以翻译为则可以翻译为 x x(P(x)(P(x) G(x)G(x) x x(P(x)(P(x) F(x)F(x) x x (P(x) (P(x) G(x)G(x) ?址悯挎悟霓情邻蒙叮丰枪弓贿汹炎蓑闺贼于滑兽戒符特荔恶膳殊傲儒寨摈第三章谓词演算基础第三章谓词演算基础例例1 某些人对某
8、些食物过敏。某些人对某些食物过敏。解:设解:设A(e)表示表示e为人;为人;B(e)表示表示e为食物;为食物;C(e1,e2)表示表示e1对对e2过敏。过敏。则原句译为:则原句译为: x(A(x) y(B(y) C(x,y)咒泡特庞挺镑孕掷值耕溜桂档诱霸费扇翁捆禹节粗炬舷亢毋支铆勉奈厅懦第三章谓词演算基础第三章谓词演算基础例 试把下列语句翻译为谓词演算公式 (1)所有蜜蜂均喜欢所有的花粉; (10级期末,3分) 解解 记记 B(e)表示表示e为蜂蜜;为蜂蜜; P(e)表示表示e为花粉;为花粉; L(e1,e2)表示表示e1喜欢喜欢e2。 原话可以翻译为:原话可以翻译为: x (B(x) y(P
9、(y) L(x,y)蚁幌蜗挣脚软踢缕僚剁衔浦咱肘徘茨出腆粱汪津局箩李宫本嘘琅斟骗哦绝第三章谓词演算基础第三章谓词演算基础例 试把下列语句翻译为谓词演算公式 (1)并非并非“人不为己,天诛地灭人不为己,天诛地灭”; (06级期末,3分) 解解(1): 设 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)悍添重瞻杉厉逮捶府氯眷平镁珍藤精氖嫉仲逸扼恃拘基壤漳矽铺是驾识楼第三章谓词演算基础第三章谓
10、词演算基础例 试把下列语句翻译为谓词演算公式 (2)有些学生喜欢所有的老师有些学生喜欢所有的老师 。 (06级期末,3分) 解解(2): 设 S(e)表示表示e为学生;学生;T(e)表示表示e为老老师; L(e1,e2)表示表示e1喜喜欢e2。 则原句可以原句可以译为:x(S(x)y(T(y) L(x,y)占肋唆毁活瓜郸正薄茨数街语圃坏柞磊迁弛瑰怖躇帅假美容川菌震像芥鸡第三章谓词演算基础第三章谓词演算基础例 试把下列语句翻译为谓词演算公式(3)凡是对顶角一定相等。凡是对顶角一定相等。 (05级期末,2分) 解解(3): 设 A(e1,e2)表示表示e1与与e2为对顶角;角;E(e1,e2)表示
11、表示e1=e2。 则原句可以原句可以译为: x y(A(x,y)E(x,y)或或 x y(A(x,y)(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)住拣枷墟惺萌篓谴秦霍猖绍勤曰媒屿妊顽檀雇地嵌樱迸胆寒结肌踞横窃寡第三章谓词演算基础第三章谓词演算基础例例4 并非并非
12、“人不为己,天诛地灭人不为己,天诛地灭”。解:设解:设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 任何人均会犯错误。任何人均会犯错误。解:设解:设 P(e)表示表示e为人;为人; M(e)表示表示e为错误;为错误; D(e1,e2)表示表示e1犯犯e2。则原句译为:则原句译为: x
13、(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)蹭她蕉若横灶贯募编励邦叹认檄木屑秘录神轴兄弯褂一此氧纱椎琢撅镣钧第三章谓词演算基础第三章谓词演算基础例例 所有的正数均可开方。所有的正数均可开方。解:解:(i
14、)若个体域为全体正实数若个体域为全体正实数R+,S(X):X可以开方,可以开方,则命题符号化为:则命题符号化为: xS(x)(ii)若个体域为全体实数集若个体域为全体实数集R,G(x,y):xy,则命题符号化为:则命题符号化为: x(G(x,0)S(x)(iii)若若D为全总个体域为全总个体域,R(x):x是实数,则符号化为:是实数,则符号化为: x(R(x)G(x,0)S(x) 臆睫沟时啼凳场敞尚报瞒苫嵌缓默估搁亿复掺限辐痴叠缓辐良鸣爪病漳俗第三章谓词演算基础第三章谓词演算基础例例 没有最大的自然数没有最大的自然数 。解:这句话可以理解为解:这句话可以理解为“对所有对所有x,若,若x是自然是
15、自然数,则存在数,则存在y,y也是自然数,且也是自然数,且yx”。引入引入N(x):x是自然数,是自然数,G(x,y):xy,则符号化为:则符号化为: x(N(x)y(N(y)G(y,x)也可以理解为也可以理解为“下句话是不对的下句话是不对的存在一存在一个个x,x是自然数且对一切自然数是自然数且对一切自然数y,x均大均大于于y”,符号化为,符号化为x(N(x) y(N(y)G(x,y)码咕低由镰豁弯袱臣椎站喻击犬顶智鬃禄硷秧块镁班负尧哲克石跃倍焰黄第三章谓词演算基础第三章谓词演算基础例例 没有最大的自然数没有最大的自然数 。解解2:设设B(x):x是最大的,是最大的,N(x):x是自然数。是自
16、然数。则命题可以表示为:则命题可以表示为:x(B(x)N(x)夫熏瑚谈敛寻炎在搪画纯币志劲汹洲猫淡雪傍监反认祭壳南庐吼呀儿柒溜第三章谓词演算基础第三章谓词演算基础典型错误量词后的主联结词错误将集合名词简单化为常个体. 例如,“人”是集合名词谓词中含有联结词引入谓词来限定常个体. 例如,“我”是常个体值胳严缮谍纬吉褒腔荡凋牟雀料孺蹬扶氮弱孵承开辉留见瞥聪椽耍坟伯衅第三章谓词演算基础第三章谓词演算基础第三章 谓词演算基础3.1 谓词与个体谓词与个体3.2 函数与量词函数与量词 3.2.1 函数项函数项 3.2.2 量词量词3.3 自由变元和约束变元自由变元和约束变元 3.4 永真性和可满足性永真性和可满足性3.5 唯一性量词与摹状词唯一性量词与摹状词覆淑灵羡搅惺殿运驻扰惩噶屑灰渊口沽灼姓盂甚丢碱刷夸昭偿玩拙寨酶谈第三章谓词演算基础第三章谓词演算基础