第 1章 命题逻辑第 1章 命题逻辑
1.1 命题及联结词
1.2 命题公式与翻译
1.3 真值表和等价公式
1.4 重言式
1.5 范式
1.6 全功能联结词集
1.7 对偶式与蕴含式
1.8 命题逻辑的推理理论 返回总目录第 1章 命题逻辑第 1章 命题逻辑
1.1命题及联结词
1.1.1 命题的基本概念在数理逻辑中把 能判断真假的陈述句称为命题 。 一般用小写英文字母或小写英文字母带下标表示 。
命题的概念包含了以下 3个要素：
⑴ 只有陈述句才有可能成为命题,而其它的语句,如：
感叹句,祈使句,疑问句等都不是命题 。
⑵ 一个语句虽是陈述句,但不能判断真假不是命题 。
⑶ 虽然要求命题能判断真假,但不要求现在就能确定真假,将来可以确定真假也可以 。
一个命题表达的判断结果称为命题的真值 。 命题的真值有,真,和,假,两种,分别用 True,T,1(真 )和 False、
F,0(假 )来表示 。 真值为真的命题称为真命题,真值为假的命题称为假命题 。 任何命题的真值是惟一的 。
第 1章 命题逻辑在命题逻辑中对命题不再细分，因而命题是数理逻辑中最基本的也是最小的研究单位。
【 例 1.1】 判断以下语句是否为命题 。 若是命题,确定其真值 。
⑴ 上海是个小村庄 。
⑵ 存在外星人 。
⑶ 禁止吸烟 ！
⑷ 北京是中国的首都 。
⑸ 4是素数或 6是素数 。
⑹ 今天你吃了吗？
⑺ 11+1=100
⑻ 我正在说谎 。
解,⑴ 命题 (F),⑵ 命题 (待定 ),⑶ 不是命题 (祈使句 )，
⑷ 命题 (T),⑸ 命题 (F),⑹ 不是命题 (疑问句 ),⑺ 命题 (由上下文确定 ),⑻ 不是命题 (悖论 )。
第 1章 命题逻辑表示命题的小写英文字母或带下标的小写英文字母常称为命题标识符 。 如果命题标识符表示一个具体,确定的命题,
称为命题常元 。 如果命题标识符表示任意一个命题,称为命题变元 。 命题变元无确定的真值 。
命题是能判断真假的陈述句 。 而命题变元代表任意的命题,其真值是不确定的 。 因而不是命题 。
如果一个命题不能再分解成更简单的命题,则称该命题为原子命题 。 如果一个命题不是原子命题,称 该命题 为复合命题 。
如果命题变元表示原子命题时,该命题变元称为原子变元 。
在自然语言中,可以通过,如果?,那么?,,,不但?,而且?,这样的连词将简单的陈述句联结成复合语句,
同样在命题逻辑当中,也可以通过命题联结词将原子变元联结起来表示复合命题 。
第 1章 命题逻辑
1.1.2 命题联结词常用的逻辑联结词有五种：否定联结词,合取联结词,析取联结词,条件联结词和双条件联结词 。
1,否定联结词定义 1.1.1 设 p为命题,则 p的否定是一个复合命题,记作,?p,读作,非 p” 或
,p的否定,。 定义为：若 P为 T,则?p为 F；
若 p为 F,则?p的真值为 T。
表 1.1
p?p
0 1
1 0
p和?p的关系如表 1.1所示,表 1.1叫做否定联结词,?”
的真值表 (下同 )。
联结词,?” 也可以看作逻辑运算,它是一元运算 。
【 例 1.2】 否定下列命题 。
p：王强是一名大学生 。
p：王强不是一名大学生 。
第 1章 命题逻辑
2,合取联结词定义 1.1.2设 p和 q均为命题,则 p
和 q的合取是一个复合命题,记作
p∧ q,读作,p与 q” 或,p合取 q” 。
定义为：当且仅当 p和 q均为 T时,
p∧ q的才为 T。
联结词,∧,的真值表 如 表 1.2
所示 。
联结词,∧,也可以看成逻辑运算，它是二元逻辑运算。
表 1.2
p q p∧ q
0 0 0
0 1 0
1 0 0
1 1 1
【 例 1.3】 设 p,2008年将在北京举办奥运会 。
q：中国是世界四大文明古国之一 。
则 p∧ q,2008年将在北京举办奥运会并且中国是世界四大文明古国之一 。
第 1章 命题逻辑
3,析取联结词定义 1.1.3 设 p和 q均为命题,
则 p和 q的析取是一个复合命题,
记作 p∨ q,读作,p或 q” 或者,p
析取 q” 。 定义为：当且仅当 p和 q
均为 F时,p∨ q才为 F。
联结词,∨,的真值表如表
1.3所示 。
联结词,∨,也可以看成逻辑运算,它是二元逻辑运算 。
表 1.3
p q p∨ q
0 0 0
0 1 1
1 0 1
1 1 1
,∨,与汉语中的,或,相似，但又不相同。汉语中的或有可兼或与不可兼或 (排斥或 )的区分。
【 例 1.4】 下列两个命题中的,或,,哪个是可兼或？ 哪个是不可兼或？
⑴在电视上看这场杂技或在剧场里看这场杂技。 (不可兼 )
⑵ 灯泡有故障或开关有故障。 (可兼,,∨,是 可兼 或 )
第 1章 命题逻辑
4,条件联结词定义 1.1.4 设 p和 q均为命题,其条件命题是个复合命题，记为,p→ q。读作,如果 p，那么 q” 或,若 p，则 q” 。
定义为：当且仅当 p为 T,q为 F时，
p→ q才为 F。 p称为条件命题 p→ q的前件，
q称为条件命题 p→ q的后件。
联结词,→,真值表如表 1.4所示 。
联结词,→,也可以看成逻辑运算，
它是二元逻辑运算。
表 1.4
p q p→ q
0 0 1
0 1 1
1 0 0
1 1 1
【 例 1.5】 p：小王努力学习 。 q：小王学习成绩优秀 。
p→ q：如果小王努力学习,那么他的学习成绩就优秀 。
联结词,→” 与汉语中的,如果?,那么?,或,若?,
则?,相似,但又是不相同的 。
第 1章 命题逻辑
5,双条件联结词定义 1.1.5设 p和 q均为命题,其复合命题 p?q称为双条件命题,读作：,p
双条件 q” 或者,p当且仅当 q” 。 定义为：当且仅当 p和 q的真值相同时,p?q
为 T。
联结词,?” 的真值表如表 1.5所示 。
联结词,?” 也可以理解成逻辑运算,
它是二元逻辑运算 。
双条件联结词表示的是一个充分必要关系,与前面所述相同,也可以不必表 1.5
p q p?q
0 0 1
0 1 0
1 0 0
1 1 1
顾及其前因后果,而只根据联结词的定义来确定其真值 。
【 例 1.6】 设 p：张华是三好学生 。
q：张华德,智,体全优秀 。
p?q：张华是三好学生当且仅当德,智,体全优秀 。
返回章目录第 1章 命题逻辑
1.2 命题公式与翻译把命题常量,命题变量按照一定的逻辑顺序用命题联结词连接起来就构成了命题演算的合式公式,也叫命题公式 。
当使用联结词集,∧,∨,→,时,合式公式定义如下：
定义 1.2.1按下列规则构成的符号串称为命题演算的合式公式,也称为命题公式,简称公式 。
⑴ 单个命题变元和常元是合式公式 。
⑵ 如果 A是合式公式,那么?A是合式公式 。
⑶ 如果 A和 B是合式公式,那么 (A∧ B),(A∨ B),(A→ B)
和 (A?B)是合式公式 。
⑷ 当且仅当有限次地应用了 ⑴,⑵,⑶ 所得到的符号串是合式公式 。
命题公式一般的用大写的英文字母 A,B,C,? 表示 。
依照这个定义,下列符号串是合式公式：
第 1章 命题逻辑
(p∨ q),?(p∨ q),(p→ (p∨?q))，
(((p→ q)∧ (q→ r))?(s?t))
下列符号串不是合式公式：
(p→ q)→ (∧ q),(p→ q,(p∧ q)→ q)
定义 1.2.1给出合式公式定义的方法称为归纳定义,它包括三部分：基础,归纳和界限 。 定义 1.2.1中的 ⑴ 是基础,⑵
和 ⑶ 是归纳,⑷ 是界限 。 下文中还将多次出现这种形式的定义 。
为方便起见,对命题公式约定如下：
⑴ 最外层括号可以省略 。
⑵ 规定联结词的优先级由高到低依次为?,∧,∨,→,
。 按此优先级别,如果去掉括号,不改变原公式运算次序,
也可以省掉这些括号 。
一般地说,命题公式中包含命题变元,因而无法计算其真值,所以不是命题 。
命题公式中的命题变元,也叫命题公式的分量 。
第 1章 命题逻辑有了命题公式的概念,就可以用命题公式表示复合命题,常将这个过程称为命题的符号化 。 命题的符号化可按如下步骤进行：
⑴ 找出复合命题中的原子命题 。
⑵ 用小写的英文字母或带下标的小写的英文字母表示这些原子命题 。
⑶ 使用命题联结词将这些小写的英文字母或带下标的小写的英文字母连接起来 。
【 例 1.7】 将下列命题符号化：
他或者骑自行车去学校,或者乘公共汽车去学校 。
解,令 p：他骑自行车去学校。
q：他乘公共汽车去学校 。
此命题中的或是不可兼或,所以不能符号化为,p∨ q。
而要 符号化为,?(p?q)或 (?p∧ q)∨( p∧?q)。 稍后会看到这个表示是正确的 。
返回章目录第 1章 命题逻辑
1.3真值表和等价公式
1.3.1命题公式的真值表定义 1.3.1 设 pl,p2,?,pn是出现在公式 A中的全部命题变元，给 pl,p2,?,pn各指定一个真值，称为对公式 A的一个赋值或解释。若指定的赋值使 A的真值为 T，则称这个赋值为 A的成真赋值，若使 A的真值为 F，则称这个赋值为 A的成假赋值。
例如，给公式 (p∨ q→r)赋值 011是指 p=0,q=1,r=1，它是该公式的成真赋值；赋值 110是指 p=1,q=1,r=0，它是该公式的成假赋值。
定义 1.3.2 在命题公式 A中,对 A的每一个赋值,就确定了
A的一个真值,把它们汇列成表,称该表为命题公式 A的真值表 。
第 1章 命题逻辑
【 例 1.8】 构造命题公式?p∨ q的真值表,并求成真赋值和成假赋值 。
解,命题公式?p∨ q的真值表如表 1.6所示。 00,01，
11是成真赋值,10是成假赋值。
表 1.6
p q?p?p∨ q
0 0 1 1
0 1 1 1
1 0 0 0
1 1 0 1
第 1章 命题逻辑表 1.7
p q p∧ q?p?q?p∧?q (p∧ q)∨ (?p∧?q)
0 0 0 1 1 1 1
0 1 0 1 0 0 0
1 0 0 0 1 0 0
1 1 1 0 0 0 1
【 例 1.9】 构造命题公式 (p∧ q)∨ (?p∧?q)的真值表，并求成真赋值和成假赋值。
解,命题公式 (p∧ q)∨ (?p∧?q)的真值表如表 1.7所示。
00,11是成真赋值,01,10是成假赋值。
第 1章 命题逻辑
1.3.2命题公式的等价定义 1.3.3 设 A和 B是两个命题公式,对 A和 B的任一赋值,
A和 B的真值都相同,则称 A和 B是等价的或逻辑相等的,记为 A?B
可以证明,命题公式等价有下面的三条性质：
⑴ 自反性,即对任意命题公式 A,A?A
⑵ 对称性,即对任意命题公式 A和 B,若 A?B,则 B?A
⑶ 传递性,即对任意命题公式 A,B和 C,若 A?B，
B?C,则 A?C
根据定义 1.3.3,可以用真值表证明命题公式是等价的，
请看下面的例题。
【 例 1.12】 根据等价的定义，用真值表证明
p→(q→p)p→(p→?q)
证明,构造 p→(q→p)和?p→(p→?q)的真值表，如表
1.10所示。 p→(q→p)和?p→(p→?q)所在的列完全相同，它们具有相同的真值表。所以 p→(q→p)p→(p→?q)
第 1章 命题逻辑表 1.10
p q?p?q q→ p p→ (q→ p) p→?q?p→ (p→?q)
0 0 1 1 1 1 1 1
0 1 1 0 0 1 1 1
1 0 0 1 1 1 1 1
1 1 0 0 1 1 0 1
证明等价 的 另外一种方法叫做等价演算法,其基本思想是：先用真值表证明一组基本等价式，以它们为基础进行公式之间的演算。 基本等价式常叫命题定律。下面是常用的命题定律。
1.双重否定律 AA
2.交换律 A∨ B?B∨ A,A∧ B?B∧ A
3.结合律 (A∨ B)∨ C?A∨ (B∨ C)
(A∧ B)∧ C?A∧ (B∧ C)
第 1章 命题逻辑
4.分配律 A∧ (B∨ C)?(A∧ B)∨ (A∧ C)
A∨ (B∧ C)?(A∨ B)∧ (A∨ C)
5.德摩根律?(A∨ B)A∧?B
(A∧ B)A∨?B
6.幂等律 A∧ A?A,A∨ A?A
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→ BA∨ B
13.双条件等价式 A?B?(A→ B)∧ (B→ A)
14.假言易位式 A→ BB→?A
15.双条件否定等价式 A?BAB
第 1章 命题逻辑以上共 23个等价式，原则上说，这些公式都可以用真值表证明。下面仅验证德摩根律。
【 例 1.13】 用真值表证明德摩根律?(A∨ B)A∧?B
解,表 1.11是?(A∨ B)和?A∧?B的真值表，从表中可以看出德摩根律成立 。
表 1.11
A B?A?B?A∧?B A∨ B?(A∨ B)
0 0 1 1 1 0 1
0 1 1 0 0 1 0
1 0 0 1 0 1 0
1 1 0 0 0 1 0
第 1章 命题逻辑定义 1.3.4如果 X是合式公式 A的一部分且 X本身也是合式公式,则称 X为公式 A的子公式 。
例如,A?q→ (p∨ (p∧ q)),X?p∧ q，则 X是 A的子公式。
定理 1.3.1设 X是合式公式 A的子公式,若 X?Y,如果将 A
中的 X用 Y来置换,得到的公式记为 B,则 B与 A等价,即 A?B
证明,对 A,B的任一赋值,X与 Y的真值相同,而 A,B
的其它部分完全相同,公式 B与公式 A的真值必相同 。 A?B
满足此定理的置换叫做等价置换 。
【 例 1.17】 用等价演算法证明 p?q?(p∧ q)∨ (?p∧?q)
证明,p?q?(p→ q)∧ (q→ p) (双条件等价式 )
(?p∨ q)∧ (?q∨ p) (条件等价式 )
(?p∧?q)∨ (?p∧ p)∨ (q∧?q)∨ (q∧ p) (分配律 )
(?p∧?q)∨ 0∨ 0∨ (q∧ p) (矛盾律 )
(?p∧?q)∨ (q∧ p) (同一律 )
(p∧ q)∨ (?p∧?q) (交换律 )
p?q?(p∧ q)∨ (?p∧?q) (等价的传递性 )
返回章目录第 1章 命题逻辑
1.4重言式定义 1.4.1 设 A是任一命题公式 。
⑴ 若对 A的任意赋值,其真值永为真,则称命题公式 A
为重言式或永真式 。
⑵ 若对 A的任意赋值,其真值永为假,则称命题公式 A
为矛盾式或永假式 。
⑶ 若 A不是矛盾式,则称命题公式 A为可满足的 。
由定义 1.4.1可以看出，任何重言式都是可满足的。
显然,重言式的真值表的最后一列全为 1,矛盾式的真值表的最后一列全为 0,可满足的公式真值表的最后一列至少有一个 1。 根据这个结论借助于真值表可以判断一个公式是否为重言式,矛盾式或可满足的 。 当然也可以用等价演算法判断公式的类型 。
【 例 1.18】 用等价演算法判断下列公式的类型。
⑴ q∨?((?p∨ q)∧ p)
第 1章 命题逻辑
⑵ (p∨?p)→((q∨?q)∧ r)
⑶ (p→q)∧?p
解,⑴ q∨?((?p∨ q)∧ p)
q∨?((?p∧ p)∨ (q∧ p)) (分配律 )
q∨?(0∨ (q∧ p)) (矛盾律 )
q∨?(q∧ p) (同一律 )
q∨ (?q∨?p) (德摩根律 )
(q∨?q)∨?p (结合律 )
1∨?p (排中律 )
1 (零律 )
由此可知,⑴ 为重言式 。
⑵ (p∨?p)→((q∧?q)∧ r)
1→((q∧?q)∧ r) (排中律 )
1→(0∧ r) (矛盾律 )
1→0 (零律 )
0 (条件联结词的定义 )
第 1章 命题逻辑由此可知,⑵ 为矛盾式 。
⑶ (p→ q)∧?p
(?p∨ q)∧?p (条件等价式 )
p (吸收律 )
由此可知，⑶是可满足的。
定理 1.4.1 任何两个重言式的合取或析取都是重言式。
证明,设 A,B是重言式,对 A和 B的任何赋值,总有 A为
1,B为 1,所以 A∧ B?1,A∨ B?1,故 A∧ B和 A∨ B都是重言式 。
推论 任何两个矛盾式的合取或析取是矛盾式。
定理 1.4.2 一个重言式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式 。
推论,一个矛盾式,对同一分量出现的每一处都用同一合式公式置换,其结果仍是矛盾式 。
第 1章 命题逻辑
【 例 1.19】 利用定理 1.4.2证明 ((p∨ q)∧ r)∨?((p∨ q)∧ r)
为重言式。
证明,由排中律知 p∨?p为重言式，以 ((p∨ q)∧ r)去置换其中的 p，得公式 ((p∨ q)∧ r)∨?((p∨ q)∧ r)，根据定理 1.4.2，
这是重言式。
定理 1.4.3 设 A,B为两个命题公式,A?B当且仅当 A?B
是重言式 。
证明,设 A?B,下证 A?B是重言式 。
给 A,B的任何赋值,因为 A?B,所以 A,B具有相同的真值,由双条件联结词的定义知 A?B为真,所以 A?B为重言式 。
设 A?B为重言式,下证 A?B
给 A,B的任何赋值,因为 A?B为重言式,故 A,B的真值相同,由命题公式等价的定义知 A?B
返回章目录第 1章 命题逻辑
1.5范式
1.5.1析取范式与合取范式定义 1.5.1由一些命题变元或其否定构成的析取式称为基本和,也叫简单析取式 。 约定单个变元或其否定是基本和 。
例如,?p∨ q,p∨?q,p∨ q,?q,?p,q都是基本和。
定义 1.5.2由一些命题变元或其否定构成的合取式称为基本积，也叫简单合取式。约定单个变元或其否定是基本积。
例如,?p∧ q,p∧?q,p∧ q,?p,?q,p都是基本积。
定义 1.5.3由 基本和的合取构成的公式叫做合取范式。 约定单个 基本和 是 合取范式 。
定义 1.5.4由基本积的析取构成的公式叫做析取范式。 约定单个 基本积 是 析取范式 。
任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步骤如下：
⑴ 消去联结词,→” 和,?”
第 1章 命题逻辑
⑵ 利用双重否定律消去否定联结词,?” 或利用德摩根律将否定联结词,?” 移到各命题变元前 (?内移 )。
⑶ 利用分配律,结合律将公式归约为合取范式和析取范式 。
【 例 1.21】 求命题公式 (p∨ q)?p 的合取范式和析取范式 。
解,⑴ 求合取范式
(p∨ q)?p
((p∨ q)→p)∧ (p→(p∨ q)) (消去?)
(?(p∨ q)∨ p)∧ (?p∨ (p∨ q)) (消去 →)
((?p∧?q)∨ p)∧ (?p∨ (p∨ q)) (?内移 )
(?p∨ p)∧ (?q∨ p)∧ (?p∨ p∨ q) (分配律,合取范式 )
1∧ (?q∨ p)∧ (1∨ q) (排中律 )
1∧ (?q∨ p)∧ 1 (零律,合取范式 )
(?q∨ p) (同一律,合取范式 )
由此例可以看出,公式的合取范式并不惟一 。
第 1章 命题逻辑
⑵ 求析取范式
(p∨ q)?p
((p∨ q)∧ p)∨ (?(p∨ q)∧?p) (消去?)
((p∨ q)∧ p)∨ ((?p∧?q)∧?p) (?内移 )
p∨ (?p∧?q∧?p) (吸收律,析取范式 )
p∨ (?p∧?p∧?q) (交换律 )
p∨ (?p∧?q) (幂等律,析取范式 )
由此例可以看出,命题公式的析取范式也不惟一 。
1.5.2主析取范式由于析取范式和合取范式不惟一，所以使用起来很不方便。为此，引入主析取范式和主合取范式的概念。当命题变元的顺序约定以后，主析取范式和主合取范式是惟一的。
析取范式和合取范式的基本成分是基本积和基本和,而主析取范式和主合取范式的基本成分是极小项和极大项,它们分别是特殊的基本积和基本和 。
第 1章 命题逻辑定义 1.5.5在基本积中，每个变元及其否定不同时存在，
但两者之一必须出现且仅出现一次，这样的基本积叫做布尔合取也叫小项或极小项。
p,q的极小项为,p∧ q,p∧?q,?p∧ q,?p∧?q
两个命题变元的极小项共 4(=22)个,三个命题变元的极小项共 8(=23)个,? 。一般地说,n个命题变元共有 2n个极小项。
表 1.12是两个变元 p和 q的极小项的真值表 。 极小项有下列的性质：
⑴ 每个极小项只有一个成真赋值,且各极小项的成真赋值互不相同 。 极小项和它的成真赋值构成了一一对应的关系 。 可用成真赋值为极小项进行编码,并把编码作为 m的下标来表示该极小项,叫做该极小项的名称 。
两个命题变元的极小项,成真赋值 和名称如表 1.13所示 。
三个命题变元的极小项,成真赋值和名称如表 1.14所示 。
从表 1.13和表 1.14中可以看出，极小项与其成真赋值的对应关系为：变元对应 1，而变元的否定对应 0。
第 1章 命题逻辑表 1.12
p q p∧ q p∧?q?p∧ q?p∧?q
0 0 0 0 0 1
0 1 0 0 1 0
1 0 0 1 0 0
1 1 1 0 0 0
表 1.13
极小项 成真赋值 名称
p∧?q 00 m0
p∧ q 01 m1
p∧?q 10 m2
p∧ q 11 m3
第 1章 命题逻辑表 1.14
极小项 成真赋值 名称
p∧?q∧?r 000 m0
p∧?q∧ r 001 m1
p∧ q∧?r 010 m2
p∧ q∧ r 011 m3
p∧?q∧?r 100 m4
p∧?q∧ r 101 m5
p∧ q∧?r 110 m6
p∧ q∧ r 111 m7
第 1章 命题逻辑
⑵ 任意两个不同的极小项的合取式为永假式 。
例如：
m001∧ m100?(?p∧?q∧ r)∧ (p∧?q∧?r)
p∧?q∧ r∧ p∧?q∧?r?0
⑶ 全体极小项的析取式为永真式 。 记为：
12
0
n
i
im
m0∨ m1∨? ∨?1
定义 1.5.6 对于给定的命题公式,如果有一个它的等价公式,仅由极小项的析取组成,称该公式为原公式的主析取范式 。
任何命题公式都存在着与之等价的主析取范式。一个命题公式的主析取范式可以由以下两种方法求得：
⑴等价演算法：即用基本等价公式推出。
12?nm
第 1章 命题逻辑用等价演算法求主析取范式的步骤如下：
① 化归为析取范式。
② 除去析取范式中所有永假的基本积 。
③ 在基本积中,将重复出现的合取项和相同变元合并 。
④ 在基本积中补入没有出现的命题变元，即添加
∧ (p∨?p)，再用分配律展开，最后合并相同的极小项。
【 例 1.22】 用等价演算法求 (p∧ q)∨ (?p∧ r)∨ (q∧ r)的主析取范式。
解,(p∧ q)∨ (?p∧ r)∨ (q∧ r)
(p∧ q∧ (r∨?r))∨ (?p∧ r∧ (q∨?q))∨ (q∧ r∧ (p∨?p))
(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)
m111∨ m110∨ m011∨ m001
m7∨ m6∨ m3∨ m1?∑1,3,6,7
第 1章 命题逻辑
⑵ 真值表法：即用真值表求主析取范式 。
用真值表求主析取范式的步骤如下：
① 构造命题公式的真值表 。
② 找出 公式的成真赋值对应的极小项 。
③ 这些极小项的析取就是此公式的主析取范式。
【 例 1.24】 用真值表法，求 (p→q)→r的主析取范式。
解,表 1.15是 (p→q)→r的真值表,公式的成真赋值对应的极小项为：
p∧?q∧ r (成真赋值为 001)
p∧ q∧ r (成真赋值为 011)
p∧?q∧?r (成真赋值为 100)
p∧?q∧ r (成真赋值为 101)
p∧ q∧ r (成真赋值为 111)
(p→q)→r 的主析取范式为：
第 1章 命题逻辑
(p∧ q∧ r)∨ (p∧?q∧ r)∨ (p∧?q∧?r) ∨ (?p∧ q∧ r)
∨ (?p∧?q∧ r)
m111∨ m101∨ m100∨ m011∨ m001?m7∨ m5∨ m4∨ m3∨ m1
∑1,3,4,5,7
表 1.15
p q r p→ q (p→ q)→ r
0 0 0 1 0
0 0 1 1 1
0 1 0 1 0
0 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 1 0 1 0
1 1 1 1 1
第 1章 命题逻辑矛盾式无成真赋值，因而主析取范式不含任何极小项，
将矛盾式的主析取范式记为 0。而重言式无成假赋值，因而主析取范式含 2n (n为公式中命题变元的个数 )个极小项。至于可满足式，它的主析取范式中极小项的个数一定小于等于 2n。
1.5.3主合取范式定义 1.5.7在基本和中,每个变元及其否定不同时存在,
但两者之一必须出现且仅出现一次,这样的基本和叫作布尔析取,也叫大项或极大项 。
两个变元 p,q构成的极大项为：
p∨ q,p∨?q,?p∨ q,?p∨?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
两个命题变元的极大项共 4(=22)个,三个命题变元的极大项共 8(=23)个,? 。 一般地说,n个变元共有 2n个极大项 。
第 1章 命题逻辑极大项有下列三个性质：
⑴ 每个极大项只有一个成假赋值,极大项不同,成假赋值也不同 。 极大项和它的成假赋值构成了一一对应的关系 。
故可用成假赋值为该极大项进行编码,并把编码作为 M的下标来表示该极大项,叫做极大项的名称 。
例如,两个变元 p,q的极大项?p∨?q,它的成假赋值是
11,表示为 M11,把 11理解为 2进制数,它的 10进制表示为 3，
所以 M11又表示为 M3。 表 1.16
极大项 成假赋值 名称
p∨ q 00 M0
p∨?q 01 M1
p∨ q 10 M2
p∨?q 11 M3
两个命题变元的极大项，成假赋值及名称见表
1.16，三个命题变元的极大项，成假赋值及名称见表 1.17。
第 1章 命题逻辑从表 1.16和表
1.17中可以看出，极大项与成假赋值的对应关系为：变元对应
0，而变元的否定对应 1。
⑵ 任意两个不同的极大项的析取式为永真式 。
⑶ 全体极大项的合取式为永假式 。 记为：
表 1.17
极大项 成假赋值 名称
p∨ q∨ r 000 M0
p∨ q∨?r 001 M1
p∨?q∨ r 010 M2
p∨?q∨?r 011 M3
p∨ q∨ r 100 M4
p∨ q∨?r 101 M5
p∨?q∨ r 110 M6
p∨?q∨?r 111 M7
12
0
n
i
iM
M0∧ M1∧? ∧
12?nM
0
第 1章 命题逻辑定义 1.5.8 对于给定的命题公式,如果有一个它的等价公式,仅由极大项的合取组成,则该等价式称为原公式的主合取范式 。
任何命题公式都存在着与之等价的主合取范式 。 主合取范式也可以由以下两种方法求得 。
⑴ 等价演算法：即用基本等价公式推出 。
其演算步骤如下：
① 化归为合取范式 。
② 除去所有永真的基本和 。
③ 在基本和中合并重复出现的析取项和相同的变元 。
④ 在基本和中补入没有出现的命题变元 。 即增加
∨ (p∧?p),然后,应用分配律展开公式,最后合并相同的极大项 。
【 例 1.25】 用等价演算法求 (p→ q)→ r的主合取范式 。
解,(p→q)→r
第 1章 命题逻辑
(?p∨ q)∨ r?(p∧?q)∨ r?(p∨ r)∧ (?q∨ r)
(p∨ r∨ (q∧?q))∧ (?q∨ r∨ (p∧?p))
(p∨ r∨ q)∧ (p∨ r∨?q)∧ (p∨?q∨ r)∧ (?p∨?q∨ r)
(p∨ q∨ r)∧ (p∨?q∨ r)∧ (?p∨?q∨ r)
M000∧ M010∧ M110?M0∧ M2∧ M6?∏0,2,6
⑵ 真值表法：用真值表求主合取范式 。
用真值表求主 合 取范式的步骤如下：
① 构造命题公式的真值表 。
② 找出公式的成假赋值对应的极大项 。
③ 这些极大项的析取就是此公式的主合取范式 。
【 例 1.26】 用真值表法求 (p→ q)→ r的主合取范式 。
解,(p→ q)→ r的真值表是表 1.15。 公式的成假赋值对应的大项为：
p∨ q∨ r (成假赋值为 000)
p∨?q∨ r (成假赋值为 010)
第 1章 命题逻辑
p∨?q∨ r (成假赋值为 110)
主合取范式为,(p∨ q∨ r)∧ (p∨?q∨ r)∧ (?p∨?q∨ r)
M000∧ M010∧ M110?M0∧ M2∧ M6?∏ 0,2,6
矛盾式无成真赋值,因而矛盾式的主合取范式含 2n (n
为公式中命题变元的个数 )个极大项 。 而重言式无成假赋值,
因而主合取范式不含任何极大项 。 将重言式的主合取范式记为 1。 至于可满足式,它的主合取范式中极大项的个数一定小于 2n。
在例 1.23和例 1.24中求出 (p→ q)→ r的主析取范式为：
m7∨ m5∨ m4∨ m3∨ m1?∑ 1,3,4,5,7
在例 1.25和例 1.26中求出该公式的主合取范式为：
M0∧ M2∧ M6?∏ 0,2,6
比较这两个结果,得出以下的结论：同一公式的主析取范式中 m的下标和主合取范式中 M的下标是互补的 。 因此,
知道了主析 (合 )取范式就可以写出主合 (析 )取范式 。
返回章目录第 1章 命题逻辑
1.6全功能联结词集定义 1.6.1 设 p和 q是两个命题,复合命题 p q称作 p和 q的不可兼析取,也叫异或 。 定义为,p q为 T当且仅当 p和 q的真值不相同时 。 联结词,,称为异或联结词 。
表 1.18
p q
0 0 0
0 1 1
1 0 1
1 1 0
p? q
联结词,,的真值表如表 1.18所示 。
,” 也可以看成逻辑运算,它是二元逻辑运算 。 它在程序设中有广泛的引用 。
不可兼析取有下列的性质,
⑴ p q?q p (交换律 )?
⑵ (p q) r?p (q r) (结合律 )
第 1章 命题逻辑
⑶ p∧ (q r)?(p∧ q) (p∧ r) (合取对异或的分配律 )
⑷ p q?(p∧?q)∨ (?p∧ q)
⑸ p q(p?q)
⑹ p p?0,0 p?p,1 pp
定理 1.6.1 设 A,B,C为命题公式,如果 A B?C,则 A
C?B,B C?A,A B C为一矛盾式 。
定义 1.6.2 设 p和 q是两个命题,复合命题 p↑q称作 p和 q的与非 。 定义为：当且仅当 p和 q真值都是真时,p↑q才为假 。
联结词,↑” 称为与非联结词 。
联结词,↑” 的真值表如表 1.19所示 。
,↑” 也可以看成逻辑运算,它是二元逻辑运算 。
由定义可以看出下式成立：
p↑q( p∧ q)
联结词,↑” 还有以下几个性质：
第 1章 命题逻辑表 1.19
p q p↑ q
0 0 1
0 1 1
1 0 1
1 1 0
⑴ p↑ p(p∧ p)p
⑵ (p↑ q)↑ (p↑ q)(p↑ q)
(p∧ q)?p∧ q
⑶ (p↑ p)↑ (q↑ q)?(?p)↑ (?q)
(?p∧?q)?p∨ q
定义 1.6.3 设 p和 q是两个命题，
复合命题 p↓ q称作 p和 q的或非。
定义为：当且仅当 p,q的真值都为假时,p↓ q的真值为真。联结词,↓” 称为或非联结词。
联结词,↓” 的真值表如表
1.20所示 。
,↓” 也可以看成逻辑运算,
它是二元逻辑运算 。
表 1.20
p q p↓ q
0 0 1
0 1 0
1 0 0
1 1 0
第 1章 命题逻辑由此定义可得到下面的公式：
p↓ q(p∨ q)
联结词 ↓ 还有下面的几个性质：
⑴ p↓ p(p∨ p)p
⑵ (p↓ q)↓ (p↓ q)(p↓ q)(p∨ q)?p∨ q
⑶ (p↓ p)↓ (q↓ q)p↓?q(?p∨?q)?p∧ q
至此已经学了 8个联结词,?,∧,∨,→,?，,↑,
↓ 。 类似于定义 1.2.1的方法,可以定义包含上述 8个联结词的命题公式 。
定义 1.6.4 设 S是一个联结词集合，如果任何 n(n≥ 1)个变元组成的公式，都可以由 S中的联结词来表示，则称 S是全功能联结词集。
根据命题公式的定义,∧,∨,→,?，,↑,↓?是全功能联结词集 。
利用下列 3个等价式可将任何命题公式中的命题联结词
,”,,↑” 和,↓” 去掉 。
第 1章 命题逻辑
p q(p?q)
p↑ q(p∧ q)
p↓q(p∨ q)
所以,∧,∨,→,是全功能联结词集 。
利用下列 2个等价式可将任何命题公式中的 命题 联结词
,→,和,?” 去掉 。
p→qp∨ q
p?q?(p→q)∧ (q→p)?(?p∨ q)∧ (?q∨ p)
所以,∧,∨?是全功能联结词集 。
用德摩根律可证明,∧?和,∨?是全功能联结词集 。
可以证明?∧,∨,→,和?∧,∨,→,的任何子集都不是全功能联结词集 。
定义 1.6.5设 S是全功能联结词集,如果去掉其中的任何联结词后,就不是全功能联结词集,则称 S是最小全功能联结词集 。
第 1章 命题逻辑可以证明,∧?,,∨?,?↑?,?↓?是最小全功能联结词集 。
现在讨论,n个命题变元可以构成多少个不等价的命题公式 。
两个命题变元可以构成多少个不等价的命题公式？
由等价的概念知道，等价的命题公式有相同的真值表，
所以上述问题就转化为两个命题变元构成的命题公式有多少个不同的真值表？ 表 1.21
p q 公式
0 0 1或 0
0 1 1或 0
1 0 1或 0
1 1 1或 0
两个命题变元构成的命题公式的真值表的格式如表 1.21所示 。 真值表中每行公式的真值都有 1,0两种可能,所以 命题 公式的真值有
2× 2× 2× 2=24= =16种可能,既有 个不同的真值表 。 故有 种不等价的公式 。
返回章目录
222
222 222
第 1章 命题逻辑三个变元可构成 28= 个不等价的命题公式,n个变元可构成 个不等价的命题公式 。
1.7对偶式与蕰含式
1.7.1对偶式从 1.3节的命题定律中可以看出,很多常用等价式是成对出现的,只要将其中的,∧,和,∨,分别换成,∨,和
,∧,,就可以由一个得到另一个 。 例如,将命题定律
(A∨ B)∨ C?A∨ (B∨ C)中的,∨,换成,∧,就得到了命题定律 (A∧ B)∧ C?A∧ (B∧ C)。 这些成对出现的等价式反映了等价的对偶性 。 本节介绍对偶式和对偶原理 。
定义 1.7.1在仅含联结词?,∧,∨ 的命题公式 A中,将联结词 ∨,∧,F,T分别换成 ∧,∨,T,F所得的公式称为公式 A的对偶式,记为 A*。
设 A*是 A的对偶式,将 A*中的 ∨,∧,F,T分别换成 ∧,
∨,T,F,就会得到 A。 即 A 是 A*的对偶式,(A*)*?A。 所以说 A*和 A互为对偶式 。
322
n22
第 1章 命题逻辑
【 例 1.27】 求 p↑ q和 p↓ q的对偶式 。
解,p↑ q(p∧ q)
(p∧ q)的对偶式是?(p∨ q)?p↓ q
故 p↑ q的对偶式是 p↓ q；同样的方法可以证明 p↓ q的对偶式是 p↑ q。
根据例 1.27,对偶式概念可以推广为：在仅含有联结词
,∧,∨,↑,↓ 的命题公式中,将联结词 ∨,∧,↑,
↓,F,T分别换成 ∧,∨,↓,↑,T,F,就得到了它的对偶式 。
关于对偶式有以下两个结论 。
定理 1.7.1 设 A*是 A的对偶式,p1,p2,…,pn是出现在 A
和 A*中的原子变元,则
A(p1,p2,?,pn)?A*(?p1,?p2,?,?pn)
A(?p1,?p2,?,?pn)A*(p1,p2,?,pn)
第 1章 命题逻辑
【 例 1.28】 设命题公式 A(p,q,r)?(p∨ q)∧ r,试用此公式验证定理 1.7.1的有效性 。
证明,⑴ 验证?A(p,q,r)?A*(?p,?q,?r)
A(p,q,r)?(p∨ q)∧ r
A(p,q,r)((p∨ q)∧ r)?(?p∧?q)∨?r
A*(p,q,r)?(p∧ q)∨ r
A*(?p,?q,?r)?(?p∧?q)∨?r
所以,?A(p,q,r)?A*(?p,?q,?r)
⑵ 验证 A(?p,?q,?r)A*(p,q,r)
A(?p,?q,?r)?(?p∨?q)∧?r
((p∧ q)∨ r)A*(p,q,r)
第 1章 命题逻辑定理 1.7.2 (对偶原理 )设 p1,p2,?,pn是出现在公式
A和 B中的所有原子变元,如果 A?B,则 A*?B*
证明,因为 A?B
所以 A(p1,p2,?,pn)?B(p1,p2,?,pn)是重言式根据定理 1.4.2,在上述重言式中用?pi置换 pi，
i＝ 1,?,n,所得的公式仍为重言式,即
A(?p1,?p2,?,?pn)?B(?p1,?p2,?,?pn)是重言式 。
所以 A(?p1,?p2,?,?pn)?B(?p1,?p2,?,?pn)
由定理 1.7.1?A*(p1,p2,?,pn)B*(p1,p2,?,pn)
即?A*B*
由双条件否定等价式知 A*?B*
定理 1.7.2叫做对偶原理 。 对偶原理是数理逻辑中最基本的规律之一 。
第 1章 命题逻辑
【 例 1.29】 证明重言式的对偶式是矛盾式,矛盾式的对偶式是重言式 。
证明,设 A是重言式,即 A?1,因为 1的对偶式是 0,由对偶原理知 A*?0。 所以 A*是矛盾式；设 A是矛盾式,即
A?0,而 0的对偶式是 1,所以 A*?1。 所以 A*是重言式 。
1.7.2蕴含式定义 1.7.2 设 A和 B是命题公式,若 A→ B是重言式,则称
A蕴含 B,记为 A?B。
根据定义可以用真值表或等价演算证明 A?B。
A?B定义为,A→ B为重言式 。 又由条件命题的定义知,
仅在 A?T,B?F时,A→ B为假,其余情况都为真 。 故要证明 A?B,只需排除 A?T,B?F的情况 。 于是就有了证明
A?B的第二种方法：
第 1章 命题逻辑
⑴ 对 A指定真值 T,若由此推出 B的真值不为 F,而为 T，
则 A→ B是重言式,即 A?B。
⑵ 对 B指定真值 F，若由此推出 A的真值不为 T，而为 F，
则 A→ B是重言式，即 A?B。
【 例 1.31】 推证?p∧ (p∨ q)?q
解,证法 1：
假定?p∧ (p∨ q)为 Tp为 T且 p∨ q为 T?p为 F且 p∨ q为
T?q为 T。
所以?p∧ (p∨ q)?q
证法 2：
假定 q为 F,则 p可以为 T或 F。
① 当 p为 T时,?p为 F,所以?p∧ (p∨ q)为 F。
② 当 p为 F时,(p∨ q)为 F,所以?p∧ (p∨ q)为 F。
故?p∧ (p∨ q)?q
第 1章 命题逻辑蕴含式是逻辑推理的重要工具。下面是一些重要的蕴含式。它们都可以用上述两种方法证明，其中 A,B,C,D是任意的命题公式。
1.附加律 A?A∨ B,B?A∨ B
2.化简律 A∧ B?A,A∧ B?B
3.假言推理 A∧ (A→ B)?B
4.拒取式?B∧ (A→ B)A
5.析取三段论?A∧ (A∨ B)?B,?B∧ (A∨ B)?A
6.假言三段论 (A→ B)∧ (B→ C)?(A→ C)
7.等价三段论 (A?B)∧ (B?C)?(A?C)
8.构造性二难 (A∨ C)∧ (A→ B)∧ (C→ D)?B∨ D
(A∨?A)∧ (A→ B)∧ (?A→ B)?B
9.破坏性二难 (?B∨?D)∧ (A→ B)∧ (C→ D)?(?A∨?C)
第 1章 命题逻辑等价式和蕴含式有下面的关系 。
定理 1.7.3 设 A,B为任意两个命题公式,则 A?B的充分必要条件是 A?B且 B?A
证明,设 A?B,下证 A?B且 B?A
因为 A?B,所以 A?B?T
由双条件等价式得 (A→ B)∧ (B→ A)?A?B?T
因而 A→ B与 B→ A都是重言式,故有 A?B且 B?A。
设 A?B且 B?A,下证 A?B。
因为 A?B且 B?A,所以 A→B与 B→A都是重言式,重言式的合取也是重言式,即
(A→B)∧ (B→A)?T
再由双条件等价式得 (A?B)?(A→B)∧ (B→A)?T
即 A?B为重言式,故有 A?B。
返回章目录第 1章 命题逻辑根据此定理,以前学过的所有等价式都可以作两个蕴含式来使用 。 例如吸收律 A∨ (A∧ B)?A可以作两个蕴含式
A∨ (A∧ B)?A和 A?A∨ (A∧ B) 来使用 。
定理 1.7.4 设 A,B,C为合式公式 。
⑴ A?A (即蕴含是自反的 )
⑵ 若 A?B且 A为重言式,则 B必为重言式 。
⑶ 若 A?B且 B?C,则 A?C (即蕴含是传递的 )
⑷ 若 A?B且 A?C,则 A?B∧ C
⑸ 若 A?B且 C?B,则 A∨ C?B
⑹ 若 A?B,C是任意公式,则 A∧ C?B∧ C
证明,仅证明 ⑸。
因为 A?B,C?B,所以 A→ B?T,C→ B?T
(A∨ C)→ B(A∨ C)∨ B?(?A∧?C)∨ B
(?A∨ B)∧ (?C∨ B)?(A→ B)∧ (C→ B)?T∧ T?T
由等价的传递性,(A∨ C)→ B?T,故 A∨ C?B
第 1章 命题逻辑
1.8命题逻辑的推论理论数理逻辑的主要任务是用逻辑的方法研究数学中的推理 。
所谓推理是指从前提出发,应用推理规则推出结论的思维过程 。 任何一个推理都由前提和结论两部分组成 。 前提就是推理所根据的已知命题,结论则是从前提出发通过推理而得到的新命题 。 要研究推理,首先应该明确什么样的推理是有效的或正确的 。
定义 1.8.1 设 A1,A2,?,An和 C是 n+1个命题公式,若
A1∧ A2∧? ∧ An?C,则称 C为 A1,A2,?,An 的有效结论 。
也称 C可由 A1,A2,?,An 逻辑的推出 。 A1,A2,?,An叫做 C的一组前提 。
A1∧ A2∧? ∧ An?C,亦可记为 A1,A2,?,An?C。
由定义 1.8.1可以看出，要证明 C是一组前提 A1,A2,?,
An的有效结论，只需证明 A1∧ A2∧? ∧ An→ C为重言式。证明一个公式为重言式，可以用真值表、等价演算、主析 (合 )
第 1章 命题逻辑取范式或已知的蕴含式等方法进行。用等价演算和主析 (合 )
取范式证明重言式的方法前面已经讨论过了，我们已经非常熟悉了。这里仅对真值表法作简单说明。
用真值表证明有效结论有以下两种方法：
⑴ 用全真值表证明要证明 C为前提 A1,A2,?,An 的有效结论,只需构造命题公式 A1∧ A2∧? ∧ An→C的真值表,证明它是重言式 。
⑵ 用部分真值表证明因为条件命题 A1∧ A2∧? ∧ An→C为假当且仅当它的前件 A1∧ A2∧? ∧ An为真,后件 C为假 。 只要能排除前件为真,
后件为假的情况,A1∧ A2∧? ∧ An→C就是重言式 。 从而 C为一组前提 A1,A2,?,An 的有效结论 。 于是就有了下面方法：
构造 A1,A2,?,An与 C的真值表,且作在一个表上 。
① 找出 A1,A2,?,An都为真的行,若 C也为真,则
A1∧ A2∧? ∧ An?C,即 C为前提 A1,A2,?,An 的有效结论 。
第 1章 命题逻辑
② 找出 C为假的行，若在每个这样的行中,A1,A2,?,
An的真值至少有一个为假，则 A1∧ A2∧? ∧ An?C，即 C为一组前提 A1,A2,?,An的有效结论。
【 例 1.32】 分析事实：,如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。,。试指出这个推理前提和结论，并证明结论是前提的有效结论。
解,令 p：我有时间 。
q：我去上街 。
r：我去书店买书 。
根据题意,前提为,p→q,q→r,?r
结论为,?p
以下证明?p是一组前提 p→q,q→r,?r的有效结论 。
即证明,(p→q)∧ (q→r)∧?rp
第 1章 命题逻辑下面用部分真值表进行证明 。
作公式 p→ q,
q→ r,?r,?p的真值表,如表 1.23所示 。
从表中可以看出：
p→ q,q→ r,?r
都为 1的行 (赋值 000
的行 ),?p也为 1。
p为 0的行 ( 赋值 100,101,110，
111的行 ) p→ q，
表 1.23
p q r p→ q q→ r?r?p
0 0 0 1 1 1 1
0 0 1 1 1 0 1
0 1 0 1 0 1 1
0 1 1 1 1 0 1
1 0 0 0 1 1 0
1 0 1 0 1 0 0
1 1 0 1 0 1 0
1 1 1 1 1 0 0
q→ r,?r至少有一个为 0,所以 (p→ q)∧ (q→ r)∧?rp
第 1章 命题逻辑我们已经有了判断推理是否正确的 4种方法,即真值表法,等值演算法,主析取范式法和蕴含演算法 。 当推理中包含的命题变元较多时,以上 4种方法的演算量太大,给推理带来了困难 。 为此引入命题逻辑的推理理论 。 命题逻辑的推理是一个描述推理过程的命题公式序列,其中的每个命题公式或者是已知前提,或者是由某些前提应用推理规则得到的结论 (中间结论或推理中的结论 )。 它有两种方法：直接推理和间接推理 。
⑴ 直接推理直接推理的基本思想是：由一组前提出发,利用一些公认的规则,根据已知的等价式或蕴含式,推演得到有效结论 。
公认的推理规则有 4条：
P规则：前提在推导过程中的任何时候都可以引入使用 。
T规则：推理中,如果一个或多个公式,蕴含了公式 S，
则公式 S可以引入到以后的推理之中 。
第 1章 命题逻辑置换规则：在推导过程的任何步骤上,命题公式中的子公式都可以用与之等价的公式置换 。
合取引入规则：任意两个命题公式 A,B可以推出 A∧ B
常用的等价式和蕴合式包括 1.3节中的 23个命题定律,1.7节中的 13个重要的蕴含式及过去学过的所有等价式和蕴含式。
【 例 1.34】 用直接推理法证明 (p→q)∧ (q→r)∧ p?r
证明,⑴ p→q P
⑵ p P
⑶ q T⑴⑵ 假言推理
⑷ q→r P
⑸ r T⑶⑷ 假言推理
⑵ 间接推理间接推理常有下列两种方法：
① CP规则有时要证明的有效结论是一个条件命题,即要证明：
第 1章 命题逻辑
H1∧ H2∧? ∧ Hn?(A→ B)
其中,H1,H2,?,Hn,A,B是命题公式 。
令 S?H1∧ H2∧? ∧ Hn
则上式可以简化为 S?(A→ B)
由蕴含的定义有 1?S→ (A→ B)S∨ (?A∨ B)
(?S∨?A)∨ B(S∧ A)∨ B
(S∧ A)→ B
H1∧ H2∧? ∧ Hn∧ A→ B
即 H1∧ H2∧? ∧ Hn∧ A?B
所以,要证明 H1∧ H2∧? ∧ Hn?(A→ B),只需证明
H1∧ H2∧? ∧ Hn∧ A?B,其中 A叫做附加前提 。
这种间接推理方法称为 CP规则。
第 1章 命题逻辑
【 例 1.37】 用 CP规则证明,p→ (q→ r),?t∨ p,q?t→ r
证明：
⑴ t P(附加前提 )
⑵?t∨ p P
⑶ p T⑴⑵ 析取三段论
⑷ p→ (q→ r) P
⑸ q→ r T⑶⑷ 假言推理
⑹ q P
⑺ r T⑸⑹ 假言推理
⑻ t→ r CP规则第 1章 命题逻辑
② 归谬法设要证明 H1∧ H2∧? ∧ Hn?C
其中,H1,H2,?,Hn,C是命题公式 。
令 S?H1∧ H2∧? ∧ Hn
则上式可以简化为 S?C
由蕴含的定义有 1?S→CS∨ C
两边否定 0?S∧?C? H1∧ H2∧? ∧ Hn∧?C
即要证明 C是前提 H1,H2,?,Hn的有效结论,只须证明
H1∧ H2∧? ∧ Hn∧?C?0
由定理 1.7.3知,上式等价下面两式：
0?H1∧ H2∧? ∧ Hn∧?C
H1∧ H2∧? ∧ Hn∧?C?0
根据条件联结词的定义,前一式显然成立 。 所以要证明
H1∧ H2∧? ∧ Hn?C，
只需证明 H1∧ H2∧? ∧ Hn∧?C?0 其中,?C叫做附加前提 。
这种间接推理方法称为归谬法,它就是常说的反证法 。
第 1章 命题逻辑
【 例 1.38】 用 归谬法证明
(p∧ q)→r,?r∨ s,?s,pq
证明：
⑴ q P(附加前提 )
⑵?r∨ s P
⑶?s P
⑷?r T⑵⑶ 析取三段论
⑸ (p∧ q)→r P
⑹?( p∧ q) T⑷⑸ 拒取式
⑺?p∨?q T⑹ 德摩根律
⑻ p P
⑼?q T⑺⑻ 析取三段论
⑽ q∧?q(矛盾 ) T⑴⑼ 合取引入第 1章 命题逻辑
【 例 1.39】 用归谬法证明 p→ q,?(q∨ r)可逻辑推出?p
证明：
⑴ p→ q P
⑵ p P(附加前提 )
⑶ q T⑴⑵ 假言推理
⑷?(q∨ r) P
⑸?q∧?r T⑷ 德摩根律
⑹?q T⑸ 化简律
⑺ q∧?q (矛盾 ) T⑶⑹ 合取引入返回总目录返回章目录
1.1 命题及联结词
1.2 命题公式与翻译
1.3 真值表和等价公式
1.4 重言式
1.5 范式
1.6 全功能联结词集
1.7 对偶式与蕴含式
1.8 命题逻辑的推理理论 返回总目录第 1章 命题逻辑第 1章 命题逻辑
1.1命题及联结词
1.1.1 命题的基本概念在数理逻辑中把 能判断真假的陈述句称为命题 。 一般用小写英文字母或小写英文字母带下标表示 。
命题的概念包含了以下 3个要素：
⑴ 只有陈述句才有可能成为命题,而其它的语句,如：
感叹句,祈使句,疑问句等都不是命题 。
⑵ 一个语句虽是陈述句,但不能判断真假不是命题 。
⑶ 虽然要求命题能判断真假,但不要求现在就能确定真假,将来可以确定真假也可以 。
一个命题表达的判断结果称为命题的真值 。 命题的真值有,真,和,假,两种,分别用 True,T,1(真 )和 False、
F,0(假 )来表示 。 真值为真的命题称为真命题,真值为假的命题称为假命题 。 任何命题的真值是惟一的 。
第 1章 命题逻辑在命题逻辑中对命题不再细分，因而命题是数理逻辑中最基本的也是最小的研究单位。
【 例 1.1】 判断以下语句是否为命题 。 若是命题,确定其真值 。
⑴ 上海是个小村庄 。
⑵ 存在外星人 。
⑶ 禁止吸烟 ！
⑷ 北京是中国的首都 。
⑸ 4是素数或 6是素数 。
⑹ 今天你吃了吗？
⑺ 11+1=100
⑻ 我正在说谎 。
解,⑴ 命题 (F),⑵ 命题 (待定 ),⑶ 不是命题 (祈使句 )，
⑷ 命题 (T),⑸ 命题 (F),⑹ 不是命题 (疑问句 ),⑺ 命题 (由上下文确定 ),⑻ 不是命题 (悖论 )。
第 1章 命题逻辑表示命题的小写英文字母或带下标的小写英文字母常称为命题标识符 。 如果命题标识符表示一个具体,确定的命题,
称为命题常元 。 如果命题标识符表示任意一个命题,称为命题变元 。 命题变元无确定的真值 。
命题是能判断真假的陈述句 。 而命题变元代表任意的命题,其真值是不确定的 。 因而不是命题 。
如果一个命题不能再分解成更简单的命题,则称该命题为原子命题 。 如果一个命题不是原子命题,称 该命题 为复合命题 。
如果命题变元表示原子命题时,该命题变元称为原子变元 。
在自然语言中,可以通过,如果?,那么?,,,不但?,而且?,这样的连词将简单的陈述句联结成复合语句,
同样在命题逻辑当中,也可以通过命题联结词将原子变元联结起来表示复合命题 。
第 1章 命题逻辑
1.1.2 命题联结词常用的逻辑联结词有五种：否定联结词,合取联结词,析取联结词,条件联结词和双条件联结词 。
1,否定联结词定义 1.1.1 设 p为命题,则 p的否定是一个复合命题,记作,?p,读作,非 p” 或
,p的否定,。 定义为：若 P为 T,则?p为 F；
若 p为 F,则?p的真值为 T。
表 1.1
p?p
0 1
1 0
p和?p的关系如表 1.1所示,表 1.1叫做否定联结词,?”
的真值表 (下同 )。
联结词,?” 也可以看作逻辑运算,它是一元运算 。
【 例 1.2】 否定下列命题 。
p：王强是一名大学生 。
p：王强不是一名大学生 。
第 1章 命题逻辑
2,合取联结词定义 1.1.2设 p和 q均为命题,则 p
和 q的合取是一个复合命题,记作
p∧ q,读作,p与 q” 或,p合取 q” 。
定义为：当且仅当 p和 q均为 T时,
p∧ q的才为 T。
联结词,∧,的真值表 如 表 1.2
所示 。
联结词,∧,也可以看成逻辑运算，它是二元逻辑运算。
表 1.2
p q p∧ q
0 0 0
0 1 0
1 0 0
1 1 1
【 例 1.3】 设 p,2008年将在北京举办奥运会 。
q：中国是世界四大文明古国之一 。
则 p∧ q,2008年将在北京举办奥运会并且中国是世界四大文明古国之一 。
第 1章 命题逻辑
3,析取联结词定义 1.1.3 设 p和 q均为命题,
则 p和 q的析取是一个复合命题,
记作 p∨ q,读作,p或 q” 或者,p
析取 q” 。 定义为：当且仅当 p和 q
均为 F时,p∨ q才为 F。
联结词,∨,的真值表如表
1.3所示 。
联结词,∨,也可以看成逻辑运算,它是二元逻辑运算 。
表 1.3
p q p∨ q
0 0 0
0 1 1
1 0 1
1 1 1
,∨,与汉语中的,或,相似，但又不相同。汉语中的或有可兼或与不可兼或 (排斥或 )的区分。
【 例 1.4】 下列两个命题中的,或,,哪个是可兼或？ 哪个是不可兼或？
⑴在电视上看这场杂技或在剧场里看这场杂技。 (不可兼 )
⑵ 灯泡有故障或开关有故障。 (可兼,,∨,是 可兼 或 )
第 1章 命题逻辑
4,条件联结词定义 1.1.4 设 p和 q均为命题,其条件命题是个复合命题，记为,p→ q。读作,如果 p，那么 q” 或,若 p，则 q” 。
定义为：当且仅当 p为 T,q为 F时，
p→ q才为 F。 p称为条件命题 p→ q的前件，
q称为条件命题 p→ q的后件。
联结词,→,真值表如表 1.4所示 。
联结词,→,也可以看成逻辑运算，
它是二元逻辑运算。
表 1.4
p q p→ q
0 0 1
0 1 1
1 0 0
1 1 1
【 例 1.5】 p：小王努力学习 。 q：小王学习成绩优秀 。
p→ q：如果小王努力学习,那么他的学习成绩就优秀 。
联结词,→” 与汉语中的,如果?,那么?,或,若?,
则?,相似,但又是不相同的 。
第 1章 命题逻辑
5,双条件联结词定义 1.1.5设 p和 q均为命题,其复合命题 p?q称为双条件命题,读作：,p
双条件 q” 或者,p当且仅当 q” 。 定义为：当且仅当 p和 q的真值相同时,p?q
为 T。
联结词,?” 的真值表如表 1.5所示 。
联结词,?” 也可以理解成逻辑运算,
它是二元逻辑运算 。
双条件联结词表示的是一个充分必要关系,与前面所述相同,也可以不必表 1.5
p q p?q
0 0 1
0 1 0
1 0 0
1 1 1
顾及其前因后果,而只根据联结词的定义来确定其真值 。
【 例 1.6】 设 p：张华是三好学生 。
q：张华德,智,体全优秀 。
p?q：张华是三好学生当且仅当德,智,体全优秀 。
返回章目录第 1章 命题逻辑
1.2 命题公式与翻译把命题常量,命题变量按照一定的逻辑顺序用命题联结词连接起来就构成了命题演算的合式公式,也叫命题公式 。
当使用联结词集,∧,∨,→,时,合式公式定义如下：
定义 1.2.1按下列规则构成的符号串称为命题演算的合式公式,也称为命题公式,简称公式 。
⑴ 单个命题变元和常元是合式公式 。
⑵ 如果 A是合式公式,那么?A是合式公式 。
⑶ 如果 A和 B是合式公式,那么 (A∧ B),(A∨ B),(A→ B)
和 (A?B)是合式公式 。
⑷ 当且仅当有限次地应用了 ⑴,⑵,⑶ 所得到的符号串是合式公式 。
命题公式一般的用大写的英文字母 A,B,C,? 表示 。
依照这个定义,下列符号串是合式公式：
第 1章 命题逻辑
(p∨ q),?(p∨ q),(p→ (p∨?q))，
(((p→ q)∧ (q→ r))?(s?t))
下列符号串不是合式公式：
(p→ q)→ (∧ q),(p→ q,(p∧ q)→ q)
定义 1.2.1给出合式公式定义的方法称为归纳定义,它包括三部分：基础,归纳和界限 。 定义 1.2.1中的 ⑴ 是基础,⑵
和 ⑶ 是归纳,⑷ 是界限 。 下文中还将多次出现这种形式的定义 。
为方便起见,对命题公式约定如下：
⑴ 最外层括号可以省略 。
⑵ 规定联结词的优先级由高到低依次为?,∧,∨,→,
。 按此优先级别,如果去掉括号,不改变原公式运算次序,
也可以省掉这些括号 。
一般地说,命题公式中包含命题变元,因而无法计算其真值,所以不是命题 。
命题公式中的命题变元,也叫命题公式的分量 。
第 1章 命题逻辑有了命题公式的概念,就可以用命题公式表示复合命题,常将这个过程称为命题的符号化 。 命题的符号化可按如下步骤进行：
⑴ 找出复合命题中的原子命题 。
⑵ 用小写的英文字母或带下标的小写的英文字母表示这些原子命题 。
⑶ 使用命题联结词将这些小写的英文字母或带下标的小写的英文字母连接起来 。
【 例 1.7】 将下列命题符号化：
他或者骑自行车去学校,或者乘公共汽车去学校 。
解,令 p：他骑自行车去学校。
q：他乘公共汽车去学校 。
此命题中的或是不可兼或,所以不能符号化为,p∨ q。
而要 符号化为,?(p?q)或 (?p∧ q)∨( p∧?q)。 稍后会看到这个表示是正确的 。
返回章目录第 1章 命题逻辑
1.3真值表和等价公式
1.3.1命题公式的真值表定义 1.3.1 设 pl,p2,?,pn是出现在公式 A中的全部命题变元，给 pl,p2,?,pn各指定一个真值，称为对公式 A的一个赋值或解释。若指定的赋值使 A的真值为 T，则称这个赋值为 A的成真赋值，若使 A的真值为 F，则称这个赋值为 A的成假赋值。
例如，给公式 (p∨ q→r)赋值 011是指 p=0,q=1,r=1，它是该公式的成真赋值；赋值 110是指 p=1,q=1,r=0，它是该公式的成假赋值。
定义 1.3.2 在命题公式 A中,对 A的每一个赋值,就确定了
A的一个真值,把它们汇列成表,称该表为命题公式 A的真值表 。
第 1章 命题逻辑
【 例 1.8】 构造命题公式?p∨ q的真值表,并求成真赋值和成假赋值 。
解,命题公式?p∨ q的真值表如表 1.6所示。 00,01，
11是成真赋值,10是成假赋值。
表 1.6
p q?p?p∨ q
0 0 1 1
0 1 1 1
1 0 0 0
1 1 0 1
第 1章 命题逻辑表 1.7
p q p∧ q?p?q?p∧?q (p∧ q)∨ (?p∧?q)
0 0 0 1 1 1 1
0 1 0 1 0 0 0
1 0 0 0 1 0 0
1 1 1 0 0 0 1
【 例 1.9】 构造命题公式 (p∧ q)∨ (?p∧?q)的真值表，并求成真赋值和成假赋值。
解,命题公式 (p∧ q)∨ (?p∧?q)的真值表如表 1.7所示。
00,11是成真赋值,01,10是成假赋值。
第 1章 命题逻辑
1.3.2命题公式的等价定义 1.3.3 设 A和 B是两个命题公式,对 A和 B的任一赋值,
A和 B的真值都相同,则称 A和 B是等价的或逻辑相等的,记为 A?B
可以证明,命题公式等价有下面的三条性质：
⑴ 自反性,即对任意命题公式 A,A?A
⑵ 对称性,即对任意命题公式 A和 B,若 A?B,则 B?A
⑶ 传递性,即对任意命题公式 A,B和 C,若 A?B，
B?C,则 A?C
根据定义 1.3.3,可以用真值表证明命题公式是等价的，
请看下面的例题。
【 例 1.12】 根据等价的定义，用真值表证明
p→(q→p)p→(p→?q)
证明,构造 p→(q→p)和?p→(p→?q)的真值表，如表
1.10所示。 p→(q→p)和?p→(p→?q)所在的列完全相同，它们具有相同的真值表。所以 p→(q→p)p→(p→?q)
第 1章 命题逻辑表 1.10
p q?p?q q→ p p→ (q→ p) p→?q?p→ (p→?q)
0 0 1 1 1 1 1 1
0 1 1 0 0 1 1 1
1 0 0 1 1 1 1 1
1 1 0 0 1 1 0 1
证明等价 的 另外一种方法叫做等价演算法,其基本思想是：先用真值表证明一组基本等价式，以它们为基础进行公式之间的演算。 基本等价式常叫命题定律。下面是常用的命题定律。
1.双重否定律 AA
2.交换律 A∨ B?B∨ A,A∧ B?B∧ A
3.结合律 (A∨ B)∨ C?A∨ (B∨ C)
(A∧ B)∧ C?A∧ (B∧ C)
第 1章 命题逻辑
4.分配律 A∧ (B∨ C)?(A∧ B)∨ (A∧ C)
A∨ (B∧ C)?(A∨ B)∧ (A∨ C)
5.德摩根律?(A∨ B)A∧?B
(A∧ B)A∨?B
6.幂等律 A∧ A?A,A∨ A?A
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→ BA∨ B
13.双条件等价式 A?B?(A→ B)∧ (B→ A)
14.假言易位式 A→ BB→?A
15.双条件否定等价式 A?BAB
第 1章 命题逻辑以上共 23个等价式，原则上说，这些公式都可以用真值表证明。下面仅验证德摩根律。
【 例 1.13】 用真值表证明德摩根律?(A∨ B)A∧?B
解,表 1.11是?(A∨ B)和?A∧?B的真值表，从表中可以看出德摩根律成立 。
表 1.11
A B?A?B?A∧?B A∨ B?(A∨ B)
0 0 1 1 1 0 1
0 1 1 0 0 1 0
1 0 0 1 0 1 0
1 1 0 0 0 1 0
第 1章 命题逻辑定义 1.3.4如果 X是合式公式 A的一部分且 X本身也是合式公式,则称 X为公式 A的子公式 。
例如,A?q→ (p∨ (p∧ q)),X?p∧ q，则 X是 A的子公式。
定理 1.3.1设 X是合式公式 A的子公式,若 X?Y,如果将 A
中的 X用 Y来置换,得到的公式记为 B,则 B与 A等价,即 A?B
证明,对 A,B的任一赋值,X与 Y的真值相同,而 A,B
的其它部分完全相同,公式 B与公式 A的真值必相同 。 A?B
满足此定理的置换叫做等价置换 。
【 例 1.17】 用等价演算法证明 p?q?(p∧ q)∨ (?p∧?q)
证明,p?q?(p→ q)∧ (q→ p) (双条件等价式 )
(?p∨ q)∧ (?q∨ p) (条件等价式 )
(?p∧?q)∨ (?p∧ p)∨ (q∧?q)∨ (q∧ p) (分配律 )
(?p∧?q)∨ 0∨ 0∨ (q∧ p) (矛盾律 )
(?p∧?q)∨ (q∧ p) (同一律 )
(p∧ q)∨ (?p∧?q) (交换律 )
p?q?(p∧ q)∨ (?p∧?q) (等价的传递性 )
返回章目录第 1章 命题逻辑
1.4重言式定义 1.4.1 设 A是任一命题公式 。
⑴ 若对 A的任意赋值,其真值永为真,则称命题公式 A
为重言式或永真式 。
⑵ 若对 A的任意赋值,其真值永为假,则称命题公式 A
为矛盾式或永假式 。
⑶ 若 A不是矛盾式,则称命题公式 A为可满足的 。
由定义 1.4.1可以看出，任何重言式都是可满足的。
显然,重言式的真值表的最后一列全为 1,矛盾式的真值表的最后一列全为 0,可满足的公式真值表的最后一列至少有一个 1。 根据这个结论借助于真值表可以判断一个公式是否为重言式,矛盾式或可满足的 。 当然也可以用等价演算法判断公式的类型 。
【 例 1.18】 用等价演算法判断下列公式的类型。
⑴ q∨?((?p∨ q)∧ p)
第 1章 命题逻辑
⑵ (p∨?p)→((q∨?q)∧ r)
⑶ (p→q)∧?p
解,⑴ q∨?((?p∨ q)∧ p)
q∨?((?p∧ p)∨ (q∧ p)) (分配律 )
q∨?(0∨ (q∧ p)) (矛盾律 )
q∨?(q∧ p) (同一律 )
q∨ (?q∨?p) (德摩根律 )
(q∨?q)∨?p (结合律 )
1∨?p (排中律 )
1 (零律 )
由此可知,⑴ 为重言式 。
⑵ (p∨?p)→((q∧?q)∧ r)
1→((q∧?q)∧ r) (排中律 )
1→(0∧ r) (矛盾律 )
1→0 (零律 )
0 (条件联结词的定义 )
第 1章 命题逻辑由此可知,⑵ 为矛盾式 。
⑶ (p→ q)∧?p
(?p∨ q)∧?p (条件等价式 )
p (吸收律 )
由此可知，⑶是可满足的。
定理 1.4.1 任何两个重言式的合取或析取都是重言式。
证明,设 A,B是重言式,对 A和 B的任何赋值,总有 A为
1,B为 1,所以 A∧ B?1,A∨ B?1,故 A∧ B和 A∨ B都是重言式 。
推论 任何两个矛盾式的合取或析取是矛盾式。
定理 1.4.2 一个重言式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式 。
推论,一个矛盾式,对同一分量出现的每一处都用同一合式公式置换,其结果仍是矛盾式 。
第 1章 命题逻辑
【 例 1.19】 利用定理 1.4.2证明 ((p∨ q)∧ r)∨?((p∨ q)∧ r)
为重言式。
证明,由排中律知 p∨?p为重言式，以 ((p∨ q)∧ r)去置换其中的 p，得公式 ((p∨ q)∧ r)∨?((p∨ q)∧ r)，根据定理 1.4.2，
这是重言式。
定理 1.4.3 设 A,B为两个命题公式,A?B当且仅当 A?B
是重言式 。
证明,设 A?B,下证 A?B是重言式 。
给 A,B的任何赋值,因为 A?B,所以 A,B具有相同的真值,由双条件联结词的定义知 A?B为真,所以 A?B为重言式 。
设 A?B为重言式,下证 A?B
给 A,B的任何赋值,因为 A?B为重言式,故 A,B的真值相同,由命题公式等价的定义知 A?B
返回章目录第 1章 命题逻辑
1.5范式
1.5.1析取范式与合取范式定义 1.5.1由一些命题变元或其否定构成的析取式称为基本和,也叫简单析取式 。 约定单个变元或其否定是基本和 。
例如,?p∨ q,p∨?q,p∨ q,?q,?p,q都是基本和。
定义 1.5.2由一些命题变元或其否定构成的合取式称为基本积，也叫简单合取式。约定单个变元或其否定是基本积。
例如,?p∧ q,p∧?q,p∧ q,?p,?q,p都是基本积。
定义 1.5.3由 基本和的合取构成的公式叫做合取范式。 约定单个 基本和 是 合取范式 。
定义 1.5.4由基本积的析取构成的公式叫做析取范式。 约定单个 基本积 是 析取范式 。
任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步骤如下：
⑴ 消去联结词,→” 和,?”
第 1章 命题逻辑
⑵ 利用双重否定律消去否定联结词,?” 或利用德摩根律将否定联结词,?” 移到各命题变元前 (?内移 )。
⑶ 利用分配律,结合律将公式归约为合取范式和析取范式 。
【 例 1.21】 求命题公式 (p∨ q)?p 的合取范式和析取范式 。
解,⑴ 求合取范式
(p∨ q)?p
((p∨ q)→p)∧ (p→(p∨ q)) (消去?)
(?(p∨ q)∨ p)∧ (?p∨ (p∨ q)) (消去 →)
((?p∧?q)∨ p)∧ (?p∨ (p∨ q)) (?内移 )
(?p∨ p)∧ (?q∨ p)∧ (?p∨ p∨ q) (分配律,合取范式 )
1∧ (?q∨ p)∧ (1∨ q) (排中律 )
1∧ (?q∨ p)∧ 1 (零律,合取范式 )
(?q∨ p) (同一律,合取范式 )
由此例可以看出,公式的合取范式并不惟一 。
第 1章 命题逻辑
⑵ 求析取范式
(p∨ q)?p
((p∨ q)∧ p)∨ (?(p∨ q)∧?p) (消去?)
((p∨ q)∧ p)∨ ((?p∧?q)∧?p) (?内移 )
p∨ (?p∧?q∧?p) (吸收律,析取范式 )
p∨ (?p∧?p∧?q) (交换律 )
p∨ (?p∧?q) (幂等律,析取范式 )
由此例可以看出,命题公式的析取范式也不惟一 。
1.5.2主析取范式由于析取范式和合取范式不惟一，所以使用起来很不方便。为此，引入主析取范式和主合取范式的概念。当命题变元的顺序约定以后，主析取范式和主合取范式是惟一的。
析取范式和合取范式的基本成分是基本积和基本和,而主析取范式和主合取范式的基本成分是极小项和极大项,它们分别是特殊的基本积和基本和 。
第 1章 命题逻辑定义 1.5.5在基本积中，每个变元及其否定不同时存在，
但两者之一必须出现且仅出现一次，这样的基本积叫做布尔合取也叫小项或极小项。
p,q的极小项为,p∧ q,p∧?q,?p∧ q,?p∧?q
两个命题变元的极小项共 4(=22)个,三个命题变元的极小项共 8(=23)个,? 。一般地说,n个命题变元共有 2n个极小项。
表 1.12是两个变元 p和 q的极小项的真值表 。 极小项有下列的性质：
⑴ 每个极小项只有一个成真赋值,且各极小项的成真赋值互不相同 。 极小项和它的成真赋值构成了一一对应的关系 。 可用成真赋值为极小项进行编码,并把编码作为 m的下标来表示该极小项,叫做该极小项的名称 。
两个命题变元的极小项,成真赋值 和名称如表 1.13所示 。
三个命题变元的极小项,成真赋值和名称如表 1.14所示 。
从表 1.13和表 1.14中可以看出，极小项与其成真赋值的对应关系为：变元对应 1，而变元的否定对应 0。
第 1章 命题逻辑表 1.12
p q p∧ q p∧?q?p∧ q?p∧?q
0 0 0 0 0 1
0 1 0 0 1 0
1 0 0 1 0 0
1 1 1 0 0 0
表 1.13
极小项 成真赋值 名称
p∧?q 00 m0
p∧ q 01 m1
p∧?q 10 m2
p∧ q 11 m3
第 1章 命题逻辑表 1.14
极小项 成真赋值 名称
p∧?q∧?r 000 m0
p∧?q∧ r 001 m1
p∧ q∧?r 010 m2
p∧ q∧ r 011 m3
p∧?q∧?r 100 m4
p∧?q∧ r 101 m5
p∧ q∧?r 110 m6
p∧ q∧ r 111 m7
第 1章 命题逻辑
⑵ 任意两个不同的极小项的合取式为永假式 。
例如：
m001∧ m100?(?p∧?q∧ r)∧ (p∧?q∧?r)
p∧?q∧ r∧ p∧?q∧?r?0
⑶ 全体极小项的析取式为永真式 。 记为：
12
0
n
i
im
m0∨ m1∨? ∨?1
定义 1.5.6 对于给定的命题公式,如果有一个它的等价公式,仅由极小项的析取组成,称该公式为原公式的主析取范式 。
任何命题公式都存在着与之等价的主析取范式。一个命题公式的主析取范式可以由以下两种方法求得：
⑴等价演算法：即用基本等价公式推出。
12?nm
第 1章 命题逻辑用等价演算法求主析取范式的步骤如下：
① 化归为析取范式。
② 除去析取范式中所有永假的基本积 。
③ 在基本积中,将重复出现的合取项和相同变元合并 。
④ 在基本积中补入没有出现的命题变元，即添加
∧ (p∨?p)，再用分配律展开，最后合并相同的极小项。
【 例 1.22】 用等价演算法求 (p∧ q)∨ (?p∧ r)∨ (q∧ r)的主析取范式。
解,(p∧ q)∨ (?p∧ r)∨ (q∧ r)
(p∧ q∧ (r∨?r))∨ (?p∧ r∧ (q∨?q))∨ (q∧ r∧ (p∨?p))
(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)
m111∨ m110∨ m011∨ m001
m7∨ m6∨ m3∨ m1?∑1,3,6,7
第 1章 命题逻辑
⑵ 真值表法：即用真值表求主析取范式 。
用真值表求主析取范式的步骤如下：
① 构造命题公式的真值表 。
② 找出 公式的成真赋值对应的极小项 。
③ 这些极小项的析取就是此公式的主析取范式。
【 例 1.24】 用真值表法，求 (p→q)→r的主析取范式。
解,表 1.15是 (p→q)→r的真值表,公式的成真赋值对应的极小项为：
p∧?q∧ r (成真赋值为 001)
p∧ q∧ r (成真赋值为 011)
p∧?q∧?r (成真赋值为 100)
p∧?q∧ r (成真赋值为 101)
p∧ q∧ r (成真赋值为 111)
(p→q)→r 的主析取范式为：
第 1章 命题逻辑
(p∧ q∧ r)∨ (p∧?q∧ r)∨ (p∧?q∧?r) ∨ (?p∧ q∧ r)
∨ (?p∧?q∧ r)
m111∨ m101∨ m100∨ m011∨ m001?m7∨ m5∨ m4∨ m3∨ m1
∑1,3,4,5,7
表 1.15
p q r p→ q (p→ q)→ r
0 0 0 1 0
0 0 1 1 1
0 1 0 1 0
0 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 1 0 1 0
1 1 1 1 1
第 1章 命题逻辑矛盾式无成真赋值，因而主析取范式不含任何极小项，
将矛盾式的主析取范式记为 0。而重言式无成假赋值，因而主析取范式含 2n (n为公式中命题变元的个数 )个极小项。至于可满足式，它的主析取范式中极小项的个数一定小于等于 2n。
1.5.3主合取范式定义 1.5.7在基本和中,每个变元及其否定不同时存在,
但两者之一必须出现且仅出现一次,这样的基本和叫作布尔析取,也叫大项或极大项 。
两个变元 p,q构成的极大项为：
p∨ q,p∨?q,?p∨ q,?p∨?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
两个命题变元的极大项共 4(=22)个,三个命题变元的极大项共 8(=23)个,? 。 一般地说,n个变元共有 2n个极大项 。
第 1章 命题逻辑极大项有下列三个性质：
⑴ 每个极大项只有一个成假赋值,极大项不同,成假赋值也不同 。 极大项和它的成假赋值构成了一一对应的关系 。
故可用成假赋值为该极大项进行编码,并把编码作为 M的下标来表示该极大项,叫做极大项的名称 。
例如,两个变元 p,q的极大项?p∨?q,它的成假赋值是
11,表示为 M11,把 11理解为 2进制数,它的 10进制表示为 3，
所以 M11又表示为 M3。 表 1.16
极大项 成假赋值 名称
p∨ q 00 M0
p∨?q 01 M1
p∨ q 10 M2
p∨?q 11 M3
两个命题变元的极大项，成假赋值及名称见表
1.16，三个命题变元的极大项，成假赋值及名称见表 1.17。
第 1章 命题逻辑从表 1.16和表
1.17中可以看出，极大项与成假赋值的对应关系为：变元对应
0，而变元的否定对应 1。
⑵ 任意两个不同的极大项的析取式为永真式 。
⑶ 全体极大项的合取式为永假式 。 记为：
表 1.17
极大项 成假赋值 名称
p∨ q∨ r 000 M0
p∨ q∨?r 001 M1
p∨?q∨ r 010 M2
p∨?q∨?r 011 M3
p∨ q∨ r 100 M4
p∨ q∨?r 101 M5
p∨?q∨ r 110 M6
p∨?q∨?r 111 M7
12
0
n
i
iM
M0∧ M1∧? ∧
12?nM
0
第 1章 命题逻辑定义 1.5.8 对于给定的命题公式,如果有一个它的等价公式,仅由极大项的合取组成,则该等价式称为原公式的主合取范式 。
任何命题公式都存在着与之等价的主合取范式 。 主合取范式也可以由以下两种方法求得 。
⑴ 等价演算法：即用基本等价公式推出 。
其演算步骤如下：
① 化归为合取范式 。
② 除去所有永真的基本和 。
③ 在基本和中合并重复出现的析取项和相同的变元 。
④ 在基本和中补入没有出现的命题变元 。 即增加
∨ (p∧?p),然后,应用分配律展开公式,最后合并相同的极大项 。
【 例 1.25】 用等价演算法求 (p→ q)→ r的主合取范式 。
解,(p→q)→r
第 1章 命题逻辑
(?p∨ q)∨ r?(p∧?q)∨ r?(p∨ r)∧ (?q∨ r)
(p∨ r∨ (q∧?q))∧ (?q∨ r∨ (p∧?p))
(p∨ r∨ q)∧ (p∨ r∨?q)∧ (p∨?q∨ r)∧ (?p∨?q∨ r)
(p∨ q∨ r)∧ (p∨?q∨ r)∧ (?p∨?q∨ r)
M000∧ M010∧ M110?M0∧ M2∧ M6?∏0,2,6
⑵ 真值表法：用真值表求主合取范式 。
用真值表求主 合 取范式的步骤如下：
① 构造命题公式的真值表 。
② 找出公式的成假赋值对应的极大项 。
③ 这些极大项的析取就是此公式的主合取范式 。
【 例 1.26】 用真值表法求 (p→ q)→ r的主合取范式 。
解,(p→ q)→ r的真值表是表 1.15。 公式的成假赋值对应的大项为：
p∨ q∨ r (成假赋值为 000)
p∨?q∨ r (成假赋值为 010)
第 1章 命题逻辑
p∨?q∨ r (成假赋值为 110)
主合取范式为,(p∨ q∨ r)∧ (p∨?q∨ r)∧ (?p∨?q∨ r)
M000∧ M010∧ M110?M0∧ M2∧ M6?∏ 0,2,6
矛盾式无成真赋值,因而矛盾式的主合取范式含 2n (n
为公式中命题变元的个数 )个极大项 。 而重言式无成假赋值,
因而主合取范式不含任何极大项 。 将重言式的主合取范式记为 1。 至于可满足式,它的主合取范式中极大项的个数一定小于 2n。
在例 1.23和例 1.24中求出 (p→ q)→ r的主析取范式为：
m7∨ m5∨ m4∨ m3∨ m1?∑ 1,3,4,5,7
在例 1.25和例 1.26中求出该公式的主合取范式为：
M0∧ M2∧ M6?∏ 0,2,6
比较这两个结果,得出以下的结论：同一公式的主析取范式中 m的下标和主合取范式中 M的下标是互补的 。 因此,
知道了主析 (合 )取范式就可以写出主合 (析 )取范式 。
返回章目录第 1章 命题逻辑
1.6全功能联结词集定义 1.6.1 设 p和 q是两个命题,复合命题 p q称作 p和 q的不可兼析取,也叫异或 。 定义为,p q为 T当且仅当 p和 q的真值不相同时 。 联结词,,称为异或联结词 。
表 1.18
p q
0 0 0
0 1 1
1 0 1
1 1 0
p? q
联结词,,的真值表如表 1.18所示 。
,” 也可以看成逻辑运算,它是二元逻辑运算 。 它在程序设中有广泛的引用 。
不可兼析取有下列的性质,
⑴ p q?q p (交换律 )?
⑵ (p q) r?p (q r) (结合律 )
第 1章 命题逻辑
⑶ p∧ (q r)?(p∧ q) (p∧ r) (合取对异或的分配律 )
⑷ p q?(p∧?q)∨ (?p∧ q)
⑸ p q(p?q)
⑹ p p?0,0 p?p,1 pp
定理 1.6.1 设 A,B,C为命题公式,如果 A B?C,则 A
C?B,B C?A,A B C为一矛盾式 。
定义 1.6.2 设 p和 q是两个命题,复合命题 p↑q称作 p和 q的与非 。 定义为：当且仅当 p和 q真值都是真时,p↑q才为假 。
联结词,↑” 称为与非联结词 。
联结词,↑” 的真值表如表 1.19所示 。
,↑” 也可以看成逻辑运算,它是二元逻辑运算 。
由定义可以看出下式成立：
p↑q( p∧ q)
联结词,↑” 还有以下几个性质：
第 1章 命题逻辑表 1.19
p q p↑ q
0 0 1
0 1 1
1 0 1
1 1 0
⑴ p↑ p(p∧ p)p
⑵ (p↑ q)↑ (p↑ q)(p↑ q)
(p∧ q)?p∧ q
⑶ (p↑ p)↑ (q↑ q)?(?p)↑ (?q)
(?p∧?q)?p∨ q
定义 1.6.3 设 p和 q是两个命题，
复合命题 p↓ q称作 p和 q的或非。
定义为：当且仅当 p,q的真值都为假时,p↓ q的真值为真。联结词,↓” 称为或非联结词。
联结词,↓” 的真值表如表
1.20所示 。
,↓” 也可以看成逻辑运算,
它是二元逻辑运算 。
表 1.20
p q p↓ q
0 0 1
0 1 0
1 0 0
1 1 0
第 1章 命题逻辑由此定义可得到下面的公式：
p↓ q(p∨ q)
联结词 ↓ 还有下面的几个性质：
⑴ p↓ p(p∨ p)p
⑵ (p↓ q)↓ (p↓ q)(p↓ q)(p∨ q)?p∨ q
⑶ (p↓ p)↓ (q↓ q)p↓?q(?p∨?q)?p∧ q
至此已经学了 8个联结词,?,∧,∨,→,?，,↑,
↓ 。 类似于定义 1.2.1的方法,可以定义包含上述 8个联结词的命题公式 。
定义 1.6.4 设 S是一个联结词集合，如果任何 n(n≥ 1)个变元组成的公式，都可以由 S中的联结词来表示，则称 S是全功能联结词集。
根据命题公式的定义,∧,∨,→,?，,↑,↓?是全功能联结词集 。
利用下列 3个等价式可将任何命题公式中的命题联结词
,”,,↑” 和,↓” 去掉 。
第 1章 命题逻辑
p q(p?q)
p↑ q(p∧ q)
p↓q(p∨ q)
所以,∧,∨,→,是全功能联结词集 。
利用下列 2个等价式可将任何命题公式中的 命题 联结词
,→,和,?” 去掉 。
p→qp∨ q
p?q?(p→q)∧ (q→p)?(?p∨ q)∧ (?q∨ p)
所以,∧,∨?是全功能联结词集 。
用德摩根律可证明,∧?和,∨?是全功能联结词集 。
可以证明?∧,∨,→,和?∧,∨,→,的任何子集都不是全功能联结词集 。
定义 1.6.5设 S是全功能联结词集,如果去掉其中的任何联结词后,就不是全功能联结词集,则称 S是最小全功能联结词集 。
第 1章 命题逻辑可以证明,∧?,,∨?,?↑?,?↓?是最小全功能联结词集 。
现在讨论,n个命题变元可以构成多少个不等价的命题公式 。
两个命题变元可以构成多少个不等价的命题公式？
由等价的概念知道，等价的命题公式有相同的真值表，
所以上述问题就转化为两个命题变元构成的命题公式有多少个不同的真值表？ 表 1.21
p q 公式
0 0 1或 0
0 1 1或 0
1 0 1或 0
1 1 1或 0
两个命题变元构成的命题公式的真值表的格式如表 1.21所示 。 真值表中每行公式的真值都有 1,0两种可能,所以 命题 公式的真值有
2× 2× 2× 2=24= =16种可能,既有 个不同的真值表 。 故有 种不等价的公式 。
返回章目录
222
222 222
第 1章 命题逻辑三个变元可构成 28= 个不等价的命题公式,n个变元可构成 个不等价的命题公式 。
1.7对偶式与蕰含式
1.7.1对偶式从 1.3节的命题定律中可以看出,很多常用等价式是成对出现的,只要将其中的,∧,和,∨,分别换成,∨,和
,∧,,就可以由一个得到另一个 。 例如,将命题定律
(A∨ B)∨ C?A∨ (B∨ C)中的,∨,换成,∧,就得到了命题定律 (A∧ B)∧ C?A∧ (B∧ C)。 这些成对出现的等价式反映了等价的对偶性 。 本节介绍对偶式和对偶原理 。
定义 1.7.1在仅含联结词?,∧,∨ 的命题公式 A中,将联结词 ∨,∧,F,T分别换成 ∧,∨,T,F所得的公式称为公式 A的对偶式,记为 A*。
设 A*是 A的对偶式,将 A*中的 ∨,∧,F,T分别换成 ∧,
∨,T,F,就会得到 A。 即 A 是 A*的对偶式,(A*)*?A。 所以说 A*和 A互为对偶式 。
322
n22
第 1章 命题逻辑
【 例 1.27】 求 p↑ q和 p↓ q的对偶式 。
解,p↑ q(p∧ q)
(p∧ q)的对偶式是?(p∨ q)?p↓ q
故 p↑ q的对偶式是 p↓ q；同样的方法可以证明 p↓ q的对偶式是 p↑ q。
根据例 1.27,对偶式概念可以推广为：在仅含有联结词
,∧,∨,↑,↓ 的命题公式中,将联结词 ∨,∧,↑,
↓,F,T分别换成 ∧,∨,↓,↑,T,F,就得到了它的对偶式 。
关于对偶式有以下两个结论 。
定理 1.7.1 设 A*是 A的对偶式,p1,p2,…,pn是出现在 A
和 A*中的原子变元,则
A(p1,p2,?,pn)?A*(?p1,?p2,?,?pn)
A(?p1,?p2,?,?pn)A*(p1,p2,?,pn)
第 1章 命题逻辑
【 例 1.28】 设命题公式 A(p,q,r)?(p∨ q)∧ r,试用此公式验证定理 1.7.1的有效性 。
证明,⑴ 验证?A(p,q,r)?A*(?p,?q,?r)
A(p,q,r)?(p∨ q)∧ r
A(p,q,r)((p∨ q)∧ r)?(?p∧?q)∨?r
A*(p,q,r)?(p∧ q)∨ r
A*(?p,?q,?r)?(?p∧?q)∨?r
所以,?A(p,q,r)?A*(?p,?q,?r)
⑵ 验证 A(?p,?q,?r)A*(p,q,r)
A(?p,?q,?r)?(?p∨?q)∧?r
((p∧ q)∨ r)A*(p,q,r)
第 1章 命题逻辑定理 1.7.2 (对偶原理 )设 p1,p2,?,pn是出现在公式
A和 B中的所有原子变元,如果 A?B,则 A*?B*
证明,因为 A?B
所以 A(p1,p2,?,pn)?B(p1,p2,?,pn)是重言式根据定理 1.4.2,在上述重言式中用?pi置换 pi，
i＝ 1,?,n,所得的公式仍为重言式,即
A(?p1,?p2,?,?pn)?B(?p1,?p2,?,?pn)是重言式 。
所以 A(?p1,?p2,?,?pn)?B(?p1,?p2,?,?pn)
由定理 1.7.1?A*(p1,p2,?,pn)B*(p1,p2,?,pn)
即?A*B*
由双条件否定等价式知 A*?B*
定理 1.7.2叫做对偶原理 。 对偶原理是数理逻辑中最基本的规律之一 。
第 1章 命题逻辑
【 例 1.29】 证明重言式的对偶式是矛盾式,矛盾式的对偶式是重言式 。
证明,设 A是重言式,即 A?1,因为 1的对偶式是 0,由对偶原理知 A*?0。 所以 A*是矛盾式；设 A是矛盾式,即
A?0,而 0的对偶式是 1,所以 A*?1。 所以 A*是重言式 。
1.7.2蕴含式定义 1.7.2 设 A和 B是命题公式,若 A→ B是重言式,则称
A蕴含 B,记为 A?B。
根据定义可以用真值表或等价演算证明 A?B。
A?B定义为,A→ B为重言式 。 又由条件命题的定义知,
仅在 A?T,B?F时,A→ B为假,其余情况都为真 。 故要证明 A?B,只需排除 A?T,B?F的情况 。 于是就有了证明
A?B的第二种方法：
第 1章 命题逻辑
⑴ 对 A指定真值 T,若由此推出 B的真值不为 F,而为 T，
则 A→ B是重言式,即 A?B。
⑵ 对 B指定真值 F，若由此推出 A的真值不为 T，而为 F，
则 A→ B是重言式，即 A?B。
【 例 1.31】 推证?p∧ (p∨ q)?q
解,证法 1：
假定?p∧ (p∨ q)为 Tp为 T且 p∨ q为 T?p为 F且 p∨ q为
T?q为 T。
所以?p∧ (p∨ q)?q
证法 2：
假定 q为 F,则 p可以为 T或 F。
① 当 p为 T时,?p为 F,所以?p∧ (p∨ q)为 F。
② 当 p为 F时,(p∨ q)为 F,所以?p∧ (p∨ q)为 F。
故?p∧ (p∨ q)?q
第 1章 命题逻辑蕴含式是逻辑推理的重要工具。下面是一些重要的蕴含式。它们都可以用上述两种方法证明，其中 A,B,C,D是任意的命题公式。
1.附加律 A?A∨ B,B?A∨ B
2.化简律 A∧ B?A,A∧ B?B
3.假言推理 A∧ (A→ B)?B
4.拒取式?B∧ (A→ B)A
5.析取三段论?A∧ (A∨ B)?B,?B∧ (A∨ B)?A
6.假言三段论 (A→ B)∧ (B→ C)?(A→ C)
7.等价三段论 (A?B)∧ (B?C)?(A?C)
8.构造性二难 (A∨ C)∧ (A→ B)∧ (C→ D)?B∨ D
(A∨?A)∧ (A→ B)∧ (?A→ B)?B
9.破坏性二难 (?B∨?D)∧ (A→ B)∧ (C→ D)?(?A∨?C)
第 1章 命题逻辑等价式和蕴含式有下面的关系 。
定理 1.7.3 设 A,B为任意两个命题公式,则 A?B的充分必要条件是 A?B且 B?A
证明,设 A?B,下证 A?B且 B?A
因为 A?B,所以 A?B?T
由双条件等价式得 (A→ B)∧ (B→ A)?A?B?T
因而 A→ B与 B→ A都是重言式,故有 A?B且 B?A。
设 A?B且 B?A,下证 A?B。
因为 A?B且 B?A,所以 A→B与 B→A都是重言式,重言式的合取也是重言式,即
(A→B)∧ (B→A)?T
再由双条件等价式得 (A?B)?(A→B)∧ (B→A)?T
即 A?B为重言式,故有 A?B。
返回章目录第 1章 命题逻辑根据此定理,以前学过的所有等价式都可以作两个蕴含式来使用 。 例如吸收律 A∨ (A∧ B)?A可以作两个蕴含式
A∨ (A∧ B)?A和 A?A∨ (A∧ B) 来使用 。
定理 1.7.4 设 A,B,C为合式公式 。
⑴ A?A (即蕴含是自反的 )
⑵ 若 A?B且 A为重言式,则 B必为重言式 。
⑶ 若 A?B且 B?C,则 A?C (即蕴含是传递的 )
⑷ 若 A?B且 A?C,则 A?B∧ C
⑸ 若 A?B且 C?B,则 A∨ C?B
⑹ 若 A?B,C是任意公式,则 A∧ C?B∧ C
证明,仅证明 ⑸。
因为 A?B,C?B,所以 A→ B?T,C→ B?T
(A∨ C)→ B(A∨ C)∨ B?(?A∧?C)∨ B
(?A∨ B)∧ (?C∨ B)?(A→ B)∧ (C→ B)?T∧ T?T
由等价的传递性,(A∨ C)→ B?T,故 A∨ C?B
第 1章 命题逻辑
1.8命题逻辑的推论理论数理逻辑的主要任务是用逻辑的方法研究数学中的推理 。
所谓推理是指从前提出发,应用推理规则推出结论的思维过程 。 任何一个推理都由前提和结论两部分组成 。 前提就是推理所根据的已知命题,结论则是从前提出发通过推理而得到的新命题 。 要研究推理,首先应该明确什么样的推理是有效的或正确的 。
定义 1.8.1 设 A1,A2,?,An和 C是 n+1个命题公式,若
A1∧ A2∧? ∧ An?C,则称 C为 A1,A2,?,An 的有效结论 。
也称 C可由 A1,A2,?,An 逻辑的推出 。 A1,A2,?,An叫做 C的一组前提 。
A1∧ A2∧? ∧ An?C,亦可记为 A1,A2,?,An?C。
由定义 1.8.1可以看出，要证明 C是一组前提 A1,A2,?,
An的有效结论，只需证明 A1∧ A2∧? ∧ An→ C为重言式。证明一个公式为重言式，可以用真值表、等价演算、主析 (合 )
第 1章 命题逻辑取范式或已知的蕴含式等方法进行。用等价演算和主析 (合 )
取范式证明重言式的方法前面已经讨论过了，我们已经非常熟悉了。这里仅对真值表法作简单说明。
用真值表证明有效结论有以下两种方法：
⑴ 用全真值表证明要证明 C为前提 A1,A2,?,An 的有效结论,只需构造命题公式 A1∧ A2∧? ∧ An→C的真值表,证明它是重言式 。
⑵ 用部分真值表证明因为条件命题 A1∧ A2∧? ∧ An→C为假当且仅当它的前件 A1∧ A2∧? ∧ An为真,后件 C为假 。 只要能排除前件为真,
后件为假的情况,A1∧ A2∧? ∧ An→C就是重言式 。 从而 C为一组前提 A1,A2,?,An 的有效结论 。 于是就有了下面方法：
构造 A1,A2,?,An与 C的真值表,且作在一个表上 。
① 找出 A1,A2,?,An都为真的行,若 C也为真,则
A1∧ A2∧? ∧ An?C,即 C为前提 A1,A2,?,An 的有效结论 。
第 1章 命题逻辑
② 找出 C为假的行，若在每个这样的行中,A1,A2,?,
An的真值至少有一个为假，则 A1∧ A2∧? ∧ An?C，即 C为一组前提 A1,A2,?,An的有效结论。
【 例 1.32】 分析事实：,如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。,。试指出这个推理前提和结论，并证明结论是前提的有效结论。
解,令 p：我有时间 。
q：我去上街 。
r：我去书店买书 。
根据题意,前提为,p→q,q→r,?r
结论为,?p
以下证明?p是一组前提 p→q,q→r,?r的有效结论 。
即证明,(p→q)∧ (q→r)∧?rp
第 1章 命题逻辑下面用部分真值表进行证明 。
作公式 p→ q,
q→ r,?r,?p的真值表,如表 1.23所示 。
从表中可以看出：
p→ q,q→ r,?r
都为 1的行 (赋值 000
的行 ),?p也为 1。
p为 0的行 ( 赋值 100,101,110，
111的行 ) p→ q，
表 1.23
p q r p→ q q→ r?r?p
0 0 0 1 1 1 1
0 0 1 1 1 0 1
0 1 0 1 0 1 1
0 1 1 1 1 0 1
1 0 0 0 1 1 0
1 0 1 0 1 0 0
1 1 0 1 0 1 0
1 1 1 1 1 0 0
q→ r,?r至少有一个为 0,所以 (p→ q)∧ (q→ r)∧?rp
第 1章 命题逻辑我们已经有了判断推理是否正确的 4种方法,即真值表法,等值演算法,主析取范式法和蕴含演算法 。 当推理中包含的命题变元较多时,以上 4种方法的演算量太大,给推理带来了困难 。 为此引入命题逻辑的推理理论 。 命题逻辑的推理是一个描述推理过程的命题公式序列,其中的每个命题公式或者是已知前提,或者是由某些前提应用推理规则得到的结论 (中间结论或推理中的结论 )。 它有两种方法：直接推理和间接推理 。
⑴ 直接推理直接推理的基本思想是：由一组前提出发,利用一些公认的规则,根据已知的等价式或蕴含式,推演得到有效结论 。
公认的推理规则有 4条：
P规则：前提在推导过程中的任何时候都可以引入使用 。
T规则：推理中,如果一个或多个公式,蕴含了公式 S，
则公式 S可以引入到以后的推理之中 。
第 1章 命题逻辑置换规则：在推导过程的任何步骤上,命题公式中的子公式都可以用与之等价的公式置换 。
合取引入规则：任意两个命题公式 A,B可以推出 A∧ B
常用的等价式和蕴合式包括 1.3节中的 23个命题定律,1.7节中的 13个重要的蕴含式及过去学过的所有等价式和蕴含式。
【 例 1.34】 用直接推理法证明 (p→q)∧ (q→r)∧ p?r
证明,⑴ p→q P
⑵ p P
⑶ q T⑴⑵ 假言推理
⑷ q→r P
⑸ r T⑶⑷ 假言推理
⑵ 间接推理间接推理常有下列两种方法：
① CP规则有时要证明的有效结论是一个条件命题,即要证明：
第 1章 命题逻辑
H1∧ H2∧? ∧ Hn?(A→ B)
其中,H1,H2,?,Hn,A,B是命题公式 。
令 S?H1∧ H2∧? ∧ Hn
则上式可以简化为 S?(A→ B)
由蕴含的定义有 1?S→ (A→ B)S∨ (?A∨ B)
(?S∨?A)∨ B(S∧ A)∨ B
(S∧ A)→ B
H1∧ H2∧? ∧ Hn∧ A→ B
即 H1∧ H2∧? ∧ Hn∧ A?B
所以,要证明 H1∧ H2∧? ∧ Hn?(A→ B),只需证明
H1∧ H2∧? ∧ Hn∧ A?B,其中 A叫做附加前提 。
这种间接推理方法称为 CP规则。
第 1章 命题逻辑
【 例 1.37】 用 CP规则证明,p→ (q→ r),?t∨ p,q?t→ r
证明：
⑴ t P(附加前提 )
⑵?t∨ p P
⑶ p T⑴⑵ 析取三段论
⑷ p→ (q→ r) P
⑸ q→ r T⑶⑷ 假言推理
⑹ q P
⑺ r T⑸⑹ 假言推理
⑻ t→ r CP规则第 1章 命题逻辑
② 归谬法设要证明 H1∧ H2∧? ∧ Hn?C
其中,H1,H2,?,Hn,C是命题公式 。
令 S?H1∧ H2∧? ∧ Hn
则上式可以简化为 S?C
由蕴含的定义有 1?S→CS∨ C
两边否定 0?S∧?C? H1∧ H2∧? ∧ Hn∧?C
即要证明 C是前提 H1,H2,?,Hn的有效结论,只须证明
H1∧ H2∧? ∧ Hn∧?C?0
由定理 1.7.3知,上式等价下面两式：
0?H1∧ H2∧? ∧ Hn∧?C
H1∧ H2∧? ∧ Hn∧?C?0
根据条件联结词的定义,前一式显然成立 。 所以要证明
H1∧ H2∧? ∧ Hn?C，
只需证明 H1∧ H2∧? ∧ Hn∧?C?0 其中,?C叫做附加前提 。
这种间接推理方法称为归谬法,它就是常说的反证法 。
第 1章 命题逻辑
【 例 1.38】 用 归谬法证明
(p∧ q)→r,?r∨ s,?s,pq
证明：
⑴ q P(附加前提 )
⑵?r∨ s P
⑶?s P
⑷?r T⑵⑶ 析取三段论
⑸ (p∧ q)→r P
⑹?( p∧ q) T⑷⑸ 拒取式
⑺?p∨?q T⑹ 德摩根律
⑻ p P
⑼?q T⑺⑻ 析取三段论
⑽ q∧?q(矛盾 ) T⑴⑼ 合取引入第 1章 命题逻辑
【 例 1.39】 用归谬法证明 p→ q,?(q∨ r)可逻辑推出?p
证明：
⑴ p→ q P
⑵ p P(附加前提 )
⑶ q T⑴⑵ 假言推理
⑷?(q∨ r) P
⑸?q∧?r T⑷ 德摩根律
⑹?q T⑸ 化简律
⑺ q∧?q (矛盾 ) T⑶⑹ 合取引入返回总目录返回章目录
