离散数学之数理逻辑

第一篇 数理逻辑

数理逻辑是应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科，它起源于公元十七世纪。十九世纪英国的德·摩根和乔治·布尔发展了逻辑代数，二十世纪三十年代数理逻辑进入了成熟时期，基本内容（命题逻辑和谓词逻辑）有了明确的理论基础，成为数学的一个重要分支，同时也是电子元件设计和性质分析的工具。冯·诺意曼，图灵，克林，? 等人研究了逻辑与计算的关系。基于理论研究和实践，随着1946年第一台通用电子数字计算机的诞生和近代科学的发展，计算技术中提出了大量的逻辑问题，逻辑程序设计语言的研制，更促进了数理逻辑的发展。除古典二值（真，假）逻辑外，还研究了多值逻辑、模态逻辑、概率逻辑、模糊逻辑、非单调逻辑等。不仅有演绎逻辑，也还有归纳逻辑。计算机科学中还专门研究计算逻辑、程序逻辑、时序逻辑等。现代数理逻辑分为四论：证明论，递归论（它们与形式语言语法有关），模型论，公理化集合论（它们与形式语言的语义有关）。

第1-1章 命题逻辑

学习要求: 掌握命题，命题公式，重言式，等价式，蕴涵式等基本概念，能利用逻辑联结词或真值表，等价式与蕴涵式进行命题演算和推理；学习范式时与集合的范式进行对比。

表述客观世界的各种现象，表述人们的思想，表述各门学科的规则、理论等，除使用自然语言（这常常是上有歧异性的）外，还要使用一些特定的术语、符号、规律等“对象语言”，这些是所研究学科的一种特殊的形式化语言，研究思维结构与规律的逻辑学也有其对象语言。本章就是讨论逻辑学中的对象语言—命题及其演算，它相当于自然语言中的语句。

§1-1-1 命题 逻辑联结词与真值表

一、 命题的基本概念

首先我们从下面的例子加以分析。 例1-1-1.1人总是要死的。 例1-1-1.2 苏格拉底是人。

1

例1-1-1.3 苏格拉底是要死的。 例1-1-1.4 中国人民是勤劳和勇敢的。 例1-1-1.5 鸵鸟是鸟。 例1-1-1.6 1是质（素）数。 例1-1-1.7 今天没有下雨。

例1-1-1.8 公元二千年会出现生物计算机。 例1-1-1.9 太阳系外的星球上有人。 例1-1-1.10 他喜欢读书也喜欢运动。 例1-1-1.11 他在机房里或者在图书馆里。

例1-1-1.12 电灯不亮是灯泡或线路有毛病，或者是停电所致。 例1-1-1.13 如果a和b都是正数，则ab也是正数。 例1-1-1.14 xy?0当且仅当x和y都大于零。 例1-1-1.15 101+1=110。 例1-1-1.16 天气多好啊？ 例1-1-1.17 他来了吗？ 例1-1-1.18 全体起立！ 例1-1-1.19 帮帮我吧！ 例1-1-1.20 x=0。 例1-1-1.21 我正在说谎。

上述例1-1-1.1?1-1-1.4，例1-1-1.12～1-1-1.13是可以判断为对（真，成立）的陈述句，例1-1-1.5，1-1-1.6，1-1-1.14是能够判断为不对（假，不成立）的陈述句，例1-1-1.7～1-1-1.9在人类历史发展的长河中能够判断它是真或是假的陈述句，例1-1-1.10～1-1-1.11根据“他”当时的情况能够判断出是真或是假的陈述句，例1-1-1.15在二进制计算中为真，在十进制计算中为假，也还是可以判断为真或为假的陈述句，例1-1-1.16是感叹句，例1-1-1.17是疑问句，例1-1-1.18是命令句，例1-1-1.19是祈使句，例1-1-1.20中x是一个未知数（变量），无法判断是真还是假，例1-1-1.21是无法判断真假的悖论。从以上的分析可以看出，表达思想的语句有不同的类别，数理逻辑中研究的是出现较多而又比较规范的语句—可以判断出真或假的陈述句。

2

定义 1-1-1.1 凡是能判断是真或是假的陈述句称为命题。

如前面的例1-1-1.1～1-1-1.15都是命题，例1-1-1.16～1-1-1.21都不是命题。

命题的值为真或假。今后约定用1表示真，0表示假，除T和F以外的大写英文字母或它们后面跟上数字如A，A1，B5，Pi等或[数字]（如[123]，[28]，??）表示命题。

如P：M8085 芯片有40条引线，或[12]：M8085芯片有40条引线。P或[12]称为命题“M8085芯片有40条引线“的标识符。当命题标识符代表一个确定的命题时（如P或[12]，A：人总是要死的），称为命题常元，当命题标识符代表非确指的命题时，称这样的命题标识符为命题变元。

注意：命题变元不是命题，只有对命题变元用一个确定的命题代入后，才能确定其值是1还是0。

定义 1-1-1.2 用一个确定的命题代入一个命题标识符（如P），称为对P进行指派（赋值，或解释）。

再看前面的例1-1-1.1～1-1-1.6，这些命题不能再分解为更简单的能判断其值为1或0的陈述句了，这类命题称为原子命题。在例1-1-1.7中，如果表示今天下雨为原子命题P，则今天没有下雨是P的否定；例10可分解为原子命题P：他喜欢读书，Q：他喜欢运动，用联结词“也”联结起来；例1-1-1.11可分解为原子命题P：他在机房里，Q：他在图书馆里，用联结词“或者”联系起来；例1-1-1.13可分解为原子命题P：a是正数，Q：b是正数，R：ab是正数，用联结词“和”与“如果?，则?”联系起来；例1-1-1.14可分解为原子命题P：xy?0，Q：x>0，R：y>0，用联结词“当且仅当”与“都”联系起来，这类用联结词，标点符号和原子命题构成的命题称为复合命题。 二、逻辑联结词

日常生活、工作和学习中，自然语言里我们常常使用下面的一些联结词，例如：非，不，没有，无，并非，并不等等来表示否定；并且，同时，以及，而（且），不但?而且?，既?又?，尽管?仍然，和，也，同，与等等来表示同时；虽然?也?，可能?可能?，或许?或许?，等和“或（者）”的意义一样；若?则?，当?则?与“如果?那么?”的意义相同；充分必要，等同，一样，相同与“当且仅当”的意义一样。即是说在自然语言中，这些逻辑

3

联结词的作用一般是同义的。在数理逻辑中将这些同义的联结词也统一用符号表示，以便书写、推演和讨论。现定义常用联结词如下：

定义 1-1-1.3 在命题P的适当地方插入“不”或者“没有”产生的新命题称为P的否定，记为?P读成“非P”。

?P的取值依赖于P 的取值，即定义运算表为

命题 真值 P 1 0 ?P 0 1

例如P: 2是一个质数（值为1），

?P：2不是一个质数（值为0）或2是一个和数。

注意：(1)不同的陈述句可能确定同一个命题；(2)否定是一个一元运算。 定义1-1-1.4 两个命题P和Q产生的一个新命题记为P?Q ，读成“P与Q”或“P和Q的合取”。合取的运算表为

命题 真值 P 1 1 0 0 Q 1 0 1 0 P?Q 1 0 0 0

如例1-1-1.10，P：他喜欢读书，Q:他喜欢运动，P和Q的合取为P?Q：他喜欢读书也喜欢运动。

又如A：猫吃鱼，B：2+2=0，则A ? B ：猫吃鱼而且2+2=0。

注意：(1) 数理逻辑中的联结词“合取”只考虑命题之间的形式关系，不考虑命题内容的实际含义，只有在研究取值时才加以考虑。

(2)合取是一个二元运算。

定义 1-1-1.5 两个命题P或Q产生一个新命题，记为P?Q ，读成“P析取Q”，析取的运算表为

命题 真值 P 1 1 0 0 Q 1 0 1 0 P? Q 1 1 1 0

4

如例1-1-1.12，P：他在机房里，Q：他在图书馆里，P?Q：他在机房或图书馆里。

又如P1：他是游泳冠军，P2：他百米是赛冠军，P1?P2：他是游泳冠军或百米赛跑冠军。

A：猫吃鱼，B：2+2=0，A?B：猫吃鱼或者2+2=0。

