当前位置：文档之家 › 离散数学-1-4 真值表与等价公式

离散数学-1-4 真值表与等价公式

  • 格式：ppt
  • 大小：173.00 KB
  • 文档页数：28

下载文档原格式

  / 28

合集下载

离散数学讲义

离散数学讲义
其内容较广，主要包括数理逻辑、 集合 论、图论、代数结构等四个基本部分。
7
什么是离散数学？
离散数学将日常的概念、判断、 推理用数学符号来表示，用数学方法 进行思维。其目标是掌握严密的思维 方法、严格证明的推理能力和演算能 力，掌握处理各种具有离散结构的事 物的描述工具与方法，适应学习其他 专业课程的各种需要，为学习其它计 算机课程提供必要的数学工具。
设P，Q是两命题，其条件命题是一个复合命题，记做P→Q， 读做“如果P，则Q”。
P 1
真值关系：
Q 1 0 1
PQ 1 0 1
“善意的推定”
1 0
0
0
1
28
1-2 联结词（续）
5、双条件
设P，Q是两命题，其双条件命题是一个复合命题， 记做P↔Q，读做“如果P，则Q”。
P 1 真值关系： 1 0 0


命题：能够判断真假的陈述语句。
例：‘中国是一个国家’， ‘9为素数’。
原子命题：不能分解成更简单的陈述语 句的命题。 复合命题：由连结词、标点符号和原子 命题复合构成的命题。

一般用字母“T”表示“真”，“F”表示 “假”。也经常用“1”表示“真”，“0” 表示“假”。
13
1-1 命题及其表示法（续）
T
F
F
T
F
T
F
T
F
F
T
T
F
命题的形式化描述：(P↔Q)。
35
1-3 命题公式及翻译（续）
例题3： （自学）
例题4： （自学）
例题5： （自学） 例题6： （自学）
36
习题：

* 各章节后习题中的双号大题中的双 号小题。

离散数学第1章 命题逻辑

离散数学第1章 命题逻辑
P Q 原命题 P Q （P Q） 利用联结词组合起来
TT F
T
TF T
F
F P、Q真值相同时为F，否则为T
T 原命题与 (P Q)真值相同
FT T
F
T
(P Q)
FF F
T
F
总结：命题公式翻译的原则（即本质的东西）：
• 列出在各种指派下的原命题的取值。
• 翻译出来的公式如果与原命题的值一致，则翻译正确，否则， 翻译的公式则是错误的。
(4) 只有有限次地应用（1）、（2）、（3）所得的结果才是公式。
其中（1）为基础，（2），（3）为归纳，（4）为界限，这是一 个递归的定义。
例如：判别下列式子是否是公式？
(P Q) (PQ (P (P Q)) (P Q) (((P Q) R) (P Q)) (PQ R) (P Q)R)
(1)以离散量为研究对象，以讨论离散量的结构和相互之间的关 系为主要目标，这些对象一般是有限个或可数个元素，充分描述了 计算机科学离散性的特点，与我们以前学过的连续数学如高等数学、 数学分析、函数论形成了鲜明对比。
(2)它是数学中的一个分支，因而它有数学的味道，比如用一 些符号、引进一些 定义、运用定理推导等等。因而学习离散数学， 对提高我们的抽象能力，归纳能力、逻辑推理能力将有很大帮助。
（5）：我正在说谎。 若它是命题，则应有确定的真值。 若为T，则我确定说谎，我讲的是真话，与说谎矛盾。 若为F，则我不在说谎，我说的是真话，原命题成立，则“我 确实是在说谎” ，与“不在说谎”矛盾。 所以它不是命题，不能确定真假，是悖论。
1-1 命题及其表示法
（6）：X=3 不是命题 不能判断真假。
应用
Image segmentation

离散数学第一章数理逻辑

