当前位置：文档之家 › 离散数学-命题逻辑等值演算-范式

离散数学-命题逻辑等值演算-范式

  • 格式：pdf
  • 大小：327.25 KB
  • 文档页数：53

下载文档原格式

  / 53

合集下载

离散数学,命题逻辑等值演算

离散数学,命题逻辑等值演算
定理2.5
任何命题公式都存在与之等值的主 析取范式和主合取范式，并且是唯 一的。
证明： （1）存在性：等值演算 （2）唯一性：反证法
例题与练习
【例2.8】求主析取范式与主合取范式： (p→q)↔r
合取范式 （p∨r) ∧ (¬q∨r) ∧ (¬p∨q∨¬r)
析取范式 （p∧¬q∧¬r）∨（ ¬p∧r ）∨（ q∧r ）
p(qr）
1 1 1 1 1 1 0 1
(pq)r
0 1 0 1 1 1 0 1
(p∧q)r
1 1 1 1 1 1 0 1
十六组重要的等值式（模式）
• 1.双重否定律 A¬¬A
• 2.幂等律 A∧A A，A∨A A
• 3.交换律 A∨B B∨A，A∧B B∧A
• 4.结合律 (A∨B)∨C A∨(B∨C) (A∧B)∧C A∧(B∧C)
2.3 联结词的完备集
定义2.6
n元真值函数F：{0,1}n →{0,1}
定理
• 每个真值函数，都一一对应一个真值表。每个真 值函数，都存在许多与之等值的命题公式。反之， 每个命题公式对应唯一的与之等值的真值函数。
定义2.7
• 设S是联结词集合，如果任何n元真值函数 都可以由仅含S中的联结词构成的公式表 示，则称S是联结词完备集。
p∧q∧r
成真赋值
000 001 010 011 100 101 110 111
名称
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
成假赋值 名称
000
M0
001

离散数学结构 第3章 命题逻辑的推理理论复习

离散数学结构 第3章 命题逻辑的推理理论复习

第3章命题逻辑的推理理论主要内容1. 推理的形式结构：①推理的前提②推理的结论③推理正确④有效结论2. 判断推理是否正确的方法：①真值表法②等值演算法③主析取范式法3. 对于正确的推理，在自然推理系统P中构造证明4. ①自然推理系统P的定义②自然推理系统P的推理规则：前提引入规则、结论引入规则、置换规则、假言推理规则、附加规则、化简规则、拒取式规则、假言三段式规则、构造性二难规则、合取引入规则。

③附加前提证明法④归谬法学习要求1. 理解并记住推理的形式结构的三种等价形式，即①{A1,A2,…,A k}├B②A1∧A2∧…∧A k→B③前提与结论分开写：前提：A1,A2,…,A k结论：B在判断推理是否正确时，用②；在P系统中构造证明时用③。

2. 熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。

3. 牢记P系统中的各条推理规则。

4. 对于给定的正确推理，要求在P系统中给出严谨的证明序列。

5. 会用附加前提证明法和归谬法。

3.1 推理的形式结构定义3.1设A1,A2,…,A k和B都是命题公式，若对于A1,A2,…,A k和B中出现的命题变项的任意一组赋值，或者A1∧A2∧…∧A k为假，或者当A1∧A2∧…∧A k为真时，B也为真，则称由前提A1,A2,…,A k推出B的推理是有效的或正确的，并称B是有效结论。

二、有效推理的等价定理定理3.1命题公式A1,A2,…,A k推B的推理正确当且仅当(A1∧A2∧…∧A k )→B为重言式。

A k为假，或者A1∧A2∧…∧A k和B同时为真，这正符合定义3.1中推理正确的定义。

由此定理知，推理形式：前提：A1,A2,…,A k结论：B是有效的当且仅当(A1∧A2∧…∧A k)→B为重言式。

(A1∧A2∧…∧A k)→B称为上述推理的形式结构。

从而推理的有效性等价于它的形式结构为永真式。

于是，推理正确{A1,A2,…,A k} B可记为A1∧A2∧…∧A k B其中同一样是一种元语言符号，用来表示蕴涵式为重言式。

离散数学-第二章命题逻辑等值演算习题及答案

离散数学-第二章命题逻辑等值演算习题及答案

第二章作业评分要求：1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分2. 给出每小题得分(注意: 写出扣分理由)3. 总得分在采分点1处正确设置.一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方法每种方法至少使用一次):说明证1. p ⇔(p ∧q)∨(p ∧¬q)解逻辑方程法设 p ↔((p ∧q)∨(p ∧¬q)) =0, 分两种情况讨论:⎩⎨⎧=⌝∧∨∧=0)()(1)1(q p q p p 或者 ⎩⎨⎧=⌝∧∨∧=1)()(0)2(q p q p p (1)(2)两种情况均无解, 从而, p ↔(p ∧q)∨(p ∧¬q)无成假赋值, 为永真式. 等值演算法(p ∧q)∨(p ∧¬q)⇔ p ∧(q ∨¬q)∧对∨的分配率⇔ p ∧1 排中律⇔ p 同一律 真值表法2. (p→q)∧(p→r)⇔p→(q∧r)等值演算法(p→q)∧(p→r)⇔ (¬p∨q)∧(¬p∨r)蕴含等值式⇔¬p∨(q∧r)析取对合取的分配律⇔ p→(q∧r)蕴含等值式3. ¬(p↔q)⇔(p∨q)∧¬(p∧q)等值演算法¬(p↔q)⇔¬( (p→q)∧(q→p) )等价等值式⇔¬( (¬p∨q)∧(¬q∨p) )蕴含等值式⇔¬( (¬p∧¬q)∨(p∧q) )合取对析取分配律, 矛盾律, 同一律⇔ (p∨q)∧¬(p∧q)德摩根律4. (p∧¬q)∨(¬p∧q)⇔(p∨q)∧¬(p∧q)等值演算法(p∧¬q)∨(¬p∧q)⇔ (p∨q)∧¬(p∧q)析取对合取分配律, 排中律, 同一律说明: 用真值表法和解逻辑方程法证明相当于证明为永真式.等值演算法证明时每一步后面最好注明理由以加深印象, 熟练后可以不写. 由于等值演算法证明具有较强的技巧性, 平时应注意总结心得.二. 求下列公式的主析取范式与主合取范式(等值演算法与用成真赋值或成假赋值求解都至少使用一次):1.2.3.4.1. (¬p→q)→(¬q∨p)解(¬p→q)→(¬q∨p)⇔ (p∨q)→(¬q∨p)蕴含等值式⇔ (¬p∧¬q)∨(¬q∨p)蕴含等值式, 德摩根律⇔ (¬p∧¬q)∨¬q ∨ p结合律⇔ p∨¬q吸收律, 交换律⇔ M1因此, 该式的主析取范式为m0∨m2∨m32. (¬p→q)∧(q∧r)解逻辑方程法设 (¬p→q)∧(q∧r) =1, 则¬p→q=1且 q∧r=1,解得q=1, r=1, p=0 或者 q=1, r=1, p=1, 从而所求主析取范式为 m3∨m7, 主合取范式为M0∧M1∧M2∧M4∧M5∧M6等值演算法(¬p→q)∧(q∧r)(p q)(q r) 蕴含等值式(p q r)(q r) 对分配律, 幂等律(p q r) (p q r)(p q r) 同一律, 矛盾律, 对分配律m7 m3主合取范式为M0∧M1∧M2∧M4∧M5∧M63. (p↔q)→r解逻辑方程法设 (p↔q)→r =0, 解得 p=q=1, r=0 或者 p=q=0, r=0, 从而所求主合取范式为M0∧M6, 主析取范式为m1∨m2∨m3∨m4∨m5∨m7等值演算法(p↔q)→r((p q)(q p))r 等价等值式((p q)(q p))r 蕴含等值式(p q)(q p)r 德摩根律, 蕴含等值式的否定(参见PPT)(p q r)(q p r) 对分配律, 矛盾律, 同一律M0 M6主析取范式为m1∨m2∨m3∨m4∨m5∨m74. (p→q)∧(q→r)解等值演算法(p→q)∧(q→r)(p q)(q r) 蕴含等值式(p q)(p r)(q r) 对分配律, 矛盾律, 同一律(p q r)(p q r) (p q r)(p q r)(p q r)(p q r)m1 m0 m3 m7主合取范式为M2 M4 M5 M6.解逻辑方程法设 (p q) (q r) = 1, 则p q =1 且 q r =1.前者解得: p=0, q=0; 或者 p=0, q=1; 或者 p=1, q=1.后者解得: q=0, r=0; 或者 q=0, r=1; 或者 q=1, r=1.综上可得成真赋值为 000, 001, 011, 111, 从而主析取范式为m0m1m3m7, 主合取范式为M2 M4 M5 M6.真值表法公式 (p q) (q r) 真值表如下:p q r(p q) (qr)00010011010001111000101011001111013724 M5 M6.。

离散数学-----命题逻辑

离散数学-----命题逻辑

离散数学-----命题逻辑逻辑：是研究推理的科学。

公元前四世纪由希腊的哲学家亚里斯多德首创。

作为一门独立科学，十七世纪，德国的莱布尼兹(Leibniz)给逻辑学引进了符号, 又称为数理逻辑(或符号逻辑)。

逻辑可分为：1. 形式逻辑（是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。

）→数理逻辑（是用数学方法研究推理的形式结构和规律的数学学科。

它的创始人Leibniz，为了实现把推理变为演算的想法，把数学引入了形式逻辑中。

其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。

）2. 辩证逻辑（是研究反映客观世界辩证发展过程的人类思维的形态的。

）一、命题及其表示方法1、命题数理逻辑研究的中心问题是推理,而推理的前提和结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位。

基本概念：命题：能够判断真假的陈述句。

命题的真值：命题的判断结果。

命题的真值只取两个值:真（用T(true)或1表示）、假（用F(false)或0表示）。

真命题：判断为正确的命题，即真值为真的命题。

假命题：判断为错误的命题，即真值为假的命题。

因而又可以称命题是具有唯一真值的陈述句。

判断命题的两个步骤：1、是否为陈述句；2、是否有确定的、唯一的真值。

说明：（1）只有具有确定真值的陈述句才是命题。

一切没有判断内容的句子，无所谓是非的句子，如感叹句、祁使句、疑问句等都不是命题。

（2）因为命题只有两种真值，所以“命题逻辑”又称“二值逻辑”。

（3）“具有确定真值”是指客观上的具有，与我们是否知道它的真值是两回事。

2、命题的表示方法在书中，用大写英文字母A,B,…,P,Q或带下标的字母P1,P2,P3 ,…,或数字(1),*2+, …,等表示命题，称之为命题标识符。

命题标识符又有命题常量、命题变元和原子变元之分。

命题常量：表示确定命题的命题标识符。

命题变元：命题标识符如仅是表示任意命题的位置标志，就称为命题变元。

《离散数学》02命题逻辑等值演算

《离散数学》02命题逻辑等值演算
类似的讨论可知，若Ai是含n个命题变项的简单合取式，且 Ai为矛盾式，则Ai中必同时含某个命题变项及它的否定式， 反之亦然。
2.2 析取范式和合取范式
定理2.1 (1)一个简单析取式是重言式当且仅当它同时含有某个命题
变项及它的否定式。 (2)一个简单合取式是矛盾式当且仅当它同时含有某个命题
变项及它的否定式。 定义2.3 (1)由有限个简单合取式构成的析取式称为析取范式
A∨1 1,A∧0 0 A∨0 A，A∧1 A A∨┐A 1 A∧┐A 0 A→B ┐A∨B AB (A→B)∧(B→A) A→B ┐B→┐A AB ┐A┐B (A→B)∧(A→┐B) ┐A
对偶原理
一个逻辑等值式，如果只含有┐、∨、∧、0、1 那么同时
把∨和∧互换 把0和1互换 得到的还是等值式。
(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
基本等值式
8.零律 9.同一律 10.排中律 11.矛盾律 12.蕴涵等值式 13.等价等值式 14.假言易位 15.等价否定等值式 16.归谬论
例2.5 解答
(1) (p→q)∧p→q
(┐p∨q)∧p→q
（蕴涵等值式）
┐((┐p∨q)∧p)∨q
（蕴涵等值式）
(┐(┐p∨q)∨┐p)∨q
（德摩根律）
((p∧┐q)∨┐p)∨q
（德摩根律）
((p∨┐p)∧(┐q∨┐p))∨q （分配律）
(1∧(┐q∨┐p))∨q

离散数学 等值式 范式 消解算法

离散数学 等值式 范式 消解算法
ABAB AB(AB)(AB) (2) 否定联结词的内移或消去 A A (AB)AB (AB)AB
15
命题公式的范式
(3) 使用分配律 A(BC)(AB)(AC) A(BC) (AB)(AC)
求合取范式 求析取范式
公式范式的不足不惟一
16
求公式的范式
例5 求下列公式的析取范式与合取范式 (1) (pq)r (2) (pq)r
p q r 1 1 0 M6
p q r 1 1 1 M7
mi与Mi的关系： mi Mi, Mi mi
23
主析取范式与主合取范式
主析取范式——由极小项构成的析取范式 主合取范式——由极大项构成的合取范式 例如，n=3, 命题变项为 p, q, r 时，
(pqr)(pqr) m1m3 ——主析取范式 (pqr)(pqr) M1M7——主合取范式 公式A的主析取(合取)范式——与A 等值的主析取(合取)范式 定理2.5 (主范式的存在惟一定理) 任何命题公式都存在与之等值的主析取范式和主合取范式, 并且是惟一的
等值演算与置换规则
1. 等值演算——由已知的等值式推演出新的等值式的过程 2. 等值演算的基础：
(1) 等值关系的性质：自反性、对称性、传递性 (2) 基本的等值式 (3) 置换规则（见3） 3. 置换规则 设 (A) 是含公式 A 的命题公式，(B) 是用公式 B 置换 (A) 中所有的 A 后得到的命题公式 若 BA，则 (B)(A)
(pr)(qr) （对分配律） 合取范式
18 r (pq) r 消去 ((pq) r) (r (pq)) 消去 ( (pq) r) (r pq) 消去
((p q) r) ( p q r ) 否定内移
合取范式：

《离散数学》命题逻辑

《离散数学》命题逻辑
由原子命题组合而成的命题称为复合 命题（compound proposition）。
例如：
和 e 都是无理数。 6和8至少有一个是合数。 说刘老师讲课不好是不正确的。 不下雨我就去买书。
7
命题与命题联结词
将命题连接起来的方式叫做命题联结词
（ proposition connective ） 或 命 题 运 算 符
3
命题与命题联结词
逻辑
如何表示？ 如何“操作”？
非真即假的陈述句称为命题（proposition）。 一个命题如果是对的或正确的，则称为真命
题，其真值为“真”（true），常用T或1表示； 一个命题如果是错的或不正确的，则称为假
命题，其真值为“假”（false），常用F或0表示。
4
命题与命题联结词
32
命题公式及其分类
为简化公式的形式，作如下规定：
(1) 优先级 , (∧, ∨), (, ) (2) 公式 (~p) 的括号可以省略，写成 ~p (3) 整个公式最外层的括号可以省略
例1
(((p)∧q)(q∨p)) p∧q q∨p
例2
p∧q∨r 不是 命题公式 应写作 (p∧q)∨r 或 p∧(q∨r)
例 判断下列句子哪些是命题，哪些不是
这门课程题为“离散数学”。 这门“离散数学”讲得好吗？ X 这门“离散数学”讲得真好！ X 请学习“离散数学” 。 X 5是素数。 太阳从西方升起。 如果明天晴，而且我有空，我就去踢球。 天王星上没有生命。 x + 3 > 5。 X 5 本命题是假的。X
俞伯牙和钟子期是好朋友。 俞伯牙是好朋友 ∧ 钟子期是好朋友 俞伯牙 ∧ 钟子期是好朋友 Friend (俞伯牙,钟子期)
23

离散数学第2章 命题逻辑等值演算

离散数学第2章 命题逻辑等值演算
6/2/2013 9:02 PM Discrete Math. , Chen Chen 15
例2.6
CHAPTER TWO
例2.6 在某次研讨会的休息时间，3名与会者根据王教授的口音 对他是哪个省市的人进行了判断： 甲说王教授不是苏州人，是上海人。
乙说王教授不是上海人，是苏州人。 丙说王教授不是上海人，也不是杭州人。 听完3人的判断，王教授笑着说，他们3人中有一人说得全对， 有一人说对了一半，有一人说得全不对。试用逻辑演算法分析 王教授到底是哪里的人？ 解： 设命题 p, q, r分别表示 ： 王教授是苏州、上海、杭州人。 则p, q, r中必有一个真命题，两个假命题。要通过逻辑演算将 真命题找出来。 设： 甲的判断为： A1= ┐p∧q; 乙的判断为：A2= p∧┐q; 丙的 判断为：A3= ┐q∧r。
等值式模式
CHAPTER TWO
当命题公式中变项较多时，用上述方法判断两个公式是否 等值计算量很大。为此，人们将一组经检验为正确的等值式作 为等值式模式，通过公式间的等值演算来判断两公式是否等值。 常用的等值式模式如下：
1.双重否定律：A⇔ ┐(┐A) 2.幂等律：A⇔A∨A, A⇔A∧A
3.交换律: A∨B⇔B∨A, A∧B⇔B∧A 4.结合律: (A∨B)∨C⇔A∨(B∨C), (A∧B)∧C⇔A∧(B∧C) 5.分配律：A∨(B∧C)⇔(A∨B)∧(A∨C) (∨对∧的分配律)
⇔ ┐(┐p∨q)∨r (蕴含等值式，置换规则） ⇔ (p∧┐q)∨r (德摩根律，置换规则）
⇔(p∨r)∧(┐q∨r)(分配律，置换规则） 为简便起见, 以后凡用到置换规则时, 均不必标出。
6/2/2013 9:02 PM Discrete Math. , Chen Chen 10

离散数学-第二章命题逻辑

离散数学-第二章命题逻辑

设A( P1，P2，…,Pn )是一个命题公式，
P1，P2，…,Pn是出现于其中的全部命题变元，对P1， P2，…,Pn分别指定一个真值,称为对P1，P2，…,Pn公式A 的一组真值指派。
列出命题公式A在P1，P2，…,Pn的所有2n种真值指 派下对应的真值，这样的表称为A的真值表。
16
例3
值表。
例12 用符号形式表示下列命题。
（1） （2） 如果明天早上下雨或下雪，那么我不去学校 如果明天早上不下雨且不下雪，那么我去学校。
（3）
（4）
如果明天早上不是雨夹雪，那么我去学校。
只有当明天早上不下雨且不下雪时，我才去学校。 解 令P：明天早上下雨； Q：明天早上下雪； R：我去学校。 （1）（P∨Q）→ ¬ R； （2）（¬ ∧¬ P Q）→R； （3）¬ (P∧Q）→R （4）R→（¬ ∧¬ Q） P
4
例4
2．合取“∧” 定义2.2.2
设P和Q是两个命题，则P和Q的合取 是一个复合命题，记作“P ∧ Q”（读作“P且Q”）。
当且仅当命题P和Q均取值为真时，P ∧ Q才取值为真。
P 0 0 1 1 Q 0 1 0 1 P∧Q 0 0 0 1
例5
设P：我们去看电影。Q：房间里有十张桌子。则
P ∧ Q表示“我们去看电影并且房间里有十张桌子。”
5
3. 析取“∨” 定义2.2.3
设P和Q是两个命题，则P和Q的析取是一个复 合命题，记作“P∨Q”（读作“P或Q”）。
当且仅当P和Q至少有一个取值为真时，P∨Q取值为真。
P
0 0 1 1 Q 0 1 0 1 P∨Q 0 1 1 1
例6 设命题P：他可能是100米赛跑冠军；
Q：他可能是400米赛跑冠军。

离散数学总复习-知识点

离散数学总复习-知识点

离散数学总复习第1章命题逻辑一、命题的判断例：1、仁者无敌！2、x+y<23、如果雪是红的，那么地球是月亮的卫星。

4、我正在说谎。

二、命题符号化例：1、蓝色和黄色可以调成绿色。

2、付明和杨进都是运动员。

3、刘易斯是百米游泳冠军或百米跨栏冠军。

4、李飞现在在宿舍或在图书馆。

5、只要天不下雨，我就步行上学校。

6、只有天不下雨，我才步行上学校。

7、并非只要你努力了，就一定成功。

三、主范式1、会等值演算；2、主合取和主析取范式的相互转换。

例：求命题公式P∨Q的主析取范式和主合取范式。

3、根据主范式进行方案的选择例1：某科研所要从3名科研骨干A,B,C中挑选1-2名出国进修，由于工作需要，选派需同时满足条件：（1）若A去，则C同去；（2）只有C不去，B才去；（3）只要C不去，则A或B就可以去。

问有哪些选派方案？例2：甲、乙、丙、丁四人有且仅有两个人参加比赛，下列四个条件均要满足：（1）甲和乙有且只有一人参加；（2）丙参加，则丁必参加；（3）乙和丁至多有一人参加；（4）丁不参加，甲也不会参加。

问哪两个人参加了比赛？四、简单的推理例1：如果明天天气好我们就去爬长城。

明天天气好。

所以我们去爬长城。

例3：课后习题16第2章谓词逻辑一、谓词逻辑中的命题符号化例：1、所有运动员都是强壮的2、并非每个实数都是有理数3、有些实数是有理数二、量词的辖域，约束变元换名、自由变元代替例：1、∀x(P(x)∨∃yR(x,y))→Q(x)2、∀x(P(x,z)∨∃yR(x,y))→Q(x)中量词的辖域，重名情况，改名等三、命题逻辑永真式的任何代换实例必是谓词逻辑的永真式。

同样，命题逻辑永假式的任何代换实例必是谓词逻辑的永假式。

例：1、(∀xP(x)→∃xQ(x))↔(⌝∀xP(x)∨∃xQ(x))2、(∀xP(x)→∃xQ(x))∧(∃xQ(x))→∀zR(z)))→(∀xP(x) →∀zR(z))1-2是永真式（重言式）3、⌝(∀xF(x) ∃yG(y)) ∧ ∃yG(y) 永假式（矛盾式）四、消量词例：个体域D={1,2}，对∀x∀y(P(x)→Q(y))消量词五、简单的前束范式会判断即可。

离散数学第二章 命题逻辑等值演算

离散数学第二章 命题逻辑等值演算

范式存在定理
定理2.3 任何命题公式都存在着与之等值的析取范式与合 定理 取范式. 取范式. 求公式 的范式的步骤 的范式的步骤： 证 求公式A的范式的步骤： (1) 消去 中的→, ↔ 消去A中的 中的→ A→B⇔¬ ∨B ⇔¬A∨ → ⇔¬ A↔B⇔(¬A∨B)∧(A∨¬ ∨¬B) ↔ ⇔ ¬ ∨ ∧ ∨¬ (2) 否定联结词¬的内移或消去 否定联结词¬ ¬ ¬A⇔ A ⇔ ⇔¬A∧¬ ¬(A∨B)⇔¬ ∧¬ ∨ ⇔¬ ∧¬B ⇔¬A∨¬ ¬(A∧B)⇔¬ ∨¬ ∧ ⇔¬ ∨¬B
真值表法
例1 判断 ¬(p∨q) 与 ¬p∧¬q 是否等值 ∨ ∧ 解 p q 0 0 0 1 1 0 1 1 ¬p ¬q 1 1 0 0 1 0 1 0 p∨q ¬(p∨q) ¬p∧¬q ¬(p∨q)↔(¬p∧¬q) ∨ ∨ ∧ ∨ ↔¬ ∧ 0 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1
实例(续)
(2) (p→q)↔(¬q→¬ → ↔ ¬ →¬ →¬p) 解 (p→q)↔(¬q→¬ → ↔ ¬ →¬ →¬p) ∨¬p) ⇔ (¬p∨q)↔(q∨¬ ¬ ∨ ↔ ∨¬ ⇔ (¬p∨q)↔(¬p∨q) ¬ ∨ ↔¬ ∨ ⇔1 该式为重言式. 该式为重言式 （蕴涵等值式） 蕴涵等值式） （交换律） 交换律）
实例(续)
(3) ((p∧q)∨(p∧¬ ∧r) ∧¬q))∧ ∧ ∨ ∧¬ 解 ((p∧q)∨(p∧¬ ∧r) ∧ ∨ ∧¬ ∧¬q))∧ （分配律） 分配律） （排中律） 排中律） （同一律） 同一律） ∨¬q))∧ ⇔ (p∧(q∨¬ ∧r ∧ ∨¬ ⇔ p∧1∧r ∧ ∧ ⇔ p∧r ∧ 成假赋值. 成假赋值 总结:A为矛盾式当且仅当 ⇔ 为重言式当且仅当A⇔ 总结 为矛盾式当且仅当A⇔0; A为重言式当且仅当 ⇔1 为矛盾式当且仅当 为重言式当且仅当 说明:演算步骤不惟一, 说明 演算步骤不惟一,应尽量使演算短些 演算步骤不惟一

离散数学基础-第二章-数理逻辑

离散数学基础-第二章-数理逻辑
41
g) 你获得这一职位表明你有最好的信誉。 h) 要成为美国公民，只要你生在美国就行了。 i) 除非下大雨，否则我是一定要出门的。 j) 要在服务器登录必须有一个有效的口令。
42
【定义】设P, Q是两个命题,复合命题“P当且仅 当Q” 称为P与Q的等价式，记做 P Q， 称为等 价联结词 。
是可兼或还是不可兼或。
▶若是可兼或，以及p, q不能同时为真的不可兼 或①，均可直接符号化为p∨q的形式。 ▶如果是不可兼或②，并且p与q可同时为真，就 应符号化为 (p∧┐q)∨(┐p∧q) 的形式。
31
【例】 将下列命题符号化。 (1)张三选修了英语课或者微积分课。 (2)今晚张三要么只看书要么只听音乐。 (3)a>0或a=0。
例：如果1+1=2，那么雪是白的。
37
4) 在数学和其他自然科学中， “如果p, 则q” 往往表达前件p为真，后件也为真的推理关 系；而在数理逻辑中，当前件p为假，不管 后件是真是假，规定 p→q都是真 (∵复合 命题p →q应有真值)。
例：校长宣布： 如果气温超过38℃，则全校停课。
38
关于“只有……, 才……”和“除非……, 否 则……”的符号化：
做 p → q， → 称为蕴涵联结词， p称为 前件， q称为后件。
“→ ”的读法：implies, if…then… （英）
蕴涵、如果…则… （中）
p→q的真值定义为：
p→q为假 iff p为真而q为
假
34
p→q的真值定义为： p→q为假 iff p为真而q为假
表2.4 p→q真值表
pq 00 01 10 11
(1) 相容或(可兼或)： 用它联结的命题具有相容性：命题可以同时为真， 如：张三会讲英语或日语。

