离散数学第1章习题解答

1. 判断下列语句是否为命题，并讨论命题的真值。

(1) 32−x 。

(2) 前进！

(3) 如果2078>+，则三角形有四条边。

(4) 请勿吸烟！

(5) 你喜欢鲁迅的作品吗？

(6) 如果太阳从西方升起，你就可以长生不老。

(7) 如果太阳从东方升起，你就可以长生不老。

解 (3), (6), (7) 表达命题，其中 (3), (6) 表达真命题，(7) 表达假命题。

2. 将下列命题符号化：

(1) 逻辑不是枯燥无味的。

(2) 我看见的既不是小张也不是老李。

(3) 他生于1963年或19年。

(4) 只有不怕困难，才能战胜困难。

(5) 只要上街，我就去书店。

(6) 如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐。

(7) 如果林芳在家里，那么他不是在做作业就是在看电视。

(8) 三角形三条边相等是三个角相等的充分条件。

(9) 我进城的必要条件是我有时间。

(10) 他唱歌的充分必要条件是心情愉快。

(11) 小王总是在图书馆看书，除非他病了或者图书馆不开门。

解

(1) 逻辑是枯燥无味的。:p

“逻辑不是枯燥无味的”符号化为p ¬。

(2) 我看见的是小张:p

我看见的是老李:q

“我看见的既不是小张也不是老李”符号化为q p ¬∧¬。

(3) 年他生于 1963 :p

年他生于 19 :q

“他生于1963年或19年”符号化为q p ⊕。

(4) 害怕困难:p

战胜困难:q

“只有不怕困难，才能战胜困难”符号化为p q ¬→。

(5) 我上街:p

我去书店:q

“只要上街，我就去书店”符号化为q p →。

(6) 小杨晚上做完了作业:p

小杨晚上没有其它事情:q

小杨晚上看电视:r

小杨晚上听音乐:s

“如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐”符号化为s r q p ∨→∧。

(7) 林芳在家里:p

林芳在做作业:q

林芳在看电视:r

“如果林芳在家里，那么他不是在做作业就是在看电视”符号化为r q p ∨→。

(8) 三角形三条边相等:p

三角形三个角相等:q

“三角形三条边相等是三个角相等的充分条件”符号化为q p →。

(9) 我进城:p

我有时间:q

“我进城的必要条件是我有时间”符号化为q p →。

(10) 他唱歌:p ，他心情愉快:q

“他唱歌的充分必要条件是心情愉快”符号化为q p ↔。

(11) 图书馆开门小王病了，小王在图书馆看书，:::r q p

