命题逻辑

第一章 命题逻辑

内容：

命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法证明等方法

教学目的：

1．熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。

2．熟练掌握常用的基本等价式及其应用。

3．熟练掌握（主）析/合取范式的求法及其应用。

4．熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。

5．熟练掌握形式演绎的方法。

教学重点：

1．命题的概念及判断

2．联结词，命题的翻译

3．主析（合）取范式的求法

4．逻辑推理

教学难点：

1．主析（合）取范式的求法

2．逻辑推理

1.1命题及其表示法

1.1.1 命题的概念

数理逻辑将能够判断真假的陈述句称作命题。

1.1.2 命题的表示

命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如Ai，[10]，R等，例如A1：我是一名大学生。A1:我是一名大学生.[10]：我是一名大学生。R：我是一名大学生。

1.2命题联结词

1.2.1 否定联结词﹁P

P P

0 1

1 0

1.2.2 合取联结词∧

P Q QP

0 0 0

0 1 0

1 0 0

1 1 1 1.2.3 析取联结词∨

P Q QP

0 0 0

0 1 1

1 0 1

1 1 1

1.2.4 条件联结词→

P Q QP

0 0 1

0 1 1

1 0 0

1 1 1

1.2.5 双条件联结词

P Q QP

0 0 1

0 1 0

1 0 0

1 1

1

1.2.6 与非联结词↑

P Q QP

0 0 1

0 1 1

1 0 1

1 1 0

性质：

（1） P↑P﹁（P∧P）﹁P；

（2）（P↑Q）↑（P↑Q）﹁（P↑Q） P∧Q；

（3）（P↑P）↑（Q↑Q）﹁P↑﹁Q P∨Q。

1.2.7 或非联结词↓

P Q QP

0 0 1

0 1 0

1 0 0

1 1 0

性质：

（1）P↓P﹁（P∨Q）﹁P；

（2）（P↓Q）↓（P↓Q）﹁（P↓Q）P∨Q；

（3）（P↓P）↓（Q↓Q）﹁P↓﹁Q﹁（﹁P∨﹁Q）P∧Q。 1.3 命题公式、翻译与解释

1.3.1 命题公式

定义 命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、PQ、 PQ都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。

例如，下面的符号串都是公式：

（（（（﹁P）∧Q）R）∨S）

（（P﹁Q）（﹁R∧S）） （﹁P∨Q）∧R

以下符号串都不是公式：

（（P∨Q）（∧Q）） （∧Q）

1.3.2 命题的翻译 可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。

命题翻译时应注意下列事项：

（1）确定所给句子是否为命题。

（2）句子中联结词是否为命题联结词。

（3）要正确的选择原子命题和合适的命题联结词。

例：假如上午不下雨，我去看电影，否则就在家里读书或看报。

解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。

本例可表示为： （PQ）∧（P（R∨S））。

1.3.3 命题公式的解释定义

设P1，P2，…，Pn是出现在命题公式G中的全部命题变元，指定P1，P2，…，Pn的一组真值，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作TI（G）。

例如，G=（P∧Q）R，则I：

P Q R

1 1 0

是G的一个解释，在这个解释下G的真值为1，即TI（G）=1。

1.4 真值表与等价公式

1.4.1 真值表

定义 将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。

构造真值表的方法如下：

（1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，…，Pn。

（2）列出G的2n个解释，赋值从00…0（n个）开始，按二进制递加顺序依次写出各赋值，直到11…1为止（或从11…1开始，按二进制递减顺序写出各赋值，直到00…0为止），然后从低到高的顺序列出G的层次。

（3）根据赋值依次计算各层次的真值并最终计算出G的真值。

例：G=（ P→Q ）∧Q

