离散数学46639省名师优质课赛课获奖课件市赛课一等奖课件

离散数学1/145离散数学:研究离散量关系一门科学。研究离散结构数学分科。（辞海）2/145离散数学内容：数理逻辑（MathematicsLogic)集合论(Sets)组合论（Combination)图论（GraphTheory)代数结构（AlgbraStructure)线性代数(LinearAlgbra)概率论（PropobilityTheory)……3/145离散数学由来与发展:一、古老历史:计数:自然数发展:图论:Konigsberg七桥问题二、年青新生:计算机:二进制运算4/145离散数学课程设置：计算机系关键课程信息类专业必修课程其它类专业主要选修课程5/145离散数学后继课程：数据结构、编译技术、算法分析与设计、人工智能、数据库、……6/145离散数学课程学习方法:强调：逻辑性、抽象性；重视：概念、方法与应用7/145用一组基本指令来编制一个计算机程序，非常类似于从一组公理来结构一个数学证实。8/145第一章 命题逻辑命题逻辑，也称命题演算，记为Ls。它与谓词逻辑组成数理逻辑基础，而命题逻辑又是谓词逻辑基础。数理逻辑是用数学方法即经过引入表意符号研究推理学问。所以，数理逻辑又名为符号逻辑。命题逻辑是研究由命题为基本单位组成前提和结论之间可推导关系。退出9/1451.1命题与联结词1.2命题变元和合式公式1.3公式分类与等价公式1.4联结词扩充与功效完全组1.5公式标准型——范式1.6公式主范式1.7命题逻辑推理理论10/1451.1 命题与联结词

１.命题概念

11/145命题：能判断真假陈说句。命题真值：命题判断结果。它只有两种可能：真用1或T表示，假用0或F表示。真值为1命题称为真命题；真值为0命题称为假命题。

12/145判断一个句子是否为命题：首先判断它是否陈说句，假如是陈说句，再判断它是否含有唯一真值。(命题真值是含有客观性质，而不是由人主观决定。)13/145例判断以下句子是否为命题（1）

3是素数。（2）

5.2是无理数。（3）

x大于y。（4）

月球上有冰。（5）

年元旦是晴天。（6）

π大于3吗？14/145（7）

请不要吸烟！（8）

这朵花真漂亮啊！（9）

我正在说假话。解

：(6)、(7)、(8)、(3)、(9)不是命题，其余都是。

15/145所谓命题，是指含有非真必假陈说句。而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命题。命题仅有两种可能真值—真和假，且二者只能居其一。因为命题只有两种真值，所以称这种逻辑为二值逻辑。16/145假如一陈说句再也不能分解成更为简单语句，由它组成命题称为原子命题或简单命题。原子命题是命题逻辑基本单位。命题分为两类，第一类是原子命题，原子命题用英文字母P，Q，R…及其带下标Pi，Qi，Ri，…表示。17/145命题常项(元)：真值确定简单命题。命题变项(元)：真值可变简单陈说句。如上例中（3）。第二类是复合命题，它由原子命题、命题联结词和圆括号组成。18/145２.命题联结词定义1.1.1 设P表示一个命题，由命题联结词l和命题P连接成lP，称lP为P否定式复合命题，lP读“非P”。称l为否定联结词。lP是真，当且仅当P为假；lP是假，当且仅当P为真。否定联结词“l”定义可由表1.1.1表示之。19/14520/145 因为否定”修改了命题，它是对单个命题进行操作，称它为一元联结词。21/145例将以下命题符号化：（1）

张伟不是三好学生。（2）

不是有理数。解：记p：张伟是三好学生。q：是有理数。则:(1)┐p；(2)┐q22/145定义1.1.2 设P和Q为两个命题，由命题联结词∧将P和Q连接成P∧Q，称P∧Q为命题P和Q合取式复合命题，P∧Q读做“P与Q”，或“P且Q”。称∧为合取联结词。当且仅当P和Q真值同为真，命题P∧Q真值才为真；不然，P∧Q真值为假。合取联结词∧定义由表1.1.2表示之。23/14524/145例将以下命题符号化(1)

2和3都是素数.(2)

张伟既用功又好学.(3)

张伟不但用功而且聪明.(4)

张伟即使用功但不聪明.(5)

张伟和王辉都是三好学生.(6)

张伟和王辉是同学.25/145解:(1)令p:2是素数；q:3是素数，则：p∧q。(2)、(3)、(4)：令r:张伟用功；s:张伟好学，t:张伟聪明；则：r∧s;r∧t;r∧┐t。(5)令x:张伟是三好学生；y:王辉是三好学生，则：x∧y。(6)是原子命题。26/145定义1.1.3 设P和Q为两个命题，由命题联结词∨把P和Q连接成P∨Q，称P∨Q为命题P和Q析取式复合命题，P∨Q读做“P或Q”。称∨为析取联结词。当且仅当P和Q真值同为假，P∨Q真值为假；不然，P∨Q真值为真。析取联结词∨定义由表1.1.3表示之。27/14528/145由定义可知，析取联结词表示“可兼和”，“不可兼和”另有别联结词定义之。前者称为相容或，后者称为排斥或。与合取联结词一样，使用析取联结词时，也不要求两命题间一定有任何关系。29/145例将以下命题符号化（1）

2或4是素数。（2）

他想去唱歌或跳舞。（3）

老王只能住204房或206房。（4）

