离散 范式PPT课件.pptx

--1
第11讲 范式
PowerPoint Template_Sub
命题与逻辑联结词
逻辑等价式和逻辑蕴涵式
范式
证明技术（补充）
第1页/共31页
范式
《离散数学》第11讲
Textbook Page 71 to 74
文字、子句、互补文字对的概念
析取范式与合取范式
主范式
联结词的扩充与规约
第2页/共31页
--3
第11讲 范式
要解决的问题
给定命题变元个数n，有无穷多个含有n个命题变元的命题公式，但只有有限多张这样的真值表
很多命题公式是互相逻辑等价的,是否它们有公共的标准形式
希望有一种规范的方法解决下面两个问题：
判定任意一个命题公式是否为永真式或永假式
判断任意两个命题公式是否等价
第3页/共31页
--4
第11讲 范式
有关术语
文字（letter）：是指命题常元、变元及它们的否定，如p，┐p。前者又称正文字，后者又称负文字。
析取子句（disjunctive clause）：指文字或文字的析取。例：p，┐p，p∨q等。
合取子句（conjunctive clause）：指文字或文字的合取。例：p，┐p，p∧┐p，p∧q∧r等。
互补文字对（complemental pair of letter）：指形如p、┐p的一对文字。
第4页/共31页
--5
第11讲 范式
关于子句的真值
析取子句A1∨A2 ∨…∨Am为永真式，当且仅当子句中含有互补文字对Ai和┐ Ai 。
合取子句A1∧A2 ∧…∧Am为永假式，当且仅当子句中含有互补文字对Ai和┐ Ai 。
第5页/共31页
--6
第11讲 范式
析取范式 (disjunctive normal form)
：命题公式A’称为公式A的析取范式，如果
（1）A’  A
（2）A’为一合取子句或若干合取子句的析取
(p∧q)∨r的析取范式： (p∧q)∨r
((p→q)∧ ┐p) ∨ ┐ q
 ((┐p ∨ q)∧ ┐p) ∨ ┐ q
 (┐p ∧ ┐p) ∨( q∧ ┐p) ∨ ┐ q
 ┐p∨(q∧┐p)∨ ┐ q
析取范式的形式为： (.∧.∧. .∧.)∨ (.∧.∧. .∧.) ∨ (.∧.∧. .∧.)
第6页/共31页
--7
第11讲 范式
合取范式 (conjunctive normal form)
：命题公式A’称为公式A的合取范式，如果
（1）A’  A
（2）A’为一析取子句或若干析取子句的合取
p→q  ┐p∨q，合取范式，也是析取范式
((p→q)∧┐p)∨┐q
 ((┐p∨q)∧┐p)∨┐q
 ((┐p∨q)∨┐q)∧(┐ p∨┐q)
 ┐ p∨┐q 合取范式
(p∧q)∨r  (p ∨r)∧(q∨r)
合取范式的形式为： (.∨.∨. .∨.)∧(.∨.∨. .∨.)∧(.∨.∨. .∨.)
第7页/共31页
--8
第11讲 范式
求析取范式和合取范式
p∧(p→q)
 p∧(┐p∨q) 合取范式
 (p∧┐p)∨(p∧q) 析取范式
 p∧q 合取范式 析取范式
例 ┐p→┐(p→q)
 p∨┐(┐p∨q)
 p∨(p∧┐q)  (p∧t)∨(p∧┐q)  p ∧(t ∨┐q)  p此为析取范式
 (p∨p)∧(p∨┐q)
 p∧(p∨┐q)  (p∨f)∧(p∨┐q)  p∨(f∧┐q)  p
这就是合取范式
第一步，消去→ 和
第二步，将┐向内深入，使之只作用于命题变元
或命题变元的否定，然后把┐┐p化为p
第三步，利用分配律进一步将公式化为所需要的范式
第8页/共31页
--9
第11讲 范式
由析取范式判断永假式
在一命题公式的析取范式中，如果每一合取子句均为永假式，则这一命题公式也为永假式
而要看一个合取子句是否为永假式，只需看其中是否含有互补文字对
因此，只要求出公式的析取范式，就可以判断该公式是否为永假式
析取范式为： (.∧.∧. .∧.)∨ (.∧.∧. .∧.) ∨ (.∧.∧. .∧.)
第9页/共31页
--10
第11讲 范式
由合取范式判断永真式
在一个命题公式的合取范式中，如果每一析取字句均为永真式，则这个命题公式也为永真式
而每一析取字句是否是永真式，只需看其