第二章 命题逻辑等值演算 主要内容 等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式,主析取范式与主合取范式 联结词完备集

Slides:



Advertisements
Similar presentations
七年级数学校本课程 台山市任远中学 李锦明. 1. 最古老的过河问题 1. 最古老的过河问题 一个农民携带一只狼,一只羊和一 箱卷心菜,要借助一条小船过河。 小船上除了农民只能再带狼、羊、 卷心菜中的一样。而农民不在时, 狼会吃羊,羊会吃菜。农民如何过 河呢?
Advertisements

國中教育會考說明 年 5 月 14 日(六) 105 年 5 月 15 日(日)  08:20- 08:30 考試說明  08:20- 08:30 考試說明  08:30-  09:40 社 會  08:30-  09:40 自 然 09:40- 10:20 休息 09:40-
興南國小強化體適能活動 學務處體育組 ( ) 此檔案家長可在學校首頁行政公告下載. 教育部體適能常模 坐姿體前彎 ( 公分 ) 立定跳遠 ( 公分 ) 仰臥起坐 ( 次 ) 心肺適能 ( 分秒 ) 10 歲男 / 女生 PR25 常模標準 19/24 119/110 19/19 347/353.
說 劍 《莊子‧雜篇》─ 第 一 組 賴泊錞 謝孟儒 張維真 羅苡芸
总 复 习 四则运算 位置与方向 运算定律与简便计算 小数和意义和性质 小数和加法和减法 三角形 统计.
德 国 鼓 励 生 育 的 宣 传 画.
第13章 土壤.
制作人:徐嘉辉 郭海霞.
第四章 组合逻辑电路 第 四 章 组 合 逻 辑 电 路.
体育田径课.
105年桃連區適性入學宣導 桃園市十二年國民基本教育宣導團 宣講講師:龍岡國中 校長 郭玉承 時 間:105年 3 月 9 日 1.
第十二章 小组评估 本章重点问题: 评估的设计 测量工具的选择和资料的收集 与分析.
前进中的山东省昌乐二中.
第一章 命题逻辑 杨圣洪 (qq) Kczx.hnu.cn 课程网站点击排行-更多-离散数学.
第七章 田 径 运 动 场 地.
江苏省2008年普通高校 招生录取办法 常熟理工学院学生处
合 同 法 主讲人: 教材:《合同法学》(崔建远) 2017/3/10.
第 三 节 电磁铁的应用.
平面直角坐标系(1) 营口市第十七中学 杨晋.
第四章 现代汉语语法.
透過教學鷹架引導 三年級學生形成科學議題 高雄市復興國小 李素貞 102年3月20日
第二章 股票市场 第三章 证券投资工具 ----债券 股票概述 股票的发行与流通
巧用叠词,妙趣横生.
必修Ⅰ 地球上的水 第三章.
实验设计中的因变量检测 乐清中学 霍晓珍.
水土保持工程施工階段監造管理之探討 授課老師:林俐玲 教授 指導老師:陳文福 教授 報告人: 顏廣智 學 號:
第二章 命题逻辑(上) 主讲人:耿国华.
第4讲 充分条件和必要条件.
钳加工技术 广西玉林高级技工学校|数控教研组.
第二章 命题逻辑.
“08高考化学学业水平(必修科目)测试的命题和教学对策研究”
公 园 大 道 ——公园链住宅社区 组员:张亚辉 程桂华 黄传东.
1.4 民用建筑的构造组成 1、基础 2、墙体和柱 3、屋顶 4、楼地层 5、楼梯 6、门窗 次要组成部分(阳台、雨蓬、台阶、散水等)
电在我们日常生活、现代化社会中的应用: 电 是 什 么?.
第4章 种群和群落 第3节 群落的结构 自主学习案   合作探究案 课后练习案. 第4章 种群和群落 第3节 群落的结构 自主学习案   合作探究案 课后练习案.
依氣候條件所區分的成土作用 作用 說明 鐵鋁化
矿产资源储量管理
1-2 正負數的乘除法.
第二章:命题逻辑等值演算 主要内容: 本章与其他各章的联系 等值式与基本的等值式 等值演算与置换规则
Chapter 5 利率的風險結構與期間結構. Chapter 5 利率的風險結構與期間結構.
命 题 # 判 断 复合命题. 命 题 # 判 断 复合命题 一、复合命题概述 1.定义 复合命题(compound proposition) ,就是以命题作为直接构成成分的命题,或者,包含有其他命题成分的命题。 例如: ① 并非所有去过作案现场的人都是作案人; ② 张××是法官,并且,张××是中共党员;
成才之路 · 语文 人教版 · 必修2 路漫漫其修远兮 吾将上下而求索.
等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式,主析取范式与主合取范式 联结词完备集 可满足性问题与消解法
离散数学 东南大学 薛 晖 1.
第 二 章 逻 辑 代 数 基 础.
第三章:命题逻辑的推理理论 主要内容 推理的形式结构 自然推理系统P 本章与其他各章的联系 本章是第五章的特殊情况和先行准备.
如何寫工程計畫書 臺北市童軍會考驗委員會 高級考驗營 版.
离散数学─逻辑和证明 南京大学计算机科学与技术系
2019年1月2日星期三 离散  数学 计算机学院 冯伟森 2019年1月2日星期三.
類別 特性 計量 (1)測量時可讀出工件之正確尺寸 (2)多用於小量生產的產品,量測與檢驗尺寸是否合乎標準。
李伟庭老师 (彩虹村天主教英文中学老师) 相似三角形.
蔣梅香 資深協理 金融機構評等部 中華信用評等公司
电子电路中的信号分为两大类: 低电平 高电平 脉冲信号是跃变信号, 持续时间很短
公式的真值表 离散结构 西安工程大学 计算机学院 王爱丽.
塑膠模具設計 與 制造基礎知識 何秀定 2006/05/20.
第一章 逻辑代数基础 本章的重点: 本章的难点: 1.逻辑代数的基本公式和常用公式。 2.逻辑代数的基本定理。 3.逻辑函数的各种表示方法。
第二部分 集合论 第六章 集合代数 主要内容 集合的基本概念 属于、包含 幂集、空集 文氏图等 集合的基本运算 并、交、补、差等 集合恒等式
数字电路.
2012慈濟大學18週年校慶運動會 裁判研習 體育教學中心 張木山 教授.
大綱:整數的加法 整數的減法 蘇奕君 台灣數位學習科技股份有限公司
§3 命题演算的形式证明 一个数学系统通常由一些描述系统特有性质的陈述句所确定,这些陈述句称为假设,
第三章 开关理论基础.
第一章-第二节 –有理数的加法(2).
§3 布尔格与布尔代数 一、布尔代数 定义16.10:有补分配格称为布尔(Boole)格, 习惯上写成(B;≤)。
北师大版四年级数学下册 手拉手 —小数的混合运算、简算.
离散数学─逻辑和证明 南京大学计算机科学与技术系
1.8 完全平方公式(一) 锦州市实验学校 数学组(3).
平面向量.
平面向量的数量积.
第五单元 简易方程  用字母表示运算定律和计算公式 湖北省武汉市育才小学 万 婕.
Presentation transcript:

