第2章谓词逻辑习题(最新)

应用离散数学谓词逻辑第2章：谓词逻辑§2.1个体词、谓词与量词习题2.11.将下列命题用0元谓词符号化。（1）小王学过英语和法语。（2）2大于3仅当2大于4。（3）3不是偶数。（4）2或3是质数。（5）除非李键是东北人，否则他一定怕冷。解：(1)令)(xP：x学过英语，Q(x)：x学过法语，c：小王，命题符号化为)()(cQcP(2)令),(yxP：x大于y,命题符号化为)3,2()4,2(PP(3)令)(xP：x是偶数，命题符号化为)3(P(4)令)(xP：x是质数，命题符号化为)3()2(PP(5)令)(xP：x是北方人；)(xQ：x怕冷；c：李键；命题符号化为)()(xPcQ2.设个体域}{cbaD，，，消去下列各式的量词。（1）))()((yQxPyx（2）))()((yQxPyx（3）)()(yyQxxP（4）))()((yyQyxPx，解：(1)中))()(()(yQxPyxA，显然)(xA对y是自由的，故可使用UE规则，得到))()(()(yQyPyyA，因此))()(())()((yQyPyyQxPyx，再用ES规则，)()())()((zQzPyQyPy，Dz，所以)()())()((zQzPyQxPyx（2）中))()(()(yQxPyxA，它对y不是自由的，故不能用UI规则，然而，对)(xA中约束变元y改名z，得到))()((zQxPz，这时用UI规则，可得：))()((yQxPyx))()((zQxPzx))()((zQxPz（3）略（4）略3.设谓词)(yxP，表示“x等于y”，个体变元x和y的个体域都是}321{，，D。求应用离散数学谓词逻辑下列各式的真值。（1）)3(，xxP（2）)1(yyP，（3）)(yxyPx，（4）)(yxyPx，（5）)(yxyPx，（6）)(yxxPy，解：（1）当3x时可使式子成立，所以为Ture。（2）当1y时就不成立，所以为False。（3）任意的x,y使得yx，显然有yx的情况出现，所以为False。(4)存在x,y使得yx，显然当1,1yx时是一种情况，所以为Ture。(5)存在x，任意的y使得yx成立，显然不成立，所以为False。(6)任意的y，存在x，使得yx成立，显然不成立，所以为False。4.设下面所有的个体变元的个体域都是整数集合，用自然语言表达下列各式并确定其真值。（1）)0(2nn（2）)2(2nn（3）)(2nnn（4）)(2mnmn（5）)(2mnmn（6）)0(mnmn（7）)(mmnmn（8）)5(22mnmn（9）)6(22mnmn（10）)14(mnmnmn（11）)24(mnmnmn（12）)2/)((mnkkmn解：(1)任意的整数n使得02n成立。因为02n是永真式，所以其值为Ture。(2)存在这样的整数n使得22n成立。因为不存在整数使得22n成立，所以其值为False。(3)任意的整数n使得nn2成立。因为n是整数，所以nn2恒成立，所以其值为Ture。(4)任意的整数n，存在m使得mn2成立。只要m就能使式子恒成立，所以其值为Ture。(5)任意的整数m，存在n使得2mn成立。只要0n就能使式子恒成立，所以其值为Ture。(6)任意的整数n，存在m使得0mn成立。只要nm就能使式子恒成立，所以应用离散数学谓词逻辑其值为Ture。(7)任意的整数m，存在n使得mmn成立。只要1n就能使式子恒成立，所以其值为Ture。(8)存在这样的整数n，m使得522mn成立。显然存在这样的整数m,n，当2,1mn时即可使式子成立，所以其值为Ture。(9)存在这样的整数n，m使得622mn成立，通过分析可知不存在这样的m,n,所以其值为False。(10)任意的整数m，存在n使得14mnmn和同时成立，只要2/3m，任意的n都不能使式子成立，所以其值为False。(11)任意的整数m，存在n使得24mnmn和同时成立，只要1m，任意的n都不能使式子成立，所以其值为False。(12)任意的整数m,n，存在整数k使得2/)(mnk成立，因为只要m,n一个为偶数，另一个为奇数，就使得k为非整数，所以其值为False。5.令谓词)(yxP，表示“x访问过y”，其中x的个体域是学校全体学生，y的个体域是所有网站的集合。用自然语言表达下列各式。（1）)...(cneduhziee，方华。（2）)..(comgoogle，。（3）)(yyP，冯友。（4）))()((yPyPy，，钱华吴笛。（5）)))()((zyPzPyzy，，（黄帅黄帅。（6）)))()(()((zyPzxPyxzyx，，。解：（1）方华已经访问过。（2）至少有一人已经访问过。（3）冯友已经至少访问过一个网站了。（4）至少友一个网站是吴笛和钱华都访问过的。（5）除了黄帅以外还有一个人访问过黄帅已经访问过的所有网站。（6）有两个不同的人已经访问过完全同样的网站。6.令谓词)(xP表示“x说德语”，)(xQ表示“x了解计算机语言C++”，个体域为杭电全体学生的集合。用)(xP、)(xQ、量词和逻辑联接词符号化下列语句。（1）杭电有个学生既会说德语又了解C++。应用离散数学谓词逻辑（2）杭电有个学生会说德语，但不了解C++。（3）杭电所有学生或会说德语，或了解C++。（4）杭电没有学生会说德语或了解C++。假设个体域为全总个体域，谓词)(xM表示“x是杭电学生”。用)(xP、)(xQ、)(xM、量词和逻辑联接词再次符号化上面的4条语句。解：（ⅰ）个体域为杭电全体学生的集合时：（1）))()((xQxPx（2）))()((xQxPx（3）))()((xQxPx（4）))()((xQxPx（ⅱ）假设个体域为全总个体域，谓词)(xM表示“x是杭电学生”时：（1）))()()((xQxPxMx（2）))()()((xQxPxMx（3）)))()(()((xQxPxMx（4）)))()(()((xQxPxMx7.令谓词)(yxP，表示“x爱y”，其中x和y的个体域都是全世界所有人的集合。用)(yxP，、量词和逻辑联接词符号化下列语句。（1）每个人都爱王平。（2）每个人都爱某个人。（3）有个人人都爱的人。（4）没有人爱所有的人。（5）有个张键不爱的人。（6）有个人人都不爱的人。（7）恰有一个人人都爱的人。（8）成龙爱的人恰有两个。（9）每个人都爱自己。（10）有人除自己以外谁都不爱。解：a：王平b：张键c：张龙(1)）axxP,((2)),(yxyPx(3)),(yxxPy(4)),(yxPyx(5))(xbPx，(6)),(yxPyx(7))))),(((),((xzzPzxyyPx(8))))()(()(),((yzxzzcPzcPxcPyxyx，(9)),(xxxP(10))),((yxyxPyx8.令谓词)(yxP，表示“x给y发过电子邮件”，)(yxQ，表示“x给y打过电话”，其应用离散数学谓词逻辑中x和y的个体域都是实验班所有同学。用)(yxP，、)(yxQ，、量词和逻辑联接词符号化下列语句。（1）周叶从未给李强发过电子邮件。（2）方芳从未给万华发过电子邮件，或打过电话。（3）实验班每个同学都给余涛发过电子邮件。（4）实验班没有人给吕键打过电话。（5）实验班每个人或给肖琴打过电话或给他发过电子邮件。（6）实验班有个学生给班上其他人都发过电子邮件。（7）实验班有个学生给班上其他人或打过电话，或发过电子邮件。（8）实验班有两个学生互发过电子邮件。（9）实验班有个学生给自己发过电子邮件。（10）实验班至少有两个学生，一个给另一个发过电子邮件，而另一个给这个打过电话。解：a：周叶b：李强c：方芳d：万华e：余涛:f吕健:g肖琴（1）），baP(（2）），（），（dcQdcP（3））exxP,(（4））fxQx,(（5））））（gxQgxPx,(,(（6）)),((yxPxyyx（7）))),(),(((yxQyxPxyyx（8）)),(),((yxQyxPyxyx（9）),(,xxPx（10）)),(),((xyQyxPyxyx§2.2谓词公式及其解释习题2.21.指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。（1）))()((yxQxPx，（2）)()(yxyQyxxP，，（3）)())()((zyxxRzyQyxPyx，，，，解：（1）x是指导变元，x的辖域是),()(yxQxP，对于x的辖域而言，x是约束变应用离散数学谓词逻辑元，y是自由变元。（2）x,y都为指导变元，x的辖域是)()(yxyQyxP，，，y的辖域是)(yxQ，；对于x的辖域而言，x,y都为约束变元，对于y的辖域而言，x是自由变元，y是约束变元。（3）x,y为指导变元，x的辖域是)())()((zyxxRzyQyxPy，，，，，y的辖域是)())()((zyxxRzyQyxP，，，，，x的辖域是)(zyxR，，；对于x的辖域而言，x,y为约束变元，z为自由变元，对于y的辖域而言，z为自由变元，y为约束变元，x即为约束变元也为自由变元，对于x的辖域而言，x为约束变元，y,z是自由变元。在整个公式中，x,y即为约束变元又为自由变元，z为自由变元。2.设个体域}21{，D，请给出两种不同的解释1I和2I，使得下面谓词公式在1I下都是真命题，而在2I下都是假命题。（1）))()((xQxPx（2）))()((xQxPx解：①解释1I：个体域}21{，D，0:)(,0:)(''xxQxxP。②解释2I：个体域}21{，D，2:)(,0:)(''xxQxxP。3.对下面的谓词公式，分别给出一个使其为真和为假的解释。（1）)))()(()((yxRyQyxPx，（2）)),()()((yxRyQxPyx解：（1）成真解释：个体域D＝{1,2,3},0:)('iiP,2:)('iiQ,3:),('jijiR,其中i,j是D中的元素。成假解释：个体域D＝{1,2,3},0:)('iiP，2:)('iiQ，1:),('jijiR，其中i,j是D中的元素。（2）成真解释：个体域D＝{1,2,3}，0:)('iiP，2:)('iiQ，3:),('jijiR，其中i,j是D中的元素。成假解释：个体域D＝{1,2,3},0:)('iiP，0:)('iiQ，1:),('jijiR，其中i,j是D中的元素。4.给定解释I如下：个体域RD（这里R为实数集合）。个体常元0a。二元函数yxyxf)(，。二元谓词yxyxP：，)(，yxyxQ：，)(。在解释I下，下列公式的含义是什么？哪些成为命题哪些不成为？成为命题的其真值又如应用离散数学谓词逻辑何？（1）))()((yxPyxQyx，，（2）))())(((yxQayxfPyx，，，（3）)))(()((ayxfPyxQyx，，，（4）))())(((yxPayxfQyx，，，解：（1）公式被解释成“)(yxyxyx”，为真命题。（2）公式被解释成“)0(yxyxyx”，它没有确切的真值，不是命题。（3）公式被解释成“)0(yxyxyx”，为真命题。（4）公式被解释成“)