离散数学复习题

离散数学复习题命题逻辑复习一、填空题1.设p:天下雨，q:天刮风，r:我去书店，则命题“如果天不下雨并且不刮风，我就去书店”的符号化形式为。2.设12:p,23:q,命题“只要12,就有23”可以符号化为。3.公式q)p(q)(p的成真赋值为和。4．公式(pq)p的成真赋值为和。5.重言式的主析取范式是_______，一个重言式与一个矛盾式的析取是________式。6．命题公式A=(p∧q)r，则解释010使A的真值为。7．重言式的主合取范式是_______，矛盾式的主析取范式_______。二、选择题1.下列语句中是命题的只有…………………………………()A、实数范围内，220xyB、在实数范围内，3xyC、请回答这个问题D、真正有学问的人怎么会不关心政治？2.命题公式A与B是等价(值)的，是指……………………（）A、A与B有相同的原子变元B、A与B都是可满足的C、A的真值为真时，B的真值也为真D、A与B有相同的真值3.所有使命题公式()pqr为真的赋值为………………（）A.010,100,101,110,111B.010,100,101,111C.全体赋值D.不存在4.若,PQ为命题变元，则()()PQPQ的类型是…（）A．永真式B.矛盾式C.可满足式D.不可满足式5.下列语句中是真命题的是…………………………………()A、实数范围内，0yxB、3或5是偶数C、如果1+2=5，那么雪是黑的D、大家想做什么，就做什么，行吗？6.若,pq为命题变元，则()()pqqp的类型是（）A、重言式B、矛盾式C、可满足式D、不可满足式7.设p：我很累，q：我去学习，则命题：“除非我很累，否则我就去学习”的符号化正确的是（）A．┐p∧qB．┐p→qC．┐p→┐qD．p→┐q8.下列命题公式为重言式的是（）A．p→(p∨q)B．(p∨┐p)→qC．q∧┐qD．p→┐q9.下面4个推理定律中，不正确的为()A.A=(A∨B)(附加律)B.(A∨B)∧┐A=B(析取三段论)C.(A→B)∧A=B(假言推理)D.(A→B)∧┐B=A(拒取式)10．下列语句中不是命题的只有（）A．这个语句是假的。B．1+1=1.0C．飞碟来自地球外的星球。D．凡石头都可练成金。三、综合题1.求公式的)()(rqqp主析取范式和主合取范式（要求写出步骤，结果用极小项或极大项的编码表示），并给出公式的成真赋值。2．求公式rqp)(的主析取范式，再用主析取范式求主合取范式，并写出成真赋值。3.求公式RQP)(的主析取范式和主合取范式（要求写出步骤，结果用极小项或极大项的编码表示）。4．在自然推理系统P中构造下面推理的证明。只要A曾到过受害者房间并且11点以前没有离开，A就犯了谋杀罪。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以A犯了谋杀罪。5.求命题公式(PQ)(P∨Q)的主析取范式和主合取范式（要求写出步骤，结果用极小项或极大项的编码表示）。6.在自然推理系统中构造下面的推理证明。（10分）若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。一、填空题1.设p:天下雨，q:天刮风，r:我去书店，则命题“如果天不下雨并且不刮风，我就去书店”的符号化形式为rqp。2.设12:p,23:q,命题“只要12,就有23”可以符号化为qp。3.公式q)p(q)(p的成真赋值为00和11。4．公式(pq)p的成真赋值为10和11。5.重言式的主析取范式是_含全部极小项_，一个重言式与一个矛盾式的析取是_重言_式。6．命题公式A=(p∧q)r，则解释010使A的真值为1。7．重言式的主合取范式是___1____，矛盾式的主析取范式__0_____。二、选择题1.下列语句中是命题的只有…………………………………(A)A、实数范围内，022yxB、在实数范围内，3yxC、请回答这个问题D、真正有学问的人怎么会不关心政治？2.命题公式A与B是等价(值)的，是指……………………（D）A、A与B有相同的原子变元B、A与B都是可满足的C、A的真值为真时，B的真值也为真D、A与B有相同的真值3.所有使命题公式)(rqp为真的赋值为………………（A）A.010,100,101,110,111B.010,100,101,111C.全体赋值D.不存在4.若QP,为命题变元，则)()(QPQP的类型是…（B）A．永真式B.矛盾式C.可满足式D.不可满足式5.下列语句中是真命题的是…………………………………(C)A、实数范围内，0yxB、3或5是偶数C、如果1+2=5，那么雪是黑的D、大家想做什么，就做什么，行吗？6.若qp,为命题变元，则)()(pqqp的类型是（C）A、重言式B、矛盾式C、可满足式D、不可满足式7.设p：我很累，q：我去学习，则命题：“除非我很累，否则我就去学习”的符号化正确的是（B）A．┐p∧qB．┐p→qC．┐p→┐qD．p→┐q8.下列命题公式为重言式的是（A）A．p→(p∨q)B．(p∨┐p)→qC．q∧┐qD．p→┐q9.下面4个推理定律中，不正确的为(D)A.A=(A∨B)(附加律)B.(A∨B)∧┐A=B(析取三段论)C.(A→B)∧A=B(假言推理)D.(A→B)∧┐B=A(拒取式)10．下列语句中不是命题的只有（A）A．这个语句是假的。B．1+1=1.0C．飞碟来自地球外的星球。D．凡石头都可练成金。三、综合题1.求公式的)()(rqqp主析取范式和主合取范式（要求写出步骤，结果用极小项或极大项的编码表示），并给出公式的成真赋值。解：方法1)()(rqqp)()(rqqp)()()()(rqqqrpqp))(())(())((rqpprqqprrqp)()()()(rqprqprqprqp7310mmmm6542MMMM方法2)()(rqqp)()(rqqp))(())((rqpprrqp)()()()(rqprqprqprqp6542MMMM7310mmmm成真赋值为：000，001，011，1112．求公式rqp)(的主析取范式，再用主析取范式求主合取范式，并写出成真赋值。解：rqp)(rqp)(rqp)())()(())((rqqpprrqp)()()()()(rqprqprqprqprqp75310mmmmm642MMM成真赋值为：000，001，011，101，1113.求公式RQP)(的主析取范式和主合取范式（要求写出步骤，结果用极小项或极大项的编码表示）。主析取范式是：13457mmmmm；主合取范式是：026MMM4．在自然推理系统P中构造下面推理的证明。只要A曾到过受害者房间并且11点以前没有离开，A就犯了谋杀罪。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以A犯了谋杀罪。解：设p：A到过受害者房间，q：A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。前提：rqp)(，p，sq，s结论：r证明：①sq前提引入②s前提引入③q①②拒取式④p前提引入⑤qp③④合取⑥rqp)(前提引入⑦r⑤⑥假言推理5.求命题公式(PQ)(P∨Q)的主析取范式和主合取范式（要求写出步骤，结果用极小项或极大项的编码表示）。解：(PQ)(P∨Q)(PQ)∨(P∨Q)(P∨Q)∨(P∨Q)(P∧Q)∨(P∨Q)(P∨P∨Q)∧(Q∨P∨Q)(P∨Q)M1m0∨m2∨m36.在自然推理系统中构造下面的推理证明。（10分）若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。解：设p：小张喜欢数学，q：小李喜欢数学，r：小赵喜欢数学，s：小李喜欢物理。前提：()pqr，sq，ps结论：r证明：①ps前提引入②s①化简③p①化简④sq前提引入⑤q②④拒取式⑥()pqr前提引入⑦qr③⑥假言推理⑧r⑤⑦析取三段论谓词逻辑复习一、填空题1.设F(x):x是人；H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为。2.设F(x):x是在北京卖菜的人，G(x):x是外地人，则命题“在北京卖菜的人不全是外地人”在一阶逻辑中可以符号化为。3．设F(x):x是在美国留学的学生，G(x):x是亚洲人，则命题“在美国留学的学生未必都是亚洲人”在一阶逻辑中可以符号化为。二、选择题1.设个体域为整数集，下列真值为真的公式是……………………（）A.1xyxyB.0xyxyC．xyxyyD.2xyxyy2.设个体域为N={0,1,2,……}，则以下谓词公式中为假的是（）A、B、C、D、3．关于谓词公式((,)(,))(,)xyPxyQyzxPxy，下面的描述中错误的是()A．x的辖域是((,)(,))yPxyQyzB．z是该谓词公式的约束变元C．x的辖域是(,)PxyD．x是该谓词公式的约束变元4．命题xG(x)取真值1的充分必要条件是().A.对任意x，G(x)都取真值1.B.有一个x0，使G(x0)取真值1.C.有某些x，使G(x0)取真值1.D.以上答案都不对.三、综合题1．将谓词公式,xyFxyzGzHx化成前束范式。2.将谓词公式),,()),()((zyxzHyxGyxxF化成前束范式。3．求公式)),()((),(2121211xxGxxFxxFx的前束范式。4.自然推理系统中，构造下面推理的证明：所有的有理数是实数，某些有理数是整数，因此，有些实数是整数。5.自然推理系统中，构造下面推理的证明：每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的，所以王大海在他的事业中将获得成功。（个体域为人类集合）6.设个体域为D＝{a,b,c}，将公式))()((yyGxFx的量词消去。7.在自然推理系统NF中构造下面的推理证明。“所有的哺乳动物都是脊椎动物；并非所有的哺乳动物都是胎生动物。所以有些脊椎动物不是胎生的。”（个体域为全总个体域）8.在自然推理系统NF中构造下面的推理证明。“所有的田径队员都是运动员；并非所有的田径队员都是健康的。所以有些运动员不是健康的。”（个体域为全总个体域）一、填空题1.设F(x):x是人；H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为,xyFxFyHxy。2.设F(x):x是在北京卖菜的人，G(x):x是外地人，则命题“在北京卖菜的人不全是外地人”在一阶逻辑中可以符号化为)))()(())(()((xGxFxxGxFx。3．设F(x):x是在美国留学的学生，G(x):x是亚洲人，则命题“在美国留学的学生未必都是亚洲人”在一阶逻辑中可以符号化为)))()((())()((xGxFxxGxFx或。二、选择题1.设个体域为整数集，下列真值为真的公式是……………………（B）A.1xyxyB.0xyxyC．xyxyyD.2xyxyy2.设个体域为N={0,1,2,……}，则