“小王总是在图书馆看书，除非他病了或者图书馆不开门”符号化为p r q →¬∨¬)(。 3. 列出除∧，∨，⊕，→，↔之外的所有二元联结词的真值表。

解 共有16个二元联结词，记除∧，∨，⊕，→，↔之外的二元联结词为1121,,,ΔΔΔ…。 p q q p 1Δq p 2Δq p 3Δq p 4Δq p 5Δq p 6Δ

0 0 0 0 0 0 0 1

0 1 0 0 0 1 1 0

1 0 0 1 1 0 0 0 1 1 0 0 1 0 1 0

p q q p 7Δq p 8Δq p 9Δq p 10Δq p 11Δ

0 0 1 1 1 1 1

0 1 0 0 1 1 1

1 0 1 1 0 1 1

1 1 0 1 0 0 1

4. 求下列公式在真值赋值)0/,0/,1/,1/(4321p p p p 下的值：

(1) )(321p p p ∧∨

(2) ))()(()(4321321p p p p p p p ∨∧∨¬∨∧∧

(3) )))((()(4321321p p p p p p p ¬∧¬∨∧¬∨¬∨∧¬

(4) 4312)(p p p p ∨¬→¬↔

(5) )()(4231p p p p →¬∧↔

(6) 421321)(p p p p p p ¬∨↔¬∧→∨

(7) )()(4231p p p p ⊕¬∧↔

解 记真值赋值)0/,0/,1/,1/(4321p p p p 为v 。

(1) 1)01(1))((321=∧∨=∧∨p p p v 。

(2) 1))00()11(()011()))()(()((4321321=∨∧∨¬∨∧∧=∨∧∨¬∨∧∧p p p p p p p v

(3) ))))((()((4321321p p p p p p p v ¬∧¬∨∧¬∨¬∨∧¬。

1)0)0)11(((0)11(=¬∧¬∨∧¬∨¬∨∧¬=

(4) 100)11())((4312=∨¬→¬↔=∨¬→¬↔p p p p v 。

(5) 0)01()01())()((4231=→¬∧↔=→¬∧↔p p p p v 。

(6) 101)101(1))((421321=¬∨↔¬∧→∨=¬∨↔¬∧→∨p p p p p p v 。

(7) 0)01()01())()((4231=⊕¬∧↔=⊕¬∧↔p p p p v 。

5. 用真值表判断以下公式是不是永真式、永假式、可满足式。

(1) ))()(()(r q p r q r p →∨→→→→

(2) p p p ¬→¬→)(

(3) ))(()(p q p q p →¬→→→

(4) ))()(())((r p q p r q p →→→→→→

(5) r r q r p q p →→∧→∧∧)()()(

(6) )(q p p →¬∧¬

(7) ))(()(p q p q p ¬→¬→→→

解 (1), (2), (4), (5), (7) 是永真式，(6) 是永假式，(3) 是非永真的可满足式。

6. 指出满足下列公式的所有真值赋值。

(1) )()(r p q p ∨¬∨∧

(2) ))((q p r q p ∨∧¬∧∨

(3) )()(r q r p r p ∨∧∨¬→∨

(4) )(r q p ↔⊕

解

(1) )0/,0/,0/(r q p ，)1/,0/,0/(r q p ，)0/,1/,0/(r q p ，)1/,1/,0/(r q p ，)1/,0/,1/(r q p ，

)0/,1/,1/(r q p ，)1/,1/,1/(r q p 。

(2) )0/,1/,0/(r q p ，)0/,0/,1/(r q p ，)1/,0/,1/(r q p ，)0/,1/,1/(r q p ，)1/,1/,1/(r q p 。

(3) )0/,0/,0/(r q p ，)0/,1/,0/(r q p 。

(4) )0/,0/,0/(r q p ，)1/,1/,0/(r q p ，)1/,0/,1/(r q p ，)0/,1/,1/(r q p 。

7. 若公式A 既不是永真式，

也不是永假式，则A 的每个替换实例一定既不是永真式，也不是永假式。对吗？

解 不对。若A 是非永真的可满足式，则它的替换实例中既有永真式，也有永假式，也有非永真的可

满足式。

8. 用真值表证明以下等值式。

(1)

(2)

(3)

(4)

9. 用等值演算证明以下等值式。

(1) )()(r p q r q p →→⇔→→

(2) r q p r p q p ∧→⇔→∧→)()(

(3) q r p q r q p →∧⇔→∨→)()(

(4) )()(q p p p q p →→¬⇔→→

(5) q r p q r q p →∨⇔→∧→)()(

(6) q p q p ¬↔⇔↔¬)(

解

(1) )()()()(r p q r p q r q p r q p →→⇔∨¬∨¬⇔∨¬∨¬⇔→→

(2) r q p r q p r p q p r p q p ∧→⇔∧∨¬⇔∨¬∧∨¬⇔→∧→)()()()()(

(3) q r p q r p q r q p q r q p →∧⇔→∧¬⇔∨¬∨∨¬⇔→∨→)()()(

(4) )(1)(q p p q p p p q p p q p →→¬⇔∨¬∨¬¬⇔⇔∨¬∨¬⇔→→

(5) q r p q r q p q r q p ∨¬∧¬⇔∨¬∧∨¬⇔→∧→)()()()()(q

r p q r p →∨⇔∨∨¬⇔)( (6) q p q p q p q p q p ¬↔⇔¬⊕¬⇔⊕⊕⊕⇔⊕⇔↔¬)(1))1(()(

10. 用等值演算证明以下公式是永真式。

(1) p q p p q ↔→¬∧→)()(

(2) )()()(s q r p s r q p ∧→∧→→∧→

(3) )()()()(s r q p s p r p q p ∨∨→→→∨→∨→

(4) )()()(r q r p r q p →∨→→→∨

解

(1) p q p p q ↔→¬∧→)()(1)()(⇔↔⇔↔¬∨∧∨¬⇔p p p q p p q

(2) )()()(s q r p s r q p ∧→∧→→∧→

s q r p s r q p ∧→∧∧∨¬∧∨¬⇔)()(

s q r s r p q p ∧→∧∨¬∧∧∨¬⇔)()(

1⇔∧→∧∧∧⇔s q r s p q

(3) )()()()(s r q p s p r p q p ∨∨→→→∨→∨→

)(s r q p s p r p q p ∨∨→→∨¬∨∨¬∨∨¬⇔

1⇔∨∨∨¬→∨∨∨¬⇔s r q p s r q p

(4) )()()(r q r p r q p →∨→→→∨

r q r p r q p ∨¬∨∨¬∨∨∨¬¬⇔))((

r q p r q p ∨¬∨¬∨¬∧∨⇔))((

111)()(⇔∧⇔∨¬∨¬∨¬∧∨¬∨¬∨∨⇔r q p r r q p q p

11. 用等值演算证明以下公式是永假式。

(1) p q p p q ¬↔→¬∧→)()(

(2) )()()(r p r q q p →¬∧→∧→

解

(1) p q p p q ¬↔→¬∧→)()(0)()(⇔¬↔⇔¬↔¬∨∧∨¬⇔p p p q p p q

(2) )()()(r p r q q p →¬∧→∧→)()()(r p r q q p ∨¬¬∧∨¬∧∨¬⇔

r p r q q p ¬∧∧∨¬∧∨¬⇔)()())(())((r r q p q p ¬∧∨¬∧∧∨¬⇔

0⇔¬∧¬∧∧⇔r q q p

12. 找出与下列公式等值的尽可能简单的由},{∧¬生成的公式。

13. 找出与下列公式等值的尽可能简单的由},{∨¬生成的公式。

(1) )(p r q p →¬∧¬∧¬

(2) q p r q p ∧¬∧¬∨→)(

(3) p q p ¬∧∧

解

(1) )(p r q p →¬∧¬∧¬

)(p r q p ∨¬¬∧¬∧¬⇔

)()(p q p r q p ∧¬∧¬∨¬¬∧¬∧¬⇔

r q p ¬¬∧¬∧¬⇔)(r q p ¬∨∨¬⇔

(2) ))(()()(q p r q p q p r q p q p r q p ¬∨∨¬∨∨¬¬¬⇔∧¬∧¬∨∨¬⇔∧¬∧¬∨→

(3) )(p q p p q p ∨¬∨¬¬⇔¬∧∧

14. 设A 是由}{↔生成的公式。证明：A 是永真式当且仅当每个命题变元在A 中出现偶数次。 证 首先证明：若A 是由}{↔生成的仅出现一个命题变元p 的公式，则

⎩

⎨⎧⇔中出现奇数次在若中出现偶数次在若 1A p p A p A 对p 在A 中的出现次数进行归纳。

① 若p 在A 中出现1次，即A 为p ，显然p A ⇔。

② 若p 在A 中出现2次，即A 为p p ↔，显然1⇔A 。

③ 设p 在A 中的出现n 次，A 为C B ↔，

p 在B ，C 中的出现次数分别为k 和l ，则l k n +=，n k <且n l <。若n 为偶数，则k 和l 的奇偶性相同，B 和C 等值于同一公式，1⇔A 。若n 为奇数，则k 和l 的奇偶性不同，B 和C 中一个等值于p ，另一个是永真式，因此p p A ⇔↔⇔1。 设在A 中的出现的所有命题变元为n p p ,,1 ，它们的出现次数分别为n k k ,,1 。因为 A B A B B A B A ↔⇔⊕¬⇔⊕¬⇔↔)()(，并且

11))(()(⊕⊕⊕⊕⇔⊕⊕¬¬⇔↔↔C B A C B A C B A

)())((11C B A C B A C B A ↔↔⇔⊕¬⊕¬⇔⊕⊕⊕⊕⇔

所以↔满足交换律和结合律，存在由}{↔生成的公式n B B ,,1 ，使得n B B A ↔↔⇔ 1，并且i B 仅出现命题变元i p ，出现次数为i k ，n i ,,1 =。若n k k ,,1 全为偶数，则

1111⇔⊕⊕⇔↔↔⇔ n B B A 。若n k k ,,1 中有m l l k k ,,1 是奇数，则

m l l n p p B B A ↔↔⇔↔↔⇔ 11，显然A 不是永真式。

15. 设A 是由}{⊕生成的公式。证明：A 是永假式当且仅当每个命题变元在A 中出现偶数次。 证 首先证明：若A 是由}{⊕生成的仅出现一个命题变元p 的公式，则

⎩

⎨⎧⇔中出现奇数次在若中出现偶数次在若 0A p p A p A 对p 在A 中的出现次数进行归纳。

① 若p 在A 中出现1次，即A 为p ，显然p A ⇔。

② 若p 在A 中出现2次，即A 为p p ⊕，显然0⇔A 。

③ 设p 在A 中的出现n 次，A 为C B ⊕，

p 在B ，C 中的出现次数分别为k 和l ，则l k n +=，n k <且n l <。若n 为偶数，则k 和l 的奇偶性相同，B 和C 等值于同一公式，0⇔A 。若n 为奇数，则k 和l 的奇偶性不同，B 和C 中一个等值于p ，另一个是永假式，因此p p A ⇔⊕⇔0。 设在A 中的出现的所有命题变元为n p p ,,1 ，它们的出现次数分别为n k k ,,1 。因为⊕满足交换律和结合律，所以存在由}{⊕生成的公式n B B ,,1 ，使得n B B A ⊕⊕⇔ 1，并且i B 仅出现命题变元i p ，出现次数为i k ，n i ,,1 =。若n k k ,,1 全为偶数，则0001⇔⊕⊕⇔⊕⊕⇔ n B B A 。若n k k ,,1 中有m l l k k ,,1 是奇数，则m l l n p p B B A ⊕⊕⇔⊕⊕⇔ 11，显然A 不是永假式。

16. 北京、上海、天津、广州四市乒乓球队比赛，三个观众猜测比赛结果。

甲说：“天津第一，上海第二。”

乙说：“天津第二，广州第三。”

丙说：“北京第二，广州第四。”

比赛结果显示，每人猜对了一半，并且没有并列名次。

问：实际名次怎样排列？

解 用字母表示命题如下：

广州第四。

广州第三，天津第二，天津第一，上海第二，北京第二，::::::432122s s r r q p 由已知条件列出以下方程：

甲猜对了一半：121=⊕q r

乙猜对了一半：132=⊕s r

丙猜对了一半：142=⊕s p

每个城市只能得一个名次：021=∧r r ，043=∧s s

没有并列名次：022=∧q p ，022=∧r p ，022=∧q r

解以上8个方程组成的方程组：

000)()()(1221221222=⊕=∧⊕∧=⊕∧=∧=q r r r q r r r r

将02=r 代入132=⊕s r 得13=s ，将13=s 代入043=∧s s 得04=s ，将04=s 代入142=⊕s p 得12=p ，将12=p 代入022=∧q p 得02=q ，将02=q 代入121=⊕q r 得11=r 。因此，天津第一，北京第二，广州第三，上海第四。

17. 某勘探队取回一块矿样，三人判断如下。

甲说：“矿样不含铁，也不含铜。”

乙说：“矿样不含铁，含锡。”

丙说：“矿样不含锡，含铁。”

已经知道，这三人中有一个是专家，一个是老队员，一个是实习队员。化验结果表明：这块矿样只含一种金属，专家的两个判断皆对，老队员的判断一对一错，实习队员的两个判断皆错。问：这三人的身分各是什么？

解 矿样含锡矿样含铜，矿样含铁，:::r q p 。

甲说的两句话为：p ¬，q ¬

乙说的两句话为：p ¬，r

丙说的两句话为：r ¬，p

如果用一个公式表达出这三人中有一个是专家，一个是老队员，一个是实习队员，公式会非常复

杂。其实我们不必完全写出这样的公式。因为矿样只含一种金属，所以0=∧q p ，0=∧r q ，0=∧p r 。甲是实习队员，即甲说的两句话都是错的，可表示为：q p ∧。乙是实习队员，即乙说的两句话都是错的，可表示为：r p ¬∧。丙是实习队员，即丙说的两句话都是错的，可表示为：p r ¬∧。甲、乙、丙三人中至少有一个是实习队员，可表示为：

1)()()(=¬∧∨¬∧∨∧p r r p q p

因为0=∧q p ，所以1)()(=¬∧∨¬∧p r r p ，即1=⊕r p ，p 和r 中恰好有一个为1，因此0=q 。甲是老队员，即甲说的话一半对一半错，可表示为：q p ¬⊕¬。乙是老队员，即乙说的话一半对一半错，可表示为：r p ⊕¬。丙是老队员，即丙说的话一半对一半错，可表示为：p r ⊕¬。甲、乙、丙三人中有奇数个老队员，可表示为：

1)()()(=⊕¬⊕⊕¬⊕¬⊕¬p r r p q p

由教材上的等值式可得到

)()()(p r r p q p ⊕¬⊕⊕¬⊕¬⊕¬

)()()(p q r r p p ⊕¬⊕⊕¬⊕¬⊕¬⇔

)1(10p q ⊕⊕⊕⊕⇔p q ⊕⇔

又知道0=q ，所以1=p 。因为0=∧p r ，所以0=r 。因此，甲说的话一半对一半错，甲是老队员。乙说的话全错，乙是实习队员。丙说的话全对，丙是专家。

18. 先用等值演算证明下列等值式，再用对偶定理得出新等值式。

(1) p q p q p ⇔∨¬¬∨¬∨¬¬)()(

(2) )()()()(q p q p q p q p ∨¬¬⇔¬∨¬∧∨∧¬∨

(3) 1))((⇔∧∨¬¬∨p q p q

解

(1) p q q p q p q p q p q p ⇔¬∨∧⇔¬∧∨∧⇔∨¬¬∨¬∨¬¬)()()()()(，由对偶定理得

p q p q p ⇔∧¬¬∨¬∧¬¬)()(。

(2) )())(()()()(q p q q p q p q p q p ¬∨¬∧∧¬∨⇔¬∨¬∧∨∧¬∨

)()()(q p p p q p p ¬∧∨¬∧⇔¬∨¬∧⇔)(q p q p ∨¬¬⇔¬∧⇔由对偶定理得)()()()(q p q p q p q p ∧¬¬⇔¬∧¬∨∧∨¬∧。

(3)

19. 设A 是由},,,1,0{∨∧¬生成的公式，*A 与A 互为对偶式。

(1) 若A 是永真式，则*A 是永假式。

(2) 若A 是永假式，则*A 是永真式。

证明

(1) 设A 是永真式，则1⇔A ，由对偶定理得0*=A ，因此*A 是永假式。

(2) 设A 是永假式，则0⇔A ，由对偶定理得1*=A ，因此*A 是永真式。

20. 证明以下联结词集合是极小完全集。

(1) },0{→

(2) },{→⊕

(3) },,{↔∧⊕

(4) },,{↔∨⊕

证明

(1) 00→⇔∨¬⇔¬p p p ，因为},{→¬是完全集，所以},0{→是完全集。任取由}0{生成的不

出现除命题变元p 之外的命题变元的公式A ，令真值赋值)0/(p v =，则0)(=A v ，而1)(=¬p v ，因此}0{不能定义¬。所以}0{不是完全集。任取由}{→生成的仅出现命题变元p 的公式A ，令真值赋值)1/(p v =，则1)(=A v ，而0)(=¬p v ，因此}{→不能定义¬。所以}{→不是完全集。所以},{→¬是极小完全集。

(2) )(1p p p p p →⊕⇔⊕⇔¬，因为},{→¬是完全集，所以},{→⊕是完全集。任取由}{⊕生成

的仅出现除命题变元p 的公式A ，令真值赋值)0/(p v =，则0)(=A v ，而1)(=¬p v ，因此}{⊕不能定义¬。所以}{⊕不是完全集。}{→不是完全集。所以},{→⊕是极小完全集。

(3) )(1p p p p p →⊕⇔⊕⇔¬，因为},{∧¬是完全集，所以},,{↔∧⊕是完全集。任取由}

,{∧⊕生成的仅出现除命题变元p 的公式A ，令真值赋值)0/(p v =，则0)(=A v ，而1)(=¬p v ，因此},{∧⊕不能定义¬。所以},{∧⊕不是完全集。任取由},{↔∧生成的仅出现命题变元p 的公式A ，令真值赋值)1/(p v =，则1)(=A v ，而0)(=¬p v ，因此},{↔∧不能定义¬。所以},{↔∧不是完全集。},{↔⊕不是完全集。所以},,{↔∧⊕是极小完全集。

(4) )(1p p p p p →⊕⇔⊕⇔¬，因为},{∨¬是完全集，所以},,{↔∨⊕是完全集。任取由}

,{∨⊕生成的仅出现除命题变元p 的公式A ，令真值赋值)0/(p v =，则0)(=A v ，而1)(=¬p v ，因此},{∨⊕不能定义¬。所以},{∨⊕不是完全集。任取由},{↔∨生成的仅出现命题变元p 的公式A ，令真值赋值)1/(p v =，则1)(=A v ，而0)(=¬p v ，因此},{↔∨不能定义¬。所以},{↔∨不是完全集。},{↔⊕不是完全集。所以},,{↔∨⊕是极小完全集。

21. 证明以下联结词集合不是完全集。

(1) },,,{↔→∨∧

(2) },,{∨∧⊕

证明

(1) 任取由},,,{↔→∨∧生成的仅出现命题变元p 的公式A ，令真值赋值)1/(p v =，则1)(=A v ，

而0)(=¬p v ，因此},,,{↔→∨∧不能定义¬。所以},,,{↔→∨∧不是完全集。

(2) 任取由},,{∨∧⊕生成的仅出现命题变元p 的公式A ，令真值赋值)0/(p v =，则0)(=A v ，而

1)(=¬p v ，因此},,{∨∧⊕不能定义¬。所以},,{∨∧⊕不是完全集。

22. 二元联结词↑（称为“与非”

）和↓（称为“或非”）的真值表如下。 p q q p ↑q

p ↓0 0 1 1

0 1 1 0

1 0 1 0

1 1 0 0

证明：

(1) }{↑是完全集。

(2) }{↓是完全集。

(3) 若Δ是二元联结词且}{Δ是完全集，则Δ是↑或↓。

证明

(1) p p p ↑⇔¬，)()()()(q p q p q p q p q p ↑↑↑⇔↑¬⇔∧¬¬⇔∧

因为},{∧¬是完全集，所以}{↑是完全集。

(2) p p p ↓⇔¬，)()()()(q p q p q p q p q p ↓↓↓⇔↓¬⇔∨¬¬⇔∨

因为},{∨¬是完全集，所以}{↓是完全集。

(3) 若000=Δ或111=Δ，则¬不能由}{Δ定义。因此，100=Δ且011=Δ。若0110Δ≠Δ，则Δ

的真值表的最后一列有偶数个1，真值表最后一列有奇数个1的∧不能由}{Δ定义。所以，0110Δ=Δ。若10110=Δ=Δ，则Δ是↑。若00110=Δ=Δ，则Δ是↓。 23. 三元联结词Δ的真值表如下。 p q r )

,,(r q p Δ0 0 0 1

0 0 1 1

0 1 0 0

0 1 1 0

1 0 0 0

1 0 1 0

1 1 0 1

1 1 1 0

证明}{Δ是极小完全集。

证 pqq q p Δ⇔↓，因为}{↓是完全集，所以}{Δ是极小完全集。

24. 在下列公式中，哪些是析取范式，哪些是合取范式?

p ，q p ∨，r q p ∧∨)(，r p ¬∧，p p ¬∨，r q q p ∨¬∧∨))((

解 p ，q p ∨，r p ¬∧，p p ¬∨是析取范式，p ，q p ∨，r q p ∧∨)(，r p ¬∧，p p ¬∨是合取范式。 25. 在下列公式中，哪些是关于p , q , r 的主析取范式，哪些是关于p , q , r 的主合取范式？

r q p ∨∨,r q p ∧¬∧,)()(r q p r q p ¬∨∨∧¬∨∨,)(r q p ∧∨,)()(r q p q p p ∨∨∧∨¬∨ 解 r q p ∧¬∧是关于p , q , r 的主析取范式，r q p ∨∨是关于p , q , r 的主合取范式。 26. 是否有这样的公式，它既是主合取范式，又是主析取范式？如果有，举出一例。 解 有。p 既是关于p 的主析取范式，又是关于p 的主合取范式。

27. 求下列公式的主范式，进而判断其是否永真式、永假式、可满足式。

(1) r q p →∧¬

(2) r q p →→)(

(3) )(q p q p ¬↔→¬∨¬

(4) ))((r q q p p →¬∨→∨

(5) )()(r q p r q p ¬∧¬→¬∧∧→

(6) )(q p q p ¬∨¬∧∧

解

(1) r q p →∧¬r q p ∨∧¬¬⇔)(r q p ∨¬∨⇔

r q p →∧¬的主合取范式是r q p ∨¬∨，包含一个极大项，因此它是非永真的可满足式。

(2) r q p →→)(r q p ∨∨¬¬⇔)(

r q p ∨¬∧¬¬⇔)()()(r q r p ∨¬∧∨⇔

))(())((r q p p r q q p ∨¬∨¬∧∧∨¬∧∨⇔

)()()(r q p r q p r q p ∨¬∨¬∧∨¬∨∧∨∨⇔

r q p →→)(的主合取范式是)()()(r q p r q p r q p ∨¬∨¬∧∨¬∨∧∨∨，包含了三个极大项，因此它是非永真的可满足式。

(3) )(q p q p ¬↔→¬∨¬))()(()(q p q p q p ∨∧¬∨¬∨¬∨¬¬⇔

)()(q p q p ∨∨¬∨¬¬⇔q p q p ∨∧∧⇔)(q p ∨⇔

)(q p q p ¬↔→¬∨¬的主合取范式为q p ∨，包含了一个极大项，因此它是非永真的可满足式。

(4) ))((r q q p p →¬∨→∨))((r q q p p ∨¬¬∨∨¬∨⇔1⇔

))((r q q p p →¬∨→∨的主合取范式为1，不包含任何极大项，因此它是永真式。

(5) )()(r q p r q p ¬∧¬→¬∧∧→

))(())((r q p r q p ¬∧¬∨¬¬∧∧∨¬⇔

)()()()(r q r q p r q r q p p p ¬∧¬∧∧∨∧∧∨¬∧¬∧¬∨∧¬⇔

)()(r q p r q p ∧∧∨¬∧¬∧¬⇔

)()(r q p r q p ¬∧¬→¬∧∧→的主析取范式为)()(r q p r q p ∧∧∨¬∧¬∧¬，包含了两个极小项，因此它是非永真的可满足式。

(6) )(q p q p ¬∨¬∧∧

)())(())((q p q p p q q p ¬∨¬∧∨¬∧∧¬∧∨⇔

)()()()(q p q p q p q p ¬∨¬∧∨¬∧¬∨∧∨⇔

)(q p q p ¬∨¬∧∧的主合取范式为)()()()(q p q p q p q p ¬∨¬∧∨¬∧¬∨∧∨，包含了所有的四个极大项，因此它是永假式。

28. 用主范式证明下列等值式。

(1) q p q p ∧→→)()()(p r p p →∧→¬⇔

(2) )()(r p q p →∧→r q p ∧→⇔

解

(1) q p q p ∧→→)()()(q p q p ∧∨∨¬¬⇔

)()(q p q p ∧∨¬∧⇔))(())((r r q p r r q p ∨¬∧∧∨∨¬∧¬∧⇔

)()())()(r q p r q p r q p r q p ∧∧∨¬∧∧∨∧¬∧∨¬∧¬∧⇔

)()(p r p p →∧→¬)()(p r p p ∨¬∧∨¬¬⇔

)(r p p ¬∨∧⇔p ⇔)()(r r q q p ∨¬∧∨¬∧⇔

)()())()(r q p r q p r q p r q p ∧∧∨¬∧∧∨∧¬∧∨¬∧¬∧⇔

q p q p ∧→→)(和)()(p r p p →∧→¬等值于同一个关于,,p q r 的主析取范式 )()())()(r q p r q p r q p r q p ∧∧∨¬∧∧∨∧¬∧∨¬∧¬∧，因此，

q p q p ∧→→)()()(p r p p →∧→¬⇔。

(2) )()(r p q p →∧→)()(r p q p ∨¬∧∨¬⇔

))(())((r q q p r r q p ∨¬∧∨¬∧¬∧∨∨¬⇔

)()()()(r q p r q p r q p r q p ∨¬∨¬∧∨∨¬∧¬∨∨¬∧∨∨¬⇔

)()()(r q p r q p r q p ¬∨∨¬∧∨∨¬∧∨¬∨¬⇔

r q p ∧→)(r q p ∧∨¬⇔)()(r p q p ∨¬∧∨¬⇔

))(())((r q q p r r q p ∨¬∧∨¬∧¬∧∨∨¬⇔

)()()()(r q p r q p r q p r q p ∨¬∨¬∧∨∨¬∧¬∨∨¬∧∨∨¬⇔

)()()(r q p r q p r q p ¬∨∨¬∧∨∨¬∧∨¬∨¬⇔

)()(r p q p →∧→和r q p ∧→的主合取范式相同，所以，

)()(r p q p →∧→r q p ∧→⇔。

29. 判断以下关系是否成立，并说明理由。

(1) q p ∨,q p =¬|

(2) q p ∨, ,p q =|

(3) 11q p →,22q p →,2121|q q p p ∧=∧

(4) q p →,q p p q ∨=→|

(5) r q p →∧,r q p r q p ∧∧=¬→∨|

解

(1) 若真值赋值v 使得1)()(=¬=∨p v q p v ，则1)(=q v 。所以q p ∨,q p =¬|。

(2) 真值赋值)1/,0/(q p v =使得1)()()(==→=∨q v q p v q p v ，但0)(=p v ，所以

q p ∨,q p →,p q /|=。

(3) 若真值赋值v 使得1)()()(212211=∧=→=→p p v q p v q p v ，则1)()(21==p v p v ，因而

1)()(21==q v q v ，1)(21=∧q q v 。所以11q p →,22q p →,2121|q q p p ∧=∧。

(4) 真值赋值)0/,0/(q p v =使得1)()(=→=→p q v q p v ，但0)(=∨q p v 。所以

q p →,q p p q ∨=→/|。

(5) 真值赋值)0/,1/,0/(r q p v =使得1)()(=¬→∨=→∧r q p v r q p v ，但0)(=∧∧r q p v 。所以

r q p →∧,r q p r q p ∧∧=¬→∨/|。

30. 判断以下公式组成的集合是否可满足，并说明理由。

(1) )()(r s q p ¬∧∨∨，)(r s ¬∧¬

(2) 1p ，21p p ∨¬，321p p p ∨¬∨¬，…，11+∨¬∨∨¬n n p p p ，…

(3) q p ∨，q p ¬∨¬，q p →

解

(1) 可满足。真值赋值)0/,1/,0/,1/(s r q p 满足它。

(2) 可满足。若真值赋值v 使得 ,2,1,1)(==i p v i ，则v 满足它。

(3) 可满足。真值赋值)1/,0/(q p 满足它。

31. 设A , B , C 是任意公式。C B A =∨|当且仅当C A =|且C B =|。

证明1

（⇒）设C B A =∨|。任取满足A 的真值赋值v ，则1)(=∨B A v ，因为C B A =∨|，所以1)(=C v 。这表明C A =|。任取满足B 的真值赋值v ，则1)(=∨B A v ，因为C B A =∨|，所以1)(=C v 。这表明C B =|。

（⇐）设C A =|且C B =|。任取满足B A ∨的真值赋值v ，则1)(=A v 或1)(=B v 。 ① 若1)(=A v ，因为C A =|，所以1)(=C v 。

② 若1)(=B v ，因为C B =|，所以1)(=C v 。

因此，C B A =∨|。

证明2

C B A C B A C B A ∨¬∧¬⇔∨∨¬⇔→∨)()(

)()()()(C B C A C B C A →∧→⇔∨¬∧∨¬⇔

C B A =∨|

当且仅当C B A →∨是永真式

当且仅当)()(C B C A →∧→是永真式

当且仅当C A →和C B →都是永真式

当且仅当C A =|且C B =|

32. 设1Γ和2Γ是公式集合，B 是公式，B Γ=|2，对于2Γ中每个公式A ，A Γ=|1。证明：B Γ=|1。 证 任取满足1Γ的真值赋值v 。对于2Γ中每个公式A ，因为A Γ=|1，

所以1)(=A v 。这表明v 满足2Γ。又因为B Γ=|2，所以1)(=B v 。因此，B Γ=|1。

33. 公式集合Γ不可满足当且仅当0|=Γ。

证 （⇒）设0/|=Γ，则存在真值赋值v 满足Γ且0)0(=v ，因此Γ可满足。

（⇐）设0|=Γ。若Γ可满足，有真值赋值v 满足Γ，由0|=Γ得出1)0(=v ，这是不可能的。因此，Γ不可满足。

34. 设n 是正整数，}1|)({},,,{111n j i q q p p q p q p Γj i n n n ≤<≤∧¬∪∨∨→→= 。证明：

)()(|11n n p q p q Γ→∧∧→= 。

证 设真值赋值v 满足Γ，则1)(1=∨∨n p p v ，存在n i ≤使1)(=i p v 。因为1)(=→i i q p v ，所以

1)(=i q v 。若i j <≤1，因为1))((=∧¬i j q q v ，因此0)(=j q v 。若n j i ≤<，因为1))((=∧¬j i q q v ，因此0)(=j q v 。所以1))()((11=→∧∧→n n p q p q v 。