第 1章 命题逻辑
1.1 命题与联结词
1.2 命题公式及其分类
1.3 等值演算
1.4 命题公式的标准形式
1.5 命题演算的推理理论第 1章 命题逻辑人类的高级思维是通过各种方式加以表达的，其中，
最重要的是通过语言，也就是自然语言,当用自然语言叙述时往往不够确切，也易产生二义性，对于进行严密的推理有诸多不利,因此，就需要引入一种目标语言，这种目标语言和一些公式符号就形成了数理逻辑的形式符号体系,
其中，目标语言就是表达判断的一些语言的集合，而判断就是对事物有肯定或否定回答的一种思维形式,
命题逻辑也称命题演算或语句逻辑,它研究以命题为基本单位构成的前提和结论之间的可推导关系，研究什么是命题、如何表示例题以及如何由一组前提推导一些结论,
本章将详细讨论这些问题,
1.1 命题与联结词
1.1.1命题的概念
1.1.2逻辑联结词
1.1.3命题的符号化
1.1.1 命题的概念数理逻辑研究的中心问题是推理，而推理的前提和结论是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位，于是我们称判断真假的陈述句为命题,为此，我们可以说：命题逻辑的研究对象是命题,
定义 1.1-1 凡是可以判断真假的陈述句均称为命题,
命题有两个特征：
（ 1）命题必须是陈述句，而不是感叹句、疑问句、祈使句等句型,
（ 2）命题是具有真值的,当一个命题是一个正确命题时，
命题的真值为真，用字母 T表示 ;当一个命题是错误命题时，
命题的真值为假，用字母 F表示,
因此，命题又称为具有确定真值的陈述句,
1.1.1 命题的概念真值就是语句为真或假的性质,一个语句的真值可以为真也可以为假,真值不是说该语句的值必为真,
任一命题必有其真值，也称为这个命题的值,既然是命题了，那它必有一个确定的真值，不管这个真值为真还是为假,当一个陈述句能够分辨其值的真假时 (也就是说，
总可以肯定是其中的某一个 )，它就是命题，
即使我们不知道它是真还是假,
1.1.1 命题的概念定义 1.1-2 命题具有两种类型，简单命题和复合命题,
（ 1）第一种类型是不可分隔或不可再分解为更简单句子的命题，称为简单命题或原子命题,通常用小写英文字母 p,q,r,…,pi,qi,ri,….
（ 2）第二种类型是由简单命题利用联结词而成的命题，称为复合命题,
例如，“雪是白的”，,2为质数”，“南京是江苏省的省会”等就是简单命题,
复合命题与联系词是密切相关的，不包含联结词的命题就是原子命题，至少包含一个联结词的命题才是复合命题,
1.1.1 命题的概念定义 1.1-3 对于简单命题来说，它的真值是确定的，因而又称为命题常项或命题常元，例 1.1（见教材第 3页） 中的（ 1）、
（ 2）、（ 3）命题常项,在例 1.1中的（ 6）
不是命题，但当给定 x与 y确定的值后，它的真值也就定了下来了，这种真值可以变化的简单陈述句称为命题变项或命题变元,
1.1.2 逻辑联结词常用的联结词有 ﹁,∧,∨,→,? 五种。
定义 1.1-4 设 p为任一命题，复合命题
“非 p”(或,p的否定” )称为 p的否定式，记作 ﹁ p,称,﹁,为否定联结词,﹁ p为真当且仅当 p为假．
自然语言中的“不是”、“没有”、
非”、“不”等都可表示否定,
1.1.2 逻辑联结词定义 1.1-5 设 p,q为命题，复合命题
,p并且 q”(或,p和 q”)称作 p与 q 的合取式，
记作 p∧ q,称,∧,为合取联结词,p∧ q为真当且仅当 p与 q同时为真,
自然语言中的“并且”、“同时”、
“和”、“既 …… 又 ……”,“不但 …… 而且 ……”,“虽然 …… 但是 ……” 等都可表示合取,
1.1.2 逻辑联结词定义 1.1-6 设 p,q为命题，复合命题,p
或 q”称作 p与 q的析取式，记作 p∨ q,称
,∨,为析取联结词,p∨ q为真当且仅当 p与
q中一个为真,
自然语言中的“或者”，“或许”，
“可能”等都可表示析取,
1.1.2 逻辑联结词定义 1.1-7 设 p,q为命题，复合命题
“如果 p,则 q”称作 p与 q的蕴涵式，记作
p→q,称 p为蕴涵式的前件,q为蕴涵式的后件，,→,为蕴涵联结词,p→q 为假当且仅当 p为真且 q为假,
自然语言中的“若 …… 则 ……,、“假如 …… 那么 ……,、“既然 …… 那就 ……,、“倘若 …… 就 ……,等都可表示蕴涵,
1.1.2 逻辑联结词定义 1.1-8 设 p,q为命题，复合命题,p
当且仅当 q”称作 p与 q的等价式，记作 p?
q，称,?,为等价联结词,p? q 为真当且仅当 p,q真值相同,
自然语言中的“当且仅当”、“充分必要”、“相同”、“一样”等都可表示等价,
1.1.3 命题的符号化由于通常对一些命题及推理是用自然语言表达的，首先需要把自然语言形式化为逻辑语言,即以符号表示命题，用联结词联结命题,
同时，应注意自然语言通常带有多义性，人们对同一语句有不同的理解，导致同一语句不等价的逻辑描述,
在将命题逻辑中的命题进行符号化处理时，首先要分清是原子命题还是复合命题，其次再将命题符号化,一般地，对于原子命题用大写英文字母来表示肯定语句，对于否定语句在肯定语句前面加上“非（﹁）”联结词；对于复合命题要进行分析，根据复合命题所陈述的含义，将复合命题分解成若干原子命题，再选用适当的联结词，然后可以将复合命题符号化,
1.2 命题公式及其分类
1.2.1 命题公式
1.2.2 真值表及命题公式的分类
1.2.1 命题公式常用的联结词及由它们组成的基本复合命题：﹁ p、
p∧ q,p∨ q,p→q,p? q，其中 p,q为简单命题，即命题常项,当然由这 5种联结词和多个命题常项可以组成更复杂的复合命题,若在复合命题中,p,q,r等不仅可以代表命题常项，还可以代表命题变项，这样组成的复合命题形式称为命题公式,
通常把含有命题变元的断言称为命题公式,但这没能指出命题公式的结构，因为不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式,为此常使用归纳定义命题公式，以便使构成的公式有规则可循,由这种定义产生的公式称为命题公式,
1.2.1 命题公式定义 1.2-1 命题标识符、逻辑联结词和圆括号按照一定的正确规则组成的合式，称为命题公式
（合式公式），简称公式,对于命题公式给出如下规定：
（ 1）单个命题常项或变项是命题公式,
（ 2）如果 A是命题公式，则 ﹁ A也是命题公式,
（ 3）如果 A,B是命题公式，则 (A∨ B)、
( A∧ B),(A→B),(A? B)也是命题公式,
（ 4）当且仅当有限次运用（ 1）、（ 2）、（ 3）
所组成的符号串是命题公式,
1.2.1 命题公式定义 1.2-2 （ 1）若 A是单个命题（常项或变项），如 p，
q,r,…,p i,q i,r i,…,0,1,则称 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的层次同②,
（ 3）若 A的最高层次为 k，则称 k层公式,
定义中的符号,=”为通常意义下的等号，以下再出现时意义相同,由定义可知,(p∧ ﹁ q)→r 是 3层公式； ﹁ p∨ q
是 2层公式； p∧ q∧ r是 2层公式,
1.2.2 真值表及命题公式的分类定义 1.2-3 设 A为含有命题变元 p1,p2,…,p n的命题公式,给 p1,p2,…,p n指定一组真值，这称为对 A的一个赋值或解释,
命题公式不是命题，因为它的真值是不确定的，只有当公式中的每一个命题变元都被指定的命题常项代替后，公式的真值才能被确定，从而成为一个命题,例如，公式（ P∧ Q） → （ P∨ ﹁ Q）
对命题变项 P,Q,R没有真值指定，故该公式没有确定的真值，不是命题,
1.2.2 真值表及命题公式的分类定义 1.2-4 设 A为一命题公式，
p1,p2,…,p n为出现在 A中所有的命题变项,给 p1,p2,…,p n指定一组真值，
称为对 A的一个赋值或解释,若指定的一组值使 A的值为真，则称这组值为 A的成真赋值；若使 A的值为假，则称这组值为 A的成假赋值,
1.2.2 真值表及命题公式的分类定义 1.2-5 对于公式中所有命题变元的每一种可能的真值指派（也叫公式的一个赋值或解释），将公式在所有赋值之下取值的情况列成表，称为该公式的真值表,
1.2.2 真值表及命题公式的分类定义 1.2-6 设 A 为任意一个命题公式，
则
（ 1）若 A在它的各种赋值下取值均为真，
则称 A 为重言式或永真式,常用,1”表示,
（ 2）若 A在它的各种赋值下取值均为假，
则称 A 为矛盾式或永假式,常用,0” 表示,
（ 3）若 A至少存在一组赋值是成真赋值，
则称 A 为可满足式,
1.2.2 真值表及命题公式的分类定义 1.2-7 若 A和 B为重言式，则 A∧ B
和 A∨ B仍是重言式,
用定义即可直接证明,
1.3 等值演算
1.3.1 两命题公式间的等值关系
1.3.2 重要等值式
1.3.3 等值演算
1.3.1 两命题公式间的等值关系
A为一命题公式,p1,p2,…,pn为出现在 A中所有的命题变项,给 p1,p2,…,pn指定一组真值，
称为对 A的一个赋值或解释,对于 A的这个赋值或解释，至少能找到另外一个命题公式 B，与 A的这个赋值或解释完全相同,下面给出命题公式 A和 B赋值或解释相同的严格定义,
定义 1.3-1 设 A,B为两命题公式，若等价式
A? B是重言式，则称 A与 B是等值的,记作 A B.
1.3.2重要等值式
1.A∨ B B∨ A,A∧ B B∧ A.（交换律）
2.(A∨ B)∨ C A∨ (B∨ C)，
(A∧ B)∧ C A∧ (B∧ C).（结合律）
3.A∨ (B∧ C) (A∨ B)∧ (A∨ C)，
A∧ (B∨ C) (A∧ B)∨ (A∧ C).（分配律）
4.﹁ (A∨ B) A∧ ﹁ B，
﹁ (A∧ B) A∨ ﹁ B.（德 ·摩根律）
5.A∨ A A,A∧ A A.（等幂律）
6.A∨ (A∧ B) A,A∧ (A∨ B) A.（吸收律）
7.A∨ 1 1,A∧ 0 0.（零律）
8.A∨ A A,A∧ 1 A.（同一律）
9.A∨ ﹁ A 1,(排中律 )
A∧ ﹁ A 0.(矛盾律 )（互否律）
10,﹁ （ ﹁ A A.（双重否定律）
11.A→B A∨ B.（蕴涵等值式）
12.A? B (A→B) ∧ (B→A),（等价等值式）
13.A→B B→ ﹁ A.（假言易位）
14.A? B A? ﹁ B.（等价否定等值）
15,(A→B) ∧ (A→ ﹁ B) A.（归谬论）
1.3.3 等值演算在进行等值演算时，还往往用到置换规则,
等值置换定理 设 C是命题公式 A的子公式且
C D,则将 A中的 C部分或全部替换成 D所得到的命题公式与 A等值,
证明 因为 C D，即对它们的命题变元作任何真值指派,C与 D的真值相同，因此用 D代替 C
后，公式 B与 A在对其命题变元作相应的任何真值指派，它们的真值仍相同，所以 A B.
定义 1.3-2 利用基本等值式以及等值置换定理求解问题的方法称为等值演算法,
1.4 命题公式的标准形式
1.4.1 范式
1.4.2 对偶
1.4.3 主范式
1.4.1 范式定义 1.4-1 仅由有限个命题变项或其否定构成的析取式称为简单析取式,仅由有限个命题变项或其否定构成的合取式称为简单合取式,
给定命题变项 p,q、﹁ p、﹁ q,p∨ q、
﹁ p∨ q,p∨ ﹁ q,﹁ p∨ ﹁ q等都是简单析取式，而 p,q、
﹁ p、﹁ q,p∧ q,﹁ p∧ q,p∧ ﹁ q、﹁ p∧ ﹁ q等都是简单合取式,
从定义不难看出以下两点：
(1) 一个简单析取式是重言式,当且仅当它同时含一个命题变项及其否定 ;
(2) 一个简单合取式是矛盾式,当且仅当它同时含一个命题变项及其否定,
1.4.1 范式定义 1.4-2（ 1）仅由有限个简单合取式构成的析取式称为析取范式；
（ 2）仅由有限个简单析取式构成的合取式称为合取范式,
设 A＝ A1∨ A2∨ … ∨ An,Ai (i＝ 1,2,…,n) 为简单合取式，
则 A是析取范式；
设 A＝ A1∧ A2∧ … ∧ An,Ai (i＝ 1,2,…,n) 为简单析取式,
则 A是合取范式,
析取范式和合取范式有以下性质：
(1) 一个析取范式是矛盾式,当且仅当它的每个简单合取式都是矛盾式 ;
(2) 一个合取范式是重言式,当且仅当它的每个简单析取式都是重言式,
1.4.1 范式定理 1.4-1 (范式存在定理 )任一命题公式存在着与之等值的析取范式和合取范式,
任给一个命题公式 A,经过以下三步演算,
即得到一个与 A等值的析取范式或合取范式,
1.4.2 对偶定义 1.4-3 在仅含了联结词﹁,∧,∨ 的命题公式 A
中，将 ∨ 换成 ∧,∧ 换成 ∨,0换成 1,1换成 0，得到的公式 A*称为 A的对偶式,
由定义可以看出,A也是 A*的对偶式，即对偶式是相互的，且有 (A*)* ＝ A.
例如,p∨ q对偶式为 p∧ q，（ p∨ q） ∧ r对偶式为
（ p∧ q） ∨ r，（ p∧ q） ∨ 0对偶式为（ p∨ q） ∧ 1.
定理 1.4-2 设 A和 A*互为对偶式,p1,p2,…,p n是出现在
A和 A*中的全部的命题变项,若将 A和 A*写成 n元函数形式,
则
(1) ﹁ A(p1,p2,…,p n) A*(﹁ p1,﹁ p2,…,﹁ pn)；
(2) A(﹁ p1,﹁ p2,…,﹁ pn) A*(p1,p2,…,pn).
1.4.2 对偶定理 1.4-3 设 A,B为二个公式，若 A
B，则 A* B*，其中 A*,B*分别为 A,B的对偶式,
1.4.3 主范式定义 1.4-4 在含 n个命题变项的简单合取式中,若每个命题变项与其否定不同时存在,而两者之一必出现且仅出现一次,且第 i个命题变项或其否定出现在从左起的第 i位上
(若命题变项无角标,则按字典顺序排序 ),这样的简单合取式称为极小项,
定义 1.4-5 设命题公式 A中含 n个命题变项,如果 A的析取范式中的简单合取式全是极小项，则称该析取范式为 A的主析取范式,
1.4.3 主范式定理 1.4-4 任何命题公式的主析取范式都是存在的,并且是唯一的,
求给定命题公式 A的主析取范式的步骤如下：
(1)求 A的析取范式 A′；
(2)若 A′的某简单合取式 B中不含命题变项 pi或其否定
﹁ pi,则将 B展成如下形式：
B B∧ 1 B∧ (pi∨ ﹁ pi) (B∧ pi)∨ (B∧ ﹁ pi);
(3)将重复出现的命题变项、矛盾式及重复出现的极小项都“消去”,如 p∧ p用 p取代,p∧ ﹁ p用 0取代,mi∨ mi用 mi
取代 ;
(4)将极小项按由小到大的顺序排列,并用 Σ表示之，如
m1∨ m2∨ m5用 Σ(1,2,5)表示,
1.4.3 主范式定义 1.4-6 在含 n个命题变项的简单析取式中,若每个命题变项与其否定不同时存在,而两者之一必出现且仅出现一次,且第 i个命题变项或其否定出现在左起的第 i位上 (若命题变项无角码,则按字典顺序排列 ),这样的简单析取式称为极大项,
定义 1.4-7 设命题公式 A中含 n个命题变项,如果 A的合取范式中的简单析取式全是极大项,则称该合取范式为主合取范式,
1.5 命题演算的推理理论
1.5.1 推理的概念
1.5.2 构造证明
1.5.1 推理的概念定义 1.5-1 推理是从前提推出结论的思维过程，前提就是推理所根据的已知的命题，结论则是从前提出发通过推理而得到的新命题,
前提可多个，由前提 A1,A2,…,Ak推出结论 B的严格定义如下,
定义 1.5-2 若（ A1∧ A2∧ … ∧ Ak） →B 为重言式，则
A1,A2,…,Ak推出结论 B的推理正确,B是 A1,A2,…,
Ak的逻辑结论或有效结论,称（ A1∧ A2∧ … ∧ Ak） →B 为由前提 A1,A2,…,Ak推出结论 B的推理的形式结构,
与用,A B”表示,A? B”是重言式类似，用,A
B”表示,A→B,是重言式,因而，若由前提 A1,A2,…,
Ak 推出结论 B的推理正确，也记作
（ A1∧ A2∧ … ∧ Ak B,
一组前提是否可以推出某个结论，可以按照定义进行判断,
1.5.2 构造证明
1．重要的推理定律
（ 1） A (A∨ B);附加
（ 2） (A∧ B) A;化简
（ 3） ((A→B) ∧ A) B;假言推理
（ 4） ((A→B) ∧ ﹁ B) A;拒取式
（ 5） ((A∨ B)∧ ﹁ A) B;析取三段论
（ 6） ((A→B) ∧ (B→C)) (A→C); 假言三段论
（ 7） ((A? B)∧ (B? C)) (A? C)；等价三段论
（ 8） (A→B) ∧ (C→D) ∧ (A∨ C) (B∨ D).构造性二难
1.5.2 构造证明
2.构造证明法依照推理规则，应用推理规律,
在使用构造证明法来进行推理时，常常采用一些技巧，下面介绍其中的几种,同时也通过例题说明如何利用以上的规则及定律构造证明及几种常用的证明有效结论的方法,
（ 1）直接证明法直接证明法就是利用所给的条件，根据推理定律一步步找到结论的过程,
（ 2）附加前提法并不是直接证明法适合于所有题目，附加前提证明法有时要证明的结论以蕴含式的形式出现，即推理的形式结构为
(A1∧ A2∧ … ∧ Ak)→(A→B).
（ 3）归谬法归谬法也称为反证法，是把结论的否定作为附加前提，与给定的前提一起推证若能引出矛盾，说明结论是有效的,
1.5.2 构造证明定义 1.5-3 设 A1,A2,…,A k是命题公式，如果对任意的公式 R，有
A1∧ A2∧ … ∧ Ak R∧ ﹁ R,
则称公式 A1,A2,…,A k是不相容的；否则称为相容的,
定理 1.5-1 设 A1,A2,…,A k,C是公式，且
A1,A2,…,A k是相容的，若 A1,A2,…,A k,﹁ C是不相容的，则 C是 A1,A2,…,A k的有效结论,
本章小结本章主要讨论了：
（ 1）命题概念、含义及其真值表；命题符号化方法,
（ 2）命题公式的定义及公式的真值表；重言式和矛盾式的定义及使用真值表进行判断命题公式的类型,
（ 3）掌握两公式等值的定义；给出重要等值式，并能利用其进行等值演算,
（ 4）简单析取式、简单合取式、对偶式、析取范式、
合取范式、极小项、主析取范式、极大项、主合取范式等基本概念；如何求主析取范式和主合取范式,
（ 5）给出推理的概念、推理定律、推理规则；掌握构造证明法；了解附加前提证明法和归谬法,
1.1 命题与联结词
1.2 命题公式及其分类
1.3 等值演算
1.4 命题公式的标准形式
1.5 命题演算的推理理论第 1章 命题逻辑人类的高级思维是通过各种方式加以表达的，其中，
最重要的是通过语言，也就是自然语言,当用自然语言叙述时往往不够确切，也易产生二义性，对于进行严密的推理有诸多不利,因此，就需要引入一种目标语言，这种目标语言和一些公式符号就形成了数理逻辑的形式符号体系,
其中，目标语言就是表达判断的一些语言的集合，而判断就是对事物有肯定或否定回答的一种思维形式,
命题逻辑也称命题演算或语句逻辑,它研究以命题为基本单位构成的前提和结论之间的可推导关系，研究什么是命题、如何表示例题以及如何由一组前提推导一些结论,
本章将详细讨论这些问题,
1.1 命题与联结词
1.1.1命题的概念
1.1.2逻辑联结词
1.1.3命题的符号化
1.1.1 命题的概念数理逻辑研究的中心问题是推理，而推理的前提和结论是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位，于是我们称判断真假的陈述句为命题,为此，我们可以说：命题逻辑的研究对象是命题,
定义 1.1-1 凡是可以判断真假的陈述句均称为命题,
命题有两个特征：
（ 1）命题必须是陈述句，而不是感叹句、疑问句、祈使句等句型,
（ 2）命题是具有真值的,当一个命题是一个正确命题时，
命题的真值为真，用字母 T表示 ;当一个命题是错误命题时，
命题的真值为假，用字母 F表示,
因此，命题又称为具有确定真值的陈述句,
1.1.1 命题的概念真值就是语句为真或假的性质,一个语句的真值可以为真也可以为假,真值不是说该语句的值必为真,
任一命题必有其真值，也称为这个命题的值,既然是命题了，那它必有一个确定的真值，不管这个真值为真还是为假,当一个陈述句能够分辨其值的真假时 (也就是说，
总可以肯定是其中的某一个 )，它就是命题，
即使我们不知道它是真还是假,
1.1.1 命题的概念定义 1.1-2 命题具有两种类型，简单命题和复合命题,
（ 1）第一种类型是不可分隔或不可再分解为更简单句子的命题，称为简单命题或原子命题,通常用小写英文字母 p,q,r,…,pi,qi,ri,….
（ 2）第二种类型是由简单命题利用联结词而成的命题，称为复合命题,
例如，“雪是白的”，,2为质数”，“南京是江苏省的省会”等就是简单命题,
复合命题与联系词是密切相关的，不包含联结词的命题就是原子命题，至少包含一个联结词的命题才是复合命题,
1.1.1 命题的概念定义 1.1-3 对于简单命题来说，它的真值是确定的，因而又称为命题常项或命题常元，例 1.1（见教材第 3页） 中的（ 1）、
（ 2）、（ 3）命题常项,在例 1.1中的（ 6）
不是命题，但当给定 x与 y确定的值后，它的真值也就定了下来了，这种真值可以变化的简单陈述句称为命题变项或命题变元,
1.1.2 逻辑联结词常用的联结词有 ﹁,∧,∨,→,? 五种。
定义 1.1-4 设 p为任一命题，复合命题
“非 p”(或,p的否定” )称为 p的否定式，记作 ﹁ p,称,﹁,为否定联结词,﹁ p为真当且仅当 p为假．
自然语言中的“不是”、“没有”、
非”、“不”等都可表示否定,
1.1.2 逻辑联结词定义 1.1-5 设 p,q为命题，复合命题
,p并且 q”(或,p和 q”)称作 p与 q 的合取式，
记作 p∧ q,称,∧,为合取联结词,p∧ q为真当且仅当 p与 q同时为真,
自然语言中的“并且”、“同时”、
“和”、“既 …… 又 ……”,“不但 …… 而且 ……”,“虽然 …… 但是 ……” 等都可表示合取,
1.1.2 逻辑联结词定义 1.1-6 设 p,q为命题，复合命题,p
或 q”称作 p与 q的析取式，记作 p∨ q,称
,∨,为析取联结词,p∨ q为真当且仅当 p与
q中一个为真,
自然语言中的“或者”，“或许”，
“可能”等都可表示析取,
1.1.2 逻辑联结词定义 1.1-7 设 p,q为命题，复合命题
“如果 p,则 q”称作 p与 q的蕴涵式，记作
p→q,称 p为蕴涵式的前件,q为蕴涵式的后件，,→,为蕴涵联结词,p→q 为假当且仅当 p为真且 q为假,
自然语言中的“若 …… 则 ……,、“假如 …… 那么 ……,、“既然 …… 那就 ……,、“倘若 …… 就 ……,等都可表示蕴涵,
1.1.2 逻辑联结词定义 1.1-8 设 p,q为命题，复合命题,p
当且仅当 q”称作 p与 q的等价式，记作 p?
q，称,?,为等价联结词,p? q 为真当且仅当 p,q真值相同,
自然语言中的“当且仅当”、“充分必要”、“相同”、“一样”等都可表示等价,
1.1.3 命题的符号化由于通常对一些命题及推理是用自然语言表达的，首先需要把自然语言形式化为逻辑语言,即以符号表示命题，用联结词联结命题,
同时，应注意自然语言通常带有多义性，人们对同一语句有不同的理解，导致同一语句不等价的逻辑描述,
在将命题逻辑中的命题进行符号化处理时，首先要分清是原子命题还是复合命题，其次再将命题符号化,一般地，对于原子命题用大写英文字母来表示肯定语句，对于否定语句在肯定语句前面加上“非（﹁）”联结词；对于复合命题要进行分析，根据复合命题所陈述的含义，将复合命题分解成若干原子命题，再选用适当的联结词，然后可以将复合命题符号化,
1.2 命题公式及其分类
1.2.1 命题公式
1.2.2 真值表及命题公式的分类
1.2.1 命题公式常用的联结词及由它们组成的基本复合命题：﹁ p、
p∧ q,p∨ q,p→q,p? q，其中 p,q为简单命题，即命题常项,当然由这 5种联结词和多个命题常项可以组成更复杂的复合命题,若在复合命题中,p,q,r等不仅可以代表命题常项，还可以代表命题变项，这样组成的复合命题形式称为命题公式,
通常把含有命题变元的断言称为命题公式,但这没能指出命题公式的结构，因为不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式,为此常使用归纳定义命题公式，以便使构成的公式有规则可循,由这种定义产生的公式称为命题公式,
1.2.1 命题公式定义 1.2-1 命题标识符、逻辑联结词和圆括号按照一定的正确规则组成的合式，称为命题公式
（合式公式），简称公式,对于命题公式给出如下规定：
（ 1）单个命题常项或变项是命题公式,
（ 2）如果 A是命题公式，则 ﹁ A也是命题公式,
（ 3）如果 A,B是命题公式，则 (A∨ B)、
( A∧ B),(A→B),(A? B)也是命题公式,
（ 4）当且仅当有限次运用（ 1）、（ 2）、（ 3）
所组成的符号串是命题公式,
1.2.1 命题公式定义 1.2-2 （ 1）若 A是单个命题（常项或变项），如 p，
q,r,…,p i,q i,r i,…,0,1,则称 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的层次同②,
（ 3）若 A的最高层次为 k，则称 k层公式,
定义中的符号,=”为通常意义下的等号，以下再出现时意义相同,由定义可知,(p∧ ﹁ q)→r 是 3层公式； ﹁ p∨ q
是 2层公式； p∧ q∧ r是 2层公式,
1.2.2 真值表及命题公式的分类定义 1.2-3 设 A为含有命题变元 p1,p2,…,p n的命题公式,给 p1,p2,…,p n指定一组真值，这称为对 A的一个赋值或解释,
命题公式不是命题，因为它的真值是不确定的，只有当公式中的每一个命题变元都被指定的命题常项代替后，公式的真值才能被确定，从而成为一个命题,例如，公式（ P∧ Q） → （ P∨ ﹁ Q）
对命题变项 P,Q,R没有真值指定，故该公式没有确定的真值，不是命题,
1.2.2 真值表及命题公式的分类定义 1.2-4 设 A为一命题公式，
p1,p2,…,p n为出现在 A中所有的命题变项,给 p1,p2,…,p n指定一组真值，
称为对 A的一个赋值或解释,若指定的一组值使 A的值为真，则称这组值为 A的成真赋值；若使 A的值为假，则称这组值为 A的成假赋值,
1.2.2 真值表及命题公式的分类定义 1.2-5 对于公式中所有命题变元的每一种可能的真值指派（也叫公式的一个赋值或解释），将公式在所有赋值之下取值的情况列成表，称为该公式的真值表,
1.2.2 真值表及命题公式的分类定义 1.2-6 设 A 为任意一个命题公式，
则
（ 1）若 A在它的各种赋值下取值均为真，
则称 A 为重言式或永真式,常用,1”表示,
（ 2）若 A在它的各种赋值下取值均为假，
则称 A 为矛盾式或永假式,常用,0” 表示,
（ 3）若 A至少存在一组赋值是成真赋值，
则称 A 为可满足式,
1.2.2 真值表及命题公式的分类定义 1.2-7 若 A和 B为重言式，则 A∧ B
和 A∨ B仍是重言式,
用定义即可直接证明,
1.3 等值演算
1.3.1 两命题公式间的等值关系
1.3.2 重要等值式
1.3.3 等值演算
1.3.1 两命题公式间的等值关系
A为一命题公式,p1,p2,…,pn为出现在 A中所有的命题变项,给 p1,p2,…,pn指定一组真值，
称为对 A的一个赋值或解释,对于 A的这个赋值或解释，至少能找到另外一个命题公式 B，与 A的这个赋值或解释完全相同,下面给出命题公式 A和 B赋值或解释相同的严格定义,
定义 1.3-1 设 A,B为两命题公式，若等价式
A? B是重言式，则称 A与 B是等值的,记作 A B.
1.3.2重要等值式
1.A∨ B B∨ A,A∧ B B∧ A.（交换律）
2.(A∨ B)∨ C A∨ (B∨ C)，
(A∧ B)∧ C A∧ (B∧ C).（结合律）
3.A∨ (B∧ C) (A∨ B)∧ (A∨ C)，
A∧ (B∨ C) (A∧ B)∨ (A∧ C).（分配律）
4.﹁ (A∨ B) A∧ ﹁ B，
﹁ (A∧ B) A∨ ﹁ B.（德 ·摩根律）
5.A∨ A A,A∧ A A.（等幂律）
6.A∨ (A∧ B) A,A∧ (A∨ B) A.（吸收律）
7.A∨ 1 1,A∧ 0 0.（零律）
8.A∨ A A,A∧ 1 A.（同一律）
9.A∨ ﹁ A 1,(排中律 )
A∧ ﹁ A 0.(矛盾律 )（互否律）
10,﹁ （ ﹁ A A.（双重否定律）
11.A→B A∨ B.（蕴涵等值式）
12.A? B (A→B) ∧ (B→A),（等价等值式）
13.A→B B→ ﹁ A.（假言易位）
14.A? B A? ﹁ B.（等价否定等值）
15,(A→B) ∧ (A→ ﹁ B) A.（归谬论）
1.3.3 等值演算在进行等值演算时，还往往用到置换规则,
等值置换定理 设 C是命题公式 A的子公式且
C D,则将 A中的 C部分或全部替换成 D所得到的命题公式与 A等值,
证明 因为 C D，即对它们的命题变元作任何真值指派,C与 D的真值相同，因此用 D代替 C
后，公式 B与 A在对其命题变元作相应的任何真值指派，它们的真值仍相同，所以 A B.
定义 1.3-2 利用基本等值式以及等值置换定理求解问题的方法称为等值演算法,
1.4 命题公式的标准形式
1.4.1 范式
1.4.2 对偶
1.4.3 主范式
1.4.1 范式定义 1.4-1 仅由有限个命题变项或其否定构成的析取式称为简单析取式,仅由有限个命题变项或其否定构成的合取式称为简单合取式,
给定命题变项 p,q、﹁ p、﹁ q,p∨ q、
﹁ p∨ q,p∨ ﹁ q,﹁ p∨ ﹁ q等都是简单析取式，而 p,q、
﹁ p、﹁ q,p∧ q,﹁ p∧ q,p∧ ﹁ q、﹁ p∧ ﹁ q等都是简单合取式,
从定义不难看出以下两点：
(1) 一个简单析取式是重言式,当且仅当它同时含一个命题变项及其否定 ;
(2) 一个简单合取式是矛盾式,当且仅当它同时含一个命题变项及其否定,
1.4.1 范式定义 1.4-2（ 1）仅由有限个简单合取式构成的析取式称为析取范式；
（ 2）仅由有限个简单析取式构成的合取式称为合取范式,
设 A＝ A1∨ A2∨ … ∨ An,Ai (i＝ 1,2,…,n) 为简单合取式，
则 A是析取范式；
设 A＝ A1∧ A2∧ … ∧ An,Ai (i＝ 1,2,…,n) 为简单析取式,
则 A是合取范式,
析取范式和合取范式有以下性质：
(1) 一个析取范式是矛盾式,当且仅当它的每个简单合取式都是矛盾式 ;
(2) 一个合取范式是重言式,当且仅当它的每个简单析取式都是重言式,
1.4.1 范式定理 1.4-1 (范式存在定理 )任一命题公式存在着与之等值的析取范式和合取范式,
任给一个命题公式 A,经过以下三步演算,
即得到一个与 A等值的析取范式或合取范式,
1.4.2 对偶定义 1.4-3 在仅含了联结词﹁,∧,∨ 的命题公式 A
中，将 ∨ 换成 ∧,∧ 换成 ∨,0换成 1,1换成 0，得到的公式 A*称为 A的对偶式,
由定义可以看出,A也是 A*的对偶式，即对偶式是相互的，且有 (A*)* ＝ A.
例如,p∨ q对偶式为 p∧ q，（ p∨ q） ∧ r对偶式为
（ p∧ q） ∨ r，（ p∧ q） ∨ 0对偶式为（ p∨ q） ∧ 1.
定理 1.4-2 设 A和 A*互为对偶式,p1,p2,…,p n是出现在
A和 A*中的全部的命题变项,若将 A和 A*写成 n元函数形式,
则
(1) ﹁ A(p1,p2,…,p n) A*(﹁ p1,﹁ p2,…,﹁ pn)；
(2) A(﹁ p1,﹁ p2,…,﹁ pn) A*(p1,p2,…,pn).
1.4.2 对偶定理 1.4-3 设 A,B为二个公式，若 A
B，则 A* B*，其中 A*,B*分别为 A,B的对偶式,
1.4.3 主范式定义 1.4-4 在含 n个命题变项的简单合取式中,若每个命题变项与其否定不同时存在,而两者之一必出现且仅出现一次,且第 i个命题变项或其否定出现在从左起的第 i位上
(若命题变项无角标,则按字典顺序排序 ),这样的简单合取式称为极小项,
定义 1.4-5 设命题公式 A中含 n个命题变项,如果 A的析取范式中的简单合取式全是极小项，则称该析取范式为 A的主析取范式,
1.4.3 主范式定理 1.4-4 任何命题公式的主析取范式都是存在的,并且是唯一的,
求给定命题公式 A的主析取范式的步骤如下：
(1)求 A的析取范式 A′；
(2)若 A′的某简单合取式 B中不含命题变项 pi或其否定
﹁ pi,则将 B展成如下形式：
B B∧ 1 B∧ (pi∨ ﹁ pi) (B∧ pi)∨ (B∧ ﹁ pi);
(3)将重复出现的命题变项、矛盾式及重复出现的极小项都“消去”,如 p∧ p用 p取代,p∧ ﹁ p用 0取代,mi∨ mi用 mi
取代 ;
(4)将极小项按由小到大的顺序排列,并用 Σ表示之，如
m1∨ m2∨ m5用 Σ(1,2,5)表示,
1.4.3 主范式定义 1.4-6 在含 n个命题变项的简单析取式中,若每个命题变项与其否定不同时存在,而两者之一必出现且仅出现一次,且第 i个命题变项或其否定出现在左起的第 i位上 (若命题变项无角码,则按字典顺序排列 ),这样的简单析取式称为极大项,
定义 1.4-7 设命题公式 A中含 n个命题变项,如果 A的合取范式中的简单析取式全是极大项,则称该合取范式为主合取范式,
1.5 命题演算的推理理论
1.5.1 推理的概念
1.5.2 构造证明
1.5.1 推理的概念定义 1.5-1 推理是从前提推出结论的思维过程，前提就是推理所根据的已知的命题，结论则是从前提出发通过推理而得到的新命题,
前提可多个，由前提 A1,A2,…,Ak推出结论 B的严格定义如下,
定义 1.5-2 若（ A1∧ A2∧ … ∧ Ak） →B 为重言式，则
A1,A2,…,Ak推出结论 B的推理正确,B是 A1,A2,…,
Ak的逻辑结论或有效结论,称（ A1∧ A2∧ … ∧ Ak） →B 为由前提 A1,A2,…,Ak推出结论 B的推理的形式结构,
与用,A B”表示,A? B”是重言式类似，用,A
B”表示,A→B,是重言式,因而，若由前提 A1,A2,…,
Ak 推出结论 B的推理正确，也记作
（ A1∧ A2∧ … ∧ Ak B,
一组前提是否可以推出某个结论，可以按照定义进行判断,
1.5.2 构造证明
1．重要的推理定律
（ 1） A (A∨ B);附加
（ 2） (A∧ B) A;化简
（ 3） ((A→B) ∧ A) B;假言推理
（ 4） ((A→B) ∧ ﹁ B) A;拒取式
（ 5） ((A∨ B)∧ ﹁ A) B;析取三段论
（ 6） ((A→B) ∧ (B→C)) (A→C); 假言三段论
（ 7） ((A? B)∧ (B? C)) (A? C)；等价三段论
（ 8） (A→B) ∧ (C→D) ∧ (A∨ C) (B∨ D).构造性二难
1.5.2 构造证明
2.构造证明法依照推理规则，应用推理规律,
在使用构造证明法来进行推理时，常常采用一些技巧，下面介绍其中的几种,同时也通过例题说明如何利用以上的规则及定律构造证明及几种常用的证明有效结论的方法,
（ 1）直接证明法直接证明法就是利用所给的条件，根据推理定律一步步找到结论的过程,
（ 2）附加前提法并不是直接证明法适合于所有题目，附加前提证明法有时要证明的结论以蕴含式的形式出现，即推理的形式结构为
(A1∧ A2∧ … ∧ Ak)→(A→B).
（ 3）归谬法归谬法也称为反证法，是把结论的否定作为附加前提，与给定的前提一起推证若能引出矛盾，说明结论是有效的,
1.5.2 构造证明定义 1.5-3 设 A1,A2,…,A k是命题公式，如果对任意的公式 R，有
A1∧ A2∧ … ∧ Ak R∧ ﹁ R,
则称公式 A1,A2,…,A k是不相容的；否则称为相容的,
定理 1.5-1 设 A1,A2,…,A k,C是公式，且
A1,A2,…,A k是相容的，若 A1,A2,…,A k,﹁ C是不相容的，则 C是 A1,A2,…,A k的有效结论,
本章小结本章主要讨论了：
（ 1）命题概念、含义及其真值表；命题符号化方法,
（ 2）命题公式的定义及公式的真值表；重言式和矛盾式的定义及使用真值表进行判断命题公式的类型,
（ 3）掌握两公式等值的定义；给出重要等值式，并能利用其进行等值演算,
（ 4）简单析取式、简单合取式、对偶式、析取范式、
合取范式、极小项、主析取范式、极大项、主合取范式等基本概念；如何求主析取范式和主合取范式,
（ 5）给出推理的概念、推理定律、推理规则；掌握构造证明法；了解附加前提证明法和归谬法,
