第2章 逻辑代数(下)：谓词演算.doc

《离散数学教程》教案与习题解析 理工学院 段景辉
第2章逻辑代数（下）：谓词演算
2.1 谓词演算基本概念
2.1.1 个体
谓词演算中把一切讨论对象都称为个体(individuals)，它们可以是客观世界中的具体客体，也可以是抽象的客体，诸如数字、符号等。确定的个体常用a，b，c等小写字母或字母串表示。a，b，c等小写字母或字母串称为个体常元(constants)。不确定的个体常用字母x，y，z，u，v，w等来表示。它们被称为个体变元，或变元(variables)。
谓词演算中把讨论对象——个体的全体称为个体域(domain of individuals)，常用字母D表示，并约定个体域都是非空的集合。当讨论对象未作具体指定，而是泛指一切客体时，个体域特称为全总域(universe)，用字母U表示。
当给定个体域时，常元表示该域中的一个确定的成员，而变元则可以取该域中的任何一个成员为其值。表示D上运算的运算符与常元、变元可组成所谓个体项(terms)。例如，数学中的代数式a2+b，x2c等。
由于在我们讨论的谓词演算中，其变元只能取值个体对象，不能取值函数、命题或谓词，因此，它又常被叫做一阶谓词演算。
2.1.2 谓词
2.1.3 量词
谓词演算中的量词(quantifiers)指数学中常用的数量词“所有的”（或“每一个”）和“有”（或“存在”），用符号 " 和 $ 来表示，分别称为全称量词和存在量词。为了用全称量词"表示个体域中所有（每一个）个体满足一元谓词P，用存在量词$表示有（存在）个体满足一元谓词P，还需使用变元：
"xP(x) 读作“所有（任意，每一个）x满足P(x)”，表示个体域中所有的个体满足谓词P(x)。
$x P(x) 读作“有（存在，至少有一个）x满足P(x)”，表示个体域中至少有一个体满足谓词P(x)。
当量词用于一谓词填式或复合的谓词表达式时，该谓词或复合的谓词表达式称为量词的辖域(domains of quantifiers)。因此，量词的辖域或者是紧邻其右侧的那个谓词；或者是其右侧第一对括号内的表达式。
量词的指导变元和量词辖域内的同名变元与通常谓词填式中的个体变元不同，因为它可以改名却不能取值作代入。因此，我们把 "xP(x) 和 $xP(x) 中变元x称为约束变元(bound variables)，而那些可以取值作代入的变元则称为自由变元(free variables)。
对于一元谓词P(x)，"xP(x)，$xP(x)均为命题，它们所断言的“所有个体满足性质P(x)”与“存在个体满足性质P(x)”，其真值已经被给定的个体域所确定。特别是,当个体域中个体有穷时，例如D = {a1,…,an}，"xP(x) 的意义与命题 P(a1)∧…∧P(an) 相一致，而 $xP(x) 的意义与命题P(a1)∨…∨P(an) 相一致。
2.1.4 谓词公式及语句形式化
定义2.1 归纳定义谓词公式(predicate formula)集合，谓词公式又称合式公式，简称公式：
（1）谓词填式是公式，命题常元是公式（看作零元谓词），常称原子公式。
（2）如果A，B是公式，x为任一个体变元，那么(ØA)，(A→B)，("xA)，($x A)（当使用五个联结词时还有(A∧B)，(A∨B)，(A«B)）都是公式。
（3）（终极条款，略）。
括号省略原则同命题公式，并约定，("xA)，($x A)中最外层括号也可省略。
语句形式化过程的四个关键步骤是：
l 准确地从语句中提取谓词。一般说来，表示性质的谓语用一元谓词表示，表示关系
的谓语用二元或更多元数的谓词来表示。
l 准确使用量词和确定量词的辖域，当辖域中多于一个谓词时必须注意括号的使用。
l 准确地使用谓词之间的真值联结词，正确地反映谓词之间的逻辑关系。
l 准确地使用多个重叠的量词以及与它们配套的指导变元，量词的排列次序应与原语
句的表述相一致。
自然语言语句中，常常涉及全总个体域的某个局部的所有个体或某些个体，这时需要使用所谓“限定谓词”把量词限于那个局部。一般地说，当限定谓词用于限定全称量词时，它必须作为蕴涵词的前件加入；当限定谓词用于限定存在量词时，它必须作为合取词的合取项加入，即用
"x(限定谓词A(x)→…) 和 $x(限定谓词A(x)∧…)
表示“所有满足A(x)的东西都 …”和“在满足A(x)的东西中有满足 … 的个体”。这里A(x)是限定谓词，将个体域暂时限定在满足A(x)的那些个体上。
练习2.1
1. 选择题
（1）下面哪个公式不是谓词公式( )
A．P B．P(x)∨Q(y)→R(x)
C．"x(P(x)∧R(x,y) D．"x(R(x)→P(x,y))
【答案】：C
（2）谓词公式"x(P(x)∨$yR(y))→Q(x)中量词"x的辖域是( )
A． "x(P(x)∨$yR(y)) B． P(x)
C． P(x)∨$yR(y) D． P(x), Q(x)
【答案】：C
（3）谓词公式"x(P(x)∨$yR(y))→Q(x)中变元x是( )
A．自由变元 B．约束变元
C．既不是自由变元也不是约束变元 D．既是自由变元也是约束变元
【答案】：D
（4）设C(x):x是国家足球队选手，G(x):x是健壮的。命题“没有一个国家足球队选手不是健壮的”可符号化为( )
A．"x(C(x)∧ØG(x)) B．"x(C(x)→G(x))
C．$x(C(x)∧ØG(x)) D．$x(C(x)→ØG(x))
【答案】：B
（5）设L(x) ：x是学员，J(x) ：x是老师，A(x,y)：x钦佩y。命题”所有学员都钦佩某些老师”符号化为( )
A．"xL(x)→A(x,y) B．"x(L(x)→$y(J(y)∧A(x,y)))
C．"x $y(L(x)∧J(y)∧A(x,y)) D．"x $y(L(x)∧J(y)→A(x,y))
【答案】：B
（6）命题”没有不犯错误的人”形式化为(设A(x) ：x是人，B(x) ：x犯错误( )
A．"x(A(x)∧B(x)) B．Ø$x(A(x)→ØB(x))
C．Ø$x(A(x)∧B(x)) D．Ø$x(A(x)∧ØB(x))
【答案】：D
（7）设I(x):x是整数，N(x):x是负数，S(x,y):y是x的平方，则“任何整数的平方非负”可表示为下述谓词公式：( )
A．"x"y(I(x)∧S(x,y)→ØN(y)) B．"x$y(I(x)∧S(x,y)→ØN(y))
C．"x"y(I(x)→S(x,y) ØN(y)) D．"x(I(x)∧S(x,y)→ØN(y))
【答案】：A
（8）令F(x):x是火车，G(y):y是汽车，H(x):x比y快。则语句“某些汽车比所有的火车慢”可表示为：( )
A．$y(G(y)→"x(F(x)∧H(x,y))) B．$y(G(y) ∧"x(F(x)→H(x,y)))
C．"x$y(G(y)→(F(x)∧H(x,y))) D．$y(G(y)→"x(F(x)→H(x,y)))
【答案】：B

2. 填空题
（1）通常一元谓词表示事物的 , 多元谓词表示事物之间的 。
【答案】：性质；关系
（2）"x"y(P(x,y)∧Q(y,z))∧$x P(x,y)中，"x的辖域为 ， "y的辖域为 , $x的辖域为 。
【答案】："y(P(x,y)∧Q(y,z))；P(x,y)∧Q(y,z)；P(x,y)
（3）公式"x(P(x)→Q(x,y)∨$zR(y,z))→S(u)中自由变元为 ，约束变元为 。
【答案】： y，u； x ，z
（4）设个体域为自然数集,则命题“不存在最大自然数”形式化为 。
【答案】：$x"y(x≥y)
（5）个体域为自然数集，P(x):x为奇数，Q(x):x为偶数，则命题“不存在既是奇数又是偶数的自然数”形式化为 。
【答案】：$x(P(x)∧Q(x))
（6）设个体域为实数集,则命题“任意实数总能比较大小”形式化为 。
【答案】："x"y(x>y∨x<y∨x=y)
（7）设个体域为实数集，则命题“如果三个数的乘积为0，那么至少有一个数为0”可形式化为 。命题“对每个实数x，存在实数y，使对于任意实数z，若z>0则x+y<z”可形式化为 。
【答案】："x"y"z(xyz=0→x=0∨y=0∨z=0)；"x$y"z(z>0→x+y<z)
（8）设个体域为全总个体域，R(x):x是实数，Q(x):x是有理数，I(x):x是整数。则命题“所有的有理数是实数”,“有些有理数是整数”，“有些有理数是实数但不是整数”可分别形式化为 ， ， 。
【答案】："x(Q(x)→R(x))；$x(Q(x)∧I(x))；$x(Q(x)∧R(x)∧I(x))

（9）令R(x):x是实数，Q(x):x是有理数。命题“并非每个实数都是有理数”，可符号化为 。
【答案】：Ø"x(R(x)→Q(x))
（10）设:C(x):x是计算机，P(x,y):x能做y，I(x):x是智能工作，则命题“并非所有智能工作都能由计算机来做”形式化为 。
【答案】："x(I(x)→$y(C(y)∧P(y,x))

3. 指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并回答它们是否是命题：
（1）"x(P(x)∨Q(x))∧R(y)
【答案】：全称量词"，辖域 P(x)∨Q(x)，其中x为约束变元。R(y)中y为自由变元。"x(P(x)∨Q(x))∧R(y)不是命题。
（2）"x(P(x)∧Q(x))∧$xS(x)→T(x)
【答案】：全称量词"，辖域 P(x)∨Q(x)，其中 x为约束变元。
存在量词$，辖域 S(x) ，其中 x为约束变元。
T(x)中x为自由变元。"x(P(x)∧Q(x))∧$xS(x)→T(x)不是命题。
（3）"x(P(x)→$y(B(x,y)∧Q(y))∨T(y))
【答案】：全称量词"，辖域 P(x)→$y(B(x,y)∧Q(y))∨T(y)，其中 x为约束变元，T(y)中y为自由变元。
存在量词$，辖域B(x,y)∧Q(y)，其中y为约束变元。"x(P(x)→$y(B(x,y)∧Q(y))∨T(y))不是命题。
（4）P(x)→("y$x(P(x)∧B(x,y))→P(x))
【答案】：全称量词"，辖域$x(P(x)∧B(x,y))，其中 y为约束变元。
存在量词$，辖域P(x)∧B(x,y)，其中 x为约束变元。
不在量词辖域中的P(x)中的x为自由变元。P(x)→("y$x(P(x)∧B(x,y))→P(x))不是命题。

4. 对个体域{0，1}判定下列公式的真值, E(x)表示“x是偶数”：
（1）"x(E(x)→Øx=1) （2）"x(E(x)∧Øx=1)
（3）$x(E(x)∧x=1) （4）$x(E(x)→x=1)
再将它们的量词消去,表示成合取或析取命题公式，鉴别你所确定的真值是否正确。
【答案】：（1）"x(E(x)→Øx=1) 真
"x(E(x)→Øx=1) 可表示成命题公式(E(0)→Ø0=1)∧(E(1)→Ø1=1)
其中E(0)→Ø0=1真，E(1)→Ø1=1也真，故(E(0)→Ø0=1)∧(E(1)→Ø1=1)真。
（2）"x(E(x)∧Øx=1) 假
"x(E(x)∧Øx=1) 可表示成命题公式(E(0)∧Ø0=1)∧(E(1)∧Ø1=1)
其中E(0)∧Ø0=1真，但E(1)∧Ø1=1假，故(E(0)∧Ø0=1)∧(E(1)∧Ø1=1)假。
（3）$x(E(x)∧x=1) 假
$x(E(x)∧x=1) 可表示成命题公式 (E(0)∧0=1)∨(E(1)∧1=1)
其中E(0)∧0=1假，E(1)∧1=1也假，故 (E(0)∧0=1)∨(E(1)∧1=1)假。
（4）$x(E(x)→x=1) 真
$x(E(x)→x=1) 可表示成命题公式 (E(0)→0=1)∨(E(1)→1=1)
其中E(0)→0=1假，但E(1)→1=1真，故 (E(0)→0=1)∨(E(1)→1=1)真。

5. 设整数集为个体域，判定下列公式的真值(*表示数乘运算)：
（1）"x $y(x*y=x) （2）"x$y (x*y=1) （3）"x $y(x+y=1)
（4）$y"x (x*y=x) （5）$y"x (x+y=1) （6）"x$y(x+y=0)
【答案】：（1）"x $y(x*y=x) 真 （2）"x$y (x*y=1) 假
（3）"x$y(x+y=1) 真 （4）$y"x (x*y=x) 真
（5）$y"x (x+y=0) 假 （6）"x$y(x+y=0) 真

6. 量词 $! 表示“有且仅有”，$!xP(x)表示有且仅有一个个体满足谓词P(x)。试用量词", $,等号“=”及谓词P(x),表示 $! P(x)，即写出一个通常的谓词公式使之与$!xP(x)具有相同的意义。
【答案】解. $!xP(x)可用以下具有相同意义的谓词公式表示
$x(P(x)∧"y(P(y)→y=x))

7. 设个体域为整数集，试确定两个谓词P(x,y)，分别使得下列两个蕴涵式假：
（1）"x $!yP(x,y)→$!y"x P(x,y) （2）$!y"x P(x,y)→"x $!yP(x,y)
【答案】解.
（1）当P(x,y)表示x+y=0时"x $!yP(x,y) →$!y"x P(x,y)为假。
（2）当P(x,y)表示x*y=0时$!y"x P(x,y)→"x $!yP(x,y) 为假(*表示数乘运算)。因为只有数0对一切整数x，有x*0=0，从而前件真；但对数0，可有众多y，使0*y=0，从而后件假。

8. 指定整数集的一个尽可能大的子集为个体域，使得下列公式为真：
（1）"x(x>0) （2）"x(x=5∨x=6) （3）"x $y(x+y=3) （4）$y "x (x+y<0)
【答案】解.
（1）对正整数集个体域，"x(x>0)为真
（2）对个体域{5，6}，"x(x=5∨x=6)为真
（3）对整数集个体域，"x $y(x+y=3)为真
（4）对负整数集个体域，$y"x (x+y<0)为真，但使得$y"x (x+y<0) 为真的整数集的最大的子集不存在。

9. 以实数集为个体域, 用谓词公式将下列语句形式化：
（1）如果两实数的平方和为零，那么这两个实数均为零。
（2）f(x)为一实函数当且仅当对每一实数x都有且只有一个实数y满足y = f(x)（不得使用量词 $!。“f(x)为实函数”可译为RF(f)）。
【答案】解.
（1）"x"y(x2+y2=0→x=0∧y=0) 。
（2）RF(f )«"x$y(y = f(x)∧Ø$z(z≠y∧z= f(x)))

10. 用谓词公式将下列语句形式化：
（1）高斯是数学家，但不是文学家。
（2）没有一个奇数是偶数。
（3）一个数既是偶数又是质数，当且仅当该数为2。
（4）有的猫不捉耗子，会捉耗子的猫便是好猫。
（5）党指向哪里，我们就奔向那里。
（6）发亮的东西不都是金子。
（7）不是所有的男人都至少比一个女人高，但至少有一个男人比所有的女人高。
（8）一个人如果不相信所有其他人，那么他也就不可能得到其他人的信任。
（9）君子坦荡荡，小人长戚戚。（孔子）
（10）谁要是游戏人生，他就一事无成；谁不能主宰自己，他就是一个奴隶。（歌德）
【答案】解.
（1）M(x) 表示“x是数学家”，A(x) 表示“x是天文学家”，g表示“高斯”，原句可表示为
M(g) ∧ØA(g)
（2）O(x) 表示“x是奇数”，E(x) 表示“x是偶数” ，原句可表示为
Ø$x(O(x)∧E(x))
（3）E(x) 表示“x是偶数”，P(x) 表示“x是质数” ，原句可表示为
"x(E(x)∧P(x) «x=2)
（4）C(x) 表示“x是猫”，M(x) 表示“x是老鼠”，G(x) 表示“x是好的”，K(x,y)表示“x会捉y” ，原句可表示为
$x(C (x)∧"y(M (y)→ØK(x,y)))∧"x(C (x)∧"y(M (y)→K(x,y))→G(x))
（5）Q(x,y) 表示“x指向y”，J(x,y) 表示“x奔向y”，party表示“党” ，us表示“我们”,原句可表示为
"x(Q(party，x)→J(us, x))
（6）G(x) 表示“x是金子”，L(x) 表示“x是发亮的” ,原句可表示为
Ø"x(L (x)→G(x))
（7）M(x) 表示“x是男人”， F(x) 表示“x是女人”，H(x,y) 表示“x比y高”,原句可表示为
Ø"x(M (x)→$y(F(y)∧H(x,y)))∧$x(M (x)∧"y(F(y)→H(x,y)))
（8）M(x) 表示“x是人”，B(x,y)表示“x相信y”, 原句可表示为
"x(M (x)∧┐$y(M(y)∧x≠y∧B(x,y))→Ø$y(M(y)∧x≠y∧B(y,x)))
（9）M(x) 表示“x是人”，J(x) 表示“x是君子”， H(x) 表示“x坦荡荡”，原句可表示为
"x(M(x)∧J(x)→H(x))∧"x(M(x)∧ØJ(x)→ØH(x))
（10）M(x) 表示“x是人”，K(x) 表示“x游戏人生”，L(x) 表示“x一事无成”， H(x,y) 表示“x主宰y”，N(x) 表示“x是奴隶”，原句可表示为
"x(M(x)∧K(x)→L(x))∧"x(ØH(x,x)→N(x))

2.2 谓词演算永真式
2.2.1 谓词公式的语义
谓词公式的真值不仅依赖于个体域，依赖于公式中各个体变元的取值状况，还依赖于对公式中谓词符号、函数符号、常元符号意义的确认，即人们对它们所作的解释。解释是这些符号与个体域上具体性质、关系、函数、对象间的一个映射，常用I表示这种解释。I恒把命题常元（零元谓词）解释为真值0或1。
定义2.2 给定个体域D及公式A中各谓词符号的解释I，如果A中个体变元x1,…,xn分别取值u1,…,un时A真，则称A在u1,…,un处真；当x1,…,xn无论取D中怎样的个体u1 ,…,un，A在u1 ,…,un处均真，则称A在解释I下真。
定义2.3 给定个体域D，若公式A在每一解释I下均真，那么称A在D上永真。若公式A对任何个体域D均有D上永真，则称A为永真式，或称A永真(valid)。A永真仍记为┝ A。
定义2.4 公式A称为可满足的，如果有某一个体域、某一解释，使得变元在某一取值状况下，A取值真。否则，称公式A不可满足。公式A不可满足时也称A为永假式。
2.2.2 谓词演算永真式
常用的谓词演算逻辑等价式与逻辑蕴涵式分为以下八组，其中A，B，C等表示任意的谓词公式。
第一组：所有命题演算中的重言式。首先，由于谓词演算中允许使用命题常元（如果不限于一阶谓词演算，还可以使用命题变元），因而谓词公式中仍包含命题公式，其中的重言式显然在谓词演算中仍然是永真式。
其次，当我们把命题演算中的重言式中的命题常元、命题变元，改为任意的谓词公式，都不会影响原式的永真性，从而它们也是谓词公式中的永真式。
第二组：当A不含自由变元x时，既A与自由变元x无关，根据我们的约定，以下两式显然成立：
"x A┝┥A , $x A┝┥A
第三组：对任意含有自由变元x的公式A(x)，有
"x A(x)┝ A(x)
A(x) ┝ $x A(x)
"x A(x)┝ $x A(x)
第四组：对任意含有自由变元x的公式A(x)，有
Ø$xØA(x)┝┥"x A(x)
Ø"xØA(x)┝┥$x A(x)
Ø$x A(x)┝┥"xØA(x)
Ø"x A(x)┝┥$xØA(x)
第五组：当公式B中不含自由变元x时，对任意含有自由变元x的公式A(x)，有
"x A(x)∨B┝┥"x (A(x)∨B)
"x A(x)∧B┝┥"x (A(x)∧B)
$x A(x)∨B┝┥$x (A(x)∨B)
$x A(x)∧B┝┥$x (A(x)∧B)
第六组：上一组永真式中的公式B若含自由变元x，情况就要复杂一些。对任意含有自由变元x的公式A(x)，B(x)，有
"x (A(x)∧B(x))┝┥"x A(x)∧"x B(x)
"x A(x)∨"x B(x)┝ "x (A(x)∨B(x))
$x (A(x)∧B(x))┝ $x A(x)∧$x B(x)
$x (A(x)∨B(x))┝┥$xA(x)∨$x B(x)
第七组：对任意含有自由变元x,y的公式A(x,y)，有
"x"yA(x,y)┝┥"y"x A(x,y)
"x"yA(x,y)┝ $y"x A(x,y)
$y"xA(x,y)┝ "x$ y A(x,y)
"x$y A(x,y)┝ $y$ x A(x,y)
$x $ y A(x,y)┝┥$y$x A(x,y)
第八组：当C中无自由变元x时，对任意含有自由变元x的公式A(x)，B(x)，有
"x(C→A(x))┝┥C→"x A(x)
$x(C→A(x))┝┥C→$x A(x)
"x (A(x)→B(x))┝ "x A(x)→"x B(x)
2.2.3 谓词公式等价变换的几个基本原理
定义2.5 设谓词公式A中含自由变元x，设t为一个体项，且t中无自由变元为A中的约束变元，那么称t是在A中对x可代入的，其代入实例记为A(t/x)（代入的意义同前）。
由于约束变元可改名，因此总可对A中约束变元改名，使t成为对x是可代入的。
定理2.1（代入原理）若A是永真式，那么对A中变元可代入的代入实例都是永真式。
定理2.2（替换原理）设A，D为谓词公式，C为A的子公式，且C┝┥D。若B为将A中子公式C的某些出现（未必全部）替换为D后所得的公式，那么A┝┥B。
定义2.6 设A为仅含联结词 Ø，∨，∧的谓词公式，A*为将A中符号∨，∧，t，f，" , $分别换为∧，∨，f，t, $，" 后所得的公式，那么称A*为A的对偶式。
注意，第1章中关于命题演算对偶式的一切讨论，即对偶原理，对于谓词演算都仍然成立。
定理2.3 （改名原理）若公式A(x)中无自由变元y，那么，
"xA(x)┝┥"yA(y) , $xA(x)┝┥$yA(y)
练习2.2
1. 选择题
（1）设论域为整数集,下列公式中哪个值为真( )
A．"x$y(x+y=0) B．$x"y(x+y=0)
C．"x"y(x+y=0) D．$x $y(x+y=0)
【答案】：A
（2）谓词公式"xP(x)∧$yP(y)是( )
A．永真的 B．不可满足的 C．可满足的 D．非永真的
【答案】：B
（3）设谓词P(x) :x是奇数，Q(x) :x是偶数，谓词公式$x(P(x)∧Q(x))在哪个个体域中是可满足的( )
A．自然数 B．整数 C．实数 D．以上均不成立
【答案】：D
（4）设个体域A={a,b},公式"xP(x)∧$xS(x)在A上消去量词后应为( )
A．P(x)∧S(x) B．P(a)∧P(b)∧(S(a)∨S(b))
C．P(a)∧S(b) D．P(a)∧P(b)∧S(a)∨S(b)
【答案】：B
（5）在谓词演算中,下列各式中哪式是正确的( )
A．$x"yA(x,y)┝┥"y$xA(x,y) B．$x$yA(x,y) ┝┥$y$xA(x,y)
C．$x"yA(x,y) ┝┥"x$yA(x,y) D．"x"yA(x,y) ┝┥"y"xB(x,y)
【答案】：B
（6）下列表达式中哪个是假命题( )
A．"x(P(x)∨Q(x)) ┝┥"xP(x)∨"xQ(x) B．$x(P(x)∨Q(x)) ┝┥$xP(x)∨$xQ(x)
C．x+3<3 D．A(P1,P2,P3) ┝┥A*(P1,P2,P3)
【答案】：A
（7）下列各式哪式不成立( )
A．"x(P(x)∨Q(x)) ┝┥"xP(x)∨"xQ(x) B．$x(P(x)∨Q(x)) ┝┥$xP(x)∨$xQ(x)
C．"x(P(x)∧Q(x)) ┝┥"xP(x)∧("x)Q(x) D．"x(P(x)∧Q) ┝┥"xP(x)∧Q
【答案】：A

2. 填空题
（1）取个体域为整数集，给定下列公式：
(a) "x$y(x×y=0) (b) "x$y(x×y=1)
(c) $x$y(x×y=2) (d) "x"y$z(x-y=z)
(e) "x"y (x－y=－y+x) (f) "x"y(x－y=y)
(g) "x(x－y=x) (h) $x"y(x+y=2y)
上面公式中，是真命题的有 ，是假命题的有 。
【答案】：(a)，(c)，(d)，(e)；(b)，(f)，(h)
（2）下列谓词公式
(a) ¬ $xA(x) 与 "x ¬A(x) (b) "x(A(x)∨B(x)) 与 "xA(x)∨"xB(x)
(c) "x(A(x)∧B(x)) 与 "xA(x)∧"xB(x) (d) $x"yD(x,y) 与 "y$xD(x,y)
中 的两个公式是等值的。
【答案】：(a)，(c)
（3）对公式"x(P(x)∨Q(x))，其中P(x):x=1，Q(x):x=2，当论域为是{1,2}时，其真值为 ，当论域为{0,1,2}，其真值为 。
【答案】：1；0
（4）设个体域为A={a,b,c}，消去公式"xP(x)∧$xQ(x)中的量词，可得 。
【答案】：P(a)∧P(b)∧P(c)∧(Q(a)∨Q(b)∨Q(c))
（5）下列各式
(a) "x( P(x)∨Q(x) )→("xP(x)∨$xQ(x) )
(b) ("x( A(x)→B(x) )∧A(c) )→B(c)
(c) ("x(A(x)→B(x))∧"xB(x))→$xA(x)
(d) ($x(P(x)∧Q(x)))→($xP(x)→Q(x))
中 是永真式。
【答案】：(a)，(b)，(c)
（6）填上逻辑等价或者逻辑蕴涵符号："xP(x)∨"xQ(x) "x(P(x)∨Q(x))
【答案】：┝
（7）只用, ", →，表示以下的公式。
(a) $x(P(x)∧Q(x)) ┝┥ ；
(b) $x(P(x) «"yQ(y)) ┝┥ ；
(c) "y("xP(x)∨Q(y)) ┝┥ ；
【答案】： (a) "x(P(x) →Q (x))
(b) "x(P(x) →"yQ(y) ) →"x("y Q(y) →P(x)))
(c) "y(Q(y) →"xP(x))
（8）给定下面谓词公式：
(a ) "x(¬F(x)→¬F(x))
(b) "xF(x)→$xF(x)
(c ) ¬((F(x)→("yG(x, y)→F(x)))
(d) "x$y F(x, y)→$x"yF(x, y)
(e ) ¬"x F(x) «$x ¬F(x)
(f ) "x (F(x) ∧G(x))→("x F(x)∨"x G(x))
(g) $x$yF(x, y)→"x"yF(x, y)
(h ) "x (F(x)∨G(x))→("x F(x)∨"x G(x))
(i ) ("x F(x)∨"x G(x))→"x (F(x)∨G(x))
(j) "x "y F(x, y) «"y "x F(x, y)
上面10个公式中，为永真式的有 ，为矛盾式的有 。
【答案】：为永真式的有(a ) (b ) (e ) (f ) (i ) (j )；为矛盾式的有(c )
（9）改名规则应施于 变元，代入规则应施于 变元。
【答案】：约束；自由

3. 利用量词意义或利用已经证明了的永真式(逻辑蕴涵式，逻辑等价式)及几个基本原理，证明2.2.2节第二组—第八组永真式中尚未证明的各式。
【答案】：证（3）之b A(x)┝ $x A(x)
设U,I,s分别是使A(x)真的个体域、解释和指派，s(x)=dÎU，那么A(d)真,因此对个体域U、解释I, $x A(x) 也真。
证（3）之c "xA(x)┝ $x A(x)
由 "xA(x)┝ A(x) 和 "xA(x)┝ $x A(x) 立即可得。
证（4）之b Ø"x┐A(x)┝┥ $x A(x)
设U,I是使Ø"xØA(x)真的个体域和解释，那么并非U中的所有个体都使得解释I下的谓词A(x)假，，因此U中有个体使得解释I下的谓词A(x)真，故个体域U和解释I下$x A(x)真。上述证明是可逆的，所以Ø"xØA(x)┝┥ $x A(x)得证。
证（4）之c "xØA(x)┝┥ Ø$x A(x)
在（4）之a中取A(x)为 ØA(x) 即可得本式。
证（4）之d Ø"xA(x)┝┥ $x┐A(x)
在（4）之b中取A(x)为 ØA(x) 即可得本式。
证（5）之a "xA(x)∨B┝┥"x(A(x)∨B)
设U,I是使"xA(x)∨B真的个体域和解释，那么
1）U,I使B真。于是U,I使A(x)∨B对一切x均真，因此U,I使"x(A(x)∨B)。
2）U,I使"xA(x)真。于是U,I使A(x)对一切x均真，从而对一切x ，A(x)∨B真，因此U,I使"x(A(x)∨B)真。故 "xA(x)∨B┝ "x(A(x)∨B) 。
上述证明是可逆的，所以"xA(x)∨B┝┥"x(A(x)∨B)得证。
证（5）之b "xA(x)∧B┝┥"x(A(x)∧B)
仿（5）之a可证。
证（5）之d $xA(x)∧B┝┥$x(A(x)∧B)
$xA(x)∧B┝┥Ø (Ø ($xA(x)∧B))
┝┥Ø (Ø$xA(x)∨ØB)
┝┥Ø ("xØA(x)∨ØB) (据（4）之c )
┝┥Ø"x(ØA(x)∨ØB) (据（5）之a )
┝┥$xØ (ØA(x)∨ØB)) (据（4）之d )
┝┥$x(A(x)∧B)
证（6）之a "x(A(x)∧B(x))┝┥"xA(x)∧"x B(x)
设U,I是使"x(A(x)∧B(x))真的个体域和解释，那么对任意dÎU，A(d)∧B(d)真。因此，对任意dÎU，A(d)真，对任意dÎU，B(d)真。故U,I使"xA(x)∧"x B(x)真。
"x(A(x)∧B(x))┝ "xA(x)∧"x B(x)得证。
上述证明是可逆的，所以"x(A(x)∧B(x))┝┥"xA(x)∧"x B(x)得证。
证（6）之b $x(A(x)∨B(x))┝┥$xA(x)∨$x B(x)
$x(A(x)∨B(x))┝┥Ø (Ø$x(A(x)∨B(x)))
┝┥Ø ("x(ØA(x)∧ØB(x))) (据（4）之c )
┝┥Ø ("xØA(x)∧"xØB(x)) (据（6）之a )
┝┥Ø (Ø$xA(x)∧Ø$xB(x)) (据（4）之d )
┝┥$xA(x)∨$xB(x))
证（7）之a "x"yA(x,y)┝┥"y"xA(x,y)
个体域和解释U,I使"x"yA(x,y)真的意义，与个体域和解释U,I使"y"xA(x,y)真的意义相同，因此"x"yA(x,y)┝┥"y"xA(x,y) 。
证（7）之b "x"yA(x,y)┝ $y"xA(x,y)
由 "x"yA(x,y)┝┥"y"xA(x,y) 和 "y"xA(x,y)┝ $y"xA(x,y) 立即可得。
证（7）之c $y"xA(x,y)┝ "x$yA(x,y)
设U,I是使$y"xA(x,y)真的个体域和解释，那么有cÎU，使得对任意dÎU，A(c,d) 真。因此，对任意dÎU，总可取cÎU，使得A(c,d) 真。故U,I也使"x$yA(x,y)真。$y"xA(x,y)┝ "x$yA(x,y)得证。
证（7）之d "x$yA(x,y)┝ $y$xA(x,y)
由 "x$yA(x,y)┝$x$yA(x,y) 和 $x$yA(x,y)┝┥ $y$xA(x,y) (（7）之e,下面给出证明) 立即可得。
证（7）之e $x$yA(x,y)┝┥ $y$xA(x,y)
$x$yA(x,y)┝┥Ø (Ø$x$yA(x,y))
┝┥Ø ("x"yØA(x,y)) (据（4）之c )
┝┥Ø ("y"xØA(x,y)) (据（7）之a )
┝┥$y$xA(x,y)