第1章 命题逻辑 本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)范式，命题逻辑的推理理论. 一、重点内容 1. 命题 命题表述为具有确定真假意义的陈述句命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义. 2. 六个联结词及真值表 h“Ø”否定联结词，P是命题，ØP是P的否命题，是由联结词 Ø 和命题P组成的复合命题.P取真值1，ØP取真值0，P取真值0，ØP取真值1. 它是一元联结词. h “Ù”合取联结词，PÙQ是命题P，Q的合取式，是“Ù”和P，Q组成的复合命题. “Ù”在语句中相当于“不但…而且…”，“既…又…”. PÙQ取值1，当且仅当P，Q均取1；PÙQ取值为0，只有P，Q之一取0. h “Ú”析取联结词，“`Ú”不可兼析取(异或)联结词， 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. h “®”蕴含联结词， 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”.h “«” 等价联结词，P«Q是P，Q的等价式，是“«”和P，Q组成的复合命题. “«”在语句中相当于“…当且仅当…”，P«Q取值1当且仅当P，Q真值相同.3. 命题公式、赋值与解释，命题公式的分类与判别 h命题公式与赋值，命题P含有n个命题变项P1，P2,…,Pn，给P1，P2,…,Pn各指定一个真值，称为对P的一个赋值(真值指派). 若指定的一组值使P的真值为1，则这组值为P的真指派；若使P的真值为0，则称这组值称为P的假指派. h命题公式分类，在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式；判定命题公式类型的方法：其一是真值表法，任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.其二是推导演算法. 利用基本等值式(教材P.16的十六个等值式或演算律)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式.既非永真，也非用假，成为非永真的可满足式.其三主析取(合取)范式法，该公式的主析取范式有2n个极小项(即无极大项)，则该公式是永真式；该公式的主合取范式有2n个极大项(即无极小项)，则该公式是永假式；该公式的主析取(或合取)范式的极小项(或极大项)个数大于0小于2n,，则该公式是可满足式.h等值式AÛB，命题公式A，B在任何赋值下，它们的真值均相同，称A，B等值。
定理1 设F(A)是含命题公式A的命题，F(B)是用命题公式B置换F(A)中的A之后得到的命题公式. 如果AÛB，则F(A)ÛF(B). 4. 范式 h 析取(合取)范式，仅有有限个简单合取式(析取式)构成的析取式(合取式)，就是析取(合取)范式. h 极小项(极大项)，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是极大项. h 主析取范式(主合取范式) 含有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)，再利用分配律展开，使得每个合取项(析取项)的命题变项齐全；④ 将极小(极大)项按由小到大的顺序排列，用S(P)表示. 5. 命题演算的推理理论 h设A1,A2,…,An,C是命题公式，如果是重言式，称C是前提集合{ A1,A2,…,An}的有效结论或{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的真值表 PQRQ®RP®(Q®R)PÙQPÙQ®RP®(Q®R)«PÙQ®R0001101100111011010010110111101110011011101110111100010111111111由表可知，公式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。