发布时间 : 星期五 文章《离散数学》（左孝凌 李为鉴 刘永才编著）课后习题答案 上海科学技术文献出版社更新完毕开始阅读
?┓P∧Q ?┐(P∨┐Q) c)
┐P∧┐Q∧(┐R→P) ?┐P∧┐Q∧(R∨P)
?(┐P∧┐Q∧R)∨(┐P∧┐Q∧P) ?(┐P∧┐Q∧R)∨F ?┐P∧┐Q∧R ?┐(P∨Q∨┐R)
解：
a)┐P? P↓P
b)P∨Q?┐(P↓Q) ? (P↓Q)↓(P↓Q) c)P∧Q?┐P↓┐Q? (P↓P)↓(Q↓Q) 解：
P→(┐P→Q) ?┐P∨(P∨Q) ?T ?┐P∨P
? (┐P↑┐P)↑(P↑P) ?P↑(P↑P)
P→(┐P→Q) ?┐P∨(P∨Q) ?T ?┐P∨P ?┐(┐P↓P) ?┐((P↓P)↓P)
?((P↓P)↓P)↓((P↓P)↓P)
解：
P↑Q
?┐(┐P↓┐Q)
页眉 13 / 28
(2) (3)(4)页眉 ?┐((P↓P)↓(Q↓Q))
? ((P↓P)↓(Q↓Q))↓((P↓P)↓(Q↓Q))
(5)证明：
┐(B↑C)
?┐(┐B∨┐C) ? ┐B↓┐C ┐(B↓C) ?┐(┐B∧┐C) ?┐B↑┐C
(6)解：联结词“↑”和“↓”不满足结合律。举例如下：
a)给出一组指派：P为T，Q为F，R为F，则(P↑Q)↑R为T，P↑(Q↑R)为F
? ↑(Q↑R). 故 (P↑Q)↑R Pb)给出一组指派：P为T，Q为F，R为F，则(P↓Q) ↓R为T，P↓(Q↓R)为F
? ↓(Q↓R). 故(P↓Q)↓R P(7)证明：
设变元P，Q，用连结词?,┐作用于P，Q得到：P，Q，┐P，┐Q，P?Q，P?P，Q?Q，Q?P。 但P?Q?Q?P，P?P?Q?Q，故实际有：
P，Q，┐P，┐Q，P?Q，P?P（T） （A） 用┐作用于（A）类，得到扩大的公式类（包括原公式类）：
P，Q，┐P，┐Q，┐（P?Q）， T，F， P?Q （B） 用?作用于（A）类，得到：
P?Q，P?┐P?F，P?┐Q?┐（P?Q），P?（P?Q）?Q，P?（P?P）?P， Q?┐P?┐（P?Q），Q?┐Q?F，Q?（P?Q）?P，Q?T?Q, ┐P?┐Q?P?Q，┐P?（P?Q）?┐Q，┐P?T?┐P, ┐Q?（P?Q）?┐P，┐Q?T?┐Q, （P?Q）?（P?Q）?P?Q.
因此，（A）类使用运算后，仍在（B）类中。 对（B）类使用┐运算得：
┐P，┐Q，P，Q， P?Q， F，T， ┐（P?Q），
14 / 28
页眉 仍在（B）类中。
对（B）类使用?运算得：
P?Q，P?┐P?F，P?┐Q?┐（P?Q），P?┐（P?Q）?┐Q，P?T?P，P?F?┐P，P?（P?Q）?Q， Q?┐P?┐（P?Q），Q?┐Q?F，Q?┐（P?Q）?┐P，Q?T?Q, Q?F?┐Q， Q?（P?Q）?P， ┐P?┐Q?P?Q，┐P?┐（P?Q）?Q，┐P?T?┐P, ┐P?F?P,┐P?（P?Q）?┐Q， ┐Q?┐（P?Q）?P，┐Q?T?┐Q, ┐Q?T?┐Q,┐Q?（P?Q）?┐P， ┐（P?Q）?T?┐（P?Q），┐（P?Q）?F?P?Q，┐（P?Q）?（P?Q）?F T?F?F，T?（P?Q）? P?Q F?（P?Q）? ┐（P?Q） （P?Q）?（P?Q）?P?Q.
故由（B）类使用?运算后，结果仍在（B）中。
由上证明：用?,┐两个连结词，反复作用在两个变元的公式中，结果只能产生（B）类中的公式，总共仅八个不同的公式，故{?,┐}不是功能完备的，更不能是最小联结词组。
已证{?,┐}不是最小联结词组，又因为P Q? ┐（P?Q），故任何命题公式中的联结词，如仅用{ , ┐}表达，则必可用{?,┐}表达，其逆亦真。故{ , ┐}也必不是最小联结词组。 (8)证明{∨ }，{∧}和{→}不是最小联结词组。∨ ∨证明：若{∨}，{∧}和{→}是最小联结词，则 ┐P?（P∨P∨……） ┐P?（P∧P∧……） ┐P?P→(P→(P→……)
对所有命题变元指派T，则等价式左边为F，右边为T，与等价表达式矛盾。 所以{∨}，{∧}和{→}不是最小联结词。
∨ c (9)证明{┐,→}和{┐, }→ 是最小联结词组。
证明：因为{┐,∨}为最小联结词组，且P∨Q?┐P→Q
所以{┐,→}是功能完备的联结词组，又{┐},{→}都不是功能完备的联结词组。 所以{┐,→}是最小联结词组。
c c c 不是功能完备的联结词组， 又因为P→Q?┐(P Q)→ ，所以{┐, }→ 是功能完备的联结词组，又{┐},{ }
→
所以{┐, }是最小联结词组。
c
→
习题 1-7
(1) 解：
P∧(P→Q)
15 / 28
页眉 ?P∧(┐P∨Q) ? (P∧┐P)∨(P∧Q) P∧(P→Q)
? (P∨(┐Q∧Q))∧(┐P∨Q) ? (P∨┐Q)∧(P∨Q)∧(┐P∨Q)
(2) 解：
a) (┐P∧Q)→R
?┐(┐P∧Q)∨R ? P∨┐Q∨R
?(P∧Q)∨(P∧┐Q) ∨(┐Q∧R)∨(┐Q∧┐R)∨(R∧P)∨(R∧┐P)
b) P→((Q∧R)→S)
?┐P∨(┐(Q∧R)∨S) ?┐P∨┐Q∨┐R∨S
?(┐P∧Q)∨(┐P∧┐Q) ∨(┐Q∧R)∨(┐Q∧┐R)∨(┐R∧S)∨(┐R∧┐S)∨(S∧P)∨(S∧┐P)
c) ┐(P∨┐Q)∧(S→T)
?(┐P∧Q)∧(┐S∨T) ?(┐P∧Q∧┐S)∨(┐P∧Q∧T) d) (P→Q)→R
?┐(┐P∨Q)∨R ?(P∧┐Q)∨R ?(P∨R)∧(┐Q∨R) e) ┐(P∧Q)∧(P∨Q)
?(┐P∨┐Q)∧(P∨Q)
?(┐P∧P)∨(┐P∧Q)∨(┐Q∧P)∨(┐Q∧Q) ? (┐P∧Q)∨(┐Q∧P) (3) 解：
a) P∨(┐P∧Q∧R)
?(P∨┐P)∧(P∨Q)∧(P∨R) ?(P∨Q)∧(P∨R) b) ┐(P→Q)∨(P∨Q)
16 / 28