当前位置：文档之家 › 1.3命题公式及翻译

1.3命题公式及翻译

  • 格式：ppt
  • 大小：104.50 KB
  • 文档页数：20

下载文档原格式

  / 20

合集下载

命题公式真值表

命题公式真值表

说明:
(1)命题变元是没有真假值的,只有当命题变元用 确定的命题代入时,才得到一个命题,命题的真值 依赖于代换变元的那些命题的真值;
1-3 命题公式与翻译
(2) 不是所有由命题变元 ,常元 ,联结词和括号组成的字符串 都能成为命题公式.例如, P , P (Q ) 等不是命题公式.
定义 1-3.1 命题演算的合式公式,规定为: (1)单个命题变元本身是一个合式公式; (2)如果 A 是合式公式,那么 A 是合式公式; (3)如果 A 和 B 是合式公式,那么
1-3 命题公式与翻译
2、命题的翻译
练习 将下列命题符号化: (1)她既聪明又用功. (2)他虽聪明但不用功. (3)虽然这次语文考试的题目很难,但是王丽还是取得了好成绩. (4)张三或李四都可以做这件事. (5)一公安人员审查一起案件,事实如下,请将案件事实符 号化: 张三或李四盗窃了机房的一台电脑,若是张三所为,则作案 时间不能发生在午夜前;若李四的证词正确,则午夜时机房 的灯未灭; 若李四证词不正确,则作案时间发在午夜前; 午夜时机房的灯全灭了.
分配律
P (Q R) ( P Q) ( P R)
吸收律
P ( P Q) P , P ( P Q) P
1-4 真值表与等价公式
4.基本等价公式
德·摩根律 同一律 零律 否定律 (互补律) 条件式转化律 双条件转化律
( P Q) P Q , ( P Q) P Q
1-3 命题公式与翻译
1、命题公式(合式公式)
定义 1 由命题变元、常元、联结词、括号以规定的格式联结 起来的字符串称为命题公式,也称合式公式.命题公式中的命 题变元称为命题公式的分量.
例如,若 P 和 Q 是命题变元, 则下面式子均是命题公式

(2)命题公式与翻译1-3

(2)命题公式与翻译1-3

二、联接词的优先集
例1 令 P：北京比天津人口多。 Q：2+2＝4。 R：乌鸦是白色的。 求下列复合命题的真值： (1) ┐P∧Q∨P∧┐Q→R (2) Q∨R→(P→┐R) (3) (┐P∨R)
↔(P∧┐R)
解 P，Q，R的真值分别为1，1，0，容易算出(1)， (2)，(3)的真值分别为1，1，0。
三、命题的符号形式
例3 他既聪明又用功。 解：P：他聪明。Q：他用功。 本题命题符号化为：P∧Q 例4 他虽聪明但不用功。
（P∧┐Q）
例5 除非你努力，否则你将失败。
（┐P→Q）
例6 张三或李四都可以做这件事。
（P∧Q）
本节小结
命题公式的定义 联接词的优先集 命题的符号形式
课后作业
P12 （5）
一、命题公式的定义
例：
(P→Q)∧(Q ↔ R)，(P∧Q)∧┐R， P∧(Q∧┐பைடு நூலகம்)等都是合式公式， 而P Q→R，（P→(R→Q)等不是合式公式。
注意： 注意：定义1-3.1给出的合式公式的定义方 式称为归纳定义方式，以后还将多次出现这 种定义方式。
二、联接词的优先集
联结词可以嵌套使用 。在嵌套使用时， 为 了减少圆括号的数量，约定最外层括号可以 省略。 规定如下优先顺序： ( )，┐，∧，∨，→， ↔ ， 对于同一优先级的联结词，先出现者先运算。 则P∧Q→R也是合式公式。
一、命题公式的定义
至少包含一个联接词的命题称作复合命题 复合命题。 复合命题 例如：P，Q为任意两个命题，则┐P， P ∧Q，（P ∨Q）∨（ P → Q）， Q ↔（Q ∨ ┐P）等都是复合命题。 注：命题公式无真假值，仅当公式中各命题变 元进行了指派（赋值）时，才得到一个命题。

离散数学第一章

离散数学第一章

离散数学第一章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.3命题公式及翻译解析

