习题一1.判断下列语句是否是命题，为什么？若是命题，判断是简单命题还是复合命题？(1)离散数学是计算机专业的一门必修课。

(2)李梅能歌善舞。

(3)这朵花真美丽！(4)３＋２＞６。

(5)只要我有时间，我就来看你。

(6)x＝５。

(7)尽管他有病，但他仍坚持工作。

(8)太阳系外有宇宙人。

(9)小王和小张是同桌。

(10)不存在最大的素数。

解在上述10个句子中，(3)是感叹句，因此它不是命题。

(6)虽然是陈述句，但它没有确定的值，因此它也不是命题。

其余语句都是可判断真假的陈述句，所以都是命题。

其中：(1)、(4) 、(8) 、(9) 、是简单命题，、(2) 、(5) 、(7)、(10) 是复合命题。

2.判断下列各式是否是命题公式，为什么？(1)(P→(P∨Q))。

(2)(⌝P→Q)→(Q→P)))。

(3)((⌝P→Q)→(Q→P))。

(4)(Q→R∧S)。

(5)(P∨QR)→S。

(6)((R→(Q→R)→(P→Q))。

解 (1)是命题公式。

(2)不是命题公式，因为括号不配对。

(3)是命题公式。

(4)是命题公式。

(5)不是命题公式，因为QR没有意义。

(6)不是命题公式，因为R→(Q→R)→(P→Q) 没有意义。

3.将下列命题符号化：(1)我们不能既划船又跑步。

(2)我去新华书店，仅当我有时间。

(3)如果天下雨，我就不去新华书店。

(4)除非天不下雨，我将去新华书店。

(5)张明或王平都可以做这件事。

(6)“2或4是素数，这是不对的”是不对的。

(7)只有休息好，才能工作好。

(8)只要努力学习，成绩就会好的。

(9)大雁北回，春天来了。

(10)小张是山东人或河北人。

解 (1)符号化为⌝(P ∧Q )，其中，P ：我们划船，Q ：我们跑步。

(2)符号化为Q →R ，其中，R ：我有时间，Q ：我去新华书店。

(3)符号化为P →⌝Q ，其中，P ：天下雨，Q ：我去新华书店。

(4)符号化为⌝P →Q ，其中，P ：天下雨，Q ：我去新华书店。

(5)符号化为P ∧Q ，其中，P ：张明可以做这件事，Q ：王平可以做这件事。

(6)符号化为⌝(⌝(P ∨Q ))，“2或4是素数，这是不对的”是不对的，其中，P ：2是素数，Q ：4是素数，。

(7)符号化为Q →P ，其中，P ：休息好，Q ：工作好。

(8)符号化为P →Q ，其中，P ：努力学习，Q ：成绩就会好的。

(9)符号化为P ↔Q ，其中，P ：大雁北回，Q ：春天来了。

(10)符号化为P ⊕Q ，其中，P ：小张是山东人，Q ：小张是河北人。

4.构造下列命题公式的真值表，并据此说明哪些是其成真赋值，哪些是其成假赋值？ (1)⌝(P ∨⌝Q )。

(2)P ∧(Q ∨R )。

(3)⌝(P ∨Q )↔(⌝P ∧⌝Q )。

(4)⌝P →(Q →P )。

解 (1)由真值表可知，公式⌝(P ∨⌝Q )的成真赋值为：01，成假赋值为00、10、11。

(2)由真值表可知，公式P ∧(Q ∨R )的成真赋值为：101、110、111，成假赋值为000、001、010、011、100。

(3)由真值表可知，公式⌝(P ∨Q )↔(⌝P ∧⌝Q )的成真赋值为：00、01、10、11，没有成假赋值。

(4)由真值表可知，公式⌝P →(Q →P )的成真赋值为：00、10、11，成假赋值为：01。

5.分别用真值表法和公式法判断下列命题公式的类型： (1)(P ∨Q )→(P ∧Q )。

(2)(P ∧Q )→(P ∨Q )。

(3)(⌝P ∨Q )∧⌝(Q ∨⌝R )∧⌝(R ∨⌝P ∨⌝Q )。

(4)(P ∧Q →R )→(P ∧⌝R ∧Q )。

(5)(Q →P )∧(⌝P ∧Q )。

(6)(⌝P ↔Q )↔⌝(P ↔Q )。

(7)(P ∧Q )∧⌝(P ∨Q)。

解 (1)真值表法：由真值表可知，公式(P ∨Q )→(P ∧Q )为可满足式。

公式法：因为(P ∨Q )→(P ∧Q )⇔⌝(P ∨Q )∨(P ∧Q )⇔(⌝P ∧⌝Q )∨(P ∧Q )，所以，公式(P ∨Q )→(P ∧Q )为可满足式。

(2)真值表法：由真值表可知，公式(P ∧Q )→(P ∨Q )为重言式。

公式法：因为(P ∧Q )→(P ∨Q )⇔⌝(P ∧Q )∨(P ∨Q )⇔⌝P ∨⌝Q ∨P ∨Q ⇔T ，所以，公式(P ∧Q )→(P ∨Q )为重言式。

(3)真值表法：由真值表可知，公式(⌝P ∨Q )∧⌝(Q ∨⌝R )∧⌝(R ∨⌝P ∨⌝Q )为矛盾式。

公式法：因为(⌝P ∨Q )∧⌝(Q ∨⌝R )∧⌝(R ∨⌝P ∨⌝Q )⇔(⌝P ∨Q )∧⌝Q ∧R ∧(⌝R ∧P ∧Q )⇔F ，所以，公式(⌝P ∨Q )∧⌝(Q ∨⌝R )∧⌝(R ∨⌝P ∨⌝Q )为矛盾式。

(4)真值表法：由真值表可知，公式(P ∧Q →R )→(P ∧⌝R ∧Q )为可满足式。

公式法：因为(P ∧Q →R )→(P ∧⌝R ∧Q )⇔⌝(⌝( P ∧Q )∨R )∨(P ∧⌝R ∧Q )⇔( P ∧Q ∧⌝R )∨(P ∧⌝R ∧Q )⇔( P ∧Q ∧⌝R )所以，公式(P ∧Q →R )→(P ∧⌝R ∧Q )为可满足式。

(5)真值表法：由真值表可知，公式(Q →P )∧(⌝P ∧Q )为可矛盾式。

公式法：因为(Q →P )∧(⌝P ∧Q )⇔(⌝Q ∨P )∧(⌝P ∧Q )⇔⌝(Q ∧⌝P )∧(⌝P ∧Q )⇔F ，所以，公式为可矛盾式。

(6)真值表法：由真值表可知，公式(⌝P ↔Q )↔⌝(P ↔Q )为永真式。

公式法：因为(⌝P ↔Q )↔⌝(P ↔Q )⇔((⌝P →Q )∧(Q →⌝P ))↔⌝((P ∧Q )∨(⌝P ∧⌝Q ))⇔((P ∨Q )∧(⌝P ∨⌝Q ))↔((⌝P ∨⌝Q )∧(P ∨Q ))⇔T所以，公式(⌝P ↔Q )↔⌝(P ↔Q )为永真式。

(7)真值表法：由真值表可知，公式(P ∧Q )∧⌝(P ∨Q )为矛盾式。

公式法：因为(P ∧Q )∧⌝(P ∨Q )⇔(P ∧Q )∧(⌝P ∧⌝Q )⇔F ，所以，公式(P ∧Q )∧⌝(P ∨Q )为矛盾式。

6.分别用真值表法和公式法证明下列各等价式： (1)(P ∨Q )∧⌝P ⇔⌝P ∧Q 。

(2)⌝(P ∨Q )∨(⌝P ∧Q )⇔⌝P 。

(3)(P ∧Q )∨⌝P ⇔⌝P ∨Q 。

(4)P →(Q ∧R )⇔(P →Q )∧(P →R )。

(5)(P →Q )∧(R →Q )⇔(P ∨R )→Q )。