派老五或小李中一个去上海。30/145解：(1)令p:2是素数；q:4是素数，则：p∨q;(2)令r:他想去唱歌；s:他想去跳舞，则：r∨s;(3)令t:老王住204房；u:老王住206房，则:(t∧┐u)∨(┐t∧u);(4)令x：派老王去上海；y：派小李去上海，则：(x∧┐y)∨(┐x∧y)。31/145定义1.1.4 设P和Q为两个命题，由命题联结词→把P和Q连接成P→Q，称P→Q为命题P和Q蕴涵（条件）式复合命题，简称蕴涵（条件）命题。P→Q读做“P蕴涵（条件）Q”或者“若P则Q”。称→为蕴涵（条件）联结词。 当P真值为真而Q真值为假时，命题P→Q真值为假；不然，P→Q真值为真。条件联结词→定义由表1.1.4表示之。

32/14533/145在条件命题P→Q中，命题P称为P→Q前件或前提，命题Q称为P→Q后件或结论。条件命题P→Q有各种方式陈说：“假如P，那么Q”；“P仅当Q”；“Q每当P”；“P是Q充分条件”；“Q是P必要条件”；“只有q才p”，“除非q才p”,“除非q，不然非p”等。34/145在日常生活中，用条件式表示前提和结论之间因果或实质关系，这种条件式称为形式条件命题。然而在命题逻辑中，一个条件式前提并不要求与结论有任何关系，这种条件式称为实质条件命题。采取实质条件式作定义，不单是出于“善意推断”，主要是因为前提与结论间有没有因果和实质关系难以区分，而且实质条件式已包含了形式条件式，更便于应用。35/145例将以下命题符号化，并指出各复合命题真值。(1)

假如3+3=6,则雪是白色。(2)

假如3+3≠6,则雪是白色。(3)

假如3+3=6,则雪不是白色。(4)

假如3+3≠6,则雪不是白色。(5)

只要a能被４整除，则a一定能被２整除。(6)

a能被４整除，仅当a能被２整除。(7)

除非a能被２整除，a才能被４整除。(8)

除非a能被２整除，不然a不能被４整除。(9)

只有a能被２整除，a才能被４整除。(10)只有a能被４整除，a才能被２整除。(a是一个给定正整数）。36/145解：令p：3+3=6；q：雪是白色。则(1)到(4)符号化形势分别为：p→q；┐p→q；p→┐q；┐p→┐q。它们真值分别为：１,１,０,１。令r：a能被４整除；s:a能被２整除。(5)到(9)都可符号化为:r→s,真值为１。(10)可符号化为s→r，真值视a值而定。37/145定义1.1.5 令P、Q是两个命题，由命题联结词

把P和Q连接成P

Q，称P

Q为命题P和Q双条件式复合命题，简称双条件命题，P

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

为双条件联结词。当P和Q真值相同时，P

Q真值为真；不然，P

Q真值为假。双条件联结词

定义由表1.1.5表示之。38/14539/145例将以下命题符号化，并讨论它们真值。(1)

√3是无理数当且仅当加拿大位于亚洲。(2)

2+3=5充要条件是√3是无理数。(3)

若两圆面积相等，则它们半径相等，反之亦然。(4)

燕子飞向北方时，春天就来了；而当春天来时，燕子就会飞回北方。40/145解：(1)令p：√3是无理数；q：加拿大位于亚洲，则p↔q,真值为0。（2）令r：2+3=5；令p：√3是无理数，则r↔p,真值为1。（3）令s：两圆面积相等；t：两圆半径相等，则s↔t,真值为1。（4）令x：燕子飞回北方；y：春天来了，则x↔y,真值为1。41/145本节小结以上定义五种最基本联结词组成一个联结词集{┐，∧，∨，→，↔}。由其中某个联结词联结两个原子命题（┐联结一个原子命题）所形成复合命题称为基本复合命题，它们真值情况以下表。pq┐pp∧qp∨qp→qp↔q000110111100000101111101100142/145

屡次使用联结词集中联结词，可组成更为复杂复合命题。求复杂复合命题真值时，可依据上述真值表逐次求取。但运算过程中应注意联结词优先次序(包含括号)：(),┐,∧,∨,→，↔。对同一优先级联结词，按出现先后次序运算。43/145例令：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。44/145在本节结束时，应强调指出是：复合命题真值只取决于各原子命题真值，而与它们内容、含义无关，与原子命题之间是否相关系无关。了解和掌握这一点是至关主要。45/1451.2命题变元和合式公式１.命题变元在命题逻辑中，命题又有命题常元和命题变元之分。一个确定详细命题，称为命题常元；一个不确定泛指任意命题，称为命题变元。显然，命题变元不是命题，只有用一个特定命题取代才能确定它真值：真或假。这时也说对该命题变元指派真值。46/145命题常元和命题变元均可用字母P等表示。因为在命题逻辑中并不关心详细命题涵义，只关心其真值，所以，能够形式地定义它们以下： 定义1.2.1 以真或1、假或0为其变域变元，称为命题变元；真或1、假或0称为命题常元。47/1452. 合式公式通常把含有命题变元断言称为命题公式。但这没能指出命题公式结构，因为不是全部由命题变元、联结词和括号所组成字符串都能成为命题公式。为此常使用归纳定义命题公式，方便组成公式有规则可循。由这种定义产生公式称为合式公式。定义1.2.2 单个命题变元和命题常元称为原子命题公式，简称原子公式。48/145定义1.2.3 合式公式是由以下规则生成公式：①单个原子公式是合式公式。②若A是一个合式公式，则(lA)也是一个合式公式。③若A、B是合式公式，则(A∧B)、(A∨B)、(A→B)和(A

B)都是合式公式。④只有有限次使用①、②和③生成公式才是合式公式。49/145当合式公式比较复杂时，经常使用很多圆括号，为了降低圆括号使用量，可作以下约定：①要求联结词优先级由高到低次序为：l、∧、∨、→、

②相同联结词按从左至右次序计算时，圆括号可省略。③最外层圆括号能够省略。为了方便计，合式公式也简称公式。50/145

定义(1)若命题公式A是单个命题(常项或变项)，则称A为0层公式。(2)称命题A是n+1(n≥0)层公式，只要A是以下情况之一：(a)A=┐B,B是n层公式;(b)A=B∧C,B,C分别为i层和j层公式，且max(i,j)=n。(c)A=B∨C,B,C分别为i层和j层公式，且max(i,j)=n。(d)A=B→C,B,C分别为i层和j层公式，且max(i,j)=n。(e)A=B↔C,B,C分别为i层和j层公式，且max(i,j)=n。比如:(┐p∧q)→r,(┐(p→┐q))∧((r∨s)↔┐p)分别为3层和4层公式。51/145

因为命题公式中含有命题变项，故其真值普通是不确定。当公式中全部命题变项都解释成详细命题后，命题公式就成了真值确定命题了。比如，在命题公式(p∨q)→r中，若将p解释成命题：2是素数，q解释成：3是偶数，r解释成：是无理数，则命题公式(p∨q)→r就被解释成了一个真命题：若2是素数或3是偶数，则是无理数。(因p,q,r真值为1,0,1)；另首先，假如p,q解释不变，而将r解释成：是有理数，则(p∨q)→r就被解释成了一个假命题。52/145定义设在命题公式A中出现全部命题变项为p1

,

p2,

…

pn

，给它们各指定一个真值，称为对公式A一个赋值(或解释)。若一个赋值使A真值为1，则称该赋值为A成真赋值(或真赋值)，不然称为A成假赋值（或假赋值)。注：设A中变项为p1