离散数学 第2章 命题逻辑

离散数学 第2章 命题逻辑

6
程序解法：
#include "stdio.h" #include "conio.h" main() { int p,q,r,A1,A2,A3,B1,B2,B3,C1,C2,C3,E; for(p=0;p<=1;p++) for (q=0;q<=1;q++) for(r=0;r<=1;r++) { A1=!p&&q;A2=(!p&&!q)||(p&&q);A3=p&&!q; B1=p&&!q;B2=(p&&q)||(!p&&!q);B3=!p&&q; C1=!q&&r;C2=(q&&!r)||(!q&&r);C3=q&&r; E=(A1&&B2&&C3)||(A1&&B3&&C2)||(A2&&B1&&C3)||(A2&&B3&&C1)||(A3&&B1&&C2)||(A3 &&B2&&C1); if (E==1) printf("p=%d\tq=%d\tr=%d\n",p,q,r); } getch(); }
复合命题： E=(A1 ∧B2 ∧C3) ∨ (A1 ∧B3 ∧C2) ∨ (A2 ∧B1 ∧C3) ∨ (A2 ∧B3∧C1) ∨ (A3 ∧B1 ∧C2) ∨ (A3 ∧B2 ∧C1)
A1 ∧B2 ∧C3 = (p ∧q ) ∧ ((p ∧ q) ∨(p ∧ q) ) ∧(q ∧ r) 0 A1 ∧B3 ∧C2 = (p ∧q ) ∧ ( p ∧ q) ∧( (q ∧ r) ∨(q ∧ r ) ) p ∧q ∧ r A2 ∧B1 ∧C3 =A2 ∧B3∧C1 = A3 ∧B2 ∧C1 = 0 A3 ∧B1 ∧C2 p ∧ q ∧ r E (p ∧q ∧ r) ∨ (p ∧ q ∧ r) 所以王教授是上海人。