P Q QP )(QP QQP)(

0 0 1 0 0

0 1 1 0 0

1 0 0 1 0

1 1 1 0 0

1.4.2 命题公式的分类

定义 设G为公式：（1）如果G在所有解释下取值均为真，则称G是永真式或重言式；（2）如果G在所有解释下取值均为假，则称G是永假式或矛盾式；（3）如果至少存在一种解释使公式G取值为真，则称G是可满足式。

1.4.3 等价公式

定义 设A和B是两个命题公式，如果A和B在任意赋值情况下都具有相同的真值，则称A和B是等价公式。记为AB。

性质定理

设A、B、C是公式，则

（1）AA

（2）若AB则BA

（3）若AB且BC则AC

定理 设A、B、C是公式，则下述等价公式成立：

（1）双重否定律 AA

（2）等幂律 A∧AA ； A∨AA

（3）交换律 A∧BB∧A ； A∨BB∨A

（4）结合律 （A∧B）∧CA∧（B∧C）

（A∨B）∨CA∨（B∨C）

（5）分配律 （A∧B）∨C（A∨C）∧（B∨C）

（A∨B）∧C（A∧C）∨（B∧C）

（6）德·摩根律 （A∨B）A∧B

（A∧B）A∨B

（7）吸收律 A∨（A∧B）A；A∧（A∨B）A

（8）零一律 A∨11 ； A∧00

（9）同一律 A∨0A ； A∧1A

（10）排中律 A∨A1

（11）矛盾律 A∧A0

（12）蕴涵等值式 A→BA∨B

（13）假言易位 A→BB→A

（14）等价等值式 AB（A→B）∧（B→A） （15）等价否定等值式 ABABBA

（16）归缪式 （A→B）∧（A→B）A

1.4.4 置换规则

定理（置换规则） 设（A）是一个含有子公式A的命题公式，（B）是用公式B置换了（A）中的子公式A后得到的公式，如果AB，那么（A）（B）。

1.5 对偶与范式

1.5.1 对偶

定义 在仅含有联结词Ø、∧、∨的命题公式A中，将联结词∧换成∨，将∨换成∧，如果A中含有特殊变元0或1，就将0换成1，1换成0，所得的命题公式A*称为A的对偶式。

例：公式（P∨Q）∧（P∨Q） 的对偶式为：（P∧Q）∨（P∧Q）

定理 设A和A*互为对偶式，P1，P2，…，Pn是出现在A和A*中的所有原子变元，若将A和A*写成n元函数形式，则

（1）A（P1，P2，…，Pn）A*（P1，P2，…，Pn）

（2）A（P1，P2，…，Pn）A*（P1，P2，…，Pn）

定理（对偶原理）设A、B是两个命题公式，若AÛB，则A*B*，其中A*、B*分别为A、B的对偶式。

1.5.2 范式

定义 仅由有限个命题变元及其否定构成的析取式称为简单析取式，仅由有限个命题变元及其否定构成的合取式称为简单合取式。

定义 仅由有限个简单合取式构成的析取式称为析取范式。仅由有限个简单析取式构成的合取式称为合取范式。

定理（范式存在定理）任何命题公式都存在着与之等价的析取范式和合取范式。

1.5.3 主范式

定义 在含有n个命题变元P1，P2，…，Pn的简单合取范式中，若每个命题变元或其否定不同时存在，但二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左起的第i个位置上（若命题变元无脚标，则按字典顺序排列），这样的简单合取式称为极小项。相应的，满足上述条件的简单析取式称为极大项。n个命题变元P1，P2，…，Pn的极小项用公式可表示为 Pi* ，极大项可表示为Pi*，其中，Pi*为Pi或Pi（i=1，2，…，n）。

定义 设G为公式，P1，P2，…，Pn为G中的所有命题变元，若G的析取范式中每一个合取项都是P1，P2，…，Pn的一个极小项，则称该析取范式为G的主析取范式。矛盾式的主析取范式为0。 定理 任意的命题公式都存在一个唯一的与之等价的主析取范式。

用等值演算求主析取范式步骤如下：

（1） 求G的析取范式G'；

（2）若G中某个简单合取式m中没有出现某个命题变元Pi或其否定Pi，则将m作如下等价变换：mm∧（Pi∨Pi）（ m∧Pi）∨（m∧Pi）

（3）将重复出现的命题变元、矛盾式和重复出现的极小项都消去；

（4）重复步骤（2）、（3），直到每一个简单合取式都为极小项；

（5）将极小项按脚标由小到大的顺序排列，并用∑表示。如m0∨m1∨m7可表示为∑（0，1，7）。

定义 设G为公式，P1，P2，…，Pn为G中的所有命题变元，若G的合取范式中每一个析取项都是P1，P2，…，Pn的一个极大项，则称该合取范式为G的主合取范式。通常，主合取范式用∏表示。重言式的主合取范式中不含任何极大项，用1表示。

定理 任意的命题公式都存在一个唯一的与之等价的主合取范式。

1.6 公式的蕴涵

1.6.1 蕴涵的概念定义

设G、H是两个公式，若G→H是永真式，则称G蕴涵H，记作GH。

蕴涵关系有如下性质：

（1） 对于任意公式G，有GG；

（2）对任意公式G、H，若GH且HG，则GH；

（3） 若GH且HL，则GL。

广义的蕴涵概念

定义 设G1，G2，…，Gn，H是公式，如果（G1∧G2∧…∧Gn）→H是永真式，则称G1，G2，…，Gn蕴涵H，又称H是G1，G2，…，Gn的逻辑结果，记作（G1∧G2∧…∧Gn）H或（G1，G2，…，Gn）H。

1.6.2 基本蕴涵式

（1）P∧QP； （2）P∧QQ；

（3）PP∨Q； (4) QP∨Q；

（5）P（P→Q）； （6）Q（P→Q）；

（7）（P→Q）P； （8）（P→Q）Q；

（9）P，P→QQ； （10）Q，P→QP；

（11）P，P∨QQ； （12）P→Q，Q→RP→R；

（13）P∨Q，P→R，Q→RR； （14）P→Q，R→S（P∧R）→（Q∧S）；

（15）P，QP∧Q。