,

p2

,

…,

pn

，给A赋值a1

,

a2

,

…

an是指p1=a1,p2

=a2,…,pn=an，其中ai

为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)都是成假赋值。53/145３. 公式真值表定义1.2.4 对于公式中命题变元每一个可能真值指派，以及由它们确定出公式真值所列成表，称为该公式真值表。定义1.2.5 假如B是公式A中一部分，且B为公式，则称B是公式A子公式。

54/145用归纳法不难证实，对于含有n个命题变元公式，有2n个真值指派，即在该公式真值表中有2n行。为方便结构真值表，特约定以下：①命题变元按字典序排列。②对每个指派，以二进制数从小到大或从大到小次序列出。③若公式较复杂，可先列出各子公式真值(若有括号，则应从里层向外层展开)，最终列出所求公式真值。55/145

例

求以下公式真值表。(1)(┐p∧q)→┐r;(2)(p∧┐p)↔(q∧┐q);(3)┐(p→q)∧q∧rpqr┐p┐r┐p∧q(┐p∧q)→┐r00000101001110010111011111110000101010100011000011101111解：

(┐p∧q)→┐r真值表

56/145

(p∧┐p)↔(q∧┐q)真值表

pq┐p┐qp∧┐pq∧┐q(p∧┐p)↔(q∧┐q)0011001011000110010011100001┐(p→q)∧q∧r真值表

pqrp→q┐(p→q)┐(p→q)∧q┐(p→q)∧q∧r0001000001100001010000111000100010010101001101000111100057/1454. 命题符号化把一个用文字叙述命题对应地写成由命题标识符、联结词和圆括号表示合式公式，称为命题符号化。符号化应该注意以下事项:①确定给定句子是否为命题。②句子中连词是否为命题联结词。③要正确地表示原子命题和适当选择命题联结词。58/145命题符号化是很主要，一定要掌握好，在命题推理中经常最先碰到就是符号化一个问题，处理不好，等于说推理首要前提没有了。59/1451.3公式分类与等价公式１.公式分类定义1.3.1 设A为任意公式，则①对应每一个指派，公式A均对应确定真值为真，称A为重言式，或永真式。②对应每一个指派，公式A均对应确定真值为假，称A为矛盾式，或永假式。③最少存在一个指派，公式A对应确定真值为真，称A为可满足式。60/145由定义可知，重言式必是可满足式，反之普通不真。重点将研究重言式，它最有用，因为它有以下特点：①重言式否定是矛盾式，矛盾式否定是重言式，这么只研究其一就能够了。②两重言式合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单重言式可结构出复杂重言式。③由重言式使用公认规则能够产生许多有用等价式和蕴涵式。61/145判定给定公式是否为永真式、永假式或可满足式问题，称为给定公式判定问题。在Ls中，因为任何一个命题公式指派数目总是有限，所以Ls判定问题是可解。其判定方法有真值表法和公式推演法。62/145２. 等价公式定义1.3.2

设A,B是两个命题公式，若A,B组成等价式A↔B为重言式，则称A与B是等值,记为A⇔B。

显然，若公式A和B真值表是相同，则A和B等值。所以，验证两公式是否等值，只需做出它们真值表即可。63/145例判断公式┐(p∨q)与┐p∧┐q是否等值。解：用真值表法判断┐(p∨q)↔┐p∧┐q是否为重言式,真值表以下：pq┐p┐qp∨q┐(p∨q)┐p∧┐q┐(p∨q)↔(┐p∧┐q)00110111011010011001100111001001从表中可见，┐(p∨q)↔(┐p∧┐q)是重言式，故┐(p∨q)与┐p∨┐q等值。64/145在这里，请读者注意

