当前位置：文档之家 › 离散数学之等值演算.PPT

离散数学之等值演算.PPT

  • 格式：ppt
  • 大小：146.00 KB
  • 文档页数：35

下载文档原格式

  / 35

合集下载

1.3等值演算(离散数学) PPT

1.3等值演算(离散数学) PPT
解答
等值 不等值
基本等值式
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) （∨对∧的分配律）
A∧(B∨C) (A∧B)∨(A∧C) （∧对∨的分配律）
等值演算的应用 –证明两个公式等值
–判断公式类型 –解判定问题
等值演算的应用举例
例3 证明两个公式等值 (p→q)→r (p∨r)∧(┐q∨r)
解答
(p→q)→r (┐p∨q)→r
（蕴含等值式、置换规则）
┐(┐p∨q)∨r （蕴含等值式、置换规则）
(p∧┐q)∨r
（德摩根律、置换规则）
(p∨r)∧(┐q∨r) （分配律、置换规则）
(蕴含等值式) (分配律) (德摩根律) (蕴含等值式)
例题
例5 证明：(p→q)→r 与 p→(q→r) 不等值
解答 方法一、真值表法。
方法二、观察法。易知，010是(p→q)→r的成假赋值，而010 是p→(q→r)的成真赋值，所以原不等值式成立。
方法三、通过等值演算化成容易观察真值的情况，再进行判断。
1.3 等值演算
两公式什么时候代表了同一个命题呢？
抽象地看，它们的真假取值完全相同时即代 表了相同的命题。
设公式A,B共同含有n个命题变项，若A与B有 相同的真值表，则说明在2n个赋值的每个赋 值下，A与B的真值都相同。于是等价式AB 应为重言式。
等值的定义及说明
定义1.10 设A,B是两个命题公式，若A,B构成的 等价式AB为重言式，则称A与B是等值的，记 作AB。

第四版离散数学PPT

第四版离散数学PPT

pq pq pq qp qp pq qp qp
16
注意： pq 与 qp 等值（真值相同）
联结词与复合命题(续)
5.等价式与等价联结词“” 定义 设p，q为二命题，复合命题 “p当且仅当q”称 作p与q的等价式，记作pq. 称作等价联结词. 并规定pq为真当且仅当p与q同时为真或同时为 假. 说明: (1) pq 的逻辑关系:p与q互为充分必要条件
21
合式公式的层次
定义 (1) 若公式A是单个的命题变项, 则称A为0层公式. (2) 称A是n+1(n≥0)层公式是指下面情况之一： (a) A=B, B是n层公式； (b) A=BC, 其中B,C分别为i层和j层公式，且 n=max(i, j)； (c) A=BC, 其中B,C的层次及n同(b)； (d) A=BC, 其中B,C的层次及n同(b)； (e) A=BC, 其中B,C的层次及n同(b).
18
联结词与复合命题(续)
以上给出了5个联结词：, , , , ，组成 一个联结词集合{, , , , }，
联结词的优先顺序为：, , , , ; 如果出 现的联结词同级，又无括号时，则按从左到右 的顺序运算; 若遇有括号时，应该先进行括号 中的运算.
注意: 本书中使用的 括号全为圆括号.
22
合式公式的层次 (续)
例如 公式 p p pq (pq)r ((pq) r)(rs)
0层 1层 2层 3层 4层
23
公式的赋值
定义 给公式A中的命题变项 p1, p2, … , pn指定 一组真值称为对A的一个赋值或解释 成真赋值: 使公式为真的赋值 成假赋值: 使公式为假的赋值 说明： 赋值=12…n之间不加标点符号，i=0或1. A中仅出现 p1, p2, …, pn，给A赋值12…n是 指 p1=1, p2=2, …, pn=n A中仅出现 p, q, r, …, 给A赋值123…是指 p=1,q=2 , r=3 … 含n个变项的公式有2n个赋值.

离散数学-命题逻辑等值演算名师公开课获奖课件百校联赛一等奖课件

离散数学-命题逻辑等值演算名师公开课获奖课件百校联赛一等奖课件

