第一部分数理逻辑第一章命题逻辑【教学目的】：1.熟练掌握命题、联结词、复合命题、命题公式及其解释的概念；2.熟练掌握常用的基本等值式及其应用：3.熟练掌握（主）析/合取范式的求法及其应用；4.熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用；5.熟练掌握形式演绎的方法。6.熟练掌握命题、联结词、复合命题、命题公式及其解释的概念：7.熟练掌握常用的基本等值式及其应用：8.熟练掌握（主）析/合取范式的求法及其应用；9.熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用；10.熟练掌握形式演绎的方法。【教学重点】：命题的概念及判断：联结词、命题的翻译：主析（合）取范式的求法：逻辑推理。【教学难点】：主析（合）取范式的求法；逻辑推理；形式演绎【教学方法】：讲授【时数】：理论课9学时【教学内容】数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其他分支、计算机科学、人工智能、语言学等学科均有密切的联系。总地说来，就目前离散数学课程中的主要内容，其应用体现在如下方面：第一，数理逻辑。数理逻辑除了对逻辑本身的贡献外，还在计算机硬件设计中广泛应用。利用命题、联接词的运算规律可以建立起高低电平所表示的信号的运算与二进制数据运算之间的联系，进而用于非门和或非门解决电路设计问题。同时，利用命题演算，可以对程序中的判断进行化简。第二，笛卡尔积与关系。关系型数据库是目前数据库系统中的主流，其重要原因是具有完整的理论基础，就是笛卡尔积与关系，以及建立在此之上的关系演算。关系数据模型建立在严格的集合代数基础上，每一张表构成一个关系，进而可以通过笛卡尔积和关系理论实现表中的数据查询、连接、投影等一系列运算。第三，抽象代数系统(结构)。抽象代数结构在研究形式语言与自动机理论、编码理论、关系数据库理论、抽象数据类型与表示理论，可计算的函数、可计算性与计算复杂性及程序设计学中的形式语义学中有着十分广泛的应用，其中，半群理论在形式语言和自动机理论中有着重要的应用，有限域理论是编码理论的数学基础，在通讯中发挥了重要作用。第四，布尔代数。布尔代数是逻辑电路设计的基础，利用布尔代数研究对开关电路的研究构成了完整的数字逻辑理论。第五，组合分析。计算机的计算模型、硬件体系结构的设计与实现、代数编码、软件设计与实现、计算机通信与密码学等都广泛使用了整数数论及组合数学。第六，图论。讨论的应用极其广泛，覆盖了计算机应用的大部分领域，如信息论、控制论、运输网络、博奔论、人工智能、形式语言、编译原理、操作系统等。离散结构可以
第一部分 数理逻辑 第一章 命题逻辑 【教学目的】： 1.熟练掌握命题、联结词、复合命题、命题公式及其解释的概念； 2.熟练掌握常用的基本等值式及其应用； 3.熟练掌握（主）析/合取范式的求法及其应用； 4.熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用； 5.熟练掌握形式演绎的方法。 6.熟练掌握命题、联结词、复合命题、命题公式及其解释的概念； 7.熟练掌握常用的基本等值式及其应用； 8.熟练掌握（主）析/合取范式的求法及其应用； 9.熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用； 10.熟练掌握形式演绎的方法。 【教学重点】：命题的概念及判断；联结词、命题的翻译；主析（合）取范式的求法；逻辑 推理。 【教学难点】：主析（合）取范式的求法；逻辑推理；形式演绎 【教学方法】：讲授 【时数】：理论课 9 学时 【教学内容】： 数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其他 分支、计算机科学、人工智能、语言学等学科均有密切的联系。 总地说来，就目前离散数学课程中的主要内容，其应用体现在如下方面： 第一，数理逻辑。数理逻辑除了对逻辑本身的贡献外，还在计算机硬件设计中广泛应 用。利用命题、联接词的运算规律可以建立起高低电平所表示的信号的运算与二进制数据 运算之间的联系，进而用于非门和或非门解决电路设计问题。同时，利用命题演算，可以 对程序中的判断进行化简。 第二，笛卡尔积与关系。关系型数据库是目前数据库系统中的主流，其重要原因是具 有完整的理论基础，就是笛卡尔积与关系，以及建立在此之上的关系演算。关系数据模型 建立在严格的集合代数基础上，每一张表构成一个关系，进而可以通过笛卡尔积和关系理 论实现表中的数据查询、连接、投影等一系列运算。 第三，抽象代数系统(结构)。抽象代数结构在研究形式语言与自动机理论、编码理 论、关系数据库理论、抽象数据类型与表示理论，可计算的函数、可计算性与计算复杂性 及程序设计学中的形式语义学中有着十分广泛的应用，其中，半群理论在形式语言和自动 机理论中有着重要的应用，有限域理论是编码理论的数学基础，在通讯中发挥了重要作 用。 第四，布尔代数。布尔代数是逻辑电路设计的基础，利用布尔代数研究对开关电路的 研究构成了完整的数字逻辑理论。 第五，组合分析。计算机的计算模型、硬件体系结构的设计与实现、代数编码、软件 设计与实现、计算机通信与密码学等都广泛使用了整数数论及组合数学。 第六，图论。讨论的应用极其广泛，覆盖了计算机应用的大部分领域，如信息论、控 制论、运输网络、博弈论、人工智能、形式语言、编译原理、操作系统等。离散结构可以
依据图论来组织和理解，平面图和树的理论可以解决印刷电路的布线问题，编译原理中通过语法编译树完成对源程序语法结构的分析，操作系统中依据图论实现对并发进程中的递归和死锁现象判定，而一些著名的问题如地图着色及四色定理、船夫过河问题、任务分配问题等都是图论与组合学的经典应第七，形式语言与自动机。程序设计采用的语言就是一种形式语言。自动机则是描述计算模型和识别语言与可计算函数的工具，这些理论在编译程序理论、人工智能、可计算性和时序电路设计领域应用广泛。引例：1.张三说；李四撤谎。李四说；王五撒谎。王五说：他们两个都撒谎。问，哪个说的真话？2.农民和小偷3.土耳其商人和帽子的故事4.巧猜围棋子5.那两个人作案1.1命题符号化及联结词数理逻辑研究的中心问题是推理，而推理的前提和结论都是表达判断的判断的陈述句。称能判断真假的陈述句为命题，又可称命题是具有唯一真值的陈述句。例1.1判断下列句子中那些是命题判断一个句子是否是为命题，首先要看它是否为陈述句，然后再看它的真值是否是唯一的，真值是否唯一与我们是否知道它的真值是两回事。命题都是简单的陈述句，都不能分解成更简单的句子，称这样的命题为简单命题或原子命题。将表示命题的符号放在该命题的前面，称为命题符号化，例如，P：2是素数真值可以变化的简单陈述句称为命题变项或命题变元，命题变项不是命题。在命题逻辑中，主要是研究由简单命题用联结词联结而成的命题，这样的命题称为复合命题。例1.2将下列命题符号化下面给出5种常用联结词的符号表示及相应复合命题的严格定义。定义1.1设p为任一命题。复合命题“非p”称为p的否定式，记作-p。7为否定联结词。定义1.2设p、q为两命题。复合命题“p并且q”称作p与q的合取式，记作p^q。入为合取联结词。定义1.3设p、q为两命题。复合命题“p或q”称作p与q的析取式，记作pVq。V为析取联结词。例1.3将下列命题符号化定义1.4设p、q为两命题。复合命题“如果p，则q”称作p与q的蕴涵式，记作p-q，称p为蕴涵式的前件，q为蕴涵式的后件。-→称为蕴涵联结词。p-→q为假当且仅当p为真且q为假。在数理逻辑中，当前件p为假时，p-q为真。例1.4将下列命题符号化定义1.5设p、q为两命题。复合命题“p当且仅当q”称作p与q的等价式，记作p
依据图论来组织和理解，平面图和树的理论可以解决印刷电路的布线问题，编译原理中通 过语法编译树完成对源程序语法结构的分析，操作系统中依据图论实现对并发进程中的递 归和死锁现象判定，而一些著名的问题如地图着色及四色定理、船夫过河问题、任务分配 问题等都是图论与组合学的经典应 第七，形式语言与自动机。程序设计采用的语言就是一种形式语言。自动机则是描述 计算模型和识别语言与可计算函数的工具，这些理论在编译程序理论、人工智能、可计算 性和时序电路设计领域应用广泛。 引例： 1 .张三说；李四撒谎。李四说；王五撒谎。王五说；他们两个都撒谎。问，哪个说的真 话？ 2.农民和小偷 3.土耳其商人和帽子的故事 4.巧猜围棋子 5.那两个人作案 1.1 命题符号化及联结词 数理逻辑研究的中心问题是推理，而推理的前提和结论都是表达判断的判断的陈述句。 称能判断真假的陈述句为命题，又可称命题是具有唯一真值的陈述句。 例 1.1 判断下列句子中那些是命题 判断一个句子是否是为命题，首先要看它是否为陈述句，然后再看它的真值是否是唯一 的，真值是否唯一与我们是否知道它的真值是两回事。 命题都是简单的陈述句，都不能分解成更简单的句子，称这样的命题为简单命题或原子 命题。 将表示命题的符号放在该命题的前面，称为命题符号化，例如， P：2 是素数 真值可以变化的简单陈述句称为命题变项或命题变元，命题变项不是命题。 在命题逻辑中，主要是研究由简单命题用联结词联结而成的命题，这样的命题称为复合 命题。 例 1.2 将下列命题符号化 下面给出 5 种常用联结词的符号表示及相应复合命题的严格定义。 定义 1.1 设 p 为任一命题。复合命题“非 p”称为 p 的否定式，记作┓p。┓为否定联 结词。 定义 1.2 设 p、q 为两命题。复合命题“p 并且 q”称作 p 与 q 的合取式，记作 p∧q。 ∧为合取联结词。 定义 1.3 设 p、q 为两命题。复合命题“p 或 q”称作 p 与 q 的析取式，记作 p∨q。∨ 为析取联结词。 例 1.3 将下列命题符号化 定义 1.4 设 p、q 为两命题。复合命题“如果 p，则 q”称作 p 与 q 的蕴涵式，记作 p→ q，称 p 为蕴涵式的前件，q 为蕴涵式的后件。→称为蕴涵联结词。p→q 为假当且仅当 p 为 真且 q 为假。 在数理逻辑中，当前件 p 为假时，p→q 为真。 例 1.4 将下列命题符号化 定义 1.5 设 p、q 为两命题。复合命题“p 当且仅当 q”称作 p 与 q 的等价式，记作 p
→q。-称作等价联结词。p+-q真当且仅当p、q真值相同。例1.5分析下列各命题的真值例1.6将下列命题符号化以上介绍的5种常用联结词也成为真值联结词或逻辑联结词。在命题逻辑中，可用这些联结词将各种各样的复合命题符号化。5种联结词符也称为逻辑运算符，它们与普通数的运算符一样，规定运算的优先级，本书规定优先级顺序为一、Λ、V、→、。在自然语言中，命题常项（或变项）往往有某种内在的联系：但在数理逻辑中，命题常项（或变项）不一定有内在联系。1.2命题公式及分类命题公式是由命题常项、命题变项、联结词、括号等组成的符号串，严格定义：定义1.6（1）单个命题常项或变项p，9，r，，p，qi，r，，0，1是合式公式；（2）如果A是合式公式，则（A）也是合式公式；（3）如果A、B为合式公式，则（A^B）、（AVB）、（A→B）、（A→B）也是合式公式；（4）只有有限次地应用（1）～（3）组成的符号串才是合式公式。我们将合式公式称为命题公式，或简称为公式。定义1.7（1）若A是单个命题（常项或变项），则称A是0层公式。（2）称A是n+1(n>=0)层公式是指A符合下列情况之一：①A=B,B是n层分层；②A=BΛC，其中B、C分别为i层和j层公式，且n=max(i，j)：③A=BVC,其中B、C的层次同②；A=B→C,其中B、C的层次同②③A=B+-C,其中B、C的层次同②；定义 1.83设A为一命题公式，pi,P，,p.为出现在A中的所有的命题变项，给指定Pi,P2，",Pa一组真值，称为对A的一个赋值或解释。若指定的一组值使A的值为真。则称这组值为A的成真赋值。含n（n>=1）个命题变项的命题公式，共有2"组赋值。将命题公式A在所有赋值之下取值的情况列成表，称为A的真值表。例1.7求下列命题公式的真值表定义1.9设A为一个命题公式（1）若A在它的各种赋值下取值均为真，则称A为重言式或永真式：（2）若A在它的各种赋值下取值均为假，则称A为矛盾式或永假式：（3）若A至少存在一组赋值是成真赋值，则A是可满足式。1.3等值演算n个命题变项只能生成22n个真值不同的命题公式。例1，3*以两命题真值表为例，具体推理以后说明定义1.10设A、B为两命题公式，若等价式A<>B是重言式，则称A与B是等值的，记作A一B.不难看出命题公式之间的等值关系是自反的、对称的和传递的，因而是等价关系。例1.8判断下列命题公式是否等值
←→q。←→称作等价联结词。p←→q 真当且仅当 p、q 真值相同。 例 1.5 分析下列各命题的真值 例 1.6 将下列命题符号化 以上介绍的 5 种常用联结词也成为真值联结词或逻辑联结词。在命题逻辑中，可用这些 联结词将各种各样的复合命题符号化。 5 种联结词符也称为逻辑运算符，它们与普通数的运算符一样，规定运算的优先级，本 书规定优先级顺序为 、 、 、→、。 在自然语言中，命题常项（或变项）往往有某种内在的联系；但在数理逻辑中，命题常 项（或变项）不一定有内在联系。 1.2 命题公式及分类 命题公式是由命题常项、命题变项、联结词、括号等组成的符号串，严格定义： 定义 1.6 （1）单个命题常项或变项 p，q，r，.，pi，qi，ri，.，0，1 是合式公式； （2）如果 A 是合式公式，则（┓A）也是合式公式； （3）如果 A、B 为合式公式，则（A∧B）、（A∨B）、（A→B）、（A←→B）也是合式公式； （4）只有有限次地应用（1）～（3）组成的符号串才是合式公式。 我们将合式公式称为命题公式，或简称为公式。 定义 1.7 （1）若 A 是单个命题（常项或变项），则称 A 是 0 层公式。 （2）称 A 是 n+1(n>=0)层公式是指 A 符合下列情况之一： ①A=┓B,B 是 n 层分层； ②A=B∧C，其中 B、C 分别为 i 层和 j 层公式，且 n=max(i,j)； ③A=B∨C,其中 B、C 的层次同②； ④A=B→C,其中 B、C 的层次同②； ⑤A=B←→C,其中 B、C 的层次同②； 定义 1.8 设 A 为一命题公式，p1,p2,.,pn 为出现在 A 中的所有的命题变项，给指定 p1,p2,.,pn 一组真值，称为对 A 的一个赋值或解释。若指定的一组值使 A 的值为真。则称这组值为 A 的成真赋值。 含 n(n>=1)个命题变项的命题公式，共有 2 n 组赋值。将命题公式 A 在所有赋值之下 取值的情况列成表，称为 A 的真值表。 例 1.7 求下列命题公式的真值表 定义 1.9 设 A 为一个命题公式 （1） 若 A 在它的各种赋值下取值均为真，则称 A 为重言式或永真式； （2） 若 A 在它的各种赋值下取值均为假，则称 A 为矛盾式或永假式； （3） 若 A 至少存在一组赋值是成真赋值，则 A 是可满足式。 1.3 等值演算 n 个命题变项只能生成 2^2^n 个真值不同的命题公式。 例 1．3*以两命题真值表为例，具体推理以后说明 定义 1.10 设 A、B 为两命题公式，若等价式 A B 是重言式，则称 A 与 B 是等值的，记 作 A B. 不难看出命题公式之间的等值关系是自反的、对称的和传递的，因而是等价关系。 例 1.8 判断下列命题公式是否等值
命题公式之间的等值关系是自反的、对称的和传递的，因而是等价关系。常用公式：（1）蕴涵等值式A→B<=>AVB（2）等价等值式A→B<=>(A→B) ^(B→A)(3)假言易位A-B<=> B→7 A（4）等价否定等值式A+→B<=>A+-→B（5）归谬论(A-B) (A-→B) <=>A有了上述基本等值式后，不用真值表法就可以推演出更多的等值式来。根据已知的等值式，推演出另外一些等值式的过程称为等值演算。在进行等值演算时，还往往用到置换规则。定理1.1设Φ（A）是含命题公式A的命题公式，Φ（B）是用命题公式B置换了Φ（A）中的A之后得到的命题公式，如果A<=>B，则Φ（A）<=>Φ（B)。例1.9验证下列等值式例1.10判断下列公式的类型例1.11用等值演算法解决下面问题1.4连接词全功能集定义1.11设p、q为两命题，复合命题“p、q之中恰有一个成立”称为p与q的排斥或或异或，记作pq。本称作排斥或或异或联结词。pq为真当且仅当p、q中恰有一个为真。定义1.12设p、q为两命题，复合命题“p与q的否定”称为p与q的与非式，记作pq。称作与非联结词。ptq为真当且仅当p、q不同时为真。定义1.13设p、q为两命题，复合命题“p或q的否定”称为p与q的或非式，记作pq。称作或非联结词。pq为真当且仅当p、q同时为假。定义1.14一个n(n>=1)维卡氏积(0，1)"到(0，1)的函数称为一个n元真值函数。设F是一个n元真值函数，则可记为F：(0，1)"→(0，1)。n个命题变项，共有2"个可能的赋值，对于每个赋值真值函数的函数值非0即1，于是n个命题变元共可以形成22″（22n）个不同的真值函数。其实，每个真值函数可对应无穷多个命题公式，它们彼此都是等值的。定义1.15在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为穴余的联结词，否则称为独立的联结词。定义1.16若任真值函数都可以用仅含某一联结词集中的联结词的命题公式表示，则称该联结词集为全功能集。若一个联结词的全功能集中不含余的联结词，则称它是极小全功能集。例1.12分别以下列给出的各联结词集中的联结词写出表1-6中Fs的一个命题公式。F3表示→（p→q）或与其等值的命题公式(1) (-,→); (2) (-,^); (3) (-,V); (4) (t); (5) (4)。例1.13若已知(→，→)是全功能集，证明{→，V)也是全功能集。1.5对偶与范式
命题公式之间的等值关系是自反的、对称的和传递的，因而是等价关系。 常用公式： （1） 蕴涵等值式 A→B<=> ┓A∨B （2） 等价等值式 A←→B<=>(A→B) ∧(B→A) （3） 假言易位 A→B<=> ┓B→┓A （4） 等价否定等值式 A←→B<=>┓A←→┓B （5） 归谬论 (A→B) ∧(A→┓B) <=> ┓A 有了上述基本等值式后，不用真值表法就可以推演出更多的等值式来。根据已知的等 值式，推演出另外一些等值式的过程称为等值演算。 在进行等值演算时，还往往用到置换规则。 定理 1.1 设Φ（A）是含命题公式 A 的命题公式，Φ（B）是用命题公式 B 置换了Φ（A） 中的 A 之后得到的命题公式，如果 A<=>B，则Φ（A）<=>Φ（B）。 例 1.9 验证下列等值式 例 1.10 判断下列公式的类型 例 1.11 用等值演算法解决下面问题 1.4 连接词全功能集 定义 1.11 设 p、q 为两命题，复合命题“p、q 之中恰有一个成立”称为 p 与 q 的排斥 或或异或，记作 p≮q。≮称作排斥或或异或联结词。p≮q 为真当且仅当 p、q 中恰有一个 为真。 定义 1.12 设 p、q 为两命题，复合命题“p 与 q 的否定”称为 p 与 q 的与非式，记作 p↑q。↑称作与非联结词。p↑q 为真当且仅当 p、q 不同时为真。 定义 1.13 设 p、q 为两命题，复合命题“p 或 q 的否定”称为 p 与 q 的或非式，记作 p↓q。↓称作或非联结词。p↓q 为真当且仅当 p、q 同时为假。 定义 1.14 一个 n(n>=1)维卡氏积{0，1}n 到{0，1}的函数称为一个 n 元真值函数。设 F 是一个 n 元真值函数，则可记为 F：{0，1}n→{0，1}。 n 个命题变项，共有 2 n 个可能的赋值，对于每个赋值真值函数的函数值非 0 即 1，于是 n 个命题变元共可以形成 2 2n（2^2^n）个不同的真值函数。其实，每个真值函数可对应无穷 多个命题公式，它们彼此都是等值的。 定义 1.15 在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义， 则称此联结词为冗余的联结词，否则称为独立的联结词。 定义 1.16 若任真值函数都可以用仅含某一联结词集中的联结词的命题公式表示，则 称该联结词集为全功能集。若一个联结词的全功能集中不含冗余的联结词，则称它是极小全 功能集。 例 1.12 分别以下列给出的各联结词集中的联结词写出表 1-6 中 F3 的一个命题公式。 F3 表示┓（p→q）或与其等值的命题公式 （1）{┓，→}；（2）{┓，∧}；（3）{┓，∨}；（4）{↑}；（5）{↓}。 例 1.13 若已知{┓，→}是全功能集，证明{┓，∨}也是全功能集。 1.5 对偶与范式
定义1.17在仅含有联结词-、人、V的命题公式中，将V换成人，人换成V，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记作A。定理1.2设A和A"互为对偶式，pl,p2,",Pa是出现在A和A"中的全部的命题变项，若将A和A写成n元函数形式，则(1) A(pl, p2,"", p.) <=> A" (pl, 7p2,"", p);(2) A (pl, p2, ", 7p.)<=> A(pl,p2, "",p.)。定理1.3设A、B为两命题公式，若A<=>B，则A<=>B，其中A、B分别为A、B的对偶式。定理1.3称为对偶原理。定义1.18仅由有限个命题变项或其否定构成的析取式称为简单析取式，仅由有限个命题变项或其否定构成的合取式称为简单合取式。定义1.199（1）仅有有限个简单合取式构成的析取式称为析取范式：（2）仅由有限个简单析取式构成的合取式称为合取范式。显然任何析取范式的对偶式称为合取范式；当然任何合取范式的对偶式为析取范式。定理1.4（范式存在定理）任一命题公式都存在着与之等值的析取范式和合取范式。任何命题公式的析取范式和合取范式不是唯一的。例1.14求下面命题公式的合取范式和析取范式定义1.20在含n个命题变项的简单合取式中，若每个命题变项与其否定不同时存在，在二者之一必出现且仅出现一次，且第i个命题变项或其否定出现在从左起的第i位上（若命题变项无角标，则按字典顺序排序），这样的简单合取式称为极小项。定义1.21设命题公式A中含n个命题变项，如果A的析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。定理1.5任何命题公式的主析取范式都是存在的，并且是唯一的。例1.15求例1.14中给出的命题公式的主析取范式例1.16试由p^Vr的真值表求它的主析取范式主析取范式有以下用途1.判断两命题公式是否等值任何命题公式的主析取范式都是唯一的。2.判断命题公式的类型设A是含n个命题变项的命题公式，A为重言式，当且仅当A的主析取范式中含全部2n个极小项：A为矛盾式，当且仅当A的主析取范式中不含任何极小项：如A的主析取范式中至少含一个极小值，则A是可满足式。例1.17判断下列公式命题的类型例1.18求p^qVr的主合取范式定义1.22在含n个命题变项的简单析取式中，若每个命题变项与其否定不同时存在，而二者之一必出现仅出现一次，且第i个命题变项或其否定出现在从左起的第i位上（若命题变项无角标，则按字典顺序排序），这样的简单析取式称为极大项。定义1.23设命题公式A中含n个命题变项，如果A的合取范式中的简单析取式全是极大项，则称该合取范式为A的主和取范式。1.6推理理论推理是从前提推出结论的思维过程，前提是指已知的命题公式，结论是从前提出发应用推理规则推出的命题公式，前提可多个。定义1.24若（A^A2^*^Ak）-B为重言式，则称Ar，Az，*，Ax推出结论B的推理真确，B是Ai，Az，***，Ax的逻辑结论或有效结论。称（A^A2^*^A）→B为由前提Ar
定义 1.17 在仅含有联结词┓、∧、∨的命题公式中，将∨换成∧，∧换成∨，若 A 中 含有 0 或 1，就将 0 换成 1，1 换成 0，所得命题公式称为 A 的对偶式，记作 A *。 定理 1.2 设 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)。 定理 1.3 设 A、B 为两命题公式，若 A<=>B，则 A * <=>B*，其中 A *、B *分别为 A、B 的对偶 式。定理 1.3 称为对偶原理。 定义 1.18 仅由有限个命题变项或其否定构成的析取式称为简单析取式，仅由有限个命 题变项或其否定构成的合取式称为简单合取式。 定义 1.19 （1）仅有有限个简单合取式构成的析取式称为析取范式； （2）仅由有限个简单析取式构成的合取式称为合取范式。 显然任何析取范式的对偶式称为合取范式；当然任何合取范式的对偶式为析取范式。 定理 1.4 （范式存在定理）任一命题公式都存在着与之等值的析取范式和合取范式。 任何命题公式的析取范式和合取范式不是唯一的。 例 1.14 求下面命题公式的合取范式和析取范式 定义 1.20 在含 n 个命题变项的简单合取式中，若每个命题变项与其否定不同时存在， 在二者之一必出现且仅出现一次，且第 i 个命题变项或其否定出现在从左起的第 i 位上（若 命题变项无角标，则按字典顺序排序），这样的简单合取式称为极小项。 定义 1.21 设命题公式 A 中含 n 个命题变项，如果 A 的析取范式中的简单合取式全是极 小项，则称该析取范式为 A 的主析取范式。 定理 1.5 任何命题公式的主析取范式都是存在的，并且是唯一的。 例 1.15 求例 1.14 中给出的命题公式的主析取范式 例 1.16 试由 p∧q∨r 的真值表求它的主析取范式 主析取范式有以下用途 1. 判断两命题公式是否等值 任何命题公式的主析取范式都是唯一的。 2. 判断命题公式的类型 设 A 是含 n 个命题变项的命题公式，A 为重言式，当且仅当 A 的主析取范式中含全部 2n 个极小项；A 为矛盾式，当且仅当 A 的主析取范式中不含任何极小项；如 A 的主析取范式 中至少含一个极小值，则 A 是可满足式。 例 1.17 判断下列公式命题的类型 例 1.18 求 p∧q∨r 的主合取范式 定义 1.22 在含 n 个命题变项的简单析取式中，若每个命题变项与其否定不同时存在， 而二者之一必出现仅出现一次，且第 i 个命题变项或其否定出现在从左起的第 i 位上（若命 题变项无角标，则按字典顺序排序），这样的简单析取式称为极大项。 定义 1.23 设命题公式 A 中含 n 个命题变项，如果 A 的合取范式中的简单析取式全是极 大项，则称该合取范式为 A 的主和取范式。 1.6 推理理论 推理是从前提推出结论的思维过程，前提是指已知的命题公式，结论是从前提出发应用 推理规则推出的命题公式，前提可多个。 定义 1.24 若（A1∧A2∧.∧AK）→B 为重言式，则称 A1，A2，.，AK 推出结论 B 的推理 真确，B 是 A1，A2，.，AK 的逻辑结论或有效结论。称（A1∧A2∧.∧AK）→B 为由前提 A1