习题与解答
⒈ 判断下列语句是否为命题，并讨论命题的真值。 ⑴ 2x 3 = 0。 ⑵ 前进！
⑶ 如果8 + 7 > 20，则三角形有四条边。 ⑷ 请勿吸烟！
⑸ 你喜欢鲁迅的作品吗？
⑹ 如果太阳从西方升起，你就可以长生不老。 ⑺ 如果太阳从东方升起，你就可以长生不老。
解 ⑶,⑹,⑺表达命题，其中⑶,⑹表达真命题，⑺表达假命题。 ⒉ 将下列命题符号化： ⑴ 逻辑不是枯燥无味的。
⑵ 我看见的既不是小张也不是老李。 ⑶ 他生于1963年或1964年。 ⑷ 只有不怕困难，才能战胜困难。 ⑸ 只要上街，我就去书店。
⑹ 如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐。 ⑺ 如果林芳在家里，那么他不是在做作业就是在看电视。 ⑻ 三角形三条边相等是三个角相等的充分条件。 ⑼ 我进城的必要条件是我有时间。 ⑽ 他唱歌的充分必要条件是心情愉快。
⑾ 小王总是在图书馆看书，除非他病了或者图书馆不开门。 解 ⑴ p：逻辑是枯燥无味的。
“逻辑不是枯燥无味的”符号化为 p。 ⑵ p：我看见的是小张。q：我看见的是老李。
“我看见的既不是小张也不是老李”符号化为pq。 ⑶ p：他生于1963年。q：他生于1964年。 “他生于1963年或1964年”符号化为p q。 ⑷ p：害怕困难。q：战胜困难。
“只有不怕困难，才能战胜困难”符号化为q p。 ⑸ p：我上街。q：我去书店。
“只要上街，我就去书店”符号化为p q。
⑹ p：小杨晚上做完了作业。q：小杨晚上没有其它事情。
r：小杨晚上看电视。s：小杨晚上听音乐。
“如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐”符号化为pqrs。
⑺ p：林芳在家里。q：林芳做作业。r：林芳看电视。
“如果林芳在家里，那么他不是在做作业就是在看电视”符号化为pqr。 ⑻ p：三角形三条边相等。q：三角形三个角相等。
“三角形三条边相等是三个角相等的充分条件”符号化为pq。 ⑼ p：我进城。q：我有时间。
“我进城的必要条件是我有时间”符号化为p q。 ⑽ p：他唱歌。q：他心情愉快。
“他唱歌的充分必要条件是心情愉快” 符号化为pq。 ⑾ p：小王在图书馆看书。q：小王病了。r：图书馆开门。
“小王总是在图书馆看书，除非他病了或者图书馆不开门”符号化为(q r) p，或者 (q r) p。也可符号化为 (q r) p，或者 (q r) p。 ⒊ 列出除，，，，之外的所有二元联结词的真值表。
解 共有16个二元联结词，记除，，，，之外的二元联结词为1,2,,11。
p 0 0 1 1
q 0 1 0 1 p 0 0 1 1 q 0 1 0 1 p1q p2q p3q p4q p5q p6q 0 0 0 0 p7q 0 0 1 0 p8q 0 0 1 1 p9q 0 1 0 0 p10q 0 1 0 1 p11q 1 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 1 1 1 1
⒋ 求下列公式在真值赋值( p1 / 1, p2 / 1, p3 / 0, p4 / 0)下的值： ⑴ p1(p2p3)
⑵ (p1p2p3)((p1p2)(p3p4)) ⑶ (p1p2)p3(((p1p2)p3)p4) (4) (p2 p1) (p3 p4) ⑸ (p1p3)(p2p4)
⑹ p1(p2p3p1)p2p4
(7) (p1 p3) (p2 p4)
解 记真值赋值( p1 / 1, p2 / 1, p3 / 0, p4 / 0)为v。 ⑴ v(p1(p2p3))1(10)1。
⑵ v((p1p2p3)((p1p2)(p3p4)))(110)((11)(00))1 ⑶ v((p1p2)p3(((p1p2)p3)p4))
(11)0(((11)0)0)1。
(4) v ((p2 p1) ( p3 p4)) = (1 1) ( 0 0) = 0 1 = 1。 ⑸ v((p1p3)(p2p4))(10)(10)0。
⑹ v(p1(p2p3p1)p2p4)1(101)101。 (7) v ((p1 p3) (p2 p4)) = (1 0) (1 0) = 0 0 = 0。 5. 用真值表判断以下公式是不是永真式、永假式、可满足式。 (1) (p r) ((q r) (p q r)) (2) (pp)p
(3) (p q) ((p q) p)
(4) (p(qr))((pq)(pr)) (5) (pq)(pr)(qr)r (6) p (p q)
(7) (pq)((pq)p)
解 (1) 将 (p r) ((q r) (p q r)) 记为A。
p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 p r q r p q p q r (q r) (p q r) A 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 (p r) ((q r) (p q r)) 是永真式。
(3) 将 (p q) ((p q) p) 记为A。
p 0 q 0 p q 1 q 1 p q 1 (p q) p 0 A 0 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 (p q) ((p q) p) 是非永真的可满足式。
(6)
p 0 0 1 1 q 0 1 0 1 p 1 1 0 0 p q 1 1 0 1 (p q) 0 0 1 0 p (p q) 0 0 0 0 p (p q) 是永假式。 解 (1), (2), (4), (5), (7)是永真式，(6)是永假式，(3)是非永真的可满足式。 6. 指出满足下列公式的所有真值赋值。 (1) (pq)(pr) (2) p(qr(pq)) (3) pr(pr)(qr) (4) p (q r)
解 (1) (p/0,q/0,r/0)，(p/0,q/0,r/1)，(p/0,q/1,r/0)，(p/0,q/1,r/1)，
(p/1,q/0,r/1)，(p/1,q/1,r/0)，(p/1,q/1,r/1)。
(2) (p/0,q/1,r/0)，(p/1,q/0,r/0)，(p/1,q/0,r/1)，(p/1,q/1,r/0)，
(p/1,q/1,r/1)。
(3) (p/0,q/0,r/0)，(p/0,q/1,r/0)。 (4) 任取满足p (q r) 的真值赋值 v。 若 v (p) = 0，则v (q r) = 1，v (q) = v (r)。 若 v (p) = 1，则v (q r) = 0，v (q) v (r)。 所以，满足p (q r) 的真值赋值有以下四个：
( p / 0, q / 0, r / 0)，( p / 0, q / 1, r / 1)，( p / 1, q / 0, r / 1)，( p / 0, q / 1, r / 0)。 7. 若公式A既不是永真式，也不是永假式，则A的每个替换实例一定既不是永真式，也不
是永假式。对吗？
解 不对。若A是非永真的可满足式，则它的替换实例中既有永真式，也有永假式，也有
非永真的可满足式。
设A中出现的命题变元是p1,…, pn，v1和v2分别是使得A为真的真值赋值和使得A为假的真值赋值。取公式B1,…, Bn, C1,…, Cn如下：
pp若v2(pi)1pp若v1(pi)1 Ci Bipp若v(p)0pp若v(p)02i1i任取真值赋值v，
p1,,pnv(AB)v[p1/v(B1),,pn/v(Bn)](A)v1(A)1， 1,,Bnp1,,pnv(AC)v[p1/v(C1),,pn/v(Cn)](A)v2(A)0， 1,,Cn所以，A的替换实例AB11,,Bnn是永真式，A的替换实例AC11,,Cnn是永假式。 A本身也是A的替换实例，它是非永真的可满足式。
8. 用真值表证明以下等值式。
(1) p (q r) (p q) ( p r)
p,,pp,,pp 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 q r 0 1 1 0 0 1 1 0 p (q r) 0 0 0 0 0 1 1 0 p q 0 0 0 0 0 0 1 1 p r 0 0 0 0 0 1 0 1 (p q) ( p r) 0 0 0 0 0 1 1 0 (2) (3) (4)
9.用等值演算证明以下等值式。 (1) p(qr)q(pr) (2) (pq)(pr)pqr (3) (p q) (r q) p r q (4) p(qp)p(pq)
(5) (pq)(rq)prq (6) (p q) p q
解 (1) p(qr)p(qr)q(pr)q(pr) (2) (pq)(pr)(pq)(pr)p(qr)pqr (3) (p q) (r q) ( p q) ( r q) ( p r) (q q)
( p r) q ( p r) q p r q
(4) p(qp)pqp1ppqp(pq) (5) (pq)(rq)(pq)(rq)(pr)q
(pr)qprq
(6) (p q) p q
p q (p q) (p (q 1)) 1 (p q) (1 1) (p q) 0 p q
10.用等值演算证明以下公式是永真式。 (1) (qp)(pq)p
(2) (p q) (r s) (p r q s)
(3) (pq)(pr)(ps)(pqrs) (4) (pqr)(pr)(qr)
解 (1) (qp)(pq)p(qp)(pq)ppp1 (2) (pq)(rs)(prqs)
(pq)(rs)prqs (pq)p(rs)rqs qpsrqs1
(3) (pq)(pr)(ps)(pqrs)
pqprps(pqrs) pqrspqrs1
(4) (pqr)(pr)(qr)
((pq)r)prqr ((pq)r)pqr
(pqpqr)(rpqr)111
11.用等值演算证明以下公式是永假式。 (1) (qp)(pq)p (2) (pq)(qr)(pr)
解 (1) (qp)(pq)p(qp)(pq)ppp0 (2)
(pq)(qr)(pr)(pq)(qr)(pr) (pq)(qr)pr((pq)p)((qr)r) pqqr0
12.找出与下列公式等值的尽可能简单的由{,}生成的公式。 13.找出与下列公式等值的尽可能简单的由{,}生成的公式。
(1) pq(rp)
(2) (pqr)pq (3) pqp
解 (1) pq(rp)pq(rp)
(pqr)(pqp)
pqr(pqr)
(2) (pqr)pq(pqr)pq((pqr)pq) (3) pqp(pqp)
14.设A是由{}生成的公式。证明：A是永真式当且仅当每个命题变元在A中出现偶数次。
证明 首先证明：若A是由{}生成的仅出现一个命题变元p的公式，则
1Ap对p在A中的出现次数进行归纳。
若p在A中出现偶数次
若p在A中出现奇数次① 若p在A中出现1次，即A为p，显然Ap。 ② 若p在A中出现2次，即A为pp，显然A1。
③ 设p在A中的出现n次，A为BC，p在B，C中的出现次数分别为k和l，则nkl，kn且ln。若n为偶数,则k和l的奇偶性相同，B和C等值于同一公式，A1。若n为奇数,则k和l的奇偶性不同，B和C中一个等值于p，另一个是永真式，因此
Ap1p。
设在A中的出现的所有命题变元为p1,,pn，它们的出现次数分别为k1,,kn。因为
AB(AB)(BA)BA，并且
(AB)C((AB)C)AB1C1 ABC11(A(BC))A(BC)
所以满足交换律和结合律，存在由{}生成的公式B1,,Bn，使得
AB1Bn，并且Bi仅出现命题变元pi，出现次数为ki，i1,,n。若k1,,kn全为偶数，则AB1Bn111。若k1,,kn中有
kl1,,klm是奇数，则AB1Bnpl1plm，显然A不是永真式。15.设A是由{}生成的公式。证明：A是永假式当且仅当每个命题变元在A中出现偶数次。
证明 首先证明：若A是由{}生成的仅出现一个命题变元p的公式，则
0Ap对p在A中的出现次数进行归纳。
若p在A中出现偶数次若p在A中出现奇数次
① 若p在A中出现1次，即A为p，显然A p。
② 若p在A中出现2次，即A为p p，显然A 0。
③ 设p在A中出现n次，A为B C，p在B，C中的出现次数分别为k和l，则
n = k + l，k < n且l < n。若n为偶数,则k和l的奇偶性相同，B和C等值于同一公式，
A 0。若n为奇数,则k和l的奇偶性不同，B和C中一个等值于p，另一个是永假式，因此A p 0 p。
设在A中的出现的所有命题变元为p1,…, pn，它们的出现次数分别为k1,…, kn。因为满足交换律和结合律，所以存在由{}生成的公式B1,…, Bn，使得A B1 … Bn，Bi中仅出现命题变元pi，并且出现次数为ki ，i = 1,…, n。若k1,…, kn全为偶数，则
A B1 … Bn 0 … 0 0。若 k1,…, kn 中有kl1,,klm是奇数，则
AB1Bnpl1plm，显然A不是永假式。
16.北京、上海、天津、广州四市乒乓球队比赛，三个观众猜测比赛结果。 甲说：“天津第一，上海第二。” 乙说：“天津第二，广州第三。” 丙说：“北京第二，广州第四。”
比赛结果显示，每人猜对了一半，并且没有并列名次。 问：实际名次怎样排列？
解 用字母表示命题如下：
p2：北京第二，q2：上海第二，r1：天津第一，
r2：天津第二，s3：广州第三，s4：广州第四。
由已知条件列出以下方程：
甲猜对了一半：r1 q2 = 1，乙猜对了一半：r2 s3 = 1， 丙猜对了一半：p2 s4 = 1； 每个城市只能得一个名次：r1 r2 = 0，s3 s4 = 0； 没有并列名次：p2 q2 = 0，p2 r2 = 0，r2 q2 = 0。 解以上8个方程组成的方程组。
r2 = r2 1 = r2 (r1 q2) = (r2 r1 ) ( r2 q2) = 0 0 = 0， 将r2 = 0代入r2 s3 = 1得s3 = 1，将s3 = 1代入s3 s4 = 0得s4 = 0，将s4 = 0代入p2 s4 = 1得p2 = 1，将p2 = 1代入p2 q2 = 0得q2 = 0，将q2 = 0代入r1 q2 = 1得r1 = 1。 将p2 = r1 = s3 = 1，q2 = r2 = s4 = 0代入8个方程验证它们满足方程组。
因此，天津第一，北京第二，广州第三，上海第四。 17.某勘探队取回一块矿样，三人判断如下。 甲说：“矿样不含铁，也不含铜。” 乙说：“矿样不含铁，含锡。” 丙说：“矿样不含锡，含铁。”
已经知道，这三人中有一个是专家，一个是老队员，一个是实习队员。化验结果表明：这块矿样只含一种金属，专家的两个判断皆对，老队员的判断一对一错，实习队员的两个判断皆错。问：这三人的身分各是什么？
r:矿样含锡。 解 p:矿样含铁， q:矿样含铜，
甲说的两句话为：p，q
乙说的两句话为：p，r 丙说的两句话为：r，p
如果用一个公式表达出这三人中有一个是专家，一个是老队员，一个是实习队员，公式会非常
复杂。其实我们不必完全写出这样的公式。因为矿样只含一种金属，所以pq0，qr0，
rp0。甲是实习队员，即甲说的两句话都是错的，可表示为：pq。乙是实习队员，即
乙说的两句话都是错的，可表示为：
pr。丙是实习队员，即丙说的两句话都是错的，可表
示为：rp。甲、乙、丙三人中至少有一个是实习队员，可表示为：
(pq)(pr)(rp)1
因为pq0，所以(pr)(rp)1，即pr1，p和r中恰好有一个为1，因此q0。甲是老队员，即甲说的话一半对一半错，可表示为：pq。乙是老队员，即乙说的话一半对一半错，可表示为：pr。丙是老队员，即丙说的话一半对一半错，可表示为：rp。甲、乙、丙三人中有奇数个老队员，可表示为：
(pq)(pr)(rp)1
由教材上的等值式可得到
(pq)(pr)(rp)
(pp)(rr)(qp)
01(q1p)qp
又知道q0，所以p1。因为rp0，所以r0。因此，甲说的话一半对一半错，甲是老队员。乙说的话全错，乙是实习队员。丙说的话全对，丙是专家。 18. 先用等值演算证明下列等值式，再用对偶定理得出新等值式。 (1) (pq)(pq)p
(2) (pq)(pq)(pq)(pq) (3) q((pq)p)1
解 (1) (pq)(pq)(pq)(pq)p(qq)p
由对偶定理得(pq)(pq)p。 (2)
(pq)(pq)(pq)(p(qq))(pq) p(pq)(pp)(pq)pq(pq)
由对偶定理得(pq)(pq)(pq)(pq)。 (3)
19. 设A是由{0, 1, , , }生成的公式，A*与A互为对偶式。 (1) 若A是永真式，则A*是永假式。 (2) 若A是永假式，则A*是永真式。
证明 (1) 设A是永真式，则A 1，由对偶定理得A* 0，因此A*是永假式。 (2) 设A是永假式，则A 0，由对偶定理得A* 1，因此A*是永真式。 20. 证明以下联结词集合是极小完全集。
(1) {0, } (2) {, } (3) {, , } (4) {, , }
证明 (1) p p 0 p 0，因为{, }是完全集，所以{0, }是完全集。任取由{0}生成的不出现除命题变元p之外的命题变元的公式A，令真值赋值v = (p/0)，则
v(A) = 0，而v(p) = 1，因此{0}不能定义。所以{0}不是完全集。任取由{}生成的仅出现命题变元p的公式A，令真值赋值v = (p/1)，则v(A) = 1，而v(p) = 0，因此{}不能定义。所以{}不是完全集。所以{0, }是极小完全集。
(2) p p 1 p (p p)，因为{, }是完全集，所以{, }是完全集。任取由{}生成的仅出现命题变元p的公式A，令真值赋值v = (p/0)，则v(A) = 0，而
v(p) = 1，因此{}不能定义。所以{}不是完全集。{}不是完全集。所以{, }
是极小完全集。
(3) p p 1 p (p p)，因为{, }是完全集，所以{, , }是完全集。任取由{, }生成的仅出现命题变元p的公式A，令真值赋值v = (p/0)，则v(A) = 0，而 v(p) = 1，因此{, }不能定义。所以{, }不是完全集。任取由{, }生成的仅出现命题变元p的公式A，令真值赋值v = (p/1)，则v(A) = 1，而v(p) = 0，因此{, }不能定义。所以{, }不是完全集。{, }不是完全集。所以{, , }是极小完全集。
(4) p p 1 p (p p)，因为{, }是完全集，所以{, , }是完全集。任取由{, }生成的仅出现命题变元p的公式A，令真值赋值v = (p/0)，则v(A) = 0，而 v(p) = 1，因此{, }不能定义。所以{, }不是完全集。任取由{, }生成的仅出现命题变元p的公式A，令真值赋值v = (p/1)，则v(A) = 1，而v(p) = 0，因此{, }不能定义。所以{, }不是完全集。{, }不是完全集。所以{, , }是极小完全集。
21.证明以下联结词集合不是完全集。 (1) {,,,} (2) {,,}
证明 (1) 任取由{,,,}生成的仅出现命题变元p的公式A，令真值赋值v(p/1)，则v(A)1，而v(p)0，因此{,,,}不能定义。所以{,,,}不是完全集。
(2) 任取由{,,}生成的仅出现命题变元p的公式A，令真值赋值v(p/0)，则
v(A)0，而v(p)1，因此{,,}不能定义。所以{,,}不是完全集。
22. 二元联结词 （称为“与非”）和 （称为“或非”）的真值表如下。
p 0 0 1 1 证明：
q 0 1 0 1 p q p q 1 1 1 0 1 0 0 0 (1) {}是完全集。 (2) {}是完全集。
(3) 若 是二元联结词且{}是完全集，则 是 或 。 证明 (1) p p p,
p q (p q) (p q) (p q) (p q)，
因为{, }是完全集，所以{}是完全集。
(2) p p p , p q (p q) (p q) (p q) (p q) ， 因为{, }是完全集，所以{}是完全集。
(3) 若0 0 = 0或1 1 = 1，则 不能由{}定义。因此，0 0 = 1且1 1 = 0。 若0 1 1 0，则 的真值表的最后一列有偶数个1，真值表最后一列有奇数个1的 不能由{}定义。所以，0 1 = 1 0。若0 1 = 1 0 = 1，则 是 。若
0 1 = 1 0 = 0，则 是 。
23.三元联结词的真值表如下。 p 0 0 0 0 1 1 1 1 证明{}是极小完全集。
q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 (p,q,r) 1 1 0 0 0 0 1 0 证明 pqpqq，因为{}是完全集，所以{}是极小完全集。 24.在下列公式中，哪些是析取范式，哪些是合取范式?
p，p q，(p q) r，p r，p p，((p q) q) r
解 p，p q，p r，p p是析取范式，
p，p q，p r，(p q) r，p p是合取范式。
25. 在下列公式中，哪些是关于p, q, r的主析取范式，哪些是关于p, q, r的主合取范式？
p q r, p q r, (p q r) ( p q r),
p ( q r), (p p q) ( p q r)
解 p q r是关于p, q, r的主析取范式，p q r是关于p, q, r的主合取范式。
26.是否有这样的公式，它既是主合取范式，又是主析取范式？如果有，举出一例。
解 有。p既是关于p的主析取范式，又是关于p的主合取范式。
27.求下列公式的主范式，进而判断其是否永真式、永假式、可满足式。 (1) pqr (2) (pq)r
(3) pq(pq) (4) p(pq(qr)) (5) (pqr)(pqr) (6) pq(pq)
解 (1) pqr(pq)rpqr
pqr的主合取范式是pqr，包含一个极大项，因此它是非永真的可满
足式。
(2) (pq)r(pq)r
(pq)r(pr)(qr) (p(qq)r)((pp)qr) (pqr)(pqr)(pqr)
(pq)r的主合取范式是(pqr)(pqr)(pqr)，包含了
三个极大项，因此它是非永真的可满足式。
(3) pq(pq)(pq)((pq)(pq)) (pq)(pq)(pq)pqpq
pq(pq)的主合取范式为pq，包含了一个极大项，因此它是非永真
的可满足式。
(4) p(pq(qr))p(pq(qr))1
p(pq(qr))的主合取范式为1，不包含任何极大项，因此它是永真式。
(5) (pqr)(pqr)
(p(qr))(p(qr))
(pp)(pqr)(qrp)(qrqr)
(pqr)(pqr)
(pqr)(pqr)的主析取范式为(pqr)(pqr)，
包含了两个极小项，因此它是非永真的可满足式。 (6) pq(pq)
(p(qq))((pp)q)(pq) (pq)(pq)(pq)(pq)
pq(pq)的主合取范式为(pq)(pq)(pq)(pq)，
包含了所有的四个极大项，因此它是永假式。 28.用主范式证明下列等值式。
(1) (pq)pq(pp)(rp) (2) (pq)(pr)pqr 式
(pqr)(pqr))(pqr)(pqr)，因此，
解 (1) (pq)pq(pq)(pq)
(pq)(pq)(pq(rr))(pq(rr))
(pqr)(pqr))(pqr)(pqr)
(pp)(rp)(pp)(rp)
p(pr)pp(qq)(rr)
(pqr)(pqr))(pqr)(pqr)
(pq)pq和(pp)(rp)等值于同一个关于p,q,r的主析取范
(pq)pq(pp)(rp)。
(2) (pq)(pr)(pq)(pr)
(pq(rr))(p(qq)r)
(pqr)(pqr)(pqr)(pqr)
(pqr)(pqr)(pqr)
pqrp(qr)(pq)(pr)
(pq(rr))(p(qq)r)
(pqr)(pqr)(pqr)(pqr) (pqr)(pqr)(pqr)
(pq)(pr)和pqr的主合取范式相同，所以，
(pq)(pr)pqr。
29.判断以下关系是否成立，并说明理由。 (1) pq,p|q (2) pq, ,q|p
(3) p1q1,p2q2,p1p2|q1q2 (4) pq,qp|pq
(5) pqr,pqr|pqr
解 (1) 若真值赋值v使得v(pq)v(p)1，则v(q)1。所以pq,p|q。 (2) 真值赋值v(p/0,q/1)使得v(pq)v(pq)v(q)1，但v(p)0，所以
pq,pq,q|/p。
(3) 若真值赋值v使得v(p1q1)v(p2q2)v(p1p2)1，则v(p1)v(p2)1，因而v(q1)v(q2)1，v(q1q2)1。所以p1q1,p2q2,p1p2|q1q2。 (4) 真值赋值v(p/0,q/0)使得v(pq)v(qp)1，但v(pq)0。所以
pq,qp|/pq。
(5) 真值赋值v(p/0,q/1,r/0)使得v(pqr)v(pqr)1，但
v(pqr)0。所以pqr,pqr|/pqr。
30.判断以下公式组成的集合是否可满足，并说明理由。 (1) (pq)(sr)，(sr)
(2) p1，p1p2，p1p2p3,…，p1pnpn1,… (3) pq，pq，pq
解 (1) 可满足。真值赋值(p/1,q/0,r/1,s/0)满足它。
(2) 可满足。若真值赋值v使得v(pi)1,i1,2,，则v满足它。 (3) 可满足。真值赋值(p/0,q/1)满足它。
31.设A,B,C是任意公式。AB|C当且仅当A|C且B|C。
证明1 （）设AB|C。任取满足A的真值赋值v，则v(AB)1，因为AB|C，所以v(C)1。这表明A|C。任取满足B的真值赋值v，则v(AB)1，因为AB|C，所以v(C)1。这表明B|C。
（）设A|C且B|C。任取满足AB的真值赋值v，则v(A)1或v(B)1。 ① 若v(A)1，因为A|C，所以v(C)1。 ② 若v(B)1，因为B|C，所以v(C)1。 因此，AB|C。
证明2 ABC(AB)C(AB)C
(AC)(BC)(AC)(BC)
AB|C
当且仅当ABC是永真式
当且仅当(AC)(BC)是永真式 当且仅当AC和BC都是永真式 当且仅当A|C且B|C
32.设1和2是公式集合，B是公式，2|B，对于2中每个公式A，1|A。证明：
1|B。
证明 任取满足1的真值赋值v。对于2中每个公式A，因为1|A，所以v(A)1。这表明v满足2。又因为2|B，所以v(B)1。因此，1|B。 33.公式集合不可满足当且仅当|0。
证明 （）设|/0，则存在真值赋值v满足且v(0)0，因此可满足。 （）设|0。若可满足，有真值赋值v满足，由|0得出v(0)1，这是不可能的。因此，不可满足。
34.设n是正整数，{p1q1,,pnqn,p1pn}{(qiqj)|1ijn}。证明：|(q1p1)(qnpn)。
证明 设真值赋值v满足，则v(p1pn)1，存在in使v(pi)1。因为
v(piqi)1，所以v(qi)1。若1ji，因为v((qjqi))1，因此v(qj)0。
若
ijn，因为v((qiqj))1，因此v(qj)0。所以
v((q1p1)(qnpn))1。
因篇幅问题不能全部显示，请点此查看更多更全内容