离散数学：第一章 命题逻辑

离散数学

DiscreteMathematics2离散数学的特点离散数学是现代数学的一个重要分支，是计算机科学基础理论的核心课程。1976年美国IEEE计算机协会典型课程分委员会把离散数学列为计算机科学中专业基础理论的核心课程。又称计算机数学。离散数学有别于一般的工程数学。传统的数学分析、微分方程、复变函数、泛函分析等课程以连续变量作为研究对象。离散数学是以研究各种各样的离散量的结构及离散量之间的关系为主要研究目标。研究对象一般是有限个或可数个元素。这充分描述了计算机科学离散性的特点。3离散数学把计算机科学中所涉及到的研究离散量的数学综合在一起，为研究计算机科学的相关问题提供了有力的数学工具。换句话说，离散数学在计算机科学中起到了工具性的作用，等同于高等数学在其他工程技术科学中的作用。离散数学的产生对计算机科学的发展具有重大影响和推动作用，而计算机科学的发展又不断地充实和丰富了离散数学的内容。特别是在被誉为计算机科学时代的今天，离散数学以它独特的魅力为越来越多的人们所瞩目，并已经成为了计算机科学工作者、应用计算机的工程技术人员以及信息科学工作者等必备的数学工具之一。离散数学是数学工具4离散数学的任务通过离散数学知识的学习和训练，一方面可以帮助学生掌握证明问题的方法，培养抽象思维的能力、符号演算和慎密概括的能力以及严密的逻辑推理的能力。另一方面使学生具有良好的专业理论素质，有益于培养学生严谨、完整、规范的科学态度，提高学生分析和解决实际问题的能力，为将来参与创新性的研究和开发工作打下坚实的基础。通过离散数学的学习，可以掌握处理离散结构的描述工具和方法，为后续课程（如数据结构、编译理论、操作系统、数字逻辑理论、密码学基础、逻辑程序设计、数据库原理、人工智能等）的学习创造条件，打下坚实的理论基础。5离散数学是建立在大量定义、定理之上的逻辑推理学科，因此对概念的理解是学习这门课程的核心。学习概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体是大量的定理和性质。因此，深入地理解和掌握离散数学的基本概念、基本定理和结论，是学好离散数学的重要前提之一。离散数学的基本概念、思想方法，大量地应用到逻辑电路、编译原理、数据结构、操作系统、人工智能、数据库原理等计算机科学专业课程。这些课程都要用到集合、关系、代数系统、图的理论等基本概念进行描述。离散数学课程学习的特点6离散数学的内容：

数理逻辑（MathematicsLogic)

集合论(Sets)

组合论（Combination)

图论（GraphTheory)

代数结构（AlgbraStructure)7教学内容：数理逻辑集合论图论代数系统谓词逻辑集合关系图的基本概念几个特殊图代数系统的基本概念特殊代数系统离散数学函数图的连通性代数系统的基本概念特殊代数系统代数系统的基本概念命题逻辑代数系统的同态与同构8逻辑学（Logic）

逻辑学是研究人的思维形式结构和规律的科学。由于研究对象和方法各有侧重而又分为辩证逻辑、形式逻辑和数理逻辑。辩证逻辑：以辩证法认识论的世界观为基础的逻辑学。形式逻辑：主要对人的思维形式结构和规律进行研究的类似于语法的一门工具性学科。思维的形式结构包括概念、判断和推理之间的结构和联系，其中概念是思维的基本单位，通过概念对事物是否具有某种属性进行肯定或否定的回答就是判断；由一个或者几个判断推出另一个判断的思维形式就是推理。

数理逻辑：用数学方法研究推理，是研究推理中前提和结论之间的形式关系的科学，又称其为符号逻辑。9数理逻辑数理逻辑包括命题逻辑和谓词逻辑。为了研究形式逻辑中的推理规律，数学家为其设计了一套表意符号体系，用人工符号来书写逻辑法则，使形式逻辑数学化。莱布尼兹是数理逻辑的首席创始人，力主“思维计算化”正是应用了一整套数学符号组成的形式系统来研究逻辑问题，才使得逻辑学有了脱胎换骨的进步，具备表达简洁、推理严谨、易于分析等优点。音乐里有简谱和五线谱等人工符号，记录音乐中音韵的节律和高低；化学中用分子式和反应方程等人工符号记录物质的分子结构和反应过程。解:逻辑学家手指一门问身旁一名战士甲说：“这扇门是死亡门，他(指另一名战士乙)将回答‘是’，对吗？”

当被问战士甲回答“对”，则逻辑学家开启所指的门从容离去。

当被问战士甲回答“否”，则逻辑学家开启另一门从容离去。例子：有一个逻辑学家误入某部落，被拘于牢狱，酋长意欲放行，他对逻辑学家说：“今有两门，一为自由，一为死亡，你可任意开启一门。为协助你脱逃，现今加派两名战士负责解答你所提的任何问题。惟可虑者，此两战士中一名天性诚实，一名说谎成性，今后生死由你自己选择。”逻辑学家沉思片刻，即向一战士发问，然后开门从容离去。该逻辑学家应如何发问？设P：被问战士甲是诚实人。