例：
三、翻译
只有你通过了英语六级考试而且不是英语专业的学生，才可以 选修这门课。
我们可以用命题公式表示复合命题，常将这个过程称为 命题的符号化，或称为命题的翻译。命题的翻译可按如下 步骤进行：
①找出复合命题中的简单命题。 ②用英文字母表示这些简单命题。 ③使用命题联结词将这些英文字母连接起来。
例 试翻译下列命题。 (1)这个材料无趣,习题也不难,而且这门课程也不使人喜欢。 (2)如果这个材料无趣,或者习题难,
• 上节介绍了将命题表示为符号串。 • 是否每个符号串都是命题呢？
pq→ • 什么样的符号串才是命题呢？ • 如下定义的符号串才是命题。
下面给出命题公式的递归定义。
(1) 单个命题变元是合式公式，并称为原子命题公式。 (2) 若A是合式公式，则(┐A)也是合式公式。 (3) 若A，B是合式公式，
则(A∧B)，(A∨B)，(A→B)，(AB)也是合式公式。 (4) 只有有限次地应用(1)～(3)形式的符号串才是合式公式。
• 公式（2）、（3）略。
公式的层次
• 定义： （1）若公式A是单个的命题变项，则称A为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分别是i层、j层公式，且n=max(i,j); （d）A是B → C，其中B，C分别是i层、j层公式，且n=max(i,j); （e）A是B ↔ C，其中B，C分别是i层、j层公式，且n=max(i,j); （3）若公式的层次为k，则称A是k层公式。
§1.3 命题公式与翻译
一、命题公式的定义

离散数学串讲

离散数学串讲

第一章命题逻辑1.1 命题及其表示方法1.2 联结词1.3 命题公式与翻译1.4 真值表与等价公式1.5 重言式与蕴含式1.6 其它联结词1.7 对偶与范式1.8 推理理论1.1 命题及其表示方法命题：具有确定真值的陈述句命题的类型（原子命题和复合命题）命题语句的形式（陈述句）命题的表示（一个命题标识符（比如P）表示确定的命题）1.2 联结词1. 否定⌝2.合取∧（TT T）3. 析取∨（FF F）4. 条件→(TF F)5. 双条件↔(同T异F)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)→R1.5 重言式与蕴含式●定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为真，则称该命题公式为重言式或永真公式。

离散数学1.2-1.3公式分类及等价演算

离散数学1.2-1.3公式分类及等价演算
第一课时复习
1、将下列命题符号化： （1）涵涵边读书边听音乐。
P:涵涵读书, Q:涵涵听音乐。
原命题符号化为 P ∧ Q
（2）小凡要么住在1104室，要么住在1105室。
P：小凡住在1104室，Q：小凡住在1105室。
原命题符号化为（ P∧﹁ Q）∨ （﹁ P∧ Q）
（3）现在没下雨，可也没出太阳，是阴天。 P：现在下雨，Q：现在出太阳了，R:现在是阴天。
2）代入规则：若原公式为永真式，则它的代入实例也为永真式。
13
例如： P(PQ)Q为永真式
则用R来取代P得到的公式（即代入实例）
也为永真式。
R(RQ)Q
或用公式RSP来取代Q得到的公式(即代入实例)
R(R (RSP)) (RSP) 也为永真式。
14
对非重言式通常不作代入运算, 特别是偶然, 因所 得代入实例的性质不确定, 没有用处。例如:
5
一、公式的类型
（1）永真式(重言式)：无论命题变元的取值如何，公式 A(P1,P2,...,Pn)的值均为真。 （2）永假式(矛盾式，不可满足的)：无论命题变元的取值 如何，公式A(P1,P2,...,Pn)的值均为假。 （3）可满足式：公式A(P1,P2,...,Pn)至少存在一个成真指 派。
如： P(QR)(PQ)(PR) P(QR)(PQ)(PR)
设AB，且A、B为命题变元P1,P2,P3…Pn和联结词,,构
成的公式，A*与B*分别为A、B的对偶公式，则B*A*。
如： PQP
PPQ
25
E13： R(PP)R E14： R(PP)T E15： R(PP)F
E4： (PQ)RP(QR) (结合律)
E5： (PQ)RP(QR)

离散数学知识点整理

离散数学知识点整理

离散数学一.逻辑和证明1.1命题逻辑命题：是一个可以判断真假的陈述句。

联接词：A. V. -、f -o记住“p仅当q”意思是“如果p,则q” ,即系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。