和

区分与联络。

是逻辑联结词，属于目口号言中符号，它出现在命题公式中；

不是逻辑联结词，属于元语言中符号，表示两个命题公式一个关系，不属于这两个公式任何一个公式中符号。65/145等值式有以下性质：①自反性，即对任意公式A，有A

A。②对称性，即对任意公式A和B，若A

B，则B

A。③传递性，即对任意公式A、B和C，若A

B、B

C，则A

C。

66/145３.基本等值式——命题定律当命题公式中变项较多时，用上述方法判断两个公式是否等值计算量很大。为此，人们将一组经检验为正确等值式作为运算规则，经过公式间等值演算来判断两公式是否等值。在判定公式间是否等值，有一些简单而又经常使用等值式，称为基本等值式或称命题定律。牢靠地记住它并能熟练利用，是学好数理逻辑关键之一，读者应该注意到这一点。67/145惯用运算规则以下：1.双重否定律：A⇔┐(┐A)2.幂等律：A⇔A∨A,A⇔A∧A3.交换律:A∨B⇔B∨A,A∧B⇔B∧A4.结合律:(A∨B)∨C⇔A∨(B∨C),(A∧B)∧C⇔A∧(B∧C)5.分配律：A∨(B∧C)⇔(A∨B)∧(A∨C)(∨对∧分配律)A∧(B∨C)⇔(A∧B)∨(A∧C)(∧对∨分配律)6.德摩根律：┐(A∨B)⇔┐A∧┐B,┐(A∧B)⇔┐A∨┐B7.吸收律：A∨(A∧B)⇔A,A∧(A∨B)⇔A68/1458.零律：A∨1⇔1,A∧0⇔09.同一律：A∨0⇔A,A∧1⇔A10.排中律：A∨┐A⇔111.矛盾律：A∧┐A⇔012.蕴含等值式：A→B⇔┐A∨B13.等价等值式:(A↔B)⇔(A→B)∧(B→A)14.假言易位律:A→B⇔┐B→┐A（逆否律）15.等价否定律:A↔B⇔┐A↔┐B16.归谬律:(A→B)∧(A→┐B)⇔┐A

69/145

利用这16组24个等值式能够推演出更多等值式。由已知等值式推演出另一些等值式过程称为等值演算。在等值演算中,经惯用到以下置换规则。置换规则:设Φ(A)是含公式A命题公式，Φ(B)是用公式B置换了Φ(A)中全部A后所得公式。若B⇔A,则Φ(B)⇔Φ(A)。此规则可用数学归纳法证实。70/145

