数理逻辑部分。
选择、填空及判断。
下列语句不是命题的（ 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
谓词公式中，变元x是 ( b )
a. 自由变元 b. 既是自由变元也是约束变元
c. 约束变元 d. 既不是自由变元也不是约束变元。
命题公式p(qq)的类型是( a )。
a) 永真式b) 矛盾式。
c) 非永真式的可满足式 (d) 析取范式。
设b不含变元x，等值于( a )
a. b. c. d.
下列语句中是真命题的是( 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 qb) (p q r) (p q)
c) (p q r) (p q rd) (p q r) (p q r)
设个体域是整数集合，p代表xy((xy)(xyx))，下面描述正确的是（ c ）。
a) p是真命题b) p是假命题。
c) p是一阶逻辑公式，但不是命题 (d) p不是一阶逻辑公式。
对一阶逻辑公式的说法正确的是( 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 ）。
设是人，犯错误。
ab) c) (d)
下列命题公式等值的是（ c ）
给定命题公式：，则所有可能使它成真赋值为（ b ），成假赋值为（ c ）。
(a) 111，011；000b) 111，011，100，101，110；
c) 000，010，001d) 000，110，011，001，100。
给定前提：，则它的有效结论为：（ b ）。
(a) s； (b) ；c) p； (d) 。
命题：“所有的马都比某些牛跑得快”的符号化公式为：（ c ）。
假设：：x是马；：x是牛；：x比y跑得快。
(a) ；b) ；
c) ；d) 。
设p：a是偶数，q：b是偶数。r：a +b是偶数，则命题“若a是偶数，b是偶数，则a +b也是偶数”符号化为( c )．
a) pqr (b) pqr (c) pqr (d) pqr
表达式中的辖域是( 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的只含联结词和∧的等值式为：。
为假言推理规则。
在一阶逻辑中符号化命题“有会说话的机器人。”设m(x):x是机器人； s(x):x是会说话的；上述句子可符号化为： (x)(m(x)∧s(x))
设p:我们爬山，q:我们划船，在命题逻辑中，命题“我们不能既爬山又划船”的符号化形式为（p∧q
设p:小王走路，q:小王唱歌，在命题逻辑中，命题“小王边走路边唱歌”的符号化形式为 （p∧q
量词否定等值式。
设f(x):x是人，h(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为。
若含有n个命题变项的公式a是矛盾式，则a的主合取范式含 2n 个极小项。
取个体域为全体整数的集合，给出下列各公式：
其中公式 (1) 的真值为真，公式 (3) 的真值为假。
若含有n个命题变项的公式a是重言式，则a的主合取范式为 1或t 。
命题公式的所有成假赋值为 000,001,010 。
谓词公式的前束范式为。
在一阶逻辑中，将命题“没有不能表示成分数的有理数”符号化为。
或（设：x是有理数；：x能表示成分数。）
设个体域d＝,那么谓词公式消去量词后的等值式为 a(1)a(2)(b(1)b(2))
设p，q是两个命题，当且仅当p，q的真值均为1时，的值为1。(
谓词公式a是的代换实例，则a是重言式。
重言式的主析取范式包含了该公式的所有的极小项。
命题公式a→(b→c)与(a∧b)→c等价。
设a，b，c为命题公式，若，则。
在一阶谓词公式中，同一变元符号不能够既约束出现又自由出现。(
在一阶逻辑中，公式的前束范式是唯一的。
计算。求命题公式(((p∨q)∧p)→q)∧r的主析取范式。
答案：m1∨m3∨m5∨m7
用等值演算法求公式的主析取范式，并由主析取范式求主合取范式。
解：主析取范式：
主合取范式为：
求公式（p∧q）∨（p∧r）的主析取范式，并由主析取范式求主合取范式。
解：（p∧q）∨（p∧r）的真值表如下：
故主析取范式为：
﹁p∧﹁q∧r）∨（p∧q∧r）∨（p∧q∧﹁r）∨（p∧q∧r）
主合取范式为：
p∨r∨q）∧（q∨p∨r）∧（p∨q∨r）∧（p∨q∨﹁r）
化公式为前束范式。
解：原式。或）
证明。构造下面推理的证明：
任何自然数都是整数；存在着自然数。所以存在着整数。个体域为实数集合r。
证明：先将原子命题符号化：设：为自然数，：为整数。则。
前提：， 结论：
前提引入。es规则。
前提引入。
us规则。假言推理。
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(xcp规则。
所以 (x)(a(x)→b(x)) x)a(x)→(x)b(x))
判断下面推理是否正确，并证明你的结论。
如果他是计算机系本科生或者是计算机系研究生，那么他一定学过delphi语言而且学过c++语言。只要他学过delphi语言或者c++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。
请用命题逻辑推理方法，证明该推理的有效结论。
离散数学试卷A
2011 2012 课程名称 离散数学考试时间120分钟 一 填空题 每空2分，共16分 1 已知个体域是 p 1,1 1 p 1,2 1,p 2,1 0,p 2,2 0,则公式xy p x，y 的真值为。2 公式 x p x y q x,y 的前束范式为。3 设二元关系f g a 则fdom f。...
离散数学试卷
一 判断题。1.设g为无向图，若g中恰好n个结点，n 1条边，则g必为一棵树。2.若a b，则p a p b 3.设g为无向图，若g无回路，则g必为一棵树。4.设a，b是集合，若a b，则p a p b 5.无向图g是欧拉图当且仅当g连通且具有零个或两个奇数度结点。6.设a,b是任意集合，则 a b...
离散数学试卷 A
2014 2015学年第二学期。每题10分，共100分，答案一律写在答题纸上 1.化为主析取范式与主合取范式。2.证明 3.甲 乙 丙 丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的 1 甲和乙只有一人参加 2 丙参加，丁必参加 3 乙或丁至多参加一人 4 丁不参加，...