1. 3命题等价式逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。

证逻辑等价是通过推导出证永真式是通过推导岀。

1・4量词谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如Vx>OP(x)o当论域中的元素可以一一列举，那么VxP(x)就等价于P(xl)AP(x2)... A P (xn) o 同理，3 xP (x)就等价于P(xl) \/P(x2)・•. VP(xn) o两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如V x (P(x) AQ(x))和(V xP(x)) A (W xQ(x))。

量词表达式的否定：「V xP (x) o 3 x「P(x), T xP (x) o V X^P (x) O 1.5量词嵌套我们釆用循环的思考方法。

量词顺序的不同会影响结果。

语句到嵌套量词语句的翻译，注意论域。

嵌套量词的否定就是连续使用徳摩根定律，将否定词移入所有量词里。

1・6推理规则一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。

但有效论证不代表结二.集合、函数、序列、与矩阵2 ］集合W说的是元素与集合的关系，匚说的是集合与集合的关系。

常见数集有N=｛0,l,2, 3...｝, Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集, C复数集。

A和B相等当仅当V X(X WA F EB)； A是B的子集当仅当V x(xGA-xGB)； A 是B 的真子集当仅当V x(xWAf xWB) AB X(X^AA X^B)。

第1章 命题逻辑(二)

第1章 命题逻辑(二)

p，q的极小项为：p∧q，p∧¬ q，¬ p∧q，p∧¬ q
两个命题变元的极小项共4(=22)个, 三个命题变元的极小项 共8(=23)个, …。一般地说，n个命题变元共有2n个极小项。
1.5.2 主析取范式
极小项有下列的性质： ⑴每个极小项只有一个成真赋值，且各极小项的成真赋值 互不相同。极小项和它的成真赋值构成了一一对应的关系。
1.5.2 主析取范式
真值表法：即用真值表求主析取范式。 用真值表求主析取范式的步骤如下： ① 构造命题公式的真值表。
② 找出公式的成真赋值对应的极小项。
③ 这些极小项的析取就是此公式的主析取范式。
1.5.2 主析取范式
【例1.24】用真值表法，求(p→q)→r的主析取范式。 解：表1.15是(p→q)→r的真值表 p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1 表1.15 p→q 1 1 1 1 0 0 1 1 (p→q)→r 0 1 0 1 1 1 0 1
1.5.2 主析取范式
矛盾式无成真赋值，因而主析取范式不含任何极小项， 将矛盾式的主析取范式记为0。 重言式无成假赋值，因而主析取范式含2n (n为公式中命题
变元的个数)个极小项。
可满足式，它的主析取范式中极小项的个数一定小于等于 2n。
1.5.3主合取范式
定义1.5.7 在基本和中，每个变元及其否定不同时存在， 但两者之一必须出现且仅出现一次，这样的基本和叫作布 尔析取，也叫大项或极大项。 两个变元p，q构成的极大项为： p∨q，p∨¬q，¬p∨q，¬p∨¬q 三个命题变元p，q，r构成的极大项为： p∨q∨r， p∨q∨¬r， p∨¬q∨r， p∨¬q∨¬r， ¬p∨q∨r，¬p∨q∨¬r，¬p∨¬q∨r，¬p∨¬q∨¬r 两个命题变元的极大项共4(=22)个, 三个命题变元的极大 项共8(=23)个, …。一般地说，n个变元共有2n个极大项。

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都是素数，这是不对的。 解 若设
④ 需要的括号不能省略，而可以省略的括号， 在需要提高公式可读性时亦可不省略。

命题公式真值表

命题公式真值表

(4) (P Q) (P Q);
(5) (P Q) (P Q).
A
6
1-4 真值表与等价公式
解 (1) P Q 的真值表为:
P
Q
T
T
T
F
F
T
F
F
P Q
T F T T
(2) P Q 的真值表为:
P
Q
PQ
T
T
T
T
F
F
F
T
T
F
F
T
A
7
1-4 真值表与等价公式
(3) (P Q) P 的真值表为:
(1)单个命题变元本身是一个合式公式;
(2)如果 A 是合式公式,那么 A是合式公式;
(3)如果 A 和 B 是合式公式,那么
A B , A B , A B, A B 是合式公式;
(4)当且仅当能够有限次地应用(1)、(2)、(3)
所得到的包含命题变元,联结词和括号的字符串
是合式公式.
A
3
1-3 命题公式与翻译
A 中的 X 用Y 置换,所得公式 B 与公式 A 等价,即 A B .
例 4 证明: Q (P (P Q)) Q P
例 5 证明下列等价式
(1) (P Q) (P Q) P ;
(2) P (Q R) Q (P R) .
练习 证明 P (Q R) (P Q) R
A
14
1-4 真值表与等价公式
例 6 化简下列命题公式: (1) P (P (Q P)) (2) (P Q) (Q P)
说明:
(1)命题变元是没有真假值的,只有当命题变元用 确定的命题代入时,才得到一个命题,命题的真值 依赖于代换变元的那些命题的真值;