比如，对公式(p→q)→r,假如用┐p∨q置换其中p→q,则得(┐p∨q)→r.因为p→q⇔┐p∨q，故(p→q)→r⇔(┐p∨q)→r。类似地，可进行以下等值演算：(p→q)→r⇔(┐p∨q)→r(蕴含等值式，置换规则）⇔┐(┐p∨q)∨r(蕴含等值式，置换规则）⇔(p∧┐q)∨r(德摩根律，置换规则）⇔(p∨r)∧(┐q∨r)(分配律，置换规则）为简便起见,以后凡用到置换规则时,均无须标出。71/145例用等值演算证实:(p∨q)→r⇔(p→r)∧(q→r)证：(p→r)∧(q→r)⇔(┐p∨r)∧(┐q∨r)(蕴含等值式)⇔(┐p∧┐q)∨r(分配律)⇔┐(p∨q)∨r(德摩根律)⇔(p∨q)→r(蕴含等值式)

注：用等值演算证实等值式时，既能够从左向右推演，也能够从右向左推演。72/145例证实：(p→q)→r⇔p→(q→r）证方法一：真值表法，略。方法二：观察法。易见010是(p→q)→r成假赋值，而它却是p→(q→r)成真赋值，故(p→q)→r⇔p→(q→r)。方法三:记A=(p→q)→r,B=p→(q→r)。先将A,B等值演算化成易于观察真值公式，再进行判断。

A=(p→q)→r⇔(┐p∨q)→r(蕴含等值式)⇔┐(┐p∨q)∨r(蕴含等值式)⇔(p∧┐q)∨r(德摩根律)B=p→(q→r)⇔┐p∨(┐q∨r)(蕴含等值式)⇔┐p∨┐q∨r(结合律)

易见，000，010是A成假赋值，而它们是B成真赋值。故(p→q)→r⇔p→(q→r)。73/145例用等值演算判断以下公式类型(1)（p→q)∧p→q;(2)┐(p→(p∨q))∧r;(3)p∧(((p∨q)∧┐p)→q).解:(1)（p→q)∧p→q⇔(┐p∨q)∧p→q(蕴含等值式)⇔┐((┐p∨q)∧p)∨q(蕴含等值式)⇔(┐(┐p∨q)∨┐p)∨q(德摩根律)⇔((p∧┐q)∨┐p)∨q(德摩根律)⇔((p∨┐p)∧(┐q∨┐p))∨q(分配律)⇔(1∧(┐q∨┐p))∨q(排中律)⇔(┐q∨┐p)∨q（同一律）⇔(┐q∨q)∨┐p（交换律，结合律）⇔1∨┐p（排中律）⇔1（零律）故(p→q)∧p→q是重言式。74/145(2)┐(p→(p∨q))∧r⇔┐(┐p∨p∨q)∧r(蕴含等值式，结合律）

⇔(p∧┐p∧┐q)∧r(德摩根律）

⇔(0∧┐q)∧r(矛盾律）

⇔0∧r(零律)

⇔0(零律）故┐(p→(p∨q))∧r是矛盾式。75/145(3)p∧(((p∨q)∧┐p)→q)⇔p∧(┐((p∨q)∧┐p)∨q)(蕴含等值式)⇔p∧(┐((p∧┐p)∨(q∧┐p))∨q)(分配律)⇔p∧(┐(0∨(q∧┐p))∨q)(矛盾律)⇔p∧(┐(q∧┐p))∨q)(同一律)⇔p∧((┐q∨p)∨q)(德摩根律，双重否定律)⇔p∧((┐q∨q)∨p)(交换律，结合律)⇔p∧(1∨p)（排中律）⇔p∧1（零律）⇔p（同一律）

可见，（3）中公式不是重言式，因为00，01都是成假赋值；它也不是矛盾式，因为10，11都是其成真赋值，故它是可满足式。76/1451.4联结词扩充与功效完全组１.联结词扩充定义1.4.1设P和Q是任两个原子命题，①由合取非联结词↑和P，Q连接成P↑Q，称它为P和Q合取非式复合命题，读作“P合取Q非”。P↑Q真值由命题P和Q真值确定：当且仅当P和Q均为Ｔ时，P↑Q为Ｆ，不然P↑Q为Ｔ。“合取非”又常称为“与非”。77/145②由析取非联结词↓和P，Q连接成P↓Q，称它为P和Q析取非式复合命题，读作“P析取Q非”。P↓Q真值由P和Q真值确定：当且仅当P和Q均为Ｆ时，P↓Q为Ｔ，不然P↓Q为Ｆ。“析取非”又常称为“或非”。③由异或(排斥或)联结词把P，Q连接成PQ，称它为P和Q异或(排斥或)。PQ真值由P和Q真值确定：当且仅当P和Q真值不一样时，PQ为Ｔ，不然PQ为Ｆ。78/14579/145由表可知，①P

Q

(P

Q) ②P

Q

(P

Q) ③PQ

(P

Q)

(

P

Q)

(P

Q)80/145２.与非、或非和异或性质与非、或非以及异或在计算机科学中是经常使用3个联结词，所以，掌握它们性质是十分必要。令P、Q和R是原子命题变元。①与非性质(a)P↑Q

Q↑P(b)P↑P

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

P∧Q(d)(P↑P)↑(Q↑Q)

P∨Q81/145②或非性质(a)P↓Q

Q↓P(b)P↓P

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

P∨Q(d)(P↓P)↓(Q↓Q)

P∧Q从上述性质可知，联结词

、

和

可分别用联结词

或者

取代，读者能够自行验证，

和

都不满足结合律。82/145③异或性质(a)P

Q

Q

P(b)P

(Q

R)

(P

Q)

R(c)P∧(Q

R)

(P∧Q)

(P∧R)(d)P

P

F，F

P

P，T

P

P(e)若P

Q

R，则Q

R

P，P

P

Q，且 P

Q

R

F。83/145以上全部性质，用真值表或命题定律都是不难证实。定义称映射F:{0,1}n→{0,1}为n元真值函数。其中{0,1}n表示由0，1组成长为n字符串集合。2元真值函数有222=16个(每个真值函数可对应无穷多个命题公式,它们之间是等值.)84/145pqF0(2)F1(2)F2(2)F3(2)F4(2)F5(2)F6(2)F7(2)0000000000010000111110001100111101010101pqF8(2)F9(2)F10(2)F11(2)F12(2)F13(2)F14(2)F15(2)001111111101000011111000110011110101010185/145３.联结词全功效集已知有8个联结词就够用了，能不能少呢？若能少，表明有些联结词逻辑功效可由其它联结词替换。实际上，也确实如此，因为有以下等价式：P

Q

(P

Q)P

Q

(P

Q)PQ

(P

Q)可见，扩充3个联结词

，

和能由原有5个联结词分别替换之。86/145又由命题定律：P

Q

(

P

Q)

(

Q

P)P

Q

P

QP

Q

(

P

Q)P

Q

(

P

Q)可知，原有5个联结词

，

，

，

和

又能由联结词组{

，

}或{

，

}取代。那么，终究最少用几个联结词？就是说，用最少几个联结词就能等价表示全部命题公式。或者说，用最少几个联结词就能替换全部联结词功效。这便是所要定义联结词全功效集。87/145定义1.4.2称G为联结词全功效集，假如G满足条件：由G中联结词组成公式能等值表示任意命题公式；若还有G中任一联结词不能用其余下联结词等价表示，则称它是极小全功效集。能够证实，{

，

，，，↔}，{，，

}，{

，，}都是联结词全功效集，而不是极小全功效集。{

，

}，{

，

}，{

，

}，{

}，{

}都是联结词极小全功效集。但为了表示方便，仍经常使用联结词组{

，

，

}。88/145注：能够证实{∧,∨,→,↔}不是联结词全功效集，其任何子集，如{∧}，{∨}，{∧,→}，{∧,∨,→}，{∧,∨,↔}等也不是联结词完备集。设S1和S2是两个不一样联结词全功效集。用S1中联结词组成任何公式，必可等值转化成用S2中联结词组成公式，反之亦然。所以，在某一特定系统中，只需采取一个联结词全功效集即可。但在不一样应用中，人们往往采取不一样联结词全功效集。比如，在计算机硬件设计中，惯用以下“与非门”或者“或非门”来设计逻辑线路。89/1451.5公式标准型——范式１.简单合取式与简单析取式定义1.5.1在一公式中，仅由有限个命题变元及其否定组成合取式，称该公式为简单合取式，其中每个命题变元或其否定，称为合取项。定义1.5.2在一公式中，仅由有限个命题变元及其否定组成析取式，称该公式为简单析取式，其中每个命题变元或其否定，称为析取项。90/145比如，公式P，

Q，P

Q和

P

Q

P等都是简单合取式，而P，Q和

P为对应简单合取式合取项；公式P，

Q，P

Q，

P

Q

P等都是简单析取式，而P，Q和

P为对应简单析取式析取项。注意，一个命题变元或其否定既能够是简单合取式，也可是简单析取式，如例中P，

Q等。91/145定理1.5.1简单合取式为永假式充要条件是：它同时含有某个命题变元及其否定。定理1.5.2简单析取式为永真式充要条件是：它同时含有某个命题变元及其否定。92/145２.析取范式与合取范式定义1.5.3一个命题公式A称为析取范式，当且仅当A可表为有限个简单合取式析取。定义1.5.4一个命题公式A称为合取范式，当且仅当A可表为有限个简单析取式合取。93/145定理1.5.3对于任何一命题公式，都存在与其等价析取范式和合取范式。求范式算法：①使用命题定律，消去公式中除

、

和

以外公式中出现全部联结词；②使用

(

P)

P和德·摩根律，将公式中出现联结词

都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。94/145例求公式(p→q)↔r析取范式与合取范式。解:(1)合取范式：(p→q)↔r⇔(┐p∨q)↔r(消去→)

⇔((┐p∨q)→r)∧(r→(┐p∨q))

(消去↔)

⇔(┐(┐p∨q)∨r)∧(┐r∨(┐p∨q))(消去→)

⇔((p∧┐q)∨r)∧(┐p∨q∨┐r)(否定号内移,结合律,交换律)

⇔(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)(∨对∧分配律)(2)析取范式(p→q)↔r⇔((p∧┐q)∨r)∧(┐p∨q∨┐r)(见上述第一至四步)⇔(p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r)∨(r∧┐p)∨(r∧q)∨(r∧┐r)(∧对∨分配律)⇔(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)(矛盾律和同一律)95/145３.范式应用利用析取范式和合取范式可对公式进行判定。定理1.5.4公式A为永假式充要条件是A析取范式中每个简单合取式最少包含一个命题变元及其否定。定理1.5.5公式A为永真式充要条件是A合取范式中每个简单析取式最少包含一个命题变元及其否定。96/145４.范式不唯一性97/145对偶式在上节介绍命题定律中，多数是成对出现，这些成对出现定律就是对偶性质反应，即对偶式。利用对偶式命题定律，能够扩大等价式个数，也可降低证实次数。98/145定义在给定仅使用联结词

、∧和∨命题公式A中，若把∧和∨交换，F和T交换而得到一个命题公式A*，则称A*为A对偶式。显然，A也是A*对偶式。可见A与A*互为对偶式。99/145定理(对偶定理)设A和A*互为对偶式，P1，P2，…，Pn是出现A和A*中原子命题变元，则①

A(P1，P2，…，Pn)

A*(

P1，

P2，…，

Pn)②A(

P1，

P2，…，

Pn)

A*(P1，P2，…，Pn)①表明，公式A否定等价于其命题变元否定对偶式；②表明，命题变元否定公式等价于对偶式之否定。100/145定理设A和B为两个命题公式，若A

B则A*

B*。101/1451.6公式主范式范式基本处理了公式判定问题。但因为范式不唯一性，对识别公式间是否等价带来一定困难，而公式主范式处理了这个问题。下面将分别讨论主范式中主析取范式和主合取范式。102/145１.主析取范式(1)极小项概念和性质定义1.6.1在含有n个命题变元简单合取式中，若每个命题变元与其否定不一样时存在，而二者之一出现一次且仅出现一次，则称该简单合取式为极小项。103/145比如，两个命题变元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。能够证实，n个命题变元共形成2n个极小项。104/145假如将命题变元按字典序排列，而且把命题变元与1对应，命题变元否定与0对应，则可对2n个极小项依二进制数编码，记为mi，其下标i是由二进制数转化十进制数。用这种编码所求得2n个小项真值表，可显著地反应出极小项性质。下表分别给出了2个命题变元P和Q、3个命题变元P、Q和R极小项真值表。105/145极小项极大项公式成真赋值名称公式成假赋值名称┐p∧┐q00m0p∨q00M0┐p∧q01m1p∨┐q01M1p∧┐q10m2┐p∨q10M2p∧q11m3┐p∨┐q11M3两个变项p、q形成极小项与极大项

106/145极小项

极大项

公式成真赋值名称公式成假赋值名称┐p∧┐q∧┐r000m0p∨q∨r000M0┐p∧┐q∧r001m1p∨q∨┐r001M1┐p∧q∧┐r010m2p∨┐q∨r010M2┐p∧q∧r011m3p∨┐q∨┐r011M3p∧┐q∧┐r100m4┐p∨q∨r100M4p∧┐q∧r101m5┐p∨q∨┐r101M5p∧q∧┐r110m6┐p∨┐q∨r110M6p∧q∧r111m7┐p∨┐q∨┐r111M7三个变项p,q,r形成极小项与极大项107/145从表中可看出，极小项有以下性质：(a)没有两个极小项是等值，即是说各小项真值表都是不一样；(b)任意两个不一样极小项合取式是永假：mi∧mj

Ｆ，i≠j。(c)全部极小项之析取为永真：mi

Ｔ。(d)每个极小项只有一个解释为真。108/145(2)主析取范式定义与存在定理定义1.6.2在给定公式析取范式中，若其简单合取式都是极小项，则称该范式为主析取范式。定理1.6.1任意含n个命题变元命题公式A都存在主析取范式，而且是唯一。（见书上定理1.5）109/145(3)主析取范式求法主析取范式求法有两种：真值表法和公式化归法。定理1.6.1证实已给出了用真值表求主析取范式方法，而公式化归法给出以下：(a)把给定公式化成析取范式；(b)删除析取范式中全部为永假简单合取式；110/145(c)用等幂律化简简单合取式中同一命题变元重复出现为一次出现，如P∧P

P。(d)用同一律补进简单合取式中未出现全部命题变元，如Q，则P

P∧

Q∨Q)，并用分配律展开之，将相同简单合取式屡次出现化为一次出现，这么得到了给定公式主析取范式。111/145２.主合取范式(1)极大项概念和性质定义1.6.3在n个命题变元简单析取式中，若每个命题变元与其否定不一样时存在，而二者之一必出现一次且仅出现一次，则称该简单析取式为极大项。112/145比如，由两个命题变元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。能够证实，n个命题变元共有2n个极大项。113/145假如将n个命题变元排序，而且把命题变元与０对应，命题变元否定与１对应，则可对2n个极大项按二进制数编码，记为Mi，其下标i是由二进制数化成十进制数。用这种编码所求2n个极大项真值表，能直接反应出极大项性质。114/145类似可给出３个命题变元Ｐ、Ｑ和Ｒ全部极大项真值表，留给大家完成。从前表中可看出极大项性质：(a)没有两个极大项是等价。(b)任何两个不一样极大项之析取是永真，即Mi∨Mj

Ｔ，i≠j。(c)全部极大项之合取为永假，即Mi

Ｆ。(d)每个极大项只有一个解释为假。115/145(2)主合取范式定义与其存在定理定义1.6.4在给定公式合取范式中，若其全部简单析取式都是极大项，称该范式为主合取范式。定理1.6.3任意含有n个命题变元非永真命题公式A，都存在与其等价主合取范式。定理1.6.4任意含n个命题变元非永真命题公式A，其主合取范式是唯一。主合取范式求法也有两种，类似于主析取范式求法。116/145３.主析取范式与主合取范式关系因为主范式是由极小项或极大项组成，从极小项和极大项定义，可知二者有以下关系：

mi

Mi

Mi

mi所以，主析取范式和主合取范式有着“互补”关系，即是由给定公式主析取范式能够求出其主合取范式。117/145

设命题公式A中含有n个命题变元，且A主析取范式中含k个极小项，则

A主析取范式中必含有2n-k个极小项，不妨设为，，…，，即

A

∨∨…∨。于是

A

A

( ∨∨…∨ )

∧

∧…∧

∧∧…∧118/145由此可知，从A主析取范式求其主合取范式步骤为：(a)求出A主析取范式中没有包含极小项。(b)求出与(a)中极小项下标相同极大项。(c)做(b)中极大项之合取，即为A主合取范式。比如，(P

Q)

Q

m1

m3，则(P

Q)

Q

M0

M2。119/145例求公式(p→q)↔r主析取范式和主合取范式。解:(1)主析取范式由前例知，(p→q)↔r⇔(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)∵(┐p∧r)⇔┐p∧(┐q∨q)∧r

⇔(┐p∧┐q∧r)∨(┐p∧q∧r)

⇔m1∨m3(q∧r)⇔(┐p∨p)∧q∧r⇔(┐p∧q∧r)∨(p∧q∧r)⇔m3∨m7（p∧┐q∧┐r)⇔m4∴(p→q)↔r⇔m1∨m3∨m4∨m7120/145(2)

主合取范式由前例知，(p→q)↔r⇔(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)∵(p∨r)⇔p∨(q∧┐q)∨r⇔(p∨q∨r)∧(p∨┐q∨r)⇔M0∧M2(┐q∨r)⇔(p∧┐p)∨┐q∨r⇔(p∧┐q∨r)∧(┐p∨┐q∨r)⇔M2∧M6(┐p∨q∨┐r)⇔M5∴(p→q)↔r⇔M0∧M2∧M5∧M6121/145４.主范式应用利用主范式能够求解判问题或者证实等价式成立。（1）判定问题依据主范式定义和定理，也能够判定含n个命题变元公式，其关键是先求出给定公式主范式Ａ；其次按以下条件判定之：(a)若A

Ｔ，或A可化为与其等价、含2n个小项主析取范式，则A为永真式。122/145(b)若A

Ｆ，或A可化为与其等价、含2n个大项主合取范式，则A为永假式。(c)若A不与Ｔ或者Ｆ等价，且又不含2n个小项或者大项，则A为可满足。（2）证实等价式成立因为任一公式主范式是唯一，所以将给定公式求出其主范式，若主范式相同，则给定两公式是等价。123/145例利用公式主析取范式判断公式类型：(1)┐(p→q)∧q;(2)p→(p∨q);(3)(p∨q)→r解：(1)┐(p→q)∧q⇔┐(┐p∨q)∧q⇔p∧┐q∧q⇔0.

故

┐(p→q)∧q是矛盾式。

(2)p→(p∨q)⇔┐p∨p∨q

⇔(┐p∧(┐q∨q))∨(p∧(┐q∨q))∨((┐p∨p)∧q)

⇔(┐p∧┐q)∨(┐p∧q)∨(p∧┐q)∨(p∧q)∨(┐p∧q)∨(p∧q)

⇔(┐p∧┐q)∨(┐p∧q)∨(p∧┐q)∨(p∧q)

⇔m0∨m1∨m2∨m3`该主析取范式含全部22个极小项，故p→(p∨q)是重言式。注：另一个推演：p→(p∨q)⇔┐p∨p∨q⇔1∨q⇔1⇔m0∨m1∨m2∨m3124/145(3)（p∨q)→r⇔┐(p∨q)∨r

⇔(┐p∧┐q)∨r

⇔(┐p∧┐q∧(┐r∨r))∨((┐p∨p)∧(┐q∨q)∧r)⇔(┐p∧┐q∧┐r)∨(┐p∧┐q∧r)∨(┐p∧┐q∧r)∨(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q∧r)

⇔m0∨m1∨m3∨m5∨m7故该公式是可满足式,但不是重言式。

125/1451.7命题逻辑推理理论在逻辑学中，把从前题（又叫公理或假设）出发，依据公认推理规则，推导出一个结论，这一过程称为有效推理或形式证实。所得结论叫做有效结论，这里最关心不是结论真实性而是推理有效性。前提实际真值不作为确定推理有效性依据。不过，假如前提全是真，则有效结论也应该真而绝非假。126/145在数理逻辑中，集中注意是研究和提供用来从前提导出结论推理规则和论证原理，与这些规则相关理论称为推理理论。提请注意，必须把推理有效性和结论真实性区分开。有效推理不一定产生真实结论，产生真实结论推理过程未必一定是有效。再说，有效推理中可能包含假前提；而无效推理却可能包含真前提。127/145可见，推理有效性是一回事，前提与结论真实是否是另一回事。所谓推理有效，指它结论是它前提合乎逻辑结果，也即，假如它前提都为真，那么所得结论也必定为真，而并不是要求前提或结论一定为真或为假。假如推理是有效话，那么不可能它前提都为真时而它结论为假。128/145１.推理基本概念和推理形式推理也称论证，它是指由已知命题得到新命题思维过程，其中已知命题称为推理前提或假设，推得新命题称为推理结论。在数理逻辑中，前提H是一个或者n个命题公式H1,H2,···Hn；结论是一个命题公式C。由前提到结论推理形式可表为H1,H2,···,Hn

C，其中符号

表示推出···。可见，推理形式是命题公式一个有限序列，它最终一个公式是结论，余下为前提或假设。129/145定义1.7.1假如存在H1，H2，…，Hn，C一个指派，使得每个Hi(1≤i≤n)为真而C为假推理形式H1，H2，…，Hn

C是无效；不然，推理是有效，此时称C是H1，H2，…，Hn有效结论，或称C是从前提H1，H2，…，Hn逻辑推出结论。定理1.7.1推理形式H1，H2，…，Hn

C是有效，当且仅当命题公式(H1∧H2∧…∧Hn)→C是永真式，亦即(H1∧H2∧…∧Hn)

C。130/1452.推理定律在研究推理过程中，人们发觉了一些主要重言蕴含式，并将它们作为推理定律，在推理过程中可直接引用。惯用推理定律有：(1)附加律:A

A∨B(2)化简律:A∧B

A(3)假言推理:(A→B)∧A

B(4)拒取式:(A→B)∧┐B

┐A(5)析取三段论:(A∨B)∧┐B

A131/145假言三段论:(A→B)∧(B→C)

(A→C)等价三段论:(A↔B)∧(B↔C)

(A↔C)结构性二难:(A→B)∧(C→D)∧(A∨C)

(B∨D)结构性二难(特殊形式):(A→B)∧(┐A→B)∧(A∨┐A)

B破坏性二难:(A→B)∧(C→D)∧(┐B∨┐D)

(┐A∨┐C)132/145另外,前面给出24个等值式中每一个都派生出两条推理定律.比如┑┑A

A产生出┑┑A

A和A

┑┑A.还有一些等值式和重言蕴含式可在推理中引用。如:A

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

A∧┐BA→(B→C)

(A∧B)→C(A↔B)

(A∧B)∨(┐A∧┐B)133/145┐(A↔B)

A↔┐B┐A

A→BB

A→BA→B

(A∨C)→(B∨C)A→B

(A∧C)→(B∧C)因为推理定律是确定有效结论不可缺乏主要依据，所以要切记并熟练利用它们。134/1453.推理规则在数理逻辑中，从前提推导出结论，要依据事先提供公认推理规则，它们是：①Ｐ规则(也称前提引入规则)：在推导任一步骤上，前提可视需要引入使用。②Ｔ规则(也称结论引入规则)：在推导任一步骤上，前面已导出有效结论都可作为后续推导前提引入。③置换规则：在证实任何步骤上,命题公式中子公式都能够用与之等值公式置换。之前九条推理定律能够按照结论引入规则在证实中引用。（见教材第23页）135/145例.结构下面推理证实:前提:p∨q,q→r,p→s,┐s结论:r∧(p∨q)证实:①p→s前提引入②

┐s前提引入③

┐p①②拒取式④

p∨q前提引入⑤q③④析取三段式⑥q→r前提引入⑦r⑤⑥假言推理⑧r∧(p∨q)⑦④合取136/145前提:┐p∨q,r∨┐q,r→s结论:p→s证实:┐p∨q前提引入p→q①置换r∨┐q前提引入q→r③置换p→r②④假言三段论r→s前提引入⑦p→s