第二章命题逻辑的等值和推理演算

第二章命题逻辑的等值和推理演算

2.1.1 等值的定义

给定两个命题公式A和B, 而P1…Pn是出现于A和B中的 所有命题变项, 那么公式A和B共有2n个解释, 若对其 中的任一解释, 公式A和B的真值都相等, 就称A和B是 等值的(或等价的)。记作A = B或AB 显然，可以根据真值表来判明任何两个公式是否是等 值的

ቤተ መጻሕፍቲ ባይዱ1: 证明(P∧P)∨Q = Q
第二章 命题逻辑的等值和推理演算



推理形式和推理演算是数理逻辑研究的基本内容 推理形式是由前提和结论经蕴涵词联结而成的 推理过程是从前提出发，根据所规定的规则来推 导出结论的过程 重言式是重要的逻辑规律，正确的推理形式、等 值式都是重言式


本章对命题等值和推理演算进行讨论，是以语义 的观点进行的非形式的描述，不仅直观且容易理 解，也便于实际问题的逻辑描述和推理。 严格的形式化的讨论见第三章所建立的公理系统。
2.1 等值定理

若把初等数学里的＋、－、×、÷等运算符看作是数 与数之间的联结词，那么由这些联结词所表达的代数 式之间，可建立许多等值式如下： x2－y2 = (x＋y)(x－y) (x＋y)2 = x2＋2xy＋y2 sin2x＋cos2x = 1 ……
在命题逻辑里也同样可建立一些重要的 等值式
证明: 画出(P∧P)∨Q与Q的真值表可看出等式 是成立的。
例2: 证明P∨P = Q∨Q

