数理逻辑复习题

1、一、选择题1、永真式的否定是（2）(1) 永真式(2) 永假式(3) 可满足式(4) (1)-(3)均有可能2、设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，则下列真命题为(1)(1) (2) (3) (4) 。3、设P：我听课，Q：我看小说，则命题R“我不能一边听课，一边看小说”的符号化为 (3) 提示：4、下列表达式错误的有 5、下列表达式正确的有 6、下列联接词运算不可交换的是(3) (3) 6、设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y，则命题“有的人喜欢所有的花”的逻辑符号化为 (3) 7、设L(x)：x是

2、演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些老师”的逻辑符号化为 (3) 8、谓词公式中的 x是自由变元 约束变元 既是自由变元又是约束变元 既不是自由变元又不是约束变元9、下列表达式错误的有 (3) 10、下列推导错在PUSESUG 无11、下列推理步骤错在PUSESUGEG 12、设个体域为a,b，则去掉量词后，可表示为 (3) 提示：原式二、填充题1、一个命题含有n个原子命题，则对其所有可能赋值有 种。2、n个命题变元可产生个互不等价的极小项，其中，任意两个不同极小项的合取式为矛盾式（永假式），而全体极小项的析取式为重言式（永真式），n个命题变元可构造包

3、括F的不同的主析取范式类别为。3、n个命题变元可产生个互不等价的极大项，其中，任意两个不同极大项的析取式为重言式（永真式），而全体极小项的合取式为矛盾式（永假式），n个命题变元可构造包括T的不同的主合取范式类别为。5、公式的对偶公式为。6、设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的逻辑符号可化为 。7、P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为； “虽然你努力了，但还是失败了”的翻译为。8、令：x会叫，：x是狗，：x会咬人，则命题“会叫的狗未必会咬人”的符号化为。9、设P(x)：x是大象，Q(x)：x是

4、老鼠，R(x,y)：x比y重，则命题“大象比老鼠重”的符号化为。10、令A（x）:x是自然数，B（x,y）：x 小于y，则命题“存在最小的自然数” 的符号化为。三、计算题1、用真值表方法判断下列公式的类型，并求（3）的主析取范式与主合取范式（1）（P®Q）«（ØPQ）；（2）Ø（P®Q）Q；（3）（P®Q）ØR；解 （1）、（2）和（3）的真值表如表1、表2和表3所示：表1 P QP®QØPQ（P®Q）«（PQ）0 0 0 1 1 0 1 1110111011111表2P Q P

5、74;QØ（P®Q）Ø（P®Q）Q0 0 0 1 1 0 1 1110100100000表3P Q RP®QØR（P®Q）ØR0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1111100111010101010100010由上述真值表可知，（1）为永真式，（2）为永假式，（3）为可满足式。（3）的主析取范式为：；其主合取范式为。2、给定解释I：D=2，3，L（x,y）为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0

6、,求谓词合式公式的真值。解：。3、个体域为1，2，求"x$y（x+y=4）的真值。解："x$y（x+y=4）Û"x（x+1=4）（x+2=4）Û（1+1=4）（1+2=4）（2+1=4）（2+2=4）Û（00）（01）Û01Û0。四、证明题1、证明下列逻辑恒等式：（1） ()()证明、用真值表法证明P Q PQ （PQ）（QP） F FF TT FT TT TF FF FT T由定义可知，这两个公式是等价的。（2）P(QP)P(PQ)证明、P(QP)P(QP) P(PQ)P(PQ) P(PQ)P(PQ)（3） 证明

