应用离散数学（第4版）（微课版）习题及答案 周丽 习题2

应用离散数学谓词逻辑杭电－周丽、方景龙第二章PAGE4PAGE第2章：谓词逻辑 §2.1个体词、谓词与量词习题2.11.将下列命题用0元谓词符号化。（1）小王学过英语和法语。 （2）2大于3仅当2大于4。 （3）3不是偶数。 （4）2或3是质数。（5）除非李键是东北人，否则他一定怕冷。解（1）令：学过英语，：学过法语，：小王，命题符号化为。（2）令：大于y，命题符号化为。（3）令：是偶数，a:3，命题符号化为¬P（a）。（4）令：是质数，a:2，b:3，命题符号化为P（a）∨P（a（5）令：是东北人；：怕冷；：李键；命题符号化为。 2.设下面所有的个体变元的个体域都是整数集合，用自然语言表达下列各式并确定其真值。 （1） （2） （3） （4） （5） （6） （7） （8） （9） （10） （11） （12）解（1）对任意的整数n有。其值为1。（2）存在整数n使得。其值为0。（3）对任意的整数n有。其值为1。（4）对任意的整数n，存在整数m使得。其值为1。（5）存在整数n使得对任意的整数m都有。其值为0。（6）对任意的整数n，存在整数m使得。其值为1。（7）存在整数n使得对任意的整数m都有。其值为1。（8）存在这样的整数n，m使得。其值为1。（9）存在这样的整数n，m使得。其值为0。（10）存在整数n使得对任意的整数m都有。其值为0。（11）存在整数n使得对任意的整数m都有。其值为0。（12）对任意的整数m，n，存在整数k使得。其值为0。 3.令谓词表示“访问过”，其中的个体域是学校全体学生，的个体域是所有网站的集合。用自然语言表达下列各式。 （1）。 （2）。 （3）。 （4）。 （5）。 （6）。解（1）方元访问过。（2）至少有一个学生访问过。（3）冯友至少访问过一个网站。（4）至少有一个网站是吴笛和钱华都访问过的。（5）有另外一个学生访问过黄帅访问过的所有网站。（6）至少有两个不同的学生访问过的网站完全相同。4.令谓词表示“说德语”，表示“了解计算机语言C++”，个体域为杭电全体学生的集合。用、、量词和逻辑联接词符号化下列语句。 （1）杭电有个学生既会说德语又了解C++。 （2）杭电有个学生会说德语，但不了解C++。 （3）杭电所有学生或会说德语，或了解C++。 （4）杭电没有学生会说德语或了解C++。 假设个体域为全总个体域，谓词表示“是杭电学生”。用、、、量词和逻辑联接词再次符号化上面的4条语句。解个体域为杭电全体学生的集合时：（1）（2）（3）（4） 若个体域为全总个体域，谓词表示“是杭电学生”，则：（1）（2）（3）（4）5.令谓词表示“爱”，其中和的个体域都是全世界所有人的集合。用、量词和逻辑联接词符号化下列语句。 （1）每个人都爱王平。 （2）每个人都爱某个人。 （3）有个人人都爱的人。 （4）没有人爱所有的人。 （5）有个张键不爱的人。 （6）有个人人都不爱的人。 （7）恰有一个人人都爱的人。 （8）成龙爱的人恰有两个。 （9）每个人都爱自己。 （10）有人除自己以外谁都不爱。 解（1）a:王平，∀xP(x,a)。 （2）∀x∃yP(x,y)。 （3）。 （4）。 （5）b:张健，xP(b，x)。 （6）。 （7） （8）c:成龙，∃x∃y(P(c,x)∧P(c,y)∧x≠y （9）。 （10）。 6.令谓词表示“给发过电子邮件”，表示“给打过电话”，N（x,y）表示“x不是y”，个体域都是实验班所有同学。用、、N（x,y）、量词和逻辑联接词符号化下列语句。 （1）周叶从未给李强发过电子邮件。 （2）方芳从未给万华发过电子邮件，或打过电话。 （3）实验班每个同学都给余涛发过电子邮件。 （4）实验班没有人给吕键打过电话。 （5）实验班每个人或给肖琴打过电话或给他发过电子邮件。 （6）实验班有个学生给班上其他人都发过电子邮件。 （7）实验班有个学生给班上其他人或打过电话，或发过电子邮件。 （8）实验班有两个学生互发过电子邮件。 （9）实验班有个学生给自己发过电子邮件。 （10）实验班至少有两个学生，一个给另一个发过电子邮件，而另一个给这个打过电话。解（1）a:周叶，b:李强，¬P（a,b（2）a:方芳，b:万华，¬P（（3）a:余涛，∀xP(x,a)（4）b:吕健，xQ(x，b)（5）a:肖琴，∀x（P(x,a)∨Q(x,a)）（6）∃x∀y（N（x,y）→P(x,y)）（7）∃x∀y（N（x,y）→(P(x,y)∨Q(x,y)）（8）∃x∃y（N（x,y）∧P(x,y)∧P(y,x)（9）（10）∃x∃y（N（x,y）∧P(x,y)∧Q(y,x)§2.2谓词公式及其解释习题2.21.指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。 （1） （2） （3）解（1）中的x是指导变元；量词的辖域是，其中x是约束变元，y是自由变元。（2）中的x，中的y都是指导变元；的辖域是，的辖域是；其中中的x是的约束变元，y是自由变元；中的x是自由变元，y是约束变元。（3）中的x，中的y以及中的x都是指导变元；的辖域是，的辖域是，的辖域是；其中中的x，y都是约束变元；中的y是约束变元；z是自由变元，中的x为约束变元，y，z是自由变元。2.设个体域，请给出两种不同的解释和，使得下面谓词公式在下都是真命题，而在下都是假命题。（1） （2）解（1）解释：个体域，。（2）解释：个体域，。3.对下面的谓词公式，分别给出一个使其为真和为假的解释。（1）（2）解（1）成真解释：个体域D＝{1,2,3},,,。成假解释：个体域D＝{1,2,3},，，。（2）成真解释：个体域D＝{1,2,3}，，，。成假解释：个体域D＝{1,2,3},，，。4.给定解释如下： 个体域（这里为实数集合）。 个体常元。 二元函数。 二元谓词，。 在解释下，下列公式的含义是什么？哪些成为命题哪些不成为？成为命题的其真值又如何？ （1） （2） （3） （4）解（1）公式被解释成“”，为真命题。（2）公式被解释成“”，为假命题。（3）公式被解释成“”，为真命题。（4）公式被解释成“”，为假命题。5.判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。 （1） （2） （3） （4） （5） （6） （7） （8） （9） （10）解（1）因为当存在某个使取1时一定取1，所以公式是为永真式。（2）因为当=1时，只能说明存在某个使取1，并不能说明都为1，所以公式是为可满足式。（3）取解释：个体域为自然数集合，。在下公式的前件与后件均为真，所以公式为真，即不是永假式。取解释：个体域仍为自然数集合，但取为。在下公式不成为命题，即不是永真式。综合知公式为可满足式。（4）因为当∀xP(x)取值为1时，说明所有的P(x)值都为1，因此公式是永真式。（5）取解释：个体域为自然数集合，。在下，对任意的，为真而为假，所以公式为假，即不是永真式。取解释：个体域仍为自然数集合，但取为。在下，对任意的，为假而为真，所以公式为真，即不是永假式。综合知公式为可满足式。（6）若xyP(x,y)=1时，说明对任意的x和任意的y都有P(x,y)=1，也就说明了对任意的y和任意的x也都有P(x,y)=1，也就是说yxP(x,y)=1，从而公式为永真式。（7）公式为永真式，用非形式化的反证法证明如下：若公式非永真，则存在一个解释，使得取1而取0。取0表明存在某对使得取0，从而也应取0。这与前面说取1矛盾。故公式是永真式。（8）取解释I：个体域D={1,2,3}，谓词P(x,y):x=y，在I下，∀x∃yP(x,y)=1，但是∃x∀yP(x,y)=0，因此公式为可满足式。（9）设为任意一个解释，个体域为。若取1，即存在，使得为真，从而为真，故为真。所以在解释下公式为真，由的任意性可知，公式为永真式。（10）取解释I：个体域D={1,2,3}，谓词P(x,y):x>y，在I下，=0，但是若取解释I’：个体域D={1,2,3}，谓词P(x,y):x=y，在I下，=1，因此公式为可满足式。6.判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。 （1）（2）（3）（4）（5）（6）（7）解任给解释I（相应的个体域为D），在I下，若∀x（P(x)∧Q（x为真。若∀x（P(x)∧Q（x）)=1时，则对任意的x，P(x)∧Qx=1，也就是说对任意的x，P(x)=1且Qx=1，即∀xP(x)=1且∀xQ(x)=1，也就是∀xP(x)∧（2）若有一个解释I（相应的个体域为D），在I下，若∀x（P(x)∨Q（x）)=0时，公式的值为真。若∀x（P(x)∨Q（x）)=1时，则对任意的x，P(x)∨Qx=1，举个例子，若a,b是个体域中的元素，P(a)=1，Pb=0，Qa=0,Qb=1,虽然满足P(a)∨Q（a）=1，但是∀xP(（3）该谓词公式是(p→q)∧q的代换实例,所以该谓词公式是永假式。（4）用反证法，若公式非永真，则存在一个解释，使得对某个有取1而取0。取0表明取1而取0，即存在某个使取0，从而取0。这与前面说取1矛盾。故公式是永真式。（5）用反证法，若公式非永真，则存在一个解释，使得为0，则∀xPx→Qx=1且Px→∀xQx=0，Px→∀xQx取0表明Px取1而取0，即存在某个使取0，前面的∀xPx→Q（6）该谓词公式是(p→（q→p）)的代换实例,所以该谓词公式是永假式。（7）该谓词公式是p→（q→p）的代换实例,所以该谓词公式是永真式。 7.给出一个非闭式的永真式，给出一个非闭式的永假式，给出一个非闭式的可满足式。解（1）永真式（2）永假式（3）P(x)可满足式§2.3谓词公式的等价演算习题2.31.将下列命题符号化，要求用两种不同的等价形式。（1）没有小于负数的正数。 （2）相等的两个角未必都是对顶角。解（1）令F(x)：x小于负数，G(x)：x是正数.x(F(x)G(x))=x(F(x)G(x))=x(F(x)G(x))（2）令F(x,y)：x和y角相等，G(x,y)：x和y是对顶角。xy(F(x,y)G(x,y))=xy(F(x,y)G(x,y))=xy(F(x,y)G(x,y))2.利用非形式化方法证明下列等价式。 （1） （2）（3） （4）解（1）任给解释（相应的个体域记为），在下，若xA(x)取值0，则xA(x)取值1，因此存在，使得取值1，即取值0，从而xA(x)取值0；若xA(x)取值1，则xA(x)取值0，因此对任意的，都取值0，即对任意的，都取值1，从而xA(x)取值1。由解释I的任意性可知（1）式成立。（2）任给解释（相应的个体域记为），在下，若x(A(x)B)取值1，则对任意的，都有A(x)B取值1，也就是分二种情况：对任意的，都有A(x)取值1或B=1，得xA(x)=1或B=1，以上二种情况都能得到xA(x)B=1。若x(A(x)B)取值0，则存在a∈D，A(a)B取值0，即存在a∈D，A(a)取值0并且B也取值0，得xA(x)=0且B=0，因此xA(x)B=0。由解释的任意性知（2）式成立。（3）任给解释（相应的个体域记为），在下，若x(A(x)∧B)取值0，则对任意的，都有A(x)∧B取值0，也就是分二种情况：对任意的，都有A(x)取值0或B=0，得xA(x)=0或B=0，以上二种情况都能得到xA(x)∧B=0。若x(A(x)∧B)取值1，则存在a∈D，A(a)∧B取值1，即存在a∈D，A(a)取值1并且B也取值1，得xA(x)=1且B=1，因此xA(x)∧B=1。由解释的任意性知（3）式成立。（4）任给解释（相应的个体域记为），在下，若x(A(x)B)取值0，则对任意的，都有A(x)B取值0，即对任意的，都有A(x)取值0且B=0，得xA(x)=0且B=0，因此xA(x)B=0。若x(A(x)B)取值1，则存在a∈D，A(a)B取值1，也就是分二种情况：存在a∈D，A(a)=1或B=1，得xA(x)=1或B=1，以上二种情况都能得到xA(x)B=1。由解释的任意性知（4）式成立。（5）任给解释（相应的个体域记为），在下，若x(A(x)B(x))取值0，则对任意的，都有A(x)B(x)取值0，即对任意的，都有A(x)取值0且任意的，B(x)=0，得xA(x)=0且xB(x)=0，因此xA(x)xB(x)=0。若x(A(x)B(x))取值1，则存在a∈D，A(a)B(a)取值1，也就是分二种情况：存在a∈D，A(a)=1或存在a∈D，B(a)=1，得xA(x)=1或xB(x)=1，以上二种情况都能得到xA(x)xB(x)=1。由解释的任意性知（5）式成立。3.设、和都是谓词，证明下列各等价式（1）（2）（3）（4）证明：（1）左边＝ ＝右边（2）左边＝＝右边（3）左边＝＝右边（4）左边＝ ＝＝＝＝右边§2.4谓词公式的推理演算习题2.41.利用非形式化证明方法或等价演算法证明如下推理关系：（1）（2）（3）（4）（5）（6）解（1）因为∀x(A(x)→B(x))→∃x(A(x)→B(x))=∀x(A(x)→B(x))∃x(A(x)→B(x=∃x(A(x)→B(x))∃x(A(x)→B(x))=∃x（(A(x)→B(x))(A(x)→B(=1因此推理成立。（2）因为（∃xA(x)→∀xB(x))→（∀xA(x)→∀xB(x))=（∃xA(x)∀xB(x))=（∃xA(x)∀xB(x=11=1（3）因为（∃xA(x)→∀xB(x))→（∀xA(x)→∃xB(x))=（∃xA(x)∀xB(x))=（∃xA(x)∃=11=1（4）因为（∃xA(x)→∃xB(x))→（∀xA(x)→∃xB(x))=（∃xA(x)∃xB(x))=（∃xA(x)=11=1（5）因为（∃xA(x)→∀xB(x))→（∃xA(x)→∃xB(x))=（∃xA(x)∀xB(x))=（∃xA(x)∃=11=1（6）因为（∀xA(x)→∀xB(x))→（∀xA(x)→∃xB(x))=（∀xA(x)∀xB(x))=（∀xA(x)∃=11=12.指出下面演绎推理中的错误，并给出正确的推导过程。（1）① P规则② US规则：①（2）① P规则② US规则：①（3）① P规则② ES规则：①（4）① P规则 ② UG规则：①（5）① P规则 ② EG规则：①（6）① P规则 ② EG规则：①解因为第1步不是前束范式，不能直接用US规则，改为1）xP(x)Q(x)P规则2）x（P(x)Q(y)）E规则，1）3）P(z)Q(y)US规则：2)（2）要同时用a或者b代，改为1） P规则P(a)Q(a)US规则：1)（3）因为第1步不是前束范式，而且化成等价的前束范式后，有自由变元，不能用ES规则，改为1） P规则2）x（P(y)Q(x)）E规则：1）（4）不能用UG规则，只能用EG规则，改为1） P规则2）x（P(x)G(x)）EG规则：1）（5）a,b是不同的常元，要分开引进存在量词。改为1） P规则2）x（P(x)G(b)）EG规则，1）3）yx（P(x)G(y)）EG规则，2）（6）可以同时引进存在量词或者全称量词，二者不可分开。改为1） P规则2）x（P(x)Q(x)）EG规则，1）3.指出下面演绎推理中的错误，并给出正确的推导过程。（1） P规则（2） US规则：（1）（3） ES规则：（2）（4） UG规则：（3）（5） US规则：（4）解错误出现在步骤（3）。因为中含有自由变元，所以不能使用ES规则得到。正确的推导过程为：（1） P规则（2） US规则：（1）4.指出下面演绎推理中的错误，并给出正确的推导过程。（1） P规则（2） US规则：（1）（3） P规则（4） ES规则：（3）（5） T规则：（2），（4）（6） EG规则：（5）解错误出现在步骤（4）。使用ES规则得到的中的已经出现在前面的公式中，所以错误，正确的推导过程为：（1） P规则（2） US规则：（1）（3） P规则（4） ES规则：（3）5.用演绎法证明下列推理式（1）（2）（3）（4）证明（1）式的证明：（1） 附加前提（2） （1），US规则（3） P规则 （4） （3），US规则（5） （2），（4），T规则 （6） （5），EG规则根据附加前提法知 （2）式的证明：（1） 附加前提（2） （1），E规则（3） （2），E规则（4） （3），T规则（5） （4），US规则（6） （5），EG规则（7） P规则 （8） （6），（7），T规则（9） （8），ES规则（10） （3），T规则（11） （10），US规则（12） （9），（11），T规则（13）0 （12），E规则所以根据附加前提法知 （3）式的证明：（1） 附加前提（2） （1），US规则（3） P规则 （4） （3），US规则（5） （2），（4），T规则（6） （5），EG规则所以根据附加前提法知 （4）式的证明（1）¬∃x(A(x)→B(x))CP规则（2）∀x¬(¬A(x)∨B(x))E规则，(1)（3）∀x(A(x)∧¬B(x))E规则，(2)（4）A(a)∧¬B(a)ES规则，(3)（5）¬B(a)T规则，(4)（6）A(a)T规则，(4)（7）∃xA(x)EG规则，(6)（8）∃xA(x)→∀xB(x)P规则（9）∀xB(x)T规则，(7)(8)（10）B(a)US规则，(9)（11）B(a)∧¬B(a)T规则，(5)(10)（12）0E规则，(11)6.用演绎法证明下列推理式（1）∃xP(x)→∀y((P(y)∨Q(y))→R(y)))，∃xP(x)⇒∃xR(x)（2）（3）（4）证明（1）式的证明：（1）∃xP(x)P规则（2）P(a)ES规则，（1）（3）∃xP(x)→∀y((P(y)∨Q(y))→R(y)))P规则（4）∀y((P(y)∨Q(y))→R(y)))T规则，（1）（3）（5）(P(a)∨Q(a))→R(a)UG规则，（4）（6）P(a)∨Q(a)T规则，（2）（7）R(a)T规则，（5）（6）（8）∃xR(x)EG规则，（7）（2）式的证明：（1） P规则（2） （1），ES规则（3） 附加前提（4） （3），E规则（5） （4），US规则（6） （2），（5），T规则（7） P规则 （8） （7），US规则（9） （2），（8），T规则（10） （9），T规则（11） （6），（10），T规则（12）0 （11），E规则所以根据附加前提法知 （3）式的证明：∀x(P(x)∨Q(x)),¬∃xQ(x)⇒∃xP(x)（1）¬∃xQ(x)P规则（2）∀x¬Q(x)E规则，(1)（3）¬Q(y)US规则，(2)

