离散数学题库及答案
- 格式：doc
- 大小：1.14 MB
- 文档页数：20
数理逻辑部分
选择、填空及判断
✓ 下列语句不是命题的（ A ）。
(A) 你打算考硕士研究生吗？ (B) 太阳系以外的星球上有生物。
(C) 离散数学是计算机系的一门必修课。 (D) 雪是黑色的。
✓ 命题公式P(PP)的类型是（ A ）
(A) 永真式 (B) 矛盾式
(C) 非永真式的可满足式 (D) 析取范式
✓ A是重言式，那么A的否定式是( A )
A. 矛盾式 B. 重言式 C. 可满足式 D.不能确定
✓ 以下命题公式中，为永假式的是( C )
A. p→(p∨q∨r) B. (p→┐p)→┐p C. ┐(q→q)∧p D. ┐(q∨┐p)→(p∧┐p)
✓ 命题公式P→Q的成假赋值是( D )
A. 00,11 B. 00,01,11 C.10,11 D. 10
✓ 谓词公式),()(yxRxxP中，变元x是 ( B )
A. 自由变元 B. 既是自由变元也是约束变元
C. 约束变元 D. 既不是自由变元也不是约束变元
✓ 命题公式P(QQ)的类型是( 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∨q B. ﹁(p∨q) C. ﹁p∧q D. p→﹁q
✓ 一个公式在等价意义下，下面写法唯一的是( D )。
(A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式
✓ 下列含有命题p，q，r的公式中，是主析取范式的是 ( D )。
(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代表xy((xy)(xyx))，下面描述正确的是（ 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；
(C) ))),()(()((yxFyCyxHx； (D) ))),()(()((yxFyCxHxy。
✓ 设P：a是偶数，Q：b是偶数.R：a +b是偶数，则命题“若a是偶数，b是偶数，则a +b也是偶数”符号化为( C )．
(A) PQR (B) PQR (C) PQR (D) PQR
✓ 表达式))(),(())(),((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能表示成分数。）
✓ 设个体域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）的真值表如下：
P Q R P∧Q ﹁P∧R （P∧Q）∨（﹁P∧R）
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1 0 0 0
0 1 1
0 0 0
0 1 1
0 0 0
0 0 0
1 0 1
1 0 1
故主析取范式为：
（﹁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