(分配律) (矛盾律) (同一律) (德摩根律) (结合律) (排中律) (零律)
等值演算旳例子
解：⑵ (p∨¬p)→((q∧¬q)∧r)
1→((q∧¬q)∧r)
(排中律)
1→(0∧r)
(矛盾律)
1→0
(零律)
0
(条件联结词旳定义)
由此可知，⑵为矛盾式。
⑶ (p→q)∧¬p
(¬p∨q)∧¬p
(蕴涵等值式)
范式存在定理
定理2.3
• 任一命题公式都存在着与之等值旳 析取范式
求•范任式旳一环命节题如公下式：都存在着与之等值旳合 ⑴取消范去式联结词“→”和“↔”
⑵ 利用双重否定律消去否定联结词“¬”或 利用德摩根律将否定联结词“¬”移到各命题 变元前(¬内移)。
⑶ 利用分配律，结合律将公式归约为合取 范式和析取范式。
极大项：简朴析取式中满足如上条件。
极小（大）项旳关键性质
• 定理：n个命题变元共有2n个极小项（极大项）。
p
q p∧q p∧¬q
¬p∧q
¬p∧¬q
0
0
0
0
0
1
0
1
0
0
1
0
1
0
0
1
0
0
1
1
1
0
0
0
• 每个极小（大）项只有一种成真（假）赋值，且 各极小项旳成真赋值互不相同。
• 极小项和它旳成真赋值构成了一一相应旳关系。
¬p
(吸收律)
由此可知，⑶是可满足式。
练习
1.用等值演算验证等值式 （1） (p∨q)→r (p→r)∧ (q→r) （2） （(p∨q)∧ ¬（p∧q））

一阶逻辑等值演算与推理课件(离散数学)分解

一阶逻辑等值演算与推理课件(离散数学)分解
( F (a ) F (b) F (c )) (G(a ) G(b) G(c ))
18
例题
(3)当个体域D={a,b}
xy( F ( x, y ) G( x, y ))
x((F ( x, a ) G( x, a )) ( F ( x, b) G( x, b)))
((F (a , a ) G(a , a )) ( F (a , b) G(a , b))) ((F (b, a ) G(b, a )) ( F (b, b) G(b, b)))
x( F ( x ) G( x ))
这句话相当于“有些学生没有上课”。
x( F ( x ) G( x ))
4
一、等值式的概念
定义：若AB为永真式，则称A与B是等 值的，记作 AB，并称AB为等值式。
其中A、B是一阶逻辑中任意的两个合式公
式。
5
二、基本等值式
1. 命题逻辑中16组基本等值式的代换实例
7
二、基本等值式
“并不是所有的人都是黄皮肤。” xA( x ) 这句话相当于 “有的人不是黄定等值式
xA( x ) xA( x ) xA( x ) xA( x )
8
二、基本等值式
4.
量词辖域收缩与扩张等值式
设A(x)是含x自由出现的公式，B中不含x的出现。 关于全称量词：
x(A(x)B)xA(x)B
x(A(x)B)xA(x)B
x(A(x)B)xA(x)B
x(BA(x))BxA(x)
9
二、基本等值式
关于存在量词: x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x))BxA(x)

离散数学课件PPT-1.3等值演算

离散数学课件PPT-1.3等值演算

p1r
（排中律）
pr
（同一律）
可满足式，101和111是成真赋值，000和010等是成假赋值.
a为矛盾式当且仅当a?0a为重言式当且仅当a?1例例3用等值演算法判断下列公式的类型1q??p?q2p?q???q??p3p??q??p??q??r等值演算的应用举例解解1q??p?q?q????p??q蕴涵等值式?q??p??q德摩根律?p??q??q交换律结合律?p??0矛盾律?0零律矛盾式判断公式类型2p?q???q??p???p??q?q??p蕴涵等值式???p??q???p??q交换律?1重言式3p??q??p??q??r?p??q??q??r分配律?p??1??r排中律?p??r同一律可满足式101和111是成真赋值000和010等是成假赋值
p(qq) （交换律，结合律）
p0
（矛盾律）
0
（零律）
矛盾式
判断公式类型
(2) (pq)(qp) (pq)(qp) （蕴涵等值式） (pq)(pq) （交换律）
1 重言式
(3) ((pq)(pq))r
(p(qq))r （分配律）
用真值表判断公式的等值
例1 判断下面两个公式是否等值： ┐(p∨q)与┐p∧┐q
解: 用真值表法判断┐(p∨q) (┐p∧┐q)是否为重言式. 此等价式的真值表如表1所示, 从表中可知它是重言式, 因
而┐(p∨q)与┐p∧┐q等值, 即┐(p∨q) (┐p∧┐q).
表1 (p∨q) (┐p∧┐q)的真值表
判断公式类型: A为矛盾式当且仅当A 0 A为重言式当且仅当A 1
例3 用等值演算法判断下列公式的类型 (1) q(pq) (2) (pq)(qp) (3) ((pq)(pq))r)

离散数学一阶逻辑等值演算与推理32页PPT