证明: 画出P∨P, Q∨Q的真值表, 可看出它 们是等值的, 而且它们都是重言式。
说明

从例1、2还可说明, 两个公式等值并不一定要 求它们一定含有相同的命题变项


若仅在等式一端的公式里有变项P出现, 那么等式 两端的公式其真值均与P无关。 例1中公式(P∧P)∨Q与Q的真值都同P无关 例2中P∨P, Q∨Q都是重言式, 它们的真值也都 与P、Q无关。

离散数学 等值式 范式 消解算法

离散数学 等值式 范式 消解算法
p(qr) (pq) r p(qr) 不与 (pq) r 等值
2
等值式例题
例1 判断下列各组公式是否等值:
(1) p(qr) 与 (pq) r
p q r qr p(qr) pq (pq)r
000 1
1
001 1
1
010 0
1
011 1
1
100 1
1
101 1
1
110 0
0
111 1
1
0
1
0
1
0
1
20
极小项与极大项
定义2.4 在含有n个命题变项的简单合取式（简单析取式） 中，若每个命题变项均以文字的形式在其中出现且仅出现 一次，而且第i个文字出现在左起第i位上（1in），称这 样的简单合取式（简单析取式）为极小项（极大项）.
几点说明： n个命题变项有2n个极小项和2n个极大项 2n个极小项（极大项）均互不等值 用mi表示第i个极小项，其中i是该极小项成真赋值的十进制
p q r 1 0 0 m4
p q r 1 0 1 m5
p q r 1 1 0 m6
p q r
1 1 1 m7
极大项
公式
成假赋值 名称
pqr
0 0 0 M0
p q r 0 0 1 M1
p q r 0 1 0 M2
p q r 0 1 1 M3
p q r 1 0 0 M4
p q r 1 0 1 M5
Bj Bj(pipi) (Bjpi)(Bjpi) 重复这个过程, 直到所有简单析取式都是长度为n的极 大项为止 (3) 消去重复出现的极大项, 即用Mi代替MiMi (4) 将极大项按下标从小到大排列
26
实例