(6)(P ∧Q ∧A →C )∧(A →P ∨Q ∨C )⇔(A ∧(P ↔Q ))→C 。

(7)⌝(P ↑Q )⇔⌝P ↓⌝Q 。

(8)⌝(P ↓Q )⇔⌝P ↑⌝Q。

证明 (1)真值表法：由真值表可知，(P ∨Q )∧⌝P ⇔⌝P ∧Q 。

公式法：(P∨Q )∧⌝P ⇔(P ∧⌝P )∨(Q ∧⌝P )⇔⌝P ∧Q 。

(2)真值表法：由真值表可知，⌝(P ∨Q )∨(⌝P ∧Q )⇔⌝P 。

公式法：⌝(P ∨Q )∨(⌝P ∧Q )⇔(⌝P ∧⌝Q )∨(⌝P ∧Q )⇔⌝P ∧(⌝Q ∨Q )⇔⌝P 。

(3)真值表法：由真值表可知，(P ∧Q )∨⌝P ⇔⌝P ∨Q 。

公式法：(P ∧Q )∨⌝P ⇔(P ∨⌝P )∧(Q ∨⌝P )⇔⌝P ∨Q 。

(4)真值表法：由真值表可知，P →(Q ∧R )⇔(P →Q )∧(P →R )。

