离散数学(第二版) 第一章、第二章习题 |
您所在的位置:网站首页 › 离散数学答案屈婉玲第二版 › 离散数学(第二版) 第一章、第二章习题 |
目录
第一章命题逻辑的基本概念习题 117 题 判断论述21 题 求下列公式的成假赋值29 题 简答题
第二章知识储备命题公式类型
习题二知识储备求下列公式的主析取范式,再用主析取范式求主合取范式.用主析取范式判断下列公式是否等值.简答题用消解法判断下列公式是否是可满足的.
第一章命题逻辑的基本概念
习题 1
17 题 判断论述
判断下面一段论述是否为真:“ π是无理数.并且如果3是无理数,则 2 \sqrt 2 2 另外 只有 6 能被 2 整除 ,6 才能被 4 整除.” 解答: p: π是无理数 1q: 3是无理数 0r: 2 \sqrt 2 2 是无理数 1s:6能被2整除 1t: 6能被4整除0命题符号化为:p∧(q→r)∧(t→s)的真值为1,所以这一段的论述为真。 21 题 求下列公式的成假赋值(格式丑字丑,见谅)由于是第一章节习题所以使用真值表进行计算 ┐(┐ p∧q)∧┐r(┐ q∨r)∧(p→q)(p→q)∧(┐(p∧r)∨p)![]() ![]() ![]() 设A,B都是含命题变项p1,p2,…pn的公式,已知A∨B是矛盾式,证明当且仅当A与B都是矛盾式。 第二章 知识储备 命题公式类型定义 2.10 设G为公式: (1) 如果G在所有解释下都是真的,则称G是恒真式(或称G是重言式,永真式); (2) 如果G在所有解释下都是假的,则称G是恒假式(或称G是矛盾式,永假式); (3) 如果G不是恒假的,则称G是可满足式。 注意: (1) 恒真公式的真值表的最后一列全为1,恒假公式的最后一列全为0,可满足公式的最后一列至少有一个1。 (2) 恒真公式一定是可满足的,可满足的不一定是恒真的。 习题二7、15、29、33 知识储备定义2.5 所有简单合取式,都是极小项的析取范式,称为主析取范式。 所有简单析取式,都是极大项的合取范式,称为主合取范式。 定理2.3(范式存在定理) 任何命题公式都存在与之等值的析取范式与合取范式。 (1) (p∧q)∨r (2) (p→q)∧(q→r) (1) 这里是解答 ⇔(p∧q∧(¬r∨r))∨((¬p∨p)∧(¬q∨q)∧r) 补项。 ⇔((p∧q∧¬r)∨(p∧q∧r))∨((¬p∨p)∧(¬q∨q)∧r) 分配律。 ⇔(p∧q∧¬r)∨(p∧q∧r)∨((¬p∨p)∧(¬q∨q)∧r) 结合律。 ⇔(p∧q∧¬r)∨(p∧q∧r)∨((¬p∧(¬q∨q)∧r)∨(p∧(¬q∨q)∧r)) 分配律。 ⇔(p∧q∧¬r)∨(p∧q∧r)∨(¬p∧(¬q∨q)∧r)∨(p∧(¬q∨q)∧r) 结合律。 ⇔(p∧q∧¬r)∨(p∧q∧r)∨((¬p∧¬q∧r)∨(¬p∧q∧r))∨(p∧(¬q∨q)∧r) 分配律。 ⇔(p∧q∧¬r)∨(p∧q∧r)∨(¬p∧¬q∧r)∨(¬p∧q∧r)∨(p∧(¬q∨q)∧r) 结合。 ⇔(p∧q∧¬r)∨(p∧q∧r)∨(¬p∧¬q∧r)∨(¬p∧q∧r)∨((p∧¬q∧r)∨(p∧q∧r)) 分配律。 ⇔(p∧q∧¬r)∨(p∧q∧r)∨(¬p∧¬q∧r)∨(¬p∧q∧r)∨(p∧¬q∧r)∨(p∧q∧r) 结合律。 ⇔(p∧q∧¬r)∨(¬p∧¬q∧r)∨(¬p∧q∧r)∨(p∧¬q∧r)∨(p∧q∧r) 等幂律。 m1∨m3∨m5∨m6∨m7 主析取式 m0∧m2∧m4主合取式 (2) 这里是解答 ⇔ (¬p∨q)∧(¬q∨r) ⇔ (¬p∨q∨(¬r∧r))∧((¬p∧p)∨¬q∨r) 补项 ⇔ ((¬p∨q∨¬r)∧(¬p∨q∨r))∧((¬p∧p)∨¬q∨r) 分配律 ⇔ (¬p∨q∨¬r)∧(¬p∨q∨r)∧((¬p∧p)∨¬q∨r) 结合律 ⇔ (¬p∨q∨¬r)∧(¬p∨q∨r)∧((¬p∨¬q∨r)∧(p∨¬q∨r)) 分配律 ⇔ (¬p∨q∨¬r)∧(¬p∨q∨r)∧(¬p∨¬q∨r)∧(p∨¬q∨r) 结合律 m1∧m2∧m3∧m5 主合取式 m0∨m4∨m6∨m7 主析取式 用主析取范式判断下列公式是否等值.(1) (p→q)→r与q→(p→r) (2) ┐(p∧q)与┐(p∨q) 因为任何命题公式的主析取范式都是唯一的,因而A与B等值,当且仅当A与B有相同的主析取范式和主合取范式. 设A= (p→q)→r,B=q→(p→r) 求解 A、B、C、D的主析取范式。 A=(p→q)→r ⇔(p∧┐q)∨r ⇔((P∧┐Q)∧(R∨┐R))∨(R∧(P∨┐P)∧(Q∨┐Q))) ⇔(P∧┐Q∧R)∨(P∧┐Q┐R)∨((R∧P)∨(R∧┐P))∧(Q∨┐Q)) ⇔(P∧┐Q∧R)∨(P∧┐Q┐R)∨(R∧P∧Q)∨(R∧P∧┐Q)∨ (R∧┐P∧Q)∨(R∧┐P∧┐Q) ⇔(P∧┐Q∧R)∨(P∧┐Q┐R)∨(P∧Q∧R)∨(P∧┐Q ∧R)∨ (┐P∧Q ∧R)∨(┐P∧┐Q∧R)(上式整理后) ⇔m1∨m3∨m4∨m5∨m7 B=q→(p→r) ⇔¬q∨¬p∨r ⇔¬p∨¬q∨r ⇔M6 ⇔m0∨m1∨m2∨m3∨m4∨m5∨m7 (1)(p→q)→r与q→(p→r)不等值 简答题在某班班委成员的选举中,已知王小红、李强、丁金生 位同学被选迸了班委会该班的甲 .乙,丙三名学生预言如下. 甲说:王小红为班长,李强为生活委员. 乙说:丁金生为班长,王小红为生活委员 丙说:李强为班长,王小红为学习委员. 班委会分工名单公布后发现,甲 、乙,丙 三人都恰好猜对了一半. 问:王小红、李强、 金生各任何职(用等值等演求解)? 设命题 a:王小红为班长 b:李强为生活委员 c:丁金生为班长 d:王小红为生活委员 e:李强为班长 f:王小红为学习委员 则 a,b当中有且只有1个为真, 即a∧b=F,a∨b=T c,d当中有且只有1个为真, 即c∧d=F,c∨d=T e,f当中有且只有1个为真, 即e∧f=F,e∨f=T 又因为a,d,f三个命题当中,有且只有1个为真(王小红只有1个职务),即 (a∧c∧e)∨(b∧d∧e)∨(b∧c∧f)=T ① (枚举3种情况,然后析取) 而b,d不可能同时为真(生活委员只有1个),即b∧d=F 则根据①,化简得 (a∧c∧e)∨(b∧c∧f)=T ② 而a,c,e三个命题当中,也有且只有1个为真(班长只有1个),即 a∧c∧e=F,代入②,得到 b∧c∧f=T 从而 b=c=f=T 即 李强为生活委员, 丁金生为班长, 王小红为学习委员 用消解法判断下列公式是否是可满足的.(1)p∧(┐p∨┐q)∧q (2)(p∨q)∧(p∨┐q)∧(┐p∨r)
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |