数理逻辑复习题

v1.0可编辑可修改v1.0可编辑可修改PAGEPAGE10v1.0可编辑可修改PAGE一、选择题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“我不能一边听课，一边看小说”的符号化为=2\*GB2⑵=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷提示：4、下列表达式错误的有=4\*GB2⑷=1\*GB2⑴=2\*GB2⑵=3\*GB2⑶=4\*GB2⑷5、下列表达式正确的有=4\*GB2⑷=1\*GB2⑴=2\*GB2⑵=3\*GB2⑶=4\*GB2⑷6、下列联接词运算不可交换的是(3)=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷6、设D：全总个体域，F（x）：x是花，M(x)：x是人，H(x,y)：x喜欢y，则命题“有的人喜欢所有的花”的逻辑符号化为=4\*GB2⑷=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷7、设L(x)：x是演员，J(x)：x是老师，A(x,y)：x钦佩y，命题“所有演员都钦佩某些老师”的逻辑符号化为=2\*GB2⑵=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷8、谓词公式中的x是=3\*GB2⑶=1\*GB2⑴自由变元=2\*GB2⑵约束变元=3\*GB2⑶既是自由变元又是约束变元=4\*GB2⑷既不是自由变元又不是约束变元9、下列表达式错误的有=1\*GB2⑴=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷10、下列推导错在=3\*GB2⑶① P② US①③ ES②④ UG③=1\*GB2⑴②=2\*GB2⑵③=3\*GB2⑶④=4\*GB2⑷无11、下列推理步骤错在=3\*GB2⑶① P② US①③ ES②④ UG③⑤ EG④=1\*GB2⑴①→②=2\*GB2⑵②→③=3\*GB2⑶③→④=4\*GB2⑷④→⑤12、设个体域为{a,b}，则去掉量词后，可表示为=4\*GB2⑷=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷提示：原式二、填充题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）（P∨Q）；（2）（PQ）∧Q；（3）（PQ）∧R；解（1）、（2）和（3）的真值表如表1、表2和表3所示：表1PQPQP∨Q（PQ）（P∨Q）00011011110111011111表2PQPQ（PQ）（PQ）∧Q00011011110100100000表3PQRPQR（PQ）∧R000001010011100101110111111100111010101010100010由上述真值表可知，（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}，求xy（x+y=4）的真值。解：xy（x+y=4）x（（x+1=4）∨（x+2=4））（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+2=4））（0∨0）∧（0∨1）0∧10。四、证明题1、证明下列逻辑恒等式：（1）ＰＱ(ＰＱ)(ＱＰ)证明、用真值表法证明PQPQ（PQ）（QP）FFFTTFTTTTFFFFTT由定义可知，这两个公式是等价的。（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)（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）P→Q，QR，R，SP=>S证明：(1)RP(2)QRPQT（1），（2）(析取三段论)P→QPPT（3），（4）(拒取式)SPP(7)ST（5），（6）(析取三段论)（2）A→(B→C)，C→(DE)，F→(DE),A=>B→F证明：(1)AP(2)A→(B→C)P(3)B→CT（1），（2）(假言推理)(4)BP（附加前提）CT（3），（4）(假言推理)C→(DE)前提DET（5），（6）(假言推理)F→(DE)前提FT（7），（8）(拒取式)B→FCP（3）(P→Q)(R→S)，(Q→W)(S→X)，(WX)，P→R=>P证明：（1）PP（假设前提）（2）P→RP（3）RT（1），（2）(假言推理)（4）(P→Q)(R→S)P（5）P→QT（4）(化简律)（6）R→ST（4）(化简律)（7）QT（1），（5）(假言推理)（8）ST（3），（6）(假言推理)（9）(Q→W)(S→X)P（10）Q→WT（9）(化简律)（11）S→XT（9）(化简律)（12）WT（7），（10）(假言推理)（13）XT（8），（11）(假言推理)（14）WXT（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) T①ES③ P④ T③US⑤Q(e) T②④(假言推理)⑥ T⑤EG⑦ CP（6）证明：⑴ P⑵ P⑶ T⑴⑵(假言推理)⑷ T⑵ES⑸ P⑹ T⑸ES⑺ T⑶US⑻ T⑹（附加律）⑼ T⑺⑻(假言推理)⑽ T⑷⑼(合取引入)⑾ T⑽EG⑿ T⑾EG（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队获亚军;若C队获亚军，则A队不能获冠军;若D队获亚军，则B队不能获亚军;A队获第一;结论:(5)D队不是亚军。证明、设A：A队得第一;B:B队获亚军;C:C队获亚军;D:D队获亚军;则前提符号化为A（BC），CA，DB，A；结论符号化为D。本题即证明A（BC），CA，DB，AD。（1）AP（2）A（BC）P（3）BCT（1），（2）(假言推理)（4）CAP（5）CT（1），（4）(拒取式)（6）BT（3），（5）(析取三段论)（7）DBP（8）DT（6），（7）(拒取式)故该结论有效2、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好。解设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生的集合，则命题可符号化为：PxA(x)，xA(x)QQP。(1)PxA(x)P(2)P