Q

：被问战士甲的回答是“对”。

R

：另一战士乙的回答是“是”。

S

：这扇门是死亡门。则有

RP

Q且有

S(P∧┐Q)∨(┐P∧┐Q)(P∨

┐P)∧┐Q┐Q11例子：设有下列情况，结论是否有效。

(1)

或者是天晴，或者是下雨；

(2)

如果是天晴，我去看电影；

(3)

如果我去看电影，我就不看书。结论：如果我在看书，则天在下雨。解:令W：天晴；Q：下雨；

S：我去看电影；R：我在看书。前提：WQ,

WS，S┐R

结论：RQ解：演绎法推理过程如下：{1}(1)R

P（附加前提）{2}(2)S┐RP

{1,2}(3)┐ST，(1)(2)I9{4}(4)WS

P{1,2,4}(5)┐W

T，(3)(4)I9

{6}(6)WQP{6}(7)┐WQT,(6)E12{6}(8)┐W

QT,(7)I1{1,2,4,6}(9)QT,(5)(8)I8{2,4,6}(10)RQCP,(1)(9)例子：设有下列情况，结论是否有效。

(1)

或者是天晴，或者是下雨；

(2)

如果是天晴，我去看电影；

(3)

如果我去看电影，我就不看书。结论：如果我在看书，则天在下雨。解:令W：天晴；Q：下雨；

S：我去看电影；R：我在看书。前提：WQ,

WS，S┐R

结论：RQ例子：设有下列情况，结论是否有效。

(1)

或者是天晴，或者是下雨；

(2)

如果是天晴，我去看电影；

(3)

如果我去看电影，我就不看书。结论：如果我在看书，则天在下雨。12命题逻辑（PropositionalLogic）也称命题演算或语句演算，它研究由命题为基本单位构成的前提和结论之间的可推导关系。

原子命题是命题逻辑中研究的基本单位，即对原子命题不再分解，只有真、假二个真值，所以命题逻辑也称二值逻辑。谓词逻辑（PredicateLogic）谓词逻辑是比命题逻辑更加广泛的推理形式；谓词逻辑对命题做进一步的分析，把原子命题分解为谓词和个体两部分，进一步揭示分析前提和结论在形式结构方面的联系。13第1章命题逻辑1.1命题与联结词1.2命题公式、翻译和真值表1.3公式分类与等价式1.4对偶式与蕴含式1.5联结词的扩充与功能完全组1.6公式标准型----范式1.7公式的主范式1.8命题逻辑的推理理论141.1命题与联结词

一、命题的概念命题：非真必假的陈述句。

具有真假意义的陈述句，且真或者假二者必居其一，也只居其一。命题的真或假称为命题的真值。真用T或1表示假用F或0表示15自然语言中的感叹句、疑问句和祈使句不是命题。这真开心！你听懂了吗？请止步！命题的注意事项：判定命题的真值会因人、因时、因地、因标准而异。A:1+1=2B:1+1=10C:1+1=1现在是六点钟一个陈述句能否分辨其真假与是否现在能判断它是真是假是两件事。张校长的头发有一万根“自指谓”的陈述句（结论是对自身而言）

不是命题我所说的是假的16例：判断下列语句哪些是命题。若是命题，指出真值巴黎在法国请勿喧哗！明天去哪里？有外星人曹操是明朝人6+8>14今天下雨今天我休息11+1=100是命题，真不是命题不是命题是，不确定真值是，假是，假是，真值不确定是，真值不确定是，真值不确定17二、命题标识符命题标识符：表示原子命题的符号称为命题标识符，简称命题符。原子命题的符号表示：大小写英文字母：P、Q、R、p、q、r、……

带下标的大写字母：Pi，Qi，Ri，……例如：P：北京是中国的首都。命题常元：一个命题标识符P，如果表示一个确定的命题，则称P

为原子命题常元，简称命题常元；命题变元：若P只表示任意命题的位置标志，或表示不确定的命题，或以原子命题为值的变元P，称P为原子命题变元，简称命题变元。命题变元是以命题的真值为值的变元。命题变元不是命题。命题指派：将一个命题变元P用一特定命题去代替，它才能确定真值，叫做对P的指派或解释，记为S(P)或I(P)。18三、联结词联结词是逻辑联结词或命题联结词的简称，它是自然语言中连词的逻辑抽象，用它和原子命题构成复合命题。否定联结词——┐

合取联结词——∧

析取联结词——∨条件联结词——→

双条件联结词——19（1）否定联结词

设P是一个命题，由联结词┐和命题P构成┐P，读“非P”。┐P为命题P的否定式复合命题。联结词┐是自然语言中的“非”、“不”和“没有”等的逻辑抽象。P┐PTFFT

P：上海是一个大城市。┐P：上海并不是一个大城市。┐P：上海是一个不大的城市。20(2)合取联结词

令P和Q是两个命题，由联结词∧把P，Q连接成P∧Q，读做“P与Q”，或“P合取Q”。称P∧Q为P和Q的合取式复合命题。联结词∧是自然语言中的“并且”，“既…又…”等的逻辑抽象。PQP∧QQ∧PTTTTTFFFFTFFFFFFP：今天下雨。Q：明天下雨。P∧Q：今天下雨而且明天下雨。P∧Q：今天与明天都下雨。P∧Q：这两天都下雨。21(3)析取联结词