注意：(1)析取可细分为两种，一种是“不可兼或”如前面例1-1-1.12，一种是“可兼或”，如P1?P2。有的将不可兼或记为“?”，可兼或记为“?”。显然“?”包含“?”为其特殊情况。故我们着重考虑“?”的情形。 (2) 在自然语言或形式逻辑中，用来析取联结的对象往往要求属于同一类事物，但是在数理逻辑中不作这种限制，例如A?B：猫吃鱼或者2+2=0是允许存在的命题。

(3) 析取是一个二元运算。

定义 1-1-1.6 设P，Q是两个命题，“若P则Q”是一个新命题，记为P→Q ，读成P推出Q（或Q是P的必要条件，P是Q的充分条件），P称为条件联结词“→”的前件，Q为→后件。

如P：河水泛滥，Q：周围的庄稼被毁。 P→Q：若河水泛滥，则周围的庄稼被毁。

A：2<3，B: 今天阳光明媚。 A→B：若2<3，则今天阳光明媚。 条件联结词的运算表为

命题 真值 P 1 1 0 0 Q 1 0 1 0 P?Q 1 0 1 1

注意：(1) 条件联结词联结的前件与后件不限定于同一类事物。

(2) 从真值表定义可知，前件取假值时无论后件的取值是真还是假，条件联结词产生的新命题都取为真，即采取的是“善意的推定”。

(3) 条件联结词为一个二元运算。

定义 1-1-1.7 设 P，Q是两个命题，“P当且仅当Q”是一个新命题，记为P?Q ，“?”称为双条件，它的运算表为:

5

命题 真值 P 1 1 0 0 Q 1 0 1 0 P?Q 1 0 0 1

双条件是数学上考虑最多，也是大家比较熟悉的，可以举出许多例子。例如例1-1-1.14是原子命题xy>0及命题：x和y都大于零用双条件联结词产生的命题，这个命题取值为0。又如，我没有收到信当且仅当没有人给我写信，它的值为1。约定在整数范围内讨论，P：2+2=0，Q：IBM-PC是一种微型计算机，P?Q：2+2=0当且仅当IBM-PC是一种微型计算机，此命题取值为0。

注意：(1) 双条件联结词联系的命题不限定属于同一类事物。 (2) 双条件是一个二元运算。

这五种逻辑联结词也可以称为逻辑运算，与一般数的运算一样，可以规定运算的优先级，我们规定的优先级顺序依次为?，?，?，?，?。如果出现的逻辑联结词相同，又没有括号时，从左到右顺序运算。如果遇到有括号时就先进行括号中的运算。

考察例1-1-1.12．令P：电灯亮，Q：灯泡有毛病，R：线路有毛病，S：停电。则可将该语句符号化为Q?R?S??P。

三、命题运算的真值表

定义 1-1-1.8 在命题公式中，对于分量指派的各种可能组合，即确定了该命题的各种真值情况，把它汇列成表格，就是命题的真值表。

任意给定一个复合命题后，用原子命题和逻辑联结词表出，再利用真值表就可以计算出复合命题的值。当复合命题用原子命题变元、逻辑联结词和括号组成时，可以得出该复合命题变元的真值表。

例1-1-1.22 求P?(P?Q)，P??P，P??P的真值表。 解：

P 1 1 0 0 Q 1 0 1 0 P?Q 1 0 0 0 P?(P?Q) 1 1 0 0 P ?P P??P

1 1 0 0 0 0 1 1 0 0 0 0 6

P 1 1 0 0 ?P 0 0 1 1 P??P 1 1 1 1 例1-1-1.23 求Q?R?S??P的真值表。 解：

P 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 Q 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 R 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 S 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 R?S 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 Q?R?S 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 ?P 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 Q?R?S??P 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1

例1-1-1.24 求?(P?Q)?? P??Q的真值表。 解：

P 1 1 0 0 Q 1 0 1 0 P?Q 1 1 1 0 ?(P?Q) 0 0 0 1 ?P??Q 0 0 0 1 ?(P?Q)??P??Q 1 1 1 1

1-1-1 习 题

1．举出原子命题和复合命题的例子五个以上。 2．将下列命题符号化：

7

(1) 我一边看书一边听音乐。 (2) 天下雨了，我不去上街。

(3) 实函数f(x)可微当且仅当f(x)连续。此命题的真值是什么？ (4) 除非你努力，否则你就会失败。

(5) 合肥到北京的列车是中午十二点半或下午五点五十分开。 (6) 优秀学生应做到思想身体学习都好。 3．求下列各式的真值表

(1) P? (Q??P)。

(2) (P?(Q?R))?((P??R)?Q)。 (3) (P→(Q→P))?( ?P→(P→Q))。 (4) (P→(Q?R))?(P→Q)?(P→R)。 (5) (P→Q)?(R→Q)?(P?R)→Q。 (6) P→(Q→(R→(?P→(?Q→?R))))。 (7) ?P?Q。

4．设命题A1，A2的真值为1，A3，A4两命题的真值为0，求下列命题的真值：

(1) (A1?(A2?A3))??((A1?A2)?(A3?A4))。

(2) ?(A1?A2)??A3?(((?A1?A2)??A3)?A4)。 (3) ?(A1?A2)??A3?((A3??A1)?(A3??A4))。 (4) (A1?(A2?(A3??A1)))?(A2??A4)。 5．将下列语句符号化：

(1) 占据空间的，有质量而且不断变化的称之为物质。 (2) 占据空间的，有质量者称为物质，而物质是不断变化的。 (3) 如果你来了，那么他唱歌与否要看你是否伴奏而定。 (4) 我们不能既划船又跑步。

8

§1-1-2 命题公式与真值函数

由命题变元，括号，逻辑联结词按下列规定形成的符号串是我们讨论的对象。 一、命题演算公式

定义 1-1-2.1 由命题变元，逻辑联结词和括号构成的下述表达式称为命题合式公式（well —formed formula）或命题演算公式，简称公式，记为wff： (1) 单个原子命题变元是wff ； (2) 若P，Q是wff ，则 (?P),(P?Q),(P?Q),(P?Q),(P?Q)都是wff ；

(3) 只有有限次使用(1),(2)得到的表达式才是wff 。

为了书写和输入计算机，以及进行运算方便起见，规定：(1) (?P)的括号，整个wff的最外层括号可以省略，(2) 已定好逻辑联结词的优先级后，优先级的括号可省略。

?(P?Q),P??Q,P?(P?Q),(P?Q)?R,(P?Q)?(Q?R)?(P?R)等都是wff。但RS?T,?P?Q)?(Q?P)就不是wff，因为前一表达式R与

S之间没有逻辑联结词，后一表达式中括号不配对，故不符合定义1-1-2.1。

按BNF（Backus—Naur Form）符号，wff的语法定义为：wff：：=<命题>|?<命题> |<命题> <二元运算符> <命题>

<二元运算符>：：=?|?|?|?， <命题>：：=〈原子公式〉| {〈wff 〉} *

定义 1-1-2.2 令A为wff，对A中出现的全部原子命题变元P1，P2，?，Pn分别赋以真值0或1所得到的一组真值（n个）称为A的一个指派或解释。

从§1-1-1的例1-1-1.22～1-1-1.24可以看出，对命题变元作指派，再利用逻辑联结词的真值表（即逻辑运算规则）可以演算出wff的真值表。

下面再看几个例子。

例1-1-2.1 求(P→Q)?(Q→P)的真值表。

9

解：

P 1 1 0 0 Q 1 0 1 0 P?Q 1 0 1 1 Q?P 1 1 0 1 (P?Q)?Q?P） 1 0 0 1 例1-1-2.2 (P→Q)?P→Q的真值表为 解：

P 1 1 0 0 Q 1 0 1 0 P?Q 1 0 1 1 (P?Q)?P 1 0 0 0 (P?Q)?P?Q 1 1 1 1 例1-1-2.3 (P→Q)?(P??Q) 的真值表为

P 1 1 0 0 Q 1 0 1 0 P?Q 1 0 1 1 P??Q 0 1 0 0 (P?Q)?(P??Q) 0 0 0 0 二、真值函数

定义 1-1-2.3 以{真，假}为定义域和值域的函数为真值函数。 如由五个逻辑联结词产生的所有wff都是真值函数，因此有无穷多个真值函数，显然最基本而重要的真值函数还是 ?P,P?Q,P?Q,P?Q,P?Q 。 当真值函数的变元为n个时，共有2n个指派。通过列出真值表也可以定义真值函数。

例1-1-2.4 确定下列真值表对应的真值函数：