离散数学第一章数理逻辑
故命题可形式化为:(A∧B∧C) ↔ P
34
中北大学离散数学课程组
例3.他既聪明又用功。 例4.他虽聪明但不用功。 例5.除非你努力，否则你将失败。 例6.张三或李四都可以做这件事。
35
中北大学离散数学课程组
作业：
（1）判断下列公式哪些是合式公式，哪些不是合 式公式。
a.(Q→R∧S） b.(P ↔(R →S)) c.((┐P→Q)→(Q→P)) d.(RS→T) e.((P→(Q→R))→((P→Q)→(P→R)) （2）用符号形式写出下列命题。 a.假如上午不下雨，我去看电影，否则就在家里读
书或看报。
36
中北大学离散数学课程组
b.我今天进城，除非下雨。 c.仅当你走我将留下。
37
中北大学离散数学课程组
练习：将下列命题符号化。 1）说逻辑学枯燥无味（P）或毫无意义（Q）是不对的。 2）如果明天有雾（P），则我乘车（Q），不坐飞机（R）。 3）有雨（P）就刮风（Q）。 4）如果小王没来上课（P），一定是他生病了（Q）。 5）如果我上街（P），我就去图书馆看看（Q），除非我很累
2020/6/30
10
中北大学离散数学课程组
结论： 命题一定是陈述句，但并非一切陈述句都是命题。 命题的真值有时可明确给出，有时还需要依靠环境、 条件、实际情况时间才能确定其真值。
2020/6/30
11
中北大学离散数学课程组
二、命题的分类
1.原子命题(简单命题)：不能再分解为更为简单命 题的命题。
游； （5）两个三角形全等当且仅当三角形的三条边全部
相等。 (6) 张辉与王丽是同学。
2020/6/30
24
中北大学离散数学课程组
例 （解）

1-3、4翻译、真值表

1-3、4翻译、真值表

(4)除非你陪我或替我叫车，否则我不去。 除非你陪我或替我叫车，否则我不去。 除非你陪我或替我叫车 (5)如果下班早，就去商店看看，除非我很累。 如果下班早， 如果下班早 就去商店看看，除非我很累。 解 (4)设 P：你陪我。 Q：你替我叫车。 R：我去。 设 ：你陪我。 ：你替我叫车。 ：我去。 则命题符号化为： 则命题符号化为： R →（ P ∨ Q） （ ） 或┐( P ∨ Q ) → ┐ R (5)设 P：我下班早。 Q：我去商店看看。R：我很 设 ：我下班早。 ：我去商店看看。 ： 累。 则命题符号化为： 则命题符号化为： ( P ∧ ┐R ) → Q 或 ┐R → ( P → Q )
这个合式公式的定义，是以递归形式给出的，其中 称为 这个合式公式的定义，是以递归形式给出的，其中(1)称为 递归形式给出的 基础， 称为归纳， 称为界限 称为界限。 基础，(2)(3)称为归纳，(4)称为界限。 称为归纳
按照定义，下列公式都是合式公式： 按照定义，下列公式都是合式公式： ┐(P∧Q）， ），┐(P→Q)，(P→(P∨┐Q) ) ， ∧ ）， ， ∨ (((P→Q ) ∧(Q→R)) (S T)) 而 (P→Q）→(∧Q)，(P→Q，(P∧Q ) →Q ) ） ∧ ， ， ∧ 等都不是合式公式。 等都不是合式公式。
二、翻译（符号化） 翻译（符号化）
有了联结词的合式公式概念， 有了联结词的合式公式概念，我们可以把自然语言中的有 些语句，翻译成数理逻辑中的符号形式。 些语句，翻译成数理逻辑中的符号形式。 把一个用文字叙述的命题相应地写成由命题标识符、 把一个用文字叙述的命题相应地写成由命题标识符、联结 词和圆括号表示的合式公式，称为命题的符号化 命题的符号化。 词和圆括号表示的合式公式，称为命题的符号化。 符号化应该注意下列事项： 确定给定句子是否为命题。 符号化应该注意下列事项：① 确定给定句子是否为命题。 句子中联结词是否为命题联结词。 ② 句子中联结词是否为命题联结词。③ 要正确地表示原子命 题和适当选择命题联结词。 题和适当选择命题联结词。

离散数学第一章

离散数学第一章

常称为“非”运算，所有可能的运算结果可用下表
（真值表）表示。
P
┒P
T F
F T
例: (a) P: 3是偶数。
则┑P： 3不是偶数。
(b)
的”。 (c) (d)
Q: 4 是质数。
则┑Q： 4 不是质数。或 “说4 是质数是不对 R: 我们都是汉族人。 则┒R: 我们不都是汉族人。 S: 今天下雨并且今天下雪。 则 ┒S:今天不下雨或者今天不下雪。
以上命题， (a)的真值取决于今天的天气，(b)和(c)是真， (d)
已无法查明它的真值，但它是或真或假的， 将它归属于命题。 (e)目前尚未确定其真假， 但它是有真值的，应归属于命题。
例 2 下述都不是命题: (a) x+y＞4。 (b) x=3。 (c) 真好啊！ (d) 你去哪里？
(a)和(b)是陈述句， 但不是命题， 因为它的真值取决于x和
∨为析取联结词。 P∨Q为真当且仅当P和Q中至少
一个为真。
P∨Q的逻辑关系是P与Q中至少有一个成立，因而， 只有P与Q同时为假时， P∨Q 才为假，其他情况 下， P∨Q 均为真。
“∨”代表的运算是二元运算，常称为“或”运 算，所有可能的运算结果用真值表表示为： P∨Q
P
Q
T T F F
T F T F
1-1 命题及其表示法
• 命题的概念
能够判断真假的陈述句，有确定真值。
例： 1、 1+1=2； 2、 明天开会吗？ 3、 我正在说谎。 4、我学英语，或者我学日语。
• 命题的表示
命题通常使用大写字母A，B，„，Z或带下标的 大写字母或数字表示，如Ai，[10]，R等，例如 A1：我是一名大学生。 [10]：我是一名大学生。 R：我是一名大学生。

真值表与等价公式

真值表与等价公式
(4)当且仅当有限次地应用（1）、(2)、（3）所得 到的符号串是命题公式。
思考：命题公式是命题吗？为 什么？
解答：命题公式不一定是命题。
因为命题公式没有确定的真值。
把符号命题翻译成自然语言命题： 这种翻译比较简单，只要求用词准确，力求保
持原命题的意思。 例 设 A: 今天下雨。
B: 今天下雪。 C: 今天天晴。试把下列命题翻译成自然语言: 1) ┐(A∧B) 2) C↔ (┐A∧┐B) 3) A∨B→┐C 解 :1) 说今天下雨且下雪是不对的。 2) 今天天晴当且仅当今天既不下雨又不下雪。 3) 如果今天下雨或者下雪, 今天就不是晴天。
¬(p→q)∧ q
0
0
0
0
( p→q)∧¬r 1 0 1 0 0 0 1 0
公式的分类 设A为一个命题公式，则：
1 若A在它的所有解释下都为真， 则 称A为 永 真 式(也 称 为 重 言 式)
2 若A在它的所有解释下都为假， 则 称A为 永 假 式(也 称 为 矛 盾 式)
3 若A在 它 的 至 少 一 个 解 释为下真 ， 则 称A为 可 满 足 式(也 称 偶 然 式)
定义1-12 如果X是命题公式A的一部分，且X本身 是一个合式公式，则称X为公式A的子公式。
定理1-3 设X是命题公式A的子公式，若X⇔Y，如 果将A中的X用Y置换，所得的公式B与命题公式 A等价。
证明：
因为在相应分量的任一种真值指派下，X和Y的 真值都相同，用Y置换X后，公式B与A在相应分 量的真值指派下，其真值仍相同，所以A⇔B 。
一、命题公式
回顾
命题公式也称命题演算的合式公式(Well form formula,简写为wff)。
定义1-6 命题公式的递归定义如下：

离散数学部分概念和公式总结

离散数学部分概念和公式总结

离散数学部分概念和公式总结命题：称能判断真假的陈述句为命题。

命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。

命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。

给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。

若指定的一组值使A的值为真，则称成真赋值。

真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。

将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。

命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。

（2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。

（3）若A至少存在一组赋值是成真赋值，则A是可满足式。

主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。

主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。

