数理逻辑复习题.doc

一、选择题1、永真式的否定是（2）(1) 永真式(2) 永假式(3) 可满足式(4) (1)-(3)均有可能2、设P：22=5，Q：雪是黑的，R：24=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是演员，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个命题变元可构造包括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是老鼠，R(x,y)：x比y重，则命题“大象比老鼠重”的符号化为。10、令A（x）:x是自然数，B（x,y）：x 小于y，则命题“存在最小的自然数” 的符号化为。三、计算题1、用真值表方法判断下列公式的类型，并求（3）的主析取范式与主合取范式（1）（PQ）（PQ）；（2）（PQ）Q；（3）（PQ）R；解 （1）、（2）和（3）的真值表如表1、表2和表3所示：表1 P QPQPQ（PQ）（PQ）0 0 0 1 1 0 1 1110111011111表2P Q PQ（PQ）（PQ）Q0 0 0 1 1 0 1 1110100100000表3P Q RPQR（PQ）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 ,求谓词合式公式的真值。解：。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）010。四、证明题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） 证明 ： 左右（4）求证：$x(A(x)B(x) xA(x)$xB(x)证明 ：$x(A(x)B(x)$x(A(x)B(x)$xA(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(P(x)Q(x)P(x)x(P(x)Q(x) 右（6）求证：xy(P(x)Q(y) $xP(x)yQ(y)证明：xy(P(x)Q(y)xy(P(x)Q(y)x(P(x)yQ(y)xP(x)yQ(y)$xP(x)yQ(y)$xP(x)yQ(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) 前提(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 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) 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)US(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（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$xA(x)，xA(x)QQP。(1)P$xA(x) P(2)PxA(x) T(1)(3)xA(x)P T(2) (4)xA(x)Q P(5)(xA(x)Q)(QxA(x) T(4)(6)QxA(x) T(5) (化简律)(7)QP T(6)(3) （假言三段