离散数学-命题演算

离散数学-命题演算

Lu Chaojun, SJTU
19
方法一
• 从每个使为真的解释写出一个各命题变
元的合取式;然后写出各合取式的析取式.
例:有三个成真解释.
P
Q
由(P,Q)=(F,F)可写出合取式: F
F
T
P Q
F
T
T
T
F
F
由(P,Q)=(F,T)可写出合取式: T
T
T
P Q
由(P,Q)=(T,T)可写出合取式:P Q
– 例如: PQ = P Q
这两个公式语法上是不同的,但语义上相同(即有 相同意义).
Lu Chaojun, SJTU
3
如何证明两公式等值?
• 真值表法 • 利用等值定理 • 利用基本等值式进行推导
Lu Chaojun, SJTU
4
例:利用真值表证明等值
证明(PP)Q = Q. 证:列出真值表即可看出等式成立.
于是得到: (PQ) (PQ) (PQ)
Lu Chaojun, SJTU
20
方法二
• 从每个使为假的解释写出一个各命题变
元的析取式;然后写出各析取式的合取式.
例:有两个成假解释.
P
Q
由(P,Q)=(T,F)可写出析取式: F
F
T
P Q
F
T
T
T
F
F
由(P,Q)=(T,T)可写出析取式: T
T
F
13. PQ = PQ 14. PQ = (PQ)(PQ) [同真或同假] 15. PQ = (PQ)(PQ) [一真一假]
Lu Chaojun, SJTU
15
其他常用等值式(续)
16. PQ = (PQ) (QP) [充分必要] 17. P(QR) = Q(PR) [交换前提] 18. (PR)(QR) = (P Q)R [析取前提] 补充: 19. P(QR) = (PQ) (PR) 20. P(QR) = (PQ) (PR) 21. (PQ)R = (PR) (QR) 22. (PQ)R = (PR) (QR)

