定义 1.1 设 p 为命题，复合命题“非 p ” (即 “p 的否定”) 称为 p 的否定式，记为 ┐p 。符号 ┐称为否定联结词。

规定：┐p 为真当且仅当 p 为假。

定义1.2 设 p , q 为两个命题。复合命题“ p 与q” 即“p 并且q” 称为 p 与 q 的合取式，记为 p ∧ q 。符号∧称为合取联结词。

规定：p ∧ q为真当且仅当 p 与q 同时为真。(∧读音为Lambda （小写λ）音标：['laemdə] 中文：拉米塔)

定义1.3 设 p , q 为两个命题 , 复合命题 “ p 或 q ” 称为 p 与 q 的析取式, 记为 p ∨q 。符号∨称为析取联结词。

规定： p ∨q 为假当且仅当 p 与 q 同时为假。

定义1.4 设p , q 为两个命题。复合命题 “如果 p , 则 q ”称为p 与q 的蕴涵式，记作p →q 。符号→称为蕴涵联结词， 称p 是蕴涵式的前件，q 是蕴涵式的后件，q 是p 的必要条件。

规定： p →q 为假当且仅当 p 为真q 为假。

假设A 是条件，B 是结论

（1）由A 可以推出B ，由B 可以推出A ，则A 是B 的充要条件(A=B)

（2）由A 可以推出B ，由B 不可以推出A ，则A 是B 的充分不必要条件(A⊆B)

（3）由A 不可以推出B ，由B 可以推出A ，则A 是B 的必要不充分条件(B⊆A)

（4）由A 不可以推出B ，由B 不可以推出A ，则A 是B 的既不充分也不必要条件(A￠B 且B ￠A)

定义1.5 设 p , q 是两个命题，复合命题 “p 当且仅当 q ”称为 p 与 q 的等价式，记为 p↔q。符号↔称为等价联结词。

规定： p↔q 为真当且仅当 p 与 q 同时为真或同时为假。

注：p↔q 可理解为“q 与p 互为充分必要条件”；它与(p →q ) ∧(q →p ) 的逻辑关系完全一致。

多次使用联结词集中的联结词，可组成更为复杂的复合命题。求复杂的复合命题的真值时，可依据上述真值表逐次求取。但运算过程中应注意联结词的优先

顺序(包括括号) ：

( ), ┐, ∧, ∨, →，↔。

对同一优先级的联结词，按出现的先后次序运算。

定义1.6 简单命题（原子命题）称为命题常项，而称真值可以变化的陈述句为命题变项。命题变项一般也用小写字母p,q,r ,…来表示。

将命题变项用联结词和括号按一定逻辑关系联结起来的符号串称为合式公式或命题公式。具体地说, 合式公式定义如下:

(1) 单个命题变项是合式公式, 称为原子命题公式.

(2) 若A 是合式公式, 则(┐A) 也是合式公式.

(3) 若A,B 是合式公式, 则(A∧B),(A∨B),(A→B),(A↔B)也是合式公式.

(4) 只有有限次地应用(1)～(3)形成的符号串才是合式公式.

设A 是合式公式, B是中的一部分, 若B 是合式公式, 则称B 为A 的子公式.

定义1.7 (1) 若命题公式A 是单个命题变项，则称A 为0层公式。

(2) 称命题A 是n +1(n ≥0) 层公式，只要A 是下列情况之一：

(a) A = ┐B, B 是 n 层公式;

(b) A= B∧C, B, C 分别为 i 层和j 层公式，且max (i , j) = n。

(c) A=B∨C, B, C 分别为 i 层和j 层公式，且max ( i , j) = n。

(d) A= B→C, B, C 分别为 i 层和j 层公式，且max ( i , j)= n。 (e) A= B↔C, B, C 分别为 i 层和j 层公式，且max (i , j)= n。

定义 1.8 设在命题公式A 中出现的所有命题变项为p 1 , p 2 , … p n ， 给它们各指定一个真值，称为对公式A 的一个赋值 (或解释) 。若一个赋值使A 的真值为1，则称该赋值为A 的成真赋值，否则称为A 的成假赋值。

定义 1.9 将命题公式A 在所有赋值下的取值情况列成表，称为A 的真值表。含n 个命题变项的公式共有2n 个不同的赋值。构造真值表的一般步骤如下：

(1) 列出命题公式中的所有命题变项 p 1, p 2, … p n ，(无下标时按字典序排列) 。列出这些变项的所有2n 个赋值。一般从00…0开始，按二进制加法依次列到11…1为止。

(2) 按从低到高的顺序依次列出公式的各个层。

(3) 对应于变项的2n 个赋值分别计算出各层的真值，直至算出公式的真值。

定义1.10 设A 是一个命题公式。

(1) 若A 在各种赋值下取值总为1，则称A 是永真式或重言式。

(2) 若A 在各种赋值下取值总为0，则称A 是永假式或矛盾式。

(3) 若A 不是矛盾式，则称A 为可满足式。

注：A 是可满足式当且仅当A 至少存在一个成真赋值。

1. 重言式必是可满足式，但反之不真。

2. 可用真值表来判断公式的类型：

(1) 若真值表最后一列全为1，则公式为重言式；

(2) 若真值表最后一列全为0，则公式为矛盾式；

(3) 若真值表最后一列至少有一个1，则公式为可满足式。

给定n 个命题变项，使用联结词和括号，可构成无穷多个命题公式。

ｎ个命题变项共有 2n 个可能的赋值，而在每个赋值下公式只能取值０或1。因此含ｎ个命题变项的公式其真值表只有22ｎ种可能的情况。从而必有无穷多个公式具有相同的真值表。

设公式Ａ、Ｂ中总共含有命题变项p 1, p 2, … p n ，但Ａ或Ｂ并不全含有这些变项。如果某个变项未在公式Ａ中出现，则称该变项为Ａ的哑元。同样可定义Ｂ的哑元。

在讨论Ａ与Ｂ是否有相同的真值表时，应将哑元考虑在内，即将Ａ、Ｂ都看成含所有p 1 , p 2 , … p n 的命题公式。

定义2.1 设A ,B 是两个命题公式，若A, B构成的等价式A ↔ B为重言式，则称A 与B 是等值的, 记为A ⇔B 。

当命题公式中变项较多时，用上述方法判断两个公式是否等值计算量很大。为此，人们将一组经检验为正确的等值式作为等值式模式，通过公式间的等值演算来判断两公式是否等值。常用的等值式模式如下：

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∨B) ∧(A∨C) (∨对∧的分配律)

A ∧(B∨C) ⇔(A∧B) ∨(A∧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) ⇔(A→B) ∧(B→A)

14. 假言易位: A →B ⇔ ┐B →┐A

15. 等价否定等值式: A ↔B ⇔┐A ↔┐B

16. 归谬论: (A→B) ∧(A→┐B) ⇔ ┐A

利用这16组24个等值式可以推演出更多的等值式。由已知的等值式推演出另一些等值式的过程称为等值演算。在等值演算中, 经常用到如下置换规则。

置换规则: 设Φ(A)是含公式A 的命题公式，Φ(B)是用公式B 置换了Φ(A)中所有的A 后所得的公式。若B ⇔A, 则Φ(B)⇔Φ(A)。

定义2.2 命题变项及其否定统称作文字。

仅由有限个文字构成的析取式称作简单析取式；

仅由有限个文字构成的合取式称作简单合取式。

定理2.1 ：

(1)一个简单析取式是重言式当且仅当它同时含有某个命题变项及它的否定式；

(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及其否定式。

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

由有限个简单析取式构成的合取式成为合取范式；

析取范式与合取范式统称为范式。

注：单个文字既是简单析取式又是简单合取式。

因此形如┐p ∧q ∧r 的公式既是由一个简单合取式构成的析取范式，又是由三个简单析取式构成的合取范式。

类似地，形如p ∨┐q ∨r 的公式既可看成析取范式也可看成合取范式。

析取范式的一般形式：

A ⇔A 1∨ A2∨…∨ An , 其中 A i (i=1,…,n) 是简单合取式；

合取范式的一般形式：

A ⇔A 1∧ A2 ∧… ∧ An , 其中 A i (i=1,…,n) 是简单析取式 。

定理2.2 （1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式；

（2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。

定理2.3 (范式存在定理) 任一命题公式都存在着与之等值的析取范式与合取范式。 求给定公式的范式的步骤：

(1) 消去联结词→和↔；

(2) 否定号┐的消去(双重否定) 或内移(德摩根律) ；

(3) 利用∨对∧的分配律求合取范式；

利用∧对∨的分配律求析取范式。

注：

1. 在演算过程中，利用交换律，可使每个简单析取式或简单合取式中命题变项都按字典序出现。

2. 上述求析取范式的过程中，第二步和第三步结果都是析取范式。这说明命题公式的析取范式是不唯一的。

同样，合取范式也是不唯一的。为了得到唯一的规范化形式的范式，需要定义主析取范式和主合取范式。为此，先引入如下极小项和极大项概念。

定义2.4 在含有n 个命题变项的简单合取式 (简单析取式) 中，若每个命题变项和它的否定式恰好出现一个且仅出现一次，并且命题变项或其否定式按下标从小到大或按字典序排列) ，则称该简单合取式(简单析取式) 为极小项 (极大项) 。 注：由于每个命题变项在极小项中以原形或否定式形式出现且仅出现一次，因而n 个命题变项共可产生2n 个不同的极小项。每个极小项仅有一个成真赋值，若一个极小项的成真赋值对应的二进制数转化为十进制数为i ，则将该极小项记为m i 。

类似地，n 个命题变项可产生2n 个不同的极大项。每个极大项只有一个成假赋值。若一个极大项的成假赋值对应的十进制数为i ，则将该极大项记为M i 。

定理2.4 设m i 与M i 是命题变项p 1, p 2 …,p n 形成的极小项和极大项，则 ┐m i ⇔M i ，┐M i ⇔ m i 。

定义2.5 如果由n 个命题变项构成的析取范式（合取范式）中所有的简单合取式 (简单析取式) 都是极小项（极大项), 则称该析取式（合取式）为主析取范式（主合取范式）。