第二章 命题逻辑等值演算 主要内容 等值式与基本的等值式 等值演算与置换规则 析取范式与合取范式,主析取范式与主合取范式 联结词完备集 可满足性问题与消解法

2.1 等值式 定义2.1 若等价式AB是重言式,则称A与B等值,记作AB,并称AB是等值式 几点说明: 2.1 等值式 定义2.1 若等价式AB是重言式,则称A与B等值,记作AB,并称AB是等值式 几点说明: 定义中,A, B, 均为元语言符号 A或B中可能有哑元出现. 例如 (pq)  ((pq)(rr)) r为左边公式的哑元. 用真值表可检查两个公式是否等值 请验证: p(qr)  (pq) r p(qr) 不与 (pq) r 等值

等值式例题 例1 判断下列各组公式是否等值: (1) p(qr) 与 (pq) r 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 (pq)r p(qr) qr p q r pq 结论: p(qr)  (pq) r

等值式例题 (2) p(qr) 与 (pq) r 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 (pq)r p(qr) qr p q r pq 结论: p(qr) 与 (pq) r 不等值

基本等值式 双重否定律 AA 幂等律 AAA, AAA 交换律 ABBA, ABBA 结合律 (AB)CA(BC), (AB)CA(BC) 分配律 A(BC)(AB)(AC), A(BC)(AB)(AC) 德摩根律 (AB)AB (AB)AB 吸收律 A(AB)A, A(AB)A