设P和Q是两个命题，由联结词∨把P，Q连接成P∨Q，读做“P或Q”。称P∨Q为P，Q的析取式复合命题。析取联结词是“或”、“或者”的逻辑抽象。析取联结词是表示可兼或，即二者可同时发生，不排斥二者发生的情况。析取联结词不表示不可兼或排斥或，即非此即彼。PQP∨QQ∨PTTTTTFTTFTTTFFFF今天晚上我在家看电视或去剧场看戏。（排斥或）----不是命题联结词他可能是100米或400米赛跑的冠军。（可兼或）----是命题联结词他昨天做了二十或三十道题。（表示近似数）----不是联结词22(4)条件联结词设P和Q是两个命题，由联结词→把P，Q连接成P→Q，读做“如果P，则Q”或者“P条件Q”。称P→Q为P和Q的条件式复合命题，把P和Q分别称为P→Q的前件和后件，或者前提和结论。联结词→是自然语言中“如果…，则…”，“若…，才能…”等的逻辑抽象，是充分条件。在自然语言中，前件为假，不管结论真假，整个语句的意义往往无法判断。在命题逻辑中，当P为F，P→Q为T，称为“善意推定”。在命题逻辑中允许前件和后件间无必然的因果关系。23(4)条件联结词PQP→QQ→PTTTTTFFTFTTFFFTTP：天下雨；Q：马路湿；

P→Q：如果天下雨，则马路湿。下面讨论P→Q的真值：如果天下雨，则马路湿；如果天下雨，则马路不湿；如果天不下雨，则马路湿；(善意推断)如果天不下雨，则马路不湿；P：2+2=4；Q：雪是黑的；P→Q：如果2+2=4，则雪是黑的。24(5)双条件联结词令P和Q是两个命题，由联结词把P，Q连接成P

Q，读做“P当且仅当Q”。称P

Q为P和Q的双条件式复合命题。双条件联结词又常称为同或，并用符号⊙表示。双条件联结词是自然语言中的“充分必要条件”、“当且仅当”等的逻辑抽象。PQPQQ

PTTTTTFFFFTFFFFTT三角形是等边三角形当且仅当三角形的三个内角相等。2+2=4当且仅当太阳是恒星。25四、命题分类命题分两类：原子命题和复合命题复合命题：由原子命题和联结词复合而成判断一个命题是否为复合命题，其关键是联结词是否出现，出现联结词则是复合命题，不出现联结词则是原子命题。复合命题的真值只取决于构成它们的各原子命题的真值，与它们的内容、含义无关。∧、∨、

具有对称性；而┐、→没有对称性；联结词都有从已知命题得到新的命题的作用，它们具有操作或运算的意义。联结词可以被看做是一、二元运算或一、二元函数。总结261.2命题公式、翻译和真值表

一、命题公式定义1.2.1原子命题公式：命题常元、命题变元统称为原子命题公式，简称原子公式。定义1.2.2

合式公式是由下列规则形成的字符串：

(1)真值T和F是合式公式。

(2)原子命题公式是一个合式公式。

(3)若A是合式公式，则┐A是合式公式。

(4)若A和B是合式公式，则A∧B、A∨B、A→B和AB都是合式公式。

(5)经过有限次地使用(1)(2)(3)(4)所得到的结果，都是合式公式。定义1.2.3