P 1 1 1 1 0 0 0 0

Q 1 1 0 0 1 1 0 0 R 1 0 1 0 1 0 1 0 f1 (P , Q , R) 1 0 1 1 0 0 1 0 10

f2 (P , Q , R) 1 0 0 0 0 0 0 1

以f1（P，Q，R）来考虑，表的第一行说明f1的值为1，且指派中P，Q，R都取值为1，可用项P∧Q∧R，表示，表的第三行说明f1的值为1，此时指派中P，R取值为1，Q取值为0，即?Q取值为1，可用P??Q?R表示，此时P，Q，R的其它指派都使P?Q?R，或P??Q?R为0，同理可用

P??Q??R,?P??Q?R分别表示表第四、七行的1，

故f1（P，Q，R）

=(P?Q?R)?(P??Q?R)?(P??Q??R)?(?P??Q?R)(*) 同理 f2（P，Q，R）= (P?Q?R)?(?P??Q??R)。

注意： 由真值表确定的真值函数不一定是最简单的wff，不一定只有一个表达式。

例如：

P 1 1 1 1 0 0 0 0 Q 1 1 0 0 1 1 0 0 R 1 0 1 0 1 0 1 0 P?R 1 0 1 0 0 0 0 0 ?R 0 1 0 1 0 1 0 1 P??Q 0 0 1 1 0 0 0 0 ?Q?R (P?R)?(P??Q)?(?Q?R) 0 0 1 0 0 0 1 0 1 0 1 1 0 0 1 0 将这个真值表与f1（P，Q，R）的真值表相比较，对变元的任一指派，可以看到(P?R)?(P??Q)?(?Q?R)与（*）这两个表达式可代表同一个真值函数，而此两式相比，(*) 就不是最简单的wff 。 三、重言式与矛盾式

我们注意到例1-1-2.2，1-1-2.3和例1-1-2.1，1-1-2.4。对命题变元无论作什么样的指派，例1-1-2.2中的wff永远取值为1，这种类型的wff称为重言(永真)式；例1-1-2.3中的wff永远取值为0，这种类型的wff称为矛盾（永假）式；而例1-1-2.1，1-1-2.4中的wff则对有的指派取值为1。对另外指派又取值为0，这种类型的wff称为可满足公式。显然重言式（或永真函数）是可满足公式，矛盾式是不可满足公式。

11

定义 1-1-2.4 对wff的命题变元无论作什么指派，公式均取值1时，称之为重言式，记为T；公式均取值0时称之为矛盾式（或不可满足式），记为F。若有指派使wff取值1，则称该公式为可满足公式。

定理 1-1-2.1 任意两个重言（矛盾）式的合取或析取仍然是一个重言（矛盾）式。

由定义1-1-2.4及析取、合取的真值表立即可以证明此定理。

1-1-2 习 题

1． 下列符号串哪些是合式公式？哪些是重言式或矛盾式？哪些是可满足公

式？

(1) ?(P?Q) ； (3) P?P?Q ；

(2) P?Q ；

(4) (?P?Q)?(P?Q)；

(5) (P?Q)?((P?Q)?(Q?P))； (6) (?P?Q)?(P??Q)。 2． 用真值表证明下列各式为重言式：

(1)(P?Q)?R?P?(Q?R); (2)(P?Q)?R?P?(Q?R); (3)P?(P?Q)?P;

(4)P?(P?Q)?P;

(5)P?(R?Q)?(P?R)?(P?Q); (6)P?(R?Q)?(P?R)?(P?Q);

(7)P??P?F,P??P?T; (8)P?Q?P,P?Q?Q; (9)P?P?Q,Q?P?Q; (10)?P?(P?Q); (11)Q?(P?Q); (12)?(P?Q)?P; (13)?(P?Q)??Q; (14)?Q?(P?Q)??P;

12

(15)?P?(P?Q)?Q;

(16)(P?Q)?(Q?R)?(P?R); (17)(P?Q)?(P?R)?(Q?R)?R;

(18)(P?Q)?(R?S)?((P?R)?(Q?S))； (19)(P?Q)?(Q?R)?(P?R)； (20)(P?Q)?(Q?P),(P?Q)?(Q?P)。

13

§1-1-3 公式的等价与蕴涵

在§1-1-2中我们已经看到真值函数f1(P,Q,R) 的表达式有：

(P?Q?R)?(P??Q?R)?(P??Q??R)?(?P??Q?R) 或

(P?R)?（P??Q)?(?Q?R)，又如P?Q和?P?Q代表同一真值函数，对同

一真值函数的几个不同的wff 有下面的定义。

定义 1-1-3.1 设P1，P2，?，Pn为出现在两个wff A和B中的原子命题变元。如果对P1，P2，?，Pn的任意真值指派，A和B的真值都相同，则称A和B逻辑相等或说A和B等价，记为A?B或（A?B）。

例如 ?P?Q?P?Q ，用真值表和定义1-1-3.1可以得到下列基本等价式：

(1)??P?P; (对合律)

(2)P?P?P,P?P?P; (幂等律) (3)P?Q?Q?P,P?Q?Q?P; (交换律)

(4)P?(Q?R)?(P?Q)?R,P?(Q?R)?(P?Q)?R; (结合律)

(5)P?(Q?R)?(P?Q)?(P?R),P?(Q?R)?(P?Q)?(P?R);(分配律)

(6)P?(P?R)?P,P?(P?R)?P; (吸收律)

(7)?(P?Q)??P??Q,?(P?Q)??P??Q; (德.摩根律) (8)P?F?P,P?T?P; (同一律) (9)P?T?T,P?F?F; (零一律) (10)P??P?T,P??P?F; (否定律)

(11)P?Q??P?Q; (条件等价式)

(12)P?Q?(P?Q)?(Q?P)。 (双条件等价式)

当wff中出现的原子命题变元很多时，用真值表和定义1-1-3.1来判断两个wff是否等价就显得麻烦，因而可利用上述基本等价式和下面的定理1-1-3.1就可以得到一些复杂的等价式。

定义 1-1-3.2 若wff X 是wff A的子串，则称X为A的子公式。

定理 1-1-3.1 X是wff A的一个子公式，wff Y与X等价，则将A中的X用Y来代替所得的wff B，必有A与B等价（替换规则）。

证明: 因为在命题变元的任意指派下X与Y的真值相同，故用Y代替X后所

14

得的wff B与A在任意相应的指派下也有相同的真值，故A与B等价。

例1-1-3.1 由吸收律和替换规则可知

Q?(P?(P?Q))?Q?P

例 1-1-3.2 证明((P?Q)?R)?((R?P)?(S?P))?T 证明: ((P?Q)?R)?((R?P)?(S?P))

?((?P?Q)?R)?((?R?P)?(?S?P)) ?(?(?P?Q)?R)?(?(?R?P)?(?S?P)) ??(?(?P?Q)?R))?(?(?R?P)?(?S?P)) ?((?P?Q)??R)?(R??P)?(?S?P)