定理2.5 任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。

主析取范式和主合取范式的用途（以主析取范式为例) 。

1. 求公式的成真与成假赋值;

2. 判断公式的类型;

设公式A 中含n 个变项，则

(1) A 为重言式当且仅当A 的主析取范式含全部2n 个极小项；

(2) A为矛盾式当且仅当A 的主析取范式不含任取极小项。(此时，记A 的主析取范式为0) 。

(3) A 为可满足式当且仅当A 的主析取范式中至少含一个极小项。

3. 判断两公式是否等值;

设公式A, B共有n 个变项。按n 个变项求出A, B的主析取范式。若A 与B 有相同的主析取范式，则A ⇔B; 否则 A/⇔B 。

4. 利用主析取范式和主合取式解决应用问题

定义2.6 称映射F: {0,1}n → {0,1}为n 元真值函数。其中 {0,1}n 表示由0，1组成的长为 n 的字符串集合。

注：每个真值函数与唯一的主析取范式(主合取范式) ）等值，而每个主析取范式(主合取范式) 对应无穷多个与之等值的命题公式。因此每个真值函数对应无穷多个与之等值的命题公式。另一方面，由定理2.5，每个命题公式都有唯一一个真值函数与之等值。

定义2.7 设S 是一个联结词集合。如果任何n 元(n≥1)）真值函数都可以由仅含S 中的联结词构成的公式表示，则称S 是联结词完备集。

