2014离散数学期中考试试题
姓名 班级 学号 成绩
一、选择填空题（每小题3分，共33分）
1、设p,r为真命题，q,s为假命题，则复合命题(p?q)?(?r?s)的真值为
2、 下列公式是重言式的有（ ）。
A、?(P?Q)； B、(P?Q)?Q；
C、?(Q?P)?P； D、(P?Q)?P
3、含有三个命题变项P，Q，R的命题公式P?Q的主析取范式是 _____________________________________________________________ 。 4、设公式B含命题变项p,q,r，已知B的成真赋值为001，011， 101， 100,
则B的主合取范式为 5、请写出命题公式的一个极小全功能集
6、谓词公式?x(P(x)??yR(y))?Q(x)中量词?x的辖域是 7、若个体域为整数域，下列公式中值为真的是 A ?x?y(x?y?0) B ?y?x(x?y?0) C ?x?y(x?y?0) D ??x?y(x?y?0) 8、将“不是所有人都喜欢离散数学”谓词逻辑符号化，
9、??x?yP(x,y)的前束范式是 10、设个体域{1,2},谓词P(1)=1,P(2)=0，Q(1)=0，Q(2)=1，则?x(P(x)?Q(x))的真值是 11、求集合A={?,{?}}的幂集P(A) 二、计算证明题（共67分）
1、求公式(?p?q)?(p?r)的真值表，并判断类型（10分）。 2、（9分）证明下面各题中两公式等价： (P?(Q??R))??P?Q与?（P??Q）
3、求命题公式(q?p)?(?p?(q?r))的主析取范式、主合取范式。（10分）
4、（10分）在自然推理系统P中，构造用自然语言描述的推理。 红、黄、蓝、白四队参加联赛.
如果红队第三，则当黄队第二时，蓝队第四。或者白队不是第一，或者红队是第三。事实上，黄队第二。所以，如果白队第一，那么蓝队第四。
5、证明谓词公式(?xF(x)??yG(y))???yG(y)??xF(x)是重言式。（8分） 6、（10分）求谓词公式?xF(x)??yG(x,y)的前束范式。
7、（10分）设计一盏电灯的开关电路，要求受3个开关A、B、C的控制，当且仅当A和C同时关闭或B和C同时关闭时灯亮。设F表示灯亮。 （1）写出F对应的命题公式；
（2）写出F的主析取范式和主合取范式。