离散数学(1.3命题公式与翻译)

离散数学(1.3命题公式与翻译)
5
第一章 命题逻辑（Propositional Logic）1.3
命题公式与翻译
• • • •
例3： 1) 我今天进城，除非下雨。[1-3.(7)] 2) 仅当你走我将留下。 3) 假如上午不下雨，我去看电影，否 则就在家里读书或看报。 • 4)除非你努力，否则你将失败。[P11 例5]
6
第一章 命题逻辑（Propositional Logic）1.3
命题公式与翻译
• 例4：P10 例题1 • 小结：本节介了命题公式的概念及复合 命题的符号化.重点是理解命题公式的递 归定义,掌握复合命题的符号化方法. • 作业: P12 (1),(5)
7
2
第一章 命题逻辑（Propositional Logic）1.3
命题公式与翻译
定义1.3.2：(1)原子公式是合式公式(wff)。 （2）若A是合式公式，则( A)也是合式公式。 （ 3 ）若 A ， B 是合式公式，则 (A∧B) ， (A∨B) ， (AB)，(AB)也是合式公式。 （4）当且仅当有限次地应用(1)~(3)所得到的包含原 子公式、联结词和括号的符号串是合式公式。 注: (1)合式公式也称为命题公式，并简称为公式。 (2) 命题公式一般不是命题 , 仅当公式中的命题变 元用确定的命题代入时,才得到一个命题.其真值依 赖于代换变元的那些命题的真值.
3
第一章 命题逻辑（Propositional Logic）1.3
命题公式与翻译
例1：指出(P→(PQ))是否是命题公式(wff)，
如果是，则具体说明。
解： ① P是wff ② Q是wff ③ PQ是wff ④ (P→(PQ)) 例2: (P Q) , (R ∧ S) 由(1) 由(1) 由(3) ①② 由(3) ①③

合式公式真值表等价置换定理 第二课

合式公式真值表等价置换定理 第二课

1 ∧ 2 ∧ 3 ⇔T 变换为（ ∧…… ∧ ） ∨ （ ∧…… ∧ ） 的形式 排除（ ∧…… ∧ ） 中Pi ∧ Pj的可能即可。A2, C1, D ¬ (( P → Q ) ∧ P ) ⇔ T
Q ∨ ¬ (( P → Q ) ∧ P ) ⇔ Q ∨ ¬ (( ¬ P ∨ Q ) ∧ P ) ⇔ Q ∨ ¬ (( ¬ P ∧ P ) ∨ ( Q ∧ P )) ⇔ Q ∨ ¬ (Q ∧ P ) ⇔ Q ∨ (¬ Q ∨ ¬ P ) ⇔
2、等价定理与常用等价式 、 定理： 和 是两个命题公式 是两个命题公式， 当且仅当A 定理：A和B是两个命题公式，A ⇔ B当且仅当 当且仅当 证明： 证明 （1）由A ⇔ B 知，在所有可能的真值指派下，A、B的真值总是 相同的，从而，A ↔ B是一个重言式。 （2）由A ↔ B为重言式， 可知：在所有可能的真值指派下，A、 B的真值总是相同的，所以A ⇔ B。 注意：“当且仅当” 注意： 当且仅当” 的证明需要分为 仅当” “当”和“仅当” 两个部分 B是一个重言式。 是一个重言式。 是一个重言式
对应于所有可能的真值指派， 、 的真值都相同 的真值都相同。 对应于所有可能的真值指派，A、B的真值都相同。又称 为两命题公式逻辑相等。记为： 为两命题公式逻辑相等。记为：A ⇔ B 思考： （（P →Q） （ P ∨ Q））在真值表中值有何特征? 思考 （ ） ）
例2 ：永真式和永假式 P T T F F 定义3 定义 Q T F T F ¬P∨P ∨ T T T T
2. 命题演算的合式公式 • 基础 （1）. 单个命题变元本身是个合式公式；
约定(1)最外层的括号可以省去 • 归纳 约定 如果A是一个合式公式，那么 A也是一个合式公 （2）. 最外层的括号可以省去 式； (2)运算符优先次序： ， ∧， ∨， →， 运算符优先次序： 运算符优先次序