基本等值式 零律 A11, A00 同一律 A0A. A1A 排中律 AA1 矛盾律 AA0 蕴涵等值式 ABAB 等价等值式 AB(AB)(BA) 假言易位 ABBA 等价否定等值式 ABAB 归谬论 (AB)(AB) A 特别提示:必须牢记这16组等值式,这是继续学习的基础

等值演算与置换规则 1. 等值演算——由已知的等值式推演出新的等值式的过程 2. 等值演算的基础: (1) 等值关系的性质:自反性、对称性、传递性 (2) 基本的等值式 (3) 置换规则(见3) 3. 置换规则 设 (A) 是含公式 A 的命题公式,(B) 是用公式 B 置换 (A) 中所有的 A 后得到的命题公式 若 BA,则 (B)(A)

等值演算的应用举例 证明两个公式等值 例2 证明 p(qr)  (pq)r 证 p(qr) 今后在注明中省去置换规则 注意:用等值演算不能直接证明两个公式不等值

等值演算的应用举例 证明两个公式不等值 例3 证明 p(qr) 与 (pq)r 不等值 证 方法一 真值表法, 见例1(2) 证 方法一 真值表法, 见例1(2) 方法二 观察法. 观察到000, 010是左边的成真赋值,是右边的成假赋值 方法三 先用等值演算化简公式,然后再观察 p(qr) pqr (pq)r (pq)r(pq)r 更容易看出前面的两个赋值分别是左边的成真赋 值和右边的成假赋值

等值演算的应用举例 判断公式类型: A为矛盾式当且仅当A  0 A为重言式当且仅当A  1 例4 用等值演算法判断下列公式的类型 例4 用等值演算法判断下列公式的类型 (1) q(pq) (2) (pq)(qp) (3) ((pq)(pq))r) 解 (1) q(pq)  q(pq) (蕴涵等值式)  q(pq) (德摩根律)  p(qq) (交换律,结合律)  p0 (矛盾律)  0 (零律) 矛盾式

判断公式类型 (2) (pq)(qp)  (pq)(qp) (蕴涵等值式)  (pq)(pq) (交换律)  1 重言式 (3) ((pq)(pq))r)  (p(qq))r (分配律)  p1r (排中律)  pr (同一律) 可满足式,101和111是成真赋值,000和010等是成假赋值.

基本等值式 双重否定律 幂等律 交换律 结合律 分配律 德摩根律 吸收律

基本等值式 零律 同一律 排中律 矛盾律 蕴涵等值式 等价等值式 假言易位 等价否定等值式 归谬论