离散数学第二章命题逻辑等值演算

离散数学第二章命题逻辑等值演算

再如 ┑p ∨ q 既是p →q的析取范式又是它的的合取范式
如果公式的范式不唯一则对于将公式按等值进行分类的利用价值就不高
p q (p → q)∧(q→p) (p∧q)∨(┓p∧┓q)
00
1
1
01
0
0
10
0
0
11
1
1
（0,0）与（1,1）为公式的成真赋值。 （0,1）与（1,0）为公式的成假赋值
命题公式的分类（根据公式在赋值下的真值情况进行分类） 1）若命题公式在它的各种赋值下取值均为真,则称命题公式是重言
式或永真式。 2）若命题公式在它的各种赋值下取值均为假,则称命题公式是矛盾
2
如：┐Q∧（Ｐ→Q） → ┐P
4
分析1：若要得出：当设 A为真，B为
假的情况不会出现，
5
那么A →B 为永真式。
6
可证明：设前件为真
7
分析2： 还可以从设 B为假，推出A
为真的情况不会出现（A为假），
9
证明： 设后件为假
8
那么A →B 为永真式。
1 0
(（Ｐ→Q）∧( Q→R)) →(Ｐ→R)
不同真值表的公式 1）当命题变元确定后，通过五个连接词及其命题变元可以构成 无数个不 同表现形式的命题公式。 问题：这些不同形式的命题公式的真值表是否都不相同？ 先看变元仅有两个p,q 那么关于这两个变元的公式的赋值仅有4组
（┐p ∨ q）∧（┐q∨┐p∨r）∧┐q
是含三个简单析取式的合取范式．
2、性质：
1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式
2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式
┐p ∧ P ∨ ┐ q∧ q ⇔ 0 ∨ 0 ⇔ 0

离散数学 第2章 命题逻辑等值演算

离散数学 第2章 命题逻辑等值演算

