第 1章 命题逻辑第 1章 命题逻辑
1.1 命题符号化及联结词
1.2 命题公式及分类
1.3 等值演算
1.4 联结词全功能集
1.5 对偶与范式
1.6 推理理论
1.7 命题演算的自然推理形式系统 N
1.8 例题选解习 题 一第 1章 命题逻辑
1.1 命题符号化及联结词任何基于命题分析的逻辑称为命题逻辑。命题是研究思维规律的科学中的一项基本要素，它是一个判断的语言表达。
命题能唯一判断真假的陈述句。
这种陈述句的判断只有两种可能，一种是正确的判断，
一种是错误的判断。如果某个陈述句判断为真（与人们公认的客观事实相符），则我们称其为一真命题，并说此命题的真值为真，否则称为假命题，并说此命题的真值为假。
第 1章 命题逻辑
【 例 1.1.1】 下述各句均为命题：
（ 1） 4是偶数。（ 2）煤是白色的。
（ 3）,几何原本,的作者是欧几里德。
（ 4） 2190年人类将移居火星。
（ 5）地球外也有生命存在。
上述命题中（ 1）、（ 3）是真命题，（ 2）是假命题，其中的
（ 3）可能有人说不出它的真假，但客观上能判断真假。（ 4）
的结果目前谁也不知道，但到了时候则真假可辨，即其真值是客观存在的，因而是命题。同样，（ 5）的真值也是客观存在的，只是我们地球人尚不知道而已，随着科学技术的发展，其真值是可以知道的，因而也是命题。
第 1章 命题逻辑
【 例 1.1.2】 下列语句不是命题：
（ 1）你好吗？
（ 2）好棒啊！
（ 3）请勿吸烟。
（ 4） x＞ 3。
（ 5）我正在说谎。
（ 1）、（ 2）、（ 3）均不是陈述句，因而不是命题。（ 4）是陈述句，但它的真假取决于变量 x的取值，
例如取 x为 4时其值为真，取 x为 2时其值为假，即其真值不唯一，因此不是命题。（ 5）也是陈述句，但它是悖论，因而也不是命题。
第 1章 命题逻辑从上面讨论可以看出，判断一个语句是否是命题的关键是：
(1)语句必须是陈述句。
(2)陈述句必须具有唯一的真值。要注意两点：
①一个陈述句在客观上能判断真假，而不受人的知识范围的限制。
②一个陈述句暂时不能确定真值，但到了一定时候就可以确定，与一个陈述句的真值不能唯一确定是不同的。以上所讨论的命题均是一些简单陈述句。在语言学中称为简单句，其结构均具有,主语 +谓语,的形式，在数理逻辑中，我们将这种由简单句构成的命题称为简单命题，或称为原子命题，用 p,q、
r,pi,qi,ri等符号表示（必要时亦可用其它小写的英文字母表示）。如：
p,4是偶数。
q：煤是白的。
r：,几何原本,的作者是欧几里德。
第 1章 命题逻辑
【 例 1.1.3】 下列命题不是简单命题：
（ 1） 4是偶数且是 2的倍数。
（ 2）北京不是个小城市。
（ 3）小王或小李考试得第一。
（ 4）如果你努力，则你能成功。
（ 5）三角形是等边三角形，当且仅当三内角相等。
上面的命题除（ 3）的真假需由具体情况客观判断外，余者的真值均为 1。但是它们均不是简单命题，分别用了,且,,,非,,
,或,,,如果 ……则 ……”,,当且仅当,等联结词。
由命题和联结词构成的命题称为复合命题。构成复合命题的可以是原子命题，也可以是另一个复合命题。一个复合命题的真值不仅与构成复合命题的命题的真值有关，而且也与所用联结词有关。下面我们给出几个基本的联结词。
第 1章 命题逻辑
1.否定设 p为任一命题，复合命题“非 p”（ p的否定）称为 p的否定式，记作,为 否定联结词。
为真，当且仅当 p为假。
的真值亦可由表 1.1.1所示的称为,真值表,的表格确定。由表 1.1.1可知：命题 p为真，当且仅当
。事实上，它定义了一个一元函数 (称为一元真值函数 )：
""?
p ""p
p
p
,{ 0,1 } { 0,1 }
( 0 ) 1 ( 1 ) 0
f
ff
表 1.1.1
p
0 1
1 0
p
第 1章 命题逻辑
【 例 1.1.4】
(1)p,4是偶数。其真值为 1。
,4不是偶数。其真值为 0。
(2)q：这些都是学生。
：这些不都是学生。
注：否定联结词使用的原则：将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。例如上例中的（ 2）,q的否定式就不能写成,这些都不是学生,。事实上严格来讲,,不是,
不一定否定,是,。如阿契贝难题：,本句是六字句,
与,本句不是六字句,均是真命题。不过，一般地，
自然语言中的,不,,,无,,,没有”、“并非”
等词均可符号化为
p
p
" ".?
第 1章 命题逻辑
2.合取,∧,
设 p,q是任意两个命题，复合命题,p且 q”（ p与 q）
称为 p与 q的合取式，记作,p∧ q。,∧,是合取联结词。 p∧ q为真,p∧ q的真值表如表 1.1.2所示，它定义了一个二元真值函数：当且仅当 p,q均为真。
f∧,{00,01,10,11}→{0,1}，
f∧ (00)=0,f∧ (01)=0，
f∧ (10)=0，
f∧ (11)=1
表 1.1.2
p q p^q
0 0 0
0 1 0
1 0 0
1 1 1
第 1章 命题逻辑
【 例 1.1.5】
(1) p,4是偶数。 q,3是素数。则
p∧ q,4是偶数且 3是素数。其真值为 1。
(2) r：煤是白的。则
p∧ r,4是偶数且煤是白的。真值为 0。
第 1章 命题逻辑
3.析取,∨,
设 p,q是任意两个命题，复合命题,p或 q”称为 p、
q的析取式，记作,p∨ q。,∨,称为析取联结词。
p∨ q为假，当且仅当 p,q同为假。
p∨ q的真值表如表 1.1.3所示，它定义了一个二元真值函数：
f∨,{00,01,10,11}→{0,1}，
f∨ (00)=0,f∨ (01)=1，
f∨ (10)=1,f∨ (11)=1
表 1.1.3
p q p ∨ q
0 0 0
0 1 1
1 0 1
1 1 1
第 1章 命题逻辑
【 例 1.1.6】
(1) p：小王喜欢唱歌。 (2) p：明天刮风。
q：小王喜欢跳舞。则 q：明天下雨。则
p∨ q：明天或者刮风或者下雨。
p∨ q：小王喜欢唱歌或喜欢跳舞。
注,∨,的逻辑关系是明确的。即 p,q二命题中至少有一个为真则析取式为真。因而，自然语言中常用的联结词诸如：,或者 ……或者 ……”,,可能 ……可能 ……”等，都可以符号化为,∨,。但日常语言中的,或,是具有二义性的，用,或,联结的命题有时是具有相容性的，如例
1.1.6中的二例，我们称之为可兼或。而有时又具有排斥性，称为不可兼或（异或），如：
（ 1）小李明天出差去上海或去广州。
（ 2）刘昕这次考试可能是全班第一也可能是全班第二。
第 1章 命题逻辑
4.蕴涵,→”
设 p,q是任意两个命题，复合命题,如果 p，则 q”称为 p
与 q的蕴涵式，记作,p→q。 P称为蕴涵式的前件,q称为蕴涵式的后件,→称为蕴涵联结词。 p→q为假，当且仅当 p为真、
q为假。
p→q的真值表如表 1.1.4所示，它定义了一个二元真值函数：
f→,{00,01,10,11}→{0,1}，
f→(00)=1,f→(01)=1，
f→(10)=0,f→(11)=1
表 1.1.4
p q p → q
0 0 1
0 1 1
1 0 0
1 1 1
第 1章 命题逻辑
【 例 1.1.7】
(1) p：天下雨了。
q：路面湿了。则
p→q：如果天下雨，则路面湿。
(2) r：三七二十一。则
p→r：如果天下雨，则三七二十一。
第 1章 命题逻辑注 (1）逻辑中，前件 p为假时，无论后件 q是真是假，蕴涵式 p→q的真值均为 1。这与日常语言中的，特别是数学上常用的,真蕴涵真,不太一样。事实上并不矛盾，
例如某人说：,如果张三能及格，那太阳从西边升起。,说话者当然知道,张三能及格,与,太阳从西边升起,风马牛不相及，而一般人此时并没有说谎的必要，即这是真命题，它所要明确的是,张三能及格,
是假命题。
（ 2）正如前面所说，数理逻辑中的联结词是对日常语言中的联结词的一种逻辑抽象，日常语言中联结词所联结的句子之间是有一定内在联系的，但在数理逻辑中，
联结词所联结的命题可以毫无关系。如在日常语言中
,如果 ……则 ……”所联结的句子之间表现的是一种因果关系，如例 1.1.7中的（ 1）。但在数理逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫不相关的，如例
1.1.7中的（ 2）。
第 1章 命题逻辑
（ 3） p→q的逻辑关系是,p是 q的充分条件,q是 p的必要条件。
在日常语言中，特别是在数学语言中,q是 p的必要条件还有许多不同的叙述方式，如：,p仅当 q（仅当 q，则 p）,,
,只有 q才 p”,,只要 p就 q”,,除非 q，否则非 p（非 p，除非 q）,等，均可符号化成 p→q的形式。
【 例 1.1.8】 符号化下列命题：
（ 1）只要天下雨，我就回家。
（ 2）只有天下雨，我才回家。
（ 3）除非天下雨，否则我不回家。
（ 4）仅当天下雨，我才回家。
解 设 p：天下雨。 q：我回家。则（ 1）符号化为 p→q。
（ 2）、（ 3）、（ 4）均符号化为 q→p（或等价形式：
).pq
第 1章 命题逻辑
5.等价,,
设 p,q是任意两个命题，复合命题,p当且当 q”称为 p与 q
的等价式，记作,p q。
,” 称为等价联结词。 p q为真，当且仅当 p,q真值相同。 p q的真值表如表 1.1.5所示，它定义了一个二元真值函数：
f,{00,01,10,11}→{0,1}，
f (00)=1,f (01)=0，
f (10)=0,f (11)=1
表 1.1.5
p q p q
0 0 1
0 1 0
1 0 0
1 1 1
第 1章 命题逻辑
【 例 1.1.9】
(1)p,2+2=4。
q,5是素数。则
p q,2+2=4当且仅当 5是素数。
(2)p,∠ A=∠ B。
q：二角是同位角。则
p q,∠ A=∠ B当且仅当二角是同位角。
在（ 1）中的 p与 q并无内在关系，但因二者均为真，
所以 p q的真值为 1。
在（ 2）中由于相等的两角不一定是同位角，所以真值为 0。
第 1章 命题逻辑
【 例 1.1.10】 将下列自然语言形式化,
（ 1）如果天不下雨并且不刮风，我就去书店。
（ 2）小王边走边唱。
（ 3）除非 a能被 2整除，否则 a不能被 4整除。
（ 4）此时，小纲要么在学习，要么在玩游戏。
（ 5）如果天不下雨，我们去打篮球，除非班上有会。
解 （ 1）设 p：今天天下雨,q：今天天刮风,r：我去书店。则原命题符号化为：
(2)设 p：小王走路,q：小王唱歌。则原命题符号化为：
p∧ q
(3)设 p,a能被 2整除,q,a能被 4整除。则原命题符号化为：
p q r
p q q p
或第 1章 命题逻辑
（ 4）此时，小纲要么在学习，要么在玩游戏。
（ 5）如果天不下雨，我们去打篮球，除非班上有会。
(4)设 p：小刚在学习,q：小刚在玩游戏。则原命题符化为：
( ) ( ) ( ) ( )p q p q p q p q或
(5)设 p：今天天下雨,q：我们去打篮球,r：今天班上有会。则原命题符号化为：
()r p q
第 1章 命题逻辑
1.2 命题公式及分类为了用数学的方法研究命题，就必须像数学处理问题那样将命题公式化，并讨论对于这些公式的演算（推理）规则，
以期由给定的公式推导出新的命题公式来。
前面我们用 p,q,r等符号表示确定的简单命题，通常此时称它们为命题常元。而事实上，这些常元无论具体是怎样的简单命题，它们的真值均只可能是,1”或,0”。为了更广泛地应用命题演算，在研究时，我们只考虑命题的,真,与
,假,,而不考虑它的具体涵义（即只重,外延,,不顾
,内涵,）。譬如：当 p是一个真命题时,p就是一个假命题，而不管此时 p表示的是命题,三七二十一,,还是命题,今天天下雨,。这时的 p实际上就是一个简单命题的抽象，就如同数学公式中的变量 x一样，我们称其为命题变元。
命题变元 一个不确指的（抽象的）命题，以 p,q,r等表之。
第 1章 命题逻辑命题公式 由命题变元（常元）符、联结词和圆括号按一定逻辑关系联结起来的字符串。
所谓按一定的逻辑关系，即字符串的构成要求合理，
如（ p）是个合理的构成，是命，（ ∧ p）不是合理的构成，就不是命题公式，同样（ p→q） ∨ r）也不是合理的构成（括号必须成对出现），因此也不是命题
wff
（ wff=Well Formed Formulas ），也称真值函数。
第 1章 命题逻辑定义 1.2.1 合式公式的递归定义：
［ 1］单个的命题变元（或常元）是合式公式。
［ 2］如果 A是一个合式公式，则（ A）也是合式公式。
［ 3］如果 A,B均是合式公式，则（ A∧ B）、（ A∨ B）、
（ A→B）、（ A B）也都是合式公式。
［ 4］只有有限次地应用［ 1］、［ 2］、［ 3］组成的字符串才是合式公式。
例如：（（ p∨ q） ∧ r）、（（ p） ∧ (q∧ r））、（（（ p→q）
∧ （ q∨ r (( p） →r））均是合式公式。第 3式的生成过程如下：
① p ［ 1］
② q ［ 1］
③（ p→q )［ 3］①②
④ r ［ 1］
⑤（ q∨ r） ［ 3］②④
第 1章 命题逻辑
⑥ （ p ） ［ 2］①
⑦ （（ p ） →r） ［ 3］④⑥
⑧ （（ p→q） ∧ （ q∨ r） ［ 3］③⑤
⑨ （（（ p→q） ∧ （ q∨ r p ） →r）） ［ 3］⑦⑧
注 (1)A,B均代表任意的命题公式。
(2)为方便起见，公式最外层及（ A）的括号可省略。
第 1章 命题逻辑定义 1.2.2
(1)若 A是单个命题（变元或常元），则称为 0层公式。
(2)称 A为 n+1（ n≥0）层公式是指 A符合下列诸情况之一：
① A= B,B是 n层公式；
② A=B∧ C，其中 B为 i层公式,C为 j层公式，
n=max（ i,j）；
③ A=B∨ C，其中 B,C的层次同②；
④ A=B→C，其中 B,C的层次同②；
⑤ A=B C，其中 B,C的层次同②。
上面生成的第 3个式（（ p→q） ∧ （ q∨ r (( p） →r））
是 3层公式。
解释 指定命题变元代表某个具体的命题。 命题变元本身是无意义的，它仅是一个符号。同样公式本身是无意义的，只有给每个命题变元作了解释，它们才有意义。
第 1章 命题逻辑
【 例 1.2.1】 公式,A=（ p∧ q） →r。
解释 I1：假设 p：现在是白天,q：现在是晴天,r：我们能看见太阳。则
A：如果现在是白天且是晴天，则我们能看见太阳。其真值为 1。
解释 I2,假设 p,q如上,r：我们能看见星星。则 A：
如果现在是白天且是晴天，则我们能看见星星。其真值为 0。
由此可见，不同的解释可使公式有不同的真值。事实上，对于命题变元无论做什么样的解释，它都只有两种结果：或者是,真,,或者是,假,。从而由变元和联结词组成的公式所表示的复合命题，也是或为,真,,或为,假,。如前所述这才是我们所需要的。因此，欲获取命题公式的真值，并非只有,解释,一个途径，还可以通过,赋值,获得。
第 1章 命题逻辑赋值（真值指派） 对命题变元指派确定的真值。
赋值是一组由 0,1构成的数串，按字典顺序（或下标）
对应公式中的命题符。
如例 1.2.1中，公公式 A=(p∧ q） →r：
解释 I1 实际上是对变元 p,q,r赋值 111，得 A的真值为 1；
解释 I2 实际上是对变元 p,q,r赋值 110，得 A的真值为 0；
A的真值是在对 p,q,r的某种赋值下所得的真值。
定义 1.2.3 设 p1,p2,…,pn是公式 A中所包含的所有命题变元，给 p1,p2,…,pn各赋一个真值称为对 A的一个赋值，那些使 A的真值为 1的赋值称为 A的成真赋值，使 A
的真值为 0的赋值称为 A的成假赋值。
如例 1.2.1中,111是 A=（ p∧ q） →r的成真赋值,110是
A的成假赋值。根据前面对联结词的讨论知,001,011、
101,000,010也都是 A的成真赋值。
第 1章 命题逻辑问题 若公式 A含有 n（ n≥1）个命题变元，那么对 A
共有多少种不同的赋值？答 因为 n个变元赋值后形成一个 n位的二进制数，所以共有 2n个。将公式 A在所有赋值情况下的取值列成表，称为 A的真值表。构造真值表的步骤如下：
（ 1）找出命题公式中所含的所有命题变元并按下标或字典顺序给出；
（ 2）按从低到高的顺序写出各层次；
（ 3）顺序列出所有的赋值（ 2n个）；对应每个赋值，
计算命题公式各层次的真值，直到最后计算出命题公式的真值。
第 1章 命题逻辑
【 例 1.2.2】 求下列命题公式的真值表：
( 1 ) ( )
( 2 ) ( ) ( )
( 3 ) ( )
p q q
p q p q
p q r
()p q q解 (1)公式 的真值表如表 1.2.1所示。
表 1.2.1
第 1章 命题逻辑
( ) ( )p q p q(2)公式 的真值表如表 1.2.2所示。
表 1.2.2
第 1章 命题逻辑表 1.2.3
(3)公式 (p→q)∧ r的真值表如表 1.2.3所示。
第 1章 命题逻辑由上可知，有的公式在任何赋值情况下真值恒为 1，
如例 1.2.2（ 1）；有的公式在任何赋值情况下真值恒为 0，
如例 1.2.2（ 2）；有的公式某些赋值使其真值为 1，而另一些赋值使其真值为 0，因此可将公式分为如下三类：
永真式（重言式） 所有赋值均为成真赋值的公式。
永假式（矛盾式） 所有赋值均为成假赋值的公式。
可满足式 至少有一组赋值是成真赋值的公式。
由定义可知，任何不是矛盾式的公式是可满足式。
第 1章 命题逻辑
1.3 等值演算
【 例 1.3.1】 构造公式
()、,,p q p q p q p q
解 公式 ()、,,p q p q p q p q
的真值表如表 1.3.1所示。
的真值表 1.3.1
第 1章 命题逻辑由例题可见，
的真值表是完全相同的，这种情况并不是偶然的。事实上，给定 n个命题变元，按照公式的生成规则，我们可以得到无穷多个命题公式，但这无穷多个命题公式的真值表却只有有限个。如例 1.3.1，许多公式在变元的各种赋值下真值是一样的，我们称其为等值的，那么如何判断两个公式等值呢？
()、,,p q p q p q p q
第 1章 命题逻辑定义 1.3.1 设 A,B是任意两个命题公式，若等价式 A B
为重言式，则称 A与 B是等值的，记作,A B。
定理 1.3.1 A B为重言式，当且仅当 A,B具有相同的真值表。
注 （ 1）如果 A B不是重言式，则称 A与 B不等值，可记作,A B。
（ 2）,,与,=”不同,,A=B”表示二公式一样，
,A B”表示二公式真值一样，如：
p∨ q p→ q，但是
p∨ q≠p→q。
第 1章 命题逻辑
（ 3）,,与,,是两个完全不同的符号。,,
是联结词,A B是一个公式。,,不是联结词，
而是两个公式之间的关系符,A B并不是一个公式，
而只是表示 A与 B是两个真值相同的公式。
（ 4）,,的性质：
① A A（自反性）；
②若 A B，则 B A（对称性）；
③若 A B,B C，则 A C（传递性）。
第 1章 命题逻辑利用真值表我们可以证明许多等值式：
(1)双重否定律
(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)德 ·摩根律
AA
()
()
A B A B
A B A B
第 1章 命题逻辑
(7)吸收律 A∨ (A∧ B) A A∧ (A∨ B) A
(8)零律 A∨ 1 1 A∧ 0 0
(9)同一律 A∨ 0 A A∧ 1 A
(10)排中律
(11)矛盾律
(12)蕴涵等值式
(13)等价等值式
(14)假言易位
(15)等价否定等值式
(16)归谬论
1
0
( ) ( )
( ) ( )
AA
AA
A B A B
A B A B B A
A B B B
A B A B A
第 1章 命题逻辑
【 例 1.3.2】 证明等价等值式,A B (A→B)∧ (B→A)。
解 作如表 1.3.2所示的真值表。
表 1.3.2
因此,A B (A→B)∧ (B→A)。?
第 1章 命题逻辑
【 例 1.3.3】 用等值演算验证等值式
p→（ q→r p∧ q） →r。
证明
()
()
()
()
()
()
p q r
p q r
p q r
p q r
p q r
p q r
（蕴涵等值式）
（蕴涵等值式）
（结合律）
（德 ·摩根律）
（蕴涵等值式）
第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑因此，公式（（ p∨ q） ∧ q） →p是一个重言式。
等值演算在计算机硬件设计，开关理论和电子元器件中都占据重要地位。
第 1章 命题逻辑
1.4 联结词全功能集前面我们一共介绍了五个联结词：
,∧,∨,→和看到了有些公式书写形式尽管不同，但实际上是等值的。因此我们不禁要问：
（ 1）总共有多少个命题公式？
（ 2）总共有多少个联结词？
对于含有两个命题变元的公式，理论上讲可以书写出无穷多个公式，但互不等值的公式恰有 = 24 =16个。对应着 16个不同的真值表（真值表共有 22行，行上的每个记入值又可在 0、
1中任取其一，因此构成
16个真值函数 Fi（ i=0,1,…,15），其中 Fi,{00,01,10，
11}→{0,1}，如表 1,4,1所示。
222
222
第 1章 命题逻辑表 1.4.1
这里,F0和 F15正是两个常值函数：永假式 0和永真式 1； F3和 F5分别是命题变元 p和 q； F1是我们所熟知的二元真值函数 p∧ q； F7是二元真值函数 p∨ q； F9是二元真值函数 p q； F10和 F12分别是一元真值函数 q和 p； F11和 F13 分别是二元真值函数 q→p和 p→q。
第 1章 命题逻辑第 1章 命题逻辑
( 1 )
( 2 ) ( ) ( )
( 3 ) ( ) ( )
( 4 ) 0
( 5 ) 0
( 6) 1
A B B A
A B C A B C
A B C A B
AA
AA
AA
)( CA?
联结词,,有以下性质：?
第 1章 命题逻辑
3.与非,↑”
设 p,q为任意两个命题，复合命题,p与 q的否定,
称为 p,q的与非，记作,p↑q。,↑” 称为与非联结词。
p↑q为假，当且仅当 p,q均为真。
由定义可知,F14是二元真值函数 p↑q。
()p q p q
性质：（ p↑q） ↑r p↑（ q↑r）
第 1章 命题逻辑第 1章 命题逻辑
【 例 1.4.1】 将下列公式化成仅含联结词,↑”的公式。
( 1 )
( 2 )
( 3 )
Ap
B p q
C p q
解第 1章 命题逻辑
4.或非,↓”
设 p,q为任意两个命题，复合命题,p或 q的否定,
称为 p,q的或非，记作,p↓q。,↓” 称为或非联结词。
p↓q为真，当且仅当 p,q均为假。
由定义可知,F8是二元真值函数 p↓q。
p↓q （ p∨ q）
类似于,↑”,,↓” 同样不满足结合律，并类似可将例 1.4.1中的公式化成仅含联结词,↓” 的公式。
第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑
),,,(),,,(
),,,(),,,(
),,,(),,,(
),,,(,),,,(),,,()1(
.
1
2121
21
1
211
21
1
211
21121121
nn
nn
nn
nnn
pppApppA
pppApppA
pppApppA
m
pppApppApppA
A
mAmA
因此于是有由归纳假设个联结词出现。有其中形呈可能是下述情形之一连接词时，
个中有立，则个连接词时，原命题成中有假设当第 1章 命题逻辑理成立。类似可证第二式，故定
），归纳成立。证明同（
形。呈）（
归纳假设摩根定律德
（
形。呈
2
),,,(),,,(),,,(3
),,,(
),,,(),,,(
.),,,(),,,(
)),,,(),,,(
),,,(
),,,(),,,(),,,()2(
21221121
21
212211
212211
212211
21
21221121
nnn
n
nn
nn
nn
n
nnn
pppApppApppA
pppA
pppApppA
pppApppA
pppApppA
pppA
pppApppApppA
第 1章 命题逻辑定理 1.5.2 设 A*,B*分别是公式 A,B的对偶式,
如果 A B,则 A* B*。
证明 设 A,B中所有不同的变元为 p1,p2,…,
pn,则由 A B知：
A（ p1,p2,…,pn) B（ p1,p2,…,pn） 是永真式,
A（ p1,p2,…,pn） B（ p1,p2,…,pn）
亦是永真式 。
所以，
1 2 1 2(,,,) (,,,)nnA p p p B p p p
第 1章 命题逻辑本定理称为对偶原理因此有即永真式仍是时，得代以当是永真式即知由定理
),,,(),,,(
),,,(),,,(
),,,(),,,(
),,,(),,,(
),,,,(),,,(1.5.1
2121
2121
2121
2121
2121
nn
nn
nn
ii
nn
nn
pppBpppA
pppBpppA
pppBpppA
pp
pppBpppA
pppBpppA
第 1章 命题逻辑定义 1.5.2 将命题变元及其否定统称为文字 。
简单析取式 （ 基本和 ） 仅由有限个文字构成的析取式 。 简单合取式 （ 基本积 ） 仅由有限个文字构成的合取式 。
例如,p,q既是一个文字的简单析取式,又是一个文字的简单合取式 。
p∨ q,p∨ r均是有两个文字的简单析取式 。
p∧ q∧ r,p∧ q∧ q均是有三个文字的简单合取式 。
第 1章 命题逻辑第 1章 命题逻辑
【 例 1.5.1】 判断下列各式是析取范式还是合取范式 。
（ 1） p
（ 2） p∨ q
（ 3） p∧ q∧ r
（ 4） p∨ （ q∧ r） ∨ r
（ 5） p∧ （ p∨ q） ∧ （ p∨ q∨ r） ∧ q
解 (1）既是一个简单析取式又是一个简单合取式,是只有一个简单析取式的合取范式,也是只有一个简单合取式的析取范式。 （ 2）是有两个简单合取式的析取范式,也是只有一个简单析取式的合取范式。 （ 3）是有三个简单析取式的合取范式，
也是只有一个简单合取式的析取范式。 （ 4）是有三个简单合取式的析取范式。 （ 5）是有四个简单析取式的合取范式。
第 1章 命题逻辑性质：
(1) 一个文字既是一析取范式又是一合取范式 。
(2) 一个析取范式为矛盾式,当且仅当它的每个简单合取式是矛盾式 。
(3) 一个合取范式为重言式,当且仅当它的每个简单析取式是重言式 。
例如,A=（ p∧ p∧ q） ∨ （ p∧ q∧ q） 是矛盾式 。
A=（ p∨ p∨ q） ∧ （ p∨ q∨ q） ∧ （ q∨ r∨ r）
是重言式 。
第 1章 命题逻辑定理 1.5.3 任一命题公式都存在着与之等值的析取范式,任一命题公式都存在着与之等值的合取范式 。
证明 对于任一公式,可用下面的方法构造出与其等值的范式：
（ 1） 利用等值式
A B (A→B） ∧ （ B→A）
A→B A∨ B
使公式中仅含联结词,∧,∨ 。
（ 2） 利用德 ·摩根律和双重否定律
（ A∨ B） A∧ B
（ A∧ B） A∨ B
A A
将否定符 (移至命题变元符前,并去掉多余的否定符 ),
第 1章 命题逻辑
（ 3） 利用分配律
A∧ （ B∨ C) （ A∧ B） ∨ （ A∧ C）
A∨ （ B∧ C） （ A∨ B） ∧ （ A∨ C）
所得即与原公式等值的范式。
第 1章 命题逻辑第 1章 命题逻辑
（分配律）
（ 分配律
（ 矛盾式
（ 同一律第 1章 命题逻辑
【 例 1.5.3】 求例 1.5.2中公式的合取范式 。
解 由例 1.5.2第 4步原式
(( ( ) ) ) ( )
( ) ( ) ( )
( ) ( ) ( )
p q r p p r
p q p r p p r
p q p r p r
（分配律）
--合取范式 （ 幂等律,交换律 ）
第 1章 命题逻辑定义 1.5.3 对于公式 A：
极小项 包含 A中所有命题变元或其否定一次且仅一次的简单合取式；
极大项 包含 A中所有命题变元或其否定一次且仅一次的简单析取式 。
注 极小项或极大项中各文字要求按角标顺序或字典顺序排列 。
第 1章 命题逻辑第 1章 命题逻辑表 1.5.1
由真值表可看出,对于 p,q的任一组赋值,有且仅有一个极小项的真值为 1,即极小项之间是不等值的,4个真值赋值与 4个极小项值之间有一一对应关系。 我们用 mi表示在十进制为 i的赋值下真值为 1的极小项。
第 1章 命题逻辑定义 1.5.4 对于公式 A：
主析取范式 与 A等值的由极小项构成的析取范式；
主合取范式 与 A等值的由极大项构成的合取范式 。
由定理 1.5.3知,任一公式的析 （ 合 ） 取范式总是存在的,求主范式只需在求范式的基础上将每个简单合 （ 析 ） 取式化成极小 （ 大 ） 项 。
第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑定理 1.5.4 任何命题公式的主析取范式存在且唯一 。
证明 由析取范式的存在性知主析取范式的存在性成立 。 下面证唯一性：
设任一命题公式 A有两个主析取范式 B和 C,则因为 A B,A C,所以 B C。
若 B,C是 A的 （ 在不计极小项的顺序的情况下 ）
不相等的主析取范式 （ B≠C）,则必存在某个极小项
mi,mi只存在于 B,C之一中 。
不妨设 mi在 B中,而不在 C中,因此 i之二进制表示是 B的成真赋值,而对于 C则为成假赋值,这与
B C矛盾,故 B=C。
第 1章 命题逻辑第 1章 命题逻辑结论 （ 主析取范式的用途 ）,
(1) 重言式的主析取范式包含公式的全部 2n个极小项 。
(2)（ 规定 ） 矛盾式的主析取范式为 0。
(3) 二等值的公式必有相同的主析取范式 （ 不计极小项的顺序 ） 。
(4) 不列真值表,由主析取范式可得公式的成真,
成假赋值 。
(5) 仅由真值表,可得公式的表达式 （ 主析取范式形式 ） 。
(6) 解决应用问题 。
前两条可用来判断公式的类型,第三条判断两个公式的等值,由此前面提出的三个问题得到了解决第 1章 命题逻辑第 1章 命题逻辑
【 例 1.5.9】 已知命题公式 A（ p,q,r） 的成真赋值为 010,101,110,求 A。
解 A m2∨ m5∨ m6
（ p∧ q∧ r） ∨ （ p∨ q ∧ r） ∨ （ p∧ q∧ r）
第 1章 命题逻辑
【 例 1.5.10】 四人比赛,三人估计成绩。 甲说,"
A第一,B第二 ",乙说,"C第二,D第四 ",丙说,"A第二,D第四 "。 结果每人都说对了一半,假设无并列名次，
问 A,B,C,D 的实际名次如何？
解 设 p,A 第一,q,B 第二 。
（ 甲说 ） （ p∧ q） ∨ （ p∧ q） 1
r,C 第二,s,D 第四 。
（ 乙说 ） （ r∧ s） ∨ （ r∧ s） 1
t,A 第二,s,D 第四。
（ 丙说 ） （ s∧ t） ∨ （ s∧ t） 1
第 1章 命题逻辑第 1章 命题逻辑对应 p,q的每一组赋值,极大项的真值有且仅有一个为 0,极大项与其成假赋值有着一一对应关系,我们用 Mi表示在十进制为 i的赋值下真值为 0的极大项。 因此,求一个公式的主合取范式,只需知道该公式的成假赋值，并将对应着这个赋值也成假的那些极大项合取起来，即得该公式的主合取范式。
第 1章 命题逻辑
【 例 1.5.11】 求公式 （ p→（ p∨ r）） ∧ （ q p）
的主合取范式 。
解 由例 1.5.7已知此公式的成假赋值为 010,011，
100,101,可得主合取范式为
2 3 4 5
( ( )) ( )
( 2,3,4,5 )
( ) ( ) ( ) ( )
p p r q p
M M M M
P q r p q r p q r p q r
第 1章 命题逻辑同样,利用等值演算法也可得主合取范式：
( ( ) ) ( )
( ) ( ) ( )
1 ( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
p p r q p
p p r q p 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
（ 等价等值式,蕴涵等值式 ）
（ 排中律,零律,交换律 ）
（同一律,分配律）
--主合取范式 （交换律）
第 1章 命题逻辑注意到,对于任一公式,在它的 2n个赋值中,非
0即 1,因此其主析取范式中的极小项和其主合取范式中的极大项的个数之和恰为 2n,且其下标不会相同 。
故当我们知道了一个公式的所有成真赋值时,也就知道了它的所有成假赋值 。 亦即,知道了主析取范式,
相应地也就得到了主合取范式,反之亦然 。
第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑
1.6 推 理 理 论推理是 " "的思维过程 。 在命题逻辑中,
前提是已知的命题公式,结论是从前提出发应用推理规则推出的命题公式 。 在传统数学中定理的证明均是由前提 （ 已知条件,全是真命题 ） 推出结论 （ 亦全是真命题 ）,这样的结论称为合法结论 。
数理逻辑有所不同,它着重研究的是推理的过程,这种过程称为演绎或形式证明。 在过程中使用的推理规则必须是公认的且要明确列出,而对于作为前提和结论的命题并不一定要求它们全是真命题,这样的结论称为有效结论。
第 1章 命题逻辑定理 1.6.1 称蕴涵式（ A1∧ A2∧ … ∧ An） →B为推理的形式结构,A1,A2,…,An为推理的前提,B为推理的结论。 若（ A1∧ A2∧ … ∧ An） →B是重言式，
则称从前提 A1,A2,…,An推出结论 B的推理正确，
B是 A1,A2,…,An的有效结论或逻辑结论。 记作：
（ A1∧ A2∧ … ∧ An） B （ A1,A2,…,An B)
否则称推理不正确,或 B不是前提 A1,A2,…,An
的有效结论 。
具有自反性,对称性,传递性 。
第 1章 命题逻辑
【 例 1.6.1】 验证下面推理是否正确：
一个数是复数,仅当它是实数或是虚数,一个数既不是实数也不是虚数,因此它不是复数 。
证明 设 p,它是复数,q,它是实数,r,它是虚数 。
推理的形式结构为：
（（ p→（ q∨ r）） ∧ （ q∧ r）） → p。
（ 1） 真值表法 (真值表如表 1.6.1所示 )。
第 1章 命题逻辑表 1.6.1
因为只有第一行前提,结论均为真,所以推理正确。
第 1章 命题逻辑第 1章 命题逻辑
（ 3） 主析取范式法 （ 略 ） 。
以上的证明方法,当形式结构比较复杂,特别是所含命题变元较多时,一般是很不方便的 。 下面介绍构造证明法,这种方法必须在给定的规则下进行,
其中有些规则建立在推理定律 （ 重言蕴涵式 ） 的基础之上 。
第 1章 命题逻辑推理定律：
第 1章 命题逻辑推理规则：
前提引入规则 在证明的任何步骤上,都可以引入前提 。 结论引入规则 在证明的任何步骤上,所得到的结论均可作后续证明的前提加以引用 。
置换规则 在证明的任何步骤上,命题公式中的任何子公式都可以用与之等值的公式置换 。 另外,由前面的 8个推理定律可得下面 8个推理规则,（ 这里 A1，
A2,…,An B表示 B是 A1,A2,…,An的逻辑结论 。 ）
第 1章 命题逻辑
第 1章 命题逻辑构造证明法：
构造证明可以看作公式的序列,其中的每个公式都是按照事先规定的规则得到的,且需将所用的规则在公式后写明,该序列的最后一个公式正是所要证明的结论 。
第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑例 1.6.4 构造证明,找出下列推理的有效结论 。
如果我考试通过了,那么我很快乐 。 如果我快乐,那么阳光灿烂 。 现在阳光不灿烂且天很暖 。 因此我考试没通过 。
解 设 p,我考试通过了,q,我很快乐,r,阳光灿烂,
s,天很暖 。
前提,p→q,q→r,结论,prs
（ 1） p→q 前提引入
（ 2） q→r 前提引入
（ 3） p→r （ 1） （ 2） 假言三段论
（ 4） r∧ s 前提引入
（ 5） r （ 4） 化简
（ 6） p （ 5） （ 3） 拒取式所以有效结论是,我考试没通过。
第 1章 命题逻辑第 1章 命题逻辑
【 例 1.6.5】 如果小张去看电影,则当小王去看电影时,小李也去 。 小赵不去看电影或小张去看电影 。
小王去看电影 。 所以当小赵去看电影时,小李也去 。
解 设 p,小张去看电影,q,小王去看电影,r：
小李去看电影,s,小赵去看电影 。
第 1章 命题逻辑第 1章 命题逻辑定义 1.6.1 如果 A1,A2,…,An均为命题公式,
A1∧ A2∧ … ∧ An 0,则称 A1,A2,…,An不相容,
否则称相容 。
第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑
【 例 1.6.7】 证明,p q,q→r,r∨ s,p→s,s不相容 。
证明 （ 1） p→s 前提引入 （ 2） s 前提引入
（ 3） p （ 1） （ 2） 拒取式
（ 4） p q 前提引入
（ 5） （ p→q） ∧ （ q→p） （ 4） 置换
（ 6） p→q （ 5） 化简
（ 7） q （ 3） （ 6） 假言推理
（ 8） q→r 前提引入
（ 9） r （ 7） （ 8） 假言推理
（ 10） r∨ s 前提引入
（ 11） r （ 2） （ 10） 析取三段论
（ 12） r∧ r （ 9） （ 11） 合取式引入,故诸命题不相容 。
第 1章 命题逻辑
1.7 命题演算的自然推理形式系统 N
1,形式系统的基本概念通过前面的讨论,我们看到,永真式是命题逻辑推理中一个非常基本和非常重要的概念,这些可以有无穷多种表达形式的永真式,它们都是逻辑推理规律的反映 。 弄清这些永真式,对于掌握命题逻辑有着极为重要的意义 。 为了系统地研究它们,就需要把所有的永真式包括在一个系统内,作为一个整体来研究,
这样的系统应当是一个形式系统,也只有形式系统,
才能进行充分的研究,从而掌握全部规律 。
第 1章 命题逻辑在形式系统中,原始概念和用于推演的逻辑规则没有任何直觉意义,甚至没有任何预先设定的涵义,
它们无非是一些约定,约定怎样用符号 （ 符号语言 ）
来表达原始概念和用于推演的逻辑规则 。 这一过程一旦结束,这个形式系统便和一切实际意义,甚至逻辑都毫不相干,留下来的只是符号串与符号串之间的关系,根据这种关系,可以进行符号串之间的变换 。 在形式系统中,决定一切的是符号串与符号串之间的关系,合法符号串的识别,系统内的推演都可以根据合法符号串的形成规则和推理规则 --符号串之间的关系机械地完成,不需要比认读和改写符号串更多的知识,
甚至不需要逻辑 。 很清楚,只有这样的形式系统,才是本质上只能做符号变换的计算机可以接受的 。
第 1章 命题逻辑当然,形式系统的提出往往是有客观背景的,这是因为现实世界的某些对象及其性质需要精确地描述 。
但是,当形式系统一旦建成,它便应当是超脱客观背景的,它描述的对象可以不限于原来考虑的那些对象,
而是与它们有着共同结构的相当广泛的一类对象 。
形式系统一般由下面几部分组成：
（ 1） 字母表 。 字母表由不加定义而采用的符号组成,字母表提供形式系统可以使用的符号 。
第 1章 命题逻辑
（ 2） 字母表上符号串集的一个子集 Form。 Form
中的元素称为公式,Form提供形式系统可以使用的符号串。
（ 3） Form的一个子集是 Axiom。 Axiom中的元素称为公理,Axiom提供形式系统一开始便要接受而不加证明的定理 。
第 1章 命题逻辑
(4) 推理规则集 Rule。 Rule中的元素称为推理规则,
Rule规定了公式间的转换关系 。
对于一个形式系统,Axiom和 Rule均有可能是空集 。
如当 Axiom和 Rule均为空集时,称这样的形式系统仅仅是一个语言生成系统 。 在数理逻辑中,如果 Axiom不是空集时,称这样的系统为公理系统； Axiom如果是空集时,称这样的推理系统为自然推理系统 。
第 1章 命题逻辑在形式系统中进行推理时,涉及的仅仅是公式的语法,并不涉及公式本身的意义是什么,推理过程仅被看作公式按照推理规则进行变形的过程 。 但是,我们可以对公式进行解释,使公式变成具体涵义的语句,
从而对某一特定的客体范畴和特定的性质进行描述,
用来讨论一个具体的实际系统,这时,有两个具体的问题必须解决：
(1) 形式系统中正确推理出来的公式 --定理在所讨论的具体实际系统中是否永真 。
(2) 在所讨论的具体实际系统中永真的语句是否均为形式系统内的定理 。 这是系统的可靠性和完备性问题 。
第 1章 命题逻辑
2,命题演算的自然推理形式系统 N
1) 字母表
(1) 命题符：
p,q,r,p1,q1,r1,…,pi,qi,ri,… ；
(2) 联结词符：
,∧,∨,→，
(3) 括号,（,） 。
其中的命题符构成的集合为可数集 。
第 1章 命题逻辑定义 1.7.1 字母表上的一个符号串是 FN中的元素,
当且仅当这个符号串能由 (1)～ (3)推导出：
(1) 单个的命题符是 FN中的元素 。
(2) 如果 A∈ FN,则
（ A） ∈ FN。
(3) 如果 A,B∈ FN,则 （ A∧ B）,（ A∨ B）,
（ A→B）,（ A B） ∈ FN。
在上面的定义中,我们使用了 A,B来表示任意的公式，
而不是某个具体的公式,因而这样的符号是元语言符号。
以下我们用大写英文字母：
A,B,C,A1,B1,C1,…,
Ai,Bi,Ci,…
来表示任意公式。
第 1章 命题逻辑
3) 推理规则
N系统中有 11条推理规则,下面以模式的形式给出：
·包含律 （ ∈ ）,如果 A∈ Γ,则 Γ├A。
·增加前提律 （ +）,
如果 Γ├A,则 Γ,Γ′├A。 （ Γ′ FN） 。
· 消去律 （ -）,
如果 Γ,A├B,Γ,A├ B,则 Γ├A。
第 1章 命题逻辑
·→消去律 （ →+）,如果 Γ├A→B,Γ├A,则 Γ├B。
·→引入律 （ →-）,如果 Γ,A├B,则 Γ├A→B。
·∧ 消去律 （ ∧ -）,如果 Γ├A∧ B,则 Γ├A,Γ├B。
·∧ 引入律 （ ∧ +）,如果 Γ├A,Γ├B,则 Γ├A(B。
·∨ 消去律 （ ∨ -）,如果 Γ,A├C,Γ,B├C,则 Γ,A∨ B├C。
·∨ 引入律 （ ∨ +）,如果 Γ├A,则 Γ├A(B,Γ├B∨ A。
· 消去律 （ -）,如果 Γ├A B,则 Γ├A→B,Γ├B→A。
· 引入律 （ +）,如果 Γ├A→B,Γ├B→A,则 Γ├A B 。
第 1章 命题逻辑定义 1.7.2
A是在 N系统中由 Γ形式可证明的,记作,Γ├A，
当且仅当 Γ├A能由有限次使用 N系统中的推理规则生成 。
【 例 1.7.1】 证明,A→B,B→C├A→C。
证明
（ 1） A→B├A→B （ ∈ ）
（ 2） A→B,B→C,A├ A→B （ +）,（ 1）
（ 3） A├A （ ∈ ）
（ 4） A→B,B→C,A├A （ +）,（ 3）
第 1章 命题逻辑
（ 5） A→B,B→C,A├B （ →-）,（ 2）,（ 4）
（ 6） B→C├B→C （ ∈ ）
（ 7） A→B,B→C,A├B→C （ +）,（ 6）
（ 8） A→B,B→C,A├C （ →-）,（ 5）,（ 7）
（ 9） A→B,B→C├A→C （ →+）,（ 8）
第 1章 命题逻辑
【 例 1.7.2】 证明,A├A。
此模式称为双 (消去律 （ 简称 -） 。
证明
（ 1） A,A├ A （ ∈ ）
（ 2） A,A├ A （ ∈ ）
（ 3） A├A （ -）,（ 1）,（ 2）
第 1章 命题逻辑
【 例 1.7.3】 证明,如果
Γ,A├ B,Γ,A├B,则 Γ├ A。
此模式称为 引入律 （ 简称 +） 。
证明
（ 1） Γ,A├ B （ 前提 ）
（ 2） Γ,A├B （ 前提 ）
（ 3） Γ├A→ B （ →+）,（ 1）
第 1章 命题逻辑
（ 4） Γ,A├A→ B （ +）,（ 3）
（ 5） Γ├A→B （ →+）,（ 2）
（ 6） Γ,A├A→B （ +）,（ 5）
（ 7） A├A （ -）
（ 8） Γ,A├A （ +）,（ 7）
（ 9） Γ,A├ B （ →-）,（ 4），（ 8）
（ 10） Γ,A├B （ →-）,（ 6）,（ 8）
（ 11） Γ├ A （ -）,（ 9）,（ 10)
– 例 1.7.4 证明,Γ├B,B├A,则 Γ├A。
– 此模式称为传递律 （ Tr ） 。
– 证明
– （ 1） Γ├B （ 前提 ）
– （ 2） B├A （ 前提 ）
第 1章 命题逻辑
4,N中推理模式的一些性质
(1) A和 B是形式等值的 （ 简称等值的 ）,记作：
A├┤B,当且仅当 A├B,B┤A。
(2) 设 A,B,C是公式,B是 A的子串,将 A中的
B用 C置换 （ 不一定全部置换 ） 后得到的公式 A′,如果
B├┤C,则 A├┤A′。
(3) 设 A和 A*互为对偶式,则有 A*├┤ A。
(4) 设 A,B为有对偶的公式,其对偶式分别为 A*，
B*,如果 A├┤B,则 A*├┤B*。
第 1章 命题逻辑
【 例 1.7.5】 证明,A→B├┤ A∨ B。
证明 先证 A→B├ A∨ B
（ 1） A├ A （ ∈ ）
（ 2） A├ A∨ B （ ∨ +）,（ 1）
（ 3） A→B,（ A∨ B）,A├ A(B （ +）,（ 2）
（ 4） A→B,（ A∨ B）,A├ （ A∨ B） （ ∈ ）
（ 5） A→B,（ A∨ B） ├A （ -）,（ 4）
（ 6） A→B,（ A∨ B） ├ A→B （ ∈ ）
（ 7） A→B,（ A∨ B） ├ B （ →-）,（ 6）
（ 8） A→B,（ A∨ B） ├ A∨ B （ ∨ +）,（ 7）
（ 9） A→B,（ A∨ B） ├ （ A∨ B） （ ∈ ）
（ 10） A→B├ A∨ B （ -）,（ 8）,（ 9）
第 1章 命题逻辑再证 A∨ B├ A→B。
（ 1） A,B,A├ A （ ∈ ）
（ 2） A,B,A├A （ ∈ ）
（ 3） A,A├B （ -）,（ 1）,（ 2）
（ 4） A├A→B （ →+）,（ 3）
（ 5） B,A├B （ ∈ ）
（ 6） B├A→B （ →+）,（ 5）
（ 7） A∨ B├A→B （ ∨ -）,（ 4）,（ 6）
故 A→B├┤ A∨ B。
第 1章 命题逻辑
5,几个定理
(1) 可靠性定理,设 Γ FN,A∈ FN,如果 Γ├A，
则 Γ A。
(2) 完备性定理,设 Γ FN,A∈ FN,如果 Γ A，
则 Γ├A。
证明略 。
第 1章 命题逻辑第 1章 命题逻辑
【 例 1.8.2】 某研究所有赵,钱,孙,李,周五位高级工程师 。 现需派一些人出国考察,由各方面的限制,此次选派必须满足下列条件：
（ 1） 若赵去,则钱也去 。
（ 2） 李,周两人中必有人去 。
（ 3） 钱,孙两人中去且仅去一人 。
（ 4） 孙,李两人同去或都不去 。
（ 5） 若周去,则赵,钱也同去 。 试分析领导的选派方案 。
分析 五个人每个人都可以去,这就得到五个原子命题 。 满足条件,即要使由所给条件确定的命题公式同时为真,方法是取五个命题公式的合取式 F,再化成主析取范式,这样每个极小项就是一个选派方案,符合题意的方案即为所求 。
第 1章 命题逻辑第 1章 命题逻辑
【 例 1.8.3】 有一种保密锁的控制电路,锁上共有三个键 A,B,C。 当三键同时按下,或只有 A,B两键按下,或只有 A,B其中之一按下时,锁被打开 。
以 G表示锁被打开,试写出 G的逻辑表达式 。
分析 因为当且仅当开锁条件成立时,G为真 。 所以,令 A,B,C分别表示命题 "A,B,C键被按下 "，
依据开锁条件,寻求出 G的成真赋值,即可解决问题 。
解 列出开锁条件的真值表,如表 1.8.1所示 。
第 1章 命题逻辑表 1.8.1
A B C G
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
0
1
0
1
0
1
1
第 1章 命题逻辑第 1章 命题逻辑
【 例 1.8.4】 验证下列推理的正确性 。
如果 6是偶数,则 7被 2除不尽 。 或 5不是素数,或
7被 2除尽 。 5是素数 。 因此,6是奇数 。
分析 显然推理的结论是个假命题,但不能由此就认定推理不正确 。 逻辑推理关心的是推理的过程是否合乎规则,并不要求前提均为真,当前题中有假命题时,正确的推理完全可推出错误的结论,因此逻辑推理的结论只是有效结论 。
第 1章 命题逻辑解 设 p,6是偶数,q,7被 2除尽,r,5是素数 。
前提,p→ q,r∨ q,r
结论,p
（ 1） r∨ q 前提引入
（ 2） r 前提引入
（ 3） q （ 1） （ 2） 析取三段论
（ 4） p→ q 前提引入
（ 5） p （ 4） （ 5） 拒取式所以推理正确。
如果 6是偶数,则 7被 2除不尽。 或 5不是素数,或 7被 2除尽。 5
是素数。 因此,6是奇数。
第 1章 命题逻辑
【 例 1.8.5】 公安人员审一件盗窃案 。 已知：
（ 1） 甲或乙盗窃了电脑 。
（ 2） 若甲盗窃了电脑,则作案时间不能发生在午夜前 。
（ 3） 若乙证词正确,则在午夜时屋里灯光未灭 。
（ 4） 若乙证词不正确,则作案时间发生在午夜前 。
（ 5） 午夜时屋里灯光灭了 。
问,谁是盗窃犯？
解 设 p,甲盗窃了电脑,q,乙盗窃了电脑,r：
作案时间发生在午夜前,s,乙证词正确,t,午夜时屋里灯光灭了 。
前提,p∨ q,p→ r,s→ t,s→r,t
第 1章 命题逻辑第 1章 命题逻辑习 题 一
1,指出下述语句哪些是命题,哪些不是命题,若是命题,
指出其真值 。
（ 1） 离散数学是计算机科学系的一门必修课 。
（ 2） 你上网了吗？
（ 3） 不存在偶素数 。
（ 4） 明天我们去郊游 。
第 1章 命题逻辑
（ 5） x≤6。
（ 6） 我们要努力学习 。
（ 7） 如果太阳从西方升起,你就可以长生不老 。
（ 8） 如果太阳从东方升起,你就可以长生不老 。
（ 9）这个理发师给一切不自己理发的人理发。
第 1章 命题逻辑
2,将下列命题符号化 。
（ 1） 逻辑不是枯燥无味的 。
（ 2） 小李边读书边听音乐 。
（ 3） 现在没下雨,可也没出太阳,是阴天 。
（ 4） 鱼和熊掌不可兼得 。
（ 5） 小王要么住在 203室要么住在 205室 。
（ 6） 小刘总是在图书馆自习,除非他病了或图书馆不开门 。
（ 7） 他只要用功,成绩就会好 。
（ 8） 他只有用功,成绩才会好 。
（ 9） 如果你来了,那么他唱不唱歌将看你是否伴奏而定 。
第 1章 命题逻辑
3,求下列公式在赋值 0011下的真值 。
（ 1） p∨ （ q∧ r） →s
（ 2） （ p r） ∧ （ ﹁ s∨ q）
（ 3） （ p∧ （ q∨ r）） ∨ （（ p∨ q） ∧ r∧ s）
（ 4） （ q∨ ﹁ p） →（ ﹁ r∨ s）
第 1章 命题逻辑
4,用真值表判断下列公式的类型 。
（ 1） （ p→（ q→p））
（ 2） ﹁ （ p→q） ∧ ﹁ q
（ 3） （（ p→q） →（ p→r）） →（ p→（ q→r））
（ 4） ﹁ （ p∨ （ q∧ r）） （（ p∨ q） ∧ （ p∨ r））?
第 1章 命题逻辑
5,证明下列等值式 。
（ 1） （ p→r） ∧ （ q→r） （ p∨ q） →r
（ 2） p→（ q→r） q→（ p→r）
（ 3） （ p∧ q） ∨ （ ﹁ p∧ r） ∨ （ q∧ r） （ p∧ q） ∨
（ ﹁ p∧ r）
（ 4） ﹁ （ p q） （ p∨ q） ∧ ﹁ （ p∧ q）
（ 5） p→（ q∨ r） ﹁ r→（ p→q）
第 1章 命题逻辑
6,设 A,B,C是任意命题公式：
（ 1） 若 A∨ B A∨ C,则 B C成立吗？
（ 2） 若 A∧ B A∧ C,则 B C成立吗？
（ 3） 若 ﹁ A ﹁ B,则 A B成立吗？
7,证明 {﹁,→}是联结词极小全功能集 。
8,将下列公式化为仅出现联结词 ﹁,→的公式 。
（ 1） p∨ （ q∧ ﹁ r）
（ 2） p （ q→（ p∨ r））
（ 3） p∧ q∧ r
第 1章 命题逻辑
9,将下列公式化为仅出现联结词 ﹁,∧ 的等价公式 。
（ 1） ﹁ r∨ q∨ （ p→q）
（ 2） p→（ q→r）
（ 3） p q
10,将下列公式化为仅出现联结词 ﹁,∨ 的等价公式 。
（ 1） ﹁ p∧ ﹁ q∧ （ ﹁ r→p）
（ 2） ﹁ p q
（ 3） p→（ q∨ ﹁ r）） ∧ ﹁ p∧ q
第 1章 命题逻辑
11,将下列公式化为仅出现联结词 ↑的等价公式,
再将其化成仅出现联结词 ↓的等价公式 。
（ 1） p→（ ﹁ p→q）
（ 2） （ p∨ ﹁ q） ∧ r
12,公式 A=（ ﹁ （ p↓q） ∧ r） ↑q,写出 A的对偶式
A*,并将 A和 A*化成仅含联结词 ﹁,∧,∨ 的等价公式 。
第 1章 命题逻辑
13,A,B,C,D 四人参加拳击比赛,三个观众猜测比赛结果 。
"C第一,B第二 。 "
乙说,"C第二,D 第三 。 "
丙说,"A第二,D第四 。 "
比赛结果显示,他们每个人均猜对了一半,并且没有并列名次 。 问实际名次怎样排列？
第 1章 命题逻辑
14,求下列公式的主析取范式和主合取范式,并指出它们的成真赋值 。
（ 1） （ ﹁ p∨ ﹁ q） →（ p ﹁ q）
（ 2） q∧ （ p∨ ﹁ q）
（ 3） p∨ （ ﹁ p→（ q∨ （ ﹁ q→r）））
（ 4） （ p→（ q∧ r）） ∧ （ ﹁ p→（ ﹁ q∧ ﹁ r））
（ 5） p→（ p∧ （ q→r））
（ 6） ﹁ （ p→q） ∨ p∨ r
（ 7） （ p→q） →r
（ 8） （ p∨ q） ∧ （ p→r） ∧ （ q→r）
第 1章 命题逻辑
15,P,Q,R,S四个字母,从中取两个字母,
但要同时满足三个条件：
a：如果取 P,则 R和 S要取一个；
b,Q,R不能同时取；
c：取 R则不能取 S。
问有几种取法？ 如何取？
第 1章 命题逻辑
16,甲,乙,丙,丁四个人有且仅有两个人参加比赛,
下列四个条件均要满足：
（ 1） 甲和乙只有一人参加；
（ 2） 丙参加,则丁必参加；
（ 3） 乙和丁至多有一人参加；
（ 4） 丁不参加,甲也不会参加 。
问哪两个人参加了比赛？
第 1章 命题逻辑
17,一个排队线路,输入为 A,B,C,其输出分别为 FA,FB,FC,在此线路中,在同一时间只能有一个信号通过,若同时有两个或两个以上信号申请输出时,则按 A,B,C的顺序输出,写出 FA,FB,FC的表达式 。
18,用两种方法 （ 真值表法和主析取范式法 ） 证明下面推理不正确 。 如果 a,b两数之积是负数,则 a，
b之中恰有一个是负数 。 a,b两数之积不是负数 。 所以
a,b中无负数 。
第 1章 命题逻辑
19,用构造证明法证明下列推理的正确性 。
（ 1） 前提 ﹁ （ p∧ ﹁ q）,﹁ q∨ r,﹁ r
结论 ﹁ p
（ 2） 前提 p∧ q,（ p q） →（ r∨ s）
结论 r∨ s
（ 3） 前提 q→p,q s,s r,r∧ t
结论 p∧ q
第 1章 命题逻辑
（ 4） 前提 p→（ q→r）,（ r∧ s） →t,﹁ u→（ s∧ ﹁ t）
结论 p→（ q→u）
（ 5） 前提 （ p∨ q） →（ u∧ s）,（ s∨ t） →r
结论 p→r
（ 6） 前提 p→（ q→r）,s→p,q
结论 s→r
（ 7） 前提 p→q
结论 p→（ p∧ q）
（ 8） 前提 s→﹁ q,s∨ r,﹁ r,﹁ p q
结论 p
第 1章 命题逻辑
20,用附加前提法推证 19题中的 （ 4）,（ 5）,
（ 6）,（ 7） 。
21,用归缪法推证 19题中的 （ 1）,（ 3）,（ 7）,
（ 8） 。
22,将下列论证用命题逻辑符号表示,然后求证逻辑推证是否成立 。
（ 1） 如果天热则蝉叫,如果蝉叫则小王不睡觉,小王游泳或睡觉,所以如果天热则小王游泳 。
（ 2） 或者逻辑难学,或者有少数学生不喜欢它,
如果数学容易学,那逻辑并不难学 。 因此,如有许多学生喜欢逻辑,,那么数学并不难学 。
第 1章 命题逻辑
（ 3） 如果小张来,则小王和小李中恰有一人来 。
如果小王来,则小赵就不来 。 所以,如果小赵来了但小李没来,则小张也没来 。
（ 4） 有甲,乙,丙,丁参加乒乓球比赛 。 如果甲第三,则当乙第二时,丙第四 。 或者丁不是第一,或者甲第三 。 事实上,乙第二 。 因此,如果丁第一,那么丙第四 。
第 1章 命题逻辑
23,判断下面推理的结论 。
若公司拒绝增加工资,则罢工不会停止,除非罢工超过 3个月且公司经理辞职 。 公司拒绝增加工资 。 罢工又刚刚开始 。 罢工是否停止？
1.1 命题符号化及联结词
1.2 命题公式及分类
1.3 等值演算
1.4 联结词全功能集
1.5 对偶与范式
1.6 推理理论
1.7 命题演算的自然推理形式系统 N
1.8 例题选解习 题 一第 1章 命题逻辑
1.1 命题符号化及联结词任何基于命题分析的逻辑称为命题逻辑。命题是研究思维规律的科学中的一项基本要素，它是一个判断的语言表达。
命题能唯一判断真假的陈述句。
这种陈述句的判断只有两种可能，一种是正确的判断，
一种是错误的判断。如果某个陈述句判断为真（与人们公认的客观事实相符），则我们称其为一真命题，并说此命题的真值为真，否则称为假命题，并说此命题的真值为假。
第 1章 命题逻辑
【 例 1.1.1】 下述各句均为命题：
（ 1） 4是偶数。（ 2）煤是白色的。
（ 3）,几何原本,的作者是欧几里德。
（ 4） 2190年人类将移居火星。
（ 5）地球外也有生命存在。
上述命题中（ 1）、（ 3）是真命题，（ 2）是假命题，其中的
（ 3）可能有人说不出它的真假，但客观上能判断真假。（ 4）
的结果目前谁也不知道，但到了时候则真假可辨，即其真值是客观存在的，因而是命题。同样，（ 5）的真值也是客观存在的，只是我们地球人尚不知道而已，随着科学技术的发展，其真值是可以知道的，因而也是命题。
第 1章 命题逻辑
【 例 1.1.2】 下列语句不是命题：
（ 1）你好吗？
（ 2）好棒啊！
（ 3）请勿吸烟。
（ 4） x＞ 3。
（ 5）我正在说谎。
（ 1）、（ 2）、（ 3）均不是陈述句，因而不是命题。（ 4）是陈述句，但它的真假取决于变量 x的取值，
例如取 x为 4时其值为真，取 x为 2时其值为假，即其真值不唯一，因此不是命题。（ 5）也是陈述句，但它是悖论，因而也不是命题。
第 1章 命题逻辑从上面讨论可以看出，判断一个语句是否是命题的关键是：
(1)语句必须是陈述句。
(2)陈述句必须具有唯一的真值。要注意两点：
①一个陈述句在客观上能判断真假，而不受人的知识范围的限制。
②一个陈述句暂时不能确定真值，但到了一定时候就可以确定，与一个陈述句的真值不能唯一确定是不同的。以上所讨论的命题均是一些简单陈述句。在语言学中称为简单句，其结构均具有,主语 +谓语,的形式，在数理逻辑中，我们将这种由简单句构成的命题称为简单命题，或称为原子命题，用 p,q、
r,pi,qi,ri等符号表示（必要时亦可用其它小写的英文字母表示）。如：
p,4是偶数。
q：煤是白的。
r：,几何原本,的作者是欧几里德。
第 1章 命题逻辑
【 例 1.1.3】 下列命题不是简单命题：
（ 1） 4是偶数且是 2的倍数。
（ 2）北京不是个小城市。
（ 3）小王或小李考试得第一。
（ 4）如果你努力，则你能成功。
（ 5）三角形是等边三角形，当且仅当三内角相等。
上面的命题除（ 3）的真假需由具体情况客观判断外，余者的真值均为 1。但是它们均不是简单命题，分别用了,且,,,非,,
,或,,,如果 ……则 ……”,,当且仅当,等联结词。
由命题和联结词构成的命题称为复合命题。构成复合命题的可以是原子命题，也可以是另一个复合命题。一个复合命题的真值不仅与构成复合命题的命题的真值有关，而且也与所用联结词有关。下面我们给出几个基本的联结词。
第 1章 命题逻辑
1.否定设 p为任一命题，复合命题“非 p”（ p的否定）称为 p的否定式，记作,为 否定联结词。
为真，当且仅当 p为假。
的真值亦可由表 1.1.1所示的称为,真值表,的表格确定。由表 1.1.1可知：命题 p为真，当且仅当
。事实上，它定义了一个一元函数 (称为一元真值函数 )：
""?
p ""p
p
p
,{ 0,1 } { 0,1 }
( 0 ) 1 ( 1 ) 0
f
ff
表 1.1.1
p
0 1
1 0
p
第 1章 命题逻辑
【 例 1.1.4】
(1)p,4是偶数。其真值为 1。
,4不是偶数。其真值为 0。
(2)q：这些都是学生。
：这些不都是学生。
注：否定联结词使用的原则：将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。例如上例中的（ 2）,q的否定式就不能写成,这些都不是学生,。事实上严格来讲,,不是,
不一定否定,是,。如阿契贝难题：,本句是六字句,
与,本句不是六字句,均是真命题。不过，一般地，
自然语言中的,不,,,无,,,没有”、“并非”
等词均可符号化为
p
p
" ".?
第 1章 命题逻辑
2.合取,∧,
设 p,q是任意两个命题，复合命题,p且 q”（ p与 q）
称为 p与 q的合取式，记作,p∧ q。,∧,是合取联结词。 p∧ q为真,p∧ q的真值表如表 1.1.2所示，它定义了一个二元真值函数：当且仅当 p,q均为真。
f∧,{00,01,10,11}→{0,1}，
f∧ (00)=0,f∧ (01)=0，
f∧ (10)=0，
f∧ (11)=1
表 1.1.2
p q p^q
0 0 0
0 1 0
1 0 0
1 1 1
第 1章 命题逻辑
【 例 1.1.5】
(1) p,4是偶数。 q,3是素数。则
p∧ q,4是偶数且 3是素数。其真值为 1。
(2) r：煤是白的。则
p∧ r,4是偶数且煤是白的。真值为 0。
第 1章 命题逻辑
3.析取,∨,
设 p,q是任意两个命题，复合命题,p或 q”称为 p、
q的析取式，记作,p∨ q。,∨,称为析取联结词。
p∨ q为假，当且仅当 p,q同为假。
p∨ q的真值表如表 1.1.3所示，它定义了一个二元真值函数：
f∨,{00,01,10,11}→{0,1}，
f∨ (00)=0,f∨ (01)=1，
f∨ (10)=1,f∨ (11)=1
表 1.1.3
p q p ∨ q
0 0 0
0 1 1
1 0 1
1 1 1
第 1章 命题逻辑
【 例 1.1.6】
(1) p：小王喜欢唱歌。 (2) p：明天刮风。
q：小王喜欢跳舞。则 q：明天下雨。则
p∨ q：明天或者刮风或者下雨。
p∨ q：小王喜欢唱歌或喜欢跳舞。
注,∨,的逻辑关系是明确的。即 p,q二命题中至少有一个为真则析取式为真。因而，自然语言中常用的联结词诸如：,或者 ……或者 ……”,,可能 ……可能 ……”等，都可以符号化为,∨,。但日常语言中的,或,是具有二义性的，用,或,联结的命题有时是具有相容性的，如例
1.1.6中的二例，我们称之为可兼或。而有时又具有排斥性，称为不可兼或（异或），如：
（ 1）小李明天出差去上海或去广州。
（ 2）刘昕这次考试可能是全班第一也可能是全班第二。
第 1章 命题逻辑
4.蕴涵,→”
设 p,q是任意两个命题，复合命题,如果 p，则 q”称为 p
与 q的蕴涵式，记作,p→q。 P称为蕴涵式的前件,q称为蕴涵式的后件,→称为蕴涵联结词。 p→q为假，当且仅当 p为真、
q为假。
p→q的真值表如表 1.1.4所示，它定义了一个二元真值函数：
f→,{00,01,10,11}→{0,1}，
f→(00)=1,f→(01)=1，
f→(10)=0,f→(11)=1
表 1.1.4
p q p → q
0 0 1
0 1 1
1 0 0
1 1 1
第 1章 命题逻辑
【 例 1.1.7】
(1) p：天下雨了。
q：路面湿了。则
p→q：如果天下雨，则路面湿。
(2) r：三七二十一。则
p→r：如果天下雨，则三七二十一。
第 1章 命题逻辑注 (1）逻辑中，前件 p为假时，无论后件 q是真是假，蕴涵式 p→q的真值均为 1。这与日常语言中的，特别是数学上常用的,真蕴涵真,不太一样。事实上并不矛盾，
例如某人说：,如果张三能及格，那太阳从西边升起。,说话者当然知道,张三能及格,与,太阳从西边升起,风马牛不相及，而一般人此时并没有说谎的必要，即这是真命题，它所要明确的是,张三能及格,
是假命题。
（ 2）正如前面所说，数理逻辑中的联结词是对日常语言中的联结词的一种逻辑抽象，日常语言中联结词所联结的句子之间是有一定内在联系的，但在数理逻辑中，
联结词所联结的命题可以毫无关系。如在日常语言中
,如果 ……则 ……”所联结的句子之间表现的是一种因果关系，如例 1.1.7中的（ 1）。但在数理逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫不相关的，如例
1.1.7中的（ 2）。
第 1章 命题逻辑
（ 3） p→q的逻辑关系是,p是 q的充分条件,q是 p的必要条件。
在日常语言中，特别是在数学语言中,q是 p的必要条件还有许多不同的叙述方式，如：,p仅当 q（仅当 q，则 p）,,
,只有 q才 p”,,只要 p就 q”,,除非 q，否则非 p（非 p，除非 q）,等，均可符号化成 p→q的形式。
【 例 1.1.8】 符号化下列命题：
（ 1）只要天下雨，我就回家。
（ 2）只有天下雨，我才回家。
（ 3）除非天下雨，否则我不回家。
（ 4）仅当天下雨，我才回家。
解 设 p：天下雨。 q：我回家。则（ 1）符号化为 p→q。
（ 2）、（ 3）、（ 4）均符号化为 q→p（或等价形式：
).pq
第 1章 命题逻辑
5.等价,,
设 p,q是任意两个命题，复合命题,p当且当 q”称为 p与 q
的等价式，记作,p q。
,” 称为等价联结词。 p q为真，当且仅当 p,q真值相同。 p q的真值表如表 1.1.5所示，它定义了一个二元真值函数：
f,{00,01,10,11}→{0,1}，
f (00)=1,f (01)=0，
f (10)=0,f (11)=1
表 1.1.5
p q p q
0 0 1
0 1 0
1 0 0
1 1 1
第 1章 命题逻辑
【 例 1.1.9】
(1)p,2+2=4。
q,5是素数。则
p q,2+2=4当且仅当 5是素数。
(2)p,∠ A=∠ B。
q：二角是同位角。则
p q,∠ A=∠ B当且仅当二角是同位角。
在（ 1）中的 p与 q并无内在关系，但因二者均为真，
所以 p q的真值为 1。
在（ 2）中由于相等的两角不一定是同位角，所以真值为 0。
第 1章 命题逻辑
【 例 1.1.10】 将下列自然语言形式化,
（ 1）如果天不下雨并且不刮风，我就去书店。
（ 2）小王边走边唱。
（ 3）除非 a能被 2整除，否则 a不能被 4整除。
（ 4）此时，小纲要么在学习，要么在玩游戏。
（ 5）如果天不下雨，我们去打篮球，除非班上有会。
解 （ 1）设 p：今天天下雨,q：今天天刮风,r：我去书店。则原命题符号化为：
(2)设 p：小王走路,q：小王唱歌。则原命题符号化为：
p∧ q
(3)设 p,a能被 2整除,q,a能被 4整除。则原命题符号化为：
p q r
p q q p
或第 1章 命题逻辑
（ 4）此时，小纲要么在学习，要么在玩游戏。
（ 5）如果天不下雨，我们去打篮球，除非班上有会。
(4)设 p：小刚在学习,q：小刚在玩游戏。则原命题符化为：
( ) ( ) ( ) ( )p q p q p q p q或
(5)设 p：今天天下雨,q：我们去打篮球,r：今天班上有会。则原命题符号化为：
()r p q
第 1章 命题逻辑
1.2 命题公式及分类为了用数学的方法研究命题，就必须像数学处理问题那样将命题公式化，并讨论对于这些公式的演算（推理）规则，
以期由给定的公式推导出新的命题公式来。
前面我们用 p,q,r等符号表示确定的简单命题，通常此时称它们为命题常元。而事实上，这些常元无论具体是怎样的简单命题，它们的真值均只可能是,1”或,0”。为了更广泛地应用命题演算，在研究时，我们只考虑命题的,真,与
,假,,而不考虑它的具体涵义（即只重,外延,,不顾
,内涵,）。譬如：当 p是一个真命题时,p就是一个假命题，而不管此时 p表示的是命题,三七二十一,,还是命题,今天天下雨,。这时的 p实际上就是一个简单命题的抽象，就如同数学公式中的变量 x一样，我们称其为命题变元。
命题变元 一个不确指的（抽象的）命题，以 p,q,r等表之。
第 1章 命题逻辑命题公式 由命题变元（常元）符、联结词和圆括号按一定逻辑关系联结起来的字符串。
所谓按一定的逻辑关系，即字符串的构成要求合理，
如（ p）是个合理的构成，是命，（ ∧ p）不是合理的构成，就不是命题公式，同样（ p→q） ∨ r）也不是合理的构成（括号必须成对出现），因此也不是命题
wff
（ wff=Well Formed Formulas ），也称真值函数。
第 1章 命题逻辑定义 1.2.1 合式公式的递归定义：
［ 1］单个的命题变元（或常元）是合式公式。
［ 2］如果 A是一个合式公式，则（ A）也是合式公式。
［ 3］如果 A,B均是合式公式，则（ A∧ B）、（ A∨ B）、
（ A→B）、（ A B）也都是合式公式。
［ 4］只有有限次地应用［ 1］、［ 2］、［ 3］组成的字符串才是合式公式。
例如：（（ p∨ q） ∧ r）、（（ p） ∧ (q∧ r））、（（（ p→q）
∧ （ q∨ r (( p） →r））均是合式公式。第 3式的生成过程如下：
① p ［ 1］
② q ［ 1］
③（ p→q )［ 3］①②
④ r ［ 1］
⑤（ q∨ r） ［ 3］②④
第 1章 命题逻辑
⑥ （ p ） ［ 2］①
⑦ （（ p ） →r） ［ 3］④⑥
⑧ （（ p→q） ∧ （ q∨ r） ［ 3］③⑤
⑨ （（（ p→q） ∧ （ q∨ r p ） →r）） ［ 3］⑦⑧
注 (1)A,B均代表任意的命题公式。
(2)为方便起见，公式最外层及（ A）的括号可省略。
第 1章 命题逻辑定义 1.2.2
(1)若 A是单个命题（变元或常元），则称为 0层公式。
(2)称 A为 n+1（ n≥0）层公式是指 A符合下列诸情况之一：
① A= B,B是 n层公式；
② A=B∧ C，其中 B为 i层公式,C为 j层公式，
n=max（ i,j）；
③ A=B∨ C，其中 B,C的层次同②；
④ A=B→C，其中 B,C的层次同②；
⑤ A=B C，其中 B,C的层次同②。
上面生成的第 3个式（（ p→q） ∧ （ q∨ r (( p） →r））
是 3层公式。
解释 指定命题变元代表某个具体的命题。 命题变元本身是无意义的，它仅是一个符号。同样公式本身是无意义的，只有给每个命题变元作了解释，它们才有意义。
第 1章 命题逻辑
【 例 1.2.1】 公式,A=（ p∧ q） →r。
解释 I1：假设 p：现在是白天,q：现在是晴天,r：我们能看见太阳。则
A：如果现在是白天且是晴天，则我们能看见太阳。其真值为 1。
解释 I2,假设 p,q如上,r：我们能看见星星。则 A：
如果现在是白天且是晴天，则我们能看见星星。其真值为 0。
由此可见，不同的解释可使公式有不同的真值。事实上，对于命题变元无论做什么样的解释，它都只有两种结果：或者是,真,,或者是,假,。从而由变元和联结词组成的公式所表示的复合命题，也是或为,真,,或为,假,。如前所述这才是我们所需要的。因此，欲获取命题公式的真值，并非只有,解释,一个途径，还可以通过,赋值,获得。
第 1章 命题逻辑赋值（真值指派） 对命题变元指派确定的真值。
赋值是一组由 0,1构成的数串，按字典顺序（或下标）
对应公式中的命题符。
如例 1.2.1中，公公式 A=(p∧ q） →r：
解释 I1 实际上是对变元 p,q,r赋值 111，得 A的真值为 1；
解释 I2 实际上是对变元 p,q,r赋值 110，得 A的真值为 0；
A的真值是在对 p,q,r的某种赋值下所得的真值。
定义 1.2.3 设 p1,p2,…,pn是公式 A中所包含的所有命题变元，给 p1,p2,…,pn各赋一个真值称为对 A的一个赋值，那些使 A的真值为 1的赋值称为 A的成真赋值，使 A
的真值为 0的赋值称为 A的成假赋值。
如例 1.2.1中,111是 A=（ p∧ q） →r的成真赋值,110是
A的成假赋值。根据前面对联结词的讨论知,001,011、
101,000,010也都是 A的成真赋值。
第 1章 命题逻辑问题 若公式 A含有 n（ n≥1）个命题变元，那么对 A
共有多少种不同的赋值？答 因为 n个变元赋值后形成一个 n位的二进制数，所以共有 2n个。将公式 A在所有赋值情况下的取值列成表，称为 A的真值表。构造真值表的步骤如下：
（ 1）找出命题公式中所含的所有命题变元并按下标或字典顺序给出；
（ 2）按从低到高的顺序写出各层次；
（ 3）顺序列出所有的赋值（ 2n个）；对应每个赋值，
计算命题公式各层次的真值，直到最后计算出命题公式的真值。
第 1章 命题逻辑
【 例 1.2.2】 求下列命题公式的真值表：
( 1 ) ( )
( 2 ) ( ) ( )
( 3 ) ( )
p q q
p q p q
p q r
()p q q解 (1)公式 的真值表如表 1.2.1所示。
表 1.2.1
第 1章 命题逻辑
( ) ( )p q p q(2)公式 的真值表如表 1.2.2所示。
表 1.2.2
第 1章 命题逻辑表 1.2.3
(3)公式 (p→q)∧ r的真值表如表 1.2.3所示。
第 1章 命题逻辑由上可知，有的公式在任何赋值情况下真值恒为 1，
如例 1.2.2（ 1）；有的公式在任何赋值情况下真值恒为 0，
如例 1.2.2（ 2）；有的公式某些赋值使其真值为 1，而另一些赋值使其真值为 0，因此可将公式分为如下三类：
永真式（重言式） 所有赋值均为成真赋值的公式。
永假式（矛盾式） 所有赋值均为成假赋值的公式。
可满足式 至少有一组赋值是成真赋值的公式。
由定义可知，任何不是矛盾式的公式是可满足式。
第 1章 命题逻辑
1.3 等值演算
【 例 1.3.1】 构造公式
()、,,p q p q p q p q
解 公式 ()、,,p q p q p q p q
的真值表如表 1.3.1所示。
的真值表 1.3.1
第 1章 命题逻辑由例题可见，
的真值表是完全相同的，这种情况并不是偶然的。事实上，给定 n个命题变元，按照公式的生成规则，我们可以得到无穷多个命题公式，但这无穷多个命题公式的真值表却只有有限个。如例 1.3.1，许多公式在变元的各种赋值下真值是一样的，我们称其为等值的，那么如何判断两个公式等值呢？
()、,,p q p q p q p q
第 1章 命题逻辑定义 1.3.1 设 A,B是任意两个命题公式，若等价式 A B
为重言式，则称 A与 B是等值的，记作,A B。
定理 1.3.1 A B为重言式，当且仅当 A,B具有相同的真值表。
注 （ 1）如果 A B不是重言式，则称 A与 B不等值，可记作,A B。
（ 2）,,与,=”不同,,A=B”表示二公式一样，
,A B”表示二公式真值一样，如：
p∨ q p→ q，但是
p∨ q≠p→q。
第 1章 命题逻辑
（ 3）,,与,,是两个完全不同的符号。,,
是联结词,A B是一个公式。,,不是联结词，
而是两个公式之间的关系符,A B并不是一个公式，
而只是表示 A与 B是两个真值相同的公式。
（ 4）,,的性质：
① A A（自反性）；
②若 A B，则 B A（对称性）；
③若 A B,B C，则 A C（传递性）。
第 1章 命题逻辑利用真值表我们可以证明许多等值式：
(1)双重否定律
(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)德 ·摩根律
AA
()
()
A B A B
A B A B
第 1章 命题逻辑
(7)吸收律 A∨ (A∧ B) A A∧ (A∨ B) A
(8)零律 A∨ 1 1 A∧ 0 0
(9)同一律 A∨ 0 A A∧ 1 A
(10)排中律
(11)矛盾律
(12)蕴涵等值式
(13)等价等值式
(14)假言易位
(15)等价否定等值式
(16)归谬论
1
0
( ) ( )
( ) ( )
AA
AA
A B A B
A B A B B A
A B B B
A B A B A
第 1章 命题逻辑
【 例 1.3.2】 证明等价等值式,A B (A→B)∧ (B→A)。
解 作如表 1.3.2所示的真值表。
表 1.3.2
因此,A B (A→B)∧ (B→A)。?
第 1章 命题逻辑
【 例 1.3.3】 用等值演算验证等值式
p→（ q→r p∧ q） →r。
证明
()
()
()
()
()
()
p q r
p q r
p q r
p q r
p q r
p q r
（蕴涵等值式）
（蕴涵等值式）
（结合律）
（德 ·摩根律）
（蕴涵等值式）
第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑因此，公式（（ p∨ q） ∧ q） →p是一个重言式。
等值演算在计算机硬件设计，开关理论和电子元器件中都占据重要地位。
第 1章 命题逻辑
1.4 联结词全功能集前面我们一共介绍了五个联结词：
,∧,∨,→和看到了有些公式书写形式尽管不同，但实际上是等值的。因此我们不禁要问：
（ 1）总共有多少个命题公式？
（ 2）总共有多少个联结词？
对于含有两个命题变元的公式，理论上讲可以书写出无穷多个公式，但互不等值的公式恰有 = 24 =16个。对应着 16个不同的真值表（真值表共有 22行，行上的每个记入值又可在 0、
1中任取其一，因此构成
16个真值函数 Fi（ i=0,1,…,15），其中 Fi,{00,01,10，
11}→{0,1}，如表 1,4,1所示。
222
222
第 1章 命题逻辑表 1.4.1
这里,F0和 F15正是两个常值函数：永假式 0和永真式 1； F3和 F5分别是命题变元 p和 q； F1是我们所熟知的二元真值函数 p∧ q； F7是二元真值函数 p∨ q； F9是二元真值函数 p q； F10和 F12分别是一元真值函数 q和 p； F11和 F13 分别是二元真值函数 q→p和 p→q。
第 1章 命题逻辑第 1章 命题逻辑
( 1 )
( 2 ) ( ) ( )
( 3 ) ( ) ( )
( 4 ) 0
( 5 ) 0
( 6) 1
A B B A
A B C A B C
A B C A B
AA
AA
AA
)( CA?
联结词,,有以下性质：?
第 1章 命题逻辑
3.与非,↑”
设 p,q为任意两个命题，复合命题,p与 q的否定,
称为 p,q的与非，记作,p↑q。,↑” 称为与非联结词。
p↑q为假，当且仅当 p,q均为真。
由定义可知,F14是二元真值函数 p↑q。
()p q p q
性质：（ p↑q） ↑r p↑（ q↑r）
第 1章 命题逻辑第 1章 命题逻辑
【 例 1.4.1】 将下列公式化成仅含联结词,↑”的公式。
( 1 )
( 2 )
( 3 )
Ap
B p q
C p q
解第 1章 命题逻辑
4.或非,↓”
设 p,q为任意两个命题，复合命题,p或 q的否定,
称为 p,q的或非，记作,p↓q。,↓” 称为或非联结词。
p↓q为真，当且仅当 p,q均为假。
由定义可知,F8是二元真值函数 p↓q。
p↓q （ p∨ q）
类似于,↑”,,↓” 同样不满足结合律，并类似可将例 1.4.1中的公式化成仅含联结词,↓” 的公式。
第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑
),,,(),,,(
),,,(),,,(
),,,(),,,(
),,,(,),,,(),,,()1(
.
1
2121
21
1
211
21
1
211
21121121
nn
nn
nn
nnn
pppApppA
pppApppA
pppApppA
m
pppApppApppA
A
mAmA
因此于是有由归纳假设个联结词出现。有其中形呈可能是下述情形之一连接词时，
个中有立，则个连接词时，原命题成中有假设当第 1章 命题逻辑理成立。类似可证第二式，故定
），归纳成立。证明同（
形。呈）（
归纳假设摩根定律德
（
形。呈
2
),,,(),,,(),,,(3
),,,(
),,,(),,,(
.),,,(),,,(
)),,,(),,,(
),,,(
),,,(),,,(),,,()2(
21221121
21
212211
212211
212211
21
21221121
nnn
n
nn
nn
nn
n
nnn
pppApppApppA
pppA
pppApppA
pppApppA
pppApppA
pppA
pppApppApppA
第 1章 命题逻辑定理 1.5.2 设 A*,B*分别是公式 A,B的对偶式,
如果 A B,则 A* B*。
证明 设 A,B中所有不同的变元为 p1,p2,…,
pn,则由 A B知：
A（ p1,p2,…,pn) B（ p1,p2,…,pn） 是永真式,
A（ p1,p2,…,pn） B（ p1,p2,…,pn）
亦是永真式 。
所以，
1 2 1 2(,,,) (,,,)nnA p p p B p p p
第 1章 命题逻辑本定理称为对偶原理因此有即永真式仍是时，得代以当是永真式即知由定理
),,,(),,,(
),,,(),,,(
),,,(),,,(
),,,(),,,(
),,,,(),,,(1.5.1
2121
2121
2121
2121
2121
nn
nn
nn
ii
nn
nn
pppBpppA
pppBpppA
pppBpppA
pp
pppBpppA
pppBpppA
第 1章 命题逻辑定义 1.5.2 将命题变元及其否定统称为文字 。
简单析取式 （ 基本和 ） 仅由有限个文字构成的析取式 。 简单合取式 （ 基本积 ） 仅由有限个文字构成的合取式 。
例如,p,q既是一个文字的简单析取式,又是一个文字的简单合取式 。
p∨ q,p∨ r均是有两个文字的简单析取式 。
p∧ q∧ r,p∧ q∧ q均是有三个文字的简单合取式 。
第 1章 命题逻辑第 1章 命题逻辑
【 例 1.5.1】 判断下列各式是析取范式还是合取范式 。
（ 1） p
（ 2） p∨ q
（ 3） p∧ q∧ r
（ 4） p∨ （ q∧ r） ∨ r
（ 5） p∧ （ p∨ q） ∧ （ p∨ q∨ r） ∧ q
解 (1）既是一个简单析取式又是一个简单合取式,是只有一个简单析取式的合取范式,也是只有一个简单合取式的析取范式。 （ 2）是有两个简单合取式的析取范式,也是只有一个简单析取式的合取范式。 （ 3）是有三个简单析取式的合取范式，
也是只有一个简单合取式的析取范式。 （ 4）是有三个简单合取式的析取范式。 （ 5）是有四个简单析取式的合取范式。
第 1章 命题逻辑性质：
(1) 一个文字既是一析取范式又是一合取范式 。
(2) 一个析取范式为矛盾式,当且仅当它的每个简单合取式是矛盾式 。
(3) 一个合取范式为重言式,当且仅当它的每个简单析取式是重言式 。
例如,A=（ p∧ p∧ q） ∨ （ p∧ q∧ q） 是矛盾式 。
A=（ p∨ p∨ q） ∧ （ p∨ q∨ q） ∧ （ q∨ r∨ r）
是重言式 。
第 1章 命题逻辑定理 1.5.3 任一命题公式都存在着与之等值的析取范式,任一命题公式都存在着与之等值的合取范式 。
证明 对于任一公式,可用下面的方法构造出与其等值的范式：
（ 1） 利用等值式
A B (A→B） ∧ （ B→A）
A→B A∨ B
使公式中仅含联结词,∧,∨ 。
（ 2） 利用德 ·摩根律和双重否定律
（ A∨ B） A∧ B
（ A∧ B） A∨ B
A A
将否定符 (移至命题变元符前,并去掉多余的否定符 ),
第 1章 命题逻辑
（ 3） 利用分配律
A∧ （ B∨ C) （ A∧ B） ∨ （ A∧ C）
A∨ （ B∧ C） （ A∨ B） ∧ （ A∨ C）
所得即与原公式等值的范式。
第 1章 命题逻辑第 1章 命题逻辑
（分配律）
（ 分配律
（ 矛盾式
（ 同一律第 1章 命题逻辑
【 例 1.5.3】 求例 1.5.2中公式的合取范式 。
解 由例 1.5.2第 4步原式
(( ( ) ) ) ( )
( ) ( ) ( )
( ) ( ) ( )
p q r p p r
p q p r p p r
p q p r p r
（分配律）
--合取范式 （ 幂等律,交换律 ）
第 1章 命题逻辑定义 1.5.3 对于公式 A：
极小项 包含 A中所有命题变元或其否定一次且仅一次的简单合取式；
极大项 包含 A中所有命题变元或其否定一次且仅一次的简单析取式 。
注 极小项或极大项中各文字要求按角标顺序或字典顺序排列 。
第 1章 命题逻辑第 1章 命题逻辑表 1.5.1
由真值表可看出,对于 p,q的任一组赋值,有且仅有一个极小项的真值为 1,即极小项之间是不等值的,4个真值赋值与 4个极小项值之间有一一对应关系。 我们用 mi表示在十进制为 i的赋值下真值为 1的极小项。
第 1章 命题逻辑定义 1.5.4 对于公式 A：
主析取范式 与 A等值的由极小项构成的析取范式；
主合取范式 与 A等值的由极大项构成的合取范式 。
由定理 1.5.3知,任一公式的析 （ 合 ） 取范式总是存在的,求主范式只需在求范式的基础上将每个简单合 （ 析 ） 取式化成极小 （ 大 ） 项 。
第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑定理 1.5.4 任何命题公式的主析取范式存在且唯一 。
证明 由析取范式的存在性知主析取范式的存在性成立 。 下面证唯一性：
设任一命题公式 A有两个主析取范式 B和 C,则因为 A B,A C,所以 B C。
若 B,C是 A的 （ 在不计极小项的顺序的情况下 ）
不相等的主析取范式 （ B≠C）,则必存在某个极小项
mi,mi只存在于 B,C之一中 。
不妨设 mi在 B中,而不在 C中,因此 i之二进制表示是 B的成真赋值,而对于 C则为成假赋值,这与
B C矛盾,故 B=C。
第 1章 命题逻辑第 1章 命题逻辑结论 （ 主析取范式的用途 ）,
(1) 重言式的主析取范式包含公式的全部 2n个极小项 。
(2)（ 规定 ） 矛盾式的主析取范式为 0。
(3) 二等值的公式必有相同的主析取范式 （ 不计极小项的顺序 ） 。
(4) 不列真值表,由主析取范式可得公式的成真,
成假赋值 。
(5) 仅由真值表,可得公式的表达式 （ 主析取范式形式 ） 。
(6) 解决应用问题 。
前两条可用来判断公式的类型,第三条判断两个公式的等值,由此前面提出的三个问题得到了解决第 1章 命题逻辑第 1章 命题逻辑
【 例 1.5.9】 已知命题公式 A（ p,q,r） 的成真赋值为 010,101,110,求 A。
解 A m2∨ m5∨ m6
（ p∧ q∧ r） ∨ （ p∨ q ∧ r） ∨ （ p∧ q∧ r）
第 1章 命题逻辑
【 例 1.5.10】 四人比赛,三人估计成绩。 甲说,"
A第一,B第二 ",乙说,"C第二,D第四 ",丙说,"A第二,D第四 "。 结果每人都说对了一半,假设无并列名次，
问 A,B,C,D 的实际名次如何？
解 设 p,A 第一,q,B 第二 。
（ 甲说 ） （ p∧ q） ∨ （ p∧ q） 1
r,C 第二,s,D 第四 。
（ 乙说 ） （ r∧ s） ∨ （ r∧ s） 1
t,A 第二,s,D 第四。
（ 丙说 ） （ s∧ t） ∨ （ s∧ t） 1
第 1章 命题逻辑第 1章 命题逻辑对应 p,q的每一组赋值,极大项的真值有且仅有一个为 0,极大项与其成假赋值有着一一对应关系,我们用 Mi表示在十进制为 i的赋值下真值为 0的极大项。 因此,求一个公式的主合取范式,只需知道该公式的成假赋值，并将对应着这个赋值也成假的那些极大项合取起来，即得该公式的主合取范式。
第 1章 命题逻辑
【 例 1.5.11】 求公式 （ p→（ p∨ r）） ∧ （ q p）
的主合取范式 。
解 由例 1.5.7已知此公式的成假赋值为 010,011，
100,101,可得主合取范式为
2 3 4 5
( ( )) ( )
( 2,3,4,5 )
( ) ( ) ( ) ( )
p p r q p
M M M M
P q r p q r p q r p q r
第 1章 命题逻辑同样,利用等值演算法也可得主合取范式：
( ( ) ) ( )
( ) ( ) ( )
1 ( ) ( )
( ) ( )
( ) ( )
( ) ( )
( ) ( )
p p r q p
p p r q p 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
（ 等价等值式,蕴涵等值式 ）
（ 排中律,零律,交换律 ）
（同一律,分配律）
--主合取范式 （交换律）
第 1章 命题逻辑注意到,对于任一公式,在它的 2n个赋值中,非
0即 1,因此其主析取范式中的极小项和其主合取范式中的极大项的个数之和恰为 2n,且其下标不会相同 。
故当我们知道了一个公式的所有成真赋值时,也就知道了它的所有成假赋值 。 亦即,知道了主析取范式,
相应地也就得到了主合取范式,反之亦然 。
第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑
1.6 推 理 理 论推理是 " "的思维过程 。 在命题逻辑中,
前提是已知的命题公式,结论是从前提出发应用推理规则推出的命题公式 。 在传统数学中定理的证明均是由前提 （ 已知条件,全是真命题 ） 推出结论 （ 亦全是真命题 ）,这样的结论称为合法结论 。
数理逻辑有所不同,它着重研究的是推理的过程,这种过程称为演绎或形式证明。 在过程中使用的推理规则必须是公认的且要明确列出,而对于作为前提和结论的命题并不一定要求它们全是真命题,这样的结论称为有效结论。
第 1章 命题逻辑定理 1.6.1 称蕴涵式（ A1∧ A2∧ … ∧ An） →B为推理的形式结构,A1,A2,…,An为推理的前提,B为推理的结论。 若（ A1∧ A2∧ … ∧ An） →B是重言式，
则称从前提 A1,A2,…,An推出结论 B的推理正确，
B是 A1,A2,…,An的有效结论或逻辑结论。 记作：
（ A1∧ A2∧ … ∧ An） B （ A1,A2,…,An B)
否则称推理不正确,或 B不是前提 A1,A2,…,An
的有效结论 。
具有自反性,对称性,传递性 。
第 1章 命题逻辑
【 例 1.6.1】 验证下面推理是否正确：
一个数是复数,仅当它是实数或是虚数,一个数既不是实数也不是虚数,因此它不是复数 。
证明 设 p,它是复数,q,它是实数,r,它是虚数 。
推理的形式结构为：
（（ p→（ q∨ r）） ∧ （ q∧ r）） → p。
（ 1） 真值表法 (真值表如表 1.6.1所示 )。
第 1章 命题逻辑表 1.6.1
因为只有第一行前提,结论均为真,所以推理正确。
第 1章 命题逻辑第 1章 命题逻辑
（ 3） 主析取范式法 （ 略 ） 。
以上的证明方法,当形式结构比较复杂,特别是所含命题变元较多时,一般是很不方便的 。 下面介绍构造证明法,这种方法必须在给定的规则下进行,
其中有些规则建立在推理定律 （ 重言蕴涵式 ） 的基础之上 。
第 1章 命题逻辑推理定律：
第 1章 命题逻辑推理规则：
前提引入规则 在证明的任何步骤上,都可以引入前提 。 结论引入规则 在证明的任何步骤上,所得到的结论均可作后续证明的前提加以引用 。
置换规则 在证明的任何步骤上,命题公式中的任何子公式都可以用与之等值的公式置换 。 另外,由前面的 8个推理定律可得下面 8个推理规则,（ 这里 A1，
A2,…,An B表示 B是 A1,A2,…,An的逻辑结论 。 ）
第 1章 命题逻辑
第 1章 命题逻辑构造证明法：
构造证明可以看作公式的序列,其中的每个公式都是按照事先规定的规则得到的,且需将所用的规则在公式后写明,该序列的最后一个公式正是所要证明的结论 。
第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑例 1.6.4 构造证明,找出下列推理的有效结论 。
如果我考试通过了,那么我很快乐 。 如果我快乐,那么阳光灿烂 。 现在阳光不灿烂且天很暖 。 因此我考试没通过 。
解 设 p,我考试通过了,q,我很快乐,r,阳光灿烂,
s,天很暖 。
前提,p→q,q→r,结论,prs
（ 1） p→q 前提引入
（ 2） q→r 前提引入
（ 3） p→r （ 1） （ 2） 假言三段论
（ 4） r∧ s 前提引入
（ 5） r （ 4） 化简
（ 6） p （ 5） （ 3） 拒取式所以有效结论是,我考试没通过。
第 1章 命题逻辑第 1章 命题逻辑
【 例 1.6.5】 如果小张去看电影,则当小王去看电影时,小李也去 。 小赵不去看电影或小张去看电影 。
小王去看电影 。 所以当小赵去看电影时,小李也去 。
解 设 p,小张去看电影,q,小王去看电影,r：
小李去看电影,s,小赵去看电影 。
第 1章 命题逻辑第 1章 命题逻辑定义 1.6.1 如果 A1,A2,…,An均为命题公式,
A1∧ A2∧ … ∧ An 0,则称 A1,A2,…,An不相容,
否则称相容 。
第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑第 1章 命题逻辑
【 例 1.6.7】 证明,p q,q→r,r∨ s,p→s,s不相容 。
证明 （ 1） p→s 前提引入 （ 2） s 前提引入
（ 3） p （ 1） （ 2） 拒取式
（ 4） p q 前提引入
（ 5） （ p→q） ∧ （ q→p） （ 4） 置换
（ 6） p→q （ 5） 化简
（ 7） q （ 3） （ 6） 假言推理
（ 8） q→r 前提引入
（ 9） r （ 7） （ 8） 假言推理
（ 10） r∨ s 前提引入
（ 11） r （ 2） （ 10） 析取三段论
（ 12） r∧ r （ 9） （ 11） 合取式引入,故诸命题不相容 。
第 1章 命题逻辑
1.7 命题演算的自然推理形式系统 N
1,形式系统的基本概念通过前面的讨论,我们看到,永真式是命题逻辑推理中一个非常基本和非常重要的概念,这些可以有无穷多种表达形式的永真式,它们都是逻辑推理规律的反映 。 弄清这些永真式,对于掌握命题逻辑有着极为重要的意义 。 为了系统地研究它们,就需要把所有的永真式包括在一个系统内,作为一个整体来研究,
这样的系统应当是一个形式系统,也只有形式系统,
才能进行充分的研究,从而掌握全部规律 。
第 1章 命题逻辑在形式系统中,原始概念和用于推演的逻辑规则没有任何直觉意义,甚至没有任何预先设定的涵义,
它们无非是一些约定,约定怎样用符号 （ 符号语言 ）
来表达原始概念和用于推演的逻辑规则 。 这一过程一旦结束,这个形式系统便和一切实际意义,甚至逻辑都毫不相干,留下来的只是符号串与符号串之间的关系,根据这种关系,可以进行符号串之间的变换 。 在形式系统中,决定一切的是符号串与符号串之间的关系,合法符号串的识别,系统内的推演都可以根据合法符号串的形成规则和推理规则 --符号串之间的关系机械地完成,不需要比认读和改写符号串更多的知识,
甚至不需要逻辑 。 很清楚,只有这样的形式系统,才是本质上只能做符号变换的计算机可以接受的 。
第 1章 命题逻辑当然,形式系统的提出往往是有客观背景的,这是因为现实世界的某些对象及其性质需要精确地描述 。
但是,当形式系统一旦建成,它便应当是超脱客观背景的,它描述的对象可以不限于原来考虑的那些对象,
而是与它们有着共同结构的相当广泛的一类对象 。
形式系统一般由下面几部分组成：
（ 1） 字母表 。 字母表由不加定义而采用的符号组成,字母表提供形式系统可以使用的符号 。
第 1章 命题逻辑
（ 2） 字母表上符号串集的一个子集 Form。 Form
中的元素称为公式,Form提供形式系统可以使用的符号串。
（ 3） Form的一个子集是 Axiom。 Axiom中的元素称为公理,Axiom提供形式系统一开始便要接受而不加证明的定理 。
第 1章 命题逻辑
(4) 推理规则集 Rule。 Rule中的元素称为推理规则,
Rule规定了公式间的转换关系 。
对于一个形式系统,Axiom和 Rule均有可能是空集 。
如当 Axiom和 Rule均为空集时,称这样的形式系统仅仅是一个语言生成系统 。 在数理逻辑中,如果 Axiom不是空集时,称这样的系统为公理系统； Axiom如果是空集时,称这样的推理系统为自然推理系统 。
第 1章 命题逻辑在形式系统中进行推理时,涉及的仅仅是公式的语法,并不涉及公式本身的意义是什么,推理过程仅被看作公式按照推理规则进行变形的过程 。 但是,我们可以对公式进行解释,使公式变成具体涵义的语句,
从而对某一特定的客体范畴和特定的性质进行描述,
用来讨论一个具体的实际系统,这时,有两个具体的问题必须解决：
(1) 形式系统中正确推理出来的公式 --定理在所讨论的具体实际系统中是否永真 。
(2) 在所讨论的具体实际系统中永真的语句是否均为形式系统内的定理 。 这是系统的可靠性和完备性问题 。
第 1章 命题逻辑
2,命题演算的自然推理形式系统 N
1) 字母表
(1) 命题符：
p,q,r,p1,q1,r1,…,pi,qi,ri,… ；
(2) 联结词符：
,∧,∨,→，
(3) 括号,（,） 。
其中的命题符构成的集合为可数集 。
第 1章 命题逻辑定义 1.7.1 字母表上的一个符号串是 FN中的元素,
当且仅当这个符号串能由 (1)～ (3)推导出：
(1) 单个的命题符是 FN中的元素 。
(2) 如果 A∈ FN,则
（ A） ∈ FN。
(3) 如果 A,B∈ FN,则 （ A∧ B）,（ A∨ B）,
（ A→B）,（ A B） ∈ FN。
在上面的定义中,我们使用了 A,B来表示任意的公式，
而不是某个具体的公式,因而这样的符号是元语言符号。
以下我们用大写英文字母：
A,B,C,A1,B1,C1,…,
Ai,Bi,Ci,…
来表示任意公式。
第 1章 命题逻辑
3) 推理规则
N系统中有 11条推理规则,下面以模式的形式给出：
·包含律 （ ∈ ）,如果 A∈ Γ,则 Γ├A。
·增加前提律 （ +）,
如果 Γ├A,则 Γ,Γ′├A。 （ Γ′ FN） 。
· 消去律 （ -）,
如果 Γ,A├B,Γ,A├ B,则 Γ├A。
第 1章 命题逻辑
·→消去律 （ →+）,如果 Γ├A→B,Γ├A,则 Γ├B。
·→引入律 （ →-）,如果 Γ,A├B,则 Γ├A→B。
·∧ 消去律 （ ∧ -）,如果 Γ├A∧ B,则 Γ├A,Γ├B。
·∧ 引入律 （ ∧ +）,如果 Γ├A,Γ├B,则 Γ├A(B。
·∨ 消去律 （ ∨ -）,如果 Γ,A├C,Γ,B├C,则 Γ,A∨ B├C。
·∨ 引入律 （ ∨ +）,如果 Γ├A,则 Γ├A(B,Γ├B∨ A。
· 消去律 （ -）,如果 Γ├A B,则 Γ├A→B,Γ├B→A。
· 引入律 （ +）,如果 Γ├A→B,Γ├B→A,则 Γ├A B 。
第 1章 命题逻辑定义 1.7.2
A是在 N系统中由 Γ形式可证明的,记作,Γ├A，
当且仅当 Γ├A能由有限次使用 N系统中的推理规则生成 。
【 例 1.7.1】 证明,A→B,B→C├A→C。
证明
（ 1） A→B├A→B （ ∈ ）
（ 2） A→B,B→C,A├ A→B （ +）,（ 1）
（ 3） A├A （ ∈ ）
（ 4） A→B,B→C,A├A （ +）,（ 3）
第 1章 命题逻辑
（ 5） A→B,B→C,A├B （ →-）,（ 2）,（ 4）
（ 6） B→C├B→C （ ∈ ）
（ 7） A→B,B→C,A├B→C （ +）,（ 6）
（ 8） A→B,B→C,A├C （ →-）,（ 5）,（ 7）
（ 9） A→B,B→C├A→C （ →+）,（ 8）
第 1章 命题逻辑
【 例 1.7.2】 证明,A├A。
此模式称为双 (消去律 （ 简称 -） 。
证明
（ 1） A,A├ A （ ∈ ）
（ 2） A,A├ A （ ∈ ）
（ 3） A├A （ -）,（ 1）,（ 2）
第 1章 命题逻辑
【 例 1.7.3】 证明,如果
Γ,A├ B,Γ,A├B,则 Γ├ A。
此模式称为 引入律 （ 简称 +） 。
证明
（ 1） Γ,A├ B （ 前提 ）
（ 2） Γ,A├B （ 前提 ）
（ 3） Γ├A→ B （ →+）,（ 1）
第 1章 命题逻辑
（ 4） Γ,A├A→ B （ +）,（ 3）
（ 5） Γ├A→B （ →+）,（ 2）
（ 6） Γ,A├A→B （ +）,（ 5）
（ 7） A├A （ -）
（ 8） Γ,A├A （ +）,（ 7）
（ 9） Γ,A├ B （ →-）,（ 4），（ 8）
（ 10） Γ,A├B （ →-）,（ 6）,（ 8）
（ 11） Γ├ A （ -）,（ 9）,（ 10)
– 例 1.7.4 证明,Γ├B,B├A,则 Γ├A。
– 此模式称为传递律 （ Tr ） 。
– 证明
– （ 1） Γ├B （ 前提 ）
– （ 2） B├A （ 前提 ）
第 1章 命题逻辑
4,N中推理模式的一些性质
(1) A和 B是形式等值的 （ 简称等值的 ）,记作：
A├┤B,当且仅当 A├B,B┤A。
(2) 设 A,B,C是公式,B是 A的子串,将 A中的
B用 C置换 （ 不一定全部置换 ） 后得到的公式 A′,如果
B├┤C,则 A├┤A′。
(3) 设 A和 A*互为对偶式,则有 A*├┤ A。
(4) 设 A,B为有对偶的公式,其对偶式分别为 A*，
B*,如果 A├┤B,则 A*├┤B*。
第 1章 命题逻辑
【 例 1.7.5】 证明,A→B├┤ A∨ B。
证明 先证 A→B├ A∨ B
（ 1） A├ A （ ∈ ）
（ 2） A├ A∨ B （ ∨ +）,（ 1）
（ 3） A→B,（ A∨ B）,A├ A(B （ +）,（ 2）
（ 4） A→B,（ A∨ B）,A├ （ A∨ B） （ ∈ ）
（ 5） A→B,（ A∨ B） ├A （ -）,（ 4）
（ 6） A→B,（ A∨ B） ├ A→B （ ∈ ）
（ 7） A→B,（ A∨ B） ├ B （ →-）,（ 6）
（ 8） A→B,（ A∨ B） ├ A∨ B （ ∨ +）,（ 7）
（ 9） A→B,（ A∨ B） ├ （ A∨ B） （ ∈ ）
（ 10） A→B├ A∨ B （ -）,（ 8）,（ 9）
第 1章 命题逻辑再证 A∨ B├ A→B。
（ 1） A,B,A├ A （ ∈ ）
（ 2） A,B,A├A （ ∈ ）
（ 3） A,A├B （ -）,（ 1）,（ 2）
（ 4） A├A→B （ →+）,（ 3）
（ 5） B,A├B （ ∈ ）
（ 6） B├A→B （ →+）,（ 5）
（ 7） A∨ B├A→B （ ∨ -）,（ 4）,（ 6）
故 A→B├┤ A∨ B。
第 1章 命题逻辑
5,几个定理
(1) 可靠性定理,设 Γ FN,A∈ FN,如果 Γ├A，
则 Γ A。
(2) 完备性定理,设 Γ FN,A∈ FN,如果 Γ A，
则 Γ├A。
证明略 。
第 1章 命题逻辑第 1章 命题逻辑
【 例 1.8.2】 某研究所有赵,钱,孙,李,周五位高级工程师 。 现需派一些人出国考察,由各方面的限制,此次选派必须满足下列条件：
（ 1） 若赵去,则钱也去 。
（ 2） 李,周两人中必有人去 。
（ 3） 钱,孙两人中去且仅去一人 。
（ 4） 孙,李两人同去或都不去 。
（ 5） 若周去,则赵,钱也同去 。 试分析领导的选派方案 。
分析 五个人每个人都可以去,这就得到五个原子命题 。 满足条件,即要使由所给条件确定的命题公式同时为真,方法是取五个命题公式的合取式 F,再化成主析取范式,这样每个极小项就是一个选派方案,符合题意的方案即为所求 。
第 1章 命题逻辑第 1章 命题逻辑
【 例 1.8.3】 有一种保密锁的控制电路,锁上共有三个键 A,B,C。 当三键同时按下,或只有 A,B两键按下,或只有 A,B其中之一按下时,锁被打开 。
以 G表示锁被打开,试写出 G的逻辑表达式 。
分析 因为当且仅当开锁条件成立时,G为真 。 所以,令 A,B,C分别表示命题 "A,B,C键被按下 "，
依据开锁条件,寻求出 G的成真赋值,即可解决问题 。
解 列出开锁条件的真值表,如表 1.8.1所示 。
第 1章 命题逻辑表 1.8.1
A B C G
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
0
1
0
1
0
1
1
第 1章 命题逻辑第 1章 命题逻辑
【 例 1.8.4】 验证下列推理的正确性 。
如果 6是偶数,则 7被 2除不尽 。 或 5不是素数,或
7被 2除尽 。 5是素数 。 因此,6是奇数 。
分析 显然推理的结论是个假命题,但不能由此就认定推理不正确 。 逻辑推理关心的是推理的过程是否合乎规则,并不要求前提均为真,当前题中有假命题时,正确的推理完全可推出错误的结论,因此逻辑推理的结论只是有效结论 。
第 1章 命题逻辑解 设 p,6是偶数,q,7被 2除尽,r,5是素数 。
前提,p→ q,r∨ q,r
结论,p
（ 1） r∨ q 前提引入
（ 2） r 前提引入
（ 3） q （ 1） （ 2） 析取三段论
（ 4） p→ q 前提引入
（ 5） p （ 4） （ 5） 拒取式所以推理正确。
如果 6是偶数,则 7被 2除不尽。 或 5不是素数,或 7被 2除尽。 5
是素数。 因此,6是奇数。
第 1章 命题逻辑
【 例 1.8.5】 公安人员审一件盗窃案 。 已知：
（ 1） 甲或乙盗窃了电脑 。
（ 2） 若甲盗窃了电脑,则作案时间不能发生在午夜前 。
（ 3） 若乙证词正确,则在午夜时屋里灯光未灭 。
（ 4） 若乙证词不正确,则作案时间发生在午夜前 。
（ 5） 午夜时屋里灯光灭了 。
问,谁是盗窃犯？
解 设 p,甲盗窃了电脑,q,乙盗窃了电脑,r：
作案时间发生在午夜前,s,乙证词正确,t,午夜时屋里灯光灭了 。
前提,p∨ q,p→ r,s→ t,s→r,t
第 1章 命题逻辑第 1章 命题逻辑习 题 一
1,指出下述语句哪些是命题,哪些不是命题,若是命题,
指出其真值 。
（ 1） 离散数学是计算机科学系的一门必修课 。
（ 2） 你上网了吗？
（ 3） 不存在偶素数 。
（ 4） 明天我们去郊游 。
第 1章 命题逻辑
（ 5） x≤6。
（ 6） 我们要努力学习 。
（ 7） 如果太阳从西方升起,你就可以长生不老 。
（ 8） 如果太阳从东方升起,你就可以长生不老 。
（ 9）这个理发师给一切不自己理发的人理发。
第 1章 命题逻辑
2,将下列命题符号化 。
（ 1） 逻辑不是枯燥无味的 。
（ 2） 小李边读书边听音乐 。
（ 3） 现在没下雨,可也没出太阳,是阴天 。
（ 4） 鱼和熊掌不可兼得 。
（ 5） 小王要么住在 203室要么住在 205室 。
（ 6） 小刘总是在图书馆自习,除非他病了或图书馆不开门 。
（ 7） 他只要用功,成绩就会好 。
（ 8） 他只有用功,成绩才会好 。
（ 9） 如果你来了,那么他唱不唱歌将看你是否伴奏而定 。
第 1章 命题逻辑
3,求下列公式在赋值 0011下的真值 。
（ 1） p∨ （ q∧ r） →s
（ 2） （ p r） ∧ （ ﹁ s∨ q）
（ 3） （ p∧ （ q∨ r）） ∨ （（ p∨ q） ∧ r∧ s）
（ 4） （ q∨ ﹁ p） →（ ﹁ r∨ s）
第 1章 命题逻辑
4,用真值表判断下列公式的类型 。
（ 1） （ p→（ q→p））
（ 2） ﹁ （ p→q） ∧ ﹁ q
（ 3） （（ p→q） →（ p→r）） →（ p→（ q→r））
（ 4） ﹁ （ p∨ （ q∧ r）） （（ p∨ q） ∧ （ p∨ r））?
第 1章 命题逻辑
5,证明下列等值式 。
（ 1） （ p→r） ∧ （ q→r） （ p∨ q） →r
（ 2） p→（ q→r） q→（ p→r）
（ 3） （ p∧ q） ∨ （ ﹁ p∧ r） ∨ （ q∧ r） （ p∧ q） ∨
（ ﹁ p∧ r）
（ 4） ﹁ （ p q） （ p∨ q） ∧ ﹁ （ p∧ q）
（ 5） p→（ q∨ r） ﹁ r→（ p→q）
第 1章 命题逻辑
6,设 A,B,C是任意命题公式：
（ 1） 若 A∨ B A∨ C,则 B C成立吗？
（ 2） 若 A∧ B A∧ C,则 B C成立吗？
（ 3） 若 ﹁ A ﹁ B,则 A B成立吗？
7,证明 {﹁,→}是联结词极小全功能集 。
8,将下列公式化为仅出现联结词 ﹁,→的公式 。
（ 1） p∨ （ q∧ ﹁ r）
（ 2） p （ q→（ p∨ r））
（ 3） p∧ q∧ r
第 1章 命题逻辑
9,将下列公式化为仅出现联结词 ﹁,∧ 的等价公式 。
（ 1） ﹁ r∨ q∨ （ p→q）
（ 2） p→（ q→r）
（ 3） p q
10,将下列公式化为仅出现联结词 ﹁,∨ 的等价公式 。
（ 1） ﹁ p∧ ﹁ q∧ （ ﹁ r→p）
（ 2） ﹁ p q
（ 3） p→（ q∨ ﹁ r）） ∧ ﹁ p∧ q
第 1章 命题逻辑
11,将下列公式化为仅出现联结词 ↑的等价公式,
再将其化成仅出现联结词 ↓的等价公式 。
（ 1） p→（ ﹁ p→q）
（ 2） （ p∨ ﹁ q） ∧ r
12,公式 A=（ ﹁ （ p↓q） ∧ r） ↑q,写出 A的对偶式
A*,并将 A和 A*化成仅含联结词 ﹁,∧,∨ 的等价公式 。
第 1章 命题逻辑
13,A,B,C,D 四人参加拳击比赛,三个观众猜测比赛结果 。
"C第一,B第二 。 "
乙说,"C第二,D 第三 。 "
丙说,"A第二,D第四 。 "
比赛结果显示,他们每个人均猜对了一半,并且没有并列名次 。 问实际名次怎样排列？
第 1章 命题逻辑
14,求下列公式的主析取范式和主合取范式,并指出它们的成真赋值 。
（ 1） （ ﹁ p∨ ﹁ q） →（ p ﹁ q）
（ 2） q∧ （ p∨ ﹁ q）
（ 3） p∨ （ ﹁ p→（ q∨ （ ﹁ q→r）））
（ 4） （ p→（ q∧ r）） ∧ （ ﹁ p→（ ﹁ q∧ ﹁ r））
（ 5） p→（ p∧ （ q→r））
（ 6） ﹁ （ p→q） ∨ p∨ r
（ 7） （ p→q） →r
（ 8） （ p∨ q） ∧ （ p→r） ∧ （ q→r）
第 1章 命题逻辑
15,P,Q,R,S四个字母,从中取两个字母,
但要同时满足三个条件：
a：如果取 P,则 R和 S要取一个；
b,Q,R不能同时取；
c：取 R则不能取 S。
问有几种取法？ 如何取？
第 1章 命题逻辑
16,甲,乙,丙,丁四个人有且仅有两个人参加比赛,
下列四个条件均要满足：
（ 1） 甲和乙只有一人参加；
（ 2） 丙参加,则丁必参加；
（ 3） 乙和丁至多有一人参加；
（ 4） 丁不参加,甲也不会参加 。
问哪两个人参加了比赛？
第 1章 命题逻辑
17,一个排队线路,输入为 A,B,C,其输出分别为 FA,FB,FC,在此线路中,在同一时间只能有一个信号通过,若同时有两个或两个以上信号申请输出时,则按 A,B,C的顺序输出,写出 FA,FB,FC的表达式 。
18,用两种方法 （ 真值表法和主析取范式法 ） 证明下面推理不正确 。 如果 a,b两数之积是负数,则 a，
b之中恰有一个是负数 。 a,b两数之积不是负数 。 所以
a,b中无负数 。
第 1章 命题逻辑
19,用构造证明法证明下列推理的正确性 。
（ 1） 前提 ﹁ （ p∧ ﹁ q）,﹁ q∨ r,﹁ r
结论 ﹁ p
（ 2） 前提 p∧ q,（ p q） →（ r∨ s）
结论 r∨ s
（ 3） 前提 q→p,q s,s r,r∧ t
结论 p∧ q
第 1章 命题逻辑
（ 4） 前提 p→（ q→r）,（ r∧ s） →t,﹁ u→（ s∧ ﹁ t）
结论 p→（ q→u）
（ 5） 前提 （ p∨ q） →（ u∧ s）,（ s∨ t） →r
结论 p→r
（ 6） 前提 p→（ q→r）,s→p,q
结论 s→r
（ 7） 前提 p→q
结论 p→（ p∧ q）
（ 8） 前提 s→﹁ q,s∨ r,﹁ r,﹁ p q
结论 p
第 1章 命题逻辑
20,用附加前提法推证 19题中的 （ 4）,（ 5）,
（ 6）,（ 7） 。
21,用归缪法推证 19题中的 （ 1）,（ 3）,（ 7）,
（ 8） 。
22,将下列论证用命题逻辑符号表示,然后求证逻辑推证是否成立 。
（ 1） 如果天热则蝉叫,如果蝉叫则小王不睡觉,小王游泳或睡觉,所以如果天热则小王游泳 。
（ 2） 或者逻辑难学,或者有少数学生不喜欢它,
如果数学容易学,那逻辑并不难学 。 因此,如有许多学生喜欢逻辑,,那么数学并不难学 。
第 1章 命题逻辑
（ 3） 如果小张来,则小王和小李中恰有一人来 。
如果小王来,则小赵就不来 。 所以,如果小赵来了但小李没来,则小张也没来 。
（ 4） 有甲,乙,丙,丁参加乒乓球比赛 。 如果甲第三,则当乙第二时,丙第四 。 或者丁不是第一,或者甲第三 。 事实上,乙第二 。 因此,如果丁第一,那么丙第四 。
第 1章 命题逻辑
23,判断下面推理的结论 。
若公司拒绝增加工资,则罢工不会停止,除非罢工超过 3个月且公司经理辞职 。 公司拒绝增加工资 。 罢工又刚刚开始 。 罢工是否停止？
