《《离散数学》-贾振华-电子教案 第一章》由会员分享，可在线阅读，更多相关《《离散数学》-贾振华-电子教案 第一章（93页珍藏版）》请在金锄头文库上搜索。
1、1,21世纪高等院校规划教材 离散数学,中国水利水电出版社,2,第1章 命题逻辑,1.1 命题命题联结词 1.2 命题公式与解释 1.3 真值表与等价公式 1.4 对偶定理 1.5 范式 1.6 公式的蕴涵 1.7 其它联结词与最小联结词组 1.8 命题逻辑推理理论,3,1.1 命题及其表示法,1.1.1 命题 把具有确定真假意义的陈述句，称为命题。 如果一个句子是命题，必需满足以下条件： （1）该句子是具有判断性的陈述语句； （2）它有确定的真值，非真即假。,4,1.1 命题及其表示法,例1.1.1 判断下列语句是否为命题，若是命题，判断其真值。 （1）10是素数。 （2）f（x）= x2在
2、a，b上连续。 （3）北京是中国的首都。 （4）1001+11=1100 （5）请勿喧哗！ （6）你记住了吗？ （7）这个风景真美呀！ （8）x+y=7,5,1.1 命题及其表示法,由于命题只有真、假二个真值情况，所以命题逻辑也称为二值逻辑。 例1.1.2 判断下面语句是否为命题。 （1）其它星球上有生命存在。 （2）我正在说谎。,6,1.1 命题及其表示法,命题通常使用大写字母A，B，Z或带下标的大写字母或数字表示，如Ai，10，R等，例如 A1：我是一名大学生。 A1:我是一名大学生. 10：我是一名大学生。 R：我是一名大学生。 表示命题的符号称为命题标识符，A1、10和R都是标识符。,
3、7,1.1 命题及其表示法,命题常量 命题变元 原子变元,8,1.1.2 命题联结词,1 否定联结词 2 合取联结词 3 析取联结词 4 条件联结词 5 双条件联结词,9,1.1.2 命题联结词,1 否定联结词P,3 析取联结词,2 合取联结词,10,4 条件联结词,5 双条件联结词,1.1.2 命题联结词,11,1.2 命题公式与解释,1.2.1 命题公式 1.2.2 命题公式的解释,12,1.2.1 命题公式,1.定义 命题公式，简称公式，定义为： （1）命题变元是公式； （2）如果P是公式，则P是公式； （3）如果P、Q是公式，则PQ、PQ、PQ、 PQ都是公式； （4）当且仅当能够有限
4、次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号 串是才是公式。,13,命题公式是由命题变元、联结词和括号组成的，但并非由命题变元、联结词和括号组成的符号串都能成为命题公式。 例如，下面的符号串都是公式： （P）Q）R）S） （PQ）（RS） （PQ）R 以下符号串都不是公式： （PQ）（Q） （Q）,1.2.1 命题公式,14,2. 命题的符号化 可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译,也称为符号化。 命题翻译时应注意下列事项： （1）确定所给句子是否为命题。 （2）句子中联结词是否为命题联结词。 （3）要正确的选择原子命题和合适的命
5、题联结词。 （4）用正确的语法将原命题表示由原子命题、联结词和圆括号组成的合式公式。,1.2.1 命题公式,15,例1.2.1 将下列命题符号化。 （1）张莉既聪明又好学。 （2）张莉虽然聪明但不好学。 （3）仅当你走，我将留下。 （4）上海到北京的14次列车是下午五点半或六点开。,1.2.1 命题公式,16,解：设P：张莉聪明；Q：张莉好学，则 （1）张莉既聪明又好学，可符号化为PQ； （2）张莉虽聪明但不好学，可符号化为P（Q）。 （3）设P：你走；Q：我留下；这句话中“你走”是“我留下”的必要条件。因此命题可表示为QP。 （4）设P：上海到北京的14次列车是五点半开；Q：上海到北京的14
6、次列车是六点开；,1.2.1 命题公式,17,汉语的意思是不可兼或，而逻辑联结词是“可兼或”，因此不能直接对两个命题析取。构造表如表1.2-1所示。,18,例1.2.2 将下列命题符号化。 （1）假如上午不下雨，我去看电影，否则就在家里读书或看报。 （2）我今天进城，除非下雨。 （3）张三或李四都可以做这件事。 （4）除非你努力，否则你将失败。 （5）如果你和她都不固执己见的话，那么不愉快的事也不会发生了。 （6）如果你和她不都是固执己见的话，那么不愉快的事也不会发生了。,1.2.1 命题公式,19,解：（1）设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。本命题可表示为：
7、（PQ）（P（RS）。 （2）设P：我今天进城；Q：今天下雨； 这句话的意思是“如果今天不下雨，那么我就进城”，本可表示为QP。 （3）设P：张三可以做这件事；Q：李四可以做这件事。这个命题可以理解为：张三可以做这件事，并且李四也可以做这件事。因此原命题可符号化为：PQ。,20,（4）设P：你努力；Q：你将失败。原命题可符号化为：PQ。 （5）设P：你固执己见；Q：她固执己见；R：不愉快的事也不会发生。原命题可符号化为：（PQ） R。 （6）设P：你固执己见；Q：她固执己见；R：不愉快的事也不会发生。原命题可符号化为：（PQ） R。,21,定义 设G是命题公式， P1，P2，Pn是出现在命题公
8、式G中的全部命题变元，指定P1，P2，Pn的一组真值，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作TI（G）。,例如，G=（PQ）R，则I： P Q R 1 1 0 是G的一个解释，在这个解释下G的真值为1，即TI（G）=1。,1.2.2 命题公式的解释,22,例1.2.3 给命题变元P、Q、R、S分别指派的真值为1、1、0、0，求下列命题公式的真值： （1）（PQ） R）（PQ） R）S） （2）（P（Q（R P）（Q S）,1.2.2 命题公式的解释,23,解：将P、Q、R、S的真值代入公式，有 （1）（PQ） R）（PQ） R）S） （11）0）（11） 0）0） （0
9、1）（01）0） 00 0,1.2.2 命题公式的解释,24,（2）（P（Q（R P）（Q S） （1（1（0 1）（1 0） （10）1 11 1,1.2.2 命题公式的解释,25,1.3 真值表与等价公式,1.3.1 真值表 1.3.2 命题公式的分类 1.3.3 等价公式 1.4.4 带入规则和替换规则,26,1.3.1 真值表,定义 将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。,构造真值表的方法如下： （1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，Pn。 （2）列出G的2n个解释，赋值从000（n个）开始，按二进制递加顺序依次写出各赋值，直到111
10、为止（或从111开始，按二进制递减顺序写出各赋值，直到000为止），然后从低到高的顺序列出G的层次。 （3）根据赋值依次计算各层次的真值并最终计算出G的真值。,1.3 真值表与等价公式,27,1.3 真值表与等价公式,例1.3.1 求下列公式的真值表。 （1）G1=（PQ）（PQ） （2）G2=（PQ）（PQ） （3）G3=（PQ）Q,28,表1.3-1,29,1.3 真值表与等价公式,1.3.1 真值表 例：G=（ PQ ）Q,30,表1.3-2,31,表1.3-3,32,1.3.2 命题公式的分类 定义 设G为公式： （1）如果G在所有解释下取值均为真，则称G是永真式或重言式； （2）如果
11、G在所有解释下取值均为假，则称G是永假式或矛盾式； （3）如果至少存在一种解释使公式G取值为真，则称G是可满足式。,1.3 真值表与等价公式,33,例1.3.2 写出下列公式的真值表，并验证其是何种公式。 （1）G1=（PQ）（PQ） （2）G2=（PQ ）P）Q） （3）G3=P（QR）,1.3 真值表与等价公式,34,表1.3-4,35,表1.3-5,36,表1.3-6,37,1.3 真值表与等价公式,1.3.3 等价公式 定义 设S和T是两个命题公式，如果S和T在任意解释I下，都具有相同的真值，则称S和T是等价公式。记为ST。,性质： 定理1.3.1 对于命题公式S和T，ST的充分必要条
12、件是：公式S T是永真式。,38,定理1.3.2 设A、B、C是公式，则有下列性质成立： （1）自反性 AA （2）对称性 若AB则BA （3）传递性 若AB且BC则AC,1.3 真值表与等价公式,39,1.3 真值表与等价公式,定理1.3.3 设A、B、C是公式，则下述等价公式成立： （1）双重否定律 AA （2）等幂律 AAA ； AAA （3）交换律 ABBA ； ABBA （4）结合律 （AB）CA（BC） （AB）CA（BC） （5）分配律 （AB）C（AC）（BC） （AB）C（AC）（BC） （6）德摩根律 （AB）AB （AB）AB,40,1.3 真值表与等价公式,（7）吸收律
13、 A（AB）A；A（AB）A （8）零一律 A11 ； A00 （9）同一律 A0A ； A1A （10）排中律 AA1 （11）矛盾律 AA0 （12）蕴涵等值式 ABAB （13）假言易位 ABBA （14）等价等值式 AB（AB）（BA） （15）等价否定等值式 ABABBA （16）归缪式 （AB）（AB）A,41,1.3 真值表与等价公式,1.3.4 代入规则和置换规则 定理1.3.4（代入规则） 设G（P1，P2，Pn）是一个命题公式，其中：P1，P2，Pn是命题变元，G1（P1，P2，Pn），G2（P1，P2，Pn），Gn（P1，P2，Pn）为任意的命题公式，此时若G是永真式或永
14、假式，则用G1代替P1、G2代替P2、Gn代替Pn后，而得到的新的命题公式： G（P1，P2，Pn）= G（ P 1，P2，Pn） 也是一个永真公式或永假公式。,42,1.3 真值表与等价公式,定理1.3.5（替换规则） 设（P）是一个含有子公式P的命题公式，（Q）是用公式Q置换了（P）中的子公式P后得到新的命题公式，如果P Q，那么（P）（Q）。,43,1.4 对偶定理,1.4.1 对偶 定义1.4.1 设A是仅含有联结词、的命题公式，将联结词换成，将换成， 0换成1，1换成0，所得的命题公式A*称为A的对偶公式。,44,1.4 对偶定理,定理1.4.1 设A和A*互为对偶式，P1，P2，P
15、n是出现在A和A*中的所有原子变元，则 （1）A（P1，P2，Pn）A*（P1，P2，Pn） （2）A（P1，P2，Pn）A*（P1，P2，Pn）,45,1.4 对偶定理,定理1.4.2 （对偶定理）设A、B是两个命题公式，若AB，则A*B*，其中A*、B*分别为A、B的对偶式。,46,1.5 范式,1.5.1 合取范式和析取范式 1.5.2 主析取范式和主合取范式,47,1.5 范式,1.5.1 合取范式和析取范式 定义1.5.1 由有限个命题变元及其否定构成的析取式称为简单析取式，仅由有限个命题变元及其否定构成的合取式称为简单合取式。 定义1.5.2 由有限个简单合取式构成的析取式称为析取范式。由有限个简单析取式构成的合取式称为合取范式。 定理1。5。1 （范式存在定理）任何命题
