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

第1章 习题解答

3.求下列命题公式的主析取范式，并求命题公式的成真赋值。 ⑴(p∧q)∨(p∧r)

作(p∧q)∨(p∧r)的真值表，如表1.50所示。

表1.50

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

由真值表可知，原式?(p∧?q∧r)∨(p∧q∧?r)∨(p∧q∧r)(主析取范式)?∑5,6,7 使得命题公式(p∧q)∨(p∧r)成真的赋值是：101，110，111。 ⑵?(p∨q)→(?p∧r) ???(p∨q)∨(?p∧r) ?(p∨q)∨(?p∧r)

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

?(?p∧?q∧r)∨(?p∧q∧?r)∨(?p∧q∧r)∨(p∧?q∧?r)∨ (p∧?q∧r)∨(p∧q∧?r)∨(p∧q∧r)(主析取范式) ?∑1,2,3,4,5,6,7

使得命题公式?(p∨q)→(?p∧r)成真的赋值是：001，010、011，100，101，110，111。 ⑶(?p∨?q)→(p??q)

作(?p∨?q)→(p??q)的真值表，如表1.51所示。

表1.51

p 0 0 1 1 q ?p ?q 0 1 0 1 1 1 0 0 1 0 1 0 ?p∨q 1 1 1 0 p?q 0 1 1 0 (p∨q)→(p?q) 0 1 1 1

由真值表可知:

原式?(?p∧q)∨(p∧?q)∨(p∧q) (主析取范式)?∑1,2,3

使得命题公式(?p∨?q)→(p??q)成真的赋值是：01，10，11。

21

第1章 习题解答

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

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

?(?p∧?q)∨(p∧?q)∨(p∧q)(主析取范式) ?∑0,2,3

使得命题公式(?p→q)→(p∨?q)成真的赋值是：00,10,11。 ⑸(p→(q∧r))∧(?p→(?q∧?r)) ?(?p∨(q∧r))∧(??p∨(?q∧?r))

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

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

?(?p∨q∨r)∧(?p∨q∨?r)∧(?p∨?q∨r)∧(p∨?q∨r)∧(p∨q∨?r)∧(p∨?q∨?r) ?(?p∧?q∧?r)∨(p∧q∧r)(主析取范式)

使得命题公式(p→(q∧r))∧(?p→(?q∧?r))成真的赋值是：000,111。 4. 求下列命题公式的主合取范式，并求命题公式的成假赋值。 ⑴(p→q)∧r ?(?p∨q)∧r

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

?(?p∨q∨r)∧(?p∨q∨?r)∧(?p∨q∨r)∧(?p∨?q∨r)∧(p∨q∨r)∧(p∨?q∨r) ?(?p∨q∨r)∧(?p∨q∨?r)∧(?p∨?q∨r)∧(p∨q∨r)∧(p∨?q∨r) ?∏0,2,4,5,6

使得命题公式(p→q)∧r成假的赋值是：000,010,100,101,110。 ⑵?(p→q)?(p→?q)

作?(p→q)?(p→?q)的真值表，如表1.52所示。

表1.52

p 0 0 1 1 q p→q ?(p→q) ?q 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 p→?q 1 1 1 0 ?(p→q)?(p→?q) 0 0 1 1

由真值表可知:

原式?(p∨q)∧(p∨?q)?∏0,1

使得命题公式?(p→q)?(p→?q)成假的赋值是：00,01。 ⑶?(p∨q)→(?p∧r)

22

第1章 习题解答

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

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

使得命题公式?(p∨q)→(?p∧r)成假的赋值是：000。 ⑷?(p→?q)∧?p ??(?p∨?q)∧?p ?p∧q∧?p

?F ?∏0,1,2,3

使得命题公式?(p→?q)∧?p成假的赋值是：00,01,10,11。 ⑸(p→(q∨r))∨r ??p∨q∨r∨r ??p∨q∨r ?∏4

使得命题公式(p→(q∨r))∨r成假的赋值是：100。

5. 求下列命题公式的主析取范式，再用主析取范式求出主合取范式。 ⑴(p→q)∧(q→r) ?(?p∨q)∧(?q∨r)

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