命题的等值式：设A、B为两命题公式，若等价式A?B是重言式，则称A与B 是等值的，记作A<=>B。

约束变元和自由变元：在合式公式xA和 xA中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。

一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A?B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。

前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Qk…xkB，称A为前束范式。

集合的基本运算：并、交、差、相对补和对称差运算。

笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。

二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。

离散数学重要公式定理汇总

离散数学重要公式定理汇总
⑴ 交换律 对任何集合A、B，有AB=BA。 ⑵ 结合律 对任何集合A、B、C，有 (AB)C=A(BC)。教材里有证明。 ⑶ 同一律 对任何集合A，有AΦ=A。 ⑷ 对任何集合A，有AA=Φ。 ⑸ ∩对可分配 A∩(BC)=(A∩B)(A∩C)
关系的性质
一. 自反性
定义:设R是集合A中的关系，如果对于任意x∈A都 有<x,x>∈R (xRx)，则称R是A中自反关系。 即 R是A中自反的关系x(xAxRx) 例如： 在实数集合中,“”是自反关系，因
离散数学重要公式定理汇总
大一上
Formula
基本的等价公式
⑴ 对合律 PP ⑵ 幂等律 P∨PP P∧PP ⑶ 结合律 P∨(Q∨R)(P∨Q)∨R P∧(Q∧R)(P∧Q)∧R ⑷交换律 P∨QQ∨P P∧QQ∧P ⑸分配律 P∨(Q∧R)(P∨Q)∧(P∨R) P∧(Q∨R)(P∧Q)∨(P∧R) ⑹ 吸收律 P∨(P∧Q)P P∧(P∨Q)P ⑺德．摩根定律 (P∨Q)P∧Q (P∧Q)P∨Q
2013-12-16 7
Formula
• 蕴含的性质
*若AB且A为重言式，则B必为重言式 *若AB且BC，则AC (传递性) *若AB且AC，则A(B ∧ C) *若AB且C B，则(A∨C) B 证明见书P22
2013-12-16
8
conjunction
一、全功能真值表
2013-12-16 10
normal form
主析取范式定义 析取范式 A1∨A2∨...∨An, , 其中每个Ai (i=1,2..n) 都是小项，称之为主析取范式。 思考：主析取范式与析取范式的区别是什么？ 主析取范式的写法 方法Ⅰ：列真值表 ⑴列出给定公式的真值表。 ⑵找出真值表中每个“T”对应的真值指派再对 应的小项。 ⑶用“∨”联结上述小项，即可。

离散数学重要公式定理汇总分解

