当前位置：文档之家 › 命题逻辑第一课 命题公式与等值演算.ppt

命题逻辑第一课 命题公式与等值演算.ppt

  • 格式：ppt
  • 大小：457.57 KB
  • 文档页数：41

下载文档原格式

  / 41

合集下载

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。

离散数学-2.2-3命题逻辑等值演算.ppt

离散数学-2.2-3命题逻辑等值演算.ppt
14
2.3 范式
• 2.3.1 析取范式与合取范式
– 简单析取式与简单合取式 – 析取范式与合取范式
• 2.3.2 主析取范式与主合取范式
– 极小项与极大项 – 主析取范式与主合取范式 – 主范式的用途
15
简单析取式与简单合取式
文字:命题变项及其否定的统称 简单析取式:有限个文字构成的析取式 如 p, q, pq, pqr, … 简单合取式:有限个文字构成的合取式 如 p, q, pq, pqr, …
29
主析取范式的用途
(1) 求公式的成真赋值和成假赋值 设公式A含n个命题变项, A的主析取范式有s个极小项, 则A 有s个成真赋值, 它们是极小项下标的二进制表示, 其余2n-s 个赋值都是成假赋值
例如 (pq)r m0 m2 m4 m5 m6 成真赋值: 000,010,100,101,110; 成假赋值: 001,011,111
范式:析取范式与合取范式的统称
定理2.4 (1) 一个析取范式是矛盾式当且仅当它的每一个 简单合取式都是矛盾式 (2) 一个合取范式是重言式当且仅当它的每一个简单析取 式都是重言式
17
范式存在定理
定理2.5 任何命题公式都存在着与之等值的析取范式与合 取范式. 证 求公式A的范式的步骤： (1) 消去A中的,
30
主析取范式的用途(续)
(2) 判断公式的类型 设A含n个命题变项，则 A为重言式当且仅当A的主析取范式含2n个极小项 A为矛盾式当且仅当 A的主析取范式不含任何极小项,记作0 A为可满足式当且仅当A的主析取范式中至少含一个极小项
31
实例
例3 用主析取范式判断公式的类型:
(1) A (pq)q (2) B p(pq) (3) C (pq)r

《命题演算》ppt课件

《命题演算》ppt课件

Show that (p∨( p∧q)) and p∧q are
logically equivalent.
EXAMPLE 6
Propositional E q u i v a命l 题e n演c算e s
Show that (p∧q) → (p∨q) is a tautology.
Propositional E q u i v a命l 题e n演c算e s
1.2 命题演算
Propositional E q u i v a命l 题e n演c算e s
Propositional Equivalences
1、命题(Proposition)
Propositional E q u i v a命l 题e n演c算e s
2、从简单命题(atomic proposition)到
例3：否认和析取组成的逻辑结合词组是极小功能 完备的。
进一步的思索：
Propositional E q u i v a命l 题e n演c算e s
三、命题公式的进一步分类。
命题公式的规范化-----范式
Propositional E q u i v a命l 题e n演c算e s
文字〔literal〕/符号〔symbol〕： 原子命题或其否认
Table 6
Propositional E q u i v a命l 题e n演c算e s
p ∨ (p ∧ q) p p ∧ (p ∨ q) p
Absorption Laws/吸收律
p → q p ∨ q
p q (p → q) ∧( q → p)
EXAMPLE 5
Propositional E q u i v a命l 题e n演c算e s

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

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