?((?P??R)?(?R?Q))?(?P?R)??S?P ?((?P??R)?(?P?R))?(?R?Q)??S?P ?(?P?((?R?R))?(?R?Q)??S?P ?(?P?T)?(?R?Q)??S?P ?(?P?P)?(?R?Q)??S

?T?(?R?Q)??S ?T

定理 1-1-3.2 在一个重言（矛盾）式中对同一命题变元都用任意一个wff去替换，仍可得一个重言（矛盾）式。

证明: 因为重言（矛盾）式的真值永为1（0），与变元的指派无关，故对同一变元用任一wff 替换后，其值仍为1（0），所以结果为一个重言（矛盾）式。

例1-1-3.3 因为P??P?T，P??P?F，当P以某 wff 替换后仍为重言(矛盾)式，例如P以(Q?R)?S去代替，则有

((Q?R)?S)??((Q?R)?S)?T ((Q?R)?S)??((Q?R)?S)?F

定理1-1-3.3 合式公式A和B等价当且仅当A?B为重言式。

证明: 必要性：若A与B等价，则对出现在A，B中的原子命题变元的任意指派A和B有相同的真值，即A?B永远取值1，即A?B为重言。

充分性：若A?B为重言（矛盾）式，则无论任何指派A?B均取值1，即

15

A，B的真值相同，故A?B。

例1-1-3.4 证明 P?Q??Q??P。 证明:

(P?Q)?(?Q??P)?((P?Q)?(?Q??P))?((?Q??P)?(P?Q))?((?P?Q)?(??Q??P))?((??Q??P)?(?P?Q))?(?(?P?Q)?(??Q??P))?(?(??Q??P)?(?P?Q))?(?(?P?Q)?(?P?Q))?(?(?P?Q)?(?P?Q))?T?T?T故由定理1-1-3.3得证。

例1-1-3.5 P→(Q→R)?(P?Q)→R 证明：

P?(Q?R)??P?(?Q?R)?(?P??Q)?R??(P?Q)?R?(P?Q)?R. 容易验证 wff 等价具有下列性质：

(1) 反身（自反）性: A?A。 (2) 对称性: 若A?B则B?A。

(3) 传递性: 若A?B,B?A，则A?C。

定义 1-1-3.3 设合式公式A和B中出现的原子命题变元为P1,P2,?,Pn，如果对它们的指派使A取值为1时B也取值为1，则称A蕴涵B（或称B是A的逻辑结果），记为A?B。

例1-1-3.6 ?P?P?Q。 证明:

P 1 1 0 0 Q 1 0 1 0 ?P 0 0 1 1 P?Q 1 0 1 1

从上面的真值表可知，使?P取值1的指派0，1和0，0它也使P→Q取值为1，根据定义1-1-3.3得证 ?P?P→Q。

例1-1-3.7 (P?Q)?(Q?R)?P?R。 证明:

16

P 1 1 1 1 0 0 0 0 Q 1 1 0 0 1 1 0 0 R 1 0 1 0 1 0 1 0 P?Q 1 1 0 0 1 1 1 1 Q?R 1 0 1 1 1 0 1 1 (P?Q)?(Q?R) 1 0 0 0 1 0 1 1 P?R 1 0 1 0 1 1 1 1 由真值表可知使(P→Q)?(Q→R )取值为1的指派(1，1，1)；(0,1,1)；(0,0,1)；（0，0，0）也使P→R取值为1，根据定义1-1-3.3知

(P?Q)?(Q?P)?P?R。

定理1-1-3.4 合式公式A?B当且仅当A?B是重言式。

证明：必要性：由A?B的定义知当A取值为1时，B取值也为1。再由A?B的运算表知，当A取值为1时，B取值也为1，A?B为重言式。

充分性：因为A?B为重言式，所以，当A取值为1时，B的真值必为1(否则A?B真值为假，与题设矛盾)，所以A?B。

例1-1-3.8 ?Q?(P?Q)??P 证明：

?Q?(P?Q)??P?(?Q?(?P?Q))??P ??(?Q?(?P?Q))??P?Q??(?P?Q)??P ?(?P?Q)??(?P?Q)?T由定理1-1-3.4得证?Q?(P?Q)??P。

用定义1-1-3.3及定理1-1-3.4易证下列常用的基本蕴涵式： (1) P?Q?P，P?Q?Q； (2) P?P?Q，Q?P?Q； (3) ?P ?P→Q； (4) Q?P→Q；

(5) ?(P→Q)?P；?(P→Q)??Q； (6) P?(P→Q)?Q； (分离规则) (7) ?Q?(P→Q)??P；

17

(8) ?P?(P?Q)?Q ； (9) (P→Q)?(Q→R)? P→R； (10) (P?Q)?(P→R) ?(Q→R) ?R； (11) (P→Q) ?(R→S)?(P?R)→(Q?S)； (12) (P?Q) ?(Q ?R)? P? R。 蕴涵具有下列常用性质：

(1) A为重言式，A?B，则B必为重言式； (2) 自反性 A?A；

(3) 反对称性 若A?B且 B?A 则A?B； (4) 传递性 若A?B且 B?C 则A?C； (5) 若A? B且 A? C 则A? B ? C 。 (6) 若A?B且C?B，故A ? C?B。 证明: (1)、(2) 由A?B的定义即可知。

(3) 因为A?B且B?A，所以A?B与B?A为重言式，由基本等价式(12)知A?B为重言式，所以A?B。

(4) 由A?B且B?C知(A→B)?(B→C)为重言式，据基本蕴涵式(9)知(A→B)?(B→C)?A→C，由性质1知A→C为重言式，故A?C。

(5) 因A?B且A?C，故(A→B)，(B→C)都为重言式，如果A取值为1，则B和C都取值为1，因而B?C取值为1；如果A取值为0，无论B?C取值为1还是取0 ，A→B?C取值均为1，故A→B?C为重言式，所以A?B?C 。 (6) 因A?B且C?B故(A→B)?(C→B)?T。

即 (?A ? B)?(?C? B)?T，即 (?A ?? C)? B?T，即 ?(A ? C)? B?T， 即(A ? C)→B?T，故 A?C ? B。

1-1-3 习 题

1．证明（A?B）?（B?C）?（C?A）?（A?B）?（B?C）?（C?A）。 2．不要构造真值表证明下列蕴涵式： (1) P?Q?P?(P?Q)； (2) (P?Q)?Q?P?Q；

18

(3) Q??Q?P； (4) ?P?Q?P?S； (5) P?R?S??S；

(6) (Q?P)?(R?(R?P))??R?(P?Q)。 3．若A?C?B?C是否有A?B？ 若A?C?B?C是否有A?B？ 若?A??B是否有A?B？ 4．证明A?B时?B??A。

5．证明A?B时?A??B┐，反之也对。

19

§1-1-4 命题逻辑的推理理论

逻辑是研究思维结构和规则的科学，要求能够提供正确的思维规律，提供判定一个论断之有效的准则。数理逻辑则研究正确的推理规则，研究论断的有效性,但要注意到：论断的正确性涉及到实践的检验。

什么是论断的有效性呢？回忆§1-1-3中命题公式的蕴涵概念，并把它推广。

定义 1-1-4.1 A1,A2,?,An和B为合式公式，若A1 ?A2 ??? An?B，则称B为前提A1,A2,?,An的有效结论，或说B是A1,A2,?,An的逻辑结果，或者说A1,A2,?,An共同蕴涵B。

例1-1-4.1 证明 R→S是P→(Q→S)，?R?P ，Q的有效结论。 证明：即要证(P→(Q→S))?(?R?P)?Q?R→S，也就是要证明

(P→(Q→S))?(?R?P)?Q?(R→S)为重言式。当然可以应用真值表验证，也可以用等价是验证，往往是比较麻烦的。

因此判定论断的有效性，需要有其他论证方法，希望有比较简明的过程，还要有正确的依据。

定理 1-1-4.1 若A1?A2???An?B?C，则

A1?A2???An?B?C。

证明：已知A1?A2???An?B?C，故A1?A2???An?B?C为重言式。即?(A1?A2???An?B)?C为重言式，即?(A1?A2???An)??B?C为重言式，即A1?A2???An?(B?C)为重言式，

所以 A1?A2???An?B?C。

定义1-1-4.2 设S为若干公式的集合（称为前提集合）。

如果有公式的有限序列A1,A2,?,An其中Ai ?S 或Ai 是A1,A2,?,Ai?1中某些公式的有效结论，且An?B，则称B是S的逻辑结果或有效结论，或者说从S演绎出B。

定理1-1-4.2 设S为公式集，B是一个公式，S能演绎出B的充分必要条件是：B是S的逻辑结果。

证明： 充分性：因为B是S的逻辑结果，由定义1-1-4.2知存在公式的有限

20

序列A1,A2,?,An,B(Ai?S), B是A1,A2,?,An,的逻辑结果，因而由定义1-1-4.2得证S演绎出B。

必要性：设S演绎出B，则存在公式的有限序列A1,A2,?,An其中A n=B且Ai?S或Ai是A1,A2,?,Ai?1中某些公式的逻辑结果。

下面用归纳法证明，因为，A1?S且A1?A1，故A1是S的逻辑结果（归纳基础）。设Ai (i

Aj1?Aj2 ???Ajl ?An (1-1-4.1)

其中j1?n,j2?n,?,jl?n。由归纳假定Aj1,Aj2,?,Ajl都是S的逻辑结果，即

S?Aj1,S?Aj2,?,S?Ajl

由§1-1-3蕴涵的性质5得Aj1?Aj2???Ajl是S的逻辑结果，即

S?Aj1?Aj2???Ajl (1-1-4.2)

由(1-1-4.1)和(1-1-4.2)式及蕴涵的传递性得S?An，而An =B，故S?B，即B是S的逻辑结果。

定理1-1-4.3 设S为前提公式集合，B和C是两个公式，若S∪{B}演绎出C，则S演绎出B→C。

证明：设S={A1, A2, ?, A n},因为S∪{B}演绎出C，则C是S∪{B}的逻辑结果，即(A1?A2 ???A n) ?B?C。由定理1-1-4.1得A1?A2 ???A n? B? C 。

定理 1-1-4.3和基本等价式及基本蕴涵式是论证演绎的根据，故在演绎推导过程中必须遵循下列推理规则：

P规则：在推演过程中可以随便使用前提。

T规则：在推演过程中可以任意使用前面演绎的某些公式的逻辑结果，当借

助于等价式记为TE，当借助于蕴涵式时记为TI。

CP规则：如果需要演绎出的公式为B→C形，那么将B作为附加前提，设法演绎出C来。

P规则和T规则的依据是定义1-1-4.2，CP规则的依据是定理1-1-4.3。 当然，论证的方法是前变万化的，除使用真值表方法以外，基本的方法就是：直接证法：由一组前提和P规则，T规则演绎出有效结论；另一方法是间接证法：(1)由一组前提和P规则，T规则，CP规则演绎出有效结论；(2)反证法，

21

否定结论后作为附加前提，利用P规则和T规则得出矛盾式。

定义1-1-4.3 设P1，P2 ，?，P n 是A1，A2 ，?，A m 中出现的原子命题变元，若对P1，P2 ，P3 ?，Pn 的一些真值指派，A1 ?A2 ?…?Am 取值为1，则称A1，A2，?，A m 是相容的，若对P1，P2，P3 ?，Pn 的任何指派，A1 ?A2 ?…?Am 取值为0，则称A1，A2 ，?，A m 是不相容的（矛盾的）。

定理1-1-4.4 A1 ?A2 ???A m ? B 当且仅当A1，A2 ，?，Am ，?B是不相容的。

证明: A1 ?A2 ???A m ? B

当且仅当A1 ?A2 ???A m ?B ?T（重言式）， 当且仅当?(A1 ?A2 ???A m )?B?T， 当且仅当A1 ?A2 ???Am ??B?F(矛盾式)， 当且仅当A1，A2 ，?，A n，?B是不相容的。 下面给出利用上面的推理理论来论证若干实例。

例1-1-4.1 证明R→S是{ P→(Q→S)，?R∨P，Q }的逻辑结果。 证明：

(1) ?R?P P

(2) R P( 附 加 前 提) (3) P T (1)(2) I (4) P→(Q→S) P (5) Q→S T(3)(4)I (6) Q P (7) S T(5)(6) I (7) R→S CP (2)(7)

例1-1-4.1 的这种书写方法写出了演绎的公式序列和使用的规则，便于复核检查推演的过程，以下都采用这样的书写方法。

例1-1-4.2 (P?Q)?(P→R) ?(Q→S)? S?R 证明:

(1) P?Q P (2) ?P→Q T(1)E

22

(3) Q→S P (4) ?P→S T(2)(3)I (5) ?S→P T(4)E (6) P→R P (7) ?S→R T(5)(6)I (8) S?R T(7)E 或者

(1) P→R P (2) P?Q→R?Q T(1)I (3) Q→S P (4) R?Q→R?S T(3)I (5) P?Q →R?S T(2)(4)I (6) P?Q P (7) R?S T(5)(6)I

这个例子说明：从前提演绎出公式时的有限序列不是唯一的，将两种演绎步骤直观地分别表示为下面的两个图：

（1） （1） （3）

（2） （3） （2） （4）

（4） （5） （6）

（5） （6） （7）

（7）

（8） 图1-1-4.1

例1-1-4.2采用的是直接证法。

例1-1-4.3 证明S={A→B，?(B?C)}演绎出 ?A。 证明： (1) A→B P

(2) A P （附加前提） (3) ?(B?C） P (4) ?B??C T(3)E

23

(5) B T(1)(2)I (6) ?B T(4)I (7) B??B?F T(5)(6)E (8) ?A 定理1-1-4.4

例1-1-4.4 用间接证法证明例1-1-4.2。

证明: (1) ?(S?R) P（附加前提） (2) ?S??R T(1)E (3) P?Q P (4) ?P→Q T(3)E

(5) Q→S P (6) ?P→S T(4)(5)I (7) ?S→P T(6)E (8) ?S??R→?R?P T(7)I (9) ?R?P T(2)(8)I (10) P→R P (11) ?P?R T(10)E (12) ?(P??R） T(11)E (13) (P??R)??(P??R)?F T(9)(12)E (14) S?R 定理1-1-4.4

例1-1-4.5 “如果下雨，春游就改期，如果没有球赛，春游就不改期。结果没有球赛，所以没有下雨”，证明这是有效的论断。

证明： 令A：天下雨 B：春游改期 C：没有球赛。 符号化题中各语句得 S={ A→B，C→ ?B，C }，S??A。

(1) A→B P (2) C→?B P (3) B→?C T(2)E (4) A→?C T(1)(3)I (5) C→?A T(4)E (6) C P (7) ?A T(5)(6)I

例1-1-4.6 如果学生学习努力，他们的父亲或母亲就高兴，若母亲高

24

兴，学生就不努力学习，若老师只表扬学生，学生的父亲就不高兴，故如果学生学习努力，老师就不是只表扬学生。试证这是有效的结论。

证明: 令A：学生学习努力；B：学生的父亲高兴；C：学生的母亲高兴；D：老师只表扬学生。则问题符号化为：

A→B?C，C→ ?A，D→?B?A→?D (1) D→?B P (2) B→?D T(1)E (3) C→?A P (4) A→?C T(3)E (5) A→(B?C) P (6) A→(?C→B) T(5)E (7) A P(附加前提) (8) ?C T(4)(7)I (9) ?C→B T(6)(7)I (10) B T(8)(9)I (11) ?D T(2)(10)I (12) A→?D CP

例1-1-4.7 证明下列命题是不相容的：如果他因病缺课，那么他考试不及格，如果他考试不及格，他就受不到教育。若他读了许多书，则他受到了教育，但是，虽然他因病缺课，他还是读了许多书。

证明 令 P：他因病缺课，Q：他考试不及格，R：他受不到教育，S：他读了许多书。则问题符号化为 ｛P→Q，Q→R，S→?R，P?S｝?F 。

现证之。

(1) P→Q P (2) Q→R P (3) P→R T(1)(2)I (4) S→?R P (5) R→?S T(4)E (6) P→?S T(3)(5)I (7) ?P??S T(6)E (8) ?(P?S) T(7)E

25

(9) P?S P (10) F T(8)(9)E

例1-1-4.6和例1-1-4.7的推演步骤分别如下图所示：

（1） （5） （3） （1） （2） （4）

（2） （6）（7）（4） （3） （5）

（8） （9） （6）

（7） （10）

（11） （8） （9）

（12） （10）

图1-1-4.2

1-1-4 习 题

1.用直接证法推演下列蕴涵式。

(1) {?A?B，C??B}?A??C； (2) A?B?C?D，D?E?G?A?G；

(3) A?(B?C)，C?D?E，?G?D??E?A?(B?G)； (4) (A?B?C)?(?B?D)?((E??G)??D)?(B?A??E)?B?E； (5) (A?B)?(C?D)，(B?E)?(D?G)，?(E?G)，A?C??A； 2．用间接证法证明上题。

3．将上题中推演步骤的图示作出来。 4．在下列前提下，结论是否有效？

今天或着天晴或者下雨。如果天晴，我去看电影，若我去看电影，我就不看书，故我在看书时说明今天下雨。

5．如果厂方拒绝增加工资，那么罢工就不会停止，除非罢工超过一年并且工厂

撤换了厂长。问：若厂方拒绝增加工资，而罢工刚开始，罢工是否能够停止？

6．下列命题相容吗？

(1) P?Q ，Q?R ，?R?S ，?P→S ，?S；

26

(2) P?Q ，?R?S ，?Q ，?S。

7．下面的推导正确吗？如果不正确要指出原因。

(1) A?B，C?B，D?(A?C)，D?B。 ① D?(A?C) P ② D P ③ A?C T①②I ④ A?B P ⑤ C?B P ⑥ A?C?B T ④⑤I ⑦ B T ③⑥I (2) A?(C?B)，?D?A，C?D?B。 ① ?D?A P ② D P(附加前提) ③ A T ①② I ④ A?(C?B) P ⑤ C?B T ③④ I ⑥ C P ⑦ B T⑤⑥I ⑧ D?B CP

8．对下面的每一组前提，写出可能导出的结论和所用的推理规则： （1）我跑步就感到累，我不累。

（2）若他犯了错误，则他的神色慌张，他神色慌张。

（3）如果我编的程序通过了，那么我很快活，若我很快活，则天气很好，现在是半夜天很好。

（4）如果我学习，那么我的功课不会不及格。若我不热衷于玩扑克，则我学习，但我的功课不及格。

（5）人总是要死的，苏格拉底是人。

27

§1-1-5 对偶与范式

在§1-1-4中我们已经看到基本等价式在推论中是非常有用的，而§1-1-3列出基本等价式(2)～(10)都是成对出现的，即把一个公式的?换成?。T换成F就可得出另一式，反过来将另一公式的?换成?，F换成T也可以得到这一个公式，我们认为逻辑联结词?和?，重言式T与矛盾式F是互为对偶的。

定义1-1-5.1 在只含逻辑联结词?，?，?的公式A中将?换成?，?换成?，如果A中有T或者F就分别换成F或T，所得到的新公式A* 称为A的对偶式。

显然(A*)* =A。

例1-1-5.1 求 (1) (P→R)→(P?Q→R?Q)；

(2) (P?Q)?F； (3) P?(Q?T)

的对偶式。

解：(1) 令A=(P→R)→(P?Q→R?Q)， 则 A=?(?P?R)?(?(P?Q)?R?Q)。 故 A* =?(?P?R)?(?(P?Q)?R?Q)。

(2)，(3)中二式的对偶式分别为(P?Q)?T，P?(Q?F)。

定理 1-1-5.1 设P1，P2，?，P n 是公式A和A*中出现的原子命题变元，现采用函数记法分别为 A(P1，P2，?，P n )，A*(P1，P2，?，P n )，则

?A(P1，P2，?，P n )? A*(?P1，?P2，?，?P n)， A(?P1，?P2，?，?P n)??A*(P1，P2，?，P n )。 证明: 根据德·摩根定律

?(P?Q)??P??Q ，?(P?Q)??P??Q ，

又因?T?F，?F?T，这正好表明?应用于?（或?）上将原子命题变元

换为他们否定的?（或?），故：

?A(P1，P2，?，P n )? A*(?P1，?P2，?，?P n)。 令Qi = ?Pi，则Pi = ?Qi （i=1，2，?，n）。

故：?A(?Q1，?Q2，?，?Q n)? A*(Q1，Q2，?，Q n )。 即：A（?Q1，?Q2，?，?Q n）?? A*(Q1，Q2，?，Q n )。 二式均得证。

定理1-1-5.2 若A，B为二合式公式，A?B则A*?B* 。

28

证明： 设P1，P2，?，P n 是出现在A，B中的原子命题变元。 因A(P1，P2，?，P n )? B(P1，P2，?，P n )，

故A(P1，P2，?，P n )? B(P1，P2，?，P n )是重言式。

即：A（?P1，?P2，?，?P n）?B(?P1，?P2，?，?P n)是重言式， 故A(?P1，?P2，?，?P n)?B(?P1，?P2，?，?P n)。

由定理1-1-5.1有 A(?P1，?P2，?，?P n)?? A*(P1，P2，?，P n )，

B(?P1，?P2，?，?Pn)??B*(P1，P2，?，Pn )，

由合式公式的等价具有传递性，可得

?A*（P1，P2，?，Pn ）??B*(P1，P2，?，Pn )。

由§1-1-3习题8可知A*?B*。

利用对偶律可以使一些命题公式的推证简化， 如S=A?(?A?(B??B))?A?(?A?F)?(A??A)? T， 则S* =A?(?A?(B??B))? F(T*)。

§1-1-2例1-1-2.4里曾经指出：一个真值函数可以由几个不同的公式表示，即是说合式公式可以有几个相互等价的表达式，那么，对于两个不同的公式如何判断他们是否等价呢？当然可以用真值表，但是，当原子命题变元的个数很多时，即使用计算机有时也不能得出全部真值表来，如果利用基本等价式进行逻辑演算来判断，有时由于观察不够或经验不足，常常会出现循环或走弯路的情形，后一情形就浪费时间，精力，前一情形就得不出结果，这是因为使用基本等价式与人的智慧有关，是非常灵活的，要能够在计算机上机械地进行判断，或者使人们能够明确地判断，下面介绍公式的范式，它既能判定公式是否等价，也能判定公式是否为重言式或矛盾式。

定义1-1-5.2 原子命题公式或它的否定称为句节（literal ，或称文字）。

定义1-1-5.3 有限个句节的析取式称为一个子句（clause）；对偶地，有限个句节的合取式称为一个短语（phrase）。

定义1-1-5.4 有限个子句的合取式（即析取式的合取式）称为合取范式；对偶地，有限个的短语的析取式（即合取式的析取式）称为析取范式。

例1-1-5.2 设P，Q为原子命题公式，则P，Q，?P，?Q，都是句节。 P? Q，P??Q，?P?Q ，?P??Q 都是子句，P? Q，P??Q，?P?Q，?P??Q都

29

是短语。P?Q，(P?Q)?(?P?Q)都是合取范式，?P?Q，(P?Q)?(?P??Q)都是析取范式。又如P，Q，R为原子命题公式，P ? Q，?Q?R 是子句，P?Q?R，P??R是短语，R?(P?Q)是合取范式，(?P?R)?(P?Q)是析取范式。

例1-1-5.3 一个子句或一个短语既是合取范式又是析取范式。 定理 1-1-5.3 给定任一个命题公式，必有与之等价的合取范式和析取范式。

证明： 若A为任一命题公式，用下列算法可以得出与A等价的合（析）取范式：

(1) 若A不含“→”或“?”，转(2)。若A含“→”或“?”，用基本等价式删去 “→”或“?”使A等价于只含?，?或 ? 的公式。

(2) 用德·摩根律将A中“?”移到原子命题变元前面并用对合律化简之。 (3) 反复使用分配律，交换律，结合律等就可得到等价于A的合取范式或析取范式。

例1-1-5.4 求?P→(P→Q)的合取和析取范式。 解： ?P→(P→Q)??P?(?P?Q)

?P?(?P? Q) （合析取范式） ?(P??P)?Q

?T?Q （合析取范式） ?T?P??P。

例1-1-5.5 求?(P?Q)?P?Q的合取和析取范式。 解： ?(P?Q)?(P?Q)

? (?(P?Q)?(P?Q))?(P?Q??(P?Q)) ? ((P?Q)?(P?Q))?(?(P?Q)??(P?Q))

? ((P?Q)?P)?( (P?Q)?Q))?((?P??Q)?(?P??Q))

? (P?Q)? ((?P??Q)??P)?( (?P??Q)??Q)) ? (P?Q)? (?P??Q) (合取范式) ? ( (P?Q)??P)?( (P?Q)??Q) ? (?P?Q)?(P??Q) (析取范式)

从上面的例子可以看出一个命题公式的合取范式和析取范式仍然有若干个，并不是唯一的，因而讨论时还是不够方便，故再引入下列的主范式概念

30

（或称正则范式）。

定义 1-1-5.5 取而且只取n个原子命题变元中每一个的句节一次构成的子句（短语）称为关于这n个变元的极大项（极小项）。

例1-1-5.6 P?Q?R，?P??Q?R是关于P，Q，R的极小项，但?P，P??Q就不是关于P，Q，R的极小项，P??Q是关于P，Q的极小项，?P是关于P的极小项。又如?P?Q??R，P??Q??R是关于P，Q，R的极大项，但P??Q不是关于P，Q，R的极大项，只是关于P，Q的一个极大项。

注意：n个原子命题变元共可构成2n 个极大项和2n 个极小项。 下面列出两个原子命题变元和三个原子命题变元的极大项真值表：

P 1 1 0 0 Q 1 0 1 0 P?Q 1 1 1 0 P??Q 1 1 0 1 ?P?Q 1 0 1 1 ?P??Q 0 1 1 1

P 1 1 1 1 0 0 0 0 Q 1 1 0 0 1 1 0 0 R 1 0 1 0 1 0 1 0 P?Q?R 1 1 1 1 1 1 1 0 P?Q??R 1 1 1 1 1 1 0 1 P??Q?R 1 1 1 1 1 0 1 1 P??Q??R 1 1 1 1 0 1 1 1

P 1 1 1 1 0 0 0 0 Q 1 1 0 0 1 1 0 0 R 1 0 1 0 1 0 1 0 ?P?Q?R 1 1 1 0 1 1 1 1 ?P?Q??R 1 1 0 1 1 1 1 1 ?P??Q?R 1 0 1 1 1 1 1 1 ?P??Q??R 0 1 1 1 1 1 1 1 从上述真值表可以看出： (1) 没有两个极大项是等价的；

31

(2) 只有一组真值指派使一个极大项取值为0 ，其余极大项在这个指派下取值为1。这不仅是两个或三个变元的情况，对四个或更多的变元也有同样的性质。

设给定的n个原子命题变元已经指定了一种排列次序为P1，P2 ，?，Pn ，关于这n个原子命题变元的2n个极大项记为M0,M1,?,M2n?1,将每个M的下标表示成n位二进制数

n n n n

(如0=00?0，5=00?101，8=00?01000,2n–1=11?1)，

即对M进行了编码,如何通过这样的二进制编码来写出相应的极大项呢?若M的下标所示二进制数左起第j位上出现0,则极大项中出现Pj，若第j位上出现1, 则极大项中出现?Pj 。例如关于P，Q，R的极大项P?Q?┐R编码项为M001 ，?P?Q?R为M100 ，M010表示极大项P??Q?R，M111表示极大项?P??Q??R 。

极大项具有下列性质：

(1)每个极大项当且仅当真值指派与编码相同时真值才为0，其余2n-1组真值指派使其真值为1；

(2)任意两个极大项的析取式为重言式； （例如M000 ? M100=(P?Q?R)?(?P?Q?R)? T）

(3)全体极大项的合取式为矛盾式(不可满足式),(由性质1可以得证)。 定义1-1-5.6 设P1，P2，?，Pn 是公式A中出现的原子命题变元，A的一个等价合取范式中的每一个子句都是关于的P1，P2，?，Pn 极大项,则称该合取范式为A的主(正则)合取范式。

定理 1-1-5.4 在公式A的真值表中，使A的取值为0的指派所对应的极大项的合取式就是A的主合取范式。

证明：设使A的取值为0的指派所对应的极大项为M1 ，M2 ，?，M k ，B=M1?M2???Mk 。现证A与B等价。

对使A取值为0的任一指派必使一个且只有一个极大项M i取值为0，故B取值为0，而使A取值为1的指派，其对应的极大项都不在B出现，这些指派使M1 ，M2 ，?, M k 取值为1，而B取值为1。因而A与B等价，而B是主合取范式。

32

例1-1-5.7 求A=(P?Q)?(Q?R)?(?P?R)主合取范式。

解： 因为A是合取范式不是主合取范式，可以求出真值表来根据定理1-1-5.4求之。

P 1 1 1 1 0 0 0 0 Q 1 1 0 0 1 1 0 0 R 1 0 1 0 1 0 1 0 P?Q 1 1 1 1 1 1 0 0 Q?R 1 1 1 0 1 1 1 0 ?P?R 1 0 1 0 1 1 1 1 (P?Q)?(Q?R)?(?P?R) 1 0 1 0 1 1 0 0 对应于真值指派 110，100，001，000，A取值为0的极大项分别为 M110= ?P??Q?R ，M100=?P?Q?R，M001=P?Q??R，M000=P?Q?R，

故所求的主合取范式为：

(?P??Q?R)?(?P?Q?R)?(P?Q??R)?(P?Q?R)

除了用真值表方法外，还可以利用基本等价式来构成主合取范式。 定理 1-1-5.5 任意命题合式公式均可利用基本等价式来构成主合取范式。

证明: 据定理1-1-5.3，A有合取范式A?使A?A?。设A ，A?中出现的原子命题变元为P1，P2，?，Pn 。

检查A?中的子句Ai?，若Ai?不是关于P1，P2，?，Pn 的极大项，则必缺若干个变元的句节，设Pi1，?，Pik的句节在Ai?中没有出现，则可以根据基本等价式P??P?F和P?F?P使这些句节出现在子句Ai?中，即

Ai??Ai??F?Ai??(Pi1??Pi1)???(Pik??Pik)再利用结合律，分配律就可以使Ai?等价于一些极大项的合取。对A?中所有非极大项的子句都作上述处理，最后终可得到等价于A的主合取范式。

上面的例1-1-5.7再按定理1-1-5.5 的证明过程（实际上是一个算法）求主合取范式如下：

A?(P?Q)?(Q?R) ?(?P?R)

? ((P?Q)?(R??R))?((Q?R)?(P??P))?((?P?R)?(Q??Q))

?(P?Q?R)?(P?Q??R)?(P?Q?R)(?P?Q?R)?(?P?Q?R)?(?P??Q?R)

33

?(P?Q?R)?(P?Q??R)?(?P?Q?R)?(?P??Q?R)。

将此式与真值法求得的结果作比较，可以看出主合取范式是一样的。实际上不论用什么方法，在不计句节，子句的次序时求公式的主合取范式都应该是相同，根据为下面的定理1-1-5.6， 1-1-5.7。

定理 1-1-5.6 公式G和H是关于原子命题变元P1，P2，?，Pn 的两个主合取范式，如果G与H不完全相同，则G与H不等价。

证明 因为G和H不完全相同，故或者是G中至少有一个极大项Mi不在H中。或者是H中至少有一个极大项Mi不在G中，不妨设G中极大项Mi不在H中，根据极大项的性质，Mi所对应的二进制编码所对应的真值指派使Mi取值为0，而其余的极大项都取1，故G的值为0，H的值取为1，因此G与H不等价。

定理 1-1-5.7 任一命题合式公式A必有唯一的与A等价的主合取范式存在（不计句节和子句的次序）。

由定理1-1-5.5，1-1-5.6立即得证。 对偶地，立即可得到

(1) 没有两个极小项是等价的。

(2) 只有一组真值指派使一个极小项取值为1，其余极小项在此指派下取值为0。

设给定的n个原子命题变元已经排列为P1 ，P2 ，? ，Pn 时，关于它们的2n 个极小项记为m0,m1,m2,?,m2n?1。将m i 的下标表为n位二进制数，就是将m i 进行了编码。若m i 下标所示二进制数左起第j位上出现0，则极小项中出现句节?Pj，若左起第j位出现1，则极小项中出现句节Pj。

例如关于P，Q的极小项m01=?P?Q，m00 =?P??Q；关于P，Q，R的小项m101=P??Q?R，m000=?P??Q??R。 极小项的性质为：

(1)每个极小项当且仅当其真值指派与编码相同时取值为1，其余2n-1 组指派取值为0；

(2)任意两个极小项的合取式为矛盾式； (3)全体极小项的析取式为重言式。

定义 1-1-5.7 P1，P2，?，Pn 是公式A中出现的原子命题变元，A的一个等价析取范式中的每一短语都是关于P1，P2，?，Pn 的极小项，则称该析取

34

范式为主（正则）析取范式。

根据定理1-1-5.2 ，1-1-5.4 ，1-1-5.7立即得证下之两个定理。

定理 1-1-5.8 在公式A的真值表中,使A取值1的真值指派所对应的极小项的析取式就是A的主析取范式。

定理 1-1-5.9 任一公式不计句节和短语的次序时都有唯一的与之等价的主析取范式。

例1-1-5.8 求例1-1-5.7中A的主析取范式。 解法一: 由真值表及定理1-1-5.8得A的主析取范式为

(P?Q?R)?(P??Q?R)?(?P?Q?R)?(?P?Q??R).

解法二: A?(P?Q)?(Q?R)?(?P?R)

?(((P?Q)?Q)?((P?Q)?R))?(?P?R) （结合律，分配律） ?(Q?(P?R)?(Q?R))?(?P?R) （吸收律，分配律） ?(Q?(P?R))?(?P?R) （吸收律，交换律） ?(Q?(?P?R))?((P?R)?(?P?R)) （分配律） ?(Q??P)?(Q?R)?(P?R?(?P?R))) （分配律，结合律） ?(Q??P))?(Q?R)?(P?R) （吸收律）