定理 2.6 S = {┐，∧，∨}是联结词完备集。

证：因任何n 元真值函数都与唯一一个主析取范式等值，而主析取范式中仅含联结词┐, ∧, ∨, 故结论成立。

推论：以下联结词集都是完备集：

(1) S 1={┐, ∧, ∨, →};

(2) S 2 ={┐, ∧, ∨, →, ↔};

(3) S 3= {┐, ∧};

(4) S 4= {┐, ∨};

(5) S 5= {┐, →}.

定义 2.8. 设p, q 为两个命题。复合命题 “p 与q 的否定式” (“p或q 的否定式”) 称为p, q的“与非式” (“或非式”），记作p↑q (p↓q)。符号↑称作与非联结词(↓称作或非联结词) 。p↑q为真当且仅当p 与q 不同时为真，(p↓q为真当且仅当p 与q 同时为假) 。

定理2.7 {↑}和{↓}都是联结词完备集。

定义3.1 设A 1, A2, „, Ak 和B 是命题公式，若对于A 1, A2, „, Ak , B中出现的命题变项的任一组赋值，要么A 1∧A 2∧„∧A k 为假，要么A 1∧A 2∧„∧A k 为真且B 也为真, 则称由前提A 1, A2, „, Ak 推出B 的推理是有效的（或正确的) ，并称B 是有效的结论.

