国防科学技术大学计算机学院离散数学课后习题答案谓词逻辑

课后答案网第五章谓词逻辑习题5.11.a)每个自然数都有唯一的后继；解：“每个”是全称的概念；“自然数”需引进一个特性谓词；“有”表示存在；“唯一”表示所有具有该性质的元素均相等（即若x具有该性质，y也具有该性质，则x等于y）；“后继”用谓词表示。于是，可令：N(x)：x是自然数；Q(x,y)：y是x的后继；E(x,y)：x等于y；则上述命题可以符号化为：(x)(N(x)(y)(Q(x,y)(z)(Q(x,z)E(y,z))b)没有以0为后继的自然数；解：“没有”表示不存在；“自然数”用特性谓词表示；“后继”用谓词表示。于是，可令：N(x)：x是自然数；Q(x,y)：y是x的后继；则上述命题可以符号化为：(x)(N(x)Q(x,0))注意：①对于引进的特性谓词，在全称量词约束下要用逻辑联结词“”，在存在量词约束下要用逻辑联结词“”。②“唯一”概念的符号化。2.a)存在唯一的偶素数；解：“存在”是存在量词的概念；“唯一”可参照上题；“偶数”、“素数”用谓词表示。于是，可令：E(x)：x是偶数；S(x)：x是素数；R(x,y)：x等于y；则上述命题可以符号化为：(x)(E(x)S(x)(y)(E(y)S(y)R(x,y))b)没有既是奇数又是偶数的数；解：“没有”表示不存在；“奇数”、“偶数”、“数”用谓词表示。于是，可令：O(x)：x是奇数；E(x)：x是偶数；Q(x)：x是数；课后答案网则上述命题可以符号化为：(x)(Q(x)O(x)E(x))3.a)所有可证明的算术命题都是真的；b)存在真的但不可证明的算术命题；c)对于任意的三个算术命题x,y,z，若z=xy且z是可证明的，则x是可证明的或y是可证明的；d)对于任意的三个算术命题x,y,z，若x是真的并且z=xy，则z是真的；4.a)对任意整数x,y和z，xz是xy且yz的必要条件；解：“任意”是全称的概念；“整数”需引进一个特性谓词；“”用谓词表示；“必要条件”用逻辑联结词来表示。于是，可令：I(x)：x是整数；L(x,y)：xy；则上述命题可以符号化为：(x)(y)(z)(I(x)I(y)I(z)(L(x,y)L(y,z)L(x,z)))b)对任意整数x，若x=2，则3x=6；反之亦然；解：“任意”是全称的概念；“整数”需引进一个特性谓词；“=”用谓词表示；“”用函词表示。于是，可令：（2、3、6可以用常元表示）I(x)：x是整数；E(x,y)：x=y；f(x,y)：xy；则上述命题可以符号化为：(x)(I(x)(E(x,2)E(f(3,x),6))(E(f(3,x),6)E(x,2)))或(x)(I(x)(E(x,2)E(f(3,x),6)))习题5.21.b)除了最后一个x是自由出现外，其它的6次x的出现都是约束出现。第一个(x)的辖域为下面的划线部分：(x)(P(x)(x)Q(x))((x)P(x)Q(x))第一个(x)的辖域为下面的划线部分：(x)(P(x)(x)Q(x))((x)P(x)Q(x))第二个(x)的辖域为下面的划线部分：(x)(P(x)(x)Q(x))((x)P(x)Q(x))课后答案网)T；b)F；c)F；d)T；e)T；f)T。以a)为例：解：因为P(a,a)为T，所以(y)P(a,y)为T；因为P(b,b)为T，所以(y)P(b,y)为T；因为(y)P(a,y)和(y)P(b,y)均为T，所以(x)(y)P(x,y)也为T。3.a)F；b)T；c)F。4.a)T；b)F；c)T。习题5.31.a)(x)(P(x)Q(x))((x)P(x)(x)Q(x))为永真式。证明：给定(x)(P(x)Q(x))((x)P(x)(x)Q(x))在论域D上的任意解释I，如果(x)P(x)(x)Q(x)在I下为假，则(x)P(x)在I下为真，并且(x)Q(x)在I下为假。因为(x)Q(x)在I下为假，所以存在cD使Q(c)在I下为假。因为(x)P(x)在I下为真，所以P(c)在I下为真。因此，P(c)Q(c)在I下为假。所以，(x)(P(x)Q(x))在I下为假。于是，(x)(P(x)Q(x))((x)P(x)(x)Q(x))为永真式。b)((x)P(x)(x)Q(x))(x)(P(x)Q(x))不是永真式。解：取上述合式公式的解释I如下：i)论域D={a,b}；ii)P(a)P(b)Q(a)Q(b)_____________________________FTFF则(x)(P(x)Q(x))在I下为假，((x)P(x)(x)Q(x))在I下为真。所以，((x)P(x)(x)Q(x))(x)(P(x)Q(x))在I下为假。c)((x)P(x)(x)Q(x))(x)(P(x)Q(x))为永真式。证明：给定((x)P(x)(x)Q(x))(x)(P(x)Q(x))在论域D上的任意解释I，如果(x)(P(x)Q(x))在I下为假，则存在cD使P(c)Q(c)在I下为假。即P(c)在I下为真并且Q(c)在I下为假。因为P(c)在I下为真，所以(x)P(x)在I下为真。因为Q(c)在I下为假，所以(x)Q(x)在I下为假。所以，(x)P(x)(x)Q(x)在I下为假。于是，((x)P(x)(x)Q(x))(x)(P(x)Q(x))为永真式。课后答案网)(x)(P(x)Q(x))((x)P(x)(x)Q(x))不是永真式。解：取上述合式公式的解释I如下：i)论域D={a,b}；ii)P(a)P(b)Q(a)Q(b)_____________________________FTFT则(x)(P(x)Q(x))在I下为真，((x)P(x)(x)Q(x))在I下为假。所以，(x)(P(x)Q(x))((x)P(x)(x)Q(x))在I下为假。2.a)(x)(y)(P(x)Q(y))(x)(P(x)(y)Q(y))（因为y在P(x)中没有自由出现）(x)P(x)(y)Q(y)（因为x在(y)Q(y)中没有自由出现）所以，(x)(y)(P(x)Q(y))(x)P(x)(y)Q(y)。b)(x)(y)(P(x)Q(y))(x)(P(x)(y)Q(y))（因为y在P(x)中没有自由出现）(x)P(x)(y)Q(y)（因为x在(y)Q(y)中没有自由出现）(x)P(x)所以，(x)(y)(P(x)Q(y))(x)P(x)。c)(x)(y)(P(x)Q(y))(x)(P(x)(y)Q(y))（因为y在P(x)中没有自由出现）(x)P(x)(y)Q(y)（因为x在(y)Q(y)中没有自由出现）所以，(x)(y)(P(x)Q(y))(x)P(x)(y)Q(y)。d)(x)(y)(P(x)Q(y))(x)(y)(P(x)Q(y))(x)(P(x)(y)Q(y))（因为y在P(x)中没有自由出现）(x)(P(x))(y)Q(y)（因为x在(y)Q(y)中没有自由出现）(x)P(x)(y)Q(y)(x)P(x)(y)Q(y)所以，(x)(y)(P(x)Q(y))(x)P(x)(y)Q(y)。e)(x)(y)(P(x)Q(y))(x)(y)(P(x)Q(y))(x)(P(x)(y)Q(y))（因为y在P(x)中没有自由出现）(x)(P(x))(y)Q(y)（因为x在(y)Q(y)中没有自由出现）(x)P(x)(y)Q(y)课后答案网(x)P(x)(y)Q(y)所以，(x)(y)(P(x)Q(y))(x)P(x)(y)Q(y)。3.解：(x)(P(x)Q(x))((x)(P(x))(x)(Q(x)))____上述这一步不正确。根据书中105页I16：(x)(P(x)Q(x))(x)(P(x))(x)(Q(x))可知：(x)(P(x)Q(x))((x)(P(x))(x)(Q(x)))因此，最后应该证明出：(x)(P(x)Q(x))(x)P(x)(x)Q(x))这就是书中的I15。习题5.41.a)(y)(z)(P(z,y)(x)(P(z,x)P(x,z)))(y)(z)((P(z,y)(x)(P(z,x)P(x,z)))(P(z,y)(x)(P(z,x)P(x,z))))（化去）(y)(z)((P(z,y)(x)(P(z,x)P(x,z)))(P(z,y)(x)(P(z,x)P(x,z))))（内移）(y)(z)((x)(P(z,y)(P(z,x)P(x,z)))(x)(P(z,y)(P(z,x)P(x,z))))（、前移）(y)(z)((x)(P(z,y)(P(z,x)P(x,z)))(u)(P(z,y)(P(z,u)P(u,z))))（换名）(y)(z)(x)(u)((P(z,y)(P(z,x)P(x,z)))(P(z,y)(P(z,u)P(u,z))))（、前移）上述公式即为原公式的前束范式。令f为二元函词，则原公式的无前束范式为：(z)(x)((P(z,a)(P(z,x)P(x,z)))(P(z,a)(P(z,f(z,x))P(f(z,x),z))))b)(x)(y)(z)((P(x,y)P(y,z)P(z,z))(P(x,y)Q(x,y)Q(x,z)Q(z,z)))(x)(y)(z)((P(x,y)(P(y,z)P(z,z)))((P(x,y)Q(x,y))(Q(x,z)Q(z,z))))（化去）(x)(y)(z)((P(x,y)(P(y,z)P(z,z)))((P(x,y)Q(x,y))(Q(x,z)Q(z,z))))（内移）上述公式即为原公式的前束范式。课后答案网令g为二元函词，则原公式的无前束范式为：(x)(y)((P(x,y)(P(y,g(x,y))P(g(x,y),g(x,y))))((P(x,y)Q(x,y))(Q(x,g(x,y))Q(g(x,y),g(x,y)))))2.令原公式为X，则X(x)(y)(P(x,y)P(y,x))(x)(y)(z)(P(x,y)P(y,z)P(x,z))(x)(y)P(x,y)(x)(P(x,x))（内移）(x)(y)(z)((P(x,y)P(y,x))(P(x,y)P(y,z)P(x,z)))(x)(y)P(x,y)(x)(P(x,x))（前移）(x)(y)(z)((P(x,y)P(y,x))(P(