1、第第3章章 命题逻辑命题逻辑3.1 命题的有关概念命题的有关概念本讲内容什么是命题什么是命题1命题的真值命题的真值2原子命题与复合命题原子命题与复合命题3逻辑常量与逻辑变量逻辑常量与逻辑变量4 命题之间的命题之间的 还有些什么关系还有些什么关系? 认知关系认知关系: 我知道我知道 偏好关系偏好关系: 他喜欢他喜欢 逻辑关系Chapter 3 命题逻辑命题逻辑 逻辑学是研究思维形式及思维规律尤其是逻辑学是研究思维形式及思维规律尤其是推理的学科推理的学科. 逻辑推理无处不在逻辑推理无处不在. 亚里士多德亚里士多德(Aristotle, 公元前公元前384公元前公元前322)是形式逻辑的创始人是形式
2、逻辑的创始人. 数学数学, 物理学物理学, 化学化学, 天文学天文学, 地学地学, 生物学生物学,逻逻辑学辑学. (MBA, MPA, 招聘等招聘等) 莱布尼茨莱布尼茨(G. Leibniz, 1647-1716) 是是数理逻数理逻辑辑的创始人的创始人. 传统的数理逻辑传统的数理逻辑(内容包括逻辑演算、公理内容包括逻辑演算、公理化集合论、模型论、递归论和证明论化集合论、模型论、递归论和证明论). 应用逻辑应用逻辑,如多值逻辑、模态逻辑、如多值逻辑、模态逻辑、归纳逻归纳逻辑辑、时序逻辑、动态逻辑、模糊逻辑、非、时序逻辑、动态逻辑、模糊逻辑、非单调逻辑、缺省逻辑、数字逻辑、电路逻单调逻辑、缺省逻辑
3、、数字逻辑、电路逻辑、算法逻辑及程序逻辑等辑、算法逻辑及程序逻辑等, 这些都与计算这些都与计算机科学密切相关机科学密切相关. 计算机如何进行逻辑思维的计算机如何进行逻辑思维的计算思维培计算思维培养养. 命题逻辑与谓词逻辑是数理逻辑的基础部命题逻辑与谓词逻辑是数理逻辑的基础部分分. 本章学习命题逻辑本章学习命题逻辑. 命题逻辑的研究对象是命题命题逻辑的研究对象是命题. . 3.1 命题的有关概念命题的有关概念 计算机的计算过程就是推理过程计算机的计算过程就是推理过程, 而每一步而每一步推理离不开判断推理离不开判断, 判断的对象就是命题判断的对象就是命题. 1. 什么是命题什么是命题? 命题是能判
4、断出真假的语句命题是能判断出真假的语句. 从三个方面去理解：从三个方面去理解： (1) 命题必须是一个完整的句子命题必须是一个完整的句子, 包括用数包括用数学式子如代表的语句学式子如代表的语句. (2) 所给语句具有真假意义所给语句具有真假意义,即有是否符合客即有是否符合客观实际或是否观实际或是否合理合理之分之分. 一般来说一般来说,只有陈只有陈述句才具有真假意义述句才具有真假意义, 祈使句、疑问句和感祈使句、疑问句和感叹句不具有真假意义叹句不具有真假意义; (3) 能判断出真假能判断出真假. 要是将来某时候能判断要是将来某时候能判断出真假也行出真假也行. 例例3-1 判断下列语句是否是命题判
5、断下列语句是否是命题. (1) 辽宁舰是中国的第一首艘航空母舰辽宁舰是中国的第一首艘航空母舰. (2) 我喜欢智能手机和平板电脑我喜欢智能手机和平板电脑 . (3) x 3. (4)立正！立正！ (5)这朵花真漂亮！这朵花真漂亮！ (6)你要我的手机号码是想给我充话费你要我的手机号码是想给我充话费? (7)火星上有生物火星上有生物.(美国美国Discovery号号: 火星上有水火星上有水? 2012年着陆火星的年着陆火星的Curiosity号号, 1 + 1 = 2) (8)我说的都是假话我说的都是假话. (9)小王和小李是同学小王和小李是同学. (10)你只有刻苦学习你只有刻苦学习,才能取得
6、好成绩才能取得好成绩. 歌德巴赫猜想歌德巴赫猜想: : 至今已至今已200多年多年. (1)1 + 1 = 2: 大于大于4 4的偶数是两个奇素数之和的偶数是两个奇素数之和. . 6 = 3 + 3; 8 = 3 + 5; 10 = 3 + 7 = 5 + 5; 12 = 5 + 7; (2)任何大于任何大于7 7的奇数是三个奇素数之和的奇数是三个奇素数之和. . 9 = 3 + 3 +3; 11 = 3 + 3 + 5; 13 = 3 + 3 +7; 15 = 3 + 5 + 7; 陈景润陈景润(1966)的的“陈式定理陈式定理”: 1 + 2 = 3, 任何充分任何充分大的偶数是一个素数与
7、两个素数乘积之和大的偶数是一个素数与两个素数乘积之和. 2007年年11月月15日重庆商报日重庆商报,大坪大坪67岁罗仁德破解岁罗仁德破解. 1935年出生的河北的何宝起自称破解年出生的河北的何宝起自称破解,奔波奔波8年年无人理无人理. 2. 命题的真值命题的真值(truth) 命题的真值就是命题的逻辑取值命题的真值就是命题的逻辑取值. . 经典逻辑值只有两个经典逻辑值只有两个: 1和和0, 它们是表示事物状态它们是表示事物状态的两个量的两个量. 若一个命题是真命题若一个命题是真命题,其真值为其真值为1; 若一若一个命题是假命题个命题是假命题, 其真值为其真值为0. 实际上在数理逻辑中实际上在
8、数理逻辑中, 更多时候逻辑真是用更多时候逻辑真是用T(True)或或t, 逻辑假用逻辑假用F(False)或或f表示的表示的. 3. 原子命题与复合命题原子命题与复合命题 若一个命题不包含有更小的命题若一个命题不包含有更小的命题, 则称其为则称其为原子命原子命题题(atom)当时认为原子最小当时认为原子最小?或简单命题或简单命题, 否则称否则称为为复合命题复合命题(compound proposition). 原子命题原子命题是命题逻辑研究的基本单位是命题逻辑研究的基本单位, 区分原子命题在后面区分原子命题在后面命题的符号化时是很重要的命题的符号化时是很重要的. 通常用通常用小写小写英文字母英
9、文字母p, q, r, s,或带下标或带下标p1, p2, p3, 等来表示原子命题等来表示原子命题, 如用如用p: 2 + 3 = 5, q: 今天今天我们上课我们上课. 4. 逻辑常量与逻辑变量逻辑常量与逻辑变量 把把1和和0称为称为逻辑常量逻辑常量(logical constant). 在逻辑表达式中出现的在逻辑表达式中出现的p, q, r或或p1, p2 , p3 等等称为称为命题变元命题变元(proposition variable)或逻辑或逻辑变量变量(logical variable). 命题变元可以代表任命题变元可以代表任意命题意命题, 从取值的角度看从取值的角度看, 命题变元
10、既可以命题变元既可以取取1又可以取又可以取0. 课堂练习课堂练习 习题习题3.1 1, 2.小结小结命题的概念命题的概念命题的真值命题的真值原子命题与复合命题原子命题与复合命题逻辑常量与逻辑变量逻辑常量与逻辑变量第第3章章 命题逻辑命题逻辑3.2 逻辑联结词逻辑联结词本讲内容 p, p q, p q12p q, p q, p q3p q, pq, pqn3.2 逻辑联结词逻辑联结词 逻辑联结词就是逻辑运算逻辑联结词就是逻辑运算: 复合命题是由原子命题构成的复合命题是由原子命题构成的, 它需要联结词它需要联结词. 给定了原子命题给定了原子命题, 使用逻辑联结词可以构成复使用逻辑联结词可以构成复合
11、命题合命题. 逻辑联结词类似于自然语言中的连词逻辑联结词类似于自然语言中的连词. 1. 否定否定(not)联结词联结词 : p p: 2 + 3 = 5, p : 2 + 3 5. p是数理逻辑中的是数理逻辑中的标准符号标准符号, 也可记为也可记为p, C语言语言!p, 在计算机其他课程中用在计算机其他课程中用 , 对应于对应于逻辑逻辑门电路中的门电路中的“非门非门”.pp1001p 2.合取合取(and)联结词联结词 : p q p: 小李能歌小李能歌, q :小李善舞小李善舞. p q :小李能歌且善舞小李能歌且善舞. 合取合取“ ”相当于相当于“并且并且”, “和和”, “与与”, “以
12、及以及”等等.pqp q111100010000 Remark (1) “小王和小李是同学小王和小李是同学”中的中的“和和”没有没有合取之意合取之意. (2)在数理逻辑中在数理逻辑中, 合取联结词可以将合取联结词可以将任意任意两两个命题联结起来以构造出新的命题个命题联结起来以构造出新的命题, 如用如用p: 2 + 3 = 5, q: 今天上课今天上课, 则则p q : 2 + 3 = 5且且今天上课今天上课. 下面要介绍的其他联结词都是这下面要介绍的其他联结词都是这样理解样理解. (3) p: 小李结婚了小李结婚了 q: 小李有小孩了小李有小孩了 p q , q p? p q : p & q,
13、 p & &q, p q = pq, 对应于对应于“与门与门”. 3. 析取析取(or)联结词联结词 : p q p: 这学期我选修人工智能课程这学期我选修人工智能课程, q: 这学期我选修模式识别课程这学期我选修模式识别课程 . p q: 这学期我选修人工智能课程这学期我选修人工智能课程或者或者模式模式识别课程识别课程 . 析取析取“ ”相当于相当于“或者或者”. p | q, p | q, p + q(“或门或门”).pqp q111101011000 4.异或异或(exclusive or, XOR)联结词联结词 : p q 自然语言中的自然语言中的“或或”: (1)“可兼或可兼或”(i
14、nclusive or), 它表示两者可同它表示两者可同时为真时为真, 用析取表示即可用析取表示即可. (2)“不可兼或不可兼或”,它表示两者不能同时为真它表示两者不能同时为真,换句话说换句话说, 两者同时为真是假命题两者同时为真是假命题. 这就需这就需要异或联结词要异或联结词. p: 明天去深圳的飞机是上午八点起飞明天去深圳的飞机是上午八点起飞, q :明明天去深圳的飞机是上午八点半起飞天去深圳的飞机是上午八点半起飞. p q: 明天去深圳的飞机是上午八点或上午明天去深圳的飞机是上午八点或上午八点半起飞八点半起飞 . 本学期张三本学期张三或或李四当选为班长李四当选为班长. 今天晚上在寝室上自
15、习或去今天晚上在寝室上自习或去电影院电影院看看3D电电影影. (都在寝室都在寝室? 7:30?) 与异或联结词对应的门电路为与异或联结词对应的门电路为“异或门异或门”. 一般来说一般来说, 只要不是非常明显的不可兼就使只要不是非常明显的不可兼就使用用 .pqp q110101011000 5. 条件条件(conditional)联结词联结词 : p q p: 我有时间我有时间, q : 我去看望我的父母我去看望我的父母. pq:如果我有时间如果我有时间,那么我去看望我的父母那么我去看望我的父母 . “”相当于相当于“如果如果那么那么”, “若若则则”,等等.p q 可读作可读作“(若若)p则则
16、q”.pqp q111100011001 蕴涵蕴涵联结词也可以称为联结词也可以称为条件联结词条件联结词. 在在p q中中, p称为称为前件前件, q称为称为后件后件. 当当 p = 1, q = 1时时p q = 1; 当当 p = 1, q = 0时时p q = 0, 这是比较好理解的两种情形这是比较好理解的两种情形. 规定的合理性见下面的例子规定的合理性见下面的例子. (1)如果太阳从西边出来如果太阳从西边出来, 那么那么2 + 3 = 5. (2)如果太阳从西边出来如果太阳从西边出来, 那么那么2 + 3 = 4. 实际上实际上, 在根据子集的定义证明在根据子集的定义证明1.1节的定理节
17、的定理: 对于任意集合对于任意集合A, 有有 A时时, 就要用到上述就要用到上述实质蕴涵的定义实质蕴涵的定义. 同样同样, 在理解关系的自反、在理解关系的自反、反自反、对称、反对称及传递性质时反自反、对称、反对称及传递性质时, 也要也要用到上述实质蕴涵的定义用到上述实质蕴涵的定义. 当然当然, 在现代逻辑中在现代逻辑中, 对蕴涵的不同理解会对蕴涵的不同理解会得到不同的逻辑系统得到不同的逻辑系统, 如由如由严格蕴涵严格蕴涵得出模得出模态逻辑系统态逻辑系统 . 6.双条件双条件(biconditional)联结词联结词 : p q p: 四边形是平行四边形四边形是平行四边形, q :四边形的对边四
18、边形的对边平行平行 . p q :四边形是平行四边形当且仅当四边四边形是平行四边形当且仅当四边形的对边平行形的对边平行. p q :可读作可读作“p当且仅当当且仅当q”. 双条件双条件联结词联结词“”相当于自然语言中的相当于自然语言中的“当且仅当当且仅当”、“充分必要条件充分必要条件”, 其英文其英文为为if and only if, 缩写为缩写为iff. “p当且仅当当且仅当q”有两层含义：有两层含义：(1) “p当当q”是指是指q p. (2) “p仅当仅当q”是指是指p q. 正因为此正因为此, 等等价联结词又可以称为价联结词又可以称为双蕴涵联结词双蕴涵联结词或或双条双条件联结词件联结词
19、. . 数字逻辑等课程数字逻辑等课程 的的“同同”,并用并用“ ” 表示表示.pqp q111100010001 7. 与非与非(NOT AND)联结词联结词 : p q 在数字逻辑以及计算机组成原理中在数字逻辑以及计算机组成原理中“ ”没没有专用的运算符号有专用的运算符号,“ p与非与非q”直接记为直接记为 ,对应的门电路为对应的门电路为“与非门与非门”. pq)(qpqp 8.或或非非(NOT OR)联结词联结词 : p q 在数字逻辑以及计算机组成原理中在数字逻辑以及计算机组成原理中“ ”没没有专用的运算符号有专用的运算符号,“ p或非或非q”直接记直接记为为 ,对应的门电路为对应的门电
20、路为“或非门或非门”.qp)(qpqp 9.条件否定条件否定(NOT-IF-THEN)联结词联结词 : 读作读作“p条件否定条件否定q”,其中其中n表示否定表示否定not. “p条件否定条件否定q” 可直接记为可直接记为qpn).(qp )(qpqpnnqpqpn 上面介绍了上面介绍了1个一元逻辑运算、个一元逻辑运算、8个二元逻个二元逻辑运算辑运算. 后面将证明：后面将证明：不同的一元逻辑运算不同的一元逻辑运算和二元逻辑运算共和二元逻辑运算共9个个. 要求要求 理解记忆上述理解记忆上述9 9个个, , 特别是最前面的特别是最前面的6 6个联结词的运算表个联结词的运算表. 思考思考 如何定义三元
21、逻辑运算如何定义三元逻辑运算? 课堂练习课堂练习 习题习题3.2 16.CDAB :ary4小结小结 p, p q, p qp q, pq, pqp q, p q, p qn第第3章章 命题逻辑命题逻辑3.3 命题公式及其真值表命题公式及其真值表本讲内容命题公式的定义命题公式的定义1命题的符号化命题的符号化2命题公式的真值表命题公式的真值表3命题公式的类型命题公式的类型43.3 命题公式及其真值表命题公式及其真值表 有了前面的两节内容有了前面的两节内容, 就可以得到命题逻辑就可以得到命题逻辑的符号体系的符号体系. 1. 命题公式命题公式(proposition formula)的定义的定义 逻
22、辑函数逻辑函数(logical function) 逻辑表达式逻辑表达式(logical expression), 其中的常量是其中的常量是逻辑常量逻辑常量1和和0, 其中的变元是命题变元或逻辑其中的变元是命题变元或逻辑变量变量. 命题公式是由命题常量、命题变元、逻辑联命题公式是由命题常量、命题变元、逻辑联结词、左圆括号及右圆括号构成的有意义结词、左圆括号及右圆括号构成的有意义(well-formed)的符号串的符号串, 其严格定义需借助于其严格定义需借助于递归定义方式给出递归定义方式给出. Definition (1)1, 0, p, q, r, (2) A ( A) (3) A, B (4
23、) 有限次应用有限次应用(1)(2)(3)所得到的符号串是仅所得到的符号串是仅有的命题公式有的命题公式. ).(),(),(),(),(),(),(),(BABABABABABABABAn 命题公式命题公式可称为可称为合式公式合式公式(Well-Formed Formula, WFF)或简称为或简称为公式公式,其全称为其全称为命命题合式公式题合式公式, 是书写正确、含义清楚的表达是书写正确、含义清楚的表达式或者说符号串式或者说符号串. 借助于借助于函数函数给命题公式下定义给命题公式下定义.?),.,(21npppAA ?)(),();)(),1 (),( ,qppqqpppp 可以省略可以省略
24、括号的约定括号的约定: (1) 最外层的括号可以省略最外层的括号可以省略. 在形成最终的命题公式时在形成最终的命题公式时, 所有的中间过程所有的中间过程得到的命题公式得到的命题公式,包含其本身包含其本身,都称为该命题都称为该命题公式的公式的子公式子公式. qqpqqp)( : )(?qp (2) 9个联结词运算的优先顺序依次为个联结词运算的优先顺序依次为: 符合本约定的有些括号符合本约定的有些括号可以可以不写不写. 如命题公如命题公式式 Remark 这种规定不是唯一的这种规定不是唯一的.n,)()(rqprqp)( (3)同级运算从左至右依次进行同级运算从左至右依次进行. 如如 实际上实际上
25、, 在对命题进行符号化时在对命题进行符号化时, 只要书写只要书写正确的逻辑函数都是命题公式正确的逻辑函数都是命题公式.rqprqp )(?)(rqp 2.命题的符号化命题的符号化 命题的符号化就是使用符号命题的符号化就是使用符号命题变元、命题变元、逻辑联结词和括号将所给出的命题表示出逻辑联结词和括号将所给出的命题表示出来来. 符号体系来源于实际问题符号体系来源于实际问题. 给出进一步学习逻辑演算系统的语义解释时的给出进一步学习逻辑演算系统的语义解释时的一种标准模型一种标准模型. 命题的符号化的步骤命题的符号化的步骤: Step 1 找出所给命题的所有原子命题找出所给命题的所有原子命题, 并用小
26、写并用小写英文字母或带下标表示；英文字母或带下标表示； Step 2 确定应使用的联结词确定应使用的联结词,进而将原命题用符进而将原命题用符号表示出来号表示出来. 例例3-7 将下列命题符号化将下列命题符号化. (1)天气很好或很热天气很好或很热. (2)如果张三和李四都不去如果张三和李四都不去,那么我就去那么我就去. (3)仅当你走仅当你走, 我留下我留下. (4)我今天进城我今天进城, 除非天下雨除非天下雨. (5)你只有刻苦学习你只有刻苦学习, 才能取得好成绩才能取得好成绩. Solution (1) 用用p:天气很好天气很好, q:天气很热天气很热 “天气很好或很热天气很好或很热”可符
27、号化为可符号化为 (2)用用p: 张三去张三去, q: 李四去李四去, r: 我去我去. 则原命题可符号化为则原命题可符号化为 (3)用用p: 你走你走, q: 我留下我留下 则则“仅当仅当你走你走, 我留下我留下”可符号化为可符号化为. qp.)(rqp. pq (4)p: 我今天进城我今天进城, q: 天下雨天下雨. 除非除非 = 如果不如果不. (5)p:你刻苦学习你刻苦学习, q: 你取得好成绩你取得好成绩. 只有只有p, 才才q?. pq . pq 3. 命题公式的真值表命题公式的真值表 命题公式的真值表就是命题公式的取值情况表命题公式的真值表就是命题公式的取值情况表. 若对中出现的
28、每个命题变元都指定一个真若对中出现的每个命题变元都指定一个真值值1或者或者0, 就对命题公式就对命题公式A进行了一种进行了一种真值真值指派指派或一个或一个解释解释, 而在该指派下会求出公式而在该指派下会求出公式A的一个真值的一个真值. 将将A的所有可能的真值指派以的所有可能的真值指派以及在每一个真值指派下的取值列成一个表及在每一个真值指派下的取值列成一个表,就得到命题公式就得到命题公式A的的真值表真值表(truth table). 例例3-8 写出命题公式写出命题公式 的真值表的真值表.rp)(q p q r p p q( p q) r1 1 10111 1 00101 0 10011 0 0
29、0010 1 11110 1 01100 0 11110 0 0110 要求大家能准确写出一个命题公式的真值要求大家能准确写出一个命题公式的真值表表, 这是本节的这是本节的重点内容重点内容,当然必须牢记联结当然必须牢记联结词的运算表才行词的运算表才行. 由表知由表知,含含3个命题变元的命题公式有个命题变元的命题公式有8 = 23 种不同的真值指派种不同的真值指派. 很显然很显然,含含2个命题变元个命题变元的命题公式有的命题公式有4 = 22 种不同的真值指派种不同的真值指派. 含含n个命题变元的命题公式的不同的真值指个命题变元的命题公式的不同的真值指派有派有2n种种. 4.命题公式的类型命题公
30、式的类型 (1) 在任何指派下均取真的命题公式称为在任何指派下均取真的命题公式称为永永真式真式或重言式或重言式(tautology)； (2) 在任何指派下均取假的命题公式称为在任何指派下均取假的命题公式称为永永假式假式或矛盾式或矛盾式(contradiction)； (3) 至少有一种指派使其为真的命题公式称至少有一种指派使其为真的命题公式称为为可满足式可满足式(satisfiable formula)； (4)至少有一种指派使其为真同时至少有一至少有一种指派使其为真同时至少有一种指派使其为假的命题公式称为种指派使其为假的命题公式称为中性式中性式(偶偶然式然式) (contingency).
31、 永假式永假式偶然式偶然式永真式永真式可满足式可满足式命题公式命题公式 例例3-9 证明证明 是永真式是永真式 真值表法真值表法? ?)()(qpqpp qpq p q1 111 010 110 01)()(qpqp 例例3-10 Proof 由由A =1可推出可推出B = 1, 则则A B永真永真. 由由B =0可推出可推出A = 0, 则则A B永真永真. 取值法取值法?(本质上是真值表法本质上是真值表法)?)(qqpp11, 11)(qqppqpp 最后介绍永真式的代入定理最后介绍永真式的代入定理RS(Rule of Substitution). Theorem 3-1(永真式的代入定理
32、永真式的代入定理) 如何使用如何使用?永真永真永真永真),.,(),.,(2121nnBBBApppA永真永真永真永真)()()()(BABAqpqp小结与作业小结与作业命题公式的定义命题公式的定义命题的符号化命题的符号化命题公式的真值表命题公式的真值表命题公式的类型命题公式的类型习题习题3.3 1(双双), 2(双双), 4, 5, 6(双双)作业作业第第3章章 命题逻辑命题逻辑3.4 逻辑等值的命题公式逻辑等值的命题公式本讲内容逻辑等值的定义逻辑等值的定义1基本等值式基本等值式2 等值演算法等值演算法3对偶原理对偶原理43.4 逻辑等值的命题公式逻辑等值的命题公式 命题命题 “四边形的对边
33、平行四边形的对边平行” 与命题与命题 “四边四边形的对边相等形的对边相等”是逻辑等值的是逻辑等值的, 它们它们在逻辑在逻辑上说的是同一回事上说的是同一回事. 上述两个命题的真值是相同的上述两个命题的真值是相同的. 下面讨论两个命题公式逻辑等值下面讨论两个命题公式逻辑等值. 1. 逻辑等值的定义逻辑等值的定义 Def 给定两个命题公式给定两个命题公式A和和B, 若在任何真若在任何真值指派下值指派下A和和B的真值都相同的真值都相同, 则称命题公式则称命题公式A和和B逻辑等价逻辑等价或或逻辑等值逻辑等值(logically equivalent)或简称为或简称为等值等值或或相等相等, 记为记为 A
34、= B. Remark “=”是命题公式之间的关系符号是命题公式之间的关系符号. A B? Theorem 3-2 A = B的充要条件是的充要条件是A B永永真真. Proof Clearly. 下面的例子说明如何下面的例子说明如何利用真值表利用真值表(第一种方第一种方法法)证明两个命题公式等值证明两个命题公式等值. 例例3-11 证明证明:.BABA p q pq p p q1 11011 00000 11110 0111?)()(永真qpqp?)()(永真BABA.BABA Theorem 3-3 例如例如, Theorem 逻辑等值是命题公式间的等价关逻辑等值是命题公式间的等价关系系:
35、(1)自反自反, (2)对称对称, (3)传递传递. Problem 等价类是什么等价类是什么?),.,(),.,(212211nnpppApppA),.,(),.,(212211nnBBBABBBABABAqpqp 2. 基本等值式基本等值式 (I)与与 , , 有关的等值式有关的等值式 Theorem 3-5 (1) (2) (3) (4) (5).:AAAA.,:,AAAAAAAAAAAA.,ABBAABBA).()(),()(CBACBACBACBAABAAABAA)(,)(.)(,ABAAAABA (6) (7) (8) (9),(10)()()(CABACBA)()()(CABAC
36、BA)(CABABCAACABCBA)(BABABABA)(,)(BAABBABA, Remarks (1)与集合的有关性质类似与集合的有关性质类似. (2)每条性质均可证明每条性质均可证明. (II)其他重要的等值式其他重要的等值式 Theorem (1) (2) (3) (4) (5) (6) Proof(?).(BABA.BABA).()(ABBABA).(BABA).(BABA).(BABAn 3. 等值演算法等值演算法 基本等值式有很多用途基本等值式有很多用途, 如化简命题公式、如化简命题公式、判断命题公式的类型、证明等值式、计算判断命题公式的类型、证明等值式、计算命题公式的范式、命
37、题逻辑中的推理等命题公式的范式、命题逻辑中的推理等, 要要求大家要熟记求大家要熟记, 特别是定理特别是定理3-5中的等值式中的等值式. 在使用等值式时在使用等值式时,常用下列的等值置换定理常用下列的等值置换定理RR (Rule of Replacement). 等值置换定理等值置换定理 设设C是命题公式是命题公式A的子公式的子公式,若若C = D, 则将则将A中的中的C部分或全部替换为部分或全部替换为D所所得到的命题公式与得到的命题公式与A等值等值. 利用基本等值式以及等值置换定理求解问利用基本等值式以及等值置换定理求解问题的方法称为题的方法称为“等值演算法等值演算法”. 例例3-13 化简化
38、简(?)下列命题公式并将最后结果下列命题公式并将最后结果用只含用只含 和和 表示表示. (1) (2) Solution (1).)(BACBABACBA)(BACBA)(BACBA)(BA).(BA数字逻辑、计算机组成中经常化简单数字逻辑、计算机组成中经常化简单! 利用等值演算法利用等值演算法, 判断一个命题公式的类型判断一个命题公式的类型是比较方便的是比较方便的. 例例3-14 设设A, B, C是任意的命题公式是任意的命题公式, 判断下判断下列命题公式的类型列命题公式的类型: (1) (2) Solution (2).(CBAA)(CBAA)(CBAA)(CBAA?A 证明两个命题公式等
39、值的第二种方法证明两个命题公式等值的第二种方法: 等值等值演算法演算法. 例例3-15 设设A, B, C是任意的命题公式是任意的命题公式,证明下证明下列等值式列等值式. (1) (2) Proof (2).)()(CBACBACBACBACBACBACBA)()()()()( 4. 对偶原理对偶原理 在与在与 , , 有关有关的基本等值式中的基本等值式中,除性质除性质(1)外外,其它性质都是成对出现的其它性质都是成对出现的,两者间有一定两者间有一定的联系的联系. 先给出命题公式的对偶式的定义先给出命题公式的对偶式的定义. Def 3-4 设命题公式设命题公式A中至多含有中至多含有3个逻辑联个
40、逻辑联结词结词 , , , (1)将将A中的中的 换成换成 ；(2)A中的中的 换成换成 ；(3)A中的中的1换成换成0；(4) A中的中的0换成换成1, 所得到的命题公式称为是所得到的命题公式称为是A的对偶式的对偶式(dual formula), 记为记为A*. 例如例如 Remark 一般来说一般来说1)(qpA0)(*qpA.*AA 对偶原理对偶原理 设设A和和B是命题公式是命题公式, 若若A = B, 则则A* = B*. 有了对偶原理后有了对偶原理后, 定理定理3-5中除性质中除性质(1)外的外的等值式等值式,只需要记住其中一个就可以了只需要记住其中一个就可以了. 有了对偶原理有了对
41、偶原理,我们可以求出任意命题公式我们可以求出任意命题公式的对偶式的对偶式. qpqpqpqp)()(qpAqpqpA*3.5 命题公式的范式命题公式的范式 命题公式的范式就是其命题公式的范式就是其标准形式标准形式或或规范形式规范形式. 有了命题公式的范式有了命题公式的范式, 就可以不用写出真值表就能就可以不用写出真值表就能确定在何真值指派下取真以及在何真值指派下取确定在何真值指派下取真以及在何真值指派下取假假. 1. 命题公式的析取范式及合取范式命题公式的析取范式及合取范式 (1) 析取范式析取范式及及合取范式合取范式的定义的定义 Def 3-5 设设A是命题公式是命题公式, 若若A = A1
42、 A2 An (n 1), 其中其中Ai(1 i n)是由命题变元或是由命题变元或其否定组成的合取式其否定组成的合取式, 则称则称A1 A2 An为为A的析取范式的析取范式(disjunctive normal form). Remarks Ai= p q r, p q, q r, q, r? n = 1? 如如A = p q r = ( p q r ). Def 3-6 设设A是命题公式是命题公式, 若若A = A1 A2 An (n 1), 其中其中Ai(1 i n)是由命题变元或是由命题变元或其否定组成的析取式其否定组成的析取式, 则称则称A1 A2 An为为A的合取范式的合取范式(co
43、njunctive normal form). Remarks Ai= p q r, p q, q r, q, r? n = 1? 如如A = p q r = ( p q r ). 若若A = p q r , 则则 p q r也也是是A的析取的析取范式范式. (2) 析取范式及合取范式的计算析取范式及合取范式的计算 Step1 使用等值式使用等值式, 将命题公式中的联结词将命题公式中的联结词归约为归约为 , , ； Step2 利用利用De Morgan律将律将 移到命题变元移到命题变元的前面；的前面； Step3 根据根据分配律分配律得到命题公式的析取范式得到命题公式的析取范式及合取范式：及
44、合取范式： A (B C) = (A B) (A C)(求析取范式用求析取范式用). A (B C) = (A B) (A C)(求合取范式用求合取范式用). 例例3-17 设设p, q和和r是命题变元是命题变元,求命题公式求命题公式A = (p q) r的析取范式及合取范式的析取范式及合取范式. Solution 求命题公式的析取范式及合取范式求命题公式的析取范式及合取范式的的Step1和和Step2是相同的是相同的.rqprqpA)()()()(qprrqp)()(qprrqp)()(rqprqp 析取范式析取范式: 合取范式合取范式:)()(rqprqpA).()()(rqprqrp)(
45、)( (rqprqpA)()()(rqprrqpqp).()()(rqrprqp (3)析取范式及合取范式的应用析取范式及合取范式的应用 根据命题公式的析取范式及合取范式可分根据命题公式的析取范式及合取范式可分别得出该命题公式取真、假的指派别得出该命题公式取真、假的指派.?1)()()(rqrprqpA).0 , 0 , 1 (),(1)(rqprqp).1 , 0 , 0(),1 , 1 , 0(),(1, 01)(rqprprp).1 , 1 , 0(),1 , 1 , 1 (),(1, 11)(rqprqrq?0)()()(rqprqrpA 例例3-18 从从p, q, r, s四人中选
46、派四人中选派2人出差人出差,求满求满足下列足下列3个条件的选派方法有哪几种个条件的选派方法有哪几种. (1)若若p去去,则则r和和s中只去中只去1人；人； (2)q和和r不能都去；不能都去； (3)若若r去去, 则则s不能去不能去. Solution p: p去出差去出差, q: q去出差去出差, r: r去出差去出差, s: s去出差去出差,则则 (1) (2) (3);(srp);(rq. sr (a)p, s去去; (b)q, s去去; (c)p, r去去.?1)()()()()()()()(srqsrpsqpsrrpsrrqsrpA 2. 命题公式的主析取范式及主合取范式命题公式的主析
47、取范式及主合取范式 一般来说一般来说, 命题公式的析取范式及合取范式命题公式的析取范式及合取范式不是唯一的不是唯一的, 如如A = (p q) (p q) = p都都是是A的析取范式的析取范式. 下面讨论下面讨论, 给定命题公式的给定命题公式的唯一的标准形式：主析取范式以及主合取唯一的标准形式：主析取范式以及主合取范式范式. 给定命题公式给定命题公式, 从从A中命题变元产生的最小中命题变元产生的最小项和最大项的角度来讨论项和最大项的角度来讨论A的主析取范式及的主析取范式及主合取范式主合取范式, 在逻辑电路中也会讨论其相应在逻辑电路中也会讨论其相应的标准形式的标准形式. (1)主析取范式主析取范
48、式 Def 对于给定的命题变元对于给定的命题变元,若由命题变元或若由命题变元或其否定组成的合取式满足其否定组成的合取式满足(1) 每个命题变元每个命题变元或其否定二者之一只出现一次或其否定二者之一只出现一次; (2)按字典顺按字典顺序或按下标从小到大顺序出现序或按下标从小到大顺序出现, 称这样的合称这样的合取式为由所给命题变元产生的取式为由所给命题变元产生的最小项最小项.,:,qpqpqpqpqp,:,rqprqprqprqprqp.,rqprqprqprqp 对于每一个最小项只有一种指派使其取对于每一个最小项只有一种指派使其取1 1. . 可以根据这个结论对最小项编码可以根据这个结论对最小项
49、编码. 最小项用最小项用表示表示mi,其下标是由成真指派得到的二进制其下标是由成真指派得到的二进制数或对应的十进制数数或对应的十进制数, 对于最小项对于最小项p q r, 成真指派得到的二进制数为成真指派得到的二进制数为110, 因为因为(110)2 = 6, 所以所以p q r = m110= m6 . 表表3-15? Def 对于命题公式对于命题公式A, 若若A等值于由等值于由A中中所有所有命题变元产生的若干个最小项的析取命题变元产生的若干个最小项的析取, 则把则把后者称为后者称为A的的主析取范式主析取范式(major disjunctive form). 含含n个命题变元的命题公式个命题
50、变元的命题公式,“若干个若干个”最大最大为为2n, 最小为最小为0. 所有最小项的析取为永真式所有最小项的析取为永真式1, 而而0个最小项的析取意味着个最小项的析取意味着A为永假式为永假式0, 这这时的主析取范式不存在时的主析取范式不存在. 除这两种极端情形除这两种极端情形外外, A均为中性式均为中性式. 显然显然, 主析取范式是析取范式主析取范式是析取范式, 但反过来不但反过来不成立成立.?)()()(rqrprqpA)()()()(rqprqprqqprp)()()()(rqprqprqpprq).()()()(rqprqprqprqpA 根据这个分析根据这个分析, 我们得到求我们得到求A
