湖南大学离散数学教案命题逻辑演示课件.ppt

第一章第一章 命题逻辑命题逻辑杨圣洪杨圣洪13007432216引言引言 逻辑学逻辑学是推理的基础，在是推理的基础，在社会学社会学、自然科学自然科学尤其计算机学科中得到普遍应用。尤其计算机学科中得到普遍应用。数理逻辑数理逻辑是逻辑学的一个分支，也是数学的分是逻辑学的一个分支，也是数学的分支，它用数学方法研究推理规律，它采用符号的支，它用数学方法研究推理规律，它采用符号的方法来描述和处理思维形式、思维过程和思维规方法来描述和处理思维形式、思维过程和思维规律，它在律，它在程序设计程序设计、数字电路数字电路设计、设计、计算机计算机原理、原理、人工智能人工智能等计算机课程得到了广泛应用。等计算机课程得到了广泛应用。命题逻辑命题逻辑是是数理逻辑数理逻辑的基础部分，的基础部分，但究竟什么是但究竟什么是命题命题？如何如何表示表示命题？命题？如何如何构造构造出复杂的命题？出复杂的命题？在本章将在本章将讨论讨论这些问题。这些问题。1.1 命题及联结词命题及联结词 对错对错确定确定的的陈述语句陈述语句称为命题称为命题。如：。如：(1)湖南大学是一本学校。湖南大学是一本学校。(2)命题逻辑是计算机科学的基础课程。命题逻辑是计算机科学的基础课程。(3)命题及联结词是命题逻辑的最基础的内容。命题及联结词是命题逻辑的最基础的内容。(4)4是素数。是素数。(5)湖南大学坐落于湘江以东。湖南大学坐落于湘江以东。(6)2011年湖南长沙轻轨通车。年湖南长沙轻轨通车。其中其中(1)、(2)、(3)与事实相符，是对的、正确的，称为与事实相符，是对的、正确的，称为真命题真命题，或者称命题的值为，或者称命题的值为“真真”，简记为，简记为T或数字或数字1。而而(4)、(5)明显与事实不相符，是错的、不正确，称为明显与事实不相符，是错的、不正确，称为假假命题命题，或称命题的值为，或称命题的值为“假假”，简记为，简记为F或数字或数字0。陈述句陈述句(6)的正确性，到的正确性，到2011年年12月时能确定的，若届月时能确定的，若届时开通了则它是对的、为真命题，否为假命题。时开通了则它是对的、为真命题，否为假命题。1.1 命题及联结词命题及联结词 对错对错确定确定的的陈述陈述语句称为命题语句称为命题。如：。如：(7)x与与y之和为之和为100，其中，其中x为整数，为整数，y为整数为整数 (8)1加加1等于等于10 (7)的对错的对错不确定不确定的。当的。当x为为50、y为为50时是对的，当时是对的，当x为为51、y为为52时是错的。时是错的。(8)的对错是的对错是不确定不确定的，为二进制时正确，当为八进制、的，为二进制时正确，当为八进制、十进制时是错的，因此这两个陈述句十进制时是错的，因此这两个陈述句不是命题不是命题。(9)岳麓山的红叶真美呀！岳麓山的红叶真美呀！(10)动作快点！动作快点！(11)你是离散数学老师吗？你是离散数学老师吗？这三个语句这三个语句不是陈述语句不是陈述语句，因此不是命题。，因此不是命题。1.1 命题及联结词命题及联结词 对错对错确定确定的的陈述陈述语句称为命题语句称为命题。如：。如：(12)我在说假话。我在说假话。(13)我只给自己不能理发的人理发。我只给自己不能理发的人理发。(14)派出所说派出所说:必须先房子再能上户口必须先房子再能上户口 单位后勤说单位后勤说:必须先有户口才能分房必须先有户口才能分房 你能上到户口与要到房子吗你能上到户口与要到房子吗?这是一个悖论，其真值不能确定，故不是命题。这是一个悖论，其真值不能确定，故不是命题。1.1 命题及联结词命题及联结词 对错对错确定确定的的陈述陈述语句称为命题语句称为命题。如：。如：(13)我既要学程序设计，又要学离散数学。我既要学程序设计，又要学离散数学。(14)我们早餐在公寓食堂或外面早点摊上吃。我们早餐在公寓食堂或外面早点摊上吃。(15)我不是数学院的学生我不是数学院的学生 这三个陈述句都与事实相符，是对的，是真命这三个陈述句都与事实相符，是对的，是真命题，其值为真题，其值为真(T/1)。其中其中(13)与与(14)可分解为另外二句话的组合，可分解为另外二句话的组合，而而(15)是对是对“我是数学院学生我是数学院学生”的否定，这些的否定，这些语句称为语句称为“复合命题复合命题”，不能再分解的语句称为，不能再分解的语句称为“简单命题简单命题”或或“原子命题原子命题”，为了便于推理与，为了便于推理与书写，常用书写，常用小写字母小写字母表示表示简单命题简单命题或或原子命题原子命题。1.1 命题及联结词命题及联结词 简单命题简单命题组合成组合成复杂命题复杂命题时所使用的辅助词称时所使用的辅助词称为为“联结词联结词”。命题逻辑中的联结词归纳为以下命题逻辑中的联结词归纳为以下5种。种。合取合取：C语言中语言中&and 并且并且 析取析取：C语言中语言中|or 或或 否定否定：C语言中语言中!not 非非,不是不是,否定否定 条件式条件式：C语言中语言中 if()如果如果那么那么 如如p则则q 双条件式双条件式：如如p则则q且如且如q则则p,当且仅当当且仅当1.1 命题及联结词命题及联结词 定义定义1.1合取合取：当当p、q都对都对，即取值为真，即取值为真(T或或1)时，时，“p合取合取q”的值为的值为真真.1.1 命题及联结词命题及联结词 定义定义1.1合取合取：当当p、q都对都对，即取值为真，即取值为真(T或或1)时，时，“p合取合取q”的值为的值为真真，其他情况为，其他情况为假假。逻辑运算符逻辑运算符“合取合取”，与汉语中与汉语中“并且、并且、而且、同时而且、同时”含义相含义相当当1.1 命题及联结词命题及联结词 定义定义1.2析取析取：当当p、q都不对都不对，即取值为假，即取值为假(F或或0)时，时，“p析取析取q”的值为的值为假假，其他情况为，其他情况为真真。逻辑运算符逻辑运算符“析取析取”，与汉语中与汉语中“或或”含含义相当，但有细微的义相当，但有细微的区别区别1.1 命题及联结词命题及联结词 逻辑运算符逻辑运算符“析取析取”与汉语的与汉语的“或或”几乎一致但有区几乎一致但有区别：别：(16)“讲离散数学的老师是杨老师或刘老师讲离散数学的老师是杨老师或刘老师”，可以表，可以表示为示为“讲离散数学的老师是杨老师讲离散数学的老师是杨老师”“讲离散数学的讲离散数学的老师是刘老师老师是刘老师”，这两个原子命题有可能，这两个原子命题有可能都是对都是对的，这的，这种种“或或”称为称为“可同时为真的或可同时为真的或”，或简称为，或简称为“可兼或可兼或”。(17)“离散数学的教室是离散数学的教室是102或或302”，不可以不可以表示为表示为“离离散数学的教室是散数学的教室是102”“离散数学的教室是离散数学的教室是302”，因为，因为这两个原子命题这两个原子命题不可能都对不可能都对，只能这二种情况之一，这，只能这二种情况之一，这种种“或或”称为称为“不可同时为真的或不可同时为真的或”，或简称为，或简称为“不可不可兼或兼或”、“排斥或排斥或”.这种这种“或或”表示表示不能简单不能简单表示为表示为“析取析取”，需要联合，需要联合使用下面将要介绍的使用下面将要介绍的“否定否定”与与“析取析取”符号，才能准符号，才能准确表达。确表达。1.1 命题及联结词命题及联结词 定义定义1.3否定否定:当当p是是1，p的否定的否定 p即为即为0。逻辑运算符逻辑运算符“否定否定”，与汉语中与汉语中“否定否定”含义相当含义相当.“我不是数学院的学生我不是数学院的学生”可表示为可表示为“我是数学院的学生我是数学院的学生”“离散数学的教室是离散数学的教室是102或或302”,表示表示离散数学的教室是离散数学的教室是102不是不是302或或离散数学的教室是离散数学的教室是302不是不是102p:离散数学的教室是离散数学的教室是102q:离散数学的教室是离散数学的教室是302上面的语句表示上面的语句表示:(p q)(p q)1.1 命题及联结词命题及联结词 定义定义1.4条件条件:当当p是是1,q是是0时时,pq为为0,即即10为为0,其他情况为其他情况为1。逻辑运算符逻辑运算符“如果如果那么那么”，它是用它是用单个运算符表示一个复合语句。单个运算符表示一个复合语句。如老妈说：如老妈说：“如果期终考了年级前如果期终考了年级前10名，那么奖励名，那么奖励1000元元”。p:期终考了年级前期终考了年级前10名名 q:奖励奖励1000元元则上面的语句表示为则上面的语句表示为pq。当当p为为1即即“期终考了年级前期终考了年级前10”，且且q为为0即即“没有奖励没有奖励1000元元”这时老妈的话是假话空话，这时老妈的话是假话空话，故故pq为为01.1 命题及联结词命题及联结词 定义定义1.4条件式条件式(蕴含式蕴含式):当当p是是1,q是是0时时,pq为为0,即即10为为0,其他情况为其他情况为1。p为前件为前件,q为后件为后件 (1)当当p为为1即即“我期终考了年级前我期终考了年级前10”q为为0即即“我老妈没有奖励我老妈没有奖励1000元元”这时老妈的话为假，即这时老妈的话为假，即pq为为0(2)当当p为为1即即“我期终考了年级前我期终考了年级前10”q为为1即即“我老妈奖励我老妈奖励1000元元”这时妈妈的话就对了，即这时妈妈的话就对了，即pq为为1 (3)至于至于p为为0即即“我期终考了年级不是前我期终考了年级不是前10”时时,无论无论q为为1或为或为0，即无论，即无论我老妈我老妈奖奖励励1000元元或或不奖励不奖励，都不能说老妈的话，都不能说老妈的话是是假的假的，故可，故可善意善意的认为的认为pq为为1均为均为11.1 命题及联结词命题及联结词 定义定义1.5双条件双条件:当当p与与q值相同值相同0时时,pq为为1,不同不同为为0。称称p与与q的等价式的等价式 “我明年赚了我明年赚了10万当且仅当我买彩万当且仅当我买彩票中了大奖票中了大奖”，可以表示为可以表示为“我明年赚了我明年赚了10万万我买彩票中了大奖我买彩票中了大奖”1.2公式及其赋值公式及其赋值 对错明确的陈述语句称为对错明确的陈述语句称为命题，其真值确定，又称为命题，其真值确定，又称为命题常元命题常元或或命题常项命题常项，相当于初等数学中的，相当于初等数学中的“常数常数”。数学的运算符号为数学的运算符号为“加加+、减、减-、乘、乘x、除、除、幂、幂”，命题逻辑的符号命题逻辑的符号“合取合取、析取、析取、否定、否定、条件、条件、双、双条件条件”数学中用数学中用变量变量x表示表示某些数某些数，如，如x2+x+10是代数式，是代数式，命题逻辑命题逻辑用用变量变量表示表示任意一个命题任意一个命题，如，如p,q,r,这时由符这时由符号与变量所构成命题表达式，简称为号与变量所构成命题表达式，简称为“命题公式命题公式”。代数式的书写有规律，命题公式也有规律与约束，称代数式的书写有规律，命题公式也有规律与约束，称满足这些规则的公式为满足这些规则的公式为“合式公式合式公式”，也称为，也称为“命题公命题公式式”，简称为，简称为“公式公式”。1.2公式及其赋值公式及其赋值定义定义1.2.1 合式公式的生成规则合式公式的生成规则(1)单个单个命题变元、命题常元为合式公式命题变元、命题常元为合式公式(原子公式原子公式)。(2)若若A是是合式公式合式公式，则，则 A、(A)也是合式公式。也是合式公式。(3)若若A、B是是合式公式合式公式，则，则A B、A B、AB、AB是合式公式。是合式公式。(4)有限次使用有限次使用(2)(3)形成的字符串均为形成的字符串均为合式公式合式公式。如如：(p 1)q是合式公式。是合式公式。因为因为p、1是合公式，则是合公式，则(p 1)是合式公式，而是合式公式，而r是合式是合式公式，故公式，故(p 1)q是合式公式。是合式公式。(p 1)r不是合式公式。不是合式公式。因为因为p、1是合公式，则是合公式，则(p 1)是合式公式，而是合式公式，而r是合式是合式公式，但公式，但(p 1)r不是合法公式。不是合法公式。1.2公式及其赋值公式及其赋值 对于代数式对于代数式x2+y+10，当，当x与与y的值不确定时，该的值不确定时，该代数式的值是不确定的。代数式的值是不确定的。对于公式对于公式(p 1)q，由于，由于p与与q值不确定时，公式值不确定时，公式(p 1)q的值不确定，因而不是命题。的值不确定，因而不是命题。只有当只有当p与与q的值确定后，公式的值确定后，公式(p 1)q的值才能的值才能确定，我们可能像表确定，我们可能像表1.2到表到表1.5一样，给出公式在一样，给出公式在各种情况下的取值，即得到这个公式的真值表。各种情况下的取值，即得到这个公式的真值表。p与与q每一种取值称每一种取值称为为p、q的一种解释的一种解释1.2公式及其赋值公式及其赋值 公式公式(p q)、pq的真值表如下表的真值表如下表。真值表的构造方法真值表的构造方法：(1)命题变元命题变元的取值从全的取值从全0开始，依次加开始，依次加1，直到全，直到全1，当有，当有n个变元时，则共个变元时，则共有有2n种不同的取值情况。种不同的取值情况。(2)分步骤分步骤计算公式的值计算公式的值(3)见见黑板黑板上写上写成真赋值成真赋值:如如pq为为(0,0),(0,1),(1,1)成假赋值成假赋值:如如pq为为(1,0)1.2公式及其赋值公式及其赋值 公式公式(pq)(qp)、pq的真值表的真值表。无论无论p/q取何值，这两个公式的值总取何值，这两个公式的值总相等。相等。1.2公式及其赋值公式及其赋值 公式公式 (p q)、p q的真值表的真值表。无论无论p/q取何值，这两个公式的值总取何值，这两个公式的值总相等。相等。1.2公式及其赋值公式及其赋值 公式公式pq、p q的真值表的真值表。无论无论p/q取何值，这两个公式的值总取何值，这两个公式的值总相等。相等。11.2公式及其赋值公式及其赋值 公式公式pq、q p的真值表的真值表。无论无论p/q取何值，这两个公式的值总取何值，这两个公式的值总相等，若前者称为原命题，后者为逆否相等，若前者称为原命题，后者为逆否命题命题11.2公式及其赋值公式及其赋值 公式公式p(q r)、(p q)(p r)的真值的真值表表。无论无论p/q取何值，这两个公式的值，与前面各例取何值，这两个公式的值，与前面各例不同，此表是将运算结果写在联结词的下方！不同，此表是将运算结果写在联结词的下方！1.3 等值式等值式一、复习一、复习 由前节可知：由前节可知：pq与与 p q、q p pq与与(pq)(qp)、(p q)(p q)(p q)与与 p q p(q r)、(p q)(p r)的真值表完全一样，称为等值。的真值表完全一样，称为等值。定义定义1.3.1 设设A、B是两个合法的命题公式，无论是两个合法的命题公式，无论其中的命题变元取何值，这两个公式的总相等，其中的命题变元取何值，这两个公式的总相等，称为两个公式等值，记为称为两个公式等值，记为AB 由定义及前节习题有：由定义及前节习题有：(1)pqp qqp条件式的等值式条件式的等值式(2)pq(pq)(qp)(p q)(pq)双条件双条件(3)pp 双重否定律双重否定律(4)pp pp p幂等律幂等律(5)p q q p，p q q p 交换律交换律(6)p(q r)(p q)r 结合律结合律 p(q r)(p q)r(7)p(q r)(p q)(p r)分配律分配律 p(q r)(p q)(p r)(8)p(p r)p吸收律吸收律(多吃少多吃少)p(p r)p(9)(p q)pq德摩律德摩律 (p q)pq 将以上等值式中的变元换成合式公式仍等值！将以上等值式中的变元换成合式公式仍等值！如：如：pq p q 则有则有 AB A B 尽管尽管A/B可能很复杂，但是公式值也只有可能很复杂，但是公式值也只有0、1二二种种可能，公式可能，公式A/B的组合只有的组合只有0/0,0/1,1/0,1/1四种，四种，如下表所示如下表所示 显然有显然有 AB A B 置换规则置换规则：当将公式：当将公式A中的子公式中的子公式B换成换成C得到得到公式公式D后，若后，若BC，那么，那么AD。因为因为A、D除了除了“A中中B所在之处、所在之处、D中中C所在之所在之处处”外，其他地方均相同，而不同之处的外，其他地方均相同，而不同之处的B与与C等等值，所以公式值，所以公式A、公式、公式D的真值表应该完全他相同的真值表应该完全他相同，故，故AD。当将一个公式的当将一个公式的局部进行等值局部进行等值替换后，替换后，仍与仍与原公式原公式等值，这也是数学中最常见的方法，等值，这也是数学中最常见的方法，不断对不断对局部进行等值替换局部进行等值替换的操作，称为的操作，称为“等值演等值演算算”。利用该规则及前述的等值式，可进行等值演算，利用该规则及前述的等值式，可进行等值演算，从而推导出新的公式。从而推导出新的公式。求证求证(p q)r(pr)(qr)(p q)r(p q)r 条件式的等值式条件式的等值式(pq)r 利用德摩律利用德摩律 r (pq)交换律交换律(rp)(rq)分配律分配律(p r)(q r)交换律交换律(pr)(qr)条件式等值式条件式等值式等值演算的基本套路等值演算的基本套路 (1)转换转换：ABA B (2)恰当转换恰当转换：AB(A B)(AB)(A B)(AB)确保公式只保留确保公式只保留 联结词联结词 (3)否定到底否定到底：A,(A B),(A B)(4)恰当使用分配律、吸收律。恰当使用分配律、吸收律。利用等值演算，判断公式的类型利用等值演算，判断公式的类型(pq)p)q(pq)p)q(p q)p)q (条件式的等值式条件式的等值式)(p q)p)q (条件式的等值式条件式的等值式)(p q)p)q (德摩律德摩律)(pq)p)q (德摩律德摩律)(pq)(p q)(结合律结合律)(pq)(pq)(逆用德摩律逆用德摩律)AA (A=(pq)1 称为永真式或重言式，即利用等值演算，可以判断公式的类型。利用等值演算判断公式类型利用等值演算判断公式类型：(p(p q)r解：解：(p(p q)r(p(p q)r (条件式的等值式条件式的等值式)(p p)q)r (结合律结合律)(1 q)r (析取的性质即析取定义真值表析取的性质即析取定义真值表)1 r (析取的性质即析取定义真值表析取的性质即析取定义真值表)0 r (否定的定义否定的定义)0 (析取的性质即析取定义真值表析取的性质即析取定义真值表)永假式或矛盾式。永假式或矛盾式。问题问题：尽管有套路可行，但是随意性还是比较大，：尽管有套路可行，但是随意性还是比较大，能否有某种方式肯定能成功呢？能否有某种方式肯定能成功呢？1.4 析取范式与合取范式析取范式与合取范式 文字文字：命题变项：命题变项(变元变元)及其否定称为文字及其否定称为文字.如如:p,q,r,p,q,r 简单析取式简单析取式:仅由有限个仅由有限个文字文字构成的析取式构成的析取式.如如:p q,p q,pq,p q,p q r 简单合取式简单合取式:仅由有限个仅由有限个文字文字构成的合取式构成的合取式.如如:p q,p q,pq,pq,p q r定理定理：简单：简单析取析取式与简单式与简单合取式合取式 (1)一个简单析取式一个简单析取式Ai是重言式是重言式 含有某个命题变元及其否定式，如含有某个命题变元及其否定式，如Ai=p p (2)一个简单合取式一个简单合取式Ai是矛盾式是矛盾式 含有某个命题变元及其否定式，如含有某个命题变元及其否定式，如Ai=p p 1.4 析取范式与合取范式析取范式与合取范式析取范式析取范式：由有限个：由有限个简单合取简单合取式的式的析取析取构成的构成的命命题公式题公式称为称为析取范式析取范式。总体是总体是析取析取式式，每对括号内是，每对括号内是合取合取式式 A=(p q)(p r)合取范式合取范式：由有限个：由有限个简单析取简单析取式的式的合取合取构成的构成的命命题公式题公式称为称为合取范式合取范式。总体是总体是合取合取式式，每对括号内是，每对括号内是析析取式取式 A=(p q)(p r)1.4 析取范式与合取范式析取范式与合取范式 总体是总体是析取析取式式，每对括号内是，每对括号内是合取合取式式 A=(p q)(p r)析取范式析取范式 总体是总体是合取合取式式，每对括号内是，每对括号内是析析取式取式 A=(p q)(p r)合取范式合取范式定理定理：析取范析取范式与式与合取范式合取范式 (1)一个一个析取范式析取范式A是矛盾式是矛盾式 每个简单合取式是矛盾式。每个简单合取式是矛盾式。A=(p q)(p r)(2)一个一个合取范式合取范式A是重言式是重言式 每个简单析取式是重言式。每个简单析取式是重言式。A=(p q)(p r)1.4 析取范式与合取范式析取范式与合取范式 (1)转换转换：ABA B (2)恰当转换恰当转换：AB(A B)(AB)(A B)(AB)(3)否定到底否定到底：A,(A B),(A B)(4)适当使用分配律：适当使用分配律：A(B C),A(B C).经过第经过第1 1步、第步、第2 2步转换后，公式中只有步转换后，公式中只有、三种运算符。三种运算符。经过第经过第3 3步后，步后，从括号外深入到变元的前面，从括号外深入到变元的前面，与变元结合成文文字，文字之间只有与变元结合成文文字，文字之间只有、。1.4 析取范式与合取范式析取范式与合取范式求求(pq)r的析取范式、合取范式的析取范式、合取范式解：解：(1)求析取范式求析取范式。即外层是。即外层是，内层是，内层是，所以，所以转换模式为转换模式为AB(A B)(AB)(pq)r(pq)r)(pq)r)(整体为析取整体为析取)(p q)r)(p q)r)(ABA B)(p q)r)(pq)r)(德摩律德摩律)(p r)(q r)(pq)r)(分配律分配律)(p r)(q r)(pq r)(结合律结合律)1.4 析取范式与合取范式析取范式与合取范式解：解：(1)求合取范式求合取范式。所以所以转换模式为转换模式为AB(A B)(AB)(pq)r(pq)r)(pq)r)(整体为合取整体为合取)(p q)r)(p q)r)(条件等价式条件等价式)(pq)r)(p q)r)(德摩律德摩律)(p r)(q r)(p q)r)(分配律分配律)(p r)(q r)(p q r)(结合律结合律)1.4 析取范式与合取范式析取范式与合取范式小项小项：在含有：在含有n个变元的个变元的简单合取式简单合取式中中,每个每个命题命题变元或其否定变元或其否定仅出现仅出现一次一次,且各变元按其字母顺序且各变元按其字母顺序出现出现,则该简单合取式为则该简单合取式为(极极)小项小项。如：如：p q r,pq r,p qr,p q r (p r),(q r)非小项非小项大项大项：在含有：在含有n个变元的个变元的简单析取式简单析取式中中,每个每个命题命题变元或其否定变元或其否定仅出现仅出现一次一次,且各变元按其字母顺序且各变元按其字母顺序出现出现,则该简单析取式为则该简单析取式为(极极)大项大项。如：如：p q r,pq r,p qr,p q r(p r),(q r)非大项非大项THANK YOUSUCCESS2024/5/8 周三43可编辑1.4 析取范式与合取范式析取范式与合取范式主析取范式主析取范式：一个析取范式中，如果所有：一个析取范式中，如果所有简单合简单合取式取式均为均为(极极)小项，小项，则称则称为主析取范式为主析取范式。(pq)r(p r)(q r)(pq r)不是不是(p q r)(p q r)(p q r)(pqr)是主析取范是主析取范式式1.4 析取范式与合取范式析取范式与合取范式主合取范式主合取范式：一个合取范式中，如果所有：一个合取范式中，如果所有简单析简单析取式取式均为均为(极极)大项，大项，则称为主合取范式。则称为主合取范式。(pq)r(p r)(q r)(p qr)不是不是(p q r)(p q r)(pq r)(p qr)是主合取范式是主合取范式 1.4 析取范式与合取范式析取范式与合取范式获取方法获取方法 通过转换联结词通过转换联结词、“到底到底”及及适当适当使用使用分配律，可以得到分配律，可以得到合取合取范式与范式与析取析取范式，这时可范式，这时可能还缺少某个变元，能还缺少某个变元，因为因为pp1，1 r1，可在缺少变元的可在缺少变元的小小项项中加入形如中加入形如“pp”的公式。的公式。如小项如小项(p r)缺少变元缺少变元q q，加入，加入q qq q，即，即 p rp 1 rp(qq)r(p q r)(pq r)。1.4 析取范式与合取范式析取范式与合取范式获取方法获取方法 通过转换联结词通过转换联结词、“到底到底”及及适当适当使用分配律，使用分配律，可以得到可以得到合取合取范式与范式与析取析取范式，这时可能还缺少某个变范式，这时可能还缺少某个变元，元，因为因为pp1，1 r1，可在缺少变元的可在缺少变元的小项小项中加中加入形如入形如“pp”的公式。的公式。(pq)r(p r)(q r)(pqr)(p(qq)r)(pp)q r)(pqr)(p q r)(pq r)(p q r)(p q r)(pqr)(p q r)(pq r)(p q r)(pqr)1.4 析取范式与合取范式析取范式与合取范式获取方法获取方法 通过转换联结词通过转换联结词、“到底到底”及及适当适当使用使用分配律，可以得到分配律，可以得到合取合取范式与范式与析取析取范式，这时可范式，这时可能还缺少某个变元，能还缺少某个变元，因为因为p pp p0 0，0 0 p pp p，可在缺少变元的，可在缺少变元的大大项项中加入形如中加入形如“p pp p”的公式的公式 。如如p rp 0 rp(qq)r(p q r)(pq r)1.4 析取范式与合取范式析取范式与合取范式获取方法获取方法 通过转换联结词通过转换联结词、“到底到底”及及适当适当使用分配律，使用分配律，可以得到可以得到合取合取范式与范式与析取析取范式，这时可能还缺少某个变范式，这时可能还缺少某个变元，元，因为因为p pp p0 0，0 0 p pp p，可在缺少变元的，可在缺少变元的大项大项中加中加入形如入形如“p pp p”的公式的公式 。(pq)r(p r)(q r)(p qr)(p(q qq q)r)(p pp p)q r)(p qr)(p q r)(pq r)(pq r)(pq r)(p qr)(p q r)(pq r)(pq r)(p qr)1.4 析取范式与合取范式析取范式与合取范式 当一个公式比较复杂时，得到其当一个公式比较复杂时，得到其析取范析取范式、合取范式式、合取范式的演算量比较大，再将简单析的演算量比较大，再将简单析取式转换为大项，或简单合取式转换为小项，取式转换为大项，或简单合取式转换为小项，又需要进一步演算，能否直接基于原公式，又需要进一步演算，能否直接基于原公式，不进行等值演算直接得到，或者能按某种统不进行等值演算直接得到，或者能按某种统一的方式得到其主析取范式、主合取范式呢一的方式得到其主析取范式、主合取范式呢？通过通过真值表真值表可以实现！为此先研究小项可以实现！为此先研究小项与大项的性质与大项的性质。1.4 析取范式与合取范式析取范式与合取范式 通过通过真值表真值表可以实现！为此先研究小项可以实现！为此先研究小项与大项的性质，下表是与大项的性质，下表是各小项各小项的真值表。的真值表。1.1.3 3个变元个变元的小项共有的小项共有8 8个，它们个，它们各不相各不相同。同。2.2.从从每一行每一行来看，命题变元的每个指派中，只有来看，命题变元的每个指派中，只有一个一个小小项的值为项的值为1 1。3.3.从从每一列每一列来看，每个小项仅在来看，每个小项仅在一个指派中值一个指派中值为为1 1，其，其余余7 7种指派中均为种指派中均为0 0。4.小项小项值为值为1(如如 pqr=1)时，时，p,q,r均为均为1，即，即(p,q,r)=(0,0,0)，取该值为小项编号，如最后一行。取该值为小项编号，如最后一行。(5)根据根据小项的编号小项的编号，可写出，可写出小项的具体小项的具体形式。形式。如小项如小项m101，其编号为，其编号为101，表示，表示(p,q,r)=(1,0,1)时该小时该小项的值为项的值为1，而小项是文字的合取，故小项的各个文字必，而小项是文字的合取，故小项的各个文字必须为须为1,则文字只能是则文字只能是p、q、r,故该小项为故该小项为pq r。规则规则：1对应变元本身对应变元本身(如如p)，0对应其否定对应其否定(如如 p)。如如m00为为 pq、m01为为 p q、m10为为pq、m11为为p q。很重要！很重要！(1)三个变元三个变元的大项共有的大项共有8个。个。(2)每一行每一行:每个指派中，只有一个大项的值为每个指派中，只有一个大项的值为0。(3)每一列每一列:每个大项仅在一个指派下值为每个大项仅在一个指派下值为0。(4)大项值为大项值为0(如如 pqr=0)时，时，p、q、r均为均为0，则，则(p,q,r)=(1,1,1)，将其记为大项编号，将其记为大项编号,如表最后行。如表最后行。(5)根据根据大项大项的编号，可写出大项的具体形式。的编号，可写出大项的具体形式。如大项如大项M101,其编号为其编号为101，表示，表示(p,q,r)=(1,0,1)时该大项时该大项的值为的值为0，而大项是文字的析取，故各个文字必须为，而大项是文字的析取，故各个文字必须为0，文字只能是文字只能是 p、q、r，故该大项为，故该大项为 p qr。规则规则：1对应变元的对应变元的否定否定(如如 p)，0对应变元对应变元(如如p)如如M00为为p q,M01为为pq,M10为为 p q,M11为为 pq。1.4 析取范式与合取范式析取范式与合取范式获取方法获取方法1、先转换、先转换析取式析取式或或合取式合取式，再，再合取合取1或或析取析取0。2、先建立、先建立真值表真值表，取出所有取出所有成真赋值成真赋值对应的小项，析取所有小项对应的小项，析取所有小项得主析取范式。得主析取范式。小项与成真赋值对应小项与成真赋值对应。取出所取出所有成假赋值有成假赋值对应的大项，合取所有大项对应的大项，合取所有大项得主合取范式。得主合取范式。大项与成假赋值对应。大项与成假赋值对应。如用真值表求主范式如用真值表求主范式:(pq)r,pq,pq,(pq)q,p(p q)(pq)r的的主析主析取范式、取范式、主合主合取范式取范式 主析取主析取范式范式公式值为公式值为1的指派对应小项的析取的指派对应小项的析取m001 m011 m100 m111 1变元变元,0变元否定变元否定,使小项=1(pq r)(p q r)(pqr)(p q r)(pq)r的的主析主析取范式、取范式、主合主合取范式取范式 主合取式主合取式范式范式公式值为公式值为0 0的指派对应的指派对应大项大项的合取的合取 M000 M010 M101 M110 1变元否定0变元,使大项=0(p q r)(pq r)(p qr)(pq r)(pq)r、与其主析取范式、主合取范式的真值完全一样，说明三者互相等值，一般情况下有如下定理：(1)不是永假的命题公式，有等值的主析取范式。(2)不是永真的命题公式，有等值的主合取范式。由于永假没有取值为1的解释，故无相应小项，故没有主析取范式。永真无取值为0的解释,故没有主合取范式.设计一个电子评分系统，3位专家打分，如果有2位以上专家打分为“通过”，则总成绩为“通过”。对应的主析取范式值为1的指派对应的小项的析取m011m101m110m111(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3)(x1x2)(x1x2)x3)(x1x2(x3x3)(x1x2)(x1x2)x3)(x1x2)(x1x2)(x1x2)x3)(x1x2)与非或门表示 某公司要从曹、乔、宋、黎、邹某公司要从曹、乔、宋、黎、邹5人中，选择一些人承人中，选择一些人承包一项工程，考虑到人与人组合优化的问题，需满足如包一项工程，考虑到人与人组合优化的问题，需满足如下约束条件：下约束条件：(1)如果曹去，那么乔也去；如果曹去，那么乔也去；(2)黎、邹两人中必有一人去；黎、邹两人中必有一人去；(3)乔、宋两人中去且仅去一人；乔、宋两人中去且仅去一人；(4)宋、黎两人同去或同时不去；宋、黎两人同去或同时不去；(5)若邹去，则曹、乔也同去；若邹去，则曹、乔也同去；解：用小写字母表示：解：用小写字母表示：c:曹去，曹去，q：乔去：乔去 s：宋去：宋去 l：黎去黎去 z：邹去时，以上：邹去时，以上5句话可表示为如下的公式：句话可表示为如下的公式：(cq)、(l z)、(qs)(q s)、(sl)、(z(q c)，5句话同时成立即每句话的值均为句话同时成立即每句话的值均为1，也即其合取式，也即其合取式(cq)(l z)(qs)(q s)(sl)(z(q c)为为1(cq)(l z)(qs)(q s)(sl)(z(q c)(c q)(l z)(qs)(q s)(s l)(sl)(z(q c)(c q)(l z)(z(q c)(qs s l)(qssl)(q s s l)(q ssl)(c q)(l z)(z(q c)(qsl)(q s l)(c q)(l z)(z qsl)(zq s l)(q csl)(c q)(zq s l)(z q csl)(czq s l)(z q csl)因因(cq)(l z)(qs)(q s)(sl)(z(q c)为为1，故，故1(czq s l)(z q csl)，故故1(czq s l)或或1(z q csl)故故方案一是：曹不去、邹不去、乔不去，宋与黎去。方案一是：曹不去、邹不去、乔不去，宋与黎去。方案二是：曹去、乔去、邹去，宋与黎均不去方案二是：曹去、乔去、邹去，宋与黎均不去 在某班班委的选举中，该班的甲、乙、丙学生预言：在某班班委的选举中，该班的甲、乙、丙学生预言：甲说：王娟为班长、刘强为生活委员；甲说：王娟为班长、刘强为生活委员；乙说：金鑫为班长、王娟为生活委员；乙说：金鑫为班长、王娟为生活委员；丙说：刘强为班长、王娟为学习委员；丙说：刘强为班长、王娟为学习委员；结果公布后，发现甲、乙、丙三人都恰好对了一半，请问王娟、结果公布后，发现甲、乙、丙三人都恰好对了一半，请问王娟、刘强、金鑫各任何职？刘强、金鑫各任何职？解解：p1,q1,r1:表示王娟，刘强，金鑫是表示王娟，刘强，金鑫是班长班长；p2,q2,r2:分别表示王娟，刘强，金鑫是分别表示王娟，刘强，金鑫是学习学习委员；委员；p3,q3,r3:分别表示王娟，刘强，金鑫是分别表示王娟，刘强，金鑫是生活生活委员；委员；“每个人说法对一半每个人说法对一半”将是一个非常复杂的公式将是一个非常复杂的公式(p1q3 r1p3 q1p2)(p1q3 r1p3q1 p2)(p1q3r1 p3 q1p2)(p1q3r1 p3q1 p2)(p1 q3 r1p3 q1p2)(p1 q3 r1p3q1 p2)(p1 q3r1 p3 q1p2)(p1 q3r1 p3q1 p2)，要构，要构造这造这9个变元的真值表，将需要个变元的真值表，将需要29=512行，工作量实在太大了，行，工作量实在太大了，！参考“真值表”，设计如下的判断表1.6 推理理论推理理论 从从已知条件已知条件、假设假设、前提前提或或公理公理出发，根据推出发，根据推理规则理规则推出推出结论、定理的过程，称为结论、定理的过程，称为推理推理。定义定义1 设设A与与C是两个命题公式，若是两个命题公式，若AC为为永真永真式式(重言式重言式)，则称，则称C是是A的的有效结论有效结论，或称，或称A可以可以逻辑推出逻辑推出C，记为，记为AC.由由“”的定义可知，当的定义可知，当A为为假假时，时，A