A00
A0A. A1A
ABAB AB(AB)(BA) ABBA ABAB (AB)(AB) A
等价否定等值式
注意：要牢记各个等值式，这是继续学习的基础
以上 16 组等值式包含了 24 个重要等值式。 由于 A,B,C 可以 代表任意的命题公式，因而以上各等值式都是用元语言符号 书写的，称这样的等值式为等值式模式，每个等值式模式都 给出了无穷多个同类型的具体的等值式。 例如，在蕴涵等值式（2.12）中， 取 A=p，B=q 时，得等值式: p→q ┐p∨q 当取 A=p∨q∨r，B=p∧q 时，得等值式: (p∨q∨r)→(p∧q) ┐(p∨q∨r)∨(p∧q) 这些具体的等值式都被称为原来的等值式 模式的代入实例。
mi 与 Mi 的关系由书上定理 2.4 给出，即 mi Mi, Mi mi
2. 主析取范式与主合取范式 定义 2.5 （1）主析取范式——由极小项构成的析取范式 （2） 主合取范式——由极大项构成的合取范式 例如，n=3, 命题变项为 p, q, r 时， (p q r) (p q r) m1m3 ——主析取范式 (p q r) (p q r) M7M1——主合取范式 3. 命题公式 A 的主析取范式与主合取范式 （1） 与 A 等值的主析取范式称为 A 的主析取范式；与 A 等值的主合 取范式称为 A 的主合取范式. （2） 主析取范式的存在惟一定理 定理 2.5 任何命题公式都存在着与之等值的主析取范式和主合取 范式,并且是惟一的
由最后一步可知， （1）为矛盾式.
（2）(pq)(qp) (pq)(qp) (pq)(pq) 1 由最后一步可知， （2）为重言式. 问：最后一步为什么等值于 1？ 说明： （2）的演算步骤可长可短，以上演算最省. （蕴涵等值式） （交换律）

离散数学之等值演算

