当前位置:首页 > 离散数学 复习资料
第1章 命题逻辑
本章重点:命题与联结词,公式与解释,真值表,公式的类型及判定, (主)析取(合取)范式,命题逻辑的推理理论.
一、重点内容
1. 命题 命题表述为具有确定真假意义的陈述句。命题必须具备二个条件:其一,语句是陈述句;其二,语句有唯一确定的真假意义. 2. 六个联结词及真值表 ?“?”否定联结词,P是命题,?P是P的否命题,是由联结词 ? 和命题P组成的复合命题.P取真值1,?P取真值0,P取真值0,?P取真值1. 它是一元联结词. ? “?”合取联结词,P?Q是命题P,Q的合取式,是“?”和P,Q组成的复合命题. “?”在语句中相当于“不但…而且…”,“既…又…”. P?Q取值1,当且仅当P,Q均取1;P?Q取值为0,只有P,Q之一取0. ? “?”析取联结词,“??”不可兼析取(异或)联结词, P?Q是命题P,Q的析取式,是“?”和P,Q组成的复合命题. P??Q是联结词“??”和P,Q组成的复合命题. 联结词“?”或“??”在一个语句中都表示“或”的含义,前者表示相容或,后者表示排斥或不相容的或. 即“P??Q”?“(?P?Q)?(P??Q)”. P?Q取值1,只要P,Q之一取值1,P?Q取值0,只有P,Q都取值0.
? “?”蕴含联结词, P?Q是“?”和P,Q组成的复合命题,只有P取值为1,Q取值为0时,P?Q取值为0;其余各种情况,均有P?Q的真值为1,亦即1?0的真值为0,0?1,1?1,0?0的真值均为1. 在语句中,“如果P则Q”或“只有Q,才P,”表示为“P?Q”.
? “?” 等价联结词,P?Q是P,Q的等价式,是“?”和P,Q组成的复合命题. “?”在语句中相当于“…当且仅当…”,P?Q取值1当且仅当P,Q真值相同.
3. 命题公式、赋值与解释,命题公式的分类与判别 ?命题公式与赋值,命题P含有n个命题变项P1,P2,…,Pn,给P1,P2,…,Pn各指定一个真值,称为对P的一个赋值(真值指派). 若指定的一组值使P的真值为1,则这组值为P的真指派;若使P的真值为0,则称这组值称为P的假指派.
?命题公式分类,在各种赋值下均为真的命题公式A,称为重言式(永真式);在各种赋值下均为假的命题公式A,称为矛盾式(永假式);命题A不是矛盾式,称为可满足式;
判定命题公式类型的方法:其一是真值表法,任给公式,列出该公式的真值表,若真值表的最后一列全为1,则该公式为永真式;若真值表的最后一列全为0,则该公式是永假式;若真值表的最后一列既非全1,又非全0,则该公式是可满足式.其二是推导演算法. 利用基本等值式(教材P.16的十六个等值式或演算律),对给定公式进行等值推导,若该公式的真值为1,则该公式是永真式;若该公式的真值为0,则该公式为永假式.既非永真,也非用假,
n
成为非永真的可满足式.其三主析取(合取)范式法,该公式的主析取范式有2个极小项(即
n
无极大项),则该公式是永真式;该公式的主合取范式有2个极大项(即无极小项),则该公
n
式是永假式;该公式的主析取(或合取)范式的极小项(或极大项)个数大于0小于2,,则该公式是可满足式.
?等值式A?B,命题公式A,B在任何赋值下,它们的真值均相同,称A,B等值。 定理1 设?(A)是含命题公式A的命题,?(B)是用命题公式B置换?(A)中的A之后得到的命题公式. 如果A?B,则?(A)??(B).
4. 范式 ? 析取(合取)范式,仅有有限个简单合取式(析取式)构成的析取式(合取式),就是析取(合取)范式. ? 极小项(极大项),n个命题变项P1,P2,…,Pn,每个变项或它的否定两者只有其一出现且仅出现一次,第i个命题变项或者其否定出现在从左起第i个位置上(无脚标时,按字典序排列),这样的简单合取式(析取式)为极小项(极大项). 以两个命题变项为例,m00=?P??Q,m01=?P?Q,m10=P??Q,m11=P?Q是极小项;M00=P?Q,M01=P??Q,M10=?P?Q,M11=?P??Q是极大项. ? 主析取范式(主合取范式) 含有n个命题变项的命题公式,如果与一个仅有极小项(极大项)的析取(合取)构成的析取(合取)范式等值,则该等值式称为原命题公式的主析取(合取)范式。
每项含有n个命题变项(变项字母齐全)的合取式(析取式)的析取(合取)为主析取(合取)范式. 任意命题公式都存在与之等值的范式,存在与之等值的主范式,且是惟一的.
求范式,包括求析取范式、合取范式、主析取范式和主合取范式. 关键有两点:其一是准确掌握范式定义;其二是巧妙使用基本等值式中的分配律、同一律和摩根律,结果的前一步适当使用幂等律. 求析取(合取)范式的步骤: ① 将公式中的联结词都化成?,?,?(即消去个数中的联结词?,?,??);
② 将否定联结词?消去或移到各命题变项之前;
③ 利用分配律、结合律等,将公式化为析取(合取)范式. 求命题公式A的主析取(合取)范式的步骤 ① 求公式A的析取(合取)范式; ② “消去”析取(合取)范式中所有永假式(永真式)的析取项(合取项),如P??P(P??P)用0(1)替代. 用幂等律将析取(合取)范式中重复出现的合取项(析取项)或相同的变项合并,如P?P(P?P)用P替代,mi?mi(Mi?Mi)用mi(Mi)替代.
③ 若析取(合取)范式的某个合取项(析取项)B不含有命题变项Pi或?Pi,则添加Pi??Pi(Pi??Pi),再利用分配律展开,使得每个合取项(析取项)的命题变项齐全;
④ 将极小(极大)项按由小到大的顺序排列,用?(?)表示. 5. 命题演算的推理理论
?设A1,A2,…,An,C是命题公式,如果A1?A2???An?C是重言式,称C是前提集
合{ A1,A2,…,An}的有效结论或{A1,A2,…,An}逻辑地推出C。记作A1?A2???An?C 掌握演绎或形式证明. 要理解并掌握14个重言蕴含式(即I1~I14),17个等值式(E1~E17);二是会使用三个规则(P规则、T规则和CP规则)。 推理方法有: 真值表法;等值演算法;主析取范式法,构造证明法(直接证明法、附加前提证明法和间接证明法)
二、实例
例1.1 判别下列语句是否命题?如果是命题,指出其真值. (1) 中国是一个人口众多的国家. (2) 存在最大的质数. (3) 这座楼可真高啊! (4) 请你跟我走!
(5) 火星上也有人.
解 (1) 是命题,真值为1. (2) 是命题,真值为0. (3), (4)不是命题因为不是陈述句. (5) 是命题. 真值是唯一的,迟早会被指出. 例1.2 将下列命题符号化:
(1) 虽然交通堵塞,但是老王还是准时到达火车站; (2) 张力是三好生,他是北京人或是天津人.
(3) 除非天下雨,否则我骑车上班.
解 (1) 设P:交通堵塞,Q:老王准时到达火车站. 该命题符号化为:P?Q. (2)设P:张力是三好生; Q:张力是北京人,R:张力是天津人. 该命题符号化为P?(Q??R ). (3)设P:天下雨,Q:我不骑车上班.
该命题符号化为:Q?P,义即“只有天下雨,我才不骑车上班”,不下雨是我骑车上班的必要条件。它的等价说法是“如果天不下雨,我就骑车上班”,即?P??Q
“如果天下雨,我就不骑车上班”,这是蕴含关系,符号化为:P?Q
注:本例各小题都是复合命题。如“李枚和张樱花是好朋友”是简单命题,用字母P表示。显然P:李枚是好朋友,Q:张樱花是好朋友,符号化为Q?P是不通的.
例1.3 证明:P?(Q?R)?P?Q?R.
证明 方法1 真值表法. 列公式P?(Q?R)与P?Q?R的真值表如表1-1. .
表1-1 公式P?(Q?R)与P?Q?R的真值表 P 0 0 0 0 1 1 1 1 Q R Q?R 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 1 1 1 0 P?(Q?R) 1 1 1 1 1 1 0 P?Q 0 0 0 0 0 0 1 P?Q?R 1 1 1 1 1 1 0 P?(Q?R)?P?Q?R 1 1 1 1 1 1 1 1 1 1 1 1 1 1 由表可知,公式P?(Q?R)与P?Q?R的真值完全相同,故P?(Q?R)?P?Q?R.. 或由表的最后一列可知,P?Q??P?Q是重言式,故P?(Q?R)?P?Q?R. 注:作为本例的证明可以不要最后1列。若本例改为判断P?(Q?R)?P?Q?R的类型,由最后列可知P?(Q?R)?P?Q?R是重言式.
方法2 等值演算法. 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)和最后一个公式P?Q)?R等值.
方法3 主范式法.
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)?P?Q?R。
注:(1)容易写出P?(Q?R)与P?Q?R的主析取范式均为m0?m1?m2?m3?m4?m5?m7
即 (?P??Q??R)?(?P??Q?R)?(?P?Q??R)
?(?P?Q?R)?(P??Q??R)?(P??Q?R)? (P?Q?R)
(2) 由真值表求公式P?(Q?R)的主析取范式,先列出P?(Q?R)的真值表,见表1-1。主析取范式是公式P?(Q?R)真值为1的项的析取,真值为1的项,即极小项,有第1,2,3,4,5,6,8共7项. 而极小项是合取式,合取式为1,必定是每个变元或其否定为1,如表1-1中第1行P,Q,R均取1,所以这一项为?P??Q??R,类似地,7个极小项为:
?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)?(?P??Q?R)?(?P?Q??R)
?(?P?Q?R)?(P??Q??R)?(P??Q?R)? (P?Q?R)
例1.4 用等值演算法判定公式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 ??((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 ?((?P?(Q?R)) ?P?Q?R)?((P??Q??R)?P?Q?R) (?对?的分配律)
?(?P?P)?Q?R?(Q?R)?1 ?1?1?1
因此,P??(Q?R)?P?Q?R是永真式. 注:也可以用真值表法或主范式法. 例1.5 化简下式:
(A?B?C)?(?A?B?C) 解 (A?B?C)?(?A?B?C)
?(A??A)?(B?C)?1?(B?C)
?B?C(分配律)(否定律)(同一律)
例1.6 求公式(?P?R)?(P?Q)的主合取范式和主析取范式.
解 先将公式(?P?R)?(P?Q)化为合取范式.
(?P?R)?(P?Q)
?(?P?R)?(P?Q)?(Q?P)(去掉?) ?(P?R)?(?P?Q)?(?Q?P) (去掉?) (合取范式)
共分享92篇相关文档