第1章 逻辑代数(上)：命题演算.doc

第1章 逻辑代数（上）：命题演算1.1 逻辑联结词与命题公式1.1.1 逻辑联结词否定词(negation)“并非”(not)，用符号 Ø （或 ）表示。设p表示一命题，那么Øp表示命题p的否定。当p真时Øp假，而当p假时Øp真。Øp读作“并非p”或“非p”。用类似表1.1的真值表(truth table)规定联结词的意义。表1.1 p Øp 0 1 1 0 合取词(conjunction)“并且”(and)，用符号表示。设p，q表示两命题，那么pq表示合取p和q所得的命题，即当p和q同时为真时pq真，否则pq为假。pq读作“p并且q”或“p且q”。合取词的意义和命题pq的真值状况可由表1.2来刻划。表1.2 p q pq001101010001 析取词(disjunction)“或”(or)用符号表示。设p，q表示两命题，那么pq表示p和q的析取，即当p和q有一为真时，pq为真，只有当p和q均假时pq为假。pq读作“p或者q”，“p或q”。析取词的意义及复合命题pq的真值状况由表1.3描述。表1.3 p q pq001101010111蕴涵词(implication)“如果，那么”(ifthen)，用符号表示。设p，q表示两命题，那么pq表示命题“如果p，那么q”，它常被称作条件命题。当p真而q假时，命题pq为假，否则均认为pq为真。pq中的p称为蕴涵前件，q称为蕴涵后件。pq的读法较多，可读作“如果p则q”，“p蕴涵q”，“p是q的充分条件”，“q是p的必要条件”，“q当p”，“p仅当q”等等。数学中还常把qp，ØpØq，ØqØp分别叫做pq的逆命题，否命题，逆否命题。蕴涵词的意义及复合命题pq的真值状况规定见表1.4。 表1.4pqpq001101011101 双向蕴涵词(two-way implication)“当且仅当”（if and only if），用符号«表示之。设p，q为两命题，那么p«q表示命题“p当且仅当q”，“p与q等价”，即当p与q同真值时p«q为真，否则为假。p«q读作“p双向蕴涵q”，“p当且仅当q”，“p等价于q”。由于“当且仅当”“等价”常在其它地方使用，因而用第一种读法更好些。双向蕴涵词的意义及p«q的真值状况由表1.5给出。表1.5 p q p«q0011010110011.1.2 命题公式 定义1.1 归纳定义命题公式（简称公式proposition formula）： （1）命题常元和命题变元是命题公式，也称为原子公式或原子。 （2）如果A，B是命题公式，那么(ØA)，(AB)，(AB)，(AB)，(A«B)也是命题公式。 （3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。定义1.2设公式A含有命题变元p1，p2，pn（有时用A(p1，p2，pn)表示这一状况），称p1，p2，pn每一取值状况为一个指派(assignments)，用希腊字母a，b等表示，当A对取值状况 a 为真时，称指派a弄真A，或a是A的弄真指派，记为a(A) = 1；反之称指派a弄假A，或a是A的弄假指派，记为a(A) = 0。1.1.3 语句形式化 将自然语言表述的命题“翻译”成命题公式，常称为语句形式化。语句形式化要注意以下几个方面：l 要善于确定原子命题，不要把一个概念硬拆成几个概念，例如“弟兄”是一个概念，不要拆成“弟”和“兄”、“我和他是弟兄”是一个原子命题。l 要注意语句的语用，不同的语用有不同的逻辑含义。例如“狗急跳墙”可能说的是一个规律，也可能说的是一个现象。l 要善于识别自然语言中的联结词（有时它们被省略）。例如“风雨无阻，我去北京”一句，可理解为“不管是否刮风、是否下雨我都去北京”。l 否定词的位置要放准确。l 需要的括号不能省略；而可以省略的括号，在需要提高公式可读性时亦可不省略。l 注意“只要¼，就¼”“只有¼，才¼”的正确理解。因果关系也常常用蕴涵词来表示，这一点是有争议的。l 语句的形式化的结果未必是唯一的。 练习1.1题解1、选择题（1）设P:我将去镇上，Q:我有时间。命题“我将去镇上，仅当我有时间”符号化为（ ）APQ ； B. QP ； C. PQ ； D. QP.。【答案】：A（2）设P:张三可以做这件事，Q李四可以做这件事。命题“张三或李四可以做这件事”符号化为（ ）APQ ； B.PQ； C. PQ ； D. (PQ)【答案】：A（3）设P:我们划船，Q:我们跑步。命题“我们不能既划船又跑步”符号化为（ ）APQ ； B.PQ ； C.(PQ)； D. PQ【答案】：B（4）下列语句中哪个是真命题（ ）A我正在说谎B. 如果1+2=3，那么雪是黑的C. 如果1+2=5，那么雪是黑的D. 严禁吸烟【答案】：C（5）PQ的逆命题是（ ）A .QP B. PQ C.QP D.PQ【答案】：A（6）下面哪一个命题是命题“2是偶数或-3是负数”的否定（ ）A2是偶数或-3不是负数B. 2是奇数或-3不是负数C. 2不是偶数且-3不是负数D. 2是奇数且-3不是负数【答案】：C2、填空题（1）下列句子中，是命题的有 .（a）我是教师。（b）禁止吸烟。（c）蚊子是鸟类动物。（d）上课去！【答案】：（a），（c）（2）设P：我生病，Q：我去学校（a）命题“我虽然生病但我仍去学校”可符号化为 。（b）命题“只有我生病的时候，我才不去学校” 可符号化为 。（c）命题“只要我生病，我就不去学校” 可符号化为 。（d）命题“当且仅当我生病，我才不去学校” 可符号化为 。【答案】：（a）PQ；（b）.QP；（c）PQ；（d）PQ（3）“a0”表示a>0 a=0 ；“a是非负实数”表示a0 a是实数（在空格中填上适当的命题联结词）。【答案】：；（4）在空格中填上表（表1.6）各列所定义的命题联结词： 表1.6P Q P QP Q0 0110 1101 0001 111【答案】：；（5）P，Q为两个命题，当且仅当 时，PQ的真值为0。【答案】：P真且Q假（6）公式PQ的否命题为 ，逆否命题为 。【答案】：PQ； QP3将下列命题形式化：（1）你是博士，但我是硕士。【答案】：可表示为 (pq)， 其中p：你是博士；q：我是硕士（2）我今天或明天去泰山的说法是谣传。【答案】：可表示为Ø (pq)，其中p：我今天去泰山；q：我明天去泰山（3）如果买不到飞机票，我不去海南岛。【答案】：可表示为ØpØq，其中，p：我买到飞机票，q：我去海南岛（4）只要他出门，他必买书，不管他带的钱多不多。【答案】：可表示为(pqr)(Øpqr)或qr，其中p：他带的钱多，q：他出门，r：他买书。（5）除非你陪伴我或代我雇辆车子，否则我不去。【答案】：可表示为(pq) r，其中p：你陪伴我，q：你代我雇车，r：我去（6）只要充分考虑一切论证，就可得到正确见解；必须充分考虑一切论证，才能得到正确见解。【答案】：可表示为(pq) (qp )或p« q，其中p：你充分考虑了一切论证，q：你得到了正确见解（7） 除非你是成年人，否则只要你身高不超过1米3，就能到儿童游乐场玩耍。 Ø r (Øst)，其中r：你是成年人，s：你身高超过1米3，t: 你到儿童游乐场玩耍（8）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。【答案】：可表示为(qp ) Øq，其中p：我懂得希腊文，q：我了解柏拉图（9）侈而惰者贫，而力而俭者富。（韩非：韩非子·显学）【答案】：可表示为(pq)r) (ØpØq)Ør)，其中p：你奢侈，q：你懒惰，r：你贫困（10）骐骥一跃，不能十步；驽马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金石可镂。（荀况：荀子·劝学）【答案】：可表示为(pØq) (sr) (mnØo) (mØnv)，其中p：骐骥一跃，q：骐骥行十步，r：驽马行千里，s：驽马不断奔跑，m：你雕刻，n：你放弃，o：你将朽木折断，v：你将金石雕刻4根据命题公式的定义和括号省略的约定，判定下列符号串是否为公式，若是，请给出它的真值表，并请注意这些真值表的特点（p,q,r,s为原子命题）：（1）Ø (p) 【答案】：Ø (p) 不是公式（2）(pqr)s【答案】：(pqr)s 不是公式（3）(pq)p【答案】：(pq)p 是公式，其真值表如表1.7所示：表1.7pqpq(pq)p0001011010111111（4）p(pq)【答案】：p(pq) 是公式，其真值表如表1.8所示（恒真）：表1.8pqpqp(pq)0001011110111111（5）p(pq)q【答案】：p(pq)q 是公式，其真值表如表1.9所示（恒真）：表1.9pqpqp(pq)p(pq)q00101011011000111111（6）p(pq)(pØq)【答案】：p(pq)(pØq) 是公式，其真值表如表1.10所示（恒假）：表1.10pqqpqp(pq)pqp(pq)(pØq)0011010010101010100101101100（7）Ø (pq) «ØqØp【答案】：Ø (pq) «ØqØp 是公式，其真值表如表1.11所示（恒真）：表1.11pqØ pØ qpqØ (pq)ØqØp(pq) « (Ø qØ p)00110111011010011001100111001001（8）Ø pq« (pq)【答案】：Ø pq«(pq) 是公式，其真值表如表1.12所示（恒真）：表1.12pqØpØpqpqØpq« (pq)001111011111100001110111（9）(pq)(qr)(p r )【答案】：(pq)(qr)(pr) 是公式，其真值表如表1.13所示（恒真）：表1.13pqrpqqrpr(pq)(qr)(pq)(qr)(pr)0001111100111111010101010111111110001001101011011101000111111111（10）(pqr) « (pr)(qr)【答案】：(pqr) « (pr)(qr) 是公式，其真值表如表1.14所示（恒真）：表1.14pqrpqpqrprqr(pr)(qr)(pqr)« (pr)(qr)0000111110010111110101010010111111111001001011011111111101010011111111115给出弄真下列命题公式的指派：（1）(pq)q)p【答案】：弄真指派有(0,0)，(0,1)，(1,0)（2）(pq)r)(qp)r)【答案】：弄真指派有(0,0,0)，(0,0,1)，(0,1,0)，(0,1,1)，(1,0,1)，(1,1,0)，(1,1,1)（3）(p«q)r)(qp) «r)【答案】：弄真指派有(0,0,0)，(0,0,1)，(0,1,0)， (1,0,1)，(1,1,0)，(1,1,1)（4）Ø (pq)r)(rp)【答案】：弄真指派有(0,0,0)，(0,1,0)， (0,1,1)，(1,0,0)，(1,0,1)，(1,1,0)，(1,1,1)1.2 逻辑等价式和逻辑蕴涵式1.2.1 重言式定义1.3 如果对命题公式A中命题变元的一切指派均弄真A，那么，称A为重言式(tautology)；重言式又称永真式；如果至少有一个这样的指派弄真A，那么，称A为可满足式(satisfactable formula)，否则称A为不可满足式或永假式、矛盾式。 1.2.2 逻辑等价式和逻辑蕴涵式 定义1.4 当命题公式A«B为永真式时，称A逻辑等价于B，记为AB，它又称为逻辑等价式(logically equivalent)。 以下是一些重要的逻辑等价式，其中A，B，C表示任意命题公式：E1 ØØAA 双重否定律E2 AAA ，AAA 幂等律E3 ABBA ，ABBA 交换律E4 (AB)CA(BC) 结合律 (AB)CA(BC) E5 A(BC)(AB)(AC) 分配律 A(BC)(AB)(AC) E6 Ø (AB)ØAØB 德摩根律 Ø (AB)ØAØB E7 A(AB)A 吸收律 A(AB)A E8 ABØAB E9 A« B(AB)(BA)E10 Att ， AffE11 AfA ， AtAE12 AØAt ，AØAf E13 Øtf, ØftE14 ABCA(BC)E15 ABC(AC)(BC)E16 ABØBØAE17 (AB)(AØB)ØAE18 A« B(AB)(ØAØB) 定义1.5 当命题公式AB为永真式时，称A逻辑蕴涵B，记为A B，它又称为逻辑蕴涵式(logically implication)。 一些十分重要的逻辑蕴涵式： I1 A AB，B ABI2 AB A，AB BI3 BABI4 A(AB) BI5 (AB)ØBØAI6 ØA(AB) B，ØB(AB) AI7 (AB)(BC) ACI8 (AB)(CD) (AC)(BD)I9 (A«B)(B«C) A«CI10 A t ； f A 逻辑等价式与逻辑蕴涵式有如下明显性质。 定理1.1 对任意命题公式A，B，C，A'，B'， （1）AB当且仅当 A«B （2）A B当且仅当 AB （3）若AB，则BA （4）若AB，BC，则AC （5）若A B，则B A （6）若A B，B C，则A C （7）若A B，AA'，BB'，则A' B' 定理1.2 设A为永真式，p为A中命题变元，A(B/p)表示将A中p的所有出现全部代换为公式B后所得的命题公式（称为A的一个代入实例），那么A(B/p)亦为永真式。 定理1.2常被称为代入原理(rule of substitution)，简记为RS 定理1.3 设A为一命题公式，C为A的子公式，且CD。若将A中子公式C的某些（未必全部）出现替换为D后得到的公式记为B，那么AB。 定理1.3常被称为替换原理(rule of replacement)简记为RR。 请注意RS与RR的区别，详见表1.15。表1.15代入原理 RS替换原理 RR使用对象任意永真式任一命题公式被代换对象任一命题变元任一子公式代换对象任一命题公式任一与代换对象等价的命题公式代换方式代换同一命题变元的所有出现代换子公式的某些出现代换结果仍为永真式与原公式等价 当然，证明逻辑蕴涵式A B不成立的方法只有一个，那就是：找出一个指派使得A为真，却使 B为假。证明逻辑等价式AB不成立的方法是：证明A B不成立或者证明BA不成立。推而广之，为证 G B（G 为公式集合）不成立，只要找出一个指派使得G中所有公式为真，却使B为假。1.2.3 对偶原理 定义1.6 设公式A仅含联结词 Ø，A*为将A中符号，t，f分别改换为，f，t后所得的公式，那么称A*为A的对偶(dual)。 下面两定理所描述的事实常称为对偶原理。定理1.4 设公式A中仅含命题变元p1,pn，及联结词Ø，那么 AØA* (Øp1p1，Øpnpn) 这里，A* (Øp1p1，Øpnpn)表示在A*中对p1,pn分别作代入Øp1, Øpn后所得的公式。定理1.5 设A，B为仅含联结词Ø，和命题变元p1,pn的命题公式，且满足AB，那么有B* A*。进而当AB时有A*B*。定义1.7 B* A*，A*B*分别称为A B和AB的对偶式。1.2.4 应用逻辑命题逻辑的相关知识，特别是逻辑等价式和逻辑蕴含式所反映的逻辑思维规律，如，排中律、矛盾律、双重否定律、德摩根律等，是人们逻辑推理的基础，在逻辑训练和实际生活中有十分广泛的应用。练习1.2题解1选择题（1）K是重言式，那么K的否定是（ ）A.重言式 B.矛盾式 C.可满足式 D. 不能确定【答案】：B（2）K不是重言式，那么它是（ ）A.永假式 B.矛盾式 C.可满足式 D.不能确定【答案】：C（3）命题公式(P(PQ) Q是（ ）A矛盾式B. 可满足式 C. 重言式 D. 不能确定【答案】：C（4）命题公式(P(ØPQ) Q是（ ）A矛盾式B. 可满足式 C. 重言式 D. 不能确定【答案】：B（5）如果PQ为真时我们称命题P强于Q，那么最强的命题是（ ），最弱的命题是（ ）。A永假式B. 可满足式 C. 永真式 D. 不能确定【答案】：A，C2填空题（1）两个重言式的析取是 ，一个重言式与一个矛盾式的析取是 。两个重言式的合取是 ，一个重言式与一个矛盾式的合取是 。一个重言式蕴涵一个矛盾式的是 ，一个矛盾式蕴涵一个重言式的是 。【答案】：重言式，重言式，重言式，矛盾式，矛盾式，重言式（2）在下列各式中，是永真式的有 。（a）(P(PQ) Q（b）P(PQ)（c）Q(PQ)（d）(P(PQ)Q（e）(PQ)Q【答案】：(a)，（b），（d）（3）化简下列各式：（a）(PQ) (PQ)可化简为 。（b）Q(P(PQ)可化简为 。（c）(PQ)(QP)P可化简为 。【答案】：（a）P；（b）QP；（c）P（4）公式(PQ)R的只含联结词，的等价式为 ，它的对偶式为 。【答案】：(PQ)R)；(PQ) R3试判定以下各式是否为重言式：（1）(pq)(qp)【答案】：否（2）p(pq)【答案】：是（3）q(pq)【答案】：是（4）pq(p«q)【答案】：是（5）(pq)(rq)(pr)q)【答案】：否（6）(pq)(rs)(pr)(qs)【答案】：否4试用真值表验证E6，E8，E15，E17。（1）【答案】： E6 (AB)AB的真值表如表1.16所示：表1.16ABAB(AB)ABAB(AB) «AB00011111011010011010010111100001(AB)AB的真值表如表1.17所示：表1.17ABAB(AB)ABAB(AB) «AB00011111010110111001011111100001（2）【答案】： E8 ABAB的真值表如表1.18所示：表1.18ABABAABAB«AB001111011111100001111011（3）【答案】：E15 ABC(AC)(BC) 的真值表如表1.19所示：表1.19ABCABABCACBC(AC)(BC)(ABC)«(AC)(BC)000011111001011111010101001011111111100100001101111111110100001111111111（4）【答案】：E17 (AB)(AØB)ØA的真值表如表1.20所示：表1.20ABABAØB(AB)(AØB)ØA (AB)(AØB) «ØA00111110111111100100111100015不用真值表，用代入、替换原理证明E16，E17。（1）E16 ABØBØA【答案】： ABAB 据E8A (B) 据E1用RR ØBØA 对E8用RS（2）E17 (AB)(AB)A【答案】：(AB)(AB)(AB) (AB) 据E8用RR A (BB) 对E5用RS Af 据E12用RR A 据E11用RS6试用真值表验证I3，I4，I6，I7。（1）【答案】： I3 BAB的真值表如表1.21所示：表1.21ABABB(AB) 0011011110011111（2）【答案】：I4 A (AB)B的真值表如表1.22所示：表1.22ABABA (AB)A (AB) B 00101011011000111111（3）【答案】：I6 A(AB) B 的真值表如表1.23所示：表1.23ABAABA(AB)A(AB)B001001011111100101110101B(AB) A的真值表如表1.24所示：表1.24ABBABB(AB)B(AB)A001001010101101111110101（4）【答案】：I7 (AB) (BC) (AC) 的真值表如表1.25所示：表1.25ABCABBCAC(AB)(BC)I700011111001111110101010101111111100010011010110111010001111111117不用真值表，用代入、替换原理证明I8，I9 。【答案】：（1）I8：(AB)(CD) (AC)(BD) 证 (AB)(CD) (AC) (AB)(CD) (AC) (ACAC) (BCAC) (ADAC) (BDAC)fff(ABCD)ABCDBD因此，(AB)(CD) (AC) (BD)为一重言式又(AB)(CD) (AC) (BD) (AB)(CD) (AC) (BD)所以(AB)(CD) (AC) (BD) 为一重言式即(AB)(CD) (AC)(BD)【答案】：（2）I9：(A«B)(B«C) (A«C) 证 (A«B)(B«C)A (AB)(BA)(BC)(CB)A (AB)(BC)A(AB) (BC) A(ABA) (ACA) (BBA) (BCA)fff(ABC)ABC C因此，(A«B)(B«C)A C为一重言式又(A«B)(B«C)A C (A«B)(B«C)(A C)所以(A«B)(B«C)(A C) 为一重言式仿上可证(A«B)(B«C)(C A) 为一重言式又根据（1），(A«B)(B«C)(A C) (A«B)(B«C)(C A)(A«B)(B«C) (A C) (C A)(A«B)(B«C) (A«C)所以(A«B)(B«C) (A«C)也是重言式，即(A«B)(B«C) (A«C)8用三种不同方法证明下列逻辑等价式和逻辑蕴涵式： （1）A«B(AB)(AB)【答案】证法1：真值表（表1.26）的最后两列等值，故A«B(AB)(AB)表1.26ABABABABA«B(AB)(AB)00011111010100001000100011100011 证法2：A«B(AB)(BA) (AB)(BA) (AB)(AA)(BB)(BA) (AB)(AB) 证法3： 先证A«B (AB)(AB) (a) 设a为任一指派，使(A«B)=1，那么a (A)= a (B)=1或a(A)= a (B)=0，从而a (AB)=1或a (AB)=1，即a (AB)(AB)=1。(a)得证；再证(AB)(AB) A«B (b)设a为任一指派，使a (A«B)=0，那么a (A)=1，a(B)=0，或者a(A)=0，aa(B)=1，从而a(AB)=0且a (AB)=0，即a (AB)(AB)=0。(b)得证。（2）A(BC)B(AC)【答案】证法1：真值表（表1.27）的最后两列等值，故A(BC)B(AC)表1.27ABCBCACA(BC)B(AC)00011110011111010011101111111001011101111111000001111111 证法2：A(BC)A(BC) (AB)C (BA)C B(AC) B(AC) 证法3：先证A(BC) B(AC) (a)设a为任一指派，使a (A(BC)=1，那么）a (A)= 0，则a ( AC)=1，从而a ( B(AC)=1）a (A)= 1，a (B)=0，则a ( B(AC)=1）a (A)= a (B)=a (C)=1，则a ( B(AC)=1综上，(a)得证；同理可证B(AC) A(BC)。（3）A(AB)AB【答案】证法1：真值表（表1.28）的最后两列等值，故A(AB)AB表1.28ABABA(AB)0011011110001111 证法2：A(AB)AAB AB 证法3：先证A(AB) AB (a) 设a为任一指派，使a( AB)=0，那么a (A)=1，a(B)=0，从而a ( A(AB)=0。(a)得证；再证AB A(AB) (b)设a为任一指派，使a (A(AB)=0，那么a (A)=1，a (AB)=0。(b)得证。（4）A(BC)(AB)(AC)【答案】证法1：真值表（表1.29）的最后两列等值，故A(BC)(AB)(AC)表1.29ABCBCABACA(BC)(AB)(AC)0001111100111111010011110111111110010011101101111100100011111111 证