离散数学第一章 命题逻辑

离散数学第一章 命题逻辑
4/5/2014 8:53 PM chapter1 10
1.2 联结词
2、合取 ∧
Proposition Logic 命题逻辑
P∧Q是P和Q的合取, 读做“P与Q”或“P并且Q”。
P 0 0 1 1 Q 0 1 0 1 P ∧Q 0 0 0 1
如： P: 王华的成绩很好。
Q: 王华的品德很好。 P∧Q: 王华的成绩很好并且品德很好。
对，成立，则真值为真，T，1
错，不成立，则真值为假，F，0
断言是一陈述语句。一个命题是一个或真或假而不能 两者都是的断言。如果命题是真, 我们说它的真值为真； 如果命题是假，我们说它的真值是假。
4/5/2014 8:53 PM chapter1 2
1.1 命题及其表示法
【例1 】判定下列各语句是否为命题： （是） (a) 巴黎在法国。 （是） （是） (c) 3+2=5 (d) 别的星球上有生物。 （是） (b) 煤是白色的。 (e) 全体立正。 (f) 明天是否开大会？
从真值表可知P∨Q为真, 当且仅当P或Q至少有一为真。
4/5/2014 8:53 PM chapter1 12
1.2 联结词
Proposition Logic 命题逻辑
“或”字常见的含义有两种: 一种是“可兼或”, 如上
例中的或, 它不排除小王既喜欢唱歌又喜欢跳舞这种情况。
一种是“排斥或”（异或）, 例如“人固有一死, 或重于泰 山, 或轻于鸿毛”中的“或”, 它表示非此即彼, 不可兼得。 运算符∨表示可兼或, 排斥或以后用另一符号表达。 如：(1)小李明天出差去上海或去广州。
所以,“如果P则Q”, “只要P则Q”,只有Q才P”, “仅当Q 则P”都可符号化为P→Q 的形式。

离散数学

离散数学

第一章命题逻辑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.3-1.4 命题逻辑

1.3-1.4 命题逻辑

同理
p ∧ r ⇔ p ∧ 1 ∧ r ⇔ p ∧ (¬ q ∨ q ) ∧ r ⇔ ( p ∧ ¬q ∧ r) ∨ ( p ∧ q ∧ r)
q ∧ r ⇔ 1 ∧ q ∧ r ⇔ (¬ p ∨ p ) ∧ q ∧ r ⇔ (¬ p ∧ q ∧ r ) ∨ ( p ∧ q ∧ r )
例子的主析取范式
逻辑联接词组是极小功能完备的： 是功能完备的并且不能少一个。
例1：否定、析取、合取组成的逻辑联结词组 ：否定、析取、 是功能完备的，但不是极小功能完备的。 极小功能完备的 是功能完备的，但不是极小功能完备的。
例2：否定和合取组成的逻辑联结词组是极 ：否定和合取组成的逻辑联结词组是极 小功能完备的。 小功能完备的。 例3：否定和析取组成的逻辑联结词组是极 ：否定和析取组成的逻辑联结词组是极 小功能完备的。 小功能完备的。
主析取范式用途
1、构造真值表 2、判断两个公式是否等值（例1.19） 3 3、判断公式类型（例1.20） 1.20 4、解决实际问题（例1.21）
例1.21
某科研所有3名青年高级工程师A，B， C。所里要选派他们中的1到2人出国进 修，由于所里工作需要选派时必须满足 以下条件： （1）若A去，则C也可以去； （2）若B去，则C不能去； （3）若C不去，则A或B可以去。 问所里该如何选派他们？
令p:派A去，q:派B去，r:派C去。则根据 条件，得命题公式为
( p → r) ∧ (q → ¬r) ∧ (¬r → ( p ∨ q))
( p → r ) ∧ ( q → ¬ r ) ∧ ( ¬ r → ( p ∨ q )) ⇔ (¬ p ∨ r ) ∧ (¬ q ∨ ¬ r ) ∧ (r ∨ p ∨ q ) ⇔ m1 ∨ m 2 ∨ m 5 ⇔