?((Q??P)?(R??R))?((Q?R)?(P??P))?((P?R)?(Q??Q))

?(?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).

用基本等价式得出一个公式的主合（析）取范式的步骤归纳如下： 第一步：将公式A变换为等价的合（析）取范式A?； 第二步：除去A?中所有永真（假）的合（析）取项； 第三步：合并相同的析（合）取项和相同的变元；

第四步：对子句（短语）Ai?补入没有出现的变元X，即Ai??(X??X)

(Ai??(X??X),)然后用分配律展开公式的项，如果需要的话再用交换律、结合律、幂等律等合并相同的极大（小）项。

35

1-1-5 习 题

1．将下列公式化为析取范式和合取范式： （1） P?(Q?R?S); （3）(P?Q)?R

（2）?(P??Q)?(S?T); （4） (?P?Q)?(P??Q);

（5）(?P??Q)?(P??Q);

（6） (P?(Q?R))?(?P?(?Q??R));

2. 用两种方法将上题中各公式的主合取范式与主析取范式求出来。 3．重言式和矛盾式的主合取范式和主析取范式是什么？ 4．用化为范式的方法判断下列公式是否等价： (1)(P?Q)?P?Q, (?P?Q)?(Q?P); （2）(P?Q)?(P?R), P?Q?R.

