下载文档原格式
1-1，1-2（1）解：a)是命题，真值为T。
b)不是命题。
c)是命题，真值要根据具体情况确定。
d)不是命题。
e)是命题，真值为T。
f)是命题，真值为T。
g)是命题，真值为F。
h)不是命题。
i)不是命题。
（2）解：原子命题：我爱北京天安门。
复合命题：如果不是练健美操，我就出外旅游拉。
（3）解：a)(┓P ∧R)→Qb)Q→Rc)┓Pd)P→┓Q（4）解：a)设Q:我将去参加舞会。
R:我有时间。
P:天下雨。
Q↔ (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。
b)设R:我在看电视。
Q:我在吃苹果。
R∧Q:我在看电视边吃苹果。
c) 设Q:一个数是奇数。
R:一个数不能被2除。
（Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。
(5) 解：a)设P：王强身体很好。
Q：王强成绩很好。
P∧Qb)设P：小李看书。
Q：小李听音乐。
P∧Qc)设P：气候很好。
Q：气候很热。
P∨Qd)设P： a和b是偶数。
Q：a+b是偶数。
P→Qe)设P：四边形ABCD是平行四边形。
Q ：四边形ABCD的对边平行。
P↔Qf)设P：语法错误。
Q：程序错误。
R：停机。
（P∨ Q）→ R(6) 解：a)P:天气炎热。
Q:正在下雨。
P∧Qb)P:天气炎热。
R:湿度较低。
P∧Rc)R:天正在下雨。
S:湿度很高。
R∨Sd)A:刘英上山。
B:李进上山。
A∧Be)M:老王是革新者。
N:小李是革新者。
M∨Nf)L:你看电影。
M:我看电影。
┓L→┓Mg)P:我不看电视。
Q:我不外出。
R:我在睡觉。
P∧Q∧Rh)P:控制台打字机作输入设备。
Q:控制台打字机作输出设备。
P∧Q1-3（1）解：a)不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式）b)是合式公式c)不是合式公式（括弧不配对）d)不是合式公式（R和S之间缺少联结词）e)是合式公式。
（2）解：a）A是合式公式，(A∨B)是合式公式，(A→(A∨B))是合式公式。
第一章命题逻辑基本概念课后练习题答案1.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.2.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；3.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.4.因为p与q不能同时为真.5.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.返回第二章命题逻辑等值演算本章自测答案5.(1)：∨∨,成真赋值为00、10、11；(2)：0，矛盾式，无成真赋值；(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部为成真赋值；7.(1)：∨∨∨∨⇔∧∧；(2)：∨∨∨⇔∧∧∧；8.(1)：1⇔∨∨∨,重言式；(2)：∨⇔∨∨∨∨∨∨；(3)：∧∧∧∧∧∧∧⇔0，矛盾式.11.(1)：∨∨⇔∧∧∧∧；(2)：∨∨∨∨∨∨∨⇔1；(3)：0⇔∧∧∧.12.A⇔∧∧∧∧⇔∨∨.第三章命题逻辑的推理理论本章自测答案6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确(1)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*1)在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即(p→q)∧p→q ⇒ q(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*2)可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等(p→q)∧q→p⇔(┐p∨q) ∧q →p⇔q →p⇔┐p∨┐q⇔⇔∨∨从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.9.设p:a是奇数，q:a能被2整除，r:a：是偶数推理的形式结构为(p→q┐)∧(r→q)→(r→┐p) (记为*)可以用多种方法证明*为重言式，下面用等值演算法证明：(p→┐q)∧(r→q)→(r→┐p)⇔(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律)⇔(p∨q)∨(┐p∧r)∨┐q∨┐r⇔(┐p∨q)∨(┐q∧┐r)⇔┐p∨(q∨┐q)∧┐r⇔110.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.推理的形式结构为(p→q)∧┐p→(┐q∧┐r)⇔(┐p∨q) ∧┐p→(┐q∧┐r)⇔┐p→(┐q∧┐r) (使用了吸收律)⇔p∨(┐q∧┐r)⇔∨∨∨由于主析取范式中只含有5个W极小项，故推理不正确.11.略14.证明的命题序列可不惟一，下面对每一小题各给出一个证明① p→(q→r)前提引入② P前提引入③ q→r①②假言推理④ q前提引入⑤ r③④假言推理⑥ r∨s前提引入（2）证明：① ┐(p∧r)前提引入② ┐q∨┐r①置换③ r前提引入④ ┐q ②③析取三段论⑤ p→q前提引入⑥ ┐p④⑤拒取式（3）证明：① p→q前提引入② ┐q∨q①置换③ (┐p∨q)∧(┐p∨p) ②置换④ ┐p∨(q∧p③置换⑤ p→(p∨q) ④置换15.(1)证明：① S结论否定引入② S→P前提引入③ P①②假言推理④ P→(q→r)前提引入⑤ q→r③④假言推论⑥ q前提引入⑦ r⑤⑥假言推理（2）证明：① p附加前提引入② p∨q①附加③ (p∨q)→(r∧s)前提引入④ r∧s②③假言推理⑤ s④化简⑥ s∨t⑤附加⑦ (s∨t)→u前提引入⑧ u⑥⑦拒取式16.(1)证明：① p结论否定引入② p→ ┐q前提引入③ ┐q ①②假言推理④ ┐r∨q前提引入⑤ ┐r③④析取三段论⑥ r∧┐s前提引入⑦ r⑥化简⑧ ┐r∧r⑤⑦合取（2）证明：① ┐(r∨s)结论否定引入② ┐r∨┐s①置换③ ┐r②化简④ ┐s②化简⑤ p→r前提引入⑥ ┐p③⑤拒取式⑦ q→s前提引入⑧ ┐q④⑦拒取式⑨ ┐p∧┐q⑥⑧合取⑩ ┐(p∨q)⑨置换口p∨q前提引入⑾①口┐(p∨q) ∧(p∨q) ⑩口合取17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。
四川大学期末考试试题（闭卷）（2014-2015学年第1学期）课程号：304039040 课程名称：离散数学（A卷）任课教师：冯伟森石兵周莉陈瑜林兰适用专业年级： 2013级计算机科学与技术学号：姓名：一、单项选择题（本大题共16小题，每小题1分，共16分）提示：在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均无分1.令R: 小王吃饭；S：小王看电视。
则语句“小王一边吃饭一边看电视”可以符号化为（）。
（A)R∨S；（B）R∧S；（C）R→S；（D）～R∨～S2.令P(x):x是实数，Q(x):x是有理数。
则语句“并非每个实数都是有理数”可以符号化为（）。
（A）～∀x(R(x)→Q(x))；（B）～(R(x)→Q(x))；（C）～∀x(R(x)∧Q(x))；（D）～∀x(R(x)∨Q(x))3.下列公式中，（）是永真公式。
（A）R→S；（B）R∧～R；（C）R∨～R；（D）(R→S) ∧(R∧～S)4.下列公式中（）是等价公式。
（A）G∧(H∨S) ⇔ (G∨H) ∧(G∨S)；（B）G∧(H∨S) ⇔ (G∧H) ∧(G∧S)；（C）G∧(H∨S) ⇔ (G∧H)∨(G∧S)；（D）G∧(H∨S) ⇔ (G∨H) ∨(G∨S)；5.公式∀x((P(x)→Q(y，x))∧∃z R(y，z))→S(x)中，自由变元是( )。
（A）x和y ；（B）y和z；（C）x和z；（D）z或者y6.设集合A={1，2，3}，则A上所有非等价关系数目为（）。
（A） 512 (B) 507 (C) 508 (D) 5067.下列关于有限集偏序集〈A,≤〉的描述，（）是正确的(A) 一定存在最大元(B) 一定存在最小元(C) 任意两元素都存在最大下界 (D) 一定存在极大元8.下列说法不正确的是（）(A)任意两个非空集合之间都可构造函数(B) 任意两个非空集合之间都可构造单射函数(C) 任意两个非空集合之间都可构造满射函数(D) 任意两个非空集合之间如可构造单射函数，也可构造满射函数，那么一定可构造双射函数9.下列各组数中，不能构成无向图的点度数序列的是（）。
习题一1、利用逻辑联结词把下列命题翻译成符号逻辑形式（1）他既是本片的编剧，又是导演--- P∧ Q（2）银行利率一降低，股价随之上扬--- P→ Q（3）尽管银行利率降低，股价却没有上扬--- P∧ Q（4）占据空间的、有质量而且不断变化的对象称为物质--- M ←→(S∧P∧T)（5）他今天不是乘火车去北京，就是随旅行团去了九寨沟--- P▽ Q（6）小张身体单薄，但是极少生病，并且头脑好使--- P∧ Q ∧ R（7）不识庐山真面目，只缘身在此山中--- P→ Q （解释：因为身在此山中，所以不识庐山真面目）（8）两个三角形相似，当且仅当他们的对应角相等或者对应边成比例--- S ←→(E∨T)（9）如果一个整数能被6整除，那么它就能被2和3整除。
如果一个整数能被3整除，那么它的各位数字之和也能被3整除解：设 P –一个整数能被6整除Q –一个整数能被2整除 R –一个整数能被3整除S –一个整数各位数字之和能被3整除翻译为：（P→（Q ∧ R））∧（R→ S）2、判别下面各语句是否命题，如果是命题，说出它的真值（1）BASIC语言是最完美的程序设计语言--- Y，T/F（2）这件事大概是小王干的--- N（3）x2 = 64 --- N（4）可导的实函数都是连续函数--- Y，T/F（5）我们要发扬连续作战的作风，再接再厉，争取更大的胜利--- N（6）客观规律是不以人们意志为转移的--- Y，T（7）到2020年，中国的国民生产总值将赶上和超过美国--- Y，N/A（8）凡事都有例外--- Y，F3、构造下列公式的真值表，并由此判别哪些公式是永真式、矛盾式或可满足式（1）（P∨（～P∧ Q））→ Q解：（2）~（4）略4、利用真值表方法验证下列各式为永真式（1）~（8）略5、证明下列各等价式（1）～（（～P∧ Q）∨（～P∧～Q））∨（P∧ Q）⇔ P证明：左式⇔（（P∨～ Q）∧（P∨ Q））∨（P∧ Q）⇔ P ∨（P∧ Q）∨（P∧～Q）∨ T ∨（P∧ Q）⇔ P ⇔右式（2）（P→ Q）∧（R→ Q）⇔（P∨ R）→Q证明：左式⇔（～P∨Q）∧（～R∨Q）⇔（～P∧～R）∨Q⇔～（P∨ R）∨Q⇔（P∨ R）→Q ⇔右式（3）P→（Q∨ R）⇔（P→ Q）∨（P→ R）证明：左式⇔～P∨Q∨ R⇔～P∨Q∨～P∨ R⇔（～P∨Q）∨（～P∨ R）⇔（P→ Q）∨（P→ R）⇔右式（4）（P∧ Q）∨（R∧ Q）∨（R∧ P）⇔（P∨ Q）∧（R∨ Q）∧（R∨ P）证明：左式⇔(（P∨R）∧ Q）∨（R∧ P）⇔(（P∨R）∨R))∧(（P∨R）∨P))∧（Q∨R）∧（Q∨P）⇔（P∨ Q）∧（R∨ Q）∧（R∨ P）⇔右式6、如果P∨ Q ⇔ Q∨R,能否断定 P ⇔ R ？如果P∧ Q ⇔ Q∧R，能否断定 P ⇔ R？如果～P ⇔～R，能否断定 P ⇔ R？解：（1）如果P∨ Q ⇔Q∨R，不能判断P ⇔R，因为如果 Q = P∨ R, 那么P∨ Q⇔P ∨P∨ R ⇔ Q∨R，但P可以不等价于R.（2）如果P∧ Q ⇔Q∧R，不能判断P ⇔R，因为如果 Q = P∧ R, 那么P∧ Q⇔P ∧P∧ R ⇔ Q∧R，但P可以不等价于R.（3）如果～P ⇔～R，那么有P ⇔ R，因为～P ⇔～R，则～P <-> ～R为永真式，及有P <-> R为永真式，所以P ⇔ R.7、检查↑和↓是否满足结合率由上表可知，↓不满住结合率8、把下列各式用↑等价表示出来（1）(P∧Q)∨～P解：原式⇔ ((P↑Q)↑(P↑Q))∨(P↑P)⇔ (((P↑Q)↑(P↑Q))↑((P↑Q)↑(P↑Q)))↑((P↑P)↑(P↑P))（2）P→（～P→ Q）解：原式⇔～P∨P∨Q⇔ Q⇔ (Q↑Q)↑(Q↑Q)（3）（P→（Q ∨～R））∧～ P解：原式⇔（～ P∨～Q ∨R）∧～ P⇔～ P∨（～Q∧～ P）∨（R∧～ P）⇔ (P↑P)∨（(Q↑Q)∧(P↑P)）∨（R∧(P↑P)）⇔ (P↑P)∨（（(Q↑Q)↑(P↑P)）↑（(Q↑Q)↑(P↑P)））∨（（R↑(P↑P)）↑（R↑(P↑P)））设：(P↑P) = N（（(Q↑Q)↑(P↑P)）↑（(Q↑Q)↑(P↑P)））= L（（R↑(P↑P)）↑（R↑(P↑P)）） = M则上式⇔ (((N↑N)↑(L↑L))↑((N↑N)↑(L↑L)))↑(M↑M)（4）～ P∧～Q∧（～R→ P）解：原式⇔～ P∧～Q∧（R∨P）⇔ (P↑P)∧(Q↑Q)∧（(P↑P)↑(R↑R)）⇔ (（(P↑P)↑(Q↑Q)）↑（(P↑P)↑(Q↑Q)）)∧（(P↑P)↑(R↑R)）设：(（(P↑P)↑(Q↑Q)）↑（(P↑P)↑(Q↑Q)）) = N（(P↑P)↑(R↑R)） = M则上式⇔ (N↑M)↑(N↑M)9、证明：{ ～→}是最小功能完备集合证明: 因为{～,∨}是最小功能完备集合,所以,如果{ ～→}能表示出∨,则其是功能完备集合。
第一章部分课后习题参考答案16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。
（1）p∨(q∧r)⇔0∨(0∧1) ⇔0（2）（p↔r）∧(﹁q∨s) ⇔（0↔1）∧(1∨1) ⇔0∧1⇔0.（3）（⌝p∧⌝q∧r）↔(p∧q∧﹁r) ⇔（1∧1∧1）↔ (0∧0∧0)⇔0(4)（⌝r∧s）→(p∧⌝q) ⇔（0∧1）→(1∧0) ⇔0→0⇔117．判断下面一段论述是否为真：“π是无理数。
并且，如果3是无理数，则2也是无理数。
另外6能被2整除，6才能被4整除。
”答：p: π是无理数 1q: 3是无理数0r: 2是无理数 1s:6能被2整除 1t: 6能被4整除0命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。
19．用真值表判断下列公式的类型：（4）(p→q) →(⌝q→⌝p)（5）(p∧r) ↔(⌝p∧⌝q)（6）((p→q) ∧(q→r)) →(p→r)答：（4）p q p→q ⌝q ⌝p ⌝q→⌝p (p→q)→(⌝q→⌝p)0 0 1 1 1 1 10 1 1 0 1 1 11 0 0 1 0 0 11 1 1 0 0 1 1所以公式类型为永真式（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1) ⌝(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)⇔(⌝p∨(p∨q))∨(⌝p∨r)⇔⌝p∨p∨q∨r⇔1所以公式类型为永真式(3)P q r p∨q p∧r （p∨q）→(p∧r)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1所以公式类型为可满足式4.用等值演算法证明下面等值式：(2)(p→q)∧(p→r)⇔(p→(q∧r))(4)(p∧⌝q)∨(⌝p∧q)⇔(p∨q) ∧⌝(p∧q)证明（2）(p→q)∧(p→r)⇔ (⌝p∨q)∧(⌝p∨r)⇔⌝p∨(q∧r))⇔p→(q∧r)（4）(p∧⌝q)∨(⌝p∧q)⇔(p∨(⌝p∧q)) ∧(⌝q∨(⌝p∧q) ⇔(p∨⌝p)∧(p∨q)∧(⌝q∨⌝p) ∧(⌝q∨q)⇔1∧(p∨q)∧⌝(p∧q)∧1⇔(p∨q)∧⌝(p∧q)5.求下列公式的主析取范式与主合取范式，并求成真赋值(1)(⌝p→q)→(⌝q∨p)(2)⌝(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：（1）主析取范式(⌝p→q)→(⌝q∨p)⇔⌝(p ∨q)∨(⌝q ∨p)⇔(⌝p ∧⌝q)∨(⌝q ∨p)⇔ (⌝p ∧⌝q)∨(⌝q ∧p)∨(⌝q ∧⌝p)∨(p ∧q)∨(p ∧⌝q)⇔ (⌝p ∧⌝q)∨(p ∧⌝q)∨(p ∧q)⇔320m m m ∨∨⇔∑(0,2,3)主合取范式：(⌝p →q)→(⌝q ∨p)⇔⌝(p ∨q)∨(⌝q ∨p)⇔(⌝p ∧⌝q)∨(⌝q ∨p)⇔(⌝p ∨(⌝q ∨p))∧(⌝q ∨(⌝q ∨p))⇔1∧(p ∨⌝q)⇔(p ∨⌝q) ⇔ M 1⇔∏(1)(2) 主合取范式为：⌝(p →q)∧q ∧r ⇔⌝(⌝p ∨q)∧q ∧r⇔(p ∧⌝q)∧q ∧r ⇔0所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为 0(3)主合取范式为：(p ∨(q ∧r))→(p ∨q ∨r)⇔⌝(p ∨(q ∧r))→(p ∨q ∨r)⇔(⌝p ∧(⌝q ∨⌝r))∨(p ∨q ∨r)⇔(⌝p ∨(p ∨q ∨r))∧((⌝q ∨⌝r))∨(p ∨q ∨r))⇔1∧1⇔1所以该式为永真式.永真式的主合取范式为 1主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14. 在自然推理系统P中构造下面推理的证明：(2)前提：p→q,⌝(q∧r),r结论：⌝p(4)前提：q→p,q↔s,s↔t,t∧r结论：p∧q证明：（2）①⌝(q∧r) 前提引入②⌝q∨⌝r ①置换③q→⌝r ②蕴含等值式④r 前提引入⑤⌝q ③④拒取式⑥p→q 前提引入⑦￢p（3）⑤⑥拒取式证明（4）：①t∧r 前提引入②t ①化简律③q↔s 前提引入④s↔t 前提引入⑤q↔t ③④等价三段论⑥（q→t）∧(t→q) ⑤置换⑦（q→t）⑥化简⑧q ②⑥假言推理⑨q→p 前提引入⑩p ⑧⑨假言推理(11)p∧q ⑧⑩合取15在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p→(q→r),s→p,q结论：s→r证明①s 附加前提引入②s→p 前提引入③p ①②假言推理④p→(q→r) 前提引入⑤q→r ③④假言推理⑥q 前提引入⑦r ⑤⑥假言推理16在自然推理系统P中用归谬法证明下面各推理：(1)前提：p→⌝q,⌝r∨q,r∧⌝s结论：⌝p证明：①p 结论的否定引入②p→﹁q 前提引入③﹁q ①②假言推理④￢r∨q 前提引入⑤￢r ④化简律⑥r∧￢s 前提引入⑦r ⑥化简律⑧r∧﹁r ⑤⑦合取由于最后一步r∧﹁r 是矛盾式,所以推理正确.第四章部分课后习题参考答案3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:(1) 对于任意x,均有2=(x+)(x).(2) 存在x,使得x+5=9.其中(a)个体域为自然数集合.(b)个体域为实数集合.解：F(x): 2=(x+)(x).G(x): x+5=9.(1)在两个个体域中都解释为)∀，在（a）中为假命题，在(b)中为真命题。