如果A1是公式A的一部分，且A1是一个公式，称A1是A的子公式。27定义补充(A∧B∧C)、(A∨B∨C)也是合式公式；(A∧B)、(A∨B)、(A→B)和(A

B)也被称为合取式、析取式、条件式和双条件式；A，B分别为(A∧B)、(A∨B)的合取项和析取项。(┐P)∨Q，(P→(Q∧R))都是合式公式；(P→Q，(P→Q)

(∧R)都不是合式公式。28联结词的优先级

公式最外层的圆括号可省略，如把(P→(Q∨R))写成P→(Q∨R)。┐只作用于邻接后的原子命题变元，例如把(┐P)∨Q写成┐P∨Q。联结词的优先级从高到低是：┐，∧，∨，→，。例：设公式A为(P→Q)→(Q∨R)，则P→Q，Q∨R都是A的子公式。29二、命题的翻译

命题的符号化要注意下列事项：确定给定句子是否为命题。句子中连词是否为命题联结词。要正确地表示原子命题和适当选择命题联结词。把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，称为翻译，也称符号化。

命题的符号化在数理逻辑中很重要！30例：符号化下列命题：他既聪明又用功。他虽聪明但不用功。除非你努力，否则你将失败。除非天气好，我才骑自行车上班。小王晚上要回家，除非下大雨。只有睡觉才能恢复疲劳。只要我还有口气，我就要战斗。A中没有元素，A就是空集。张明或者李强都可以做这件事。张明和李强都做这件事了。仅当你走，我将留下。P∧Q，P:他聪明Q：他用功P∧┐Q，P:他聪明Q：他用功┐P→Q，

P:你努力

Q:你失败

Q→P,

P:天气好

Q:我骑自行车上班┐Q→P,P:小王晚上回家

Q:下大雨Q→P，P：睡觉

Q：恢复疲劳P∧Q,P:张明做这件事

Q:李强做这件事P→Q，P：我还有口气

Q：我要战斗P

Q，P:A中没有元素

Q:A是空集P∨Q,P:张明做这件事

Q:李强做这件事Q→P,P:你走了

Q:我留下31例：符号化下列命题：铁和氧化合，但铁和氮不化合。如果我下班早，就去商店看看，除非我很累。李四是计算机系的学生，他选修了日语课或法语课。李四是计算机系的学生，他住在312室或313室。除非天气好，否则我是不会去公园的。如果晚上做完作业且没有其他的事，他就会去看电视或听音乐。P∧┐Q,P:铁和氧化合Q:铁和氮化合┐P→(Q→R),P:我很累Q:我下班早

R:我去商店看看P∧(Q∨R),P:李四是计算机系的学生

Q:他选修日语课R:他选修法语课P∧((Q∧┐R)∨(┐Q∧R)),P:李四是计算机系的学生Q:他住312R:他住313

Q→P,P:天气好Q:我去公园(P∧Q)→((L∧┐M)∨(┐L∧M))P:他晚上做完作业，Q：他没有其他事L：他看电视M：他听音乐32三、真值表

定义1.2.4

对于命题公式A中每个命题变元Pi，任给一个指派

S(Pi)或解释I(Pi)，得到一种真值的组合S(P1)S(P2)…S(Pn)或

I(P1)I(P2)…I(Pn)称为A的一个真值指派，或称为A的一种解释，记为S(A)或I(A)。若S(A)或I(A)为T，称S(A)或I(A)为A的成真指派或说A的解释为真。A的成假指派的定义类似。为方便计，有时将S(Pi)=1或S(Pi)=0记为Pi/1或Pi/0，1≤i≤n。显然，若公式A中有n个不同命题变元，便有2n组真值指派。33真值表定义1.2.5

设A为一命题公式，对其中出现的命题变元做所有可能的每一组真值指派S，连同公式A的相应的S(A)汇列成表，称为A的真值表。

真值表由两部分组成：表的左部分列出公式的每一种解释；表的右部分给出相应每种解释公式得到的真值。真值表的约定：命题变元按字典序排列。对公式每个解释，以二进制数从小到大或者从大到小顺序列出。若公式复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所给公式的真值。34P┐PTFFTPQP∧QQ∧PTTTTTFFFFTFFFFFFPQP∨QQ∨PTTTTTFTTFTTTFFFFPQP→QQ→PTTTTTFFTFTTFFFTTPQPQQ

PTTTTTFFFFTFFFFTT35例子：求(P→Q)(┐P∨Q)的真值表

PQ(P→Q)(┐P∨Q)

001111011111100100111101步骤

①

③

①

②36例子：求(P→Q)∧┐R的真值表

PQR(P→Q)∧┐R

000111001100010111011100100001101000110111111100步骤①

②

①此真值表有3个成真指派：(P/0,Q/0,R/0),(P/0,Q/1,R/0),(P/1,Q/1,R/0)。37例：作出下列命题的真值表:并非“室内很冷或很乱”，

也不是“室外暖和且室内太脏”PQRS┐(P∨Q)∧┐（R∧S）000011100011110010111001110001000010101001解：P：室内很冷Q：室内很乱

R：室外暖和S：室内太脏

本题可用符号表示为：┐(P∨Q)∧┐（R∧S）381.3公式分类一、公式分类定义1.3.1

设A为一个命题公式，对A做所有可能的解释I，对于这些解释I：若I(A)皆为成真，称A为永真式；若I(A)皆为成假，称A为永假式；若至少存在一个I(A)为真，称A为可满足式。永真式也称重言式，常用T表示；永假式也称矛盾式，常用F表示。判定给定公式是否为永真式，永假式或可满足式的问题，称为给定公式的判定问题。判定方法有真值表法和公式推演法。39二、等价公式定义1.3.2

设A和B是两个命题公式，如果A、B在其任意解释下，其真值都是相同的，则称A和B是等价的，或逻辑相等.

记作AB，读作A等价B，称AB为等价式。若公式A和B的真值表是相同的，则A和B等价。因此验证两公式是否等价，只需做出它们的真值表即可。40是逻辑双条件联结词，属于对象语言(命题逻辑)中的符号，它出现在命题公式中；不是逻辑联结词，属于元语言(描述对象语言的语言)中的符号，表示两个命题公式之间的一种充分必要(记为iff)关系，它不属于这两个公式的任何一个公式中的符号。与iff可通用。自反性：对任意公式A，有AA。对称性：对任意公式A和B，若AB，则BA。传递性：对任意公式A、B和C，若AB、BC，则AC。等价式有下列性质：41定理1.3.1

AB当且仅当A

B是永真式。证明：（1）必要性：若AB，则A

B是永真式。（2）充分性：若A

B是永真式，则AB。ABABB

ATTTTTFFFFTFFFFTT42例1：（1）如果A∨CB∨C，是否有AB

？（2）如果A∧CB∧C，是否有AB

？（3）如果┐A┐B，是否有AB?解：（1）若有真值指派使得S(A)=T,S(B)=F,S(C)=T

则A∨CB∨C成立，但AB

不成立（2）若有真值指派使得S(A)=T,S(B)=F,S(C)=F

则A∧CB∧C成立，但AB不成立（3）┐A┐B，则┐A

┐

B是永真式，即

A

B是永真式，所以

AB成立43三、基本等价式—命题定律(1)双否律：┐┐AA。(2)交换律：A∧BB∧A，A∨BB∨A，A

BB

A

。(3)结合律：(A∧B)∧CA∧(B∧C)，(A∨B)∨CA∨(B∨C)，

(A

B)

CA(B

C)。(4)分配律：A∧(B∨C)(A∧B)∨(A∧C)，

A∨(B∧C)(A∨B)∧(A∨C)。(5)德·摩根律：┐(A∧B)┐A∨┐B，┐(A∨B)┐A∧┐B。(6)等幂律：A∧AA，A∨AA

。(7)同一律：A∧TA，A∨FA

。判断公式间是否等价，有一些简单而又经常使用的等价式，称为基本等价式或命题定律，牢记并熟练运用它们是学好数理逻辑的关键。44三、基本等价式—命题定律（二）(8)零律：A∧FF，A∨TT

。(9)吸收律：A∧(A∨B)

A，A∨(A∧B)A

。(10)互补律：A∧┐AF

，(矛盾律)A∨┐AT

。(排中律)(11)条件式转化律：A→B┐A∨B

，A→B┐B→┐A。(12)双条件式转化律：

A

B(A→B)∧(B→A)(A∧B)∨(┐A∧┐B)，┐A

B┐(A

B)。(13)输出律：(A∧B)→CA→(B→C)。(14)归谬律：(A→B)∧(A→┐B)┐A

。由已知的等价式可以推演出更多的等价式，称这一过程为等价演算。等价演算是逻辑代数或布尔代数的重要组成部分。

45例1：证明P→(Q→R)Q→(P→R)┐R→(Q→┐P)证明：P→(Q→R)┐P∨(┐Q∨R)┐Q∨(┐P∨R)Q→(P→R)R∨

(┐Q∨┐P)例2：证明(P∧Q)

∨(P∧┐Q)P证明：(P∧Q)

∨(P∧┐Q)

P∧

(Q∨┐Q)

P∧T

P┐R→(Q→┐P)

46四、代入规则和替换规则（1）代入规则例1：求证：

(P→Q)

∨┐(P→Q)

是永真式。定理1.3.2

在一个永真式A中，任何一个原子命题变元R出现的每一处，用另一个公式代入，所得公式B仍是永真式。本定理称为代入规则。

逻辑联结词能够从已知公式合并形成新公式，可把逻辑联结词看成运算。“代入”和“替换”也有从已知公式得到新公式的作用，因此也可以看成运算。证明：由排中律知，A∨┐AT，即A∨┐A为永真式。用公式P→Q代入A中，则得(P→Q)

∨┐(P→Q)

根据代入规则可知，给定公式是永真式。47（2）替换规则定理1.3.3

设A1是合式公式A的子公式，若A1B1，并且将

A中的A1用B1

替换，得到公式B，则AB。本定理称为替换规则。这种替换称为等价替换。证明：因为Q→P

Q→P又由吸收律可知，

P∨(P∧Q)P

根据替换规则可得，

Q→(P∨(P∧Q))

Q→P例2:

证明：Q→(P∨(P∧Q))

Q→P48代入规则和替换规则的区别:代入是对原子命题变元而言的；而替换通常是可对命题公式实行之；代入规则必须用于永真式；而替换则不必；代入必须是处处代入；替换则可部分替换，亦可全部替换。491.4对偶式与蕴涵式定义1.4.1

在给定的仅使用联结词┐、∧和∨的命题公式

A中，若把∧和∨互换，F和T互换而得到一个命题公式A*，则称A*为A的对偶式，同时A也是A*的对偶式。

A与A*互为对偶式。一、对偶式50例：写出下列公式的对偶式（1）(P∧

Q)∨┐R（2）P∨T解：（1）(P∨Q)∧┐R（2）P∧F（3）┐(P∨Q)∧(P∨┐(Q∧┐S))

（3）┐(P∧Q)∨(P∧┐(Q∨┐S))51定理1.4.1(对偶定理)(德摩根律的推广)设A和A*互为对偶式，P1，P2，…，Pn是出现在A和A*的原子命题变元，则：①┐A(P1，P2，…，Pn)A*(┐P1，┐P2，…，┐Pn)②A(┐P1，┐P2，…，┐Pn)┐A*(P1，P2，…，Pn)证明：令公式A(P1，P2，…，Pn)中含有联结词┐，∧，∨的数目为L，

对L归纳证明。当L=0时，A=P1，┐(P1)┐P1，结论成立。当L=1时，A=P1∧P2或A=P1∨P2或A=┐P1，即:┐A=┐P1∨┐P2，或┐A=┐P1∧┐P2，或┐A=┐┐P1

=P1,结论成立。假设当L<=k-1时结论成立，可以证明当L=k时结论也成立。（略）①表明，公式A的否定等价于其命题变元否定的对偶式；②表明，命题变元否定的公式等价于对偶式之否定。52定理1.4.2

设A和B为两个命题公式，若AB，则A*B*。

证明：令P1，P2，…，Pn是A和B中的所有的命题变元。因为A(P1，P2，…，Pn)B(P1，P2，…，Pn)

所以┐A(P1，P2，…，Pn)┐

B(P1，P2，…，Pn)根据定理1.4.1(1)可知，┐A(P1，P2，…，Pn)A*(┐P1，┐P2，…，┐Pn)┐

B(P1，P2，…，Pn)

B*(┐P1，┐P2，…，┐Pn)则A*(┐P1，┐P2，…，┐Pn)

B*(┐P1，┐P2，…，┐Pn)利用代入规则，得

A*(P1，P2，…，Pn)

B*(P1，P2，…，Pn)53例试证明：（1）┐(P∧

Q)→(┐P∨Q)┐P∨Q

（2）(P∨Q)∧(┐P∧

Q)┐P

∧

Q证明：（1）┐(P∧Q)→(┐P∨Q)

(P∧Q)

∨(┐P∨Q)

(P∨┐P

∨Q)∧(Q∨┐P∨Q)T∧(┐P∨Q)┐P∨Q

（2）是（1）的对偶式，根据定理1.4.2即证得结论。54二、蕴涵式定义1.4.2

设A和B是两个命题公式，若A→B是永真式，则称A蕴涵B，记作AB，称AB为蕴涵式或永真条件式。

符号→和的区别与联系类似于和的关系。区别：→是逻辑联结词，属于对象语言(命题逻辑)中的符号，是公式中的符号；不是联结词，属于元语言(描述对象语言的语言)中的符号，表示两个公式间的关系，不是两公式中符号。联系：AB成立，其充要条件A→B是永真式。55蕴涵式性质①自反性，即对任意公式A，有AA。②传递性，即对任意公式A、B和C，若AB，BC，则AC。③对任意公式A、B和C，若AB，AC，则AB∧C。④对任意公式A、B和C，若AC，BC，则A∨BC。56蕴涵式性质定理1.4.3

设A和B是两命题公式，AB的充要条件是：

AB

且BA。证明：（1）必要性：若AB成立，则AB是永真式，即A→B且B→A均是永真式，所以AB且BA成立。（2）充分性：若AB且BA成立，则A→B且B→A均是永真式，即AB是永真式，故AB成立。57三、蕴涵式证明方法证明AB是蕴涵式即证A→B是永真式。（1）当A为T，B为T时，则A→B为T；（2）A→B┐B→┐A，即B为F，A为F时，则A→B为T。蕴涵式证明方法：真值表法前件真推导后件真方法设公式的前件A为真，若能推导出后件B也为真，则条件式A→B是永真式，故蕴涵式AB成立。后件假推导前件假方法设公式的后件B为假，若能推导出前件A也为假，则条件式A→B是永真式，故蕴涵式AB成立。58例子：┐Q∧(P→Q)┐P

证明：（1）前件真推导后件真方法：

前件为真：┐Q∧(P→Q)为真，则┐Q和(P→Q)都为真，即┐Q和(┐P∨Q)都为真.于是Q

为F，P为F，得┐P

为真，即后件为真；（2）后件假推导前件假方法：

后件为假：┐P

为假，则P

为真，

(a)若Q

为F，则(P→Q)为F，前件为假；

(b)若Q

为T，则┐Q为F，前件为假。59四、基本蕴涵式(1)A∧BA化简式(2)A∧BB化简式(3)AA∨B附加式(4)┐AA→B附加式变形(5)BA→B附加式变形(6)┐(A→B)A化简式变形(7)┐(A→B)┐B化简式变形(8)A∧(A→B)B假言推论(9)┐B∧(A→B)┐A拒取式下面给出常用的蕴涵式，称为基本蕴涵式，它们的正确性可用上述方法或归纳法证明之。60四、基本蕴涵式（续）(10)┐A∧(A∨B)B析取三段论(11)(A→B)∧(B→C)A→C

条件三段论(12)(AB)∧(BC)AC

双条件三段论(13)(A→B)∧(C→D)∧(A∧C)B∧D合取构造二难(14)(A→B)∧(C→D)∧(A∨C)B∨D析取构造二难特别当B=D时，有

(A→B)∧(C→B)∧(A∧C)B二难推论

(A→B)∧(C→B)∧(A∨C)B二难推论(15)A→B(A∨C)→(B∨C)前后件附加

A→B

(A∧C)→(B∧C)(16)A∧

BA∧B合取引入611.5联结词的扩充与功能完全组一、联结词的扩充

为了简洁而直接地表达命题间的联系，尚需定义4个联结词，它们分别是：合取非联结词↑析取非联结词↓条件非联结词双条件非联结词62(一)合取非联结词定义1.5.1

设P和Q是任两个原子命题，由合取非联结词↑把P，Q连接成P↑Q，读作“P合取非Q”，称它为P和Q的合取非式复合命题。

P↑Q的真值由命题P和Q的真值确定：当且仅当P和Q均为T时，P↑Q为F，否则P↑Q为T。

“合取非”又常称为“与非”。P↑Q

┐(P∧Q)63（二）析取非联结词定义1.5.1

设P和Q是任意两个原子命题，由析取非联结词↓把P，Q连接成P↓Q，读作“P析取非Q“，称它为P和Q的析取非式复合命题。

P↓Q的真值由P和Q的真值确定：当且仅当P和Q均为F时，P↓Q为T，否则P↓Q为F。“析取非”又常称为“或非”。P↓Q┐(P∨Q)64（三）条件非联结词定义1.5.1

设P和Q是任意两个原子命题，由条件非联结词把P，Q连接成P

Q，读作“P条件非Q“，称它为P和Q的条件非式复合命题。

P

Q的真值由P和Q的真值确定：当且仅当P为T而Q为F时，P

Q为T；否则P

Q为F。有时也把条件非联结词记为“→′“

P

Q

┐(P→Q)65（四）双条件非联结词定义1.5.1

设P和Q是任两个原子命题，由双条件非联结词把P，Q连接成P

Q，读作“P双条件非Q“

，称它为P和Q的双条件非式复合命题。

P

Q的真值由P和Q的真值确定：当且仅当P和Q的真值不同时，P

Q为T，否则P

Q为F。“双条件非”又常称为“异或”，常用符号“”或“

′”表示之。P

Q

┐(PQ)P

QP↑Q

P↓Q

P

Q

P

Q

00011011110010011011000066P↑Q

┐(P∧Q)P↓Q┐(P∨Q)P

Q

┐(P→Q)P

Q

┐(PQ)上述4个联结词构成的复合命题，其真值表如下：由真值表可知：67二、与非、或非和异或的性质(a)P↑QQ↑P(b)P↑P┐P(c)(P↑Q)↑(P↑Q)P∧Q(d)(P↑P)↑(Q↑Q)P∨Q（一）与非的性质

与非、或非以及异或在计算机科学中是经常使用的三个联结词。因此掌握它们的性质是十分必要的。

令P,Q,R是原子命题变元。(a)P↓QQ↓P(b)P↓P┐P(c)(P↓Q)↓(P↓Q)P∨Q(d)(P↓P)↓(Q↓Q)P∧Q（二）或非的性质68（三）异或的性质(a)P

Q

Q

P交换律(b)P(Q

R)(P

Q)R结合律(c)P∧(Q

R)(P∧Q)(P∧R)分配律(d)P

PF，F

PP，T

P┐P(e)若P

QR，则Q

RP，R

PQ，且P

Q

RF。69例2.把P↑Q表示为只含有↓的等价公式，

把P↓Q表示为只含有↑的等价公式。解：

P↑Q

┐(P

∧Q)

┐P∨┐Q

(P↓P)∨(Q↓Q)

((P↓P)↓(Q↓Q))↓((P↓P)↓(Q↓Q))

P↓Q

┐(P∨Q)

┐P∧

┐Q

(P↑P)∧

(Q↑Q)

((P↑P)↑(Q↑Q))↑((P↑P)↑(Q↑Q))

70例3.联接词

↑

和↓

服从结合律吗？解：联接词↑和

↓

不满足结合律。举例如下：

(a)

给出一组指派：P为F,Q为T,R为T，则

(P↑Q)↑R为F，但P↑(Q↑R)为T

故

(P↑Q)↑RP↑(Q↑R)

不成立(b)给出一组指派：P为T,Q为F,R为F，则

(P↓Q)↓R为T

，但P↓(Q↓R)为F

故

(P↓Q)↓R

P↓(Q↓R)

不成立71例4.如果A(P,Q,R)由R↑(Q∧┐(R↓P))给出，求它的对偶式A*(P,Q,R),并求出与A及A*等价且仅包含联结词“∧”“∨”

和“┐”的公式。解：AR↑(Q∧┐(R↓P))，则A*R↓(Q∨┐(R↑P))A

R↑(Q∧┐(R↓P))R↑(Q∧

(R∨

P))

┐(R∧(Q∧

(R∨

P)))

┐(R∧Q)∨┐(R∨

P)A*R↓(Q∨┐(R↑P))R↓(Q∨(R∧P))┐(

R∨(Q∨(R∧P)))┐(

R∨Q)∧┐(R∧P)72三、联结词功能完全组P↑Q┐(P∧Q)P↓Q┐(P∨Q)P

Q┐(PQ)P

Q

┐(P

Q)P

Q(┐P∨Q)∧(┐Q∨P)P→Q┐P∨QP∧Q┐(┐P∨┐Q)P∨Q┐(┐P∧┐Q)

即扩充的4个联结词↑↓能由原有5个联结词分别替代之，而原有5个联结词┐∧∨→又能由联结词组{┐，∧

}或{┐，∨

}取代。73定义1.5.2

称G为联结词功能完全组(最小联结词组)，如果G满足下列两个条件：①由G中联结词构成的公式能等价表示任意命题公式；②G

中的任一联结词不能用其余下联结词等价表示。可以证明以下都是联结词功能完全组：{┐，∨}，{┐，∧}，{┐，→}，{↑}，{↓}可以证明以下不是联结词功能完全组：{┐，

},{∧}，{∨}，{∧，∨}74例1.证明任意命题公式都可由仅包含{┐，∨}，{┐，∧}的命题公式代换，且它们是最小联结词组。证明：因为（1）P

Q(┐P∨Q)∧(┐Q∨P)，故可把包含“”的公式等价变换为包含“∧”和“→”的公式。（2）P→Q┐P∨Q

说明包含“→”的公式可变换为包含“┐”和“∨”的公式。（3）P∧Q┐(┐P∨┐Q)

和P∨Q┐(┐P∧┐Q)说明“∧”和“∨”可以互换。故由┐∧∨→这五个联结词组成的命题公式，必可由{┐，∨}，{┐，∧}组成的命题公式所替代。（4）P↑Q┐(P∧Q)

（5）P↓Q┐(P∨Q)（6）P

Q┐(PQ)

（7）P

Q

┐(P

Q)因此，任意命题公式都可由仅包含{┐，∨}，{┐，∧}的命题公式代换，且它们是最小联结词组。75例5.证明{∨}，{∧}，{→}不是最小联结词组。证明：若{∨}或{∧}是最小联结词组，则

┐P(P∨……)┐P(P∧……)

对所有命题变元指派T，则等价式左边为F,右边为T,

与等价表达式矛盾!。若{→}是最小联结词组，则┐PP→(P→(P→…)…)

对所有命题变元指派T，则等价式左边为F，右边为T，与等价表达式矛盾！761.7公式标准型——范式一、简单合取式与简单析取式定义1.7.1命题变元和命题变元的否定，称为文字。如果一个文字恰为另一个文字的否定，则称它们为一对相反文字。例如：P和┐P都是文字，并且是一对相反文字；

┐┐P不是文字；

P和┐Q都是文字，但不是一对相反文字。对于给定公式的判定问题，可用真值表方法加以解答。当公式中命题变元的数目较大时，真值表很麻烦。增加一个命题变元，真值表的行数目比原来增加一倍。为解决这一问题，需要研究公式标准型问题。77定义1.7.2

设L1，L2，······，

Lk都是文字，其中1≤i≤k，称L1∨L2∨······∨Lk为简单析取式，并称Li为析取项；称L1∧L2∧······∧Lk为简单合取式，并称Li为合取项。公式P，┐Q，P∧Q和┐P∧Q∧P等都是简单合取式，其中P，Q和┐P为相应的简单合取式的合取项；公式P，┐Q，P∨Q，┐P∨Q∨P等都是简单析取式，其中P，Q和┐P为相应简单析取式的析取项。一个命题变元或其否定既可以是简单合取式也可以是简单析取式，如P,┐Q等。78定理1.7.1

简单合取式为永假式的充要条件是：它至少含有相反文字出现。定理1.7.2

简单析取式为永真式的充要条件是：它至少含有相反文字出现。证明：充分性：因为对于任何命题变元P,有P∧┐P为F,

所以，

若P

∧┐P在简单合取式中出现，根据定义1.7.1,它必是永假式F。

必要性：假设某个简单合取式为永假式F，但该简单合取式中不同时包含相反文字。对这个简单合取式中各命题变元指派真值T，而各带否定的命题变元指派真值F，则使简单合取式取真值T，这与原假设矛盾！79二、析取范式与合取范式定义1.7.3

设A1，A2，·····Am为简单合取式，称A1∨A2∨······∨Am为析取范式，其中1≤m。定义1.7.4

设B1，B2，·····Bn为简单析取式，称B1∧B2∧······∧Bn为合取范式，其中1≤n。(P∧Q)∨

(┐P∧Q)∨

(P∧Q∧┐Q)是析取范式P∧

(┐P∨┐Q)是合取范式P∧Q既是析取范式又是合取范式

例子：80定理1.7.3

对于任何一个命题公式，都存在与其等价的析取范式和合取范式。求范式算法：①使用命题定律，消去公式中除∧、∨和┐以外的公式中出现的所有联结词；②使用┐(┐P)P

和德•摩根律，将公式中出现的联结词┐都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。81例子：求(P∧(QR))S

的析取范式和合取范式。

解：(P∧(QR))S┐(P∧(┐Q∨R))∨S(┐P∨(Q∧

┐R))

∨S┐P∨(Q∧┐R)∨S析取范式(┐P∨Q∨S)∧(┐P∨┐R∨S)合取范式82三、范式的应用利用析取范式和合取范式可对公式进行判定。定理1.7.4公式A为永假式的充要条件是A

的析取范式中每个简单合取式至少包含一对相反文字。定理1.7.5公式A为永真式的充要条件是A

的合取范式中每个简单析取式至少包含一对相反文字。83例：判定下面公式为何种公式：(1)P∨(QR)∨┐(P∨R)(2)(PQ)P解:(1)

P∨(QR)∨┐(P∨R)

P∨(┐Q∨

R)∨