5．判断下列公式是重言式还是矛盾式（化为范式）： （1） (A?B?C)?(?A?(?B??C)); （2） A?(A?B?A); （3） (B?A)?(?A?B); （4） (?A??B)?(A??B).

6．从A，B，C，D四个人中派二人出差，要求符合以下条件：若A去为必需C，D中去一人B，C不能同去，若C去为D必须留下，问如何派去。

7．A，B，C，D四个队参加足球比赛，有三个球迷预测比赛结果，第一人认为“A第一，B第二”，第二人认为“C第二，D第四”，第三人认为“A第二，D第四”，结果三人都对了一半，问四个队的名次如何。

§1-1-6 其它逻辑联结词

§1-1-1中已将常用的逻辑联结词的符号意义和作用作了讲叙，并指出了应该注意的地方。本节将对计算机设计，开关理论，电子元件中常用的逻辑联结词和另一些基本的逻辑联结词进行讨论。

定义 1-1-6.1 由命题公式P和Q产生的新命题P?Q称为P和Q的不可

36

兼或，其真值表为

P 1 1 0 0 Q 1 0 1 0 P?Q 0 1 1 1

P 1 1 0 0 Q 1 0 1 0 P?Q 0 1 1 0

不可兼或已在1-1-1中举过实际例子。“”有下列基本等价式： (1) P?Q?Q?P； (2) (P?Q)?R?P?(Q?R)；