7、 ： 左右（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）求证："x(P(x)®Q(x)"xP(x)Û"x(P(x)Q(x)证明：左Û"x(P(x)®Q(x)P(x)Û"x(Ø

8、;P(x)Q(x)P(x)Û"x(P(x)Q(x) Û右（6）求证："x"y(P(x)®Q(y)Û $xP(x)®"yQ(y)证明："x"y(P(x)®Q(y)Û"x"y(ØP(x)Q(y)Û"x(ØP(x)"yQ(y)Û"xØP(x)"yQ(y)ÛØ$xP(x)"yQ(y)Û$xP(x)®"yQ(

9、y)（7）求证：证明：左右2、用推理规则证明下列各结论是各前提的有效结论：（1）PQ，QR，R，SP=>S证明：(1) R P(2) QR P(3) Q T（1），（2）(析取三段论)(4) PQ P(5) P T（3），（4）(拒取式)(6) SP P(7) S T（5），（6）(析取三段论)（2）A(BC)，C(DE)，F(DE),A=>BF证明： (1) A P (2) A(BC) P (3) BC T（1），（2）(假言推理)(4) B P（附加前提）(5) C T（3），（4）(假言推理)(6) C(DE) 前提(7) DE T（5），（6）(假言推理)(8) F(DE)

10、 前提(9) F T（7），（8）(拒取式)(10) BF CP （3）(PQ)(RS)，(QW)(SX)，(WX)，PR => P证明：（1） P P （假设前提）（2） PR P（3） R T（1），（2）(假言推理)（4） (PQ)(RS) P（5） PQ T（4）(化简律)（6） RS T（4）(化简律)（7） Q T （1），（5）(假言推理)（8） S T（3），（6）(假言推理)（9） (QW)(SX) P（10） QW T（9）(化简律)（11） SX T（9）(化简律)（12） W T（7），（10）(假言推理)（13） X T（8），（11）(假言推理)（14） WX

11、 T（12），（13）(合取引入)（15） (WX) P（16） (WX)(WX) T（14），（15）(合取引入)由（16）得出矛盾式，故P为原前提的有效结论（4）"x(P(x)®Q(y)R(x)，$xP(x)ÞQ(y)$x(P(x)R(x)证明(1)$xP(x) P(2)P(a) T(1)，ES(3)"x(P(x)®Q(y)R(x) P(4)P(a)®Q(y)R(a) T(3)，US(5)Q(y)R(a) T(2)(4) (假言推理)(6)Q(y) T(5) (化简律) (7)R(a) T(5) (化简律)(8)P(a)R(a)

12、T(2)(7) (合取引入)(9)$x(P(x)R(x) T(8)，EG(10)Q(y)$x(P(x)R(x) T(6)(9) (合取引入)（5）证明：$xP(x) P（附加前提）P(e)TESPTUSQ(e)T(假言推理)TEGCP（6）Þ证明：PPT(假言推理)TESPTESTUST（附加律）T(假言推理)T(合取引入)TEGTEG（7）证明：（1） P（假设前提） （2） T （1） （3） T（2）(化简律) （4） T（3）ES （5） P （6） T （5） （7） T（6）US （8） T (4). (7) (假言推理)(9) T (2) (化简律)(10) T(9)U

13、S(11) T (8) (10) (合取引入)由（11）得出矛盾式，故为原前提的有效结论 五、将下列命题形式化，并证明结论的有效性：1、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效?前提: (1) 若A队得第一，则B队或C队获亚军;(2) 若C队获亚军，则A队不能获冠军;(3) 若D队获亚军，则B队不能获亚军;(4) A 队获第一;结论: (5) D队不是亚军。证明、设A：A队得第一;B: B队获亚军;C: C队获亚军;D: D队获亚军;则前提符号化为A（BC），CA，DB，A；结论符号化为 D。 本题即证明 A（BC），CA，DB，AD。（1） A P （2） A

14、（BC） P （3） BC T（1），（2）(假言推理) （4） CA P （5） C T（1），（4）(拒取式) （6） B T（3），（5）(析取三段论) （7） DB P （8） D T（6），（7）(拒取式) 故该结论有效2、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好。解 设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生的集合，则命题可符号化为：ØP®$xØA(x)，"xA(x)«QQ®P。(1)ØP®$xØA(x) P(2)ØP®Ø"xA(x) T(1)(3)"xA(x)®P T(2) (4)"xA(x)«Q P(5)("xA(x)®Q)(Q®"xA(x) T(4)(6)Q®"xA(x)