发布时间 : 星期六 文章数理逻辑部分更新完毕开始阅读fdbe5d29cfc789eb172dc8c7
数理逻辑部分
一、 填空题
1、将几个命题联结起来，形成一个复合命题的逻辑联结词主要有 、 、 、 和 。 2、命题公式G=（P?Q）?R，则G共有 个不同的解释；把G在其所有解释下所
取真值列成一个表，称为G的 ；解释（?P，Q，?R）或（0，1，0）使G的真值为 。 3、 已知命题公式G?(?P?Q)?R，则G的主析取范式是 。
4、 求公式?(P?Q)?(P?Q)的析取范式
合取范式是 。
5、 设命题公式G?P??(Q?R)，则使公式G为假的解释是 、 和 。
6、设F(x):x是火车，G?y?:y是汽车，H(x,y):x比y快，则“每 一列火车都比某些汽车快。”可符号化为
7、将公式化成等价的前束范式，?x(??yP(x,y)?(?zQ(z)?R(x)))? 。 8、设谓词的定义域为{a,b,c}，将表达式?x(P(x)?Q(x))中的量词消除，写成与之等价的
命题公式是 。
二、 单项选择题 1、下列语句中，（ ）是命题。
A．下午有会吗？ B．这朵花多好看呀！ C．2是常数。 D．请把门关上。 2、一个公式在等价意义下，下面哪个写法是唯一的（ ）。
A．析取范式 B．合取范式 C．主析取范式 D．以上答案都不对 3、设命题公式G?P?(P?(Q?R))，则G是（ ）。 A. 恒假的 B. 恒真的 C. 可满足的 D. 析取范式
4、设命题公式G?P?Q,H?P?(P?Q)，则G与H的关系是（ ）。 A.G?H;B.H?G;C.G?H;D.以上都不是。
5、已知命题G??(P?(Q?R))，则所有使G取真值1的解释是（ B ）。
A （0，0，0），（0，0，1），（1，0，0）
B （1，0，0），（1，0，1），（1，1，0） C （0，1，0），（1，0，1），（0，0，1） D （0，0，1），（1，0，1），（1，1，1）
6、设I是如下一个解释，D?{a,b},P(a,a)1P(a,b)0P(b,a)1P(b,b)0，
则在解释I下取真值为1的公式是（ ）。 A.?x?yP(x,y);B.?x?yP(x,y);C.?xP(x,x);D.?x?yP(x,y)
7、下面给出的一阶逻辑等价式中，（ ）是错的。
A.B.C.D.?x(A(x)?B(x))??xA(x)??xB(x);?x(A(x)?B(x))??xA(x)??xB(x);??xA(x)??x(?A(x));A??xB(x)??x(A?B(x)).
三、 计算题
1、 求命题公式?（P?Q）?（P?Q）的析取范式与合取范式。
2、试求下列公式的主析取范式：
（1）P?((P?Q)??(?Q??P))；
3、用真值表判断下列公式是恒真？恒假？可满足？
（1）（P??P）?Q （2）?（P?Q）?Q （3）（（P?Q）?（Q?R））?（P?R） 4、设解释I为：
（1） 定义域D={-2，3，6}； （2） F（x）：x?3；
G（x）：x?5。
在解释I下求公式?x（F（x）?G（x））的真值。 5、设I是如下一个解释：
D?{2,3},af(2)f(3)F(2)F(3)G(2,2)G(2,3)G(3,2)G(3,3)232011111，试求下列公
式在I下的真值：
1)2)?x(F(x)?G(x,a));?x(F(f(x))?G(x,f(x))).
6、设N(x):x是数，L(x,y):x小于y，将“不存在最小的数。”符号化。 四、 证明题
1. 利用基本等价式证明下列命题公式为恒真公式。
（（P?Q）?（Q?R））?（P?R） （（P?Q）??（?P?（?Q??R）））?（?P??Q）?（?P??R） 2、 证明等价式(?P?(?Q?R))?(Q?R)?(P?R)?R。 3、 用形式演绎法证明：{?P?Q,?Q?R,R?S}蕴涵P?S
4、 利用一阶逻辑的基本等价式，证明：
?x?y（F（x）?G（y））=?xF（x）??yG（y）