数学语言与证明方法

1、第一章数学语言与证明方法1 集合的概念和运算（ 4 学时）【教学目的】了解、掌握集合 的基本概念及例子【教学要求】掌握集合 的基本概念及例子； 掌握集合五种运算和集合相等证明；【教学重点】掌握集合五种运算和集合相等证明；【教学难点】如何正确的证明集合之间包含和相等关系【教学方法】讲练结合教学法、提问式与启发式相结合教学法。【教学手段】传统板书与多媒体课件辅助教学相结合。【课型】 新授课教学过程集合是一切数学的基础，每一门数学的讨论都离不开集合，为此， 我们必须掌握集合的基本定义及运算规律，掌握集合的证明方法，这对于学习离散数学将有极大的帮助。除此以外，在离散数学中，序列、整除、矩阵也将是十分重

2、要的基础知识。下面就从6 个知识点来加以阐述。1.1 集合与元素集合是任意客体 (对象 )的聚集。客体称为这个集合的“成员”或“元素” ，元素 a 要么属于集合 A ，要么不属于集合 A, 记为：aA或aA此时，要充分的认识“任意客体”和“聚集”的含义。1.2集合与集合的关系集合与集合之间的关系有包含、相等、真包含、不真包含等，具体定义如下：(1)B包含 A中（或 A包含 B）,记为 BABA(x)( xBxA), 此时，也称 B是A 的子集。（ 2）集合 A 与集合 B 相等，记为A=B.AB(BA)(AB)此时，两个集合各自包含的对象一一对应相等（或者说完全相等），该定义称为集合的外延性定

3、理。(3) 集合 B不被 A 所包含，记为 BA。BA( x)( xB x A) ，此时，也称集合B 不是集合 A 的子集。（ 4）集合 A 与集合 B 不相等，记为 A B。AB( BA)( AB)(5) 集合 B 真包含在集合A 中或集合A 真包含集合 B,记为 BA 。BA (BA)(BA)(x)( x BxA)(x)( xAxB) ，此时，也称集合B 是集合 A 的真子集。（ 6）集合 B 不被 A 所真包含， 记为 BABA(BA)( BA)在集合中，常常涉及到集合之间的包含与集合之间相等的证明。证明时，常依据上述定义，采用离散数学中特有的按定义证明方法来加以证明。由于离散数学中的很

4、多定义，都是由两部分构成，即“如 ，则 ”，我们把定义中的前半部分叫“已知”，后半部分叫“结论”，所以，所谓按定义证明方法就是首先叙述出你所要证明问题的定义，利用定义中的“已知”条件，加上题目中的其他的已知条件，推出定义中的“结论”。1.3特殊的集合(1) 空集：不含任何元素的集合叫做空集，记为。空集是绝对唯一的，且是任何集合的子集。证明一个集合是空集， 或证明集合的唯一性， 常采用反证方法， 即假设该集合不是空集，或不唯一，导致与已知条件的矛盾或导致唯一。（ 2） 全集：在一个具体的问题中， 所研究的集合都是某个固定集合的子集，则称这个固定集合为全集，记为 E 或 U 。全集仅是相对唯一的。

5、（ 3） 幂集：任一集合A 的一切子集作为元素所构成的称谓A 的幂集，记为P（ A），P( A) x |一切 x A。如 |A|=n,|A|为集合 A 的元素个数，即集合的基数，则| P( A) | 2|A|2n ( C|0A| C|1A|C|AA|(1 1)|A|2|A|2n )显然 |A|P （ A） | ，由此可知，集合中不存在最大的集合。1.4集合的运算与定律1. 集合的运算集合的基本运算有并，交 ，差，补 ，对陈差，其定义如下：AB x | ( xAB x | ( xAB x | ( xA) ( x B)A) ( x B)A) (x B) AEA xE)(xA) x | xA( A的

6、补也常记为A, A, Ac )AB(AB)(BA)(AB)(AB) x | ( xA)( xB)( xB)(xA) x | ( xA)( xB)( xA)(xB)2. 运算的定律(1)幂等律： AAA, AAA（2） 结合律：( AB)CA ( BC),( AB)CA(B C)（3） 交换律： ABBA, ABBA（4） 分配律： A(BC )( AB)(AC ),A(BC)(AB)(AC)(5)吸收律： A(AB)A,A (AB)A(6)同一律： AA, AEA(E , 分别表示关于运算，的零元)(7)零律： A EE, A(E ,分别表示关于运算，的零元)(8)排中律、矛盾律：A AE,

