君，已阅读到文档的结尾了呢~~
离散数学(命题逻辑),命题逻辑,数理逻辑 永真命题,命题逻辑连接符,命题逻辑的公理化,离散数学,离散数学及其应用,离散数学答案,离散数学 pdf,离散数学左孝凌答案
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
离散数学(命题逻辑)
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
主析取范式的求法
下载积分：2000
内容提示：主析取范式的求法
文档格式：PPT|
浏览次数：40|
上传日期： 16:15:07|
文档星级：
全文阅读已结束，如果下载本文需要使用
 2000 积分
下载此文档
该用户还上传了这些文档
主析取范式的求法
官方公共微信我的图书馆
1.1 命题与命题联结词
(Proposition)
“”
(Truth Value)“”“”(True Proposition)“”“”(False Proposition)
“”“”
“”
1.1-11.1-2(Atomic Proposition)(Compoud Proposition)
(Logical Connective)
(Negation)
1.1-1 p“ p” p
p3p p0 1
(Truth Table)
1.1-1
(Conjunction)
1.1-2 pq“pq”pq
 pq1 1
(Disjunction)
1.1-3 pq“pq”pq
pq“”
()Implication
1.1-4 pqpqpq pq
pq“” pq
(Equivalent)
1.1-5 pq“pq”pq
pq“”
(Proporsitional signify)
1.1-5 p2+3=5q &#=5”pq
1.1-3r&#&4”s“” r
“”“”“”“”
“”“”
“”“” “”
“”“”pq
“”r
pq01+10=11r
pq1 0 01 pq10 1 0 00
⑶你说什么？
⑷今天天气多好呀！
⑸我明天或者后天去郑州。
⑹我明天去郑州或后天去郑州是谣传。
⑺一个整数为偶数当且仅当它能被2整除。
⑻这个命题是假的。
⑼太阳是不会发光的。
2.判断下列语句是否是命题，为什么？若是命题判断是原子命题还是复合命题，并把复合命题符号化，要求符号化到原子命题。
⑴他们明天或者后天去百货公司。
⑵你能告诉我我什么时候一定会死吗？你不能！
⑶如果这个语句是命题，那么它就是个假命题。
⑷李刚和李春是兄弟。
⑸王海和李春在学习。
⑹只要努力学习，就一定能取得优异成绩。
⑺李春对李刚说：“今天天气真好呀！”
⑻如果你想中奖，你就得买奖券；如果你买奖券，你就可能中奖。
⑼你知道这个是真命题还是假命题就请告诉我！
⑽王海不是女孩子。
3.设表示命题“李春迟到了”，表示命题“李春错过了考试”，表示命题“李春通过了考试”。请将下列命题翻译成自然语言（汉语）。
⑴ ；⑵ ；⑶ ；⑷ 。
4.设表示命题“天下大雨”，表示命题“他乘公共汽车上班”，表示命题“他骑自行车上班”。请将下列命题符号化。
⑴如果天不下大雨，他乘公共汽车上班或者骑自行车上班。
⑵只要天下大雨，他就乘公共汽车上班。
⑶只有天下大雨，他才乘公共汽车上班。
⑷除非天下大雨，否则他不乘公共汽车上班。
1.2 命题公式及其分类
1.1-1 xyxy
(Propositional Variable)10(Propositional Constant)p,q,r,…
1.2-1 01……等
(Propositional Formula)
(True value assignment)A(Value assignment)(Explanation)使1为公式AA0为公式A
001p1,p2,p30,0, 01p1,p20, 1101100
(2n)000111
，计算公式AA
A下取值均为真，则称A(Tautology)
A下取值均为假，则称A(Contradiction)
A是成真赋值，则称A(Contingency)
A1AA1.2-1A0AA1.2-1A01A赋值，即公式A1.2-1
1.3 等值演算
n ( )和最终一列来讲，这些真值表有许多其实是相类同的。如
1.3-1 AB AB(Logical Equivalence)
下，填入值均对应相同，可得到
&&&&&&&&&& &&&&&&&
&&&&&&&&&&&&&& &&&&&&&
&&&&&& &&&&&&&&&&
&& &&&&&&&&&&&& &&&&&&&&&&&
&&&&&&&&&&&& &&&&&&&&&&
&&&&&&&&&&&&&&
&&&&& (•)
&&&&&&& ()
&&&&&&&&&&& &
&&&&&&&&&&&&&& &
&&&&&&&&&&& &
&&&&&&&&&&&&&&&& &
&&&&&&&&&&&&& &&&•
&&&&&&&&&&&&&&&& &&
&&&&&&&&&&&&&&&&&&&&&& &&
&&&&&&&&&&&&&&&&&&&&&&&&&& &&&
&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&
1.3-5 if A then if B then X else Y else if B then X else Y
[(()())][(()())]
if B then X else Y
*1.4 其他联结词及功能完备集
1.4-1 “ &#-1
“ ”
“ ”
1.4-2 “ &#-2 pq
“ ”
“ ”
1.4-3 “ &#-3 pq
“ ”“ ”
“”
“”“”“”“”
1.1 “ ”“ ”“ ”“ ”“ ”“ ”“ ”“ ”
}{ }{ }{ }
“ ”“ ”“ ”“”“”
1.4-3 { }{ }
1.5 对偶与范式
1.5-1 A“ ”“ ”“ ”“ &#AA*
A*AAA*A**=A
1.5-1 AA*p1p2…pnAA*AA*n
⇔ A*
1.5-1 ⇔ A* ⇔
⇔ ⇔ ⇔
1.5-2 AB A* B*,A* B*AB
A(p1p2pn)⇔ B(p1p2pn)
A(p1p2pn)⇔ B(p1p2pn)
A(p1p2pn)⇔A*
A* ⇔ B*
A* ⇔ B*
1.5-2(Atomic Conjunctive Form)
(Atomic Disjunctive Form)
1.5-3(Disjunctive Normal Form)
(Conjunctive Normal Form)
①pq⇔pq②p q⇔(pq)(pq)
(p)⇔p
(pq), (pq)
①(pq)⇔pq②(pq)⇔pq
“”“”, “”“”
1.5-3 ((pq)r)p
((pq)r)p⇔((pq)r)p⇔((pq)r)p
⇔(pr)(qr)p
⇔p(pr)(qr)⇔p(qr)
((pq)r)p⇔((pq)r)p
⇔(pqp)(rp)
(pqp)(rp)⇔(pq)(rp)
n2nm0m1…
1.5-5 &AA(Principal Disjunctive Normal Form)
1.5-3 ⇔
⇔m4 m5 m6 m7 m2 m6⇔m2 m4 m5 m6 m7
01111m0m1m3A
001011101110111m1m3m5m6m7 ⇔m1 m3 m5 m6 m7⇔(13567)
AnAA2nAAA0AA
n2n01n=21.5-3
1.5-7 A(Principal Conjunctive Normal Form)
⇔M0 M2 M4⇔024
⇔m1m3m5m6m7
1.5-4 m2 m4 m5 m6 m7
1.6 推理理论
A1A2ABB{A1A2A(Logical consequence)
“ ”“ ”“ ”“ ”
⇔ ⇔
⇔ ⇔11⇔1
⇔1⇔0123
1. &&&&&&&&&&&&&&&&&&&&&&&&&&&附加
2. &&&&&&&&&&&&&&&&&&&&&&&&&&&附加
3. &&&&&&&&&&&&&&&&&&&&&&&&&&&化简
4. &&&&&&&&&&&&&&&&&&&&&&&&&&&化简
9. &&&&&&&&&&&&&&&&&&&&&&&&&&&合取
10. &&&&&&&&&&&&&&&&&&&&&
11. &&&&&&&&&&&&&&&&&&
12. &&&&&&&&&&&&&&&&&&&&&&
13. &&&&&&&&&&&
&&&&&&&&&&&&&&&&&&& P
&&&&&&&&&&&&&&&&&&&&&& P
&&&&&&&&&&&&&&&&&&&&& T
&&&&&&&&&&&&&&&&& P
&&& &r&&&&&&&&&&&&&&&&&&&&&&&& T
& &&&&&&&&&&&&&&&&P
&&&&&&&&&&&&&&&&&&&&& &T
&&&&&&&&&&&&&&&&&& &&P
&&&& q&&&&&&&&&&&&&&&&&&&&&& &&&T⑦
&&&&&&&&& &&&&&&&&&P
p&&&&&&&&&&&&&&&&&&&&& &&&&&&&&P
&&&&&&&&&&&&&&&&&& &&&&&&T
&&&&&&&&&&&&&&& &&&&&&&P
&&&&& s&&&&&&&&&&&&&&&&&&&&& &&&&&&&&P
&&&&&&&&&&&&&&&&&&&& &&&&&&T
&&&&& r &&&&&&&&&&&&&&&&&&&&&&&&&&&&&T
s &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&& &&&&&&
p &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&& &&&&&&&&
&&&&&&&&&&&& &&&&&&&&&&&&&&&
q &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
r &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&& &&&&&&&&CP
A1A2AkkA1 A2
AkA1A2AkA1A2AkA1A2Ak
&&&&&&& &&P
&&&& p&&&&&&&&&&&&&&&&&&&&&&&&&&&& &P
&&&&&&&&&&&&&&& T
&&&&&&&&&&&&&&&&&&&&&& &P
&&&&&&&&&&&&&&&&&&&&&&& &&T
&&&& s&&&&&&&&&&&&&&&&&&&&&&&&&& &&&T
&&&&&&&&&&&&&&&&&&&&&&&&&&&P
&&&&&&&&&&&&&&&&&&&& &&&T⑥
前提：⑴如果这里有演出，则通行是困难的；
⑵如果他们按照指定的时间到达，则通行是不困难的；
⑶他们按照指定时间到达了。
结论：这里没有演出。
1.6-2.形式证明给出下列推理的过程的形式证明。
1.6-3.下面的推理过程是否正确，结论是否有效，并说明理由。
① &&&&&&&&&&&&&&&&&&&&&&&&&&& P前提引入
② &&&&&&&&&&&&&&&&&&&&&&&&&&&&&& T ①化简
③ &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& P前提引入
④ &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& T ②③假言推理
证明：① &&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&⑴
&&&&& ② &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &⑵
&③ &&&&&&&&&&&&&&& &&&&&&&&&&&&&&&&&&&&⑶
&&&& ④ &&&&&&&&&&&&&&&&&&&&&&&&&⑷
⑤ & &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&⑸
&⑥ &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &⑹
&⑦ &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &⑺
⑧ &&&&&&&&&&&&&&&&&& &&&&&&&&&&&&&⑻
1.6-5.用推理规则证明下列推理的正确性：如果张三努力工作，那么李四或王五感到高兴；如果李四感到高兴，那么张三不努力工作；如果刘强高兴，那么王五不高兴。所以，如果张三努力工作，则刘强不高兴。
1.6-6.已知事实如下，问结论是否有效。
前提：⑴如果天下雪，则马路就会结冰；
⑵如果马路结冰，汽车就不会开快；
⑶如果汽车开得不快，马路上就会塞车；
⑷马路上没有塞车。
结论：天没有下雪。
1.7 * 命题逻辑在门电路中的应用介绍
“”“”“”“”“”“”“ ”“ ”“ ”“”“&#-1
p p⇒L1& q q ⇒L2
r r⇒L3
r⇔ ⇔ 1.7-2
1.8& 例题解析
“……”“……”“……”
&&& &&& &&&
M0M1M3M4004
A & B & C && D
“ ”“ ”“ ”“ ”“  ”“ ”“ ”
解 p q rst
&&&&&&&&&&&&&&&&&&&&&&&&& P
&&&&&&&&&&&&&&&&&&&&&&&& &&&P
&&&&&&&&&&&&&&&&&&&&&&&&& &&T
&&&&&&&&&&&&&&&&&&&&& &&P
r&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&T
&&&& &&&&&&&&&&&&&&&&&&&P
&&&&&&&&&&&&&&&&&&&&&&&&&& &T
&&&&&&&&&&&&&&&&&&&&&&& &&P
q&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&T
&&&&&&&&&&&&&&&&&&&& P
&&&&&&&&&&&&&&&&&&&&& P
&&&&&&&& &&&&&&&&&&&&T
& &&&&&&&&&&&&&&&&T
&&&&&&&&&&&&&&&& T
&&&&&&&&&&&&&&&&&&&&& T
&&&&&&&& &&&&&&&&&T
&&&&& &&&&&&&&&&&T
&&&&&&&&&&&&&&&&& &&&&&P
&&&&&&&&&&&&&&&&&&&& &&P
⑴中国有四大发明。
⑵吸烟请到吸烟室去！
⑶ 是无理数！
⑷李春和李红是姐妹。
⑸李春在说谎。
⑹如果3是偶数，那么中国人的母语是汉语。
⑺只要你抽烟，你就很容易得病。
⑻只有今天是星期一，明天才是星期二。
⑼李春这个学期《离散数学》和《数据结构》都考了100分。
⑽下雪路滑，他迟到了。
⑾不经一事，不长一智。
⑿一朝被蛇咬，十年怕井绳。
⑵写出与等值的主析取范式和主合取范式；
⑶写出与等值的析取范式的最简形式。
8.证明下列推理。
⑵前提： ， ， ， ，
⑶ ， ， 。
9.用推理规则说明：
， ， 是否能同时成立。
10.用真值表、等值演算、求主范式和构造推理证明下面的推理正确。
只要小王曾经到过受害人的房间并且11点以前没有离开，小王就犯了谋杀罪。小王曾经到过受害者房间。如果小王在1点以前离开，看门人会看到他。看门人没有看到他。所以小王犯了谋杀罪。
TA的推荐TA的最新馆藏[转]&[转]&[转]&[转]&[转]&
喜欢该文的人也喜欢主析取范式/主析取范式
主析取范式主析取范式是大学数学里一门名叫离散数学（Discrete mathematics）的课程中的内容，在离散数学的数理逻辑一节中，利用真值表和等值演算法可以化简或推证一些命题，但是当命题的变元的数目较多时，上述方法都显得不方便，所以需要给出把命题公式规范的方法，即把命题公式化成主合取范式和主析取范式的方法。
内容简介/主析取范式
析取范式(DNF)是逻辑公式的标准化（或规范化），它是合取子句的析取。作为规范形式，它在自动定理证明中有用。一个逻辑公式被认为是 DNF 的，当且仅当它是一个或多个文字的一个或多个合取的析取。同合取范式（CNF）一样，在 DNF 中的命题算子是与、或和非。非算子只能用做文字的一部分，这意味着它只能领先于命题变量。
基本内容/主析取范式
本节给出含n个命题变项的公式的两种规范表示方法。要求: 了解简单析取式、简单合取式、析取范式、合取范式的概念 深刻理解极小项、极大项的定义，名称、下角标与成真(假)赋值的关系 熟练掌握求主析取(主合取)范式的方法。 会用主析取范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值。一、析取范式与合取范式定义2.2 命题变项及其否定统称作文字。 仅由有限个文字构成的析取式称为简单析取式。仅由有限个文字构成的合取式称为简单合取式。例如，文字：p,┐q,r,q.简单析取式: p,q,p∨q,p∨┐p∨r,┐p∨q∨┐r.简单合取式: p,┐r,┐p∧r,┐p∧q∧r,p∧q∧┐q.定理2.1（1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定。（2）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定。定义2.3（1）由有限个简单合取式构成的析取式称为析取范式。（2）由有限个简单析取式构成的合取式称为合取范式。（3）析取范式与合取范式统称为范式。例如，析取范式：（p┐∧q）∨r, ┐p∧q∧r, p∨┐q∨r.合取范式:(p∨q∨r)∧(┐q∨r), ┐p∧q∧r, p∨┐q∨r.定理2.2（1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。（2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。范式的特点：（1） 范式中不出现联结词→、←;，求范式时可消去：A→B↔┐A∨BA←B↔(┐A∨B)∧(A∨┐B)（2）范式中不出现如下形式的公式：┐┐A, ┐(A∧B), ┐(A∨B)因为：┐┐A↔A┐(A∧B)↔┐A∨┐B┐(A∨B)↔┐A∧┐B（3）在析取范式中不出现如下形式的公式：A∧(B∨C)在合取范式中不出现如下形式的公式：A∨(B∧C)因为：A∧(B∨C)↔(A∧B)∨(A∧C)A∨(B∧C)↔(A∨B)∧(A∨C)定理2.3 (范式存在定理)任一命题公式都存在着与之等值的析取范式与合取范式。求范式的步骤：1．消去联结词→、←；2．消去否定号┐；3．利用分配律。命题公式的析取范式与合取范式都不是唯一的。例2.7 求公式(p→q)↔r的析取范式与合取范式。解: (1)合取范式：(p→q)↔r＝(┐p∨q)↔ r＝ ((┐p∨q)→ r)∧(r→(┐p∨q))＝(┐(┐p∨q)∨r)∧(┐r∨(┐p∨q))＝ ((p∧┐q)∨r)∧(┐p∨q∨┐r)＝ (p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)(2) 析取范式(p→q)↔r＝((p∧┐q)∨r)∧(┐p∨q∨┐r)＝ (p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r)∨(r∧┐p)∨(r∧q)∨(r∧┐r)＝(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)下面介绍命题公式的唯一规范化形式的范式：主析取范式与主合取范式。二、主析取范式定义：对于给定的命题公式A（P1，P2，P3，……，Pn），如果有一个仅由最小项的析取构成的身先士等值式称为原命题公式的主析取范式。定理：任意含n个命题变元的非永假式，其主析取范式是惟一的。证明：（反正法）假设非永假式A（P1，P2，P3，……，Pn）有两个不同的主析取范式A1和A2则AA1,AA2,故A1A2,由于A1和A2是两个不同的主析取范式故，至少存在一最小项mi，是mi只存在于A1和A2两者之一中，不妨设mi在A1中，而不再A2中。设mi在A1中有一组成真指派R，于是在R指派下，主析取范式A1为真，但在R指派情况下，主析取范式A2为假，这与A1 A2相矛盾。——证毕
&|&相关影像
互动百科的词条（含所附图片）系由网友上传，如果涉嫌侵权，请与客服联系，我们将按照法律之相关规定及时进行处理。未经许可，禁止商业网站等复制、抓取本站内容；合理使用者，请注明来源于。
登录后使用互动百科的服务，将会得到个性化的提示和帮助，还有机会和专业认证智愿者沟通。
此词条还可添加&
编辑次数：6次
参与编辑人数：6位
最近更新时间： 03:10:45
申请可获得以下专属权利：
贡献光荣榜