2.2 析取范式与合取范式 基本概念 (1) 文字——命题变项及其否定的总称 (2) 简单析取式——有限个文字构成的析取式 2.2 析取范式与合取范式 基本概念 (1) 文字——命题变项及其否定的总称 (2) 简单析取式——有限个文字构成的析取式 p, q, pq, pqr, … (3) 简单合取式——有限个文字构成的合取式 p, q, pq, pqr, … (4) 析取范式——由有限个简单合取式组成的析取式 p, pq, pq, (pq)(pqr)(qr) (5) 合取范式——由有限个简单析取式组成的合取式 p, pq, pq, (pqp(pqr) (6) 范式——析取范式与合取范式的总称

范式概念 说明: 单个文字既是简单析取式,又是简单合取式 形如 pqr, pqr 的公式既是析取范式,又是合取范式

范式的性质 定理2.1 (1) 一个简单析取式是重言式当且仅当它同时含有某 个命题变项和它的否定式. (2) 一个简单合取式是矛盾式当且仅当它同时含有某个命题 变项和它的否定式. 定理2.2 (1) 一个析取范式是矛盾式当且仅当它每个简单合 取式都是矛盾式. (2) 一个合取范式是重言式当且仅当它的每个简单析取式都 是重言式.

命题公式的范式 定理2.3(范式存在定理) 任何命题公式都存在与之等值的析取范式与合取范式 公式A的析取(合取)范式与A等值的析取(合取)范式 求公式A的范式的步骤: (1) 消去A中的, (若存在) ABAB AB(AB)(AB) (2) 否定联结词的内移或消去  A A (AB)AB (AB)AB

命题公式的范式 (3) 使用分配律 A(BC)(AB)(AC) 求合取范式 A(BC) (AB)(AC) 求析取范式 公式范式的不足不惟一

求公式的范式 例5 求下列公式的析取范式与合取范式 (1) (pq)r (2) (pq)r 解 (1) (pq)r 例5 求下列公式的析取范式与合取范式 (1) (pq)r (2) (pq)r 解 (1) (pq)r  (pq)r (消去)  pqr (结合律) 最后结果既是析取范式(由3个简单合取式组成的析取式),又 是合取范式(由一个简单析取式组成的合取式)

求公式的范式 (2) (pq)r  (pq)r (消去第一个)  (pq)r (消去第二个)  (pr)(qr) (对分配律) 合取范式

极小项与极大项 定义2.4 在含有n个命题变项的简单合取式(简单析取式) 中,若每个命题变项均以文字的形式在其中出现且仅出现 一次,而且第i个文字出现在左起第i位上(1in),称这 样的简单合取式(简单析取式)为极小项(极大项). 几点说明: n个命题变项有2n个极小项和2n个极大项 2n个极小项(极大项)均互不等值 用mi表示第i个极小项,其中i是该极小项成真赋值的十进制表示. 用Mi表示第i个极大项,其中i是该极大项成假赋值的十进制表示. mi(Mi)称为极小项(极大项)的名称.

实例 由两个命题变项 p, q 形成的极小项与极大项 极小项 极大项 公式 成真赋值 名称 成假赋值 pq pq pq pq 0 0 0 1 1 0 1 1 m0 m1 m2 m3 pq pq pq pq M0 M1 M2 M3

mi与Mi的关系: mi  Mi, Mi  mi 实例 由三个命题变项 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 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 m0 m1 m2 m3 m4 m5 m6 m7 p  q  r p  q  r p  q  r p  q r p  q  r p  q  r p  q  r p  q r M0 M1 M2 M3 M4 M5 M6 M7 mi与Mi的关系: mi  Mi, Mi  mi

主析取范式与主合取范式 主析取范式——由极小项构成的析取范式 主合取范式——由极大项构成的合取范式 例如,n=3, 命题变项为 p, q, r 时, (pqr)(pqr)  m1m3 ——主析取范式 (pqr)(pqr)  M1M7——主合取范式 公式A的主析取(合取)范式——与A 等值的主析取(合取)范式 定理2.5 (主范式的存在惟一定理) 任何命题公式都存在与之等值的主析取范式和主合取范式, 并且是惟一的

求公式主范式的步骤 求公式主析取范式的步骤: 设公式A含命题变项p1,p2,…,pn (1) 求A的析取范式A=B1 B2 …  Bs , 其中Bj是简单合取 式 j=1,2, … ,s (2) 若某个Bj既不含pi, 又不含pi, 则将Bj展开成 Bj  Bj(pipi)  (Bjpi)(Bjpi) 重复这个过程, 直到所有简单合取式都是长度为n的极 小项为止 (3) 消去重复出现的极小项, 即用mi代替mimi (4) 将极小项按下标从小到大排列

求公式主范式的步骤 求公式的主合取范式的步骤: 设公式A含命题变项p1,p2,…,pn (1) 求A的合取范式A=B1B2 … Bs , 其中Bj是简单析取 式 j=1,2, … ,s (2) 若某个Bj既不含pi, 又不含pi, 则将Bj展开成 Bj  Bj(pipi)  (Bjpi)(Bjpi) 重复这个过程, 直到所有简单析取式都是长度为n的极 大项为止 (3) 消去重复出现的极大项, 即用Mi代替MiMi (4) 将极大项按下标从小到大排列

实例 例6 (1) 求公式 A=(pq)r的主析取范式和主合取范式 解 (pq)r  (pq)r (析取范式) ①  (pq)(rr)  (pqr)(pqr)  m6m7 ② r  (pp)(qq)r  (pqr)(pqr)(pqr)(pqr)  m1m3m5m7 ③ ②, ③代入①并排序,得 (pq)r  m1m3m5 m6m7 (主析取范式)

实例 (pq)r  (pr)(qr) (合取范式) ④ pr  p(qq)r  (pqr)(pqr)  M0M2 ⑤ qr  (pp)qr  (pqr)(pqr)  M0M4 ⑥ ⑤, ⑥代入④ 并排序,得 (pq)r  M0M2M4 (主合取范式)

主范式的应用 1.求公式的成真成假赋值 设公式A含n个命题变项, A的主析取范式有s个极小项, 则A 有s个成真赋值, 它们是极小项下标的二进制表示, 其余2n-s 个赋值都是成假赋值 例如 (pq)r  m1m3m5 m6m7 成真赋值为 001, 011, 101, 110, 111, 成假赋值为 000, 010, 100. 类似地,由主合取范式也立即求出成假赋值和成真赋值.

主范式的应用 2. 判断公式的类型 设A含n个命题变项. A为重言式  A的主析取范式含全部2n个极小项 2. 判断公式的类型 设A含n个命题变项. A为重言式  A的主析取范式含全部2n个极小项  A的主合取范式不含任何极大项, 记为1. A为矛盾式  A的主合析取范式含全部2n个极大项  A的主析取范式不含任何极小项, 记为0. A为非重言式的可满足式  A的主析取范式中至少含一个、但不是全 部极小项  A的主合取范式中至少含一个、但不是全 部极大项.

主范式的应用 例7 用主析取范式判断公式的类型: (1) A (pq)q (2) B p(pq) (3) C (pq)r 解 (1) A  ( pq)q  ( pq)q  0 矛盾式 (2) B   p(pq)  1  m0m1m2m3 重言式 (3) C  (pq)r  (pq)r  (pqr)(pqr)(pqr) (pqr)(pqr)(pqr)  m0m1m3 m5m7 非重言式的可满足式

主范式的应用 3. 判断两个公式是否等值 例8 用主析取范式判以下每一组公式是否等值 ⑴ p(qr) 与 (pq)r 3. 判断两个公式是否等值 例8 用主析取范式判以下每一组公式是否等值 ⑴ p(qr) 与 (pq)r ⑵ p(qr) 与 (pq)r 解 p(qr) = m0m1m2m3 m4m5 m7 (pq)r = m0m1m2m3 m4m5 m7 (pq)r = m1m3 m4m5 m7 显见,⑴中的两公式等值,而⑵的不等值.

主范式的应用 4. 解实际问题 例9 某单位要从A,B,C三人中选派若干人出国考察, 需满足下 述条件: (1) 若A去, 则C必须去; 问有几种可能的选派方案? 解 记 p:派A去, q:派B去, r:派C去 (1) pr, (2) qr, (3) (pq)(pq) 求下式的成真赋值 A=(pr)(qr)((pq)(pq))

主范式的应用 求A的主析取范式 A=(pr)(qr)((pq)(pq))  ((pq)(pr)(rq)(rr)) ((pq)(pq))  ((pq)(pq))((pr)(pq)) ((rq)(pq))((pq)(pq)) ((pr)(pq))((rq)(pq))  (pqr)(pqr) 成真赋值:101,010 结论: 方案1 派A与C去, 方案2 派B去

用成真赋值和成假赋值确定主范式 由主析取范式确定主合取范式 例10 设A有3个命题变项, 且已知A= m1m3m7, 求A的主合取 范式. 解 A的成真赋值是1,3,7的二进制表示, 成假赋值是在主析取 范式中没有出现的极小项的下角标0,2,4,5,6的二进制表示, 它 们恰好是A的主合取范式的极大项的下角标, 故 A  M0M2M4M5M6 由主合取范式确定主析取范式 用真值表确定主范式

2.3 联结词的完备集 定义2.6 称F:{0,1}n {0,1} 为n元真值函数. 2.3 联结词的完备集 定义2.6 称F:{0,1}n {0,1} 为n元真值函数. {0,1}n={00…0, 00…1, …, 11…1},包含 个长为n的0,1符号串. 共有 个n元真值函数. 1元真值函数 p 0 0 0 1 1 1 0 1 0 1

真值函数 2元真值函数 p q 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1

公式与真值函数 任何一个含n个命题变项的命题公式A都对应惟一的一个n元 真值函数 F , F 恰好为A的真值表. 等值的公式对应的真值函数相同. 例如:pq, pq 都对应

联结词完备集 定义2.7 设S是一个联结词集合,如果任何n(n1) 元真值函 数都可以由仅含S中的联结词构成的公式表示,则称S是联结 证明 由范式存在定理可证

联结词完备集 推论 以下都是联结词完备集 (1) S1 = {, , , } (2) S2 = {, , , , } 证明 (1),(2) 在联结词完备集中加入新的联结词后仍为完备集 (3) AB  (AB) (4) AB  (AB) (5) ABAB {,,,}不是联结词完备集, 0不能用它表示 它的子集{},{},{},{},{,},{,,}等都不是

复合联结词 定义2.8 设 p, q 为两个命题, (pq)称作p与q的与非式, 记作 (pq) 称作 p 与 q 的或非式, 记作 pq, 即 pq  (pq),  称为或非联结词 定理2.7 {}与{}为联结词完备集. 证明 {, , }为完备集 p  pp  (pp)  pp pq  (pq)  pq  (pp)(qq) pq  (pq)  (pq)  (pq)(pq) 得证{}为联结词完备集. 对{}类似可证

2.4 可满足性问题与消解法 不含任何文字的简单析取式称作空简单析取式,记作. 规定是不可满足的. 约定:简单析取式不同时含某个命题变项和它的否定 S:合取范式, C:简单析取式, l:文字, :赋值, 带下角标或  文字l的补lc:若l=p,则lc=p;若l=p,则lc=p. SS:S是可满足的当且仅当S 是可满足的 定义2.9 设C1=lC1, C2=lcC2, C1和C2不含l和lc, 称C1C2为 C1和C2(以l和lc为消解文字)的消解式或消解结果, 记作 Res(C1,C2) 例如, Res(pqr, pqs)= qrs

消解规则 定理2.8 C1C2Res(C1,C2) 证 记C= Res(C1,C2)=C1C2, 其中l和lc为消解文字, C1=lC1, C2=lcC2, 且C1和C2不含l和lc. 假设C1C2是可满足的, 是它的满足赋值, 不妨设(l)=1. C2必含有文字l l, lc且(l )=1. C中含有l, 故满足C. 反之, 假设C是可满足的, 是它的满足赋值. C必有l 使得 (l )=1, 不妨设C1含l, 于是满足C1. 把扩张到l(和lc)上: 若l=p, 则令(p)=0; 若lc=p, 则令(p)=1. 恒有(lc)=1, 从而 满足C2. 得证C1C2是可满足的. 注意: C1C2与Res(C1,C2)有相同的可满足性, 但不一定等值.

消解序列与合取范式的否证 定义2.10 设S是一个合取范式, C1,C2,,Cn是一个简单析取式 序列. 如果对每一个i(1in), Ci是S的一个简单析取式或者是 Res(Cj,Ck)(1j<k<i), 则称此序列是由S导出Cn的消解序列. 当 Cn=时, 称此序列是S的一个否证. 定理2.9 一个合取范式是不可满足的当且仅当它有否证. 例11 用消解规则证明S=(pq)(pqs)(qs)q是不可 满足的. 证 C1=pq, C2= pqs, C3=Res(C1,C2)=qs, C4=qs, C5=Res(C3,C4)=q, C6=q, C7=Res(C5,C6)=, 这是S的否证.

消解算法 消解算法 输入: 合式公式A 输出: 当A是可满足时, 回答“Yes”; 否则回答“No”. 1. 求A的合取范式S 2. 令S0, S2, S1S的所有简单析取式 3. For C1S0和C2S1 4. If C1, C2可以消解 then 5. 计算CRes(C1,C2) 6. If C= then 7. 输出“No”, 计算结束 8. If CS0且C S1 then 9. S2S2{C}

消解算法 10. For C1S1, C2S1且C1C2 11. If C1, C2可以消解 then 12. 计算CRes(C1,C2) 13. If C= then 14. 输出“No”, 计算结束 15. If CS0且C S1 then 16. S2S2{C} 17. If S2= then 18. 输出“Yes”, 计算结束 19. Else S0S0S1, S1S2, S2, goto 3

消解算法例题 例12 用消解算法判断下述公式是否是可满足的: p(pq)(pq)(qr)(qr) 解 S= p(pq)(pq)(qr)(qr) 循环1 S0=, S1={p, pq, pq, qr, qr}, S2= Res(pq, pq)=p Res(pq, qr)=pr Res(pq, qr)= pr Res(qr, qr)=q S2={pr, pr, q} 循环2 S0={p, pq, pq, qr, qr}, S1={pr, pr, q}, S2= Res(pq, q)=p

消解算法例题 Res(qr, pr)=pq Res(qr, pr)=pq Res(pr, pr)=p S2= 输出“Yes”

第二章 习题课 主要内容 等值式与等值演算 基本等值式(16组,24个公式) 主析取范式与主合取范式 联结词完备集 消解法

基本要求 深刻理解等值式的概念 牢记基本等值式的名称及它们的内容 熟练地应用基本等值式及置换规则进行等值演算 理解文字、简单析取式、简单合取式、析取范式、合取范式的概念 深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系,并理解简单析取式与极小项的关系 熟练掌握求主范式的方法(等值演算、真值表等) 会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值 会将公式等值地化成指定联结词完备集中的公式 会用命题逻辑的概念及运算解决简单的应用问题 掌握消解规则及其性质 会用消解算法判断公式的可满足性

练习1:概念 1. 设A与B为含n个命题变项的公式,判断下列命题是否为真? (1) AB当且仅当A与B有相同的主析取范式 (2) 若A为重言式,则A的主合取范式为0 (3) 若A为矛盾式,则A的主析取范式为1 (4) 任何公式都能等值地化成{, }中的公式 (5) 任何公式都能等值地化成{, , }中的公式 真 假 假 假 真 说明: (2) 重言式的主合取范式不含任何极大项,为1. (3) 矛盾式的主合析范式不含任何极小项, 为0. (4) {, }不是完备集,如矛盾式不能写成{, }中的公式. (5) {, }是完备集.

练习2: 判断公式类型 2. 判断下列公式的类型: (1) (pq)(qp) 解 用等值演算法求主范式 (pq)(qp) 解 用等值演算法求主范式 (pq)(qp)  (pq)(qp)  (pq)(qp)  (pq)(pq)(pq)(pq)  m2  m1  m3  m0  m0  m1  m2  m3 主析取范式  1 主合取范式 重言式

练习题2(续) (2) (pq)q 解 用等值演算法求公式的主范式 (pq)q  (pq)q  pqq 解 用等值演算法求公式的主范式 (pq)q  (pq)q  pqq  0 主析取范式  M0  M1  M2  M3 主合取范式 矛盾式

练习2(续) (3) (pq)p 解 用等值演算法求公式的主范式 (pq)p  (pq)p  p 解 用等值演算法求公式的主范式 (pq)p  (pq)p  p  (pq)(pq)  m0  m1 主析取范式  M2  M3 主合取范式 非重言式的可满足式

练习3:求公式的主范式 3.已知命题公式A中含3个命题变项p, q, r,并知道它的成真 赋值为001, 010, 111, 求A的主析取范式和主合取范式,及A对 应的真值函数. 解 A的主析取范式为m1  m2  m7 A的主合取范式为M0  M3  M4  M5  M6 p q r F p q r F 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 1

练习4:联结词完备集 4.将A = (pq)r改写成下述各联结词集中的公式: (1) {, , } (2) {, } (3) {, } (4) {, } (5) {} (6) {} 解 (1) (pq)r  (pq)r (2) (pq)r  (pq)r (3) (pq)r  (pq)r  ((pq)r)

练习4 解答 (4) (pq)r  ((pq)r)  ((pq)r)  ((pp)(qq)(rr) 说明:答案不惟一

练习5:应用题 5. 某公司要从赵、钱、孙、李、周五名新毕业的大学生中选 派一些人出国学习. 选派必须满足以下条件: (1) 若赵去,钱也去. (2) 李、周两人中至少有一人去 (3) 钱、孙两人中去且仅去一人. (4) 孙、李两人同去或同不去. (5) 若周去,则赵、钱也去. 用等值演算法分析该公司如何选派他们出国?

练习5解答 解此类问题的步骤: 1.设简单命题并符号化 2. 用复合命题描述各条件 3. 写出由复合命题组成的合取式 4. 将合取式成析取式(最好是主析取范式) 5. 求成真赋值, 并做出解释和结论

练习5解答 解 1. 设简单命题并符号化 设 p: 派赵去,q: 派钱去,r: 派孙去,s: 派李去,u: 派周去 2. 写出复合命题 (3) 钱、孙两人中去且仅去一人 (qr)(qr) (4) 孙、李两人同去或同不去 (rs)(rs) (5) 若周去,则赵、钱也去 u(pq)

练习5解答 3. 设(1)—(5)构成的合取式为A A = (pq)(su)((qr)(qr)) ((rs)(rs))(u(pq)) 4. 化成析取式 A  (pqrsu)(pqrsu) 结论:由上述析取式可知,A的成真赋值为00110与11001, 派孙、李去(赵、钱、周不去) 派赵、钱、周去(孙、李不去)

练习5解答 A  (pq)((qr)(qr)) (su)(u(pq)) ((rs)(rs)) B1=(pq)((qr)(qr))  ((pqr)(pqr)(qr)) (分配律) B2=(su)(u(pq))  ((su)(pqs)(pqu)) (分配律) B1B2  (pqrsu)(pqrsu) (qrsu)(pqrs)(pqru) 再令 ((rs)(rs))=B3,则 B1B2B3  (pqrsu)(pqrsu)

练习6:消解法 6. 构造公式A=(pq)( qr) (pq)r的否证, 从而证明 它是矛盾式. 解 消解序列: 解 消解序列: ① pq A的简单析取式 ② pq A的简单析取式 ③ q ①,②消解 ④ qr A的简单析取式 ⑤ r A的简单析取式 ⑥ q ④,⑤消解 ⑦  ③,⑥消解 这是A的一个否证, 从而证明A是矛盾式.

练习7:消解法 7. 用消解法判断下述公式是否是可满足的: (pq)(qr)(qr) 7. 用消解法判断下述公式是否是可满足的: (pq)(qr)(qr) 解 S=(pq)(qr)(qr) 第1次循环 S0=,S1={pq, qr, qr}, S2= pq, qr 消解得到pr qr, qr消解得到r S2={pr,r} 第2次循环 S0={pq, qr, qr},S1={pr,r}, S2= S2= 输出“Yes”,计算结束.