离散数学 第1章 命题逻辑_2
- 格式：ppt
- 大小：537.50 KB
- 文档页数：22
下载文档原格式
合集下载
离散数学第一章 命题逻辑
令Q表示：张亮是跳远运动员。
于是命题，张亮可能是跳高或跳远运动员就可以用P∨Q来表示，因为这里的或是可 兼或。 逻辑联结词析取也是个二元运算符。
1.1 命题和联结词
逻辑联结词单条件—“→”
设P是一个命题，Q是一个命题，由联结词→把P、Q连接成P→Q，称P→Q为P、 Q的条件式复合命题，把P和Q分别称为P→Q的前件和后件，或者前提和结论。 P→Q读作“如果P则Q”或“如果P那么Q”。其中P被称为前件，Q被称为为后件。 很多时候联结词→也被称为蕴涵。 P→Q的真值是这样定义的，当且仅当P→Q的前件P的真值为T，后件Q的真值为F
1.1 命题和联结词
逻辑联结词否定—“┓”
设P是一个命题，则联结词┓和命题P构成┓P，┓P为命题P的否定式复合 命题，读作“非P”。联结词┓是自然语言中的“非”、“不”和“没有” 等的逻辑抽象。 其真值是这样定义的，若P的真值是T，那么┓P的真值是F；若P的真值 是F，则┓P的真值是T。命题P与其否定┓P的如表1.1所示。
1.2 合式公式与真值表
例1.4 令P表示：小明现在正在睡觉。
令Q表示：小明现在正在打球。 于是命题，小明现在正在睡觉或者正在打球不能用P∨Q来表示。因为这里自然语言陈述的或是 排斥或，这种意义的或我们用另一个逻辑联结词“异或”“”来表示，后面我们将给出它的 定义。
1.1 命题和联结词
逻辑联结词析取——“∨”
例1.5 将句子“他昨晚做了20或者30道作业题”表示为复合命题。 在此例中，该句子不能被表示成复合命题，因为这里的“或”表示的是近似或者猜 测的意思。 例1.6 令P表示：张亮是跳高运动员。
P F F T T Q F T F T P∧Q F F F T P 0 0 1 1 Q 0 1 0 1 P∧Q 0 0 0 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
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
离散数学第一章命题逻辑知识点总结
数理逻辑部分第1章命题逻辑命题符号化及联结词命题: 判断结果惟一的陈述句命题的真值: 判断的结果真值的取值: 真与假真命题: 真值为真的命题假命题: 真值为假的命题注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。
简单命题(原子命题)：简单陈述句构成的命题复合命题：由简单命题与联结词按一定规则复合而成的命题简单命题符号化用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示简单命题用“1”表示真，用“0”表示假例如，令p：是有理数，则p 的真值为 0q：2 + 5 = 7，则q 的真值为 1联结词与复合命题1.否定式与否定联结词“”定义设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假.2.合取式与合取联结词“∧”定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真注意：描述合取式的灵活性与多样性分清简单命题与复合命题例将下列命题符号化.(1) 王晓既用功又聪明.(2) 王晓不仅聪明，而且用功.(3) 王晓虽然聪明，但不用功.(4) 张辉与王丽都是三好生.(5) 张辉与王丽是同学.解令p：王晓用功，q：王晓聪明，则(1) p∧q(2) p∧q(3) p∧q.令r : 张辉是三好学生，s :王丽是三好学生(4) r∧s.(5) 令t : 张辉与王丽是同学，t 是简单命题 .说明:(1)~(4)说明描述合取式的灵活性与多样性.(5) 中“与”联结的是两个名词，整个句子是一个简单命题.3.析取式与析取联结词“∨”定义设p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q. ∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.例将下列命题符号化(1) 2或4是素数.(2) 2或3是素数.(3) 4或6是素数.(4) 小元元只能拿一个苹果或一个梨.(5) 王晓红生于1975年或1976年.解令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 :王晓红生于1975年,w:王晓红生于1976年,则 (5) 既可符号化为 (v∧w)∨(v∧w), 又可符号化为v∨w , 为什么?4.蕴涵式与蕴涵联结词“”定义设p,q为二命题，复合命题“如果p,则q” 称作p与q的蕴涵式，记作p q，并称p是蕴涵式的前件，q为蕴涵式的后件. 称作蕴涵联结词，并规定，p q为假当且仅当p 为真q 为假.p q 的逻辑关系：q 为p 的必要条件“如果p，则q ” 的不同表述法很多：若p，就q只要p，就qp 仅当q只有q 才p除非q, 才p 或除非q, 否则非p.当p 为假时，p q 为真常出现的错误：不分充分与必要条件5.等价式与等价联结词“”定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作p q. 称作等价联结词.并规定p q为真当且仅当p与q同时为真或同时为假.说明:(1) p q 的逻辑关系:p与q互为充分必要条件(2) p q为真当且仅当p与q同真或同假联结词优先级:( ),, , , ,同级按从左到右的顺序进行以上给出了5个联结词：, , , , ，组成一个联结词集合{, , , , }，联结词的优先顺序为：, , , , ; 如果出现的联结词同级，又无括号时，则按从左到右的顺序运算; 若遇有括号时，应该先进行括号中的运算.注意: 本书中使用的括号全为园括号.命题常项命题变项命题公式及分类命题变项与合式公式命题常项：简单命题命题变项：真值不确定的陈述句定义合式公式 (命题公式, 公式) 递归定义如下：(1) 单个命题常项或变项p,q,r,…,p i ,q i ,r i ,…,0,1是合式公式(2) 若A是合式公式，则 (A)也是合式公式(3) 若A, B是合式公式，则(A B), (A B), (A B), (A B)也是合式公式(4) 只有有限次地应用(1)~(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的层次及n同(b)；(d) A=B C, 其中B,C的层次及n同(b)；(e) A=B C, 其中B,C的层次及n同(b).例如公式p 0层p 1层p q 2层(p q)r 3层((p q) r)(r s) 4层公式的赋值定义给公式A中的命题变项p1, p2, … , p n指定一组真值称为对A的一个赋值或解释成真赋值: 使公式为真的赋值成假赋值: 使公式为假的赋值说明：赋值=12…n之间不加标点符号，i=0或1.A中仅出现p1, p2, …, p n，给A赋值12…n是指p1=1, p2=2, …, p n=nA中仅出现p,q, r, …, 给A赋值123…是指p=1,q=2 , r= 3 …含n个变项的公式有2n个赋值.真值表真值表: 公式A在所有赋值下的取值情况列成的表例给出公式的真值表A= (q p) q p的真值表例 B = (p q) q的真值表例C= (p q) r的真值表命题的分类重言式矛盾式可满足式定义设A为一个命题公式(1) 若A无成假赋值，则称A为重言式(也称永真式)(2) 若A无成真赋值，则称A为矛盾式(也称永假式)(3) 若A不是矛盾式，则称A为可满足式注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式A= (q p)q p，B =(p q)q，C= (p q)r等值演算等值式定义若等价式A B是重言式，则称A与B等值，记作A B，并称A B是等值式说明：定义中，A,B,均为元语言符号, A或B中可能有哑元出现.例如，在 (p q) ((p q) (r r))中，r为左边公式的哑元.用真值表可验证两个公式是否等值请验证：p(q r) (p q) rp(q r) (p q) r基本等值式双重否定律 : A A等幂律：A A A, A A A交换律: A B B A, A B B A结合律: (A B)C A(B C)(A B)C A(B C)分配律: A(B C)(A B)(A C)A(B C) (A B)(A C)德·摩根律: (A B)A B(A B)A B吸收律: A(A B)A, A(A B)A零律: A11, A00同一律: A0A, A1A排中律: A A1矛盾律: A A0等值演算:由已知的等值式推演出新的等值式的过程置换规则：若A B, 则(B)(A)等值演算的基础：(1) 等值关系的性质：自反、对称、传递(2) 基本的等值式(3) 置换规则应用举例——证明两个公式等值例1 证明p(q r) (p q)r证p(q r)p(q r) （蕴涵等值式，置换规则）(p q)r（结合律，置换规则）(p q)r（德摩根律，置换规则）(p q) r（蕴涵等值式，置换规则）说明:也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出熟练后，基本等值式也可以不写出应用举例——证明两个公式不等值例2 证明: p(q r) (p q) r用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.方法一真值表法（自己证）方法二观察赋值法. 容易看出000, 010等是左边的的成真赋值，是右边的成假赋值.方法三用等值演算先化简两个公式，再观察.应用举例——判断公式类型例3 用等值演算法判断下列公式的类型(1) q(p q)解q(p q)q(p q) （蕴涵等值式）q(p q) （德摩根律）p(q q) （交换律，结合律）p0 （矛盾律）0 （零律）由最后一步可知，该式为矛盾式.(2) (p q)(q p)解 (p q)(q p)(p q)(q p) （蕴涵等值式）(p q)(p q) （交换律）1由最后一步可知，该式为重言式.问：最后一步为什么等值于1？(3) ((p q)(p q))r)解 ((p q)(p q))r)(p(q q))r（分配律）p1r（排中律）p r（同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A0A为重言式当且仅当A1说明：演算步骤不惟一,应尽量使演算短些对偶与范式对偶式与对偶原理定义在仅含有联结词, ∧,∨的命题公式A中，将∨换成∧, ∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)* 还原成A定理设A和A*互为对偶式，p1,p2,…,p n是出现在A和A*中的全部命题变项，将A和A*写成n元函数形式，则 (1) A(p1,p2,…,p n) A* (p1, p2,…, p n) (2) A(p1, p2,…, p n) A* (p1,p2,…,p n) 定理（对偶原理）设A，B为两个命题公式，若A B，则A* B*.析取范式与合取范式文字:命题变项及其否定的总称简单析取式:有限个文字构成的析取式如p, q, p q, p q r, …简单合取式:有限个文字构成的合取式如p, q, p q, p q r, …析取范式:由有限个简单合取式组成的析取式A 1A2Ar, 其中A1,A2,,A r是简单合取式合取范式:由有限个简单析取式组成的合取式A 1A2Ar, 其中A1,A2,,A r是简单析取式范式:析取范式与合取范式的总称公式A的析取范式: 与A等值的析取范式公式A的合取范式: 与A等值的合取范式说明：单个文字既是简单析取式，又是简单合取式p q r, p q r既是析取范式，又是合取范式(为什么?)命题公式的范式定理任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：(1) 消去A中的, （若存在）(2) 否定联结词的内移或消去(3) 使用分配律对分配（析取范式）对分配（合取范式）公式的范式存在，但不惟一求公式的范式举例例求下列公式的析取范式与合取范式(1) A=(p q)r解 (p q)r(p q)r（消去）p q r（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）(2) B=(p q)r解 (p q)r(p q)r（消去第一个）(p q)r（消去第二个）(p q)r（否定号内移——德摩根律）这一步已为析取范式（两个简单合取式构成）继续： (p q)r(p r)(q r) （对分配律）这一步得到合取范式（由两个简单析取式构成）极小项与极大项定义在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1i n）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.说明：n个命题变项产生2n个极小项和2n个极大项2n个极小项（极大项）均互不等值用m i表示第i个极小项，其中i是该极小项成真赋值的十进制表示. 用M i 表示第i个极大项，其中i是该极大项成假赋值的十进制表示, m i(M i)称为极小项(极大项)的名称.m与M i的关系: m i M i , M i m ii主析取范式与主合取范式主析取范式: 由极小项构成的析取范式主合取范式: 由极大项构成的合取范式例如，n=3, 命题变项为p, q, r时，(p q r)(p q r) m1m3是主析取范式(p q r)(p q r) M1M5 是主合取范式A的主析取范式: 与A等值的主析取范式A的主合取范式: 与A等值的主合取范式.定理任何命题公式都存在着与之等值的主析取范式和主合取范式, 并且是惟一的.用等值演算法求公式的主范式的步骤：(1) 先求析取范式（合取范式）(2) 将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项的析取（极大项的合取），需要利用同一律（零律）、排中律（矛盾律）、分配律、幂等律等.(3) 极小项（极大项）用名称m i（M i）表示，并按角标从小到大顺序排序.求公式的主范式例求公式A=(p q)r的主析取范式与主合取范式.(1) 求主析取范式(p q)r(p q)r , （析取范式）①(p q)(p q)(r r)(p q r)(p q r)m 6m7,r(p p)(q q)r(p q r)(p q r)(p q r)(p q r)m 1m3m5m7③②, ③代入①并排序，得(p q)r m1m3m5m6m7（主析取范式）(2) 求A的主合取范式(p q)r(p r)(q r) , （合取范式）①p rp(q q)r(p q r)(p q r)M 0M2,②q r(p p)q r(p q r)(p q r)M 0M4③②, ③代入①并排序，得(p q)r M0M2M4 （主合取范式）主范式的用途——与真值表相同(1) 求公式的成真赋值和成假赋值例如 (p q)r m1m3m5m6m7，其成真赋值为001, 011, 101, 110, 111，其余的赋值 000, 010, 100为成假赋值.类似地，由主合取范式也可立即求出成假赋值和成真赋值.(2) 判断公式的类型设A含n个命题变项，则A为重言式A的主析取范式含2n个极小项A的主合取范式为1.A为矛盾式A的主析取范式为0A的主合取范式含2n个极大项A为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项例某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习. 选派必须满足以下条件：(1)若赵去，钱也去；(2)李、周两人中至少有一人去；(3)钱、孙两人中有一人去且仅去一人；(4)孙、李两人同去或同不去；(5)若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出国？解此类问题的步骤为：①将简单命题符号化②写出各复合命题③写出由②中复合命题组成的合取式④求③中所得公式的主析取范式解①设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去.② (1) (p q)(2) (s u)(3) ((q r)(q r))(4) ((r s)(r s))(5) (u(p q))③ (1) ~ (5)构成的合取式为A=(p q)(s u)((q r)(q r))((r s)(r s))(u(p q))④ A (p q r s u)(p q r s u)结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.A的演算过程如下:A (p q)((q r)(q r))(s u)(u(p q)) ((r s)(r s)) （交换律) B1= (p q)((q r)(q r))((p q r)(p q r)(q r)) （分配律）B2= (s u)(u(p q))((s u)(p q s)(p q u)) （分配律）B 1B2(p q r s u)(p q r s u) (q r s u)(p q r s)(p q r u)再令B3 = ((r s)(r s))得A B1B2B3(p q r s u)(p q r s u)注意：在以上演算中多次用矛盾律要求：自己演算一遍推理理论推理的形式结构推理的形式结构—问题的引入推理举例:(1) 正项级数收敛当且仅当部分和有上界.(2) 若推理: 从前提出发推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.证明: 描述推理正确的过程.判断推理是否正确的方法•真值表法•等值演算法判断推理是否正确•主析取范式法•构造证明法证明推理正确说明：当命题变项比较少时，用前3个方法比较方便, 此时采用形式结构“” . 而在构造证明时，采用“前提: , 结论: B”.推理定律与推理规则推理定律——重言蕴涵式构造证明——直接证明法例构造下面推理的证明：若明天是星期一或星期三，我就有课. 若有课，今天必备课. 我今天下午没备课. 所以，明天不是星期一和星期三.解设p：明天是星期一，q：明天是星期三，r：我有课，s：我备课推理的形式结构为例构造下面推理的证明:2是素数或合数. 若2是素数，则是无理数.若是无理数，则4不是素数. 所以，如果4是素数，则2是合数.用附加前提证明法构造证明解设p：2是素数，q：2是合数，r：是无理数，s：4是素数推理的形式结构前提：p∨q, p r, r s结论：s q证明① s附加前提引入②p r前提引入③r s前提引入④p s②③假言三段论⑤p①④拒取式⑥p∨q前提引入⑦q⑤⑥析取三段论请用直接证明法证明之。
离散数学II
b)：相同的运算符，从左到右次序计算时，括号 可省去。
c)：最外层括号可省。 如，(¬((P ∧ ¬Q) ∨R) →((R ∨P)∨Q))
¬(P ∧ ¬Q∨R) →R ∨P∨Q
21/73
1.1 命题与命题联结词
• 例1.3：符号化下列命题。
a)：他既有理论知识又有实践经验 b)：i. 如果明天不是雨夹雪则我去学校
26/73
1.2 公式的解释与真值表
• 原子命题在不指派真值时称为命题变元，而
复合命题由原子命题和联结词构成，可以看 作是命题变元的函数，且该函数的值仍为 “真”或“假”，可以称为真值函数（True Value Function）或命题公式。但不是说原 子命题和联结词的一个随便的组合都可以为 命题公式，我们用递归的方法来定义命题公 式。
• 例，(¬ P∧Q)，(P→(¬P ∧Q)) ，(((P∧Q) ∧(R
∨Q)) ↔(P →R))是命题公式 (P →Q )∧¬ Q)， (P →Q， (¬ P∨Q ∨(R， P∨Q ∨不是命题公式
28/73
1.2 公式的解释与真值表
• 注意：
– 如果G是含有n个命题变元 P1, P2, …,Pn的公式， 通常记为G（P1, …,Pn）或简记为G。
汇集起来的一门综合学科。离散数学的应用遍
及现代科学技术的诸多领域。
–离散数学是随着计算机科学的发展而逐步建立
起来的一门新兴的工具性学科，形成于上上个
世纪七十年代。
2/73
引言
• 课程意义
–离散数学是计算机科学的数学基础，其基本概念、 理论、方法大量地应用在数字电路、编译原理、数 据结构、操作系统、数据库系统、算法设计、人工 智能、计算机网络等专业课程中，是这些课程的基 础课程。
c)：最外层括号可省。 如，(¬((P ∧ ¬Q) ∨R) →((R ∨P)∨Q))
¬(P ∧ ¬Q∨R) →R ∨P∨Q
21/73
1.1 命题与命题联结词
• 例1.3：符号化下列命题。
a)：他既有理论知识又有实践经验 b)：i. 如果明天不是雨夹雪则我去学校
26/73
1.2 公式的解释与真值表
• 原子命题在不指派真值时称为命题变元，而
复合命题由原子命题和联结词构成，可以看 作是命题变元的函数，且该函数的值仍为 “真”或“假”，可以称为真值函数（True Value Function）或命题公式。但不是说原 子命题和联结词的一个随便的组合都可以为 命题公式，我们用递归的方法来定义命题公 式。
• 例，(¬ P∧Q)，(P→(¬P ∧Q)) ，(((P∧Q) ∧(R
∨Q)) ↔(P →R))是命题公式 (P →Q )∧¬ Q)， (P →Q， (¬ P∨Q ∨(R， P∨Q ∨不是命题公式
28/73
1.2 公式的解释与真值表
• 注意：
– 如果G是含有n个命题变元 P1, P2, …,Pn的公式， 通常记为G（P1, …,Pn）或简记为G。
汇集起来的一门综合学科。离散数学的应用遍
及现代科学技术的诸多领域。
–离散数学是随着计算机科学的发展而逐步建立
起来的一门新兴的工具性学科，形成于上上个
世纪七十年代。
2/73
引言
• 课程意义
–离散数学是计算机科学的数学基础，其基本概念、 理论、方法大量地应用在数字电路、编译原理、数 据结构、操作系统、数据库系统、算法设计、人工 智能、计算机网络等专业课程中，是这些课程的基 础课程。
第一章 逻辑与证明(2)
15
NEC-DM
p
T T T F T F F F
q
T T F T F T F F
r
T F T T F F T F
q∨r
p → (q∨r)
¬q
¬r
¬p
p → (q∨r) ¬q ¬r _________ ¬p
注意到：当p → (q∨r) ，¬q ， ¬r 三 个命题都为T的时候，¬p也为T，因此本 论证有效。
NEC-DM
例
假设d、d1、d2 和x 是任意实数 if d=min(d1,d2) and x ≤d then x ≤d1 and x ≤d2 证明：根据min 的定义可以推出d ≤ d1 并且d ≤ d2。 依x ≤ d 并且d ≤ d1，可以根据前面的定理（例 1.5.5 的第二个定理）推出x ≤ d1。由于x ≤ d 并且d ≤ d2，可以根据前面的同一个定理推出 x ≤ d2。因此，x ≤ d1 并且x ≤ d2。
2
NEC-DM
1.5.2 命题逻辑的有效论证
从一系列前提得出结论的方法称为演绎推理。 前提：已知的命题系列 结论：由假设得出的结论
结论从前提导出 结论为真 任何论证过程都有形式： 如果p1并且p2并且…并且pn, 则q。 论证有效在于形式不在于内容
3
NEC-DM
定义
一个论证过程是一系列的命题， p1,p2,…,pn/∴q p1,p2,…,pn称为前提，命题q是结论 如p1,p2,…,pn全为真，则q也必为真， 那么论证有效；否则论证过程是无 效的
假设３段论
p q pq
析取３段论
化简
附加
pq p
p pq
pq qr pr
pq p q
8
离散数学第一章命题逻辑知识点总结
数理逻辑部分第1章命题逻辑命题符号化及联结词命题: 判断结果惟一的陈述句命题的真值: 判断的结果真值的取值: 真与假真命题: 真值为真的命题假命题: 真值为假的命题注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。
简单命题(原子命题)：简单陈述句构成的命题复合命题：由简单命题与联结词按一定规则复合而成的命题简单命题符号化用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示简单命题用“1”表示真，用“0”表示假例如，令p：是有理数，则p 的真值为 0q：2 + 5 = 7，则q 的真值为 1联结词与复合命题1.否定式与否定联结词“”定义设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假.2.合取式与合取联结词“∧”定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真注意：描述合取式的灵活性与多样性分清简单命题与复合命题例将下列命题符号化.(1) 王晓既用功又聪明.(2) 王晓不仅聪明，而且用功.(3) 王晓虽然聪明，但不用功.(4) 张辉与王丽都是三好生.(5) 张辉与王丽是同学.解令p：王晓用功，q：王晓聪明，则(1) p∧q(2) p∧q(3) p∧q.令r : 张辉是三好学生，s :王丽是三好学生(4) r∧s.(5) 令t : 张辉与王丽是同学，t 是简单命题 .说明:(1)~(4)说明描述合取式的灵活性与多样性.(5) 中“与”联结的是两个名词，整个句子是一个简单命题.3.析取式与析取联结词“∨”定义设p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q. ∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.例将下列命题符号化(1) 2或4是素数.(2) 2或3是素数.(3) 4或6是素数.(4) 小元元只能拿一个苹果或一个梨.(5) 王晓红生于1975年或1976年.解令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 :王晓红生于1975年,w:王晓红生于1976年,则 (5) 既可符号化为 (v∧w)∨(v∧w), 又可符号化为v∨w , 为什么4.蕴涵式与蕴涵联结词“”定义设p,q为二命题，复合命题“如果p,则q” 称作p与q的蕴涵式，记作p q，并称p是蕴涵式的前件，q为蕴涵式的后件. 称作蕴涵联结词，并规定，p q为假当且仅当p 为真q 为假.p q 的逻辑关系：q 为p 的必要条件“如果p，则q ” 的不同表述法很多：若p，就q只要p，就qp 仅当q只有q 才p除非q, 才p 或除非q, 否则非p.当p 为假时，p q 为真常出现的错误：不分充分与必要条件5.等价式与等价联结词“”定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作p q. 称作等价联结词.并规定p q为真当且仅当p与q同时为真或同时为假.说明:(1) p q 的逻辑关系:p与q互为充分必要条件(2) p q为真当且仅当p与q同真或同假联结词优先级:( ),, , , ,同级按从左到右的顺序进行以上给出了5个联结词：, , , , ，组成一个联结词集合{, , , , }，联结词的优先顺序为：, , , , ; 如果出现的联结词同级，又无括号时，则按从左到右的顺序运算; 若遇有括号时，应该先进行括号中的运算.注意: 本书中使用的括号全为园括号.命题常项命题变项命题公式及分类命题变项与合式公式命题常项：简单命题命题变项：真值不确定的陈述句定义合式公式 (命题公式, 公式) 递归定义如下：(1) 单个命题常项或变项p,q,r,…,p i ,q i ,r i ,…,0,1是合式公式(2) 若A是合式公式，则 (A)也是合式公式(3) 若A, B是合式公式，则(A B), (A B), (A B), (A B)也是合式公式(4) 只有有限次地应用(1)~(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的层次及n同(b)；(d) A=B C, 其中B,C的层次及n同(b)；(e) A=B C, 其中B,C的层次及n同(b).例如公式p 0层p 1层p q 2层(p q)r 3层((p q) r)(r s) 4层公式的赋值定义给公式A中的命题变项p1, p2, … , p n指定一组真值称为对A的一个赋值或解释成真赋值: 使公式为真的赋值成假赋值: 使公式为假的赋值说明：赋值=12…n之间不加标点符号，i=0或1.A中仅出现p1, p2, …, p n，给A赋值12…n是指p1=1, p2=2, …, p n=nA中仅出现p,q, r, …, 给A赋值123…是指p=1,q=2 , r= 3 …含n个变项的公式有2n个赋值.真值表真值表: 公式A在所有赋值下的取值情况列成的表例给出公式的真值表A= (q p) q p的真值表例 B = (p q) q的真值表例C= (p q) r的真值表命题的分类重言式矛盾式可满足式定义设A为一个命题公式(1) 若A无成假赋值，则称A为重言式(也称永真式)(2) 若A无成真赋值，则称A为矛盾式(也称永假式)(3) 若A不是矛盾式，则称A为可满足式注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式A= (q p)q p，B =(p q)q，C= (p q)r等值演算等值式定义若等价式A B是重言式，则称A与B等值，记作A B，并称A B是等值式说明：定义中，A,B,均为元语言符号, A或B中可能有哑元出现.例如，在 (p q) ((p q) (r r))中，r为左边公式的哑元.用真值表可验证两个公式是否等值请验证：p(q r) (p q) rp(q r) (p q) r基本等值式双重否定律 : A A等幂律：A A A, A A A交换律: A B B A, A B B A结合律: (A B)C A(B C)(A B)C A(B C)分配律: A(B C)(A B)(A C)A(B C) (A B)(A C) 德·摩根律: (A B)A B(A B)A B吸收律: A(A B)A, A(A B)A零律: A11, A00同一律: A0A, A1A排中律: A A 1矛盾律: A A0等值演算:由已知的等值式推演出新的等值式的过程置换规则：若A B, 则(B)(A)等值演算的基础：(1) 等值关系的性质：自反、对称、传递(2) 基本的等值式(3) 置换规则应用举例——证明两个公式等值例1 证明p(q r) (p q)r证p(q r)p(q r) （蕴涵等值式，置换规则）(p q)r（结合律，置换规则）(p q)r（德摩根律，置换规则）(p q) r（蕴涵等值式，置换规则）说明:也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出熟练后，基本等值式也可以不写出应用举例——证明两个公式不等值例2 证明: p(q r) (p q) r用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.方法一真值表法（自己证）方法二观察赋值法. 容易看出000, 010等是左边的的成真赋值，是右边的成假赋值.方法三用等值演算先化简两个公式，再观察.应用举例——判断公式类型例3 用等值演算法判断下列公式的类型(1) q(p q)解q(p q)q(p q) （蕴涵等值式）q(p q) （德摩根律）p(q q) （交换律，结合律）p0 （矛盾律）0 （零律）由最后一步可知，该式为矛盾式.(2) (p q)(q p)解 (p q)(q p)(p q)(q p) （蕴涵等值式）(p q)(p q) （交换律）1由最后一步可知，该式为重言式.问：最后一步为什么等值于1(3) ((p q)(p q))r)解 ((p q)(p q))r)(p(q q))r（分配律）p1r（排中律）p r（同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A0A为重言式当且仅当A 1说明：演算步骤不惟一,应尽量使演算短些对偶与范式对偶式与对偶原理定义在仅含有联结词, ∧,∨的命题公式A中，将∨换成∧, ∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)* 还原成A定理设A和A*互为对偶式，p1,p2,…,p n是出现在A和A*中的全部命题变项，将A和A*写成n元函数形式，则 (1) A(p1,p2,…,p n) A* (p1, p2,…, p n)(2) A(p1, p2,…, p n) A* (p1,p2,…,p n)定理（对偶原理）设A，B为两个命题公式，若A B，则A* B*.析取范式与合取范式文字:命题变项及其否定的总称简单析取式:有限个文字构成的析取式如p, q, p q, p q r, …简单合取式:有限个文字构成的合取式如p, q, p q, p q r, …析取范式:由有限个简单合取式组成的析取式A 1A2Ar, 其中A1,A2,,A r是简单合取式合取范式:由有限个简单析取式组成的合取式A 1A2Ar, 其中A1,A2,,A r是简单析取式范式:析取范式与合取范式的总称公式A的析取范式: 与A等值的析取范式公式A的合取范式: 与A等值的合取范式说明：单个文字既是简单析取式，又是简单合取式p q r, p q r既是析取范式，又是合取范式(为什么)命题公式的范式定理任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：(1) 消去A中的, （若存在）(2) 否定联结词的内移或消去(3) 使用分配律对分配（析取范式）对分配（合取范式）公式的范式存在，但不惟一求公式的范式举例例求下列公式的析取范式与合取范式(1) A=(p q)r解 (p q)r(p q)r（消去）p q r（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）(2) B=(p q)r解 (p q)r(p q)r（消去第一个）(p q)r（消去第二个）(p q)r（否定号内移——德摩根律）这一步已为析取范式（两个简单合取式构成）继续： (p q)r(p r)(q r) （对分配律）这一步得到合取范式（由两个简单析取式构成）极小项与极大项定义在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1i n）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.说明：n个命题变项产生2n个极小项和2n个极大项2n个极小项（极大项）均互不等值用m i表示第i个极小项，其中i是该极小项成真赋值的十进制表示. 用M i表示第i个极大项，其中i是该极大项成假赋值的十进制表示, m i(M i)称为极小项(极大项)的名称.m与M i的关系: m i M i , M i m ii主析取范式与主合取范式主析取范式: 由极小项构成的析取范式主合取范式: 由极大项构成的合取范式例如，n=3, 命题变项为p, q, r时，(p q r)(p q r) m1m3是主析取范式(p q r)(p q r) M1M5 是主合取范式A的主析取范式: 与A等值的主析取范式A的主合取范式: 与A等值的主合取范式.定理任何命题公式都存在着与之等值的主析取范式和主合取范式, 并且是惟一的.用等值演算法求公式的主范式的步骤：(1) 先求析取范式（合取范式）(2) 将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项的析取（极大项的合取），需要利用同一律（零律）、排中律（矛盾律）、分配律、幂等律等.(3) 极小项（极大项）用名称m i（M i）表示，并按角标从小到大顺序排序.求公式的主范式例求公式A=(p q)r的主析取范式与主合取范式.(1) 求主析取范式(p q)r(p q)r , （析取范式）① (p q)(p q)(r r)(p q r)(p q r)m 6m7,r(p p)(q q)r(p q r)(p q r)(p q r)(p q r)m 1m3m5m7③②, ③代入①并排序，得(p q)r m1m3m5m6m7（主析取范式）(2) 求A的主合取范式(p q)r(p r)(q r) , （合取范式）①p rp(q q)r(p q r)(p q r)M 0M2,②q r(p p)q r(p q r)(p q r)M 0M4③②, ③代入①并排序，得(p q)r M0M2M4 （主合取范式）主范式的用途——与真值表相同(1) 求公式的成真赋值和成假赋值例如 (p q)r m1m3m5m6m7，其成真赋值为001, 011, 101, 110, 111，其余的赋值 000, 010, 100为成假赋值.类似地，由主合取范式也可立即求出成假赋值和成真赋值.(2) 判断公式的类型设A含n个命题变项，则A为重言式A的主析取范式含2n个极小项A的主合取范式为1.A为矛盾式A的主析取范式为0A的主合取范式含2n个极大项A为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项例某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习. 选派必须满足以下条件：(1)若赵去，钱也去；(2)李、周两人中至少有一人去；(3)钱、孙两人中有一人去且仅去一人；(4)孙、李两人同去或同不去；(5)若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出国解此类问题的步骤为：①将简单命题符号化②写出各复合命题③写出由②中复合命题组成的合取式④求③中所得公式的主析取范式解①设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去.② (1) (p q)(2) (s u)(3) ((q r)(q r))(4) ((r s)(r s))(5) (u(p q))③ (1) ~ (5)构成的合取式为A=(p q)(s u)((q r)(q r))((r s)(r s))(u(p q))④ A (p q r s u)(p q r s u) 结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.A的演算过程如下:A (p q)((q r)(q r))(s u)(u(p q)) ((r s)(r s)) （交换律) B1= (p q)((q r)(q r))((p q r)(p q r)(q r)) （分配律）B2= (s u)(u(p q))((s u)(p q s)(p q u)) （分配律）B 1B2(p q r s u)(p q r s u) (q r s u)(p q r s)(p q r u)再令B3 = ((r s)(r s))得A B1B2B3(p q r s u)(p q r s u) 注意：在以上演算中多次用矛盾律要求：自己演算一遍推理理论推理的形式结构推理的形式结构—问题的引入推理举例:(1) 正项级数收敛当且仅当部分和有上界.(2) 若推理: 从前提出发推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.证明: 描述推理正确的过程.判断推理是否正确的方法•真值表法•等值演算法判断推理是否正确•主析取范式法•构造证明法证明推理正确说明：当命题变项比较少时，用前3个方法比较方便, 此时采用形式结构“” . 而在构造证明时，采用“前提: , 结论: B”.推理定律与推理规则推理定律——重言蕴涵式构造证明——直接证明法例构造下面推理的证明：若明天是星期一或星期三，我就有课. 若有课，今天必备课. 我今天下午没备课. 所以，明天不是星期一和星期三.解设p：明天是星期一，q：明天是星期三，r：我有课，s：我备课推理的形式结构为例构造下面推理的证明:2是素数或合数. 若2是素数，则是无理数.若是无理数，则4不是素数. 所以，如果4是素数，则2是合数.用附加前提证明法构造证明解设p：2是素数，q：2是合数，r：是无理数，s：4是素数推理的形式结构前提：p∨q, p r, r s结论：s q证明① s附加前提引入②p r前提引入③r s前提引入④p s②③假言三段论⑤p①④拒取式⑥p∨q前提引入⑦q⑤⑥析取三段论请用直接证明法证明之。
第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章命题逻辑基本概念
离散数学结构第1章命题逻辑基本概念第1章命题逻辑基本概念主要内容1. 命题与真值（或真假值）。
2. 简单命题与复合命题。
3. 联结词：否定联结词┐，合取联结词∧，析取联结词∨，蕴涵联结词→，等价联结词。
4. 命题公式（简称公式）。
5. 命题公式的层次和公式的赋值。
6. 真值表。
7. 公式的类型（重⾔式（或永真式），⽭盾式（或永假式），可满⾜式）。
学习要求1. 在5种联结词中，要特别注意蕴涵联结的应⽤，要弄清三个问题：① p→q的逻辑关系② p→q的真值③ p→q的灵活的叙述⽅法2. 写真值表要特别仔细认真，否则会出错误。
3. 深刻理解各联结词的逻辑含义。
4. 熟练地将复合命题符号化。
6. 会⽤真值表求公式的成真赋值和成假赋值。
1.1 命题与联结词 (2)⼀、命题的概念 (2)⼆、复合命题与联结词 (2)三、复合命题真假值 (5)1.2 命题公式及其赋值 (6)⼀、命题公式的定义 (6)⼆、公式的层次 (6)三、公式的赋值 (6)四、真值表 (7)五、公式的真假值分类 (8)1.1 命题与联结词⼀、命题的概念引⾔中的例⼦就是要对“我戴的是⿊帽⼦”进⾏判断。
这样的陈述句称为命题。
作为命题的陈述句所表达的判断结果称为命题的真值，真值只取两个值：真或假。
真值为真的命题称为真命题，真值为假的命题称为假命题。
真命题表达的判断正确，假命题表达的判断错误。
任何命题的真值都是唯⼀的。
判断给定句⼦是否为命题，应该分两步：⾸先判定它是否为陈述句，其次判断它是否有唯⼀的真值。
例1.1 判断下列句⼦是否为命题。
(1) 4是素数。
(2) 是⽆理数。
(3) x⼤于y。
(4) ⽉球上有冰。
(5) 2100年元旦是晴天。
(6) π⼤于吗？(7) 请不要吸烟！(8) 这朵花真美丽啊！(9) 我正在说假话。
解:本题的(9)个句⼦中，(6)是疑问句，(7)是祈使句，(8)是感叹句，因⽽这3个句⼦都不是命题。
剩下的6个句⼦都是陈述句，但(3)⽆确定的真值，根据x,y的不同取值情况它可真可假，即⽆唯⼀的真值，因⽽不是命题。
离散数学——精选推荐
离散数学第一章命题逻辑定义1。
设P为一命题，P的否定是一个新的命题，记作¬P。
若P为T，¬P为F；若P为F，¬P为T。
联结词“¬”表示命题的否定。
否定联结词有时亦可记作“¯”。
（P3）定义2。
两个命题P和Q的合取是一个复合命题，记作P∧Q。
当且仅当P,Q同时为T时，P∧Q为T，在其他情况下，P∧Q的真值都是F。
（P4）定义3。
两个命题P和Q的析取是一个复合命题，记作P∨Q。
当且仅当P，Q同时为F时，P∨Q的真值为F，否则P∨Q的真值为T。
（P5）定义4。
给定两个命题P和Q，其条件命题是一个复合命题，记作P→Q，读作“如果P，那么Q”或者“若P则Q”。
当且仅当P的真值为T，Q的真值为F时，P→Q的真值为F，否则P→Q的真值为T。
我们称P为前件，Q为后件。
（P6）定义5。
给定两个命题P和Q，其复合命题P⇆Q的真值为F。
（P7）定义6。
命题演算的合式公式（wff），规定为：（1）单个命题变元本身是一个合式公式。
（2）如果A是合式公式，那么¬A是合式公式。
（3）如果A和B是合式公式，那么（A∧B），（A∨B），（A→B）和（A⇆B）都是合式公式。
（4）当且仅当能够有限次地应用（1），（2），（3）所得到的包含命题变元，联结词和括号的符号串是合式公式。
（P9）定义7。
在命题公式中，对于分量指派真值得各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。
（P12）定义8。
给定两个命题公式A和B，设P1，P2，…，P n为所有出现于A和B中的原子变元，若给P1，P2，…，P n任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等。
记作A⇔B。
（P15）定义9。
如果X是合式公式的A的一部分，且X本身也是一个合式公式，则称X为公式A 的字公式。
（P16）定理1。
设X是合式公式A的字公式，若X⇔Y，如果将A中的X用Y来置换，所得到公式B 与公式A等价，即A⇔B。
离散数学复习资料
离散数学复习资料第1章命题逻辑本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)范式，命题逻辑的推理理论.一、重点内容1. 命题命题表述为具有确定真假意义的陈述句。
命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义.2. 六个联结词及真值表h“”否定联结词，P是命题，P是P的否命题，是由联结词和命题P组成的复合命题.P取真值1，P取真值0，P取真值0，P取真值1. 它是一元联结词.h “”合取联结词，P Q是命题P，Q的合取式，是“”和P，Q组成的复合命题. “”在语句中相当于“不但…而且…”，“既…又…”. P Q取值1，当且仅当P，Q均取1；P Q取值为0，只有P，Q之一取0.h “”析取联结词，“”不可兼析取(异或)联结词， P Q是命题P，Q的析取式，是“”和P，Q组成的复合命题. P Q是联结词“”和P，Q组成的复合命题. 联结词“”或“”在一个语句中都表示“或”的含义，前者表示相容或，后者表示排斥或不相容的或. 即“P Q”“(P Q)(P Q)”. P Q取值1，只要P，Q之一取值1，P Q取值0，只有P，Q都取值0.h “”蕴含联结词， P Q是“”和P，Q组成的复合命题，只有P取值为1，Q取值为0时，P Q取值为0；其余各种情况，均有P Q的真值为1，亦即10的真值为0，01，11，00的真值均为1. 在语句中，“如果P则Q”或“只有Q，才P，”表示为“P Q”.h “” 等价联结词，P Q是P，Q的等价式，是“”和P，Q组成的复合命题. “”在语句中相当于“…当且仅当…”，P Q取值1当且仅当P，Q真值相同.3. 命题公式、赋值与解释，命题公式的分类与判别h命题公式与赋值，命题P含有n个命题变项P1，P2,…,P n，给P1，P2,…,P n各指定一个真值，称为对P的一个赋值(真值指派). 若指定的一组值使P的真值为1，则这组值为P的真指派；若使P的真值为0，则称这组值称为P的假指派.h命题公式分类，在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式；判定命题公式类型的方法：其一是真值表法，任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.其二是推导演算法. 利用基本等值式(教材的十六个等值式或演算律)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式.既非永真，也非用假，成为非永真的可满足式.其三主析取(合取)范式法，该公式的主析取范式有2n个极小项(即无极大项)，则该公式是永真式；该公式的主合取范式有2n个极大项(即无极小项)，则该公式是永假式；该公式的主析取(或合取)范式的极小项(或极大项)个数大于0小于2n,，则该公式是可满足式.h等值式A B，命题公式A，B在任何赋值下，它们的真值均相同，称A，B等值。
离散数学之1—命题逻辑
pq 的逻辑关系：p为 q 的充分条件， 或者：q为 p 的必要条件。 注意：当 p 为假时，pq恒为真。 实例： 如果天气好，我就去游玩。 p → q 如果我得到这本小说，我将读完它。 p → q 如果雪是黑的，那么太阳从西方升起。 p → q
28
蕴涵联结词的实例
我将去旅游，仅当我有时间。 p: 我去旅游 q: 我有时间 p→q p: 不下雨 q: 我骑自行车上班 只要不下雨，我就骑自行车上班 p→q 只有不下雨，我才骑自行车上班。 q→p
说谎者悖论 亚里士多德,古希腊人，是世界
古典形式逻辑
如果这个人说的是假话，既 在中世纪，形式逻辑作为一门独 “我没有说谎”，既他说的是 立的科学得到了发展。 真话，矛盾。
第一篇 数理逻辑
6
数理逻辑创始人
德国哲学家和数学家莱布 尼茨是德国最重要的自然 科学家、数学家、物理学 家和哲学家，一个举世罕 见的科学天才，和牛顿同 为微积分的创建人。 莱布尼茨是现在公认的数 理逻辑创始人，他的目的 是建立一种“表意的符号 语言”，其中把一切思维 推理都化归为计算。实际 上这正是数理逻辑的总纲 领。
29
蕴涵联结词的实例
除非你努力，否则你不能成功。 表示p q的常用词： 除非你努力，你才能成功。 p是q的充分条件 p: 你努力 q: 你成功 q是p的必要条件 p → q 或 q → p 如果（若）p，则q p 0 0 1 1 q 0 1 0 1 p 1 1 0 0
只要p，就q q qp pq 只有q 才p 1因为p所以 1 q 1 0p仅当q0 0 才p 1除非q, 1 1 p 0除非q，否则非 1 1
数理逻辑
“事实上，它们（程 序设计）或者就是 数理逻辑，或者是 用计算机语言书写 的数理逻辑，或者 是数理逻辑在计算 机上的应用。”
28
蕴涵联结词的实例
我将去旅游，仅当我有时间。 p: 我去旅游 q: 我有时间 p→q p: 不下雨 q: 我骑自行车上班 只要不下雨，我就骑自行车上班 p→q 只有不下雨，我才骑自行车上班。 q→p
说谎者悖论 亚里士多德,古希腊人，是世界
古典形式逻辑
如果这个人说的是假话，既 在中世纪，形式逻辑作为一门独 “我没有说谎”，既他说的是 立的科学得到了发展。 真话，矛盾。
第一篇 数理逻辑
6
数理逻辑创始人
德国哲学家和数学家莱布 尼茨是德国最重要的自然 科学家、数学家、物理学 家和哲学家，一个举世罕 见的科学天才，和牛顿同 为微积分的创建人。 莱布尼茨是现在公认的数 理逻辑创始人，他的目的 是建立一种“表意的符号 语言”，其中把一切思维 推理都化归为计算。实际 上这正是数理逻辑的总纲 领。
29
蕴涵联结词的实例
除非你努力，否则你不能成功。 表示p q的常用词： 除非你努力，你才能成功。 p是q的充分条件 p: 你努力 q: 你成功 q是p的必要条件 p → q 或 q → p 如果（若）p，则q p 0 0 1 1 q 0 1 0 1 p 1 1 0 0
只要p，就q q qp pq 只有q 才p 1因为p所以 1 q 1 0p仅当q0 0 才p 1除非q, 1 1 p 0除非q，否则非 1 1
数理逻辑
“事实上，它们（程 序设计）或者就是 数理逻辑，或者是 用计算机语言书写 的数理逻辑，或者 是数理逻辑在计算 机上的应用。”
(完整版)《离散数学》同步练习答案
华南理工大学网络教育学院《离散数学》练习题参考答案第一章命题逻辑一填空题（1）设：p：派小王去开会。
q：派小李去开会。
则命题：“派小王或小李中的一人去开会”可符号化为：(p∨⌝q) ∧ (⌝p∨q) 。
（2）设A，B都是命题公式，A⇒B，则A→B的真值是T。
（3）设：p：刘平聪明。
q：刘平用功。
在命题逻辑中，命题：“刘平不但不聪明，而且不用功”可符号化为：p∧q。
（4）设A , B 代表任意的命题公式，则蕴涵等值式为A → B⇔⌝A∨B。
（5）设，p：径一事；q：长一智。
在命题逻辑中，命题：“不径一事，不长一智。
”可符号化为：⌝ p→⌝q 。
（6）设A , B 代表任意的命题公式，则德•摩根律为⌝（A ∧ B）⇔⌝A ∨⌝B）。
（7）设，p：选小王当班长；q：选小李当班长。
则命题：“选小王或小李中的一人当班长。
”可符号化为：(p∨⌝q) ∧ (⌝p∨q) 。
（8）设，P：他聪明；Q：他用功。
在命题逻辑中，命题：“他既聪明又用功。
”可符号化为：P∧Q 。
（9）对于命题公式A，B，当且仅当 A → B 是重言式时，称“A蕴含B”，并记为A⇒B。
（10）设：P：我们划船。
Q：我们跑步。
在命题逻辑中，命题：“我们不能既划船又跑步。
”可符号化为：⌝ (P∧Q) 。
（11）设P , Q是命题公式，德·摩根律为：⌝（P∨Q）⇔⌝P∧⌝Q）。
（12）设P：你努力。
Q：你失败。
在命题逻辑中，命题：“除非你努力，否则你将失败。
”可符号化为：⌝P→Q。
（13）设p：小王是100米赛跑冠军。
q：小王是400米赛跑冠军。
在命题逻辑中，命题：“小王是100米或400米赛跑冠军。
”可符号化为：p∨q。
（14）设A，C为两个命题公式，当且仅当A→C为一重言式时，称C可由A逻辑地推出。
二．判断题1.设A，B是命题公式，则蕴涵等值式为A→B⇔⌝A∧B。
（⨯）2.命题公式⌝p∧q∧⌝r是析取范式。
（√）3.陈述句“x + y > 5”是命题。
离散数学课后习题答案
第一章命题逻辑基本概念课后练习题答案1.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.2.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；3.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.4.因为p与q不能同时为真.5.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.返回第二章命题逻辑等值演算本章自测答案5.(1)：∨∨,成真赋值为00、10、11；(2)：0，矛盾式，无成真赋值；(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部为成真赋值；7.(1)：∨∨∨∨⇔∧∧；(2)：∨∨∨⇔∧∧∧；8.(1)：1⇔∨∨∨,重言式；(2)：∨⇔∨∨∨∨∨∨；(3)：∧∧∧∧∧∧∧⇔0，矛盾式.11.(1)：∨∨⇔∧∧∧∧；(2)：∨∨∨∨∨∨∨⇔1；(3)：0⇔∧∧∧.12.A⇔∧∧∧∧⇔∨∨.第三章命题逻辑的推理理论本章自测答案6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确(1)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*1)在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即(p→q)∧p→q ⇒ q(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*2)可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等(p→q)∧q→p⇔(┐p∨q) ∧q →p⇔q →p⇔┐p∨┐q⇔⇔∨∨从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.9.设p:a是奇数，q:a能被2整除，r:a：是偶数推理的形式结构为(p→q┐)∧(r→q)→(r→┐p) (记为*)可以用多种方法证明*为重言式，下面用等值演算法证明：(p→┐q)∧(r→q)→(r→┐p)⇔(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律)⇔(p∨q)∨(┐p∧r)∨┐q∨┐r⇔(┐p∨q)∨(┐q∧┐r)⇔┐p∨(q∨┐q)∧┐r⇔110.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.推理的形式结构为(p→q)∧┐p→(┐q∧┐r)⇔(┐p∨q) ∧┐p→(┐q∧┐r)⇔┐p→(┐q∧┐r) (使用了吸收律)⇔p∨(┐q∧┐r)⇔∨∨∨由于主析取范式中只含有5个W极小项，故推理不正确.11.略14.证明的命题序列可不惟一，下面对每一小题各给出一个证明① p→(q→r)前提引入② P前提引入③ q→r①②假言推理④ q前提引入⑤ r③④假言推理⑥ r∨s前提引入（2）证明：① ┐(p∧r)前提引入② ┐q∨┐r①置换③ r前提引入④ ┐q ②③析取三段论⑤ p→q前提引入⑥ ┐p④⑤拒取式（3）证明：① p→q前提引入② ┐q∨q①置换③ (┐p∨q)∧(┐p∨p) ②置换④ ┐p∨(q∧p③置换⑤ p→(p∨q) ④置换15.(1)证明：① S结论否定引入② S→P前提引入③ P①②假言推理④ P→(q→r)前提引入⑤ q→r③④假言推论⑥ q前提引入⑦ r⑤⑥假言推理（2）证明：① p附加前提引入② p∨q①附加③ (p∨q)→(r∧s)前提引入④ r∧s②③假言推理⑤ s④化简⑥ s∨t⑤附加⑦ (s∨t)→u前提引入⑧ u⑥⑦拒取式16.(1)证明：① p结论否定引入② p→ ┐q前提引入③ ┐q ①②假言推理④ ┐r∨q前提引入⑤ ┐r③④析取三段论⑥ r∧┐s前提引入⑦ r⑥化简⑧ ┐r∧r⑤⑦合取（2）证明：① ┐(r∨s)结论否定引入② ┐r∨┐s①置换③ ┐r②化简④ ┐s②化简⑤ p→r前提引入⑥ ┐p③⑤拒取式⑦ q→s前提引入⑧ ┐q④⑦拒取式⑨ ┐p∧┐q⑥⑧合取⑩ ┐(p∨q)⑨置换口p∨q前提引入⑾①口┐(p∨q) ∧(p∨q) ⑩口合取17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。
(完整版)离散数学电子教材1(可编辑修改word版)
第1 章命题逻辑逻辑是研究人的思维的科学，包括辩证逻辑和形式逻辑。
辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。
形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。
数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。
所谓的数学方法也就是用一套有严格定义的符号，即建立一套形式语言来研究。
因此数理逻辑也称为符号逻辑。
数理逻辑的基础部分是命题逻辑和谓词逻辑。
本章主要讲述命题逻辑，谓词逻辑将在第2 章进行讨论。
1.1命题及其表示1.1.1命题的基本概念数理逻辑研究的中心问题是推理（Inference)，而推理就必然包含前提和结论，前提和结论都是表达判断的陈述句，因而表达判断的陈述句就成为推理的基本要素。
在数理逻辑中，将能够判断真假的陈述句称为命题。
因此命题就成为推理的基本单位。
在命题逻辑中，对命题的组成部分不再进一步细分。
定义1.1.1 能够判断真假的陈述句称为命题（Proposition）。
命题的判断结果称为命题的真值，常用T(True)（或1）表示真，F(False)（或0）表示假。
真值为真的命题称为真命题，真值为假的命题称为假命题。
从上述的定义可知，判定一个句子是否为命题要分为两步：一是判定是否为陈述句，二是能否判定真假，二者缺一不可。
例1.1.1 判断下列句子是否为命题（1）北京是中国的首都。
（2）请勿吸烟！（3）雪是黑的。
（4）明天开会吗？（5）x+y=5。
（6）我正在说谎。
（7）9+5≤12 。
（8）1+101=110 。
（9）今天天气多好啊！（10）别的星球上有生物。
解在上述的十个句子中，（2）、（9）为祈使句，（4）为疑问句，（5）、（6）虽然是陈述句，但（5）没有确定的真值，其真假随x、y 取值的不同而有改变，（6）是悖论(Paradox)（即由真能推出假，由假也能推出真），因而（2）、（4）、（5）、（6）、（9）均不是命题。
离散数学第一章 命题逻辑
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.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)
论(conclusion)或后件(consequent)。 “→”是一个二元运算。 条件联结词→的定义如表1.1.4
所示。
表1.1.4
第1章 命题逻辑
第1章 命题逻辑 5. 双条件联结词
定义1.1.6 如果 P和Q是命题， 那么“P当且仅当 Q” 是一个复合命题， 记做 P Q， 称为P和Q的双条件命题
表1.1.1
第1章 命题逻辑
第1章 命题逻辑
2. 合取联结词
定义1.1.3 如果 P和Q是命题， 那么“P并且Q”是一个 复合命题， 记做P∧Q， 称为P和Q 的合取(conjunction)。 符号∧用于表示合取联结词。 P∧Q 为T， 当且仅当P、 Q
均为T。 “∧”是一个二元运算符。 合取联结词∧的定义如表
第1章 命题逻辑
定义1.1.1 一个具有真或假但不能两者都是的断言称为 命题。
如果一个命题所表达的判断为真， 则称其真值(truth value)为“真”， 用大写字母T或数字1表示； 如果一个命题 所表达的判断为假， 则称其真值为“假”， 用大写字母F或 数字0表示。 为简便起见， 本书在构建真值表时一般用0表示 “假”， 用1表示“真”。
(biconditional proposition)。
词。 P Q为T， 当且仅当 P和Q 的真值相同。
1.1.5所示。
表1.1.5
第1章 命题逻辑
第1章 命题逻辑
1.2 命 题 公 式
1.2.1 命题公式及其符号化
定义1.2.1 用于代表取值为真(T、 1)或假(F、 0)之一 的变量， 称为命题变元， 通常用大写字母或带下标或上标的
大写字母表示， 如 P、 Q、 R、 P1、 P2等。 将T和F称为命
所示。
表1.1.4
第1章 命题逻辑
第1章 命题逻辑 5. 双条件联结词
定义1.1.6 如果 P和Q是命题， 那么“P当且仅当 Q” 是一个复合命题， 记做 P Q， 称为P和Q的双条件命题
表1.1.1
第1章 命题逻辑
第1章 命题逻辑
2. 合取联结词
定义1.1.3 如果 P和Q是命题， 那么“P并且Q”是一个 复合命题， 记做P∧Q， 称为P和Q 的合取(conjunction)。 符号∧用于表示合取联结词。 P∧Q 为T， 当且仅当P、 Q
均为T。 “∧”是一个二元运算符。 合取联结词∧的定义如表
第1章 命题逻辑
定义1.1.1 一个具有真或假但不能两者都是的断言称为 命题。
如果一个命题所表达的判断为真， 则称其真值(truth value)为“真”， 用大写字母T或数字1表示； 如果一个命题 所表达的判断为假， 则称其真值为“假”， 用大写字母F或 数字0表示。 为简便起见， 本书在构建真值表时一般用0表示 “假”， 用1表示“真”。
(biconditional proposition)。
词。 P Q为T， 当且仅当 P和Q 的真值相同。
1.1.5所示。
表1.1.5
第1章 命题逻辑
第1章 命题逻辑
1.2 命 题 公 式
1.2.1 命题公式及其符号化
定义1.2.1 用于代表取值为真(T、 1)或假(F、 0)之一 的变量， 称为命题变元， 通常用大写字母或带下标或上标的
大写字母表示， 如 P、 Q、 R、 P1、 P2等。 将T和F称为命
离散数学命题逻辑
Q）
(MQ) P（附加前提）
(2) SR
P
第一章命题逻辑
本题即证：M Q, MS, SR R→Q (3) RS T(2)E (4) S T(1)(3)I (5) MS P (6) M T(4)(5)I (7) (MQ) P (8) MQ T(7)E (9) (MQ)∧(QM) T(8)E (10) QM T(9)E (11) MQ T(10)E (12) Q T(6)(11)E (13) R→Q CP
第一章命题逻辑
请根据下面事实，找出凶手：
1. 清洁工或者秘书谋害了经理。 2. 如果清洁工谋害了经理，则谋害不会发生在午夜前。 3.如果秘书的证词是正确的，则谋害发生在午夜前。 4.如果秘书的证词不正确，则午夜时屋里灯光未灭。 5. 如果清洁工富裕，则他不会谋害经理。 6.经理有钱且清洁工不富裕。 7.午夜时屋里灯灭了。 令A:清洁工谋害了经理。 B:秘书谋害了经理。 C:谋害发生在午夜前。 D:秘书的证词是正确的. E:午夜时屋里灯光灭了。 H:清洁工富裕. G:经理有钱. 命题符号为： A∨B,AC,DC,DE,HA,G∧H,E ?
第一章命题逻辑
例题1-8.2 用命题逻辑推理方法证明下面推理的 有效性： 如果我学习，那么我数学不会不及格。如果我不 热衷于玩朴克，那么我将学习。但是我数学不 及格。因此，我热衷于玩朴克。 解 设 P：我学习。 Q：我数学及格。 R：我热衷于玩朴克。 于是符号化为： P→Q，R→P，Q R
1-8 推理理论
第一章得出一个新 的判断的思维过程。称这些已知的判断为前提。 得到的新的判断为前提的有效结论。 实际上，推理的过程就是证明永真蕴含式的过程， 即令H1，H2，…，Hn是已知的命题公式(前提)， 若有 H1∧H2∧....∧Hn C 则称C是H1，H2，…Hn的有效结论，简称结论。
离散数学
大家好
25
离散数学
区别：
真值表法是把所给前提一起使用；而直接证法则 是不断使用前提和前面推出的结论，构成推导序列， 是把前提一步一步拿来使用。
大家好
26
离散数学
证明：
(W∨R) →V ,V→C∨S, S→U, ┐C∧ ┐U ┐W
大家好
27
离散数学
二、证明方法
1. 真值表法 2. 直接证法 3. 间接证法
H1 ∧ H2 ∧ … ∧ Hn的真值均为F，则称公式H1，
H2，…，Hn是不相容大的家好。
29
离散数学
(2)证法
可以把不相容的概念应用于命题公式的证明。
设有一组前提H1，H2，…，Hn ，要推出结论C， 即证H1 ∧ H2 ∧ … ∧ Hn C，记作S C，即 ┐C→ ┐S为永真，或C∨┐S为永真，故┐C ∧S为永 假 。因此要证明H1 ∧ H2 ∧ … ∧ Hn C，只要证 明H1，H2，…，Hn与┐C是不相容的。类似于假定 ┐C为真，推出矛盾。
E19
E20
E21
大家好
E22
P→ (Q→R) (P∧Q) →R
P Q (P→Q) ∧(Q→P)
P Q (P∧Q) ∨(┐P∧ ┐Q)
19
┐(P Q) P ┐Q 离散数学
合取引入规则：任意两个命题公式A，B可以推出
A∧B
用直接推理法证明(p→q)∧(q→r)∧pr）
证明： ⑴ p→q
P
⑵p
P
⑶q
T⑴,⑵I（假言推理）
⑷ q→r
P
⑸r
T⑶,⑷I（假言推理）
大家好
20
离散数学
例题1 证明 (P∨Q) ∧(P→R)∧(Q→S) S∨R
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1∧(¬ q∨p)∧(1∨q)
1∧(¬ q∨p)∧1 (¬ q∨p)
(排中律)
(零律) (同一律，合取范式)
第1章 命题逻辑
⑵求析取范式 (p∨q)↔p ((p∨q)∧p)∨(¬ (p∨q)∧¬ p) p∨(¬ p∧ ¬ q∧¬ p)
A↔B (A∧B) ∨(¬ A∧¬ B) (消去↔) (吸收律) ←析取范式 ←析取范式
p∨q∨¬ r
p∨¬ q∨r
001
010
M1
M2
p∨¬ q∨¬ r
¬ p∨q∨r p∨q∨¬ r ¬ p∨¬ q∨r ¬ p∨¬ q∨¬ r 0
011
100 101 110 111
M3
M4 M5 M6 M7
Mi
M0∧M1∧…∧M
2n 1
第1章 命题逻辑
定义 1.5.8 对于给定的命题公式，如果有一个它的等价公式， 仅由极大项的合取组成，则该等价式称为原公式的主合取范 式。 任何命题公式都存在着与之等价的主合取范式。主合取 范式也可以由以下两种方法求得。 ⑴等价演算法：即用基本等价公式推出。 其演算步骤如下： ①化归为合取范式。 ②除去所有永真的基本和。 ③在基本和中合并重复出现的析取项和相同的变元。 ④在基本和中补入没有出现的命题变元。即增加 ∨ ( x∧ ¬ x)，然后，应用分配律展开公式，最后合并相同的 极大项。
2 n 1 i0
mi m0∨m1∨…∨ m2 1 1
n
定义1.5.6 对于给定的命题公式，如果有一个它的等价公式， 仅由极小项的析取组成，称该公式为原公式的主析取范式。 任何命题公式都存在着与之等价的主析取范式。一个 命题公式的主析取范式可以由以下两种方法求得： ⑴等价演算法：即用基本等价公式推出。
第1章 命题逻辑
极大项有下列三个性质： ⑴ 每个极大项只有一个成假赋值，极大项不同，成假赋 值也不同。极大项和它的成假赋值构成了一一对应的关系。 故可用成假赋值为该极大项进行编码，并把编码作为M的下 标来表示该极大项，叫做极大项的名称。 例如，两个变元p，q的极大项¬ p∨ ¬ q，它的成假赋值是11， 表示为 M11 ，把 11理解为 2 进制数，它的 10 进制表示为 3 ，所 以M 11又表示为M3。 表1.16 两个命题变元的极大项， 成假赋值及名称见表1.16， 三个命题变元的极大项， 成假赋值及名称见表1.17。 极大项 p∨q p∨ ¬ q 成假赋值 00 01 名称 M0 M1
析取范式和合取范式的基本成分是基本积和基 本和，而主析取范式和主合取范式的基本成分是极 小项和极大项，它们分别是特殊的基本积和基本和。
第1章 命题逻辑
定义1.5.5在基本积中，每个变元及其否定不同时存在，但两 者之一必须出现且仅出现一次，这样的基本积叫做布尔合取 也叫小项或极小项。 p，q的极小项为：p∧q，p∧¬ q，¬ p∧q，¬ p∧¬ q 两个命题变元的极小项共4(=22)个, 三个命题变元的极小 项共8(=23)个, …。一般地说，n个命题变元共有2n个极小项。 表1.12是两个变元p和q的极小项的真值表。极小项有下列的 性质： 表1.12 p 0 0 1 1 q 0 1 0 1 p∧q 0 0 0 1 p∧ ¬ q 0 0 1 0 ¬ p∧q 0 1 0 0 ¬ p∧¬ q 1 0 0 0
M000∧M010∧M110M0∧M2∧M6∏0，2，6
第1章 命题逻辑
⑵ 真值表法：用真值表求主合取范式。 用真值表求主合取范式的步骤如下： ①构造命题公式的真值表。 ②找出公式的成假赋值对应的极大项。 ③这些极大项的合取就是此公式的主合取范式。 【例1.26】用真值表法求(p→q)→r的主合取范式。 解：(p→q)→r的真值表是表1.15。公式的成假赋值对 应的大项为： p∨q∨r (成假赋值为000) p∨¬ q∨r (成假赋值为010) ¬ p∨¬ q∨r (成假赋值为110) 主合取范式为：(p∨q∨r)∧(p∨¬ q∨r)∧(¬ p∨¬ q∨r) M000∧M010∧M110M0∧M2∧M6∏0，2，6
((p∨q)∧p)∨((¬ p∧¬ q)∧¬ p) (内移) p∨(¬ p∧¬ p∧¬ q)
p∨(¬ p∧¬ q)
(交换律)
(幂等律，析取范式)
由此例可以看出，命题公式的析取范式也.2主析取范式 由于析取范式和合取范式不惟一，所以使用起 来很不方便。为此，引入主析取范式和主合取范式 的概念。当命题变元的顺序约定以后，主析取范式 和主合取范式是惟一的。
p∧¬ q
p∧q
10
11
m2
m3
三个命题变元的极小项，成真赋值和名称如表1.14所示。
第1章 命题逻辑
表1.14 极小项 ¬ p∧ ¬ q∧¬ r ¬ p∧¬ q∧r ¬ p∧q∧¬ r ¬ p∧q∧r p∧ ¬ q∧¬ r p∧ ¬ q∧r 成真赋值 000 001 010 011 100 101 名称 m0 m1 m2 m3 m4 m5
第1章 命题逻辑
【例1.24】用真值表法，求(p→q)→r的主析取范式。 解：表1.15是(p→q)→r的真值表，公式的成真赋 值对应的极小项为： ¬ p∧¬ q∧r (成真赋值为001) ¬ p∧q∧r (成真赋值为011) p∧¬ q∧¬ r (成真赋值为100) p∧¬ q∧r (成真赋值为101) p∧q∧r (成真赋值为111) (p→q)→r 的主析取范式为： (¬ p∧¬ q∧r)∨(¬ p∧q∧r)∨(p∧¬ q∧¬ r)∨(p∧¬ q∧r)∨ (p∧q∧r) m001∨m011∨m100∨m101∨m111 m1∨m3∨m4∨m5∨m7 ∑1，3，4，5，7
第1章 命题逻辑
【例1.25】用等价演算法求(p→q)→r的主合取范式。 解：(p→q)→r
¬ (¬ p∨q)∨r(p∧¬ q)∨r(p∨r)∧(¬ q∨r) (p∨r∨(q∧¬ q))∧(¬ q∨r∨(p∧¬ p)) (p∨r∨q)∧(p∨r∨¬ q)∧(p∨¬ q∨r)∧(¬ p∨¬ q∨r) (p∨q∨r)∧(p∨¬ q∨r)∧(¬ p∨¬ q∨r)
第1章 命题逻辑
⑴每个极小项只有一个成真赋值，且各极小项的成真赋值互 不相同。极小项和它的成真赋值构成了一一对应的关系。可 用成真赋值为极小项进行编码，并把编码作为m的下标来表 示该极小项，叫做该极小项的名称。 两个命题变元的极小项、成真赋值和名称如表1.13所示。 表1.13 极小项 ¬ p∧¬ q ¬ p∧q 成真赋值 00 01 名称 m0 m1
第1章 命题逻辑
矛盾式无成真赋值，因而矛盾式的主合取范式含2n (n为 公式中命题变元的个数)个极大项。而重言式无成假赋值， 因而主合取范式不含任何极大项。将重言式的主合取范式记 为1。至于可满足式，它的主合取范式中极大项的个数一定 小于2n 。
第1章 命题逻辑
在例1.23和例1.24中求出(p→q)→r的主析取范式为： m7∨m5∨m4∨m3∨m1∑1，3，4，5，7 在例1.25和例1.26中求出该公式的主合取范式为： M0∧M2∧M6∏0，2，6 比较这两个结果，得出以下的结论: 同一公式的主析取范式中m的下标和主合取范式中M的 下标是互补的。因此，知道了主析(合)取范式就可以写出主 合(析)取范式。
第1章 命题逻辑
定义1.5.3由基本和的合取构成的公式叫做合取范式。约定单 个基本和是合取范式。 定义1.5.4由基本积的析取构成的公式叫做析取范式。约定单 个基本积是析取范式。 1)基本和和基本积既是析取范式，又是合取范式。 2)析取范式和合取范式都仅含联结词¬ ,∧,∨。
第1章 命题逻辑
任何命题公式都可以化成与其等价的析取范式或合取
¬ p∨q
¬ p∨¬ q
10
11
M2
M3
第1章 命题逻辑
从表1.16和表1.17中 可以看出，极大项与 成假赋值的对应关系 为：变元对应0，而变 元的否定对应1。 ⑵任意两个不同的极 大项的析取式为永真式 ⑶全体极大项的合取式 为永假式。记为：
2 n 1 i 0
表1.17
极大项 p∨q∨r 成假赋值 000 名称 M0
范式。求析取范式和合取范式的步骤如下：
⑴ 消去联结词“→”和“↔”
⑵利用双重否定律消去否定联结词“¬ ”或利用德摩根律 将否定联结词“¬ ”移到各命题变元前(¬ 内移)。
⑶利用分配律，结合律将公式归约为合取范式和析取范式。
第1章 命题逻辑
【例1.21】求命题公式(p∨q)↔p的合取范式和析取范式。 解：⑴求合取范式 (p∨q)↔p ((p∨q)→p)∧(p→(p∨q)) (消去↔) (¬ (p∨q)∨p)∧(¬ p∨(p∨q)) (消去→) ←合取范式 ((¬ p∧¬ q)∨p)∧(¬ p∨(p∨q)) (内移) (¬ p∨p)∧(¬ q∨p)∧(¬ p∨p∨q) (分配律)
第1章 命题逻辑
用等价演算法求主析取范式的步骤如下： ①化归为析取范式。 ②除去析取范式中所有永假的基本积。 ③在基本积中，将重复出现的合取项和相同变元合并。 ④在基本积中补入没有出现的命题变元，即添加∧(x∨¬ x)， 再用分配律展开，最后合并相同的极小项。 例1.22 用等价演算法求(p∧q)∨(¬ p∧r)∨(q∧r)的主析取范式。 解：(p∧q)∨(¬ p∧r)∨(q∧r) (p∧q∧(r∨¬ r))∨(¬ p∧r∧(q∨¬ q))∨(q∧r∧(p∨¬ 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)∨(¬ p∧q∧r)∨(¬ p∧¬ q∧r) m111∨m110∨m011∨m001 m7∨m6∨m3∨m1∑1，3，6，7
第1章 命题逻辑
矛盾式、重言式、可满足式主析取范式的性质
①矛盾式无成真赋值， 因而其主析取范式不含任何极小项， 将矛盾式的主析取范式记为0。 ②重言式无成假赋值， 因而主析取范式含2n (n为公式中命题变 元的个数)个极小项。 ③可满足式的主析取范式中极小项的个数一定小于等于2n。