1.9 数学基础知识

　　1.9.1命题逻辑的基础知识

　　1. 命题

　　命题表述为具有确定真假意义的陈述句。

　　命题必须具备二个条件：

　　其一，语句是陈述句；

　　其二，语句有唯一确定的真假意义。

　　2. 联结词

　　● “”否定联结词：P是命题，P是P的否命题。 是由联结词 和命题P组成的复合命题。 一元命题。

　　●  “”合取联结词，PQ是命题P，Q的合取式，是“”和P，Q组成的复合命题。“”在语句中相当于“不但…而且…”，“既…又…”。 PQ取值1，当且仅当P，Q均取1；PQ取值为0，只要P，Q之一取0。

　　●  “”析取联结词，“`”不可兼析取（异或）联结词， PQ是命题P，Q的析取式，是“”和P，Q组成的复合命题。 P`Q是联结词“`”和P，Q组成的复合命题。 联结词“”或“？`”在一个语句中都表示“或”的含义，可以表示相容或，也可以表示排斥或。 `表示不相容的或。 即“P`Q”“PQPQ”。 P?Q取值1，只要P，Q之一取值1，PQ取值0，只有P，Q都取值0。

　　●  “” 等价联结词，PQ是P，Q的等价式，是“”和P，Q组成的复合命题。“”在语句中相当于“…当且仅当…”，PQ取值1当且仅当P，Q取值相同。

　　●  “”蕴含联结词， PQ是“”和P，Q组成的复合命题。 PQ取值为0，只有P取值为1，Q取值为0时；其余各种情况，均有PQ取值为1，亦即10的真值为0，01，11，00的真值均为1。

　　3. 命题公式、永真性的判定或命题公式的分类

　　● 命题公式与赋值，命题P含有n个命题变项P1,P2,…，Pn，给P1,P2,…，Pn各指定一个真值0或1，称为对P的一个赋值（真值指派）。 若指定的一组值使P的值为1，则这组值为P的真指派；若使P的值为0，则称这组值称为P的假指派。

　　● 命题公式分类，在各种赋值下均为真的命题公式A，称为重言式（永真式）；在各种赋值下均为假的命题公式A，称为矛盾式（永假式）；命题A不是矛盾式，称为可满足式；

　　判定命题公式类型的方法：其一是真值表法，对于任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式。 其二是推导法。 利用基本等值式（双重否定律、幂等律、交换律、结合律、分配律、吸收律、摩根律、同一律、零律、否定律、蕴含等值式、等价等值式、假言易位和等价否定等值式等），对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式。

　　● 定理1：设是含命题公式A的命题，是用命题公式B置换中的A之后得到的命题公式。 如果AB，则。

　　4. 范式

　　●  析取（合取）范式，仅有有限个简单合取式（合取式）构成的析取式（合取式），就是析取（合取）范式。

　　●  极小项（极大项），n个命题变项，每个变项与它的否定不同时出现，但是两者必须出现且仅出现一次，而且第i个命题变项或者其否定出现在从左算起第i个位置上（无脚标时，按字典序排列），这样的简单合取式（析取式）为极小项（极大项）。

　　极小项是n个变项的合取，m00=PQ，m01=PQ,…； 极大项是n个变项的析取，M00=PQ，M01=PQ,…；

　　●  主析取范式（主合取范式），对于含有n个命题变项的命题公式如果有一个仅有极小项（极大项）的析取（合取）构成的等式，则该等式为原命题公式的主析取范式（主合取范式）。

　　每项含有n个命题变项（变项字母齐全）合取式（析取式）的析取（合取）为主析取（主合取）范式。

　　任意命题公式都存在与之等值的析取范式和合取范式，与之等值的主析取范式和主合取范式是惟一的。

　　求范式，包括求析取范式、合取范式、主析取范式和主合取范式。 关键有两点：

　　其一是准确掌握范式定义；

　　其二是巧妙使用基本等值式中的分配律、同一律和摩根律，结果的前一步适当使用幂等律。

　　求析取（合取）范式的步骤：

　　① 将公式中的联结词都化成，，（在析取（合取）范式中不能有联结词，，`）；

　　② 将否定联结词？消去或移到各命题变项之前；

　　③ 利用分配律、结合律等，将公式化为析取（合取）范式。

　　求命题公式A的主析取（合取）范式的步骤

　　① 求公式A的析取（合取）范式；

　　② “消去”析取（合取）范式中所有永假式（永真式）的析取项（合取项），如PP（PP）用0（1）替代。 用幂等律将析取（合取）范式中重复出现的合取项（析取项）或相同的变项合并，如PP（PP）用P替代，mimi（MiMi）用mi（Mi）替代。

　　③ 若析取（合取）范式的某个合取项（析取项）B不含有命题变项Pi或Pi，则添加PiPi（PiPi），再利用分配律展开，使得每个合取项（析取项）的命题变项齐全；

　　④ 将极小（极大）项按由小到大的顺序排列，用S（P）表示。

　　5. 命题演算的推理理论

　　掌握演绎或形式证明。 要理解并掌握14个重言蕴含式（即I1～I14），17个等值式（E1～E17）；二是会使用三个规则（P规则、T规则和CP规则）。