离散数学(第五版)清华大学出版社第1章习题解答.doc

离散数学（第五版）清华大学出版社第1章习题解答
1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），
（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。
分析 首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。
本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，
所以它们都不是命题。
其次，4）这个句子是陈述句，但它表示的 判断结果是不确定。又因为（1），
（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们
都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，
（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来
的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许
多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，
一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与”
联结的是主语，构成简单命题。例如，（14）、（15）中的“与”与“和”是联结
的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或
“与”出现的命题时，要根据命题所陈述的含义加以区分。
1．2 （1）p: 2是无理数，p为真命题。
（2）p:5能被2整除，p为假命题。
（6）p→q。其中，p:2是素数，q：三角形有三条边。由于p与q都是真
命题，因而p→q为假命题。
（7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。由于p为假命
题，q为真命题，因而p→q为假命题。
（8）p:2000年10月1日天气晴好，今日（1999年2月 13日）我们还不
知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。
（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。
1
（10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。
（12）p∨q，其中，p:4是偶数，q:4是奇数。由于q是假命题，所以，q
为假命题，p∨q为真命题。
（13）p∨q，其中，p:4是偶数，q:4是奇数，由于q是假命题，所以，p∨q
为假命题。
（14） p：李明与王华是同学，真值由具体情况而定（是确定的）。
（15） p：蓝色和黄色可以调配成绿色。这是真命题。
分析 命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不
能马上知道，但它们的真值不会变化，是客观存在的。
1．3 令p:2+2=4,q:3+3=6,则以下命题分别符号化为
（1）p→q
（2）p→¬q
（3）¬p→q
（4）¬p→¬q
（5）p↔q
（6）p↔¬q
（7）¬p→q
（8）¬p↔¬q
以上命题中，（1），（3），（4），（5），（8）为真命题，其余均为假命题。
分析 本题要求读者记住p→q及p↔q的真值情况。p→q为假当且仅当
p为真,q为假,而p↔q为真当且仅当p与q真值相同.由于p与q都是真命题，
在4个蕴含式中，只有（2）p→r，其中，p同（1），r：明天为3号。
在这里，当p为真时，r一定为假，p→r为假，当p为假时，无论r为真
还是为假，p→r为真。
2
1．5 （1）p∧q，其中，p：2是偶数，q：2是素数。此命题为真命题。
（2）p∧q，其中，p：小王聪明，q：小王用功
（3）p∧q，其中，p：天气冷，q：老王来了
（4）p∧q，其中，p：他吃饭，q：他看电视
（5）p∧q，其中，p：天下大雨，q：他乘公共汽车上班
（6）p→q，其中，p，q的含义同（5）
（7）p→q，其中，p，q的含义同（5）
（8）¬p↔¬q，其中，p：经一事，q：长一智
分析 1°在前4个复合命题中，都使用了合取联结词，都符号化为合取式，
这正说明合取联结词在使用时是很灵活的。在符号化时，应该注意，不要将联结
词部分放入简单命题中。例如，在（2）中，不能这样写简单命题：p：小王不但
聪明，q：小王而且用功。在（4）中不能这样写：p：他一边吃饭， q：他一边
看电视。
2° 后4个复合命题中，都使用了蕴含联结词，符号化为蕴含式，在这里，
关键问题是要分清蕴含式的前件和后件。
p→q所表达的基本逻辑关系为，p是q的充公条件，或者说q是p的必要
条件，这种逻辑关系在叙述上也是很灵活的。例如，“因为p，所以q”，“只要p，
就q”“p仅当q”“只有q才p”“除非q，否则¬p”“没有q，就没有p”等都表
达了q是p的必要条件，因而都符号化为p→q或¬p↔¬q的蕴含式。
在（5）中，q是p的必要条件，因而符号化为p→q，而在（6）（7）中，
p成了q的必要条件，因而符号化为q→p。
在（8）中，虽然没有出现联结词，但因两个命题的因果关系可知，应该符
号化为蕴含式。
1．6 （1），（2）的真值为0，（3），（4）的真值为1。
分析 1° （1）中公式含3个命题变项，因而它应该有23=8个赋值：000，
3
001，…，111题中指派p, q为0, r为1，于是就是考查001是该公式p∧(q∧r)的成真赋值，还是成假赋值，易知001是它的成假赋值。
2° 在公式（2），（3），（4）中均含4个命题就项，因而共有24=16个赋值：0000，0001，…，1111。现在考查0011是它的成假赋值。
1.7 （1），（2），（4），（9）均为重言式，（3），（7）为矛盾式，（5），（6），（8），（10）为非重言式的可满足式。
一般说来，可用真值表法、等值演算法、主析取范式（主合取范式）法等判断公式的类型。
（1）对（1）采用两种方法判断它是重言式。
真值表法
表1.2给出了（1）中公式的真值表，由于真值表的最后一列全为1，所以，（1）为重言式。
p∨q∨rp→(p∨q∨r)
p q r
0 0 0 0 1
0 0 1 1 1
0 1 0 1 1
0 1 1 1 1
1 0 0 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 1 1
等值演算法
p→(p∨q∨r)
⇔¬p∨(p∨p∨r) （蕴含等值式）
⇔(¬p∨p)∨p∨r （结合律）
⇔1∨q∨r （排中律）
⇔1 （零律）
4
由最后一步可知，（1）为重言式。
（2）用等值演算法判（2）为重言式。
(p→¬p)→¬p
⇔(¬p∨¬)→¬p （蕴含等值式）
⇔¬p∨¬p （等幂律）
⇔ p∨¬p （蕴含等值式）
⇔1 （排中律）
（3）用等值演算法判（3）为矛盾式
¬(p→q)∧q
⇔¬(p¬∨q)∧q （蕴含等值式）
⇔ p∨¬q∧q （德·摩根律）
⇔ p∨(¬q∧q) （结合律）
⇔ p∧0 （矛盾律）
⇔0 （零律）
由最后一步可知，（3）为矛盾式。
（5）用两种方法判（5）为非重言式的可满足式。
真值表法
p q ¬p ¬p→qq→¬p(¬p→q)→(q→¬p)0 0 1 0 1 1
0 1 1 1 1 1
1 0 0 1 1 1
1 1 0 1 0 0
由表1.3可知（5）为非重言式的可满足式。
主析取范式法
(¬p→q)→(q→¬p)
⇔(p∨q)→(¬q∨¬p)
5
⇔¬(p∨q)∨(¬q∨¬p)
⇔(¬p∨¬q)∨¬q∨¬p
⇔¬p∨¬q
⇔(¬p∧1)∨(1∧¬q)
⇔(¬p∧(¬q∨q)∨((¬p∨p)∧¬q)
⇔(¬p∧¬q)∨(¬p∨q)∨(¬p∧¬q)∨(p∨¬q)
⇔(¬p∧¬q)∨(¬p∨q)∨(¬p∧¬q)
⇔m0∨m1∨m2.
在（3）的主析取范式中不含全部（4个）极小项，所以（3）为非重言式的可满足式，请读者在以上演算每一步的后面，填上所用基本的等值式。
其余各式的类型，请读者自己验证。
分析 1 真值表法判断公式的类别是万能。公式A为重言式当且仅当A的o
真值表的最后一旬全为1；A为矛盾式当且仅当A的真值表的最后一列全为0；A为非重言式的可满足式当且仅当A的真值表最后一列至少有一个1，又至少有一个0。真值表法不易出错，但当命题变项较多时，真值表的行数较多。
2o 用等值演算法判断重言式与矛盾式比较方例，A为重言式当且仅当A与1等值；A为矛盾式当且仅当A与0等值，当A为非重言式的可满足式时，经过等值演算可将A化简，然后用观察法找到一个成真赋值，再找到一个成假赋值，就可判断A为非重言式的可满足式了。例如，对（6）用等值演算判断它的类型。
(p∧¬p)↔q
⇔0↔q （矛盾律）
⇔(p→q)∧(q→0) （等价等值式）
⇔(¬0∨q)∧(¬q∨0) （蕴含等值式）
⇔(1∨q)∧¬q （同一律）
⇔1∧¬q （零律）
6
⇔¬q （同一律）
到最后一步已将公式化得很简单。由此可知，无论p取0或1值，只要q取0值，原公式取值为1，即00或10都为原公式的成真赋值，而01，11为成假赋值，于是公式为非重言式的可满足式。
用主析取范式判断公式的类型也是万能的。A为重言式当且仅当A的主析取范式含2n（n为A中所含命题变项的个数）个极小项；A为矛盾式当且仅当A的主析取范式中不含任何极小项，记它的主析取范式为0；A为非重言式的可满足式当且仅当A的主析取范式中含极小项，但不是完全的。
当命题变项较多时，用主析取范式法判公式的类型，运算量是很大的。
用主合取范式判断公式的类型也是万能的。A为重言式当且仅当A的主合取范式中不含任何极大项，此时记A的主合取范式为1；A为矛盾式当且仅当A的主合取范式含2n个极大项（n为A中含的命题变项的个数）；A为非重言式的可满足式当且仅当A的主析取范式中含含极大项，但不是全部的。
1.8 （1）从左边开始演算
(p∧q)∨(p∧¬q)
⇔ p∧(q∨¬q)（分配律）
⇔p∧1 （排中律）
⇔p.（同一律）
（2）从右边开始演算
p→(q∧r)
⇔¬p∨(q∧r) （蕴含等值式）
⇔(¬p∨q)∧(¬p∨r)（分配律）
⇔(p→q)∧(p→r).（蕴含等值式）
（3）从左边开始演算
¬(p↔q)
7
⇔((p→q)∧(q→p))
⇔¬((¬p∨q)∨(¬p∨q))
⇔¬((¬p∧q)∨(¬p∧)∨(q∧¬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∧q))
⇔¬((¬p∧q)∧(¬p∨q)∧(¬q∨p)∧(¬q∨q))⇔¬(1∧p∨q)∧(¬q∨p)∧1
⇔¬((p→q)∧(q→p))
⇔¬(p↔q).
读者填上每步所用的基本的等值式。1.9 （1）
¬((p∧q)→p)
⇔¬(¬(p∧q)∨p （蕴含等值式）⇔¬(¬(p∧q)∨p) （德·摩根律）⇔ p∧q∧¬p （结合律、交换律）⇔(p∧¬p)∧q （矛盾式）⇔0. （零律）
8
由最后一步可知该公式为矛盾式。
（2）((p→q)∧(q→p))→(p↔q)
⇔¬(¬(p∧q)∨p) （蕴含等值式）
由于较高层次等价号两边的公式相同，因而此公式无成假赋值，所以，它为重言式。
（3）(¬p→q)→(q→¬p)
⇔(p∨q)→(¬q∨¬p) （蕴含等值式）
⇔¬(p∨q)∨(¬q∨¬p) （蕴含等值式）
⇔(¬p∧q)∨¬q∨¬p （德·摩根律）
⇔¬q∨¬p （吸收律）
⇔¬p∨¬q. （交换律）
由最后一步容易观察到，11为该公式成假赋值，因而它不是重言式，又00，01，10为成真赋值，因而它不是矛盾式，它是非重言式的可满足式。
1.10 题中给出的F，G，H，R都是2元真值函数。给出的5个联结词集都是全功能集，可以用观察法或等值演算法寻找与真值函数等值的公式。
首先寻找在各联结词集中与F等值的公式。
（1）设A=¬(p→q)，易知A是{¬,→}中公式且与F等值，即F⇔A.
（2）设B=p∧¬q，易知B是{¬,∧}中公式且与F等值，即F⇔B.
（3）设C=¬(¬p∨q)，易知C是{¬,∧}中公式，且F⇔C.
（4）设D=(p↑(q↑q))↑(p↑(q↑q))，易知D为{↑}中公式，且F⇔D.
（5）设E=(p↓p)↓q，易知E为{↓}中公式，且F⇔E.
分析 1° 只要找到一个联结词集中与F等值的公式，经过等值演算就可以找出其他联结词集中与F等值的公式。例如，已知A=¬(p→q)是{¬,→}公式，且F⇔A。进行以下演算，就可以找到F等值的其他联结词集中的公式。对 A进行等值演算，消去联结词→，用¬，∧取代，得
9
A=¬(p→q)
⇔¬(¬p∨q)
⇔p∧¬q记为B.
则B为{¬,∧}中公式，且F⇔B。再对A进行等值演算，消去→，用¬，∧取代，得
A=¬(p→q)
⇔¬(¬p∨q)记为C.
则C为{¬,∧}中公式，且F⇔C。再对B进行演算，消去¬，→，用↑取代，在演算中，注意，对于任意的公式A，有
¬A⇔¬(A∧A)⇔A↑A.
B=p∧¬q
⇔ p∧(q↑q)
⇔¬¬(p∧(q↑q))
⇔¬(p↑(q↑q))
⇔(p↑(q↑q))↑(p↑(q↑q)记为D.
则D为{↑}中公式，且F⇔D.再对C进行演算，消去¬,∨,用↓取代，在演算中注意，对于任意的公式A
¬A⇔¬(A∨A)⇔A↓A.
C=¬(¬p∨q)
⇔¬p↓q
⇔(p↓p)↓q记为E.
则E为{↓}中公式，且F⇔E.
2° 开始找一个与某真值函数等值的公式的方法，除观察法外，就是根据
10
该真值函数的真值表，求它的主析取范式，而后进行等值演算即可。例如，由G的真值表可知G的主析取范式为m1∨m3，于是
G⇔m1∨m3
⇔(¬p∧q)∨(p∧q)
⇔(¬p∨p)∧q
⇔q.
由于公式q不带联结词，所以，它应该为任何联结词集中的合式公式。
3° 在各联结词集中找到的与某真值函数等值的公式并不唯一。例如，取
A=¬q→q.({¬,→}中公式)
B=q∧q.({¬,∧}中公式)
C=q∨q.({¬,∨}中公式)
D=(q↑q)↑(q↑q).({↑}中公式)
E=(q↓q)↓(q↓q).({↓}中公式)
则G⇔A⇔B⇔C⇔D⇔E,对于同一个真值函数G，找到与它等值的形式各异的公式。
对于H和R，请读者自己去完成。
1.11 （1）对C是否为矛盾式进行讨论。
当C不是矛盾式时，A∨C⇔B∨C，则一定有A⇔B，这是因为，此时，A∨C⇔A,B∨C⇔B，所以，有
A⇔A∨C⇔B∨⇔B
必有A⇔B
而当C不是矛盾式时，A∨C⇔B∨C，不一定有A⇔B，举反例如下：
设A,B,C均为含命题变项p,q的公式，A，B，C及A∨C,B∨C的真值表如表1.4所示，从表1.4可看出，A∨C⇔B∨C，但A⇔B。
表1.4
11
p q A B C AVC BVC
0 0 0 0 0 0 0
0 1 0 0 0 0 0
1 0 1 1 1 1 1
1 1 0 1 1 1 1
(2) 对C是否为重言式进行讨论:
若C为重言式,则A∧C⇔A,C⇔B,于是
A⇔A∧C⇔B∧C⇔B.
因而有
A⇔B
当 C 不是重言式时,请读者举反例说明, A∧C⇔B∧C时, 不一定有A⇔B.
(3) 若¬A⇔¬B,则A⇔B.证明如下:
A⇔¬¬A (双重否定律)
⇔¬¬B(¬A⇔¬B)
⇔B(双重否定律)
所以
A⇔B
1.12 (1) 设(1)中公式为A.
A⇔(p∨(q∧r))→(p∧q∧r)
A⇔¬(p∨(q∧r))∨(p∧q∧r)
A⇔¬p∧(¬q∧¬r)∨(p∧q∧r)
A⇔(¬p∧¬q)∨(¬q∧¬r)∨(p∧q∧r)
A⇔(¬p∧¬q∧(¬r∧r))∨(¬p∧q∧r)∧¬r)∨(p∧q∧r)
∨(¬p∧q∧¬r)∨(p∧q∧r)
A⇔m0∨m1∨m7
12
于是,公式A的主析取范式为
m0∨m1∨m2∨m7易知,A的主合取范式为
M3∨M4∨M5∨M6A的成真赋值为
000, 001, 010, 111A的成假赋值为
011,100,101,110(2)设(2)中公式为B
B⇔(¬p→q)→(¬q∧p)
⇔(¬¬p∨q)→(¬q∧p)
⇔(p∨q)→(¬q∧p)
⇔¬(p∨q)∨(¬q∧p)
⇔(¬p∨¬q)∨¬q∧p
⇔¬q∧p (吸收律)
⇔((¬p∨q)∧¬)∨p∧(¬q∧p)
⇔(¬p∨¬q)∨p∧(p∧¬q)∨(p∧q)⇔m0∨m2∨m3
所以,B的主析取范式为m0∨m2∨m3.B的主合取范式为M1
B的成真赋值为00,10,11.
B的成假赋值为01.
(3)设(3)中公式为C.
C⇔¬(p→q)∧q∧r
⇔(p∧¬q)∧q∧r]
13⇔ p∧(¬q∧q)∧r
⇔p∧0∧r
⇔0.
所以,C的主析取范式为0.
C的主合取范式为M0∧M1∧M2∧M3
C的成假赋值为00,01,10,11
C无成真赋值,C为矛盾式.
分析 1°设公式 A 中含n(n≥1)个命题变项,且 A 的主析取范式中含l(0≤l≤2n)个极小项,则A的主合邓范式中含2n−l个极大项,而且极大项的角标分别为0到2n−1这2n个十进制数中未在A的主析取范式的极小项角标中出现过的十进制数.
在(1)中,n=3,A的主析取范式中含4个极小项,所以,A的主合取范式中必含23−4=4个极大项,它们的角标为0到7中未在主析取范式的极小项角标中出现过的3,4,5,6. 这样,只要知道A的主析取范式,它的主合邓范式自然也就知道了,在(2),(3)中情况类似.
2° A的主析取范式中极小项角标的二进制表示即为A的成真赋值.在(1)中,由于主析取范式中的极小项角标分别为 0,1,2,7,它们的二进制表示分别为000,001,010,111,所以,A 的成真赋值为以上各值.类似地,A 的主合取范式中所含极大项角标的二进制表示,即为A的成假赋值.
1.13 (1) 首先求p→(q→r)的主析取范式.
p→(q→r)
⇔¬p∨(¬q∨r)
⇔¬p∨¬q∨r).
由于演算过程较长,可以分别先求出由¬p,¬q,r派生的极小项.注意,本公式中含3个命题变项,所以,极小项长度为3.
14
¬p⇔¬p∧(¬q∨q)∧(¬r∨r)
⇔(¬p∧¬q∧r)∨(¬p∧¬q∧r)
∨(¬p∧q∧¬r)∨(¬p∧¬q∧r)
⇔m0∨m1∨m2∨m3
¬p⇔(¬p∨p)∧¬q∧(¬r∨r)
⇔(¬p∧¬q∧¬r)∨(¬p∧¬q∧r)
∨(¬p∧¬q∧¬r)∨(p∧¬q∧r)
⇔m0∨m1∨m4∨m5
r⇔(¬p∨p)∧(¬q∨q)∧r
⇔(¬p∧¬q∧r)∨(¬p∧¬q∧r)
⇔(p∧¬q∧r)∨(p∧q∧r)
⇔m1∨m31∨m5∨m7
p→(q→r)⇔m0∨m1∨m2∨m3∨m4∨m5∨m7
类似地,可求出q→(p→r)主的析取范式也为上式,由于公式的主析取范式的唯一性,可知,
(p→(q→r))⇔(q→(p→r)).
(2) ①
p↑q
⇔¬(p∧q)
⇔¬p∨¬q
⇔(¬p∧(¬q∨q))∨((¬p∨p)∧¬q)
⇔(¬p∧¬q)∨(¬p∧q))∨((¬p∨¬p)∨(p∧¬q)
⇔(¬p∧¬q)∨(¬p∧q)∨(p∨¬p)
15
⇔m0∨m1∨m2.
②p↓q
⇔¬(p∧q)
⇔¬p∨¬q
⇔m0.
由于p↑q与p↓q的主析取范式不同.因而它们不等值,即p↑q⇔ p↓q.
1.14 设p:A输入;
设q:B输入;
设r:C输入;
由题的条件,容易写出FA,FB,FC的真值表,见表1.5所示.由真值表分别写出它们的主析范邓范式,而后,将它们都化成与之等值的{↓}中的公式即可.
表1.5
p qrFFF
ABC
0 00 0 0 0
0 01 00 1
0 10 0 1 0
0 11 0 1 0
1 00 1 0 0
1 01 1 0 0
1 101 0 0
1 11 1 0 0
FA⇔(p∧¬q∧¬r)∨(p∧¬q∧r))∨(p∧q∧¬r)∨(p∧q∧r)
⇔(p∧¬q)∧(¬r∨r)∨(p∧q)∧(¬r∨r)
⇔(p∧¬q)∨(p∧q)
⇔ p
16
⇔¬¬(p∧q)
⇔¬(p↓q)
⇔¬(p↓q)
⇔(p↓q)↓(p↓p)
FB⇔(¬p∧q∧¬r)∨(¬p∧q∧r)
⇔(¬p∧q)∧(¬r∨r)
⇔(¬p∧q)
⇔¬¬(¬p∧q)
⇔¬(p∧¬q)
⇔ p↓¬q)
⇔ p↓(q↓q).
FC ⇔(¬p∧¬p∧r)
⇔¬(p∨q)∧r
⇔(p↓q)∧r
⇔¬¬((p↓q)∧r
⇔¬(¬(p↓q)∨¬r
⇔¬(p↓q)↓¬r
⇔((p↓q)↓(p↓q))↓(r↓r)\
分析 在将公式化成{↑}或{↓}中公式时,应分以下几步:(1)先将公式化成全功能集{¬,∧,∨}中的公式.
(2) 使用
¬A⇔¬(A∧A)⇔A↑A,
17
或
¬A⇔¬(A∨A)⇔A↓A.使用双重否定律
A∧B⇔¬¬(A∧B)⇔¬(A↑B)
⇔(A↑B)↑(A↑B)或
A∨B⇔¬¬(A∨B)⇔¬(A↓B)
⇔(A↓B)↓(A↓B)使用德·摩根律
A∧B⇔¬¬(A∧B)⇔¬(¬A∨¬B)
⇔¬A↓¬B⇔(A↓A)↓(B↓B)或
A∨B⇔¬¬(A∨B)⇔¬(¬A∧¬B)
⇔¬A↑¬B⇔(A↑A)↑(B↑B)1．15 设p：矿样为铁；
q：矿样为铜；
r：矿样为锡.
设
F1⇔(甲全对)∧(乙对一半)∧(丙全错)，
⇔(¬p∧¬q)∧((¬p∧¬r)∨(p∧r))∧(¬p∧r)⇔(¬p∧¬q∧¬p∧¬r∧¬p∧r)
∨(¬p∧¬q∧p∧r∧¬p∧r)
⇔0∨0⇔0.
F2⇔(甲全对)∧(乙全错)∧(丙对一半)
⇔(¬p∧¬q)∧(p∧¬r)∧((p∧r)∨(¬p∧¬r)
18
⇔(¬p∧¬q∧p∧¬r∧p∧r)
∨(¬p∧¬q∧p∧r∧¬p∧¬r)
⇔0∨0⇔0
F3⇔(甲对一半)∧(乙全对)∧(丙全错)
⇔((¬p∧q)∨(p∧¬q))∧(¬p∧r)∨(¬p∧¬r)
⇔(¬p∧q∧¬p∧r∧¬p∧r
∨(p∧¬q∧¬p∧r∧¬p∧r)
⇔(¬p∧q∧r)∨0
⇔¬p∧q∧r.
F4⇔(甲对一半)∧(乙全错)∧(丙全对)⇔((¬p∧q)∨(p∧¬q))∧(p∧¬r)∧(p∧¬r)
⇔(¬p∧q¬∧¬r∧p∧¬r
∨(p∧¬q∧p∧¬r∧p∧¬r)
⇔0∨(p∧¬q∧¬r)
⇔ p∧¬q∧¬r.
F5⇔(甲会错)∧(乙对一半)∧(丙全对)
⇔(p∧q)∧((¬p∧¬r)∨(p∧r))∧(p∧¬r)
⇔(p∧q∧¬p∧¬r∧p∧¬r
∨(p∧q∧p∧r∧p∧¬r)
⇔0∨0
⇔0.
F6⇔(甲全错)∧(乙全对)∧(丙对一半)
⇔(p∧q)∧((¬p∧r)∧((p∧r)∨(¬p∧¬r)
19⇔(p∧q∧¬p∧r∧p∧r
∨(p∧q∧¬p∧r∧¬p∧¬r)
⇔0∨0
⇔0.
设
F⇔(一人全对)∧(一人对一半)∧(一人全错)
则F为真命题，并且
F⇔F1∨F2∨F3∨F4∨F5∨F6
⇔(¬p∧q∧r)∨(p∧¬q∧¬r)⇔1.
但，矿样不可能既是铜又是锡，于是q,r中必有假命题，所以¬p∧q∧r⇔0,因而必有
p∧¬q∧¬r⇔1.
于是，必有P为真，q与r为假，即矿样为铁。
1.16 令p：今天是1号；
q：明天是5号.
由于本题给出的推理都比较简单，因而可以直接判断推理的形式结构是否为重言式。
（1）推理的形式结构为
(p→q)∧p→q.
可以用多种方法判断上公式为重言式，其实，本推理满足假言推理定律，即
(p→q)∧p⇒q.
所以，推理正确。
（2）推理的形式结构为
(p→q)∧p→q.
可以用多种方法证明上公式不是重言式，其实，当 p 为假（即今天不是 1号），q为真（明天真是5号），也即01是上面公式的成假赋值，所以，推理的
20
形式结构不是重方式，故，推理不正确。
（3）推理的形式结构为
(p→q)∧¬p→¬q.
可以用多种方法证明上面公式为重言式，其实，它满足拒取式推理定律，即
(p→q)∧¬p⇒¬q.
所以，推理正确。
（4）推理的形式结构为
(p→q)∧¬p→¬q.
可以用多种方法证明上公式不是重言式，01 为上公式的成假赋值，所以，推理不正确。
分析 对于前提与结论都比较简单的推理，最好直接判推理的形式结构是否为重言式，来判断推理是否正确，若能观察出一个成假赋值，立刻可知，推理不正确。
1．17 (1)
证明 ①¬q∨r 前提引入
②¬r前提引入
③¬q①②析取三段论
④¬(p∧¬q) 前提引入
⑤¬p∨q ④置换
⑥¬p②⑤析取三段论
（2）
证明 ①p→(q→s) 前提引入
②q→(q→s) ①置换
③q 前提引入
④p→s②③假言推理
⑤p∨¬r 前提引入
21
⑥r→ p⑤置换
⑦r→s ④⑥假言三段论
（3）
证明 ①p 附加前提引入②p→q 前提引入
③q ①②假言推理
④p∧q ①③合取
或者
证明 ①p→q前提引入②¬p∨q ①置换
③(¬p∨p)∧(¬p∨q) ②置换
④¬p∨(p∧q) ③置换
⑤p→(p∧q) ④置换
（4）
证明 ① 前提引入②(s→t)∧(t→s) ①置换
③ ②化简
④t∧r 前提引入
⑤t
⑥s ③⑤假言推理⑦ 前提引入
⑧(q→s)∧(s→q) ⑦置换
⑨s↔q⑧化简
⑩q ⑥⑨似言推理⑪q↔ p前提引入
22⑫p ⑩⑪ 假言推理
⑬r ④化简
⑭p∧q∧s∧r ⑥⑩⑪⑫合取
分析 由于
(A1∧A2∧L∧Ak)→(C→B)
⇔¬(A1∧A2∧L∧Ak)∨(¬C∨B)
⇔¬(A1∧A2∧L∧Ak∧C)∨B
⇔A1∧A2∧L∧Ak∧C→B
所以,当推理的结论也为蕴含式时,可以将结论的前件作为推理的前提,称为附加前提,并称使用附加前提的证明方法为附加前提证明法.(3)中第一个证明,即为附加前提证明法.
1.18 设p：他是理科生
q：他是文科生
r：他学好数学
前提 p→r,¬q→p,¬r
结论q
通过对前提和结论的观察，知道推理是正确的，下面用构造证明法给以证明。
证明 ① p→r 前提引入
¬r前提引入
③¬p ①②拒取式
④¬q→ p 前提引入
⑤¬¬q ③④拒邓式
⑥q⑤置理
1．19 本题可以用多种方法求解，根据要求回答问题，解本题最好的方法是真值表示或主析取范式法。这里采用主析取范式的主析取范式（过程略）
23
p∨(q∧¬r)
⇔m2∨m4∨m5∨m6∨m7
所以，成真赋值为010，100，101，110，111，由④给也，成假赋值为000，001，011，由③给出，公式是非重言式的可满足式，由③给出。
1．20 答案 A：③； B：④； C：②
分析 解本题的方法不限于求主析取范式或主合取范式，也可以利用真值表法。
方法1： 求主析取范式
¬(p∧q)→r
⇔(p∧q)∨r
⇔(p∧q)∧(r∨¬r)∨(p∨¬p)∧(q∨¬q)∧r
⇔m1∨m3∨m5∨m6∨m7
从上式可知，¬(p∧q)→r的主析取范式中含5个极小项。极小项角码的二进制表示为成真赋值，因而成真赋值为001，011，101，110，111。由成真赋值立即可知成假赋值为000，
010，100，成假赋值的十进制的十进表示为极大项的角码，因而极大项为M0,M2,M4，故有3个极大项。
方法2：求主合取范式，分析类似主析取范式法。
方法3：真值表法
由真值表，求出成真赋值，将成真赋值转化成十进制数做为极小项的角码，这样就求出了全部极小项，也容易求出极大项。
1．21 答案 A：③； B：⑤； C：⑥
分析 可用构造证明法解此题。
（1） ①¬q∨r前提引入
②¬r前提引入
③¬q①②析取三段论
24
④¬(p∧¬q) 前提引入
⑤¬p∨q ④置换
⑥¬p ③⑤析取三段论
至此可知¬p是（1）的逻辑结论。
（2） ①¬r∨s 前提引入
②¬s 前提引入
③¬r ①②析取三段论
④(p∧q)→r 前提引入
⑤¬(p∧q) ④置换
⑥¬p∨¬q ⑤置换
至此可知¬p∨¬q是（2）的国逻辑结论。
（3） ①¬p∨q 前提引入
②p→q ①置换前提引入
③¬q∨r前提引入
④q→r ③置换
⑤p→r ②④假言推理
⑥r→s 前提引入
⑦p→s ⑤⑥假言推理
至此可知p→s是（3）的逻辑结论。
1．22答案 A：④
分析 在本题中，设A，B，C分别表示3个开关状态的命题变项，开关的扳键向上时，对应命题变项的真值为1，否则为0，由真值表易知。
F⇔(¬A∧¬B∧C)∨(¬A∧B∧¬C)
∨(A∧¬B∧¬C)∨(A∧B∧C)
25
⇔¬A∧((¬B∧C)∨(B∧¬C))
∨A∧((¬B∧¬C)∨(B∧C))
⇔(¬A∧(B∨C))∨(A∧(¬B∨C)∧(B∨¬C))⇔(¬A∧(B∨C))∨(A∧¬((B∧¬C)∨(¬B∧C))⇔(¬A∧(B∨C))∨(A∧¬(B∨C))
⇔A∨B∨C
26