7、A A( A又叫做 A的补元 )(9)D.M 律： A( BC)AB)(AC )A(BC)AB)(AC) ( BC ) B C ( BC ) B C (10) 双重否定律 ：（ A） A1.5 有穷集合的计数解决有穷集合的计数问题有两种方法：文氏图法和包含排斥原理。设 S 是有穷集， p1,p 2, ,p m 是 m 条性质， S中的任何元素x 对于对于性质pi (i=1,2, ,m) 具有或者不具有，两种情况必居其一。令 Ai表示 S 中不具有性质 pi的元素构成的集合，则包含排斥原理可描述为：m1)m| A1A2Am | | S | Ai| AiAj | AiAjAk |(| A1. Am

8、i 11 i j m1 i j k mm( 1)m1A1A2. Am| Ai| Ai Aj | AiAjAk | A1.Ami 11 i j m1 i j k m1.6 无限集合1 可数无限集合自然数集合N=0， 1，2， 是一个可数（可列）无限集合，凡是与自然数集合等势的集合就是可数无限集合。如整数集合、 奇数集合、 偶数集合、 素数集合有理数集合等。2. 不可数集合开区间（ 0，1）称为不可数集合，凡与（0，1）等势的集合都是不可数集合，如闭区间 0 ， 1 ，实数集合、无理数集合、复数集合等。3. 有限集合和无限集合的重要差别（ 1）两个有限集合等势当且仅当它们有相同个数的元素；（ 2）

9、有限集合不和其任何真子集等势；（ 3）无限集合可以和其真子集等势；（ 4）如 A，B 是两个有限集合，且|A|=|B|， AB ，则 A=B。1.7序列1. 序列一个序列就是按某种顺序排列的一张表。2. 增序列设 S 是一个序列，如对任意的 n，有： Sn Sn+1 , 则序列 S 称为增序列；如对任意的 n, 有 Sn+1 Sn，则序列 S 称为减序列。3. 子序列对于 n=m,m+1, , 令 Sn 是一个序列，且令 n1,n 2,n 3, 是一个增序列，对于所有的值在 m,m+1,. 中的 k 值，满足 nk 0，则有 m=qn+r, 其中商， r 称为余数。一个大于1 的正整数p 被称

10、为素数，如果仅有q,r是整数，且0rp 自身和数字1 能整除p.n。 q 称为2. 最大公因子如果 a,b 和 k 都是正整数，且k|a,k|b,则称 k 是 a 和 b 的公因子。如果d 是最大的这种 k, 则 d 被称为最大公因子，记为d=GCD(a,b)如果 a,b 是任何正整数，且GCD(a,b)=1 ，则我们称互质的。3 最小公倍数如果 a,b 和 k 都是正整数，且a|k,b|k,则称 k 是 a 和 b 的公倍数。如果c 是最小的这种 k, 则 c 被称为最小公倍数，记为C=LCM(a,b)1.10总结通过本章的学习，应达到下面的基本要求：（ 1） 能正确地表示一个集合，会画文氏

11、图；（ 2） 能判定元素是否属于给定的集合；（ 3） 能利用安定以证明法证明两个集合之间的包含、相等、和真包含的关系；（ 4） 能熟练地作集合之间的并、交、 差、补和对称差运算，掌握集合运算的定律；（ 5） 能熟练地计算 P（ A）；（ 6） 能求解与有穷集合计数相关的实际问题；（ 7） 会求序列与子序列，并能进行序列的运算；（ 8） 能熟练地将一个数分解成素数的积， 并能求两个数的最大公因子和最小公倍数；（ 9） 能熟练地进行矩阵的各类运算。第2章命题逻辑命题逻辑 (4 学时 )【教学目的】介绍命题逻辑的基本概念。 掌握利用命题逻辑表示自然语言，描述概念、判断和推理。建立初步的语言形式化方法

12、。【教学要求】1识记命题表示方法、真值判断、命题公式的递归定义。2领会联结词真值确定、翻译、命题公式的等价性和蕴涵性证明、任给公式化为析取范式、任给公式化为主析取范式、任给公式化为合取范式、任给公式化为主合取范式。3简单应用命题逻辑推理规则【教学重点】掌握数理逻辑中命题的翻译及命题公式的定义； 利用真值表技术和公式转换方式求公式的主析取范式和主合取范式； 利用规则、 基本等价和蕴涵公式、 三种不同的推理方法完成命题逻辑推理；【教学难点】如何正确地掌握对语言的翻译，如何利用推理方法正确的完成命题推理【教学方法】讲练结合教学法、提问式与启发式相结合教学法。【教学手段】传统板书与多媒体课件辅助教学相

13、结合。【课型】 新授课教学过程课题导入数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其他分支、 计算机学科、 人工智能、 语言学等学科均有十分密切的联系，并且益显示出它的重要作用和更加广泛的应用前景。要很好地使用计算机，就必须学习逻辑。 数理逻辑分五大部分。在离散数学中仅介绍命题逻辑和谓词逻辑。 命题逻辑是谓词逻辑的基础， 只有掌握了命题逻辑，才能学好谓词逻辑。对于命题逻辑，下面从六个知识点来加以阐述。1.1命题符号化及联系结词1 命题有确切真值的陈述句称为命题。所谓确切真值是指在具体的环境，具体的时间，具体的对象，具体的位置等情况下能唯一确定真值的。命题分为两种：(

14、1) 简单命题：不能分解为更为简单的句子的命题。(2) 复合命题：能够分解为更为简单的命题。2 命题联结词联结词记号复合命题读法记法真值结果否定乛P 是不对的P 的否定乛 P乛 P 为真当且仅当P 为假合取P并且 QP与 Q的合取P QP Q 为真当且仅当P， Q 同为真析取P或者 QP与 Q的析取P QP Q 为真当且仅当P， Q 至少一个为真蕴涵若P，则QP蕴涵 QP QP Q 为假当且仅当P为真， Q为假等价P当且仅当 Q P等价于 QP P Q 为真当县仅当P， Q 同为真假Q关于联结词，有如下几点提醒大家注意：（ 1）此联结词是联结的句子与句子之间的联结，而非单纯的名记号、形容词、数

15、词等的联结；（ 2）此联结词是两个句子真值之间的联结词，而非句子的具体含义的联结，两句子之间可以无任何的内在联系；（ 3）联结词与自然语言之间的对应并非一一对应，如合取联结词“”对应了自然语言中的“既又” 、“不仅而且” 、“虽然但是” 、“并且”、“和”、“与”等。如蕴涵联结词“” ， PQ 对应了自然语言中的“加P 则 Q”，“只要 P 就 Q”，“P 仅当 Q”，“只有 Q 才 P”，“除非 Q 否则乛 P”对应了自然语”等。如等价联结词“言中的“等价” 、“并且仅当” 、“充分必 ”等。如析取联结词是对应相容的或(中兼的或 )。2.2 命题公式及分类一般称具有确切真值的简单命题叫命题常

16、量，用予具体内容的简单命题称为命题变量（变元），此时的1合式公式P， Q， R，等表示。而没有赋P，Q，R 没有具体的真值。（ 1）单个的命题变量或常量（含1 或0）是合式公式；（ 2）若P 是合式公式，则（乛P）也是合式公式；（ 3）若P，Q 是合式公式，则（P Q）、（ P Q）、（ PQ）、（ P Q）也是合式公式。只有有限次使用上述三步形式的符号串才是合式公式（命题公式）“”，简称公式。为了简化公式，可按如下优先级别进行：“（）”“乛”“ ”“”“ ”其中，为避免错误，合取与析取看成是同等优先级别，要改变或强调其优先级别，采用括号。另外，最外层的括号可以省掉，同级的按从左到右的顺序进行

17、运算。2赋值或解释与真值表设 G 是命题公式， P1， P2， Pn (n 1)是出现在公式G 中的所有命题变元，指定P1，P2， Pn 一组真值，则这组真值称为G 的一个解释或赋值。此时不同的赋值就有2n种。将此 2n 种不同的赋值下的取值情况列成的表称为G 的真值表。3公式的分类设 G 为一公式，（ 1）如 G 在它所有的解释之下都为真，则称G 为永真或重言式；（ 2）如 G 在它所有的解释之下都为假，则称G 为永假或矛盾式；（ 3）如 G 在它所有的解释之下至少有一个为真，则称G 为可满足式。2.3 等价公式与演算1等价关系称公式 G， H 是等价的，如果在其任意的解释下，其真值相同，记

18、为G=H 。说明： G=H 仅描述了两公式 G，H 之间的一种等价的关系， G=H 本身并非是一个公式，它不能作直接计算。要判断 G=H ，可采用： G=H 当且仅当公式GH 是一个永真式。2代入定理设 G(P1， P2， Pn)是一个公式， G1(P1，P2， Pn)， Gn(P1， P2， Pn)为任意公式，若 G 是永真式或永假式，则用 G1， G2， Gn 取代公式 G 中的 P1， P2， Pn后而得的新公式G(G 1， Gn) G (P1，P2， Pn)仍是一个永真式或永假式。3运算定律设 G， H， S 是任意的公式，则有如下基本的运算定律：（ 1）幂等律： G G G， G G

19、 G（ 2）结合律： (G H) S G (H S),（ G H） SG（ H S）（ 3）交换律： G H H G， G H H G（ 4）分配律：G（ H S）（GH ）（ GS），G（ H S）（ GH ）（ GS）（ 5）吸收律： G（ GH ） G，G（ G H） G（ 6）同一律： G 0=G，G 1=G(0 ， 1 分别是关于运行，的幺元)（ 7）零律： G 1=1， G 0=0(0， 1 分别是关于运算，的零元)（ 8）排中律，矛盾律： G乛 G=1， G 0=0( 乛 G 又叫做 G 的补元 )（ 9）D ， M 律：乛 (G H)= 乛 G乛 H ，乛 (GH)= 乛 G乛

20、 H（ 10）双重否定律：乛（乛G） G（ 11）蕴涵等值式： GH 乛 GH（ 12）等价等值式： G H （ G H ）（ H G）（乛 GH ）（乛 H G）（ 13）假言易位： GH 乛 H乛 G（ 14）等价否定等值式： GH 乛 G乛 H（ 15）归谬论： (GH ) (G 乛 H)乛 G其中：只要将运处“乛”，“”，“”分别对应集合中的运算“”，“”、“”，真值“ 1”，“ 0”分别对应集合中的全集E 和空集，集合对应于命题的公式，则定律(1) (10)就完全同集合中的定律(1) (10).另外 ,(11) (15)是命题逻辑中特有的公式,重点要求记住(11),(12).4等值演

21、算利用等值定律到已有的公式中而推演出新的公式的过程称为等值演算。5置换规则设 G(G 1)是含子公式 G1 的公式， G(G 2)是用 G2 置换了 G(G 1)之后的公式， 若 G1 G2，则 G(G1) G(G2)2.4全功能联结词集1其他联结词表 2.2PQU00U101U210U311U4设 P，Q 为两个命题元， U 为其对应的联结词， 则 U 作用于 P，Q 后的真值表如表22所示。由组合的意义， U，U ，U ，U的不同真值结果有24 16 种，即从0000 到 1111，1234联结词记号复合命题读法记法真值结果异或G 不可兼或 HG 异或GHAH 为真当县仅当G.H 不同为真

22、H假G 与 H 的蕴涵否定G 蕴涵否定GH 为真当且仅当G为真，H为蕴涵否定HGH假与非G与 H的与非G与非 HG HGH 为假当且仅当G, H 同为真或非G与 H的或非G或非 HG HGH 为真当且仅当G， H 同为假为此除已有的五个联结词以外，还需引入下面四个联结词如表2 3 所示。表中，在逻辑电路中称为异或门，与非门，或非门。2全功能联合词集合设 S 是联结词集合，用S 中的联结词可表示任何的命题公式；且从S 中删除任一个联结词后而得的新联结词集合S1，至少存在一个命题公式不能用S1 中联结词表示。则称S是一个全功能联结词集合。如乛， ， 乛， ， 乛， ， ， 等都是全功能联结词集合。

23、表 2.32.5范式1. 析取范式和合取范式(1) 称命题变元或其否定为文字；(2) 有限个文字的合取称为短语；(3) 有限个文字的析取称为子句；(4) 有限个短词的析取称为析取范式；(5) 有限个子句的合取称为合取范式。求一个公式G 所对应的析取、合取范式一般通过公式的等值演算而得到。2. 主析取范式和主合取范式(1) 在含有 n 个命题变元 P1 , P2, , Pn 的公式中，一个短语或一个子句如果恰当包括所有这 n 个命题变元或其否定，且排列顺序与P1, P2, , Pn 一致，则称此短语或子句为关于P1, P2, , Pn 的一个有小项或极大项。此时极小项有2n 个，极大项也有2n

24、个；(2) 由有限个极小项组成的析取范式称为主析取范式；(3) 由有限个极大项组成的合取范式称为主合取范式。求一个公式G 所对应的主析取、主合取范式可采用真值表技术、公式的等值演算、公式的主析取与主合取范式之间的转换。其中，最方便、最直观、最不易出错的方法是真值表技术。该方法为：设G（ P1, P2, , Pn）是一个公式，建立该公式所对应的真值表。(4) 在真值表中，公式G 取值为真的所有行所对应解释之极小项的析取为该公式G的主析取范式。(5) 在真值表中，公式G 取值为假的所有行所对应解释之极大项的合取为该公式G的主合取范式。 其中，极小项与解释之间的对应为：如 P 值为 0，在极小项中则

25、还原为乛P，如 P 值取 1，在有小项中则还原为1，如 P,Q,R 之解释为010，则对应的有小项为乛P乛 Q乛 R；极大项与解释之间的对应为：如P 取值 0，在极大项中则还原为P，如 P 取值 1，在极大项中则还原为0，如 P,Q,R 之解释为110，则对应的极大项为乛P乛 Q R。3、主要定理(1) 任一命题公式都存在与其等值的析取范式和合取范式；(2) 任一命题公式都存在与其等值的主析取范式和主合取范式；(3) 如果一个命题公式是永真公式它的主析取范式包含所有的极小项，此时无主合取范式或者说主合取范式为空；(4) 如果一个命题公式是永假公式它的主合取范式包含所有的极大项，此时无主析取范式

26、或者说主析取范式为空；(5) 两个命题公式是相等的它们所对应的主析取范式上等和主合取范式相等；(6) 任一公式对应主析取范式包括的极小项的个数加对应主合取范式包括的极大项的个数为 2n。2.6推理理论1. 推理的形式结构设 G1, G2 , , Gn ，H 是命题公式，称G1 G2 Gn H为推理的形式结构， 其中 G1, G2, , Gn 为前提， H 为结论。 当 G1 G2 Gn H 为永真式时， 则此时推理正确， 并称 G1, G2, , Gn 逻辑蕴涵 H 是 G1, G2, , Gn 的逻辑结果，并且记为 G1 G2 Gn H 或记为 G1, G2, , G n H 。说明：G1,

27、 G2, , GnH 仅描述了公式G1, G2, , Gn 与公式 H 之间的逻辑蕴涵关系，G1, G 2, , G nH 本身并不是一个公式，它不能作直接的计算。要判断 G1, G2, , GnH 可采用：G1, G 2, , G nH 当且仅当G1 G2 Gn H 是一个永真公式。2. 判断推理是否正确的方法(1) 真值表法：利用真值表法，可建立如下推理定律：设 G，H ，S 是任意的命题公式，则： 附加定律： G G H ，H G H 化简定律： G HG，GHH 合并定律： G， HGH 假言推理： G， GHH 拒取式： GH，乛 H乛 G 析取三段论：G H， 乛 GH 假言三段论

28、：G H， H SG S 二难推论： G H ，GS， H SS 等价三段论： G?H ； H?SG?S(2) 等值演算法；(3) 主析取（主合取）范式法；(4) 构造证明法。 推理规则：规则 P（前提引入规则） ：在推导的过程中，可以随时引入前提集合中的任一前提及附加前提。规则 T （逻辑结果引用规则） ：在推导的过程中，可以随时引用公式S，该公式S是由其前的一个或多个公式推导出的逻辑结果。规则 P（附加前提规则） ：如果能从给定理前提集合P 与公式 P 推导出 S，则能从此前提集中P 推导出 P S。 直接证明方法： 此证明法是一个描述推理过程的命题公式序列C1, C2, , Cn，其中

29、C1, C2, , Cn 或者为已知的前提和附加前提，或者是由某些前提或中间结论应用推理规则得到的中间结论或结论， Cn 为最终的结论。 间接证明法（反证法或归谬法） ：要证明 G1 , G2, ,GnH，等价地证明G1 , G2, ,Gn， 乛 H R 乛 R，其中 R 可以是任意的公式，此时证明G1, G2, , G n, 乛 HR乛 R即可采取直接证明方法。 带CP 规则的直接证明方法：带CP 规则的证明法主要是针对结论为P S（或 乛P S）的公式十分方便，即要证明G1, G2, , GnPS，等价地证明G1, G2 , , Gn，PS，此时证明 G1, G2, , G n, P S

30、可采用直接证明方法 （此时 P 为附加前提） 。当推出结论 S 后，采用 CP 规则，即可由 G1, , Gn 推出 P S。上述三种方法对命题逻辑中的任何推理问题都是适用的，只是不同的逻辑推理问题采用不同的方法其方便程度不同而已。2.7总结通过本章的学习，应达到下面的基本要求：(1) 要弄清命题与陈述句之间的关系与差别。命题都是陈述句；但陈述句不一定都是命题，只有陈述句所表达的判断结果查惟一确定的，它才是命题；(2) 掌握并能熟练应用6 种基本的联结词（乛， ? ）来对复合命题进行翻译及判断真值；(3) 记住 24 个基本的等价公式，并能熟练地应用到公式的转换中；(4) 会利用真值表技术和公

31、式的演算方法求一公式所对应的主析取范式和主合取范式，并能利用范式判断两公式是否相等，是否为永真式、永假式、可满足式；(5) 掌握并能熟练地应用推理的三种证明方法。命题逻辑例题例 5.1设 P 表示命题“天下雨” ，Q 表示命题“他骑自行车上班”， R 表示命题“他乘公共汽车上班” ，试以符号形式写出下列命题（西南交大1995 年考研试题） ：（ 1）只要不下雨，他才骑自行车上班；（ 2）只要不下雨，他就骑自行车上班；（ 3）除非下雨，否则他就骑自行车上班；（ 4）他或者骑自行上班，或者乘公共汽车上班。分析对于命题只要Q 才 P，只要 P 就 Q，除非所以上述 (1)，(2) ，(3) 分别可翻

32、译为：(1) Q 乛 P， (2)Q，否则 P 等，都可以翻译成PQ，乛 PQ，(3) 乛 QP 。句子 (4) 可翻译为Q R。例 5.2(1) 使用连接词乛，构造三个命题变项P,Q,R 的公式 L （ P,Q,R），使得：乛L （ P,Q,R）=L( 乛 P,Q,R)=L(P,乛 Q,R)=L(P,Q, 乛 R)（ 2）求（ 1）中公式L （ P,Q,R）的主合取范式， （北师大2001 年考研试题） 。7( ai M i )解 (1) 设 L （ P,Q,R）= i 00其中 a i1 ， Mi 为关于P,Q,R 的极大项。7(1a) M i )则乛 L(P,Q,R)=i0L( 乛 P,

33、Q,R)= a0M 4 a1M 5 a2M 6a3M 7 a4M 0 a5M 1 a6M 2a7M 3L(P,乛 Q,R)= a 0M 2 a1M 3 a2M 0a3M 1 a4M 6 a5M 7 a6M 1a7M 2L(P,Q,乛 R)= a 0M 1 a1M 0 a2M 3a3M 2 a4M 5 a5M 4 a6M 7a7M 6由乛 L(P,Q,R)=L( 乛 P,Q,R)=L(P,乛 Q,R)=L(P,Q, 乛 R)对应极大项M i 的系数应相等，为此有：(1 a0)= a4= a2= a1，(1 a4)= a0 = a6= a5(1 a1)= a5= a3= a0，(1 a5)= a1