1.3特称命题全称命题

1.3特称命题全称命题
【提示】 意义相反，即命题②是命题①的否定，同时， 命题①也是对命题②的否定． 特称命题
全称命题的否定是 .
，特称命题的否定
是
全称命题
一般地，对于一个含有一个量词的全称命题的否定有下面的结论 x, p ,))p( x) 的否定 p 全称命题 ： ： x p p ( x p x M p ( x 全称命题 ： 的否定
使p(x0)成立”
“存在M中的一个x0，使p(x0)成立”，可简记为
全称命题与特称命题的否定
下面有两个命题： ①对任意 x∈R，都有 2x＞0； ②存在 x0∈R，使 2 ≤0. (1)从形式上看，这两个命题有什么不同？
x0
思
【提示】
①是全称命题，判断词是“＞”；
②是特称命题，判断词是“≤”．
(2)从意义上看这两个命题有什么不同？
命题 全称命题 特称命题
（1）所有的 x A，使 p ( x) 成立； （1）存在 x A ，使p ( x) 成立；
表 述 方 法
（2）对一切 x A，使 p ( x) 成立； （2）至少有一个 x A ，使 p ( x) 成 （3）对每一个 x A ，使 p ( x) 成 立； （4）任意一个 x A ，使 p ( x) 成 立； （5）若 x A，则 p ( x) 成立； 立； （3）对有些 x A ，使 p ( x) 成立；
1.3 特称命题与全称命题
【问题导入】
下面有两个命题： ①本节课高二(016)班的每一位学生都没有打瞌睡； ②本节课高二(016)班存在一位学生在打瞌睡． (1)这两个命题的含义相同吗？
【提示】 不同． (2)造成含义不同的原因是什么？ 【提示】 这两个命题使用了不同的量词．命题①使用

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

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

定义1-3.1 命题演算的合式公式(wff)，规定为：
(1)单个命题变元（常元）本身是一个合式公式。
(2)如果A是合式公式，那么┐A是合式公式。
(3)如果A和B是合式公式，那么(A∧B)，(A∨B)， (A→B）和(A B)都是合式公式。 (4)当且仅当能够有限次地应用(1)、(2)、(3)所得到 的包含命题变元，联结词和括号的符号串是合式公 式。
P17(1) (C) (P ∨Q) P T T F F Q T F T F P ∨Q T T T F Q ∨P T T T F
(Q ∨P)
(P ∨Q) (Q ∨P)
T T T T
P17(1) (e) (P →(Q→R) )→((P→Q) →(P→R)) 设S (P →(Q→R) )→((P→Q) →(P→R))
离散数学
Discrete Mathematics
课程回顾
命题：命题的定义、真值、分类及其表示。 命题联结词： 否定、合取、析取、条件、双条件。
P Q ┐P P∧Q P∨Q P→Q P Q
T T
T F F T
F
F T
T
F F
T
T T
T
F T
T
F F
F F
T
F
F
T
T
第一章 命题逻辑第2讲
1—3 命题公式与翻译 1—4 真值表与等价公式 要求：理解合式公式及两个合式公式等价 的定义，熟悉真值表与命题定律，会证明 等价公式。 重点：合式公式的定义，两个合式公式等价 的定义，命题定律。 难点：推证等价公式。
例题4
给出┐(P∧Q） （┐P∨┐Q）的真值表。
解
P Q ┐P T T T F F T F F F F T T ┐Q F T F T P∧Q T F F F ┐(P∧Q) ┐P∨┐Q F T T T F T T T ┐(P∧Q） T T T T ┐P∨┐Q）

1-34 真值表与等价公式

1-34 真值表与等价公式

1-3.1 命题公式
注：这是一个递归方式的定义（递归定义） 这是一个递归方式的定义（递归定义） （1）是递归定义的基础 ） ）、（3） （2）、（ ）是归纳 ）、（ （4）是递归的界限 ） 例： →(P∨Q)就不是合式公式 ∨ 就不是合式公式 联结词的运算次序： 联结词的运算次序： (1) 使用括号 (2) 规定运算符运算优先次序：¬, ∧, ∨, →, 规定运算符运算优先次序：
1-3.2 翻译
除非你努力，否则你将失败。 例1. 除非你努力，否则你将失败。 解：设P：你努力。 ：你努力。 Q：你将失败。 ：你将失败。 原命题可以符号化为： 原命题可以符号化为： ¬ P → Q 除非(仅当 我有时间，我才去看电影。 仅当)我有时间 例2. 除非 仅当 我有时间，我才去看电影。 解：设P：我有时间。 ：我有时间。 Q：我去看电影。 ：我去看电影。 原命题可以符号化为： 原命题可以符号化为： ¬ P → ¬ Q 或化为： → 或化为：Q→P
如果你和他都不固执己见的话， 例3. 如果你和他都不固执己见的话，那么不愉快 的事也不会发生了。 的事也不会发生了。 解：设P：你固执己见。 ：你固执己见。 Q：他固执己见。 ：他固执己见。 R：不愉快的事也不会发生了 ： 原命题可以符号化为：（ ∧¬ ：（¬ ∧¬Q） 原命题可以符号化为：（¬P∧¬ ）→R 如果你和他不都是固执己见的话， 例4. 如果你和他不都是固执己见的话，那么不愉 快的事也不会发生了。 快的事也不会发生了。 解：设P：你固执己见。 ：你固执己见。 Q：他固执己见。 ：他固执己见。 R：不愉快的事也不会发生了 ： 原命题可以符号化为： 原命题可以符号化为： ¬（P∧Q）→R ∧ ）
1-3命题公式与翻译 命题公式与翻译
1-3.1 命题公式
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
(2)如果这个材料无趣,或者习题难, 那么这门课程就不使人喜欢。 (3)这个材料有趣,意味着习题难,反之亦然。 (4)或者这个材料有趣, 或者习题难,二者恰具其一。
解：设 P表示”这个材料有趣”, Q表示”这些习题难”, R表示”这门课使人喜欢”,
例 设A=明天上午七点下雨, B=明天上午七点刮风,C=我去学校, 试用A，B，C表示下列复合命题： (1)如果明天上午七点不刮风下雨，则我去学校； (2)如果明天上午七点不下雨并且也不刮风，则我去学校； (3)如果明天上午七点下雨或不刮风，则我去学校； (4)明天我风雨无阻，一定去学校； (5)只有当明天上午七点不下雨并且也不刮风时，我才去学校； (6)只有当明天上午七点下雨或刮风都不发生时，我才去学校．
公式的层次
• 定义： （1）若公式A是单个的命题变项，则称A为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分别是i层、j层公式，且n=max(i,j); （d）A是B → C，其中B，C分别是i层、j层公式，且n=max(i,j); （e）A是B ↔ C，其中B，C分别是i层、j层公式，且n=max(i,j); （3）若公式的层次为k，则称A是k层公式。
例
• • • • p，q是0层公式。 ¬p ∧ q是2层公式。 (¬p ∧ q) → r 是3层公式。 (¬(p → ¬q )) ∧((r ∨ s) ↔ ¬p )是4层公式。
命题公式的分类
• 定义 (1) 如果A在它的所有赋值下取值均为真，则称命题公 式A为重言式(或永真式) (2) 如果A在它的所有赋值下取值均为,则称命题公式A 为矛盾式(永假式). （3）若A不是矛盾式，则称A为可满足式。 . • 例如： p ∧ (¬ p)为矛盾式，p ∨ (¬ p)为重言式。 (¬ p) ∨q为可满足式。
• 由定义可知：
– – – – ¬p关于p的成真赋值为F, 成假赋值为T. p ∧ q关于p、q的成真赋值为T T, 成假赋值为TF, FT, FF. p ∨ q关于p、q的成真赋值为TT, TF, FT,成假赋值为FF. 不难给出p→q、p↔q的成真和成假赋值.
• 不难看出，含n（n≧1）个命题变项的公式共有2n个不同的 赋值。 • 例如，若公式中共有p、q、r三个不同命题变项，则共有 23=8个指派，分别是： （F，F，F）（F，F，T）（F，T，F）（F，T，T） ， （T，F，F）（T，F，T）（T，T，F）（T，T，T） 。
(4)
只有有限次地应用(1)～(3)形式的符号串才是合式公式。
合式公式也称为命题公式或命题形式，并简称为公式。
下列符号串都是合式公式：
(¬p) (p∧(¬q)) (p ∨(¬p)) (p ↔(¬p)) (p ∧(¬p)) ((p ∧ p) →(¬(p ∨r)))
下列符号串是否为命题公式？
（1）pq → （2）(p¬q) （3）( ( (p∧(¬q)) （4）p∧(¬q) （5）¬p
说明
• A是可满足式：A至少有一个成真赋值。 • 永真式一定是可满足式，反之则不真。 • 真值表可用来判断公式的类型： – 若真值表最后一列全为T，则公式是永真式（重言式）。 – 若真值表最后一列全为F，则公式是永假式（矛盾式）。 – 若真值表最后一列至少有一个T，则公式是可满足式。
例：
三、翻译
只有你通过了英语六级考试而且不是英语专业的学生，才可以
选常将这个过程称为 命题的符号化，或称为命题的翻译。命题的翻译可按如下 步骤进行： ①找出复合命题中的简单命题。
②用英文字母表示这些简单命题。
③使用命题联结词将这些英文字母连接起来。
例
试翻译下列命题。
(1)这个材料无趣,习题也不难,而且这门课程也不使人喜欢。
例
求(p∧q) → (¬(q∨r))的成真和成假赋值。 解： 令(p∧q) → (¬(q∨r))为A。 要使A为假，必须p∧q为真且¬(q∨r)为假。 从而p∧q必须为真，且q∨r也必须为真。 故A的成假指派为TTT和TTF. A的成真指派为FFF、TFF、FTF、FFT、FTT、 TFT。
例
• 例 写出下列公式的真值表，并求它们的成真赋值 和成假赋值： （1）（¬p ∧ q）→ ¬r （2）（p ∧ ¬p ） ↔ （q ∧ ¬q ） （3） ¬（p → p） ∧q ∧r
若指定的一组值使A的真值为T，则称这组值为A的成真赋值； 若使A的真值为F，则称这组值为A的成假赋值。
定义 在命题公式A中，对A的每一个赋值，就确定了A的一个真值， 把它们汇列成表，称该表为命题公式A的真值表。
2
赋值
• 命题公式的真值由其中的命题变元的值 完全确定。 • 公式(p∨q)→r – 若将 p解释成：2是素数 ，T – q解释成：3是偶数， F – r解释成： 是无理数 ，T 2 – 此时公式 (p∨q)→r 被解释成 一个真命题。 – 但是若作别的解释，公式(p∨q)→r 也可以被解释成一 个假命题。
（¬p ∧ q）→ ¬r的真值表
p q r
F F F F F T F T F F T T
¬p
T T T T
¬r
T F T F
¬p ∧ q
F F T 1
（¬p ∧ q）→ ¬r
T T T F
T F F
T F T T T F T T T
F
F F F
T
F T F
F
F F F
T
T T T
• 从表可知公式(1)的成假赋值为FTT，其他7个赋值都是成 真赋值。 • 公式（2）、（3）略。
§1.3 命题公式与翻译
一、命题公式的定义
一个赋予特定内容的命题的真值是确定的，只有“T”
和“F”两种，即命题常项或称为命题常元。 一个没有任 何意义的没有赋予具体内容的命题是一个命题变元。
下面我们正式定义命题变元： 定义：以“真”“假”为其变域的变元称为命题变元。
公式、命题公式（命题形式、合式公式 well-formed formula, wff ）
二、真值表的构建
命题公式的真假是由命题公式中所出现的命题变元 的真假惟一确定，命题变元的一组确定的值叫做命题的 一个指派。每个指派对应命题公式的一个确定的值，所 有的指派构成公式的值，即构成了此命题公式的真值表。
定义
设p1,p2,„,pn是出现在公式A中的全部命题符号，
给p1,p2,„,pn各指定一个真值，称为对A的一个赋值或解释。
• 上节介绍了将命题表示为符号串。
• 是否每个符号串都是命题呢？
pq→ • 什么样的符号串才是命题呢？
• 如下定义的符号串才是命题。
下面给出命题公式的递归定义。
(1)
(2) (3)
单个命题变元是合式公式，并称为原子命题公式。
若A是合式公式，则(┐A)也是合式公式。 若A，B是合式公式， 则(A∧B)，(A∨B)，(A→B)，(AB)也是合式公式。