离散数学一阶逻辑等值演算与推理32页PPT
离散数学一阶逻辑等值演算与推理
•
46、寓形宇内复几时，曷不委心任去 留。
•
47、采菊东篱下，悠然见南山。
•
48、啸傲东轩下日 有所长 。
•
50、环堵萧然，不蔽风日；短褐穿结 ，箪瓢 屡空， 晏如也 。
谢谢你的阅读
❖ 知识就是财富 ❖ 丰富你的人生
71、既然我已经踏上这条道路，那么，任何东西都不应妨碍我沿着这条路走下去。——康德 72、家庭成为快乐的种子在外也不致成为障碍物但在旅行之际却是夜间的伴侣。——西塞罗 73、坚持意志伟大的事业需要始终不渝的精神。——伏尔泰 74、路漫漫其修道远，吾将上下而求索。——屈原 75、内外相应，言行相称。——韩非

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

离散数学2课件 第2章 命题逻辑等值演算
个命题变项和它的否定式。
23/56
范式的性质
定理2.2 (1) 一个析取范式是矛盾式当且仅当它每个简单合取
式都是矛盾式。 (2) 一个合取范式是重言式当且仅当它的每个简单析
取式都是重言式。
定理2.3（范式存在定理） 任何命题公式都存在与之等值的析取范式与合
取范式。
24/56
命题公式的范式
求公式A的范式的步骤： (1) 消去A中的, （若存在） ABAB AB(AB)(AB) (2) 否定联结词的内移或消去 A A (AB)AB (AB)AB (3) 使用分配律
的十进制表示. 用Mi表示第i个极大项，其中i是该极大项成假赋值
的十进制表示. mi（Mi）称为极小项（极大项）的名称。
29/56
实例
由两个命题变项 p, q 形成的极小项与极大项
极小项
公式 成真赋 值
pq 0 0
pq
01
pq
10
pq
11
名称
m0 m1 m2 m3
极大项
公式 成假赋 值
pq 0 0 pq 0 1 pq 1 0 pq 1 1
(2) 简单析取式——仅由有限个文字构成的析取式
p, q, pq, pqr, …
(3) 简单合取式——仅由有限个文字构成的合取式
p, q, pq, pqr, …
(4) 析取范式——由有限个简单合取式组成的析取式
p, pq, pq, (pq)(pqr)(qr)
(5) 合取范式——由有限个简单析取式组成的合取式
14/56
等值演算的应用举例
判断公式类型: A为矛盾式当且仅当A 0 A为重言式当且仅当A 1
例4 用等值演算法判断下列公式的类型 (1) q(pq) (2) (pq)(qp) (3) ((pq)(pq))r)

离散数学课件-5-一阶逻辑等值演算与推理

离散数学课件-5-一阶逻辑等值演算与推理

离散数学课件-5-一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理§1 一阶逻辑等值式与置换规则定义：A，B两个谓词公式，若A?B是永真式，则称A与B是等值的，记为A?B。

常用等值式：第一组：命题逻辑中常用等值式的代换实例第二组：一阶逻辑中的特有等值式1．消去量词当D={a1, a2,…, a n}时，有①?xA(x)?A(a1)∧A(a2)∧…∧A(a n)②?xA(x)?A(a1)∨A(a2)∨…∨A(a n)2．量词否定①??xA(x)??x?A(x)②﹁?xA(x)??x?A(x)3．辖域收缩与扩张①?x(A(x)∨B)??xA(x)∨B②?x(A(x)∧B)??xA(x)∧B③?x(A(x)∨B)??xA(x)∨B④?x(A(x)∧B)??xA(x)∧B4．量词分配①?x(A(x)∧B(x))??xA(x)∧?xB(x)②?x(A(x)∨B(x))??xA(x)∨?xB(x)演算规则：1．置换规则：φ(A)：含A的谓词公式φ(B)：用公式B替换φ(A)中所有A之后的公式若A?B，则φ(A)?φ(B)。

2．换名规则：设A是谓词公式，把A中某指导变元对应的全部约束出现替换为A中未出现过的符号，而A中其余部分不变，设所得谓词公式为A′，则A?A′。

3．代替规则设A是谓词公式，把A中某个体变项的全部自由出现替换为A中未出现过的符号，而A中其余部分不变，设所得公式为A′，则A?A′。

