离散数学试卷

离散数学2014.1.1010:00-11:40阜阳师范学院电子与通信工程数理逻辑部分选择、填空及判断下列语句不是命题的（A）。(A)你打算考硕士研究生吗？(B)太阳系以外的星球上有生物。(C)离散数学是计算机系的一门必修课。(D)雪是黑色的。命题公式P(PP)的类型是（A）(A)永真式(B)矛盾式(C)非永真式的可满足式(D)析取范式A是重言式，那么A的否定式是(A)A.矛盾式B.重言式C.可满足式D.不能确定以下命题公式中，为永假式的是(C)A.p→(p∨q∨r)B.(p→┐p)→┐pC.┐(q→q)∧pD.┐(q∨┐p)→(p∧┐p)命题公式P→Q的成假赋值是(D)A.00,11B.00,01,11C.10,11D.10谓词公式),()(yxRxxP中，变元x是(B)A.自由变元B.既是自由变元也是约束变元C.约束变元D.既不是自由变元也不是约束变元命题公式P(QQ)的类型是(A)。(A)永真式(B)矛盾式(C)非永真式的可满足式(D)析取范式设B不含变元x，))((BxAx等值于(A)A.BxxA)(B.))((BxAxC.BxxA)(D.BxAx)((下列语句中是真命题的是(D)。A．你是杰克吗？B．凡石头都可练成金。C．如果2+2=4，那么雪是黑的。D．如果1+2=4，那么雪是黑的。从集合分类的角度看，命题公式可分为(B)A.永真式、矛盾式B.永真式、可满足式、矛盾式C.可满足式、矛盾式D.永真式、可满足式命题公式﹁p∨﹁q等价于(D)。A.﹁p∨qB.﹁(p∨q)C.﹁p∧qD.p→﹁q一个公式在等价意义下，下面写法唯一的是(D)。(A)范式(B)析取范式(C)合取范式(D)主析取范式下列含有命题p，q，r的公式中，是主析取范式的是(D)。离散数学2014.1.1010:00-11:40阜阳师范学院电子与通信工程(A)(pqr)(pq)(B)(pqr)(pq)(C)(pqr)(pqr)(D)(pqr)(pqr)设个体域是整数集合，P代表xy((xy)(xyx))，下面描述正确的是（C）。(A)P是真命题(B)P是假命题(C)P是一阶逻辑公式，但不是命题(D)P不是一阶逻辑公式对一阶逻辑公式((,)(,))(,)xyPxyQyzxPxy的说法正确的是(B).(A)x是约束的，y是约束的，z是自由的；(B)x是约束的，y既是约束的又是自由的，z是自由的；(C)x是约束的，y既是约束的又是自由的，z是约束的；(D)x是约束的，y是约束的，z是约束的；n个命题变元可产生(D)个互不等价的布尔小项。(A)n(B)n2(C)2n(D)2n命题“没有不犯错误的人”符号化为（D）。设xxM：)(是人，xxP：)(犯错误。(A)))()((xPxMx(B))))()(((xPxMx(C))))()(((xPxMx(D))))()(((xPxMx下列命题公式等值的是（C）BBAAQPQQPQBAABAAQPQP),()D(),()C()(),()B(,)A(给定命题公式：)(RQP，则所有可能使它成真赋值为（B），成假赋值为（C）。(A)111，011；000(B)111，011，100，101，110；(C)000，010，001；(D)000，110，011，001，100。给定前提：RPQSQP,,)(，则它的有效结论为：（B）。(A)S；(B)SR；(C)P；(D)QR。命题：“所有的马都比某些牛跑得快”的符号化公式为：（C）。假设：)(xH：x是马；)(xC：x是牛；),(yxF：x比y跑得快。(A)))),()(()((yxFyCyxHx；(B)))),()(()((yxFyCyxHx；离散数学2014.1.1010:00-11:40阜阳师范学院电子与通信工程(C)))),()(()((yxFyCyxHx；(D)))),()(()((yxFyCxHxy。设P：a是偶数，Q：b是偶数.R：a+b是偶数，则命题“若a是偶数，b是偶数，则a+b也是偶数”符号化为(C)．(A)PQR(B)PQR(C)PQR(D)PQR表达式))(),(())(),((zzQyxRyzQyxPx中x的辖域是(B)．(A)P(x,y)(B)P(x,y)Q(z)(C)R(x,y)(D)P(x,y)R(x,y)判断一个语句是否为命题，首先要看它是否为陈述句，然后再看它是否有唯一的真值。命题公式(P∨Q)→R的只含联结词和∧的等值式为：))((RQP。BABA)(为假言推理规则。在一阶逻辑中符号化命题“有会说话的机器人。”设M(x):x是机器人；S(x):x是会说话的；上述句子可符号化为：(x)(M(x)∧S(x))。设p:我们爬山,q:我们划船,在命题逻辑中，命题“我们不能既爬山又划船”的符号化形式为¬（p∧q）.设p:小王走路,q:小王唱歌,在命题逻辑中，命题“小王边走路边唱歌”的符号化形式为（p∧q）.量词否定等值式)(xxA)(xAx。设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为(()()(,))xyFxFyHxy.若含有n个命题变项的公式A是矛盾式，则A的主合取范式含2n个极小项。取个体域为全体整数的集合，给出下列各公式：(1)()()()()xyzxyz(2)()()xxyx(3)()()(2)xyxyy其中公式(1)的真值为真，公式(3)的真值为假。若含有n个命题变项的公式A是重言式，则A的主合取范式为1或T。命题公式)(RQP的所有成假赋值为000,001,010。谓词公式()()xPxxQx的前束范式为(()())xPxQx。在一阶逻辑中，将命题“没有不能表示成分数的有理数”符号化为))()((xGxFx或))()((xGxFx（设)(xF：x是有理数；)(xG：x能离散数学2014.1.1010:00-11:40阜阳师范学院电子与通信工程表示成分数。）设个体域D＝{1,2},那么谓词公式)()(yyBxxA消去量词后的等值式为A(1)A(2)(B(1)B(2)).设P，Q是两个命题，当且仅当P，Q的真值均为1时，QP的值为1。(×)谓词公式A是qqp)(的代换实例，则A是重言式。(×)重言式的主析取范式包含了该公式的所有的极小项。(√)命题公式A→(B→C)与(A∧B)→C等价。(√)设A，B，C为命题公式，若,ABBC，则AC。(√)在一阶谓词公式中，同一变元符号不能够既约束出现又自由出现。(×)在一阶逻辑中，公式的前束范式是唯一的。(×)计算求命题公式(((p∨q)∧¬p)→q)∧r的主析取范式。答案：m1∨m3∨m5∨m7用等值演算法求公式(())PQRP的主析取范式，并由主析取范式求主合取范式。解：主析取范式：013(())()()()()()()()()PQRPPQRPPPQPRPPQRPQRPQRPQRmmm主合取范式为：24567MMMMM求公式（P∧Q）∨（﹁P∧R）的主析取范式，并由主析取范式求主合取范式。解：（P∧Q）∨（﹁P∧R）的真值表如下：PQRP∧Q﹁P∧R（P∧Q）∨（﹁P∧R）000001010011100101110000011000011000000101离散数学2014.1.1010:00-11:40阜阳师范学院电子与通信工程111101故主析取范式为：（﹁P∧﹁Q∧R）∨（﹁P∧Q∧R）∨（P∧Q∧﹁R）∨（P∧Q∧R）主合取范式为：（P∨R∨Q）∧（﹁Q∨P∨R）∧（﹁P∨Q∨R）∧（﹁P∨Q∨﹁R）化公式))]},(),((),([),(){(yxBxyAyyxByxyxyAx为前束范式。解：原式))]},(),((),([),({)(yxBxyAyyxByxyxyAx))]},(),((),([),(){(yxBxyAyyxByxyxyAx))]},(),((),([),(){(wuBuwAwvuBvuyxyAx))]},(),((),([),({wuBuwAvuBwvuyxAyx))]},(),((),([),({wuBuwAvuByxAwvuyx（或))]},(),((),([),({wuBuwAvuByxAwvuyx）证明构造下面推理的证明：任何自然数都是整数；存在着自然数。所以存在着整数。个体域为实数集合R。证明：先将原子命题符号化：设()Fx：x为自然数，()Gx：x为整数。则前提：(()())xFxGx，()xFx结论：()xGx①()xFx前提引入②()Fc①ES规则③(()())xFxGx前提引入④()()FcGc③US规则⑤()Gc②④假言推理离散数学2014.1.1010:00-11:40阜阳师范学院电子与通信工程⑥()xGx⑤EG规则用自然推理系统中，证明下列推理：(x)(A(x)→B(x))((x)A(x)→(x)B(x))证明：①(x)A(x)附加前提引入②A(c)①-③(x)(A(x)→B(x))前提引入④A(c)→B(c)③-⑤B(c)②④假言推理⑥(x)B(x)⑤⑦(x)A(x)→(x)B(x)①⑥CP规则⑧t⑤⑥假言推理在自然推理系统P中构造下面推理的证明：前提：qprqp,),(结论：sr所以(x)(A(x)→B(x))((x)A(x)→(x)B(x))判断下面推理是否正确，并证明你的结论。如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。证明：令p：他是计算机系本科生q：他是计算机系研究生r：他学过DELPHI语言s:他学过C++语言t:他会编程序前提：(p∨q)→(r∧s),(r∨s)→t结论：p→t证①p附加前提②p∨q①附加律③(p∨q)→(r∧s)前提引入④r∧s②③假言推理⑤r④化简律⑥r∨s⑤附加律⑦(r∨s)→t前提引入离散数学2014.1.1010:00-11:40阜阳师范学院电子与通信工程证明：○1)(rqp前提引入○2p前提引入○3rq○1○2假言推理○4q前提引入○5r○3○4假言推理○6sr○5附加律判断下面推理是否正确，并证明你的结论。如果小王今天家里有事，则他不会来开会。如果小张今天看到小王，则小王今天来开会了。小张今天看到小王。所以小王今天家里没事。解：设p:小王今天家里有事，q:小王来开会，r:小张今天看到小王本题推理的形式结构是：前提：pq,rq,r结论：p证明：1.rq前提引入2.r前提引入3.q1,2假言推理4.pq前提引入5.p3,4拒取式集合论部分选择、填空及判断设集合A={1,2,3,4},B＝{2,4,6,9}，那么集合A，B的对称差AB＝（C）.(A){1,3}(B){2,4,6}(C){1,3,6,9}(D){1,2,3,4,6,9}集合A={1,2,3,6}，A上的小于等于关系具有的性质是（D）。(A)自反的，对称的，传递的；(B)反自反的，对称的，传递的；(C)反自反的，反对称的，传递的；(D)自反的，反对称的，传递的。设A={a，b，c}，