(分配律) (矛盾律) (同一律) (德摩根律) (结合律) (排中律) (零律)
等值演算旳例子
解：⑵ (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））

命题逻辑-

命题逻辑-

4.2有效推理得形式证明
• 自然演绎系统形式证明就是建立在 推理规则基础之上得。这些规则大 约可分为四部分:一就是基本推导 规则,二就是等值替换规则,三就是 条件证明规则,四就是间接证明规 则。
一、基本推导规则:
根据合取式得逻辑特征:
组合式 简记为∧+
根据析取式得逻辑特征:
选言三段论
简记∨-
根据蕴涵式得逻辑特征:
• 例2.判定命题公式“(p∧q) →r”与“p∨(q →r)”就是否逻辑等值。
2.1命题公式之间得逻辑等值
• 如果两个公式就是等值得,那么以这两个公 式为子公式构造一个等值式:
• (﹁p∨ ﹁ q )(﹁ (p∧q))。 • 这个等值式就是恒真得,由此可推知,一个等
值式就是重言式,那么她得两个子公式逻辑 等值。
• 证:① (A∨B)→C
P \A→C
• ② (A∨B) ∨ C
①Impl
• ③ ( A ∧ B) ∨ C
②DeM
• ④ ( A ∨C) ∧( B ∨ C ) ③Dist
• ⑤ A ∨C
④∧-
• ⑥A →C
⑤Impl
作业
• 一、运用真值表方法,判定下列命题就是不 就是等值命题。
• l、如果这匹马儿不吃饱草,那么这匹马儿不 能跑。
• 3.德摩根律 ¬(p∧q) ¬p∨¬q;
•
¬(p∨q) ¬p∧¬q。
• 4、分配律 p∧(q∨r) (p∧q)∨(p∧r)
•
p∨(q∧r) (p∨q) →(p∨r)
• 5、实质蕴涵(p→q) ( p ∨ q)
• 6.假言易位 (p→q) ( q → p )
• 7、移出律 (p∧q) →r p→(q →r)

命题逻辑第一课-命题公式与等值演算省名师优质课赛课获奖课件市赛课一等奖课件

命题逻辑第一课-命题公式与等值演算省名师优质课赛课获奖课件市赛课一等奖课件
命题），整个句子是一种简朴命题.
9
联结词与复合命题(续)
3.析取式与析取联结词“∨”
定义 设 P,Q为任意两个命题，复合命题“P或Q” 称作P与Q 旳析取式，记作P∨Q。其中符合∨， 表达“相容或”，称作析取联结词。P∨Q为假当且 仅当p与q均为假.
例 将下列命题符号化 (1) 2或4是素数. (2) 2或3是素数. (3) 4或6是素数. (4) 小元元只能拿一种苹果或一种梨. (5) 王晓红生于1995年或1996年.
是合式公式 (2) 若A是合式公式，则 (A)也是合式公式 (3) 若A, B是合式公式，则(AB), (AB), (AB),
(AB)也是合式公式 (4) 只有有限次地应用(1)~(3)形成旳符号串才是
合式公式 阐明: 外层括号能够省去
19
合式公式旳层次
定义 (1) 若公式A是单个命题常/变元, 则称A为0层公式. (2) 称A是n+1(n≥0)层公式是指下面情况之一：
12
联结词与复合命题(续)
PQ 旳逻辑关系： P 为 Q 旳充分条件
，Q 为 P 旳必要条件
“若 P，则 Q ” 旳不同表述法诸多： 若 P，就 Q 只要 P，就 Q P 仅当 Q 只有 Q 才 P 除非 Q, 才 P 或 除非 Q, 不然非 P.
当 P 为假时，PQ 为真 常出现旳错误：不分充分与必要条件
13
例 设 p:天冷，q:小王穿羽绒服，
将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，不然天不冷. (7) 假如天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当日冷旳时候.

命题逻辑等值演算

mi(Mi)称为极小项(极大项)的名称。且有mi Mi ,
Mi mi。
例 2 由p, q两个命题变项形成的极小项与极大项
例 3 p, q, r三个命题变项形成的极小项与极大项
三、主范式
1、主析取范式：由极小项构成的析取范式。
2、主合取范式：由极大项构成的合取范式。
3、主范式：主析取范式与主合取范式统称为主范式。
值。
方法三 用等值演算先化简两个公式，再观察.
例3用等值演算法判断下列公式的类型
(1) q(pq)
解： q(pq)
q(pq) （蕴涵等值式）
q(pq)
（德摩根律）
p(qq)
（交换律，结合律）
p0
（矛盾律）
0
（零律）
由最后一步可知，该式为矛盾式.
(pq)r
（否定号内移——德摩根律）
这一步已为析取范式（两个简单合取式构成）
继续： (pq)r
(pr)(qr) （对分配律）
得到合取范式（由两个简单析取式构成）。
二、极小项与极大项
1、定义 在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项（或它的
否定式）均以文字的形式出现且仅出现一次，称这样的简单合取式(简单析取式)为极
离散数学
第二章 命题逻辑等值演算
|
第二章 命题逻辑等值演算
一、等值式
1、等值式：设A，B是命题公式，且AB为重言式,则称A与B是等值的，记作AB。
说明 ：1）符号不是联结符，只是一种记法。
2）若A与B的真值表相同（真值表法），则AB；否则A
B。
3）判断公式等值的方法——利用已知的等值式通过代换得到新的等值式。
五、主范式的应用
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
注意: 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论以及判断结果不惟一确定的也不是 命题
3
例 下列句子中那些是命题？ (1) 2是无理数. (2) 2 + 5 ＝8. (3) x + 5 ＞ 3. (4) 你有铅笔吗？ (5) 这只兔子跑得真快呀！ (6) 请不要讲话！ (7) 我正在说谎话.
15
例
例 求下列复合命题的真值
(1) 2 + 2 ＝ 4 当且仅当 3 + 3 ＝ 6.
1
(2) 2 + 2 ＝ 4 当且仅当 3 是偶数.
0
(3) 2 + 2 ＝ 4 当且仅当 太阳从东方升起. 1
(4) 2 + 2 ＝ 4 当且仅当 美国位于非洲.
0
(5) 函数 f (x) 在x0 可导的充要条件是它在 x0
10
解 令 p:2是素数, q:3是素数, r:4是素数, s:6是素数, 则 (1), (2), (3) 均为相容或. 分别符号化为: p∨r , p∨q, r∨s, 它们的真值分别为 1, 1, 0.
(4), (5) 为排斥或. 令 t :小元元拿一个苹果，u:小元元拿一个梨， 则 (4) 符号化为 (t∧u) ∨(t∧u). 令v :王晓红生于1995年,w:王晓红生于1996年, 则 (5) 可符号化为 (v∧w)∨(v∧w)。注：在 不强调只能生于一个年份时，也可符号化为 v∨w .
例如，令 p： 2 是有理数，则 p 的真值为 0 q：2 + 5 = 7，则 q 的真值为 1
6
复合命题及其符号化：联结词
1.否定式复合命题与否定联结词“”
定义 设P为任意命题，复合命题 “非P”(或“p的否定”)称 为P的否定式，记作P。其中符号表示“非”，称作否定联
结词。P 为真当且仅当P为假（根据联结词的涵义）
第1章 命题逻辑
1.1 命题符号化及联结词 1.2 命题公式及分类 1.3 等值演算 1.4 范式 1.5 联结词完备集 1.6 推理理论
1
1.1 命题符号化及联结词
• 命题与真值 • 原子命题 • 复合命题 • 命题常元 • 命题变元 • 联结词
2
命题与真值
命题: 判断结果惟一的陈述句 命题的真值: 判断的结果，非真即假 真命题: 真值为真的命题 假命题: 真值为假的命题
解 令 p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) q ∧p.
8
例 (续)
令 r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令 t : 张辉与王丽是同学，t 是简单命题 .
说明: (1)~(4)说明描述合取式的灵活性与多样性. (5) 中“与”联结的是两个名词（而不是两个
12
联结词与复合命题(续)
PQ 的逻辑关系： P 为 Q 的充分条件
，Q 为 P 的必要条件
“若 P，则 Q ” 的不同表述法很多： 若 P，就 Q 只要 P，就 Q P 仅当 Q 只有 Q 才 P 除非 Q, 才 P 或 除非 Q, 否则非 P.
当 P 为假时，PQ 为真 常出现的错误：不分充分与必要条件
2.合取式复合命题与合取联结词“∧”
定义 设P,Q为任意两个命题,复合命题“P且Q”(或“P与Q”) 称为P与Q的合取式，记作P∧Q。其中符号∧表示“且”， 称作合取联结词。 P∧Q为真当且仅当P与Q均为真。
注意：合取式描述方式的灵活性与多样性 分清简单命题与复合命题
7
例 将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学.
连续.
0Hale Waihona Puke 16联结词与复合命题(续)
以上给出了5个联结词：, , , , ，组成 一个联结词集合{, , , , }，
联结词的优先顺序为：, , , , ; 如果出 现的联结词同级，又无括号时，则按从左到右 的顺序运算; 若遇有括号时，应该先进行括号 中的运算.
注意: 本书中使用的 括号全为圆括号.
pq pq pq qp qp pq qp qp
注意： pq 与 qp 等值（真值相同）
14
联结词与复合命题(续)
5. 等价式与等价联结词“” 定义 设P，Q为任意两个命题，复合命题 “P当且
仅当Q”称作P与Q的等价式，记作PQ. 称作 等价联结词.PQ为真当且仅当P与Q真值相同. 说明: (1) PQ 的逻辑关系: P与Q互为充分必要条件 (2) PQ为真当且仅当P与Q同真或同假
11
联结词与复合命题(续)
4.蕴涵式与蕴涵联结词“”
定义 设 P,Q为任意两个命题，复合命题 “若P, 则Q” 称作P与Q的蕴涵式，记作PQ，并称P是 蕴涵式的前件或前提，q为蕴涵式的后件或结论.
符号表示“若，则”（形式推论关系），称作
蕴涵联结词。 根据形式推论的涵义，PQ为假 当且仅当 P为真且 Q为假。
命题），整个句子是一个简单命题.
9
联结词与复合命题(续)
3.析取式与析取联结词“∨”
定义 设 P,Q为任意两个命题，复合命题“P或Q” 称作P与Q 的析取式，记作P∨Q。其中符合∨， 表示“相容或”，称作析取联结词。P∨Q为假当 且仅当p与q均为假.
例 将下列命题符号化 (1) 2或4是素数. (2) 2或3是素数. (3) 4或6是素数. (4) 小元元只能拿一个苹果或一个梨. (5) 王晓红生于1995年或1996年.
真命题 假命题 真值不确定 疑问句 感叹句 祈使句 悖论
(3)~(7)都不是命题
4
命题的分类
简单命题(原子命题)： 简单陈述句构成的命题
复合命题： 由简单命题与联结词按一定规则复合 而成的命题
5
简单命题符号化
用小写英文字母 p, q, r, … ,pi,qi,ri (i≥1）表示 简单命题 真值的符号化：用“1”表示真，用“0”表示假
13
例 设 p:天冷，q:小王穿羽绒服，
将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候.