?(?p∧?q∧r)∨(?p∧?q∧?r)∨(?p∧?q∧r)∨(?p∧q∧r)∨(?p∧q∧r)∨(p∧q∧r) ?(?p∧?q∧r)∨(?p∧?q∧?r)∨(?p∧q∧r)∨(p∧q∧r)(主析取范式) ?∑0,1,3,7 ?∏2,4,5,6

?(p∨?q∨r)∧(?p∨q∨r)∧(?p∨q∨?r)∧(?p∨?q∨r)(主合取范式) ⑵?(?p∨?q)∨r ?(p∧q)∨r

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

?(p∧q∧r)∨(p∧q∧?r)∨(p∧q∧r)∨(p∧?q∧r)∨(?p∧q∧r)∨(?p∧?q∧r) ?(p∧q∧r)∨(p∧q∧?r)∨(p∧?q∧r)∨(?p∧q∧r)∨(?p∧?q∧r)(主析取范式) ?∑1,3,5,6,7 ?∏0,2,4

?(p∨q∨r)∧(p∨?q∨r)∧(?p∨q∨r)(主合取范式)

6. 求下列命题公式的主合取范式，再用主合取范式求出主析取范式。 ⑴(p?q)∧r

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

23

第1章 习题解答

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

?(?p∨q∨r)∧(?p∨q∨?r)∧(p∨?q∨r)∧(p∨?q∨?r)∧ (?p∨?q∨r)∧(p∨q∨r)(主合取范式)

?∏0,2,3,4,5,6?∑1,7?(?p∧?q∧r)∨(p∧q∧r)(主析取范式) ⑵(p∧q)→q ??(p∧q)∨q ??p∨?q∨q

?T(无主合取范式)

?∑0,1,2,3?(?p∧?q)∨(?p∧q)∨(p∧?q)∨(p∧q) 7.用主析取范式判断下列命题公式是否等价。 ⑴p→(q→r)和q→(p→r)

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

?(?p∧?q∧?r)∨(?p∧?q∧r)∨(?p∧q∧?r)∨(?p∧q∧r)∨ (p∧?q∧?r)∨(p∧?q∧r)∨(p∧q∧r)(主析取范式) ?∑0,1,2,3,4,5,7

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

?(?p∧?q∧?r)∨(?p∧?q∧r)∨(?p∧q∧?r)∨(?p∧q∧r)∨ (p∧?q∧?r)∨(p∧?q∧r)∨(p∧q∧r)(主析取范式) ?∑0,1,2,3,4,5,7

因为p→(q→r)与q→(p→r)的主析取范式相同，所以p→(q→r)?q→(p→r)。 ⑵(p→q)∧(p→r)和p→(q∧p)

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

?(?p∧q∧r)∨(?p∧q∧?r)∨(?p∧?q∧r)∨(?p∧?q∧?r)∨(?p∧q∧r)∨(p∧q∧r) ?(?p∧q∧?r)∨(?p∧?q∧r)∨(?p∧?q∧?r)∨(?p∧q∧r)∨(p∧q∧r)(主析取范式) ?∑0,1,2,3,7

p→(q∧p)??p∨(q∧p)?(?p∨q)∧(?p∨p)??p∨q ?(?p∧q)∨(?p∧?q)∨(?p∧q)∨(p∧q) ?(?p∧q)∨(?p∧?q)∨(p∧q) (主析取范式) ?∑0,1,3

因为(p→q)∧(p→r)与p→(q∧p)的主析取范式不相同，所以(p→q)∧(p→r)与p→(q∧p)不等价。

8. 用主合取范式判断下列命题公式是否等价。 ⑴(p→q)→r和p→(q→r)

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

?(p∨?q∨r)∧(p∨q∨r)∧(?p∨?q∨r) ?∏0,2,6

24

第1章 习题解答

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

?∏6

因为(p→q)→r与p→(q→r)的主合取范式不相同，所以(p→q)→r与p→(q→r)不等价。 ⑵(p∧?q)∨(?p∧q)和(p∨q)∧?(p∧q)

(p∧?q)∨(?p∧q)?∑1,2?∏0,3?(p∨q)∧(?p∨?q) (p∨q)∧?(p∧q)?(p∨q)∧(?p∨?q)?∏0,3

因为(p∧?q)∨(?p∧q)和(p∨q)∧?(p∧q)的主合取范式相同，所以(p∧?q)∨(?p∧q)? (p∨q)∧?(p∧q)。

25