34、 = a7= a4(1 a2)= a6= a0= a3，(1 a6)= a2 = a4= a7(1 a3)= a7= a1= a2，(1 a7)= a3 = a5= a6所以a0= a3= a5= a6a1= a2= a4= a7如令此时如令此时a0= a3= a5= a6=0，则 a1= a2= a4= a7=1L(P,Q,R)=M 1 M 2 M 4 M 7=乛(乛 M1乛 M2乛 M4乛 M 7)=乛 (乛 (P Q乛 R)乛 (P乛 Q R)乛 (乛 P Q R) 乛 (乛 P乛 Q乛 R)a0= a3= a5= a6=1，则 a1= a2= a4= a7=0L(P,Q,R)=M 0

35、M 3 M 5 M 6=乛 (乛 M 0乛 M 3乛 M 5乛 M 6)=乛 (乛 (P QR)乛 (P乛 Q乛 R)乛 (乛 P Q乛 R)乛 (乛 P乛 Q R)(2) L(P,Q,R)=M 1 M 2 M 4 M 7=(P Q乛 R)乛 (P乛 Q R) (乛 PQR) (乛 P乛 Q 乛 R)主合取范式 =M0M3M5M6=(P Q R)(P乛 Q乛 R) (乛 PQ乛 R) (乛 P乛 Q R) 主合取范式例 5.3 没有命题 P：明天上午七点下雨Q：明天上午七点下雪R：我将去学校符号化下列语句：（ 1）除非明天上午七点不下雨且不下雪，否则我将不去学校；（ 2）只要明天上午七点不下雨

36、或不下雪，我就去学校；（ 3）只有明天上午七点不是雨夹雪，我才去学校；（ 4）明天上午七点我将雨雪无阻一定去学校。分析根据命题PQ 的定义，它可对应语句除非Q，否则乛P；只要 P，就 Q；只有Q 才 P。所以上述（ 1），（2），（ 3）可分别对应符号化为：（ 1） R（乛 P乛 Q）（ 2）乛 P乛 Q R（ 3） R乛（ P Q）句子（ 4）是雨雪无阻一定去学校，即无论任何天气都不影响去学校，即去学校与天气无关，因此，句子（ 4）可简单地符号化为： R但为了完整的表达出该句子的全部意思，应将雨雪无阻符号化。所谓雨雪无阻即是：（ PQ）（乛 PQ）（ P乛 Q）（乛 P乛 Q）所以句子（ 4

37、）完整地符合号为：（ PQ）（乛 PQ）（ P乛 Q）（乛 P乛 Q） R 或 （ PQ R）（乛 PQ R）（ P乛 Q R）（乛 P乛 Q R）说明 由于雨雪无阻与 R 是同时发生，没有因果关系，所以天气与去学校之间用合取。例 5.4 求公式 G1(P， Q， R) (P Q) (PQ)G2(P， Q) (P Q) (P Q)的主析取范式和主合取范式。分析 公式 G1， G2 的右端虽然是相同的，但公式的左岸表明两个公式所含的命题变元不同，在求主析取，主合取范式时，由于其极小项，极大项依赖于命题变元，所以不能仅根据右端的公式来求， 还应该根据该公司所含的命题变元的情况来求。 因此，上述两个

38、公式的主析取范式，主合取范式安全不同。下面采用两种方式来求。方法 1采用真值表技术。建立公式 G1(P，Q， R) (P Q) (P Q)的真值表如表2 4 所示。表 24P，Q， R(PQ) (P Q)000100001100010100011100100000101000110111111111则公式 G1(P， Q，R) 所对应的主析取范式、主合取范分别为：G1（P， Q， R） （ PQ乛 R）（ P Q R）主析取范式G1（P， Q， R） （ PQ R）（ P Q乛 R） (P乛 QR) (P乛 Q乛 R)（乛 PQR）（乛PQ乛 R）主合取范式建立公式 G2(P， Q) （ P

39、Q）（ P Q）的真值表如表2 5 所示。表 25PQ（ P Q）（ P Q）00100011001000011111则公式 G2(P， Q) 所对应的主析取范式、主合取范式分别为：G2（ P， Q）=（ PQ）主析取范式G2（ P， Q）=（ PQ）（乛 P Q）（ P乛 Q）主合取范式方法 2 采用公式转换法。G1（P， Q， R） （ PQ） (P Q) （乛 P Q） P Q P QP Q(乛 RR) （ PQ乛 R）（ PQR）主析取范式G1（P， Q， R） 乛（乛 G1(P， Q， R)）乛（ (P乛 Q R) (乛 P QR) (P乛 Q乛 R) （乛 P Q乛 R）（乛 P乛

40、 Q R）（乛 P乛 Q乛 R）(乛 P Q乛 R)（ P乛 Q乛 R）（乛 P Q R）(乛 P Q R)（ PQ乛 R）（ P Q R）(P Q R)（ P Q乛 R）（ P乛 Q R）（ P乛 Q乛 R） (乛 P Q R)（乛 P Q乛 R）主合取范式G2（P， Q） （ P Q）（ PQ） （乛 PQ） P Q （ P Q）主析取范式G2（P， Q） 乛（乛 G2 (P， Q)） 乛（ (P乛 Q) (乛 P Q)( 乛 P乛 Q)）（乛 P Q）（ P乛 Q）（ P Q）（P Q）（乛 P Q）（ P乛 Q）主合取范式从上可以看出，两个公式的主析取，主合取范式安全不同。例 5.5判

41、断下面公式的类型（重言式，矛质式，可满足式）（ 1）（P Q）（乛Q乛 P）（ 2）（PQ）乛（ P Q）（北师大2000 年考研试题）解 判断一个公式是否是重方式、矛盾式，可满足公式，可采用三种方式：(1)真值表技术； (2)公式等值演算； (3)求主析取，主合取范式。下面分别采用三种方法：方法 1真值表技术。建立公式 (1) ，(2) 的真值表如表2 6 所示。表 26P Q（ P Q）（乛 Q乛 P） （ P Q）乛（ P Q）00111111011110101001001011111100由上述真值可知，公式(1)是重言式，公式(2) 是可满足式。方法 2公式等值演算。 （P Q）（乛

42、Q乛 P） （P Q）乛（ P Q）乛（乛 PQ）（乛P Q） 1所以公式是永真式（重言式）。方法 3求公式的主析取、主合取范式。（ PQ）乛（ PQ） 乛（ PQ）乛（ PQ）乛（ P Q）乛（ Q P）（乛 P乛 Q）乛（乛 PQ）乛（乛QP）（乛P乛 Q）（P乛 Q）（乛 P Q）（乛P乛 Q）主析取范式乛（乛 (PQ)乛 (P Q)）乛（ P Q） （乛 P乛 Q）主合取范式显然公式所对应的主析取范式不包括所有的极小项， 所以不是重言式， 公式所对应的主合取范式不包括所有的极大项，所以不是矛盾式，因此，仅是可满足式。例 5.6符号化下列命题，并证明其结论： 一公安人员审查一件盗窃案，已知事实如下：（ 1）张平或王磊盗窃了机房的计算机一台；（ 2）若张平盗窃了计算机，则作案时间不可能发生在午夜之前；（ 3）若王磊的证词正确，则午夜时机房里的灯未灭；（ 4）若王磊的证词不正确，则作案时间发生在午夜之前；（ 5）午夜时机房灯光灭了。问：盗窃计算机的是张平？王磊？分析首先将事实符号化：设 P：张平盗窃了计算机；Q：王磊盗窃了计算机；R：作案时