离散数学重要公式定理汇总分解
⑴ 交换律 对任何集合A、B，有AB=BA。 ⑵ 结合律 对任何集合A、B、C，有 (AB)C=A(BC)。教材里有证明。 ⑶ 同一律 对任何集合A，有AΦ=A。 ⑷ 对任何集合A，有AA=Φ。 ⑸ ∩对可分配 A∩(BC)=(A∩B)(A∩C)
关系的性质
一. 自反性
定义 :设 R是集合 A中的关系，如果对于任意x∈A都 有<x,x>∈R (xRx)，则称R是A中自反关系。 即 R是A中自反的关系x(xAxRx) 例如： 在实数集合中 , “ ”是自反关系，因
例 邻居关系和朋友关系是对称关系。
四.反对称性
定义:设R为集合A中关系,若对任何x, y∈A,如果有 xRy,和yRx,就有x=y,则称R为A中反对称关系 。
R是A上反对称的 xy((xAyAxRyyRx) x=y) xy((xAyAxyxRy)y Rx) (P112) 由R的关系图看反对称性：两个不同的结点之间 最多有一条边。 从关系矩阵看反对称性：以主对角线为对称的两 个元素中最多有一个1。 另外对称与反对称不是完全对立的，有些关系它 既是对称也是反对称的，如空关系和恒等关系。
如 实数的大于关系>，父子关系是反自反的。 注意：一个不是自反的关系，不一定就是反自反
的。
三.对称性 定义:R是集合A中关系,若对任何x, y∈A,如果有
xRy,必有yRx,则称R为A中的对称关系。 R是A上对称的
xy((xAyAxRy) yR方向相反的两 条边。 从关系矩阵看对称性：以主对角线为对 称的矩阵。
3
2018/10/25
Formula
等价公式(前10个)与集合论的公式比较： ⑴ 对合律 ~~AA ~A表示A的绝对补集 ⑵ 幂等律 A∪AA A ∩ A A ⑶ 结合律 A∪(B∪C)(A∪B)∪C； A∩(B∩C)(A∩B)∩C ⑷交换律 A∪BB∪A A∩BB∩A ⑸分配律 A∪(B∩C)(A∪B)∩(A∪C) A∩(B∪C)(A∩B)∪(A∩C) ⑹ 吸收律 A∪(A∩B)A A∩(A∪B)A

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

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

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

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

作为一门独立科学，十七世纪，德国的莱布尼兹(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+, …,等表示命题，称之为命题标识符。

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

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

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

离散数学第一章

离散数学第一章

离散数学第一章1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。

1.1.2 命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。

A1:我是一名大学生.[10]：我是一名大学生。

R：我是一名大学生。

1.2命题联结词1.2.1 否定联结词﹁PP P0 11 01.2.2 合取联结词∧P∧P Q Q0 0 00 1 01 0 01 1 11.2.3 析取联结词∨P∨P Q Q0 0 00 1 11 0 11 1 11.2.4 条件联结词→P Q Q0 0 10 1 11 0 01 1 11.2.5 双条件联结词?P?P Q Q0 0 10 1 01 0 01 1 11.2.6 与非联结词↑P↑P Q Q0 0 10 1 11 0 11 1 0性质：（1）P↑P?﹁（P∧P）?﹁P；（2）（P↑Q）↑（P↑Q）?﹁（P↑Q）? P∧Q；（3）（P↑P）↑（Q↑Q）?﹁P↑﹁Q? P∨Q。

1.2.7 或非联结词↓P↓P Q Q0 0 10 1 01 0 0性质：（1）P↓P?﹁（P∨Q）?﹁P；（2）（P↓Q）↓（P↓Q）?﹁（P↓Q）?P∨Q；（3）（P↓P）↓（Q↓Q）?﹁P↓﹁Q?﹁（﹁P∨﹁Q）?P∧Q。

1.3 命题公式、翻译与解释1.3.1 命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、P?Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。

例如，下面的符号串都是公式：（（（（﹁P）∧Q）→R）∨S）（（P→﹁Q）?（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）?（∧Q））（∧Q）1.3.2 命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。

1-3命题公式与翻译1-4真值表与等价公式解析

1-3命题公式与翻译1-4真值表与等价公式解析

PQR TTT TTF TFT TFF FTT FTF FFT FFF
Q∨R T T T F T T T F
P → (Q∨R) T T T F T T T T
P17(1) (C) (P ∨Q) (Q ∨P)
PQ TT TF FT FF
P ∨Q T T T F
Q ∨P T T T F
(P ∨Q) (Q ∨P) T T T T
命题符号化步骤： ❖(1)分成原子命题 ❖(2)用大写字母代替命题 ❖(3)按题意用联结词
自然语言的语句用Wff 形式化注意方面：
① 要准确确定原子命题，并将其形式化。 ② 要选用恰当的联结词，尤其要善于识别自然语 言中的联结词（有时它们被省略），否定词的位置要 放准确。
③ 必要时可以进行改述，即改变原来的叙述方式， 但要保证表达意思一致。
FF T
T
F
T
T
T
❖ 可以看出，有一类公式不论命题变元作何种 指派，其真值永为真(假)，记为T(F)。
❖ 在真值表中，命题公式真值的取值数目，决 定于分量的个数。一般说来，n个命题变元组 成的命题公式共有2n种真值情况。
练习 17页（1）a, c, e 18页（6）
P17 (1)求下列复合命题的真值表 (a) P → (Q∨R)
若设 P：你努力。 Q：你失败。 本命题可表示为：
┐P→Q
例题6 张三或李四都可以做这件事。
解 这个命题的意义是： 张三可以做这件事，并且李四也可以做这件事。 若设
P：张三可以做这事。 Q：李四可以做这 事。 本命题可表示为：
P∧Q
例题7 （1）2是素数，这是假的。
（2） 2与4都是素数，这是不对的。 解 若设
④ 需要的括号不能省略，而可以省略的括号， 在需要提高公式可读性时亦可不省略。

离散数学命题逻辑 第一章(1)

离散数学命题逻辑 第一章(1)
第一篇 数理逻辑
我现在年纪大了，搞了这么多年软件，错误 不知犯了多少，现在觉悟了。我想，假如我早在 数理逻辑上好好下点功夫的话，我就不会犯这么 多错误。不少东西逻辑学家早就说过了，可是我 不知道。要是我能年轻20岁的话，我就会回去学 逻辑。
E.W.Dijkstra
先看著名物理学家爱因斯坦出过的一道题： 一个土耳其商人想找一个十分聪明的助手协助他经商，有两人 前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间 漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是 红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置 弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后， 请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人 将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下 的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商 人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽 子。” 请问这个人说得对吗？他是怎么推导出来的呢？
Page 13
2、命题满足的条件
命题的语句形式：陈述句 非命题语句：疑问句、命令句、感叹句、非命题陈述句 (悖论语句) 命题所表述的内容可决定是真还是假，不能不真又不假， 也不能又真又假。
Page 14
3、举例
• • • • • • • • • 北京是中国的首都。 土星上有生物。 ３＋２≥9。 1+101=110 请关门！ 你要出去吗？ 如果天气好，那么我去散步。 x＝ 2。 我正在撒谎。
Page 9
第一章 命题逻辑
研究以命题为基本单位构成的前提和结论之间的 可推导关系。
Page 10
第一章 命题逻辑
1
命题及其表示方法 联结词

离散数学第1章命题公式与翻译 真值表与等价公式

离散数学第1章命题公式与翻译 真值表与等价公式

这个合式公式的定义，是以递归形式给出的，其 中(1)称为基础，(2)(3)称为归纳，(4)称为界限。
按照定义，下列公式都是合式公式： ┐(P∧Q），┐(P→Q)，(P→(P∨┐Q)， (((P→Q）∧(Q→R)) （S T)) 而 (P→Q）→(∧Q)，(P→Q，(P∧Q）→Q） 等都不是合式公式。
在这里，请注意和的区别与联系： 区别：

是逻辑联结词，它出现在命题公式中；
不是逻辑联结词，它表示两个命题公式的一种

关系，不属于这两个公式的任何一个公式中的符 号。

2、等价公式的证明方法： ⑴真值表法
例题5 证明 P Q (P→Q) ∧(Q→P) 证明 列出其值表 表 1-4.7
注意


由表1-4.4 (表1-4.2)可以看出，有一类公式不论命 题变元作何种指派，其真值永为真(假)，我们把这 类公式记为T(F)。 在真值表中，命题公式真值的取值数目，决定于 分量（命题变元）的个数。例如，由2个命题变元 组成的命题公式共有四种可能的真值，由3个命题 变元组成的命题公式共有八种真值。一般说来，n 个命题变元组成的命题公式共有2n种真值情况。
同理(P∧Q)∨(┐P∧┐Q)与P 同，如表1-4.6所示。 表1-4.6 P Q P T T T F F T F F T F F T Q
Q对应的真值相
(P∧Q)∨(┐P∧┐Q) T F F T
二、等价公式
1.定义
定义1-4.2 给定两个命题公式A和B，设P1， P2，……，Pn为所有出现于A和B中的原子变 元，若给P1，P2，……，Pn任一组真值指派， A和B的真值都相同，则称A和B是等价的或逻 辑相等。记作A B。
P T T F F

离散数学定义列表

离散数学定义列表

A.定义1.简单命题/原子命题、复合命题2.定义1.1：否定式、否定联结词3.定义1.2：合取式、合取联结词4.定义1.3：析取式、析取联结词定义1.4：蕴含式、前件、后件、蕴含联结词；规定19.4、20.45.定义1.5：等价式、等价联结词；规定6.联结词的定义（真值表）表1.1、优先级7.命题常项、命题变项（不是命题）、合式公式8.定义1.6：原子命题公式、公式、子公式9.定义1.7：公式层次10.定义1.8：赋值/解释、成真赋值、成假赋值11.定义1..9：真值表12.定义1..10：重言式/永真式、矛盾式/永假式、可满足式13.哑元************************重点：命题逻辑等值演算***************15.等值演算、置换规则4.116.定义2.2：文字、简单析取式、简单合取式17.定义2.3：析取范式、合取范式、范式18.定义2.4：极小项、极大项定义2.5：主析取范式、主合取范式********************************一阶逻辑**********************19.个体词、个体常项、个体变项、个体域/论域、全总个体域20.谓词、谓词常项、谓词变项、n元谓词、0元谓词量词、全称量词、存在量词全称蕴含、存在合取P71 5.3********************************集合代数**********************21.定义6.1：子集、包含22.定义6.2：相等23.定义6.3：真子集定义6.4：空集P139 124.n元集、m元子集、（单元集）25.定义6.5：幂集公式：26.定义6.6：全集27.定义6.7:并集、交集、相对补集、不交28.定义6.8：对称差集29.定义6.9：绝对补集30.定义6.10：广义并31.定义6.11：广义交幂等律、结合律、交换律、分配律、同一律、零律、排中律、矛盾律、吸收律、德摩根律、双重否定律eg6.8,P108 36****************************重点：二元关系***********************32.定义7.1：有序对/序偶33.定义7.2：笛卡尔积性质P11134.定义7.3：二元关系/关系P139 735.定义7.4：从A到B的二元关系、A上的二元关系、空关系36.定义7.5：A上的全域关系（E）、恒等关系（I）、小于等于关系（L）、整除关系（D）、包含关系（R）37.关系矩阵（x行，y列）、关系图38.定义7.6：定义域、值域、域39.定义7.7：逆关系40.定义7.8：右复合（左复合）41.定义7.9：R在A上的限制、A在R下的像42.定义7.10：关系的n次幂定义7.11：自反、反自反定义7.12：对称、反对称定义7.13：传递43.定义7.15：等价关系（性质）P142 32(4)、4144.定义7.16：等价类45.定义7.17：商集46.定义7.18：划分、划分块 P134 eg7.1847.定义7.19：偏序关系（性质）48.定义7.20：小于、可比49.定义7.21：全序关系/线序关系50.定义7.22：偏序集P13551.定义7.23：偏序集中顶点的覆盖关系（为画哈斯图）P143 43（2）***************************函数*******************************53.定义8.1：函数54.定义8.2：函数相等55.定义8.3：从A到B的函数P171 6（8）（9）56.定义8.4：从A到B的函数的集合B A57.定义8.5：A1在ƒ下的像、函数的像、完全原像定义8.6：满射、单射、双射/一一映射P173 2558.定义8.7: 常函数、恒等函数、单调递增、单调递减、严格单调递减、特征函数、自然映射59.反函数（双射）*************************代数系统*****************************60.定义9.2：一元运算定义9.3：可交换/交换律定义9.4：可结合/结合律定义9.5：幂等律、幂等元61.定义9.6：可分配/分配律62.定义9.7：吸收律63.定义9.8：左单位元（右单位元）、单位元/幺元64.定义9.9：左零元（右零元）65.定义9.10:左逆元（右逆元）、逆元、可逆66.定义9.11：消去律、左消去律（右消去律）注意P183 eg9.667.定义9.12：代数系统/代数、特异元素/代数常数68.定义9.13：具有相同的构成成分/同类型69.定义9.14：子代数系统/子代数、平凡的子代数、真子代数（函数对子集封闭）70.定义9.15：积代数、因子代数************************************群与环***************************************半群与群都是具有一个二元运算的代数系统71.定义 10.1：半群（）、幺半群/独异点（）、群（）72.有理数加群、整数加群、实数加群、复数加群、四元群、子代数、语言73.定义 10.2：有限群、无限群、平凡群、交换群/Abel群74.定义 10.3：n次幂75.定义 10.4：（元素的）阶/周期、k阶元、无限阶元***********************************格与布尔代数**********************************格与布尔代数是具有两个二元运算的代数系统定义11.1：格（偏序集定义的）P22176.幂集格、子群格77.定义11.2：对偶命题、格的对偶原理78.定义11.3：格（代数系统定义的）79.定义11.4：子格80.定义11.5：分配格81.定义11.6：全上界、全下界82.定义11.7：有界格83.定义11.8：补元84.定义11.9：有补元定义11.10：布尔格/布尔代数（有补分配格）85.定义11.11：布尔代数（代数系统定义）86.定义11.12：原子**********************************14.图的基本概念********************************87.无序积A&B88.定义14.1：无向图、顶点集、顶点/结点、边集、无向边/边89.定义14.2：有向图、无向边/边90.（P294）图、阶、n阶图；零图、平凡图；空图；标定图、非标定图；基图；端点、关联、关联次数、环、相邻；始点、终点、孤立点；邻域、闭邻域、关联集、后继元集、先驱元集91.定义14.3：平行边、重数、多重图、简单图92.定义14.4：度数/度、出度、入度、最大度、最小度、悬挂顶点、悬挂边、偶度（奇度）顶点93.度数列、可图化的、可简单图化的，出度列、入度列94.定义14.6：n阶无向完全图/n阶完全图、n阶有向完全图、n阶竞赛图95.定义14.7：k-正则图96.定义14.8：母图、真子图、生成子图、导出的子图97.定义14.10：删除边e、删除E’、删除顶点v、删除V‘、边的收缩、新加边删点边不留，删边点还在98.定义14.11：通路、始点、终点、长度、回路、简单通路、简单回路、初级通路/路径、初级回路/圈、奇圈、偶圈、复杂通路、复杂回路99.定义14.12:连通、连通图、非连通图100.定义14.13：连通分支、连通分支数101.定义14.14：短程线、距离102.定义14.15：点割集、割点103.定义14.16：边割集/割集、割边/桥104.定义14.21：弱连通图/连通图、单向连通图、强连通图105.定义14.22：二部图/二分图/偶图，完全二部图定义14.23：无向图关联次数、关联矩阵定义14.24：有向图关联矩阵定义14.25：邻接矩阵定义14.26可达矩阵**********************************15.欧拉图与哈密顿图****************************106.定义15.1：欧拉通路、欧拉回路、欧拉图、半欧拉图107.定义15.2：哈密顿通路、哈密顿回路、哈密顿图、半哈密度图**********************************16.树*****************************************108.定义16.1：无向树/树、森林、平凡树、树叶、分支点109.定义16.2：生成树、树枝、弦、余树110.定义16.:5：权、最小生成树111.避圈法（Kruskal算法）B.定理1.定理2.1：简单析取式是重言式的充要条件；简单合取式是矛盾式的充要条件2.定理2.2：析取范式（矛盾式）、合取范式（重言式）3.定理2.3：范式存在定理4.定理2.4：极小项和极大项关系5.定理2.5：主析、主合存在并唯一6.定理6.1：子集是一切集合的子集推论：空集是唯一的7.定理7.1：逆关系性质8.定理7.2：复合结合律、逆9.定理7.3：关系与恒等关系复合10.定理7.4：复合分配律注意交11.定理7.5：限制和像的分配律注意像的交12.定理7.6：有穷集上只有又穷多个不同的二元关系13.定理7.7：关系的幂性质14.定理7.8：有穷集A上的关系R的幂序列R0，R1，R2等是一个呈现周期性变化的序列15.定理7.9：五大性质16.定理7.14：等价关系的性质17.定理8.1：函数的复合（关系的右复合）推论1：函数复合结合律推论2：ƒ：A→B，g：B→C，则ƒ。

离散数学

离散数学

第一章命题逻辑1.1 命题及其表示方法1.2 联结词1.3 命题公式与翻译1.4 真值表与等价公式1.5 重言式与蕴含式1.6 其它联结词1.7 对偶与范式1.8 推理理论1.1 命题及其表示方法命题：具有确定真值的陈述句命题的类型（原子命题和复合命题）命题的表示（一个命题标识符（比如P）表示确定的命题）重点：如何判断语句是否为命题。

1.2 联结词否定⌝合取∧析取∨条件→双条件↔重点：五种联结词的含义、真值表1.3 命题公式与翻译命题公式符号化：所谓命题的符号化就是把一个用文字叙述的句子相应地写成由命题标识符、联结词和括号表示的合式公式。

命题符号化的重要性命题符号化是很重要的，一定要掌握好，在命题推理中最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。

重点：命题的符号化符号化应该注意下列事项:①确定给定句子是否为命题。

②句子中连词是否为命题联结词。

③要正确地表示原子命题和适当选择命题联结词。

1.4 真值表与等价公式真值表的构造方法(1) 找出公式中所含的全体命题变元P1, P2, …, Pn, (若无下角标就按字典顺序排列), 列出2n个赋值. 赋值从00…0开始, 然后按二进制加法依次写出各赋值, 直到11…1为止.(2) 按从低到高的顺序写出公式的各个层次.(3) 对应各个赋值计算出各层次的真值, 直到最后计算出公式的真值.等价关系的含义等价式的判别方法•真值表法•等价演算法基本等价式（必须掌握）(1)对合律（双重否定）：⌝⌝P⇔P(2)幂等律：P∧P⇔P，P∨P⇔P(3)结合律：(P∧Q)∧R⇔P∧(Q∧R)，(P∨Q)∨R⇔P∨(Q∨R)(4)交换律：P∧Q⇔Q∧P，P∨Q⇔Q∨P(5)分配律：P∧(Q∨R)⇔(P∧Q)∨(P∧R)，P∨(Q∧R)⇔(P∨Q)∧(P∨R)(6)德·摩根律：⌝ (P∧Q) ⌝⇔P∨⌝Q，⌝ (P∨Q) ⌝⇔P∧⌝Q(7)吸收律：P∧(P∨Q)⇔P，P∨(P∧Q)⇔P(8)同一律：P∧T⇔P，P∨F⇔P(9)零律：P∧F⇔F，P∨T⇔T(10)否定律：P∧⌝P⇔F，P∨⌝P⇔T(11) 条件式转化律：P→Q⌝⇔P∨Q，P→Q⌝⇔Q→⌝P(12) 双条件式转化律：P↔Q ⇔(P→Q)∧(Q→P) ⇔(P∧Q)∨(⌝P∧⌝Q)⌝ (P↔Q) ⇔P⌝↔Q ⌝⇔P↔Q(13) 输出律(CP规则)：P→(Q→R) ⇔(P∧Q)→R重点：等价式的证明、基本等价式1.5 重言式与蕴含式重言式或永真公式定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为真，则称该命题公式为重言式或永真公式。

1-4 主范式

1-4 主范式
离散数学西安电子科技大学软件学院第一篇数理逻辑11命题第1课时第1章命题逻辑13逻辑等价式与永真蕴含式12命题公式14主范式15命题逻辑的推理与证明方法第2课时第3课时第4课时第5课时16命题逻辑的应用第6课时西安电子科技大学软件学院主析取范式141极小项含n个命题变元的极小项是所有这n个变元或其否定形式恰出现一次所构成的合取式这样的极小项共有2n个
§1.4.2 主合取范式
方法一、真值表法
西安电子科技大学 软件学院
【例题】求命题公式A=¬P ∧ (Q → R)的主合取范式。
§1.4.2 主合取范式
方法二、等价推演法
西安电子科技大学 软件学院
【例题】求命题公式A=¬P∧(Q→R)的主合取范式。
A⇔ ⇔ ⇔
¬P∧(¬ Q ∨R) (¬P∨(Q∧¬Q)∨(R∧¬R) )∧((P∧¬P)∨¬Q∨R) (¬P∨Q∨R)∧(¬P∨Q∨¬R)∧(¬P∨¬Q∨R) ∧(¬P∨¬Q∨¬R )∧(P∨¬Q∨R)∧(¬P∨¬Q∨ R)
极小项
西安电子科技大学 软件学院
例如，以下是含有三个命题变元P,Q,R的极小项：
P1 ∧ ¬P2 ∧ P3
该极小项的编号为： 1 记为： 0 1
m5
含n个命题变元的极小项共有2n个， 编号为0~2n-1。
§1.4.1 主析取范式
000 001 010 011 100 101 110 111 m0 = m1 = m2 = m3 = m4 = m5 = m6 = m7 =
§1.4.2 主合取范式
极大项
西安电子科技大学 软件学院
例如，以下是含有三个命题变元P,Q,R的极大项：
P ∨ ¬Q ∨ R
该极大项的编号为： 0 记为： 1 0
M2
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
24
六、等值演算
例:证明 (P∨Q)→R ⇔(P→R)∧(Q→R) 证明 证： 可以从左边开始演算，也可以从右边 开始演算。现在从左边开始演算。 (P∨Q)→R ⇔┐(P∨Q)∨R (蕴含等值式） ⇔(┐P∧┐Q)∨R （德摩根律） ⇔(┐P∨R)∧(┐Q∨R)（分配律） ⇔(P→R)∧(Q→R) （蕴含等值式） 练习：从右边开始演算？
18
六、等值演算
1. 双重否律(对合律） P ⇔ ┐┐P 2. 幂等律 P∨P ⇔P P∧P⇔ P 3. 结合律 (P∨Q)∨R ⇔P∨(Q∨R) (P∧Q)∧R ⇔P∧(Q∧R) 4. 交换律 P∨Q ⇔ Q∨P P∧Q ⇔ Q∧P
19
六、等值演算
5.分配律 P∨(Q∧R) ⇔(P∨Q)∧(P∨R) （∨对∧的分配律） 的分配律） P∧(Q∨R) ⇔(P∧Q)∨(P∧R) （∧对∨的分配律） 的分配律） 6.吸收律 P∨(P∧Q) ⇔ P P∧(P∨Q) ⇔ P 7.德.摩根律 ┐(P∨Q) ⇔ ┐P∧┐Q ┐(P∧Q) ⇔ ┐P∨┐Q 8. 同一律 A∨0 ⇔ A A∧1 ⇔ A 20
二、命题公式分量指派
公式就代表命题，但代表的命题是真还是假呢？ 在命题公式中，由于有命题符号的出现，因而 真值是不确定的。当将公式中出现的全部命题符 号都解释成具体的命题之后，公式就成了真值确 定的命题了。 例如，在公式(P∨Q)→R中: (P Q) R 若将P解释成：2是素数， Q解释成：3是偶数， R解释成：是无理数，则P与R被解释成真命 题，Q被解释成假命题了，此时公式(P∨Q)→R被 解释成：若2是素数或3是偶数，则 是无理数。 这是一个真命题。
六、等值演算
9.零律 P∨1 ⇔ 1 P∧0 ⇔ 0 10.否定律 P∨┐P ⇔ 1 （排中律） P∧┐P ⇔ 0 （矛盾律） 11.蕴涵等值式（补充） P→Q⇔┐P∨Q 12. 等价等值式（补充） (P ↔ Q) ⇔(P→Q)∧(Q→P)
21
六、等值演算
13.假言易位 （补充） P→Q ⇔ ┐Q→┐P 14.等价否定等值式（补充） P ↔ Q ⇔ ┐P ↔ ┐Q 15.归谬论（补充） (P→Q)∧(P→┐Q) ⇔ ┐P
28
22
六、等值演算
在最基本的15组命题公式的等价关系的基础上， 利用等价置换就可以推证一些更为复杂的命题等 价公式。 例：命题公式(P→Q)→R中 ，可用┐P∨Q置换其中 的P→Q，由蕴涵等值式可知， P→Q P Q ⇔ ┐P∨Q， P Q 所以有 (P→Q)→R ⇔ (┐P∨Q) → R 在这里，使用了等价置换规则。如果再一次地用 蕴涵等值式及等价置换规则，又会得到 (┐P∨Q)→R ⇔ ┐(┐P∨Q)∨R
5
二、命题公式分量指派
不难看出，含n(n≥1)个命题变元的公式共 有2n个不同的指派（赋值）。 下面的问题是，指定P，Q，R的真值为何值 时，(P∨Q)→R的真值为1；指定P，Q，R的 真值为何值时，(P∨Q)→R的真值为0。 为看清命题公式在各种指派下的取值情况， 通常构造下面的“真值表”。
6
三、真值表
4
二、命题公式分量指派
2．若A中出现的命题符号为P，Q，R...,给定A的指 派（赋值）α1,α2,…,αn是指P＝α1，Q＝α2,…， 最后一个字母赋值αn。 上述αi取值为0或1，i＝1,2,…,n。 例如，在公式(┐P1∧┐P2∧┐P3)∨(P1∧P2)中
000(P1＝0，P2＝0，P3＝0)， 110(P1＝1，P2＝1，P3＝0)都是成真赋值 而001(P1＝0，P2＝0，P3＝1) 011(P1＝0，P2＝1，P3＝1)都是成假赋值。 在(P∧┐Q)→R中，011(P＝0，Q＝1，R＝1)为成真赋 值，100(P＝1，Q＝0，R＝0)为成假赋值。
第一章 命题逻辑
1-4 真值表与等价公式
1
一、公式的层次
公式的层次（补充）定义： 公式的层次 (1)若公式A是单个的命题变元，则称A为0层公式 0层公式。 (2)称A是n+1(n≥0)层公式是指下面情况之一： (a)A＝┐B，B是n层公式； (b)A＝B∧C，其中B，C分别为i层和j层公式，且n＝ max(i，j)； (c)A＝B∨C，其中B，C的层次及n同(b)； (d)A＝B→C，其中B，C的层次及n同(b)； (e)A＝B↔C，其中B，C的层次及n同(b)； (3)若公式A的层次为k，则称A是k层公式 k层公式。 易知， (┐P∧Q)→R，(┐(P→┐Q))∧((R∨S)↔┐P)分 别为3层和4层公式。 2
如表1所示。
(┐P∧Q)→┐R P∧Q)→┐R的真值表 表1 (┐P∧Q)→┐R的真值表
从表1可知，公式(1)的成假赋值为011，其余7个赋值都是 成真赋值。
9
三、真值表
公式(2)是含2个命题变项的3层合式公式，它的真值表如表2 所示。
表2 (P∧┐P)↔(Q∧┐Q)的真值表 (P∧┐P) (Q∧┐Q)的真值表
23
六、等值演算
如果再用德摩根律及置换规则，又会得到 ┐(┐P∨Q)∨R ⇔(P∧┐Q)∨R 再用分配律及置换规则，又会得到 (P∧┐Q)∨R ⇔(P∨R)∧(┐Q∨R) 将以上过程连在一起，可得到 (P→Q)→R ⇔(┐P∨Q) → R ⇔ ┐(┐P∨Q)∨R ⇔(P∧┐Q)∨R ⇔(P∨R)∧(┐Q∨R) 上述演算中得到的5个公式彼此之间都是等值的 个公式彼此之间都是等值的， *上述演算中得到的 个公式彼此之间都是等值的， 在演算的每一步都用到了等价置换规则 在演算的每一步都用到了等价置换规则 上述用等值式及等价置换规则进行推演的过程称 等值演算，这是数理逻辑的主要内容。 为等值演算，这是数理逻辑的主要内容。 数理逻辑的主要内容
11
三、真值表
注意：表1～表3都是按构造真值表的步骤一步一 步地构造出来的，这样构造真值表不易出错。如 果构造的思路比较清楚，有些层次可以省略。 有一类公式，不论其命题变元做何种指派，其真 值永为真（假），就把这类公式记为T（F）。 关于n个命题变元P1,P2,…,Pn,可以构造多少个真 值表呢? n个命题变元共产生2n个不同指派,在每个指派下,公 式的值只有0和1两个值。于是n个命题变元的真值 表共有 种不同情况。
从表2可以看出，该公式的4个赋值全是成真赋值，即无成 假赋值。
10
三、真值表
公式(3)是含3个命题变项的4层合式公式。它的真值表如表3 所示。
表3 ┐(P→Q)∧Q∧R的真值表 ┐(P→Q)∧Q∧R的真值表 P→Q)∧Q∧R
它的真值表如表3所示。不难看出，该公式的8个赋值全是 成假赋值，它无成真赋值。
17
六、等值演算
虽然用真值法可以判断任何两个命题公式 是否等值，但当命题变元较多时，工作量 是很大的。可以先用真值表验证一组基本 的又是重要的等价公式，以它们为基础进 行公式之间的演算，来判断公式之间的是 否等值。下面给出15组（共24个）重要的 等值式，希望同学们牢牢记住它们。在下 面公式中出现的P,Q,R仍然是元语言符号， 它们代表任意的命题公式。P15 表1-4.8
15
五、公式置换
在一命题公式中，如果用公式置换命题的 某个部分，一般地会产生某种新的公式， 例如Q→（P∨（P∧Q））中以（ ┐P →Q）取 代（P∧Q），则Q→（P∨ （ ┐P →Q））就与 原式不同。为了保证取代后的公式与原式 等价（即真值相同），需要对置换作出一 些规定。
16
五、公式置换
定义 1-4.3 如果X是合式公式A的一部分， 且X本身也是一个合式公式，则称X为公式A 的子公式。 定理 1-4.1 设X是合式公式A的子公式，若 X ⇔Y，如果将A中的X用Y来置换，所得到 公式B与公式A等价，即A ⇔B。 证明 书P16 *满足定理1-4.1条件的置换称为等价置换（等 价代换）
3
二、命题公式分量指派
若P，Q的解释不变，R被解释为：是有理数，则 (P∨Q)→R被解释成：若2是素数或3是偶数，则 是有理数。这是个假命题。 其实，将命题符号P解释成真命题，相当于指定P 的真值为1，解释成假命题，相当于指定P的真值 为0。 在本课中，对含n个命题变项的公式A的指派（赋 值）情况做如下规定： 1．若A中出现的命题符号为P1,P2,…,Pn，给定A的 指派（赋值）α1,α2,…,αn 是指P1＝α1，P2＝ α2,…，Pn＝αn。
26
本节小结
公式层次 命题公式分量指派 真值表 公式等价 公式置换 等值演算
27
课后作业
复习课本例题 P18 （7）a)、c)、e)、f)、h) (使用等值 演算方法证明） 补充:（使用等值演算方法或真值表证明） (1) ┐(P ∨ Q ) ∨ (┐ P ∧Q) ⇔ ┐P (2) (P∧Q) →R⇔(P→R)∨(Q →R) (3) P→(Q→R)⇔(P∧┐R) → ┐Q
12
四、公式等价
根据真值表，有些命题公式在分量的不同 指派下，其对应的真值与另一命题公式对 应的真值完全相同，如表（P14 1-4.5)：
P 0 0 1 1 Q 0 1 0 1 P→Q 1 1 0 1
P 0 0 1 1 Q 0 1 0 1 ┐P 1 1 0 0 ┐P∨ Q 1 1 0 1
P→Q
┐P∨Q
定义1-4.1 在命题公式中，对于各分量指派真值的 各种可能组合，就确定了这个命题公式的各种真 种情况，把它汇列成表，就是命题公式的真值表 命题公式的真值表。 命题公式的真值表 真值表的构造步骤： (1) 找出公式中所含的全体命题变项P1,P2,…,Pn (若 无下角标就按字典顺序排列)，列出2n个赋值。本 课规定，赋值从00…0开始，然后按二进制加法 依次写出各赋值，直到11…1为止。
25
六、等值演算
证明： 例2.4 证明：(P→Q)→R P→(Q→R) 证 方法一 方法一：真值表法，可自己证明。 方法二 ：设A=(P→Q)→R,B=P→(Q→R)
先将A,B通过等值演算化成容易观察真值的情况，再进行判断。