公式法：P →(Q ∧R )⇔⌝P ∨(Q ∧R )⇔(⌝P ∨Q )∧(⌝P ∨R )⇔(P →Q )∧(P →R )。

(5)真值表法：由真值表可知，(P →Q )∧(R →Q )⇔(P ∨R )→Q )。

公式法：(P →Q )∧(R →Q )⇔(⌝P ∨Q )∧(⌝R ∨Q )⇔(⌝P ∧⌝R )∨Q⇔⌝(P ∨R )∨Q ⇔(P ∨R )→Q )。

(6)真值表法：由真值表可知，(P ∧Q ∧A →C )∧(A →P ∨Q ∨C )⇔(A ∧(P ↔Q ))→C 。

公式法：(P ∧Q ∧A →C )∧(A →P ∨Q ∨C )⇔(⌝P ∨⌝Q ∨⌝A ∨C )∧(⌝A ∨P ∨Q ∨C )⇔(⌝P ∨⌝Q ∨⌝A ∨C )∧(⌝A ∨P ∨Q ∨C ) ⇔((⌝P ∨⌝Q ∨⌝A )∧(⌝A ∨P ∨Q ))∨C ⇔⌝((P ∧Q ∧A )∨(A ∧⌝P ∧⌝Q ))∨C ⇔⌝( A ∧((P ∧Q )∨(⌝P ∧⌝Q )))∨C ⇔⌝( A ∧(P ↔Q ))∨C ⇔(A ∧(P ↔Q ))→C 。

(7)真值表法：由真值表可知，⌝(P ↑Q )⇔⌝P ↓⌝Q 。

公式法：⌝(P ↑Q )⇔⌝(⌝(P∧Q ))⇔⌝(⌝P ∨⌝Q ))⇔⌝P ↓⌝Q 。

(8)真值表法：由真值表可知，⌝(P ↓Q )⇔⌝P ↑⌝Q 。

公式法：⌝(P ↓Q )⇔⌝(⌝(P ∨Q ))⇔⌝(⌝P ∧⌝Q )⇔⌝P ↑⌝Q 。

7.设A 、B 、C 为任意的三个命题公式，试问下面的结论是否正确？ (1)若A ∨C ⇔B ∨C ，则A ⇔B 。

(2)若A ∧C ⇔B ∧C ，则A ⇔B 。

(3)若⌝A ⇔⌝B ，则A ⇔B 。

(4)若A →C ⇔B →C ，则A ⇔B 。

(5)若A ↔C ⇔B ↔C ，则A ⇔B 。

解 (1)不正确。

例如，设有一赋值：A ＝T ，B ＝F ，C ＝T ，则A ∨C ⇔B ∨C ，但A ⇔B 不成立。

(2)不正确。

例如，设有一赋值：A ＝T ，B ＝F ，C ＝F ，则A ∧C ⇔B ∧C ，但A ⇔B 不成立。

(3)正确。

因为⌝A ↔⌝B ⇔(⌝A →⌝B )∧(⌝B →⌝A )⇔(A ∨⌝B )∧(B ∨⌝A )⇔(B → A )∧(A →B )⇔ A ↔B ，所以，若⌝A ⇔⌝B ，则A ⇔B 。

(4)不正确。

例如，设有一赋值：A ＝T ，B ＝F ，C ＝T ，则A →C ⇔B →C ，但A ⇔B 不成立。

(5)正确。

因为，若A ↔C ⇔B ↔C ，则A ↔C 与B ↔C 等值。

当A ↔C 与B ↔C 都为真时，A 和C 等值且B 和C 等值，从而A 和B 等值，此时A ⇔B ；当A ↔C 与B ↔C 都为假时，A 和C 不等值且B 和C 也不等值，从而A 和B 等值，此时A ⇔B 。

总之有，若A ↔C ⇔B ↔C ，则A ⇔B 。

8.试给出下列命题公式的对偶式： (1)(P ∧Q )∨R 。

(2)T ∨(P ∧Q )。

(3)(P ∨Q )∧F 。

(4)⌝(P ∧Q )∧(⌝P ∨Q )。

解 (1)对偶式为(P ∨Q )∧R 。

(2)对偶式为F ∧(P ∨Q )。