1、由前提A 1,A 2, „,A k 推结论B 的推理是否正确与诸前提的排列次序无关。 将一个推理诸前提的集合记为Г，则由Г推出结论B 的推理记为Г├ B 。若该推理是正确的，则记为Г╞ B (或Г B), 否则记为Г⊭ B (或Г⇏B) 。称Г├ B 和 {A1,A 2, „,A k }├ B 为推理的形式结构。

设命题公式A 1, A2, …, Ak , B中共有n 个命题变项。对于任一组赋值α1, α2, …, αn (αi 取0或1, i=1,2,…, n), 前提和结论的取值情况有如下四种：

(1) A 1∧A 2∧… ∧ A k 为0，B 为0

(2) A 1∧A 2∧… ∧ A k 为0，B 为1

(3) A 1∧A 2∧… ∧ A k 为1，B 为0

(4) A 1∧A 2∧… ∧ A k 为1，B 为1

按照定义，只要不出现(3)，推理就是正确的。因而判断一个推理正确与否，只需判断是否会出现情况(3)即可。

推理正确，并不能保证结论B 一定为真。因为前提可能是假的(情况(1))。

定理3.1 命题公式 A 1,A 2, …,A k 推 B 的推理正确,

即{A1,A 2, …,A k }╞ B 当且仅当(A1∧A 2∧…∧A k ) →B 为重言式。

由该定理，推理的形式结构：

{A1,A 2, „,A k }┣B （3.1）

可用 (A1∧A 2∧„∧A k ) →B （3.2） 表示

同时{A1,A 2, „,A k }╞ B 换成A 1∧A 2∧„∧A k ⇒B

推理定律

在研究推理过程中，人们发现了一些重要的重言蕴含式，并将它们作为推理定律，在推理过程中可直接引用。常用的推理定律有：

(1) 附加律: A ⇒ A∨B

(2) 化简律: A ∧B ⇒ A

(3) 假言推理: (A→B)∧A ⇒ B

(4) 拒取式: (A→B)∧┐B ⇒ ┐A

(5) 析取三段论: (A∨B) ∧┐B ⇒ A

(6) 假言三段论: (A→B)∧(B→C) ⇒ (A→C)

(7) 等价三段论: (A↔B)∧(B↔C) ⇒ (A↔C)

(8) 构造性二难: (A→B)∧(C→D) ∧(A∨C) ⇒ (B∨D)

构造性二难(特殊形式): (A→B)∧(┐A →B) ∧(A∨┐A) ⇒ B

(9) 破坏性二难: (A→B)∧(C→D) ∧(┐B ∨┐D) ⇒(┐A ∨┐C)