离散数学之等值演算
说明:也可以从右边开始演算（请做一遍） 因为每一步都用置换规则，故可不写出 熟练后，基本等值式也可以不写出
7
应用举例——证明两个公式不等值
例2 证明: p(qr) (pq) r 用等值演算不能直接证明两个公式不等值,证明两
个公式不等值的基本思想是找到一个赋值使一个成 真,另一个成假.
方法一 真值表法（自己证） 方法二 观察赋值法. 容易看出000, 010等是左边的 的成真赋值，是右边的成假赋值. 方法三 用等值演算先化简两个公式，再观察.
31
例 (续)
解此类问题的步骤为： ① 将简单命题符号化 ② 写出各复合命题 ③ 写出由②中复合命题组成的合取式 ④ 求③中所得公式的主析取范式
32
例 (续)
解 ① 设p：派赵去，q：派钱去，r：派孙去， s：派李去，u：派周去.
② (1) (pq) (2) (su) (3) ((qr)(qr)) (4) ((rs)(rs)) (5) (u(pq))
按角标从小到大顺序排序.
23
求公式的主范式
例 求公式 A=(pq)r的主析取范式与主合
取范式.
(1) 求主析取范式
(pq)r
(pq)r , （析取范式） ①
(pq)
(pq)(rr)
(pqr)(pqr)
m6m7 ,
②
24
求公式的主范式(续)
r
(pp)(qq)r
(pqr)(pqr)(pqr)(pqr)
(pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1 由最后一步可知，该式为重言式. 问：最后一步为什么等值于1？
10
例3 (续)
(3) ((pq)(pq))r)
解 ((pq)(pq))r)
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1
F2( 1 ) 1
0
F3( 1 ) 1
1
16
2.2.2 联结词完备集
2元真值函数 p q 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1
F0( 2 ) F1( 2 ) F2( 2 ) F3( 2 ) F4( 2 ) F5( 2 ) F6( 2 ) F7( 2 )
0 0 0 0
F8( 2 )
8
2.2.1 等值式与等值演算
等值演算
等值演算: 由已知的等值式推演出新的等值式的过程 置换规则:设(A)是含公式A的命题公式， (B)是用公式 B 置换了 (A)中所有的 A 后得到的命题公式，若 BA, 则(B)(A) 例 在公式 (pq)r中，可用 pq 置换其中的 pq， 由蕴涵等值式可知， pq pq，所以 (pq)r (pq) r
pq为真当且仅当 pq为真当且仅当
p, q不同时为真 p, q同时为假
20
2.2.2 联结词完备集
复合联结词
定理2.2 {},{}都是联结词完备集 证：已知{, , }是完备集，因而只需证明其中的每个 联结词都可以由 {}定义即可. p (pp) pp pq (pq) (pq) (pq)(pq) p∨q ⇔ ( p∨q )⇔ ( p∧ q) ⇔ p↑ q⇔(p↑p)↑(q↑q) 得证{}是联结词完备集. 对于{}可类似证明. 练习：分别用{},{}表示 p→q ?
结论: (pq) (pq)
4
2.2.1 等值式与等值演算
真值表法(续)
例2 判断下述3个公式之间的等值关系: p(qr), (pq)r, (pq)r 解 p q r p(qr) (pq)r 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 0 1 0 1 0 1 1 1 0 1 (pq)r 1 1 1 1 1 1 0 1
15
非重言式的可满足式.如101是它的成真赋值,0是它的
2.2.2 联结词完备集
真值函数
定义2.12 称F:{0,1}n{0,1}为n元真值函数 n元真值函数共有 个
每一个命题公式对应于一个真值函数 每一个真值函数对应无穷多个命题公式 1元真值函数 p 0 1
F0( 1 ) 0
0
F1( 1 ) 0
5
结论： p(qr)与(pq)r等值, 但与(pq)r不等值
2.2.1 等值式与等值演算
基本等值式
双重否定律 幂等律 交换律 结合律 分配律 德摩根律 吸收律 AA A A A, A A A A B B A, A B B A (AB)CA(BC) (AB)CA(BC) A(BC)(AB)(AC) A(BC) (AB)(AC) (AB)AB (AB)AB A(AB)A, A(AB)A
23
2.3.1 析取范式与合取范式
简单析取式与简单合取式（续）
性质： (1) 设Ai 是含有n个文字的简单析取式，若Ai 中既含某个命题 变项 pj ，又含它的否定式pj ，由交换律、排中律和零律 可知， Ai 为 重言式 ； (2) 反之，若Ai 为重言式的简单析取式，则它必同时含某个 命题变项及其否定式；（否则，若不同时含某个命题变项 及其否定式，其它文字也都取0，则Ai 的真值为0，矛盾） (3) 设 Ai是含有n个文字的简单合取式，若Ai 中既含某个命题 变项 pj ，又含它的否定式 pj ，由交换律、矛盾律和零律 ； 可知， Ai为 矛盾式 (4) 反之，若 Ai为矛盾式，则它必同时含某个命题变项及其 否定式；（否则，若不同时含某个命题变项及其否定式， 24 其它文字也都取1，则Ai 的真值为1，矛盾）
– 真值函数 – 联结词完备集 – 与非联结词, 或非联结词
2
2.2.1 等值式与等值演算
等值式
定义2.11 若等价式AB是重言式, 则称A与B等值, 记作 AB, 并称AB是等值式 说明: (1) 是元语言符号, 不是联结词，不要混同于和= (2) A与B等值当且仅当A与B在所有可能赋值下的真值都相 同, 即A与B有相同的真值表 (3) n个命题变项的真值表共有 个, 每个命题公式都有无 穷多个等值的命题公式 (4) 可能有哑元出现. 在B中出现, 但不在A中出现的命题变 项称作A的哑元. 同样,在A中出现, 但不在B中出现的命题变 项称作B的哑元. 哑元的值不影响命题公式的真值. 3
18
2.2.2 联结词完备集
联结词完备集（续）
说明： (1) 不是所有联结词集都可以是完备集. 如 {, , , } ， 因为矛盾式不能由这4个联结词表示. (2) 设S1和 S2是两个不同的联结词完备集，用S1中联结词 构成任何公式，可等值的转化为用 S2中联结词构成的 公式，反之亦然. 从而可根据需要构造最简单的联结词 完备集.
离散数学（第3版） 屈婉玲 耿素云 张立昂 编著 清华大学出版社出版
2.2 命题逻辑等值演算
上海大学 谢江
1
离散数学（第3版） 屈婉玲 耿素云 张立昂 编著 清华大学出版社出版
2.2 命题逻辑等值演算
• 2.2.1 等值式与等值演算
– 等值式与基本等值式 – 真值表法与等值演算法
• 2.2.2 联结词完备集
9
2.2.1 等值式与等值演算
等值演算（续）
例3 用等值演算法证等值式： (p∨q)r (pr)∧(q→r) 证 (p∨q)r (pq)r (p∧q)r (p r)(q→r （蕴涵等值式） （德摩根律） （蕴涵等值式）
(pr)( q∨r （分配律）
等值演算不能直接证明两个公式不等值. 证明两个公式不 等值的基本思想是找到一个赋值使一个成真, 另一个成假. 例5 证明: p(qr) (pq) r
方法一 真值表法（见例2） 方法二 观察法. 容易看出000使左边成真, 使右边成假. 方法三 先用等值演算化简公式, 再观察.
12
2.2.1 等值式与等值演算
2.3.1 析取范式与合取范式
简单析取式与简单合取式（续）
定理2.3 (1) 一个简单析取式是重言式当且仅当它同时含 某个命题变项和它的否定 (2) 一个简单合取式是矛盾式当且仅当它同时含某个命 题变项和它的否定式 注：(1) 当A是由n个文字构成的简单析取式 a. 若A成真当且仅当 n个文字中 至少一个文字为真 。 * 全部为假 b. 若A成假当且仅当 n个文字 (2) 当A是由n个文字构成的简单合取式 * a. 若A成真当且仅当 n个文字全部为真 b. 若A成假当且仅当 n个文字中至少一个文字为假 。
19
2.2.2 联结词完备集
复合联结词
定义 设 p, q 为两个命题，复合命题“ p 与 q 的否定式” （“ p 或 q 的否定式” ）称作 p ， q 的与非式（或非 式），记作: pq (pq).. 与非式: pq(pq), 称作与非联结词 或非式: pq(pq), 称作或非联结词
1 1 1 1
17
2.2.2 联结词完备集
联结词完备集
定义2.13 设S是一个联结词集合, 如果任何n(n1) 元真值 函数都可以由仅含S中的联结词构成的公式表示,则称S是 联结词完备集 定理2.1 下述联结词集合都是完备集: (1) S1={, , , , } (2) S2={, , , } AB (AB)(BA) (3) S3={, , } A B A B (4) S4={, } AB (AB) (AB) (5) S5={, } AB (AB) AB (A)B AB (6) S6={, }
(2) (pq)(qp) 解 (pq)(qp) (pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1 该式为重言式.
14
2.2.1 等值式与等值演算
实例(续)
(3) ((pq)(pq))r) 解 ((pq)(pq))r) （分配律） （排中律） （同一律） (p(qq))r p1r pr 成假赋值. 总结: A为矛盾式当且仅当 A0 ; A为重言式当且仅当 A1 说明: 演算步骤不唯一,应尽量使演算短些
7
A00
A0A, A1A
2.2.1 等值式与等值演算
以上A, B, C可以是任意的公式，称为等值式模式 例 取 在蕴涵等值式：A→B⇔ A∨B中，取A=p，B=q， 得等值式 → ⇔ ∨ ∨ ∨ ， ∨ ∨ → ∧ ∧ ，得等值式 ⇔ ∨ ∨ ∨ ∧
这些具体的等值式被称为原来的等值式模式的代入实例. 由已知的等值式可以推演出更多的等值式 ！
25
2.3.1 析取范式与合取范式
析取范式与合取范式
析取范式:由有限个简单合取式组成的析取式 A1A2Ar, 其中A1,A2,,Ar是简单合取式 合取范式:由有限个简单析取式组成的合取式 A1A2Ar , 其中A1,A2,,Ar是简单析取式 范式:析取范式与合取范式的统称 例 设 Ai为简单合取式， A1= pq ， A2= qr ， A3=r， 则 A= A1 ∨A2∨ A3= (pq)∨ (qr)∨ r 为析取范式； 类似地， A1= p∨q ， A2= q∨r ， A3=r ，则 A= A1 A2 A3= (p∨q)∧ (q∨r) ∧ r 为合取范式 例 pqr ：简单合取式 由3个简单析取式构成 是合取范式？ 26 一个简单合取式构成 是析取范式？
0 0 0 1
F9( 2 )
0 0 1 0
( 2) F10
0 0 1 1
( 2) F11
0 1 0 0
( 2) F12
0 1 0 1
( 2) F13
0 1 1 0
( 2) F14
0 1 1 1
( 2) F15
p q
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1