(3) P? (Q?R)? (P?Q)?(P?R)； (4) P?Q? (P??Q)?(?P?Q)； (5) P?Q??(P?Q)；

(6) P?P?F , P?F?P , P?T??P 。 以上等价式可以用真值表法加以证明。

定义 1-1-6.2 由命题公式P和Q产生的新命题公式P?Q与P?Q分别称为P和Q的“与非”与“或非”，其真值表分别为

P 1 1 0 0 Q 1 0 1 0 P?Q 0 0 0 1 “?”和“?”有如下等价式，最基本的为：

（1） P?P??(P?P)??P ； （2）(P?Q)?(P?Q)??(P?Q)? P?Q ；

（3）(P?P)?(Q?Q)??P??Q??(?P??Q)? P?Q ； （4） P? P?? (P?P)??P ； （5）(P?Q)?(P?Q)??(P?Q)?P?Q ；

（6）(P?P)?(Q?Q)??P??Q??(?P??Q)?P?Q。 由§1-1-5的对偶概念和定理知“?”与“?”互为对偶。 例1-1-6.1 A=P?(Q??(R? P))，求A* 。 解： A* =P?(Q??(R?P))。

例1-1-6.2 A= (A?B)?(B?B)，求A*

37

解： A* =((A?B)?(B?B))*