（4）∀x(P(x)∨Q(x))P规则（5）P(y)∨Q(y)US规则，(4)（6）P(y)T规则，(3)(5)（7）∃xP(x)EG规则，(6)（4）式的证明：（1） P规则（2） （1），US规则（3） P规则（4） （3），US规则（5） （2），（4），T规则（6） P规则（7） （3），US规则（8） （5），（7），T规则（9） （8），UG规则7.将下列命题符号化，并用演绎推理法证明其结论是有效的。 （1）有理数、无理数都是实数；虚数不是实数。因此，虚数既不是有理数，也不是无理数。（个体域取全总个体域） （2）所有的舞蹈者都很有风度；万英是个学生并且是个舞蹈者。因此，有些学生很有风度。（个体域取人类全体组成的集合） （3）每个喜欢步行的人都不喜欢骑自行车；每个人或者喜欢骑自行车或者喜欢乘汽车；有的人不喜欢乘汽车。所以有的人不喜欢步行。（个体域取人类全体组成的集合） （4）每个旅客或者坐头等舱或者坐经济舱；每个旅客当且仅当他富裕时坐头等舱；有些旅客富裕但并非所有的旅客都富裕。因此有些旅客坐经济舱。（个体域取全体旅客组成的集合）解（1）命题符号化为：P（x）:x是有理数，Q（x）:x是无理数，R（x）:x是实数，T（x）:x是虚数。前提：∀x(P(x)→R(x))，∀x(Q(x)→R(x))，∀x(T(x)→¬R(x))结论：∀x(T(x)→（¬P(x)∧¬Q(x))1）∀x(P(x)→R(x))P规则2）P(y)→R(y)US规则，1）3）∀x(Q(x)→R(x))P规则4）Q(y)→R(y)US规则，3）5）∀x(T(x)→¬R(x))P规则6）T(y)→¬R(y)US规则，5）7)T(y)→¬P(y)T规则，2）6）8）T(y)→¬Q(y)T规则，4）6）9）（T(y)→¬P(y)）∧（T(y)→¬Q(y)）T规则，7）8）10）（T(y)→（¬P(y)）∧¬Q(y)）E规则，9）11）∀x(T(x)→（¬P(x)∧¬Q(x))UG规则，10）（2）命题符号化为：P（x）:x是舞者，Q（x）:x很有风度，R（x）:x是学生，T（x）:x是虚数,a：万英。前提：∀x(P(x)→Q(x))，R（a）∧P（a），结论：∃x(R（x）∧Q(x))1）R（a）∧P（a）P规则2）R（a）T规则，1）3）P（a）T规则，1）4）∀x(P(x)→Q(x))P规则5）P(a)→Q(a)UG规则，4）6