Download presentation
Presentation is loading. Please wait.
1
第一章 命题逻辑 杨圣洪 yangshenghong8@tom.com 13007432216 346260267(qq)-81968986
Kczx.hnu.cn 课程网站点击排行-更多-离散数学
2
离散数学有何用？: 1．计算机的基础是0-1组成的2进制. 0-false,1-true 2进制-布尔代数即命题逻辑
George Boole 19世纪 英国数学老师，它首次将数学与逻辑联系起来。 1938 香农在其硕士论文中用布尔代数实现开关电路，布尔代数(命题逻辑)成为数字电路基础 由于所有内容(整数，实数，字符，汉字，图片，声音，视频，网页，……)进入电脑后，全是01组成的字符串，从而都可以用布尔运算即逻辑运算实现，命题逻辑成为计算机的基础。 命题逻辑将数学由连续变到离散，由高数进入离散。 Google采用逻辑运算进行搜索： 杨圣洪 两者对应位置与运算。 离散数学 逻辑运算 1秒10亿
3
离散数学有何用？: 2．七桥问题，可用于网络爬虫去搜索下载网页. 图中ABCD看成网站，桥就是“超链接”。 图论是离散数学非常重要的内容。
通过互联网或图书馆,查看离散数学与计算机哪些课程相关，数字电路设计，计算理论，数据库，编译原理，操作系统，体系结构……，所有计算机专业。
4
目的: 1．掌握离散数学四大核心内容（集合论、数理逻辑、代数结构、图论）的基本概念、基本理论、基本方法，训练提高学生的概括抽象能力、逻辑思维能力、归纳构造能力，培养学生严谨、完整、规范的科学态度和学习思维习惯。 2．通过课程实验的训练，应用所学理论锻炼学生在数学建模、设计算法、编写程序和调试方面的能力。 思考: 通过互联网或图书馆,查看离散数学与计算机哪些课程相关，数字电路设计，计算理论，数据库，编译原理，操作系统，体系结构……，写小论文。
5
学习方法: 1．勤查资料掌握每章的发展历史，与其他课程的横向联系，想明白为什么要学这些内容，在整个 计算机学科中处于什么位置—用途？ 2、提高听堂效率，课后立马看懂例题，争取当日做完习题，不过23点，越拖越学不下去。 3、勤于用程序解题，解能解之题！写程序是将你的算法，告诉计算机，让电脑解放人脑，你会发现电脑真的好蠢！人脑想办法让脑聪明起来。 4、多交流，同一道较难的题，往往有多种解法，有这本书的，其那本书的，有我的，有你的，有他的。
6
考核方法: 总评成绩= 25%*各章考试。5分*5次，随堂考，中考 12%*程序设计。2分*6次，不怕打断腿！ 10%*小班讨论。2分*5次 8%*作业 。 分*8次，下次上课前交 5%*考勤 分*5次 40%*期末考试 总之，平常不努力，单凭期末一次肯定不行！ 分数随时公布在kczx.hnu.cn 答疑：QQ群！ ，课程中心提问
7
引言 逻辑学是推理的基础，在社会学、自然科学尤其计算机学科中得到普遍应用。 数理逻辑是逻辑学的一个分支，也是数学的分支，它用数学方法研究推理规律，它采用符号的方法来描述和处理思维形式、思维过程和思维规律，它在程序设计、数字电路设计、计算机原理、人工智能等计算机课程得到了广泛应用。 命题逻辑是数理逻辑的基础部分， 但究竟什么是命题？ 如何表示命题？ 如何构造出复杂的命题？ 在本章将讨论这些问题。
8
1.1 命题及联结词 对错确定的陈述语句称为命题。如： (1)湖南大学是985学校。 (2)命题逻辑是计算机科学的基础课程。
(3)命题逻辑的数字电路的基础。 (4)4是素数。 (5)湖南大学坐落于湘江以东。 (6)2014年湖南大学游泳馆建成。 其中(1)、(2)、(3) 与事实相符，是对的、正确的，称为真命题，或者称命题的值为“真”，简记为T或数字1。 而(4)、(5)明显与事实不相符，是错的、不正确，称为假命题，或称命题的值为“假”，简记为F或数字0。 陈述句(6)的正确性，到2014年12月时能确定的，若届时开通了则它是对的、为真命题，否为假命题。
9
1.1 命题及联结词 对错确定的陈述语句称为命题。如： (7) x与y之和为100，其中x为整数，y为整数 (8)1加1等于10
(8)的对错是不确定的，为二进制时正确，当为八进制、十进制时是错的，因此这两个陈述句不是命题。 (9)青枫峡的红叶真美呀！ (10)动作快点！ (11)你是杨老师吗？ 这三个语句不是陈述语句，因此不是命题。
10
1.1 命题及联结词 对错确定的陈述语句称为命题。如： (12)我在说假话。 (13)派出所说:必须先房子再能上户口
单位后勤说:必须先有户口才能分房 你能上到户口与要到房子吗? 这些是悖论，其真值不能确定，故不是命题。。
11
1.1 命题及联结词 对错确定的陈述语句称为命题。如： (12)我在说假话。 (13)派出所说:必须先房子再能上户口
单位后勤说:必须先有户口才能分房 你能上到户口与要到房子吗? 某市仅一位理发师，“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！” 有一天理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，能给他自己刮脸呢？ 若不刮自己，属于“不给自己刮脸的人”，他就要给自己刮脸， 真给自己刮脸呢？根据其所订规矩，不给自己刮。
12
1.1 命题及联结词 对错确定的陈述语句称为命题。如： (13)我既要学程序设计，又要学离散数学。
(14)我们早餐在公寓食堂或外面早点摊上吃。 (15)我不是数学院的学生 这三个陈述句都与事实相符，是对的，是真命题，其值为真(T/1)。 其中(13)与(14)可分解为另外二句话的组合， 而(15)是对“我是数学院学生”的否定，这些语句称为“复合命题”，不能再分解的语句称为“简单命题”或“原子命题”，为了便于推理与书写，常用小写字母表示简单命题或原子命题。
13
1.1 命题及联结词 next 简单命题组合成复杂命题时所使用的辅助词称为“联结词”。 命题逻辑中的联结词归纳为以下5种。
合取：C语言中 && and 并且 析取：C语言中 || or 或 否定：C语言中 ! not 非,不是,否定 条件式：C语言中 if () 如果…那么 若p则q 双条件式： 若p则q且若q则p,当且仅当
14
1.1 命题及联结词 定义1.1合取： 当p、q都对，即取值为真(T或1)时，“p合取q”的值为真.
15
1.1 命题及联结词 定义1.1合取： 当p、q都对，都为真(T或1)时，“p合取q”的值为真，其他情况为假。
逻辑运算符“合取”，与汉语中“并且、而且、同时”含义相当
16
1.1 命题及联结词 定义1.2析取： 当p、q都不对，都为假(F或0)时，“p析取q”的值为假，其他情况为真。
逻辑运算符“析取”，与汉语中“或”含义相当，但有细微的区别
17
1.1 命题及联结词 运算符“析取” 与汉语的“或”几乎一致但有区别：哪些老师讲离散数学？有人回答如下： (16)“讲离散数学的老师是杨老师或刘老师”， 分解为 “讲离散数学的老师是杨老师”或 “讲离散数学的老师是刘老师”， 这两个原子命题有可能都是对的， 这种“或”称为“可同时为真的或”， 或简称为“可兼或”。 这种“或”表示可表 示为“析取”
18
1.1 命题及联结词 运算符“析取” 与汉语的“或”几乎一致但有区别： (17)“星期二的离散数学的教室是202或204”， 分解为“星期二的离散数学教室是202”或 “星期二的离散数学教室是204”， 因为这两个原子命题不可能都对， 只能这二种情况之一，这种“或”称为 “不可同时为真的或”，或简称为 “不可兼或”、“排斥或”. 这种“或”表示不能简单表 示为“析取”，
19
1.1 命题及联结词 定义1.3否定:当p是1 ，p的否定p即为0。 逻辑运算符“否定”，与汉语中“否定”含义相当.
“我不是数学院的学生”可表示为“我是数学院的学生” “离散数学的教室是202或204”,表示 离散数学的教室是202不是204" 或 “离散数学的教室不是202是204" p:离散数学的教室是202 q:离散数学的教室是204 上面的语句表示: (pq)(pq)
20
1.1 命题及联结词 定义1.4条件:当p是1 ,q是0时,pq为0,即10为0,其他情况为1。 逻辑运算符“如果…那么”，
如老妈说：“如果期终考了年级前10名，那么奖励1000元”。 p:期终考了年级前10名 q:奖励1000元 则上面的语句表示为pq。 先考虑值为0即假的情况： 当p为1即“期终考了年级前10”， 且q为0即“没有奖励1000元” 这时老妈的话是假话空话， 故pq为0
21
1.1 命题及联结词 定义1.4条件式当p是1 ,q是0时,pq为0,即10为0,其他情况为1。 p称为前件,q称为后件
22
1.1 命题及联结词 定义1.5双条件:当p与q值相同时,pq为1,不同为0。 称p与q的等价式
“我赚了100万当且仅当我买彩票中了大奖”， 可以表示为“我赚了100万我买彩票中了大奖” 这个例题有点不正点！ “郎才当且仅当女貌”， 可以表示为“郎才女貌”
23
1.2命题公式 对错明确的陈述语句称为命题，其真值确定，又称为命题常元或命题常项，相当于 “常数”。
数学运算：加+、减-、乘x、除、幂”， 命题逻辑：合、析、否定、条件、双条件 数学中用变量x表示某些数，如x2+x+10是代数式， 用变量p,q,r表示任意命题，由命题常元与此类变量所构成表达式，称为“命题公式”。 代数式有规律， 命题公式也有规律与约束， 满足规则的公式为“合式公式”，简称为“公式”。
24
1.2合法公式命题公式 定义1.2.1 合式公式的生成(组合)规则 (1)单个命题变元、命题常元为合式公式(原子公式)。
(2)若A是合式公式，则A、(A)也是合式公式。 (3)若A、B是合式公式，则AB、AB、AB、AB是合式公式。 (4)有限次使用(2)~(3)形成的字符串均为合式公式。 如：(p1)q是合式公式。 因为p、1是合公式，则(p1)是合式公式，而q是合式公式，故(p1)q是合式公式。 (p1)r不是合式公式。 因为p、1是合公式，则(p1)是合式公式，而r是合式公式，但(p1) r不是合法公式。
25
对于代数式x2+y+10，当x与y的值不确定时，该代数式的值是不确定的。
1.2公式的值 对于代数式x2+y+10，当x与y的值不确定时，该代数式的值是不确定的。 对于公式 (p1)q，由于p与q值不确定时，公式(p1)q的值不确定，因而不是命题。 只有当p与q的值确定后，公式(p1)q的值才确定，可像表1.2到表1.5一样，给出公式在各种情况下的值，即得到这个公式的真值表。 p与q每一种取值称为p、q的一种解释
26
公式(pq)、pq的真值表如下表。
1.2公式的值 公式(pq)、pq的真值表如下表。 真值表的构造方法： (1)命题变元的取值从全0开始，依次加1，直到全1，当有n个变元时，则共有2n种不同的取值情况。 (2)分步骤计算公式的值 (3)见黑板上写 成真赋值:如pq为(0,0),(0,1),(1,1) 成假赋值:如pq为(1,0)
27
1.2公式的值 公式(pq)(qp)、pq的真值表。 无论p/q取何值，这两个公式的值总相等。黑板上慢慢写
28
1.2公式的值 公式 (pq)、 p q的真值表。 无论p/q取何值，这两个公式的值总相等。
29
无论p/q取何值，这两个公式的值总相等，若前者称为原命题，后者为逆否命题
1.2公式及其值 公式pq、qp的真值表。 1 无论p/q取何值，这两个公式的值总相等，若前者称为原命题，后者为逆否命题
30
公式p(qr)、(pq)(pr)的真值表。
1.2公式及其值 公式p(qr)、(pq)(pr)的真值表。 无论p/q取何值，这两个公式的值，与前面各例不同，此表是将运算结果写在联结词的下方！
31
1.3 等值式 定义1.3.1等值： 对于合法的命题公式A、B，若无论其中的命题变元取何值，A 、B值总相等，称为两个公式等值，记为AB (边播边板) 1
32
1
33
(1)pqpqqp 条件式的等值式(板)
(3)(pq)pq (pq) pq 德摩律 (4)p(qr) (pq)(pr) 分配律 p(qr) (pq)(pr) (边播边板) (5)p(pq) p p(pq) p 吸收律(多吃少) p(pq)pq p(pq) pq 吸收背判者 (pq)(pr)(qr)pqpr 吸收共同助手 (6)pp 双重否定律 (7)ppppp 幂等律 (8)pq qp，pq qp 交换律 (9) p(qr) (pq) r 结合律 p(qr) (pq) r
34
反演规则(广义德摩律) (板) 将公式A中：条件式()、双条件()处理后： 从左到右依次完成以下反变换 1(T) 0(F),
0(F) 1(T), p p即p p p 得到A。 如：( (pq)(pq)) (pq) (pq) (pq)(pq) 也可用反演规则直接写出
35
对偶等值式规则 (板) 将等值式两边：条件式()、双条件()处理后 对等值式从左到右依次完成以下对偶变换 1(T) 0(F),
0(F) 1(T), 得到式子称为原式的对偶式，仍然等值式。 (3)(pq)pq (pq) pq 德摩律 (4)p(qr) (pq)(pr) p(qr) (pq)(pr) (5)p(pq) p p(pq) p 吸收律(多吃少) p(pq)pq p(pq) pq 吸收背判者
36
变元换公式规则 (板) 将等值式中的变元换成合式公式仍等值！ 如：pq pq 则有 AB AB 尽管A/B可能很复杂，但其值也只有0、1二种可能，公式A/B的组合只有0/0,0/1,1/0,1/1四种，如下表所示，仍可用真值表证明。 显然有 AB AB
37
等值演算规则(板) A=(pq)r D=(pq)r 将公式A中(pq)换成(pq),得到公式D
所以A D，常直接写成： (pq)r (pq)r，称为等值演算 置换规则(局部等值替换)： BC, D=A中所有子公式B换成C得到，则AD。 局部进行等值替换后,仍与原公式等值。 因为A、D除了“A中B所在之处、D中C所在之处”外，其他地方均相同. 而不同之处的B与C等值，所以A、D的真值表应该完全相同，故AD。 最基本的方法。
38
求证 (pq)r(pr) (qr)
r (pq) 交换律 (rp)( rq) 分配律 (p r)( qr) 交换律 (pr) (qr) 条件式等值式
39
等值演算的基本套路(板) (1)转换 ： ABAB (2)恰当转换 ：AB(AB) (AB)
确保公式只保留 联结词 (3)否定到底 ： A, (AB), (AB) (4)恰当使用分配律、吸收律、其他律。
40
利用等值演算，判断公式的类型 ((pq)p)q 解： ( (pq)p)q (条件式的等值式) ( (pq)p)q (条件式的等值式) ((pq)p)q (德摩律) ( (pq)p)q (德摩律) (pq)(pq) (结合律) (pq) (pq) (逆用德摩律) AA (A= (pq)) 1 称为永真式或重言式， 即利用等值演算，可以判断公式的类型。
41
利用等值演算判断公式类型：(p(pq))r
解： (p(pq))r (p(pq))r (条件式的等值式) ((pp)q) r (结合律) (1q) r (析取的性质即析取定义真值表) 1r (析取的性质即析取定义真值表) 0r (否定的定义) 0 (析取的性质即析取定义真值表) 永假式或矛盾式。 问题：尽管有套路可行，但是随意性还是比较大，能否有某种方式肯定能成功呢？
42
1.4 析取范式(Norm)与合取范式(板等值)
文字：命题变项(变元)及其否定称为文字. 如:p,q,r, p, q, r (板) 简单析取式:仅由有限个文字构成的析取式. 如:pq, pq,pq, p q,pqr (板) 简单合取式:仅由有限个文字构成的合取式. 如:pq, pq,pq, pq,pqr (板) 定理：简单析取式与简单合取式 (1)一个简单析取式Ai是重言式 含有某个命题变元及其否定式，如Ai=pp… (2)一个简单合取式Ai是矛盾式 含有某个命题变元及其否定式，如Ai=pp…
43
1.4 析取范式与合取范式 析取范式：由有限个简单合取式的析取构成的命题公式称为析取范式。 总体是析取式，每对括号内是合取式 (板)
A=(pq)(pr) 合取范式：由有限个简单析取式的合取构成的命题公式称为合取范式。 总体是合取式，每对括号内是析取式(板) A=(pq)(pr)
44
1.4 析取范式与合取范式 总体是析取式，每对括号内是合取式 A=(pq)(pr) 析取范式 总体是合取式，每对括号内是析取式
定理：析取范式与合取范式 (1)一个析取范式A是矛盾式 每个简单合取式是矛盾式。 A=(pq)(pr) (2)一个合取范式A是重言式 每个简单析取式是重言式。 A=(pq)(pr)
45
1.4 析取范式与合取范式(板) (1)转换 ： ABAB (2)恰当转换 ：AB(AB) (AB)
(3)否定到底(广义德摩) A, (AB), (AB) (4)适当分配律： A(BC), A(BC). 经过第1步、第2步转换后，公式中只有、、三种运算符。 经过第3步后，从括号外深入到变元前，与变元结合成文文字，文字之间只有、，这时比较简单了。 但对新手仍是有难度
46
求(pq)r的析取范式、合取范式(右边推导)
1.4 析取范式与合取范式 求(pq)r的析取范式、合取范式(右边推导) 解：(1)求析取范式。即外层是，内层是， 转换模式为AB (AB)(AB) (pq) r ((pq) r)( (pq) r) (整体为析取) ((pq) r)( (pq) r) (ABAB) ((pq) r)( (pq) r) (德摩律) ((p r )(qr))( (pq) r) (分配律) (p r )(qr)( pq r) (结合律)
47
1.4 析取范式与合取范式 (右边推导) 解：(1)求合取范式。所以转换模式为AB(AB)(AB) (pq) r
1.4 析取范式与合取范式 (右边推导) 解：(1)求合取范式。所以转换模式为AB(AB)(AB) (pq) r ( (pq)r)( (pq) r) (整体为合取) ( (pq)r)( (pq) r) (条件等价式) ((pq)r)( (pq) r) (德摩律) ((pr) (qr))( (pq) r) (分配律) (pr) (qr)( pq r) (结合律)
48
1.4 析取范式与合取范式 小项：在含有n个变元的简单合取式“”中,每个命题变元(原变量)或其否定(反变量)仅出现一次,且各变元按其字母顺序出现,则该简单合取式为(极)小项。 如：pqr, pqr, pqr, pqr(板) (p r), (qr) 非小项 大项：在含有n个变元的简单析取式“”中,每个命题变元(原变量)或其否定(反变量)仅出现一次,且各变元按其字母顺序出现,则该简单析取式为(极)大项。 如：pqr, pqr, pqr, pqr(板) (pr), (qr) 非大项
49
1.4 析取范式与合取范式 主析取范式：一个析取范式(整体局部)中，若所有简单合取式均为(极)小项，则为主析取范式
(pq) r (以右边板书为例) (p r)(qr)(pqr) 不是 (pqr)(pqr)(pqr)(pqr) 是主析取范式
50
1.4 析取范式与合取范式 主合取范式：一个合取范式(总体局部)中，如果所有简单析取式均为(极)大项，则为主合取范式.
(pq)r (以右边板书为例) (pr)(qr)(pqr) 不是 (pqr)(pqr)(pqr)(pqr) 是主合取范式
51
1.4 析取范式与合取范式—获取方法 通过转换联结词、“到底”及适当使用分配律，可以得到合取范式与析取范式，可能还缺少某个变元，
因pp1，1r r , 故 r=(pp)r=(pr)(p r) 可将缺少变元加入到小项中。 pr 缺q p1r 析1 p(qq)r 合取(qq) (pqr)(pqr)。
52
1.4 析取范式与合取范式—获取方法 通过转换联结词、“到底”及适当使用分配律，可以得到合取范式与析取范式，这时可能还缺少某个变元，因pp1，1r r , 故 r=(pp)r=(pr)(p r) 可将缺少变元加入到小项中。 (pq) r (pr)(qr)(pqr) (p(qq) r)((pp)qr)(pqr) 不细讲 (pqr )(pqr) (pqr )(pqr) (pqr) (pqr )(pqr) (pqr ) (pqr)
53
1.4 析取范式与合取范式—获取方法 因pp0, q0q(pp)q(pq)(pq) 可将缺少的变元引入到大项中。
如 pr 缺q p0r 析取0仍等值 p(qq)r 析取互反变元对合取 (pqr)(pqr) 两边分配
54
1.4 析取范式与合取范式—获取方法 因pp0, q0q(pp)q(pq)(pq) 可将缺少的变元引入到大项中。
(pq)r (pr)(qr)(pqr) (p(qq)r)((pp)qr)(pqr) (pqr)(pqr)(pqr)(pqr) (pqr) 不细讲 (pqr) (pqr)(pqr) (pqr)
55
1.4 析取范式与合取范式 复杂公式的析取范式、合取范式的演算量大，再转换为主析取范式、主合取范式，工作量更大。 能否按某种统一方式得到其主析取范式、主合取范式呢？ 通过真值表可以实现！ 为此先研究小项与大项的性质。
56
1.4 析取范式与合取范式 3变元各小项真值表 0-反变量 1-原变量
57
1、3个变元的小项共有8个，它们各不相同。 2、每一行：命题变元的每组值中，只有一个小项为1。 3、每一列：每小项仅有一个组值为1，其余7组均为0。 小项与变元的取值组即指派一一对应! 4.小项值为1时各变元的值为小项的编号。 如pqr=1p=0,q=0,r=0，故编号000。 小项规则：原变量--1 反变量—0,反之由编号可写出小项
58
小项规则：原变量--1 反变量--0。(板) (5)根据小项的编号，可写出小项的表达式。 如小项m101的表达式为pqr。 如m00为pq、m01为pq、 m10为pq、m11为pq。 很重要！!!!
59
(1)三个变元的大项共有8个。 (2) 每一行:只有一个大项的值为0。 (3)每一列:每个大项仅在一个指派即一组值为0。 (4)大项值为0时各变元的值为大项的编号。 如pqr=0p=0,q=0,r=0 p=1,q=1,r=1，其编号为 111。大项规则：原变量—0 反变量—1。
60
大项规则：原变量—0 反变量—1 (板) 如M101, 其表达式为pqr。 如M00表达式为 pq, M01为pq, M10表达式为pq, M11为pq。
61
1.4 基于真值表求主析取范式、主合取范式 1、先建立真值表， 2、成真赋值对应的小项之析取，为主析取范式
3、成假赋值对应的大项之合取，为主合取范式 如用真值表求主范式: (pq)r, pq, pq, (pq)q,p(pq)
62
(pqr) (pqr)(pqr)( pqr)
主析取范式 公式值为1的指派对应小项的析取 m001 m011 m100 m 小项规则：原变量-1 反变量-0 (pqr) (pqr)(pqr)( pqr)
63
(pq) r的主析取范式、主合取范式 主合取式范式 大项规则：原变量-0 反变量-1 公式值为0的指派对应大项的合取 两类范式编号互补
主合取式范式 大项规则：原变量-0 反变量-1 公式值为0的指派对应大项的合取 两类范式编号互补 M000 M010 M101 M110 (pqr)( pqr)( pqr)( pqr)
64
(pq)r、主析取m001 m011 m100 m111 、主合取M000 M010 M101 M110，互相等值。有如下定理 ：
(1)不是永假的命题公式，有等值的主析取范式。 (2)不是永真的命题公式，有等值的主合取范式。 因永假没有取值为1的解释，故无相应小项，故没有主析取范式。永真没有取值为0的解释,故没有主合取范式.
65
定理:不是永假公式,存在与之等值的主析取范式
设原公式为A,主析取范式为B为小项小项…. (1)根据主析构造方法,B是A之值为1时所对应小项的析取,因此当A为1时,B中有一个小项为1,故B为1. 当B为1时,根据析取运算性质,有一个小项为１,根据主析取的构造方法,在该小项编号对应的取值情况下,A的值为1. 即两者同为1. (2)当公式A为0时，由于B为A值为1的指派所对应的小项，由小项的性质(3)可知，B中各小项均为0，故B为0 B为0时，B中每个小项的值均0，此时不在A为1的任何指派中(反证：若在A为1的某个指派则至少有一个小项为1，则B为1矛盾)，只能在A为0的指派中，即A此时为0。 综上所述，A为1时B也为1，B为1时A也为1， 同时A为0时B为0，B为0时A也为0， 因此A与B的值，同为1同为0，故二者等值
66
设计一个电子评分系统，3位专家打分，如果有2位以上专家打分为“通过”，则总成绩为“通过” 。
对应的主析取范式值为1的指派对应的小项的析取 m011m101m110m111 (x1x2x3) (x1x2x3)(x1x2x3)(x1x2x3) ((x1x2x3)(x1x2x3))((x1x2x3) (x1x2x3)) ( ((x1x2) (x1x2))x3)(((x1x2(x3x3))) (((x1x2) (x1x2))x3)( x1x2) ((x1x2)(x1x2)x3)( x1x2) 卡诺图与非或门表示
67
某公司要从曹、乔、宋、黎、邹5人中，选择一些人承包一项工程，考虑到人与人组合优化的问题，需满足如下约束条件：
(1)如果曹去，那么乔也去； (2)黎、邹两人中必有一人去； (3)乔、宋两人中去且仅去一人； (4)宋、黎两人同去或同时不去； (5)若邹去，则曹、乔也同去； 解：用小写字母表示： c:曹去， q：乔去 s：宋去 l：黎去 z：邹去时，以上5句话可表示为如下的公式： (cq)、(lz)、((qs)(qs))、(sl)、(z(qc))， 5句话同时成立即每句话的值均为1，也即其合取式(cq)(lz)((qs)(qs))(sl)(z(qc))为1
68
(cq)(lz)((qs)(qs))(sl)(z(qc))
(cq)(lz)((qs)(qs))((sl)(sl))(z(qc)) (cq)(lz)(z(qc))((qssl)(qssl)(qssl)(qssl)) (cq)(lz)(z(qc))((qsl)(qsl)) (cq)(lz)((zqsl)(zqsl)(qcsl)) (cq)((zqsl)(zqcsl)) (czqsl)(zqcsl) 因(cq)(lz)((qs)(qs))(sl)(z(qc))为1，故1(czqsl)(zqcsl)， 故1(czqsl)或1(zqcsl) 故 方案一是：曹不去、邹不去、乔不去，宋与黎去。 方案二是：曹去、乔去、邹去，宋与黎均不去
69
在某班班委的选举中，该班的甲、乙、丙学生预言：
甲说：王娟为班长、刘强为生活委员； 乙说：金鑫为班长、王娟为生活委员； 丙说：刘强为班长、王娟为学习委员； 结果公布后，发现甲、乙、丙三人都恰好对了一半，请问王娟、刘强、金鑫各任何职？ 解：p1,q1,r1:表示王娟，刘强，金鑫是班长； p2,q2,r2:分别表示王娟，刘强，金鑫是学习委员； p3,q3,r3:分别表示王娟，刘强，金鑫是生活委员； “每个人说法对一半”将是一个非常复杂的公式(p1q3r1p3q1p2)( p1q3r1p3q1p2)( p1q3r1p3q1p2)( p1q3r1p3q1p2)( p1q3r1p3q1p2)( p1q3r1p3q1p2)( p1q3r1p3q1p2)( p1q3r1p3q1p2)，要构造这9个变元的真值表，将需要29=512行，工作量实在太大了， ！
70
参考“真值表”，设计如下的判断表
71
3、 黄、李、肖预测德国A、乌拉圭B、西班牙C、荷兰D的名次，黄说“德国冠军，乌拉圭亚军”，李说“荷兰亚军，西班牙第4名”，肖说“德国亚军，乌拉圭第四名”，结果三人预测的结果都只对了一个，请问最后的名次是什么。 4、 某公司要从A、B、C、D、E选派一些人去参观 世博会，必须满足如下条件： (1)若A去则B肯定不能去； (2)若A与C只能去一个； (3)C与D两人同去或同不去； (4)若B去则C肯定去 (5)若E去则B，C，D肯定有一人陪同。 证明：是否存在满足以上条件的人选？若存在则请给出全部方案。
72
5、赵、钱、孙、李4个参加ACM程序大赛后，有同学问他们，谁的成绩最好，赵说“不是我”，钱说“是李”，孙说“是钱”，李说“不是我”，4个人的回答只有一个人的说法符合实际情况，请问谁的成绩最好！已知只有一个第一名，即没有并列第一名。要求：用Z表示“赵第一”，Q表示“钱第一”，用S表示“孙第一”，L表示“李第一”，描述解题思想，并给出详细的解题过程。。 6、二、 三人估计比赛结果，A说“甲第一、丙第二”，B说“甲第二，丙第三”，C说“甲第二，乙第三”。结果三人估计都只对了一半，请问是否有解，若有解，请给出所有解？
73
7、赵国、钱多、孙少3个人拟加盟天马、岳麓、凤凰三支球队，记者事先预测。王记者说“孙少去天马，赵国去凤凰”，杨记者说“钱多去岳麓，赵国去天马”，刘记者说“钱多去凤凰，孙少去岳麓”！，最后的结果表明：每位记者的话错了一半，现以TZ、TQ、TS表示“赵国去了天马”、“钱多去了天马”、“孙少去了天马”，YZ、YQ、YS表示“赵国去了岳麓”、“钱多去了岳麓”、“孙少去了麓”，FZ、FQ、FS表示“赵国去了凤凰”、“钱多去了凤凰”、“孙少去了凤凰”，请在此基础上写出详细解题过程。
74
8、A、B、C、D同学有关假期旅游的谈话内容为：A说“如果B去、那我也去”，B说“C与D去，那我去”，C说“A与B不可能同时去”。D说“如果A、B、C有一人去了，我铁定去”，请给出满足这些要求所有结果。
75
9、高吉、王清、柯立拟转会到天马、岳麓、凤凰三支球队，记者事先预测。A记者说“柯立去天马，高吉去凤凰”，B记者说“王清去岳麓，高吉去天马”，C记者说“柯立去凤凰，王清去岳麓”！，最后的结果表明：每位记者的话都错了，现以TG、TW、TK表示“高吉去天马”、“王清去天马”、“柯立去天马”，YG、YW、YK表示“高吉去岳麓”、“王清去岳麓”、“柯立去麓”，FG、FW、FK表示“高吉去凤凰”、“王清去凤凰”、“柯立去凤凰”，请问此题有解吗？请给出详细的有解答过程。
76
10、某次考试以后，某班ABCD四位同学特别关心是否及格。每位同学依次作了如下猜测。A说：如果A及格了，则B没及格。B说：如果C及格，B肯定及格。C说：C与D都及格了。D说：如果A与B都及格，则D肯定及格了。最后结果这四句都对了。现用A表示A及格，B表示B及格了，C表示C及格了，D表示D及格了，据此将每人说的话分别表示命题公式，利用这些4个命题公式表示“四句都对了”，然后写出该命令公式的真值表，给出其各个小项，从而给出其析取范式，最终判断该问题是否有解，若有解请给出所有可能的解。。
77
1.6 推理理论 从已知条件、假设、前提或公理出发，根据推理规则推出结论、定理的过程，称为推理 。 前提: 如果老天下雨,那么我带伞
前提: 如果老天下雨,那么我带伞 今天老天下雨 结论: 今天我带伞 今天没带伞 结论: 老天没下雨 以上推理,当前提成立(为1),结论总成立(为1) 因此“推理”是指前提成立时,要判断结论是否成立 用符号表示为： (pq)pq, (pq)qp 当前提(pq)p成立(为1)时，结论q成立(为1)，不为假(0)，即10的情形不会出现,因此 (pq)pq, (pq)qp 为永真式
78
1.6 推理理论 从已知条件、假设、前提或公理出发，根据推理规则推出结论、定理的过程，称为推理 。
定义1 设A与C是两个命题公式，若AC为永真式(重言式)，则称C是A的有效结论，或称A可以逻辑推出C，记为AC. 由“”的定义可知，当A为假时，AC肯定为真，故只要考虑A为真时C是否为真即可，故有: 定义2 设A与C是两个命题公式，若当A为真时C也为真，则称C是A的有效结论，或称A可以逻辑推出C，记为AC。 一般情况下，利用定义2去证明要简单些，我们在其他学科中遇到的证明都是基于定义2的。 判断AC为永真可用等值演算、真值表等方法
79
例题 求证：A(AB)B (A(AB)) B (A(AB))B (的等值式)
((AA)(AB))B (分配律) (0(AB))B (合取的性质) (AB)B (析取的性质) (AB)B (德摩律) A(BB) (结合律) A (析取的性质) (析取的性质) 所以(A(AB)) B是重言式，真值表也证永真 所以A(AB)B。这是有名的“假言推理(modus ponens)”，或“分离原则”
80
假如我今年进入年级前10名老爸给我买iphone 4; 期末考试后我为年级第8名，所以老爸应该给我买iphone4。这是假言推理。
A(AB)B 从形式上看，结论B是AB的后件，推导的结果是将后件分离出来，故也称为分离原则。 利用假言推理规则或分离规则，结合析取、合取、否定的定义，只要不歉麻烦，几乎可推出所有的结论。 为了提高推理效率，还需要学习、掌握某些推理规则。
81
例题 求证 AAB 采用定义1来证明，即证明AAB为永真式。 AAB A(AB) (的等值式) (AA)B (结合律) 1B (析取的性质) (析取的性质) 所以AAB
82
例题 求证 ABA ABA (AB)A (的等值式) (AB)A (德摩律) ABA (结合律) 1B (析取的性质) (析取的性质) 类似 ABB 根据的定义可知AB为真时，A与B均为真，因此由推理定义2可知 ABA， AB B 。 同样由的定义可知A为真时 AB为真，故由推理定义2可知AAB。 然这3个推理式不必记忆！推理定义2效率较高
83
例题 求证 (AB)(BC)(AC)
根据定义1，要证明下式为永真式。 (AB)(BC) (AC) ((AB)(BC)) (AC) (的等值式) ((AB)( BC)) (AC) (的等值式) ((AB) (BC)) (AC) (德摩律) ((A B)(A C )(B B) (BC)) (AC) (分配律) ((A B)(A C )1(BC)) (AC) (析取的性质) ((A B)(A C )(BC)) (AC) (析取的性质) (A BAC)(A CAC )(BCAC) (分配律) (1 BC)(1 CC )(BA1) (析取的性质) 11 (析取的性质) (析取的性质) 判断公式的类型，除等值演算外，还有真值表与范式等方法。
84
例题 求证 (AB)(BC)(AC)
这是有名的传递律，要记住呀！
85
例题 求证 (AB)(CD)(AC)BD
利用定义1证明了假言推理规则(AB)AB,传递规则(AB)(BC)(AC)。 有了这2条规则后,可用定义2来证明推理式了。 由于这2条规则的结论中没有析取式，只有条件式，因此将题中结论转换为 BD,题设中转换为 (1)(AB)(CD)(AC)为真 前提条件(定义2的套路) (2) (AB)为真 (1)及合取的性质 (3) (CD)为真 (1)及合取的性质 (4) (AC)为真 (1)及合取的性质 (5)(BA)为真 (2)及(AB) (BA) (6) (AC)为真 (4)及(AC) (AC) (7) (BC)为真 (5)、(6)及推理传递律 (8) (BD)为真 (7)、(3)及推理传递律 (9) BD为真 (8)及(BD) BD
86
例题 求证 (AB)(CD)(BD)AC
可用传递律来证明，还有更高效的方法 由定义1只要证((AB)(CD)(BD))(AC)为重言式，而 ((AB)(CD)(BD))(AC) ((AB)(CD)(BD)) (AC) ( ((AB)(CD)(BD))A)C) ((AB)(CD)(BD))A)C) ((AB)(CD)(BD))A)C 故只需证 ((AB)(CD)(BD))A)C为重言式 即只需证明(AB)(CD)(BD))AC A从结论中挪到前提中，这种技巧称为附加条件(CP)法，适合于结论为条件式的情形。
87
例题 求证 (AB)(CD)(BD)AC
(1)(AB)(CD)(BD)A为真 CP规则及前提 (2)AB为真 (1)及合取的性质 (3)A为真 (1)及合取的性质 (4)B为真 (2)(3)及假言推理式(AB)AB (5)BD为真 (1)及合取的性质 (6)BD为真 (5)及BDBD (7)D为真 (4)(6)及假言推理式(BD)BD (8)CD为真 (1)及合取的性质 (9)DC为真 (8)及原命题逆否命题 (10)C为真 (7)(9)假言推理式(DC)DC 提示：熟练后可不写(1)式，直接引用(2)(3)(5)(8)！
88
例题 求证 (AB)(CD)(BD)AC
(3)B为真 (1)(2)及假言推理式(AB)AB (4)BD为真 前提条件 (5)BD为真 (4)及BDBD (6)D为真 (3)(5)及假言推理式(BD)BD (7)CD为真 前提条件 (8)DC为真 (7)及原命题逆否命题 (9)C为真 (6)(8)假言推理式(DC)DC
89
求证 (WR)V, V(CS),SU,C,UW
提示：此处用逗号简写前述各例中的合取式，从而鼓励大家直接引用前提。 利用假言推理、传递律及前面所学的等值式，可以推出结论。在黑板上演示一番 考虑到本题的结论是W，可采用反证法。 根据定义2可知“当前提为真时结论也为真”， 反证法是“前提为真时，假设结论不为真即结论的否定为真”。 即基于前提、结论否定进行推理。 如果推出了一个矛盾的结论出来，则说明“假设结论不为真”是错误的，即表示结论只能为真了
90
求证 (WR)V, V(CS),SU,C,UW
(1)W为真 假设结论W为0即 W为1(真) (2)W为真 (1)与否定的性质 (3)(WR)为真 (2)与析取的性质 (4)(WR)V为真 前提条件 (5)V为真 (4)(3)假言推理((WR)V)(WR) V (6)V(CS)为真 前提条件 (7) (CS)为真 (5)(6)假言推理(V(CS))V(CS) (8) CS为真 (7)与条件式的等值式CSCS (9)C为真 前提条件 (10)S为真 (8)(9)与假言推理(CS)( C)S (11) SU为真 前提条件 (12)U为真 (10)(11)假言推理(SU)SU (13) U为真 前提条件 显然(12)与(13)矛盾，故假设有误！
91
应用题 天气情况要么天晴，要么天下雨；如果天晴我去爬山，如果我去爬山那么我回来后不做饭， 结论是：如果我已做饭那么肯定天下雨了。 解：用M表示天晴， R表示天下雨， C表示爬山， F表示做饭，则问题可表示为 MR，MC，CFFR (MR)(MR) ，MC，CFFR
92
应用题MR，MC，CFFR (1)F为真 附件前提 (2)CF为真 前提条件 (3)FC为真 (2)的等值式 (4) FC为真 (3)的等值式 (5) C为真 (1)(4)的假言推理 (6) MC为真 前提条件 (7)CM为真 (6)的等值式 (8) M为真 (5)(7)的假言推理 (9) MR为真 前提条件 (10) MR为真 (9)的等值式 (11) R为真 (8)(10)的假言推理
93
应用题MR，MC，CFFR (1)F为真 附件前提 (2)CF为真 前提条件 (3)FC为真 (2)的等值式 (4) FC为真 (3)的等值式 (5) C为真 (1)(4)的假言推理 (6) MC为真 前提条件 (7)CM为真 (6)的等值式 (8) M为真 (5)(7)的假言推理 (9) (MR)(MR)为真 前提条件 (10) (MR) (MR)为真 (9)的等值式 (11) MR (MR)为真 (10)的等值式 (12) MR为真 (8)与析取的定义 (13) (MR)为真 (11)(12)的假言推理 (14) R为真 (13)与合取的定义
94
定义2证明推理式的规律 (1)利用“条件等值式”，尽可能将前提、中间结论及最终结论中的“析取式”转换为“条件式”，以便可引用假言推理、传递律。 (2)如果结论为条件式，则将条件式的前件做为附加前提。CP原则 (3)如果结论的否定在前提中多次出现，可采 用反证法。 (4)每一步的推理理由可简化，如“前提条件”简写为“P”，“假言推理”可简写“M”，等值式只写“等值”或简写“E”。 (5)这种从前提出发，应用已证明的推理式，不断推出中间结论，最后推出结论的方式，称为自然推理，这是最常见的方式。
95
1.7消解规则 证明(AC)(BC)AB (1) (AC)为真 前提条件 (2) A C为真 与(1)等值
由于(AC(BC)中互补的公式C、C同时消失了，称“AB”为 “(AC)，(BC)”的消解式。 因此在采用定义2进行推理时，只要(AC)、(BC)同时为真，则可直接写出AB为真，从而节省大量的中间环节，提高了证明效率。
96
1.7消解规则 例题 (AB)(CD)(BD)AC 利用条件式的等值式，则此题等价于证明
(3) AD为真 当(1)(2)为真消解式AD为真 (4) CD为真 前提条件 (5) AC为真 当(3)(4)为真消解式AC为真 采用假言推理原则时，尽可能将析取转换为条件式。 采用消解法时，尽可能将条件式转换为析取。 消解法是一种高效的方法。 消解法可完成1.6节中所有推理式
97
1.7消解规则 采用定传递律证明了(AC)(BC)AB (1) A为真 附加前提 (2) (AC)为真 前提条件
因AB AB,故可用假言推理及CP原则证明 (1) A为真 附加前提 (2) (AC)为真 前提条件 (3) A C为真 与(1)等值 (4) C为真 (1)(3)假言推理 (5) B C 为真 前提条件 (6)CB为真 与(4)等值 (7) B为真 (4)(6)假言推理 用假言推理证明了消解规则，反过来 用消解规则可证明假言推理
98
1.7消解规则 用假言推理证明了消解规则证明了 (AC)(BC)AB 反过来，用消解规则可证明假言推理 A(AB)B
“假言推理”与“消解规则”可以互相推出，因此一方推出的结论另一方也可以推出 因此习题三可由消解规则推导出来呀
Similar presentations
