第1章 离散数学习题解答(4)

第1章 习题解答

表1.46

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 1 1 1 1 0 0 1 1 q→r 1 1 0 1 1 1 0 1 (p→q)∧(q→r) 1 1 0 1 0 0 0 1 p→r 1 1 1 1 0 1 0 1 ((p→q)∧(q→r))→(p→r) 1 1 1 1 1 1 1 1

⑸((p∨q)∧(p→r)∧(q→r))→r

((p∨q)∧(p→r)∧(q→r))→r的真值表如表1.47所示。由表1.47可以看出((p∨q)∧(p→r)∧(q→r))→r是重言式。

表1.47

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?0 0 1 1 1 1 1 1 p→r?1 1 1 1 0 1 0 1 q→r?(p∨q)∧(p→r)∧(q→r)?((p∨q)∧(p→r)∧(q→r))→r?1 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1

16

第1章 习题解答

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

((p→q)∧(r→s))→((p∧r)→(q∧s))的真值表如表1.48所示。由表1.48可以看出((p→q)∧(r→s))→((p∧r)→(q∧s))是重言式。

表1.48

p 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 q 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 r 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 s?0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 p→q?r→s?(p→q)∧(r→s)?p∧r?q∧s?(p∧r)→(q∧s)?1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 原公式?1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ⑺((p?q)∧(q?r))→(p?r)

((p?q)∧(q?r))→(p?r)的真值表如表1.49所示。由表1.49可以看出((p?q)∧(q?r))→(p?r)是重言式。

表1.49

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 1 1 0 0 0 0 1 1 q?r 1 0 0 1 1 0 0 1 (p?q)∧(q?r) 1 0 0 0 0 0 0 1 p?r 1 0 1 0 0 1 0 1 ((p?q)∧(q?r))→(p?r) 1 1 1 1 1 1 1 1

17

第1章 习题解答

3. 用等价演算证明题2中的命题公式是重言式。 ⑴(p∧(p→q))→q ??(p∧(?p∨q))∨q ?(?p∨(p∧?q))∨q

?((?p∨p)∧(?p∨?q))∨q ?(?p∨?q)∨q ?T

⑵(?q∧(p→q))→?p ?(?q∧(?p∨q))→?p ??(?q∧(?p∨q))∨?p ?(q∨(p∧?q))∨?p ?(?p∨q)∨(p∧?q) ??(p∧?q)∨(p∧?q) ?T

⑶(?p∧(p∨q))→q ?(?p∧q)→q ??(?p∧q)∨q ?p∨?q∨q

?T ⑷((p→q)∧(q→r))→(p→r)

??((?p∨q)∧(?q∨r))∨(?p∨r) ?(p∧?q)∨(q∧?r)∨(?p∨r)

?(p∧?q)∨((?p∨q∨r)∧(?p∨?r∨r)) ?(p∧?q)∨(?p∨q∨r)

?(?p∨q∨r∨p)∧(?p∨q∨r∨?q) ?T

⑸((p∨q)∧(p→r)∧(q→r))→r ?((p∨q)∧(?p∨r)∧(?q∨r))→r ?((p∨q)∧(?(p∨q)∨r))→r ?((p∨q)∧r)→r ??((p∨q)∧r)∨r ??(p∨q)∨?r∨r ?T

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

??((?p∨q)∧(?r∨s))∨(?(p∧r)∨(q∧s)) ?((p∧?q)∨(r∧?s))∨((?p∨?r)∨(q∧s))

?((p∧?q)∨(r∧?s))∨((?p∨?r∨q)∧(?p∨?r∨s))

?((p∧?q)∨(r∧?s)∨(?p∨?r∨q))∧((p∧?q)∨(r∧?s)∨(?p∨?r∨s)) ?((r∧?s)∨((?p∨?r∨q∨p)∧(?p∨?r∨q∨?q)))∧((r∧?s)∨

18

第1章 习题解答

((?p∨?r∨s∨p)∧(?p∨?r∨s∨?q)))

?((r∧?s)∨T)∧((r∧?s)∨(?p∨?q∨?r∨s)) ?(r∧?s)∨(?p∨?q∨?r∨s)

?(?p∨?q∨?r∨s∨r)∧(?p∨?q∨?r∨s∨?s) ?T

⑺((p?q)∧(q?r))→(p?r)

?((?p∨q)∧(?q∨p)∧(?q∨r)∧(?r∨q))→(p?r)

??((?p∨q)∧(?q∨p)∧(?q∨r)∧(?r∨q))∨(p∧r)∨(?p∧?r) ?(p∧?q)∨(p∧r)∨(r∧?q)∨(q∧?r)∨(q∧?p)∨(?p∧?r) ?((p∧(?q∨r))∨?(?q∨r))∨(r∧?q)∨(q∧?p)∨(?p∧?r)

?((?(?q∨r)∨(?q∨r))∧(p∨?(?q∨r)))∨(r∧?q)∨(q∧?p)∨(?p∧?r) ?(T∧(p∨?(?q∨r)))∨(r∧?q)∨(q∧?p)∨(?p∧?r) ?p∨(q∧?r)∨(r∧?q)∨(q∧?p)∨(?p∧?r) ?p∨(q∧?r)∨((q∧?p)∨(?p∧?r))∨(r∧?q) ?p∨(q∧?r)∨((?p∧(q∨?r))∨?(q∨?r)) ?p∨(q∧?r)∨?p∨(?q∧r) ?T

4.证明下列等价式： ⑴((p→r)∧(q→r)) ?(?p∨r)∧(?q∨r) ?(?p∧?q)∨r ??(p∨q)∨r ?(p∨q)→r

⑵(p→q)∧(p→?q) ?(?p∨q)∧(?p∨?q) ??p∨(q∧?q) ??p∨F ??p

⑶p∧(p→q) ?p∧(?p∨q)

?(p∧?p)∨(p∧q) ?F∨(p∧q) ?p∧q

19

第1章 习题解答

习题 1.5

1.求下列命题公式的析取范式。 ⑴(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∧(?p∨q) ?(p∧?p)∨(p∧q) ? p∧q

⑷(p→q)∧(q∨r) ?(?p∨q)∧(q∨r) ? q∨(?p∧r)

⑸?(p∨?q)∧(r→t) ?(?p∧q)∧(?r∨t)

?(?p∧q∧?r)∨(?p∧q∧t)

2. 求下列命题公式的合取范式。 ⑴?(p→q) ??(?p∨q) ?p∧?q

⑵?q∨(p∧q∧r)

?(?q∨p)∧(?q∨q)∧(?q∨r) ?(?q∨p)∧(?q∨r) ⑶(?p∧q)∨(p∧?q)

?((?p∧q)∨p)∧((?p∧q)∨?q))

?(?p∨p)∧(q∨p)∧(?p∨?q)∧(q∨?q) ?(p∨q)∧(?p∨?q) ⑷?(p?q)

??((p∧q)∨(?p∧?q)) ?(?p∨?q)∧(p∨q) ⑸?(p→q)→r ???(?p∨q)∨r ?(?p∨q)∨r ??p∨q∨r

20