《应用离散数学》方景龙版-2.2 谓词公式及其解释

《《应用离散数学》方景龙版-2.2 谓词公式及其解释》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、§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.设个体域，请给出两种不同的解释和，使得下面谓词公式

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）解

3、（1）公式被解释成“”，为真命题。（2）公式被解释成“”，为假命题。（3）公式被解释成“”，为真命题。（4）公式被解释成“”，为假命题。5.判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）解（1）因为当存在某个使取1时一定取1，所以公式是为永真式。（3）取解释：个体域为自然数集合，。在下公式的前件与后件均为真，所以公式为真，即不是永假式。取解释：个体域仍为自然数集合，但取为。在下公式不成为命题，即不是永真式。综合知公式为可满足式。（5

4、）取解释：个体域为自然数集合，。在下，对任意的，为真而为假，所以公式为假，即不是永真式。取解释：个体域仍为自然数集合，但取为。在下，对任意的，为假而为真，所以公式为真，即不是永假式。综合知公式为可满足式。（7）公式为永真式，用非形式化的反证法证明如下：若公式非永真，则存在一个解释，使得取1而取0。取0表明存在某对使得取0，从而也应取0。这与前面说取1矛盾。故公式是永真式。（9）设为任意一个解释，个体域为。若取1，即存在，使得为真，从而为真，故为真。所以在解释下公式为真，由的任意性可知，公式为永真式。（2）、（4）、（6

5、）、（8）、（10）略。6.判断下列谓词公式哪些是永真式，哪些是永假式，哪些是可满足式，并说明理由。（1）（2）（3）（4）（5）（6）（7）解略7.给出一个非闭式的永真式，给出一个非闭式的永假式，给出一个非闭式的可满足式。解略