离散数学课后习题答案

? ?p ∨ (?q ∨ r ) ??p ∨?q ∨r) .

由于演算过程较长,可以分别先求出由?p,?q,r派生的极小项.注意,本公式 中含3 个命题变项,所以,极小项长度为3. ?p ? ?p ∧ (?q ∨q) ∧ (?r ∨r ) ? (?p ∧?q ∧r ) ∨ (?p ∧ ?q ∧r ) ∨ (?p ∧q ∧?r ) ∨ (?p ∧ ?q ∧r ) 0 1 2 3 ? m ∨ m ∨m ∨m ?p ?(?p ∨ p)∧?q ∧ (?r ∨r) ? (?p ∧?q ∧ ?r ) ∨ (?p ∧?q ∧r ) ∨ (?p ∧ ?q ∧?r ) ∨ ( p ∧ ?q ∧r ) 0 1 4 5 ? m ∨ m ∨m ∨m r ? (?p ∨ p) ∧ (?q ∨q ) ∧r ?(?p ∧?q ∧r)∨ (?p ∧?q ∧r) ? ( p ∧ ?q ∧r ) ∨ ( p ∧q ∧r ) 1 31 5 7 ? m ∨m ∨m ∨m

0 1 2 3 4 5 7 p →(q →r ) ?m ∨m ∨m ∨m ∨ m ∨ m ∨m

类似地,可求出q →(p →r )主的析取范式也为上式,由于公式的主析取范式 的唯一性,可知,

( p → (q →r )) ? (q →( p →r )). (2) ① p ↑ q ? ?(p ∧q) ? ?p ∨ ?q

课后答案网 www.khdaw.com 16 ? (?p ∧(?q ∨q )) ∨ ((?p ∨ p) ∧?q) ? (?p ∧?q) ∨ (?p ∧q )) ∨ ((?p ∨ ?p ) ∨ ( p ∧ ?q ) ? (?p ∧?q) ∨ (?p ∧q ) ∨ (p ∨?p) . 0 1 2 ? m ∨m ∨ m ②p ↓ q ? ?( p ∧q ) ? ?p ∨ ?q . 0 ? m

由于p ↑ q与p ↓q 的主析取范式不同.因而它们不等值,即p ↑ q ? p ↓ q . 1.14 设p:A 输入; 设q:B 输入; 设r:C 输入;

由题的条件,容易写出的真值表,见表1.5 所示.由真值表分别写出A B C F ,F ,F 它们的主析范邓范式,而后,将它们都化成与之等值的{↓}中的公式即可. 表1.5

F ( p q r ) ( p q r )) (p q r ) ( p q r ) A ? ∧ ? ∧? ∨ ∧? ∧ ∨ ∧ ∧? ∨ ∧ ∧ p q r FA FB C F

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

? ( p ∧ ?q ) ∧ (?r ∨ r ) ∨ (p ∧q) ∧ (?r ∨r ) ? ( p ∧ ?q ) ∨ (p ∧q) ? p ? ??( 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) . F ( p p r ) C ? ? ∧ ? ∧ ? ?(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, 或 ?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 .

( ) ( ) ( ) 2 F ? 甲全对∧ 乙全错∧ 丙对一半 ?(?p ∧?q)∧ (p ∧?r )∧ ((p ∧r )∨ (?p ∧?r) ? (?p ∧ ?q ∧ p ∧ ?r ∧ p ∧r ) ∨ (?p ∧?q ∧ p ∧r ∧ ?p ∧ ?r )

( ) ( ) ( ) 3 F ? 甲对一半∧ 乙全对∧ 丙全错 ? ((?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.

( ) ( ) ( ) 4 F ? 甲对一半∧ 乙全错∧ 丙全对 ? ((?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.

( ) ( ) ( ) 5 F ? 甲会错∧ 乙对一半∧ 丙全对 ?(p ∧q)∧ ((?p ∧?r )∨ (p ∧r))∧ (p ∧?r) ? ( p ∧q ∧ ?p ∧?r ∧ p ∧ ?r ∨ ( p ∧q ∧ p ∧r ∧ p ∧ ?r ) ? 0 ∨ 0 ? 0.

? 0 ∨ 0? 0

( ) ( ) ( ) 6 F ? 甲全错∧ 乙全对∧ 丙对一半 ? ( p ∧q ) ∧((?p ∧r ) ∧ (( p ∧r ) ∨ (?p ∧?r ) ? ( p ∧q ∧ ?p ∧r ∧ p ∧r ∨ (p ∧q ∧?p ∧r ∧?p ∧?r) ? 0 ∨ 0 ? 0. 设

F ? (一人全对) ∧ (一人对一半) ∧(一人全错) 则F 为真命题，并且

1 2 3 4 5 6 F ? F ∨F ∨F ∨F ∨F ∨F ? (?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.

课后答案网 www.khdaw.com 21

可以用多种方法证明上公式不是重言式，其实，当p 为假（即今天不是1