第一章 命题逻辑
一、选择
1、 下列语句是命题的有（ ）。
A、2是素数；B、x+5 > 6；C、地球外的星球上也有人；D、这朵花多好看呀！。 2、下列语句不是命题的有（ ）。
A、 x=13； B、离散数学是计算机系的一门必修课； C、鸡有三只脚； D、太阳系以外的星球上有生物； E、你打算考硕士研究生吗？ 3、下列语句是命题的有（ ）。
A、 明年中秋节的晚上是晴天； B、x?y?0； C、xy?0当且仅当x和y都大于0； D、我正在说谎。
4、下列各命题中真值为真的命题有（ ）。
B、 2+2=4当且仅当3是奇数；B、2+2=4当且仅当3不是奇数； C、2+2≠4当且仅当3是奇数； D、2+2≠4当且仅当3不是奇数
5、下列各符号串，不是合式公式的有（ ）。 A、(P?Q)??R； B、((P?Q)?(R?S)； C、P?Q??R； D、(?(P?Q)?R)?S。 6、下列公式是重言式的有（ ）。
A、?(P?Q)；B、(P?Q)?Q；C、?(Q?P)?P；D、(P?Q)?P 7、下列问题成立的有（ ）。
A、 若A?C?B?C，则A?B； B、若A?C?B?C，则A?B； C、若?A??B，则A?B； D、若A?B，则?A??B。 8、命题逻辑演绎的CP规则为（ ）。 B、 在推演过程中可随便使用前提；
B、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果；
C、如果要演绎出的公式为B?C形式，那么将B作为前提，设法演绎出C； D、设?(A)是含公式A的命题公式，B?A，则可用B替换?(A)中的A。
(P?Q)?R的合取范式为（ ）。
A、(P??Q)?R ；B、(P?R)?(?Q?R) ； C、
(P??Q?R)?(P??Q??R)?(P?Q?R)?(P??Q?R)?(?P?Q?R)?(?P??Q?R) D、(P?Q?R)?(P??Q?R)?(P??Q?R)?(?P??Q?R)。 9、 下列符号串是合式公式的有（ ）
A、P?Q；B、P?P?Q；C、(?P?Q)?(P??Q)；D、?(P?Q)。 10、下列等价式成立的有（ ）。
A、P?Q??Q??P；B、P?(P?R)?R；
C、 P?(P?Q)?Q； D、P?(Q?R)?(P?Q)?R。 11、若A1,A2?An和B为wff，且A1?A2???An?B则（ ）。 A、称A1?A2???An为B的前件； B、称B为A1,A2?An的有效结论 C、当且仅当
A1?A2???An?B?F；D、当且仅当
A1?A2???An??B?F。
12、A，B为二合式公式，且A?B，则（ ）。
**A、A?B为重言式； B、A?B；
**C、A?B； D、A?B； E、A?B为重言式。
13、下述命题公式中，是重言式的为（ ）。
A、(p?q)?(p?q)； B、(p?q)?((p?q))?(q?p))； C、?(p?q)?q； D、(p??p)?q。 14、wff?(p?q)?r的主析取范式中含极小项的个数为（ ）。
A 、2； B、 3； C、5； D、0； E、 8 。
二、填空
1、若P，Q，为二命题，P?Q真值为0 当且仅当 。
2、设P，Q 的真值为0，R，S的真值为1，则
?(P?(Q?(R??P)))?(R??S)的真值= 。
3、P，Q真值为0 ；R，S真值为1。则wff(P?(R?S))?((P?Q)?(R?S))的真值为 。
4、wff?((P?Q)?R)?R的主合取范式为 。
5、公式(P?R)?(S?R)??P的主合取范式为
。
6、2是有理数的真值为 。 7、Q：我将去上海，R：我有时间，公式(Q?R)?(R?Q)的
自
然
语
言
为 。
8、 若P，Q为二命题，P?Q真值为1，当且仅当 。 9、 一个命题含有4个原子命题，则对其所有可能赋值有 种。 10、所有小项的析取式为 。
三、证明题
1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T
证明: 左端?((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律)
? ((P∨Q)∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律) ? ((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R)) (等幂律) ?T (代入)
2)?x(P(x)?Q(x))∧?xP(x)??x(P(x)∧Q(x))
证明：?x(P(x)?Q(x))∧?xP(x)??x((P(x)?Q(x)∧P(x))
??x((?P(x)∨Q(x)∧P(x))
??x(P(x)∧Q(x))??xP(x)∧?xQ(x) ??x(P(x)∧Q(x))
3)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R
证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)
?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R
4)?x(A(x)?B(x))? ?xA(x)??xB(x)
证明 ：?x(A(x)?B(x))??x(?A(x)∨B(x))
??x?A(x)∨?xB(x) ???xA(x)∨?xB(x)
??xA(x)??xB(x) 5）证明(P?Q)∧(Q?R)?(P?R)
解：因为((P?Q)∧(Q?R))?(P?R)
??((?P∨Q)∧(?Q∨R))∨(?P∨R) ?(P∧?Q)∨(Q∧?R)∨?P∨R
?(P∧?Q)∨((Q∨?P∨R)∧(?R∨?P∨R)) ?(P∧?Q)∨(Q∨?P∨R)
?(P∨Q∨?P∨R)∧(?Q∨Q∨?P∨R) ?T
所以，(P?Q)∧(Q?R)?(P?R)。
四、计算题
1）求命题公式(?P?Q)?(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)?M1 ?m0∨m2∨m3
2）求命题公式(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)∨(?P∧?R))∨(P∧Q∧R)
?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P
∧Q∧R)
?m0∨m1∨m2∨m7
?M3∨M4∨M5∨M6
3）求(P∨Q)?R的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。
解 (P∨Q)?R??(P∨Q)∨R?(?P∧?Q)∨R
?(?P∨(Q∧?Q)∨R)∧((P∧?P)∨?Q∨R)
?(?P∨Q∨R)∧(?P∨?Q∨R)∧(P∨?Q∨R)∧(?P∨?Q∨R) ?M2∧M4∧M6 ?m0∨m1∨m3∨m5
所以，其相应的成真赋值为000、001、011、101、111：成假赋值为：010、100、110。
五、用公式法判断下列公式的类型：
(1)(?P∨?Q)?(P??Q) (2)(P?Q)?(P∧?(Q∨?R))
解：（1）因为(?P∨?Q)?(P??Q)??(?P∨?Q)∨(P∧?Q)∨(?P∧Q)
?(P∧Q)∨(P∧?Q)∨(?P∧Q) ?m1∨m2∨m3
?M0
所以，公式(?P∨?Q)?(P??Q)为可满足式。
（2）因为(P?Q)?(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R))
?(P∨Q)∨(P∧?Q∧R))
?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R)
?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ?M0∧M1
?m2∨m3∨m4∨m5∨m6∨m7
所以，公式(P?Q)?(P∧?(Q∨?R))为可满足式。
六、推理证明题
1)(P?(Q?S))∧(?R∨P)∧Q?R?S
证明：（1）R 附加前提 （2）?R∨P P
（3）P T(1)(2)，I （4）P?(Q?S) P
（5）Q?S T(3)(4)，I （6）Q P
（7）S T(5)(6)，I （8）R?S CP
2）C∨D， (C∨D)? ?E， ?E?(A∧?B)， (A∧?B)?(R∨S)?R∨S
证明：(1) (C∨D)??E (2) ?E?(A∧?B)
P P
P
(3) (C∨D)?(A∧?B) T(1)(2)，I (4) (A∧?B)?(R∨S) (5) (C∨D)?(R∨S) (6) C∨D
T(3)(4)， I
P
(7) R∨S T(5)，I