例①?xF(x,y,z)→?yG(x,y,z)sF(s,y,z)→?tG(x,t,z) 换名②?x(F(x,y)→?yG(x,y,z))x(F(x,t)→?yG(s,y,z)) 代替例给定解释I：D I ={2,3}，a：2，b：3G(x,y)：G(a, a)=G(a, b)=G(b, a)=1，G(b, b)=0F(x)：F(a)=0，F(b)=1① ?x(F(x)∧G(x,a))(F(a)∧G(a,a))∧(F(b)∧G(b,a))?(0∧1)∧(1∧1)? 0② ?x?yG(x,y)x(G(x,a)∧G(x,b))(G(a,a)∧G(a,b))∨(G(b,a)∧G(b,b))(1∧1)∨(1∧0)1例证明：﹁?x(F(x)→G(x))??x(F(x)∧﹁G(x)) 解：﹁?x(F(x)→G(x))﹁?x(﹁F(x)∨G(x))x﹁(﹁F(x)∨(G(x)x(F(x)∧﹁G(x))§2 前束范式定义：设A是谓词公式，若A有如下形式Q1x1Q2x2…Q k x k B其中Q i(1≤i≤k)为?或?，B为不含量词的公式，则称A为前束范式。

离散数学2课件 第5章 一阶逻辑等值演算与推理

离散数学2课件 第5章 一阶逻辑等值演算与推理

15/58
求前束范式的实例
例4 求下列公式的前束范式 (3) xF(x)y(G(x,y)H(y))
解: xF(x)y(G(x,y)H(y)) zF(z)y(G(x,y)H(y)) 换名规则 zy(F(z)(G(x,y)H(y))) 辖域收缩扩张规则
或 xF(x)y(G(z,y)H(y)) 代替规则 xy(F(x)(G(z,y)H(y)))
x(F(x)G(x)) x(F(x)G(x)) x(F(x)G(x))
x(F(x)G(x))
量词否定等值式 置换
置换
7/58
实例
例1 将下面命题用两种形式符号化, 并证明两者等值. (2) 不是所有的人都爱看电影
解: 令F(x)：x是人，G(x)：爱看电影. x(F(x)G(x)) 或 x(F(x)G(x))
第二组 基本等值式生成的推理定律 如, xF(x) xF(x), xF(x) xF(x) xF(x)xF(x), xF(x) xF(x)
第三组 其他常用推理定律
(1) xA(x)xB(x) x(A(x)B(x))
(2) x(A(x)B(x)) xA(x)xB(x)
(3) x(A(x)B(x)) xA(x)xB(x)
x(F(x)G(x)) x(F(x)G(x)) x(F(x)G(x)) x(F(x)G(x))
量词否定等值式 置换 置换
8/58
实例
例2 将公式化成等值的不含既有约束出现、又有自
由出现的个体变项: x(F(x,y,z)yG(x,y,z)) 解: x(F(x,y,z)yG(x,y,z))
x(F(x,y,z)tG(x,t,z))
11/58
实例
例3 设个体域D={a,b,c}, 消去下述公式中的量词: (2) xyF(x,y)
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

满足式.如101是它的成真赋值,000是它的成假赋值.
总结：A为矛盾式当且仅当A0
A为重言式当且仅当A1
说明：演算步骤不惟一,应尽量使演算短些
.
11
1.4 范式
▪ 析取范式与合取范式 ▪ 主析取范式与主合取范式
.
12
析取范式与合取范式
文字:命题变项及其否定的总称
简单析取式:有限个文字构成的析取式
p(qr) (pq) r
.
2
基本等值式
双重否定律 : AA
等幂律： AAA, AAA
交换律:
ABBA, ABBA
结合律:
(AB)CA(BC)
(AB)CA(BC)
分配律:
A(BC)(AB)(AC)
A(BC) (AB)(AC)
.
3
基本等值式(续)
德·摩根律: (AB)AB
(AB)AB
吸收律: 零律: 同一律:
(1) 消去A中的, （若存在） (2) 否定联结词的内移或消去 (3) 使用分配律
对分配（析取范式） 对分配（合取范式） 公式的范式存在，但不惟一
.
15
求公式的范式举例
例 求下列公式的析取范式与合取范式
(1) A=(pq)r 解 (pq)r
(pq)r pqr
（消去） （结合律）
这既是A的析取范式（由3个简单合取式组成的析 取式），又是A的合取范式（由一个简单析取式 组成的合取式）
如 p, q, pq, pqr, … 简单合取式:有限个文字构成的合取式
如 p, q, pq, pqr, …
析取范式:由有限个简单合取式组成的析取式
A1A2Ar, 其中A1,A2,,Ar是简单合取式 合取范式:由有限个简单析取式组成的合取式
A1A2Ar , 其中A1,A2,,Ar是简单析取式
.
13
析取范式与合取范式(续)
.
16
求公式的范式举例(续)
(2) B=(pq)r 解 (pq)r
(pq)r （消去第一个） (pq)r （消去第二个） (pq)r （否定号内移——德摩根律）
这一步已为析取范式（两个简单合取式构成）
继续： (pq)r (pr)(qr) （对分配律）
这一步得到合取范式（由两个简单析取式构成）
.
5
等值演算与置换规则
等值演算: 由已知的等值式推演出新的等值式的过程
置换规则：若AB, 则(B)(A)
等值演算的基础： (1) 等值关系的性质：自反、对称、传递 (2) 基本的等值式 (3) 置换规则
.
6
应用举例——证明两个公式等值
例1 证明 p(qr) (pq)r 证 p(qr)
p(qr) （蕴涵等值式，置换规则） (pq)r （结合律，置换规则） (pq)r （德摩根律，置换规则） (pq) r （蕴涵等值式，置换规则）
(pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1
由最后一步可知，该式为重言式. 问：最后一步为什么等值于1？
.
10
例3 (续)
(3) ((pq)(pq))r)
解 ((pq)(pq))r)
(p(qq))r （分配律）
p1r
（排中律）
pr
（同一律）
这不是矛盾式，也不是重言式，而是非重言式的可
1.3 命题逻辑等值演算
▪ 等值式 ▪ 基本等值式 ▪ 等值演算 ▪ 置换规则
.
1
等值式
定义 若等价式AB是重言式，则称A与B等值， 记作AB，并称AB是等值式 说明：定义中，A,B,均为元语言符号, A或B中 可能有哑元出现. 例如，在 (pq) ((pq) (rr))中，r为左边 公式的哑元. 用真值表可验证两个公式是否等值 请验证：p(qr) (pq) r
.
17
2元真值函数对应的真值表
pq
00 01 10 11 pq
00 01 10 11
FFFFFFFF ( 2 ) ( 2 ) ( 2 ) ( 2 ) ( 2 ) ( 2 ) ( 2 ) ( 2 ) 01 234567
00000000
00001111
00110011
01010101
FFFFFFFF ( 2 ) ( 2 ) ( 2 ) ( 2 ) ( 2 ) ( 2 ) ( 2 ) ( 2 ) 8 9 1 01 11 21 31 41 5
说明:也可以从右边开始演算（请做一遍）
因为每一步都用置换规则，故可不写出
熟练后，基本等值式也可以不写出
.
7
应用举例——证明两个公式不等值
例2 证明: p(qr) (pq) r 用等值演算不能直接证明两个公式不等值,证明两
个公式不等值的基本思想是找到一个赋值使一个成 真,另一个成假.
方法一 真值表法（自己证） 方法二 观察赋值法. 容易看出000, 010等是左边的 的成真赋值，是右边的成假赋值. 方法三 用等值演算先化简两个公式，再观察.
.
8
应用举例——判断公式类型
例3 用等值演算法判断下列公式的类型
(1) q(pq)
解 q(pq)
q(pq) （蕴涵等值式）
q(pq) （德摩根律）
p(qq) （交换律，结合律）
p0
（矛盾律）
0
（零律）
由最后一步可知，该式为矛盾式.
.
9
例3 (续)
(2) (pq)(qp) 解 (pq)(qp)
范式:析取范式与合取范式的总称 公式A的析取范式: 与A等值的析取范式 公式A的合取范式: 与A等值的合取范式 说明： 单个文字既是简单析取式，又是简单合取式 pqr, pqr既是析取范式，又是合取范式 (为什么?)
.
14
命题公式的范式
定理 任何命题公式都存在着与之等值的析取范式 与合取范式. 求公式A的范式的步骤：
A(AB)A, A(AB)A A11, A00 A0A, A1A
排中律: AA1
矛盾律: AA0
.
4
基本等值式(续)
蕴涵等值式: ABAB
等价等值式: AB(AB)(BA)
假言易位:
ABBA
等价否定等值式: ABAB
归谬论:
(AB)(AB) A
注意:
A,B,C代表任意的命题公式
牢记这些等值式是继续学习的基础
11111111
00001111
00110011
0101010有n个命题变项的简单合取式(简单析取式)中， 若每个命题变项均以文字的形式出现且仅出现一次，称这 样的简单合取式(简单析取式)为极小项(极大项）.
说明： n个命题变项产生2n个极小项和2n个极大项
2n个极小项（极大项）均互不等值
在极小项和极大项中文字均按下标或字母顺序排列
用mi表示第i个极小项，其中i是该极小项成真赋值的十 进制表示. 用Mi表示第i个极大项，其中i是该极大项成 假赋值的十进制表示, mi(Mi)称为极小项(极大项)的名称.