离散数学单元测试（数理逻辑部分）一、填空题1. 命题公式，则G共有 个不同的真值赋值，使公式G为假的赋值是 ，把G在其所有赋值下所取真值列成一个表，称为G的 ，并可以通过它判定该公式的类型是 。2. 给定谓词合式公式A，其中一部分公式形式为xB(x)或$xB(x)，则量词，$后面所跟的x称_-，而称B(x)为相应量词的 。3. 给定个体域为整数域，令F（x）：x是偶数，G（x）：x是奇数；则：（1）的值为 ；（2）的值为 。4. 在谓词逻辑中将下面命题符号化：（1）在北京工作的人未必都是北京人。（设F（x）：x在北京工作，G（x）：x是北京人）（2）没有不犯错误的人。（设F（x）：x是人，G（x）：x犯错误）5. 设个体域为，将中的量词消除，写成与之等值的命题公式:二、单项选择题1. 下列语句中不是命题的是（ ）。A这个语句是假的。B1+1=1.0C飞碟来自地球外的星球。D凡石头都可练成金。2. 令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）。Apq Bpq Cpq Dpq3. 下面联结词运算不可交换的是（ ）。A BC D4. 由两个命题变元p，q的极小项是（ ）。AppqBpq Cpq Dppq5. 下列命题公式不是重言式的是（ ）。Aq（pq） B（pq）pC（p q）（ pq） D（pq）（pq）6. 下列4个推理定律中，不正确的是（ ）。AA（AB）B（AB）ABC（AB）ABD（AB）BA7. 谓词公式x(P(x)$yR(y)Q(x)中量词x的辖域是（ ）。ABP（x）C(P(x)$yR(y)DP(x), Q(x)8. 设个体域A=a,b，公式x（P(x)$xS(x)）在A中消去量词后应为（ ）。AP(x)S(x)BP(a)P(b)(S(a)S(b)CP(a)S(b)DP(a)P(b)S(a)S(b)9. 设个体域是整数集，则下列命题的真值为真的是（ ）。A$ yx(xy=1)Bx$y (xy0)Cx$y (xy=y2)D$yx(xy=x2)10. 下列公式是前束范式的是（ ）。ABC D11. 下面给出的一阶逻辑等值式中，（ ）是错的。三、判断题1. 判断下列陈述是否是命题？哪些是简单命题？哪些是复合命题？（1） 是无理数。 （2） 什么时候开会呀？ （3） 。（2） 苹果树和梨树都是落叶乔木。（3） 李辛与李末是兄弟。2. 设A与B均为含n个命题变项的公式，判断下列命题的真值。（1） AB当且仅当AB是可满足式。（2） 若A为重言式，则A的主析取范式中含有2n个不同的极小项。（3） A为矛盾式，当且仅当A的主合取范式中含有2n个不同的极大项。（4） 任何公式A都能等值地化为联结词集、中的公式。3. 任何一阶逻辑公式都存在唯一与之等值的前束范式。四、计算题1. 求命题公式的主析取范式与主合取范式，并判断公式的类型。2. 已知命题A含有命题变元p、q、r，且已知公式A的成真赋值为：001,010,111，试求公式A的主析取范式和主合取范式。3. 某科研所要从3个项目A、B、C中选择12个项目上马，由于某些原因，立项时要满足以下条件：(1)若A上，则C也要上；(2)若B上，则C不能上；(3)若C不上，则A或B可以上。请找出所有的立项方案。4. 设I是如下一个解释：，试求下列公式在I下的真值： 五、证明题1. 利用等值演算法证明命题公式（pq）（qr）（pr）为永真式。2. 构造下列推理的证明（1）前提：结论：（2）前提：pq, rq ,rs 结论：ps3. 在命题逻辑中构造下面推理的证明。（1）（P50-例3.5）如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。（2）（P54-17）只要A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以A犯了谋杀罪。（3）如果今天是星期六，我们就到颐和园或圆明园去玩；如果颐和园游人太多，我们就不去颐和园玩；今天是星期六，并且颐和园游人太多。所以我们去圆明园玩。4.在一阶逻辑中构造下列推理的证明：（1）凡人都要呼吸。张三是人。所以张三要呼吸。（2）前提： x(F(x)(G(x)R(x)，$xF(x)结论：$x(F(x)R(x)（3）前提：x(F(x)G(x)， $xG(x)结论：$xF(x)（4）前提：x(F(x)G(x)，x(G(x)R(x)，xR(x)结论：xF(x)7