=((?A?B)?(B?B))* =(?A?B)?(B?B)。

命题是能判别真假的陈述句，即是说命题的值只有两个：真（1），假（0）。这是二值逻辑。而各种电的机械的器件常常考虑两种可能的状态，如开、关；通过、不通过；传导、不传导；啮合、不啮合；顺时针方向、逆时针方向等等，现在加以推广，即通过的不仅是电，机械物，各种液体，也可以是信息，?。因此将上述开关等术语统一称为“门”，逻辑联结词?，?，?，?，?，? 分别称为非门，与门，或门，异或门，与非门，或非门，涉及到的原子命题变元真值指派称为输入,逻辑连结词产生的公式在真值指派下运算的结果称为输出.在理论和实际设计中为了便于讨论,对上述各种”门”采用下列图示标号:

非门 P ?P

与非门 P P?Q

Q

Q

与门 P P?Q

Q 或门 P P?Q

或非门 ： P P?Q Q

P

异或门 Q P?Q

P

Q

上面的各种门(组件)可以按图示互相连结,恰当地选取就能实现所要求的逻辑表达式(命题公式),经过联结后的“门”图称为逻辑网络(组合网络)。

由于一个命题公式可以有多个等价的表达式，因如形成逻辑网络的方式也就不同，对生产和维护来说，需要考虑设计的技巧，使用单一种类的门常常比使用多种类型的门或使用较少的门比使用较多的门要方便或便宜些，有时也常利用对偶性使一个门即可作与非门有又可作或非门用,这些设计思想在大规模集成电路中已经采用。

例1-1-6.3 某仓库装有一个警报系统,它只在保卫部门的一个人工控制开关关闭时进行工作。当此人工开关关闭时，如果通到设施范围内的禁区的门有盗贼进入，或者保卫人员还没有关闭一个专门开关时，设施的主要出入口就已

38

打开。则报警器鸣响。设计此控制线路。

解: 令 A：警报器鸣响，B：关闭人工控制开关，C：设施的主要出入口打开，D:禁区的门有盗贼进入，E:专门开关关闭。

则 A=B?(D?(?E?C))

故控制线路图

E C D B A 例1-1-6.4 一家航空公司，为了保证安全，用三台计算机同时复核飞行计划是否正确。由计算机所给的答案，根据少数服从多数的原则作出计划是否正确的判断，试画出逻辑网络。

解：设P，Q，R表示3台计算机，C表示判断结果，由题设得真值表如下：

P 1 1 1 1 0 0 0 0 Q 1 1 0 0 1 1 0 0 R 1 0 1 0 1 0 1 0 C 1 1 1 0 1 0 0 0

据1-1-5.4定理得

C=(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??R))?((P?R)?(Q??Q))?((Q?R)?(P??P)) ?((P?Q)?T)?((P?R)?T)?((Q?R)?T) ?(P?Q)?(P?R)?(Q?R) 故逻辑网络为

P Q

C

R 39

除了上述常用的逻辑联结词：?，?，?，?，?，?，?，?以外，还

?c??”（或记为???，称为条件否定），其真值表为 有逻辑联结词“?P 1 1 0 0 Q 1 0 1 0 P?Q 0 1 0 0 c

????实际是?与?复合而成，故不在作讨论。

1-1-6 习 题

1．用真值表验证“?”的基本等价式。

2.“?”的结合律中括号能否去掉不写？为什么？ 3.“?”和“?”满足结合律吗？

4.将下列各式用?（或?）的等价式表示出来，并尽可能简化。

（1）（P?Q）??P ； （2）?Q??P?（?R??P）； （3）（P?Q??R）??P?Q ； （4）P?（?P?Q）。

5.设计一个盥洗室的照明电路，使分别装在卧室和盥洗室的两个开关都能控制照明。

6.设计十字路口的自动控制线路，要求：传感器中计数器的内容C?5时亮绿灯，C?2 时亮红灯，2?C?5 时亮黄灯。

7.一个小型演播厅共四个门，每道门有一个双态开关，要求设计出线路能在改变一个开关状态时，都能改变演播厅的亮或暗，假若厅里没有人的时候暗，有人时亮，试画出电路图（尽可能简单）。

8.一个二进制译码器是有n条输入线和2n条输出线的装置，且输入与输出合于：对每组输入只有一条输出值为1，其余输出线的输出值为0，对此译码器设计一种极小电路。

§1-1-7 逻辑联结词的功能完备集

§1-1-6与§1-1-1两节我们已经看到了利用真值表定义了九个逻辑联结词，是否还可以定义其他联结词呢？有没有必要再定义呢？这九个联结词是否

40

本文来源：https://www.bwwdw.com/article/8hh6.html