第 1章 命题逻辑基本概念离 散 数 学哈尔滨理工大学本科生课程计算机系本章说明
本章的主要内容
– 命题、联结词、复合命题
– 命题公式、赋值、命题公式的分类
本章与后续各章的关系
– 本章是后续各章的准备或前提
1.1 命题与联结词
数理逻辑研究的 中心问题 是 推理 。
推理的 前提 和 结论 都是 表达判断 的 陈述句 。
表达判断的陈述句构成了推理的 基本单位 。
1.1 命题与联结词
称能判断真假而不是可真可假的陈述句为 命题
（ proposition） 。
作为命题的陈述句所表达得的判断结果称为命题的 真值 。
真值只取两个,真与假 。
真值为真的命题称为 真命题 。
真值为假的命题称为 假命题 。
感叹句、疑问句、祈使句都不能称为命题。
判断结果不唯一确定的陈述句不是命题。
陈述句中的悖论不是命题 。
说明
(1)4是素数。
(2)
(3)x大于 y。
(4)充分大的偶数等于两个素数之和。
(5)今天是星期二。
(6)
(7)请不要吸烟！
(8)这朵花真美丽啊！
(9)我正在说假话。
例 1.1 判断下列句子是否为命题。
(1)是，假命题
(2)是，真命题
(3)不是，无确定的真值
(4)是，真值客观存在
(5)是，真值根据具体情况而定。
(6)不是，疑问句
(7)不是，祈使句
(8)不是，感叹句
(9)不是，悖论是无理数2
吗？大于 2?
命题和真值的符号化
用小写英文字母 p,q,r…,pi,qi,ri … 表示命题
用,1” 表示真，用,0” 表示假
r,充分大的偶数等于两个素数之和 。s,今天是星期二 。
是无理数2
p,4是素数。
q：
不能被分解成更简单的陈述句，称这样的命题为 简单命题 或 原子命题 。
由简单陈述句通过联结词而成的陈述句，称这样的命题为 复合命题 。
例 1.2
将下面这段陈述中所出现的原子命题符号化，并指出它们的真值，然后再写出这段陈述。
是有理数是不对的； 2是偶素数； 2或 4是素数；如果 2
是素数,则 3也是素数； 2是素数当且仅当 3也是素数 。2
p,是有理数
q,2是素数；
r,2是偶数
s,3是素数；
t,4是素数
2 0
1
1
1
0
非 p；
q并且 (与 )r；
q或 t；
如果 q,则 s；
q当且仅当 s。
例 1.2的讨论
半形式化形式
数理逻辑研究方法的主要特征是将论述或推理中的 各种要素都符号化 。即构造各种符号语言来代替自然语言 。
形式化语言,完全由符号所构成的语言。
将联结词（ connective）符号化，消除其二义性，对其进行严格定义。
例如,他 是 100米或 400米赛跑的冠军。
鱼香肉丝或锅包肉，加一碗汤。
定义 1.1 否定 (negation)
设 p为命题，复合命题,非 p”(或,p
的否定,)称为 p的否定式,记作 ┐ p，
符号 ┐ 称作 否定联结词,并规定 ┐ p
为真当且仅当 p为假 。
例如,p,哈尔滨 是一个大城市 。
┐ p,哈尔滨是一个不大城市。
┐ p,哈尔滨不是一个大城市。
p ┐ p
1 0
0 1
定义 1.2 合取 (conjunction)
设 p,q为二命题，复合命题,p
并且 q”(或,p与 q”)称为 p与 q
的 合取式,记作 p∧q,∧ 称作合取联结词,并规定 p∧q 为真当且仅当 p与 q同时为真 。
使用合取联结词时要注意的两点：
1) 描述合取式的灵活性与多样性。
自然语言中的,既 …… 又 ……,,,不但 …… 而且 ……,,
,虽然 …… 但是 ……,,,一面 …… 一面 ……,等联结词都可以符号化为 ∧ 。
2) 分清简单命题与复合命题。
不要见到,与,或,和,就使用联结词 ∧ 。
p q p∧ q
1 1 1
1 0 0
0 1 0
0 0 0
例 1.3 将下列命题符号化
(1)吴颖既用功又聪明 。
(2)吴颖不仅用功而且聪明 。
(3)吴颖虽然聪明,但不用功 。
(4)张辉与王丽都是三好学生 。
(5)张辉与王丽是同学 。
p,吴颖用功 。
q,吴颖聪明 。
r,张辉是三好学生 。
s,王丽是三好学生 。
t,张辉与王丽是同学 。
(1)p∧q
(2)p∧q
(3)q∧┐p
(4)r∧s
(5)t
解题要点：
正确理解命题含义 。
找出原子命题并符号化 。
选择恰当的联结词 。
合取举例
p,我们去看电影。
q,房间里有十张桌子。
p∧ q,我们去看电影并且房间里有十张桌子。
在数理逻辑中，关心的只是复合命题与构成复合命题的各原子命题之间的真值关系，即抽象的逻辑关系，并不关心各语句的具体内容 。
说明定义 1.3 析取 (disjunction)
设 p,q为二命题，复合命题,p
或 q”称作 p与 q的 析取式,记作
p∨ q,∨ 称作 析取联结词,并规定 p∨ q为假当且仅当 p与 q同时为假 。
自然语言中的,或,具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或 和 排斥或 (排异或 )。
说明
p q p∨ q
1 1 1
1 0 1
0 1 1
0 0 0
例 1.4 将下列命题符号化
(1)张晓静爱唱歌或爱听音乐。
(2)张晓静只能挑选 202或 203房间。
(3)张晓静是江西人或安徽人。
(4)他昨天做了二十或三十道习题。
(1)设 p,张晓静爱唱歌,q,张晓静爱听音乐。
相容或，符号化为 p∨ q
(2)设 t,张晓静挑选 202房间,u,张晓静挑选 203房间。
排斥或，符号化为,(t∧┐ u)∨(┐ t∧ u)
(3)设 r,张晓静是江西人,s,张晓静是安徽人。
排斥或，符号化为,r∨ s。
(排斥或 联结的两个命题事实上不可能同时为真 )
或符号化为,(r∧┐s)∨(┐r∧s)
(4)原子命题，因为,或,只表示了习题的近似数目。
定义 1.4 蕴涵 (implication)
设 p,q为二命题，复合命题,如果 p，
则 q”称作 p与 q的 蕴涵式,记作 p→ q，
并称 p是蕴涵式的 前件,q为蕴涵式的后件,→ 称作 蕴涵联结词,并规定 p→ q
为假当且仅当 p为真 q为假 。
说明
p→ q的逻辑关系表示 q是 p的必要条件。
q是 p的必要条件有许多不同的叙述方式
– 只要 p,就 q
– 因为 p,所以 q
– p仅当 q
– 只有 q才 p
– 除非 q才 p
– 除非 q,否则非 p
p q p → q
1 1 1
1 0 0
0 1 1
0 0 1
例 1.5 将下列命题符号化，并指出其真值
(1)如果 3+3＝ 6，则雪是白的。
(2)如果 3+3≠6,则雪是白的。
(3)如果 3+3＝ 6，则雪不是白的。
(4)如果 3+3≠6,则雪不是白的。
解：令 p,3+3＝ 6,p的真值为 1。
q,雪是白色的,q的真值也为 1。
(1) p→ q
(2)┐ p→ q
(3) p→┐ q
(4) ┐ p→┐ q
1
1
0
1
例 1.5 将下列命题符号化，并指出其真值以下命题中出现的 a是一个给定的正整数：
(5) 只要 a能被 4整除，则 a一定能被 2整除。
(6) a能被 4整除，仅当 a能被 2整除。
(7) 除非 a能被 2整除,a才能被 4整除。
(8) 除非 a能被 2整除，否则 a不能被 4整除。
(9)只有 a能被 2整除,a才能被 4整除。
(10)只有 a能被 4整除,a才能被 2整除。
解,令 r,a能被 4整除 s,a能被 2整除
(5)至 (9)五个命题均叙述的是 a能被 2整除是 a能被 4整除的必要条件,因而都符号化为 r→ s。 其真值为 1
在 (10)中,将 a能被 4整除看成了 a能被 2整除的必要条件,因而应符号化为 s→ r。 a值不定时，真值未知。
关于蕴含的进一步说明
作为一种规定，当 p为假时，无论 q是真是假,p→ q均为真
。也就是说，只有 p为真 q为假这一种情况使得复合命题
p→ q为假。称为 实质蕴含 。
例：如果 x>5,则 x>2。
(1) x=6 如果 6>5，则 6>2。
(2) x=3 如果 3>5，则 3>2。
(3) x=1 如果 1>5，则 1>2。
例：如果我有车，那么我去接你
常出现的错误，没有分清充分条件与必要条件。
定义 1.5 等价 (two-way-implication)
设 p,q为二命题，复合命题,p
当且仅当 q”称作 p与 q的 等价式
，记作 p?q,称作 等价联结词
，并规定 p?q为真当且仅当 p与
q同时为真或同时为假 。
说明
,当且仅当,（ if and only if）
p?q的逻辑关系为 p与 q互为充分必要条件。
(p→q)∧(q→p) 与 p?q的逻辑关系完全一致。
p q p?q
1 1 1
1 0 0
0 1 0
0 0 1
例 1.6 将下列命题符号化，并讨论它们的真值
(1) π 是无理数当且仅当加拿大位于亚洲。
(2) 2+3＝ 5的充要条件是 π 是无理数。
(3) 若两圆 A,B的面积相等，则它们的半径相等；反之亦然。
(4) 当王小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快 。
(1)设 p,π 是无理数,q,加拿大位于亚洲。
符号化为 p?q,真值为 0。
(2)设 p,2+3＝ 5,q,π 是无理数。
符号化为 p?q,真值为 1。
(3)设 p,两圆 A,B的面积相等,q,两圆 A,B的半径相等。
符号化为 p?q,真值为 1。
(4)设 p,王小红心情愉快,q,王小红唱歌。
符号化为 p?q,真值由具体情况而定。
关于基本联结词的说明
{┐,∧,∨,→,?}，称为一个联结词集。
由联结词集 {┐,∧,∨,→,?}中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题，可以称它们为 基本的复合命题 。
基本复合命题的真值见下表：
关于基本联结词的说明
多次使用联结词集中的联结词，可以组成更为复杂的复合命题。
求复杂复合命题的真值时，除依据上表外，还要规定联结词的优先顺序，将括号也算在内。
本书规定的联结词优先顺序为,( ),┐,∧,∨,→,
，对于同一优先级的联结词，先出现者先运算。
例 1.7
令 p,北京比天津人口多 。
q,2+2＝ 4.
r,乌鸦是白色的 。
求下列复合命题的真值：
(1)((┐ p∧q)∨(p∧┐q))→r
(2)(q∨r)→(p→┐r)
(3)(┐p∨r)?(p∧┐r)
解,p,q,r的真值分别为
1,1,0
(1) 1
(2) 1
(3) 0
我们关心的是复合命题中命题之间的真值关系，
而不关心命题的内容。
说明
1.2 命题公式及其赋值
简单命题是真值唯一确定的命题逻辑中最基本的研究单位，
所以也称简单命题为 命题常项 或 命题常元 。
(proposition constant)
称真值可以变化的陈述句为 命题变项 或 命题变元
(proposition variable)。也用 p,q,r,… 表示命题变项。
当 p,q,r,… 表示命题变项时，它们就成了取值 0或 1的变项，
因而 命题变项已不是命题 。
这样一来,p,q,r,… 既可以表示命题常项，也可以表示命题变项。在使用中，需要由上下文确定它们表示的是常项还是变项。
将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为 合式公式 或 命题公式 。
定义 1.6 合式公式 ( wff )
(1)单个命题变项是合式公式，并称为 原子命题公式 。
(2)若 A是合式公式，则 (┐ A)也是合式公式。
(3)若 A,B是合式公式，则 (A∧B),(A∨B),(A→B),
(A?B)也是合式公式。
(4)只有有限次地应用 (1)～ (3)形式的符号串才是合式公式。
合式公式也称为 命题公式 或 命题形式,并简称为 公式 。
设 A为合式公式,B为 A中一部分，若 B也是合式公式，则称
B为 A的 子公式 。
合式公式,Well Formed Formula
关于合式公式的说明
定义 1.6给出的合式公式的定义方式称为 归纳定义 或 递归定义方式。
定义中引进了 A,B等符号，用它们表示任意的合式公式，而不是某个具体的公式，这与 p,p∧q,(p∧q)→r 等具体的公式是有所不同的。
A,B等符号被称作元语言符号。 p,q等被称作对象语言符号。
所谓 对象语言 是指用来描述研究对象的语言，而 元语言 是指用来描述对象的语言，这两种语言是不同层次的语言。
例如中国人学习英语时，英语为对象语言，而用来学习英语的汉语则是元语言。
关于合式公式的说明
(┐ A),(A∧B) 等公式单独出现时，外层括号可以省去，写成
┐ A,A∧B 等。
公式中不影响运算次序的括号可以省去，
如公式 (p∨q)∨(┐r) 可以写成 p∨q∨┐r 。
合式公式的例子：
(p→q)∧(q? r)
(p∧q)∧┐r
p∧(q∧┐r)
不是合式公式的例子
pq→r
(p→(r→q)
定义 1.7 公式层次
(1)若公式 A是单个的命题变项，则称 A为 0层合式 。
(2)称 A是 n+1(n≥0) 层公式 是指下面情况之一：
(a) A＝ ┐B,B是 n层公式；
(b) A＝ B∧C,其中 B,C分别为 i层和 j层公式，且 n=max(i,j)；
(c) A＝ B∨C,其中 B,C的层次及 n同 (b)；
(d) A＝ B→C,其中 B,C的层次及 n同 (b)；
(e) A＝ B?C,其中 B,C的层次及 n同 (b)。
(3)若公式 A的层次为 k,则称 A是 k层公式 。
例如,(┐p∧q)→r,(┐(p→┐q))∧((r∨s)?┐p)
分别为 3层和 4层公式公式的解释
在命题公式中，由于有命题符号的出现，因而真值是不确定的。当将公式中出现的全部命题符号都解释成具体的命题之后，公式就成了真值确定的命题了。
(p∨q)→r
若 p,2是素数,q,3是偶数,r,π 是无理数，则 p与 r被解释成真命题,q被解释成假命题，此时公式 (p∨q)→r 被解释成：若 2是素数或 3是偶数，则 π 是无理数。（真命题）
r被解释为,π 是有理数，则 (p∨q)→r 被解释成：若 2是素数或 3是偶数，则 π 是有理数。（假命题）
将命题变项 p解释成真命题，相当于指定 p的真值为 1，解释成假命题，相当于指定 p的真值为 0。
定义 1.8 赋值或解释
设 p1,p2,…,pn是出现在公式 A中的全部命题变项，给
p1,p2,…,pn各指定一个真值，称为对 A的一个 赋值 或 解释 。若指定的一组值使 A的真值为 1，则称这组值为 A的成真赋值 ；若使 A的真值为 0，则称这组值为 A的 成假赋值 。
对含 n个命题变项的公式 A的赋值情况做如下规定：
(1)若 A中出现的命题符号为 p1,p2,…,pn,给定 A的赋值
α 1,α 2,…,α n 是指 p1＝ α 1,p2＝ α 2,…,pn＝ α n。
(2)若 A中出现的命题符号为 p,q,r...,给定 A的赋值
α 1,α 2,…,α n是指 p＝ α 1,q＝ α 2,…,最后一个字母赋值 α n。
上述 α i取值为 0或 1,i＝ 1,2,…,n。
赋值举例
在公式 (┐ p1∧┐p 2∧┐p 3)∨(p 1∧p 2)中，
000(p1＝ 0,p2＝ 0,p3＝ 0)，
110(p1＝ 1,p2＝ 1,p3＝ 0)都是成真赋值，
001(p1＝ 0,p2＝ 0,p3＝ 1)，
011(p1＝ 0,p2＝ 1,p3＝ 1)都是成假赋值。
在 (p∧┐q)→r 中，
011(p1＝ 0,p2＝ 1,p3＝ 1)为成真赋值，
100(p1＝ 1,p2＝ 0,p3＝ 0)为成假赋值。
重要结论：
含 n(n≥1) 个命题变项的公式共有 2n个不同的赋值。
定义 1.9 真值表
将命题公式 A在所有赋值下取值情况列成表，称作 A的 真值表 。
构造真值表的具体步骤如下：
(1)找出公式中所含的全体命题变项 p1,p2,…,pn (若无下角标就按字典顺序排列 )，列出 2n个赋值。本书规定，赋值从 00… 0
开始，然后按二进制加法依次写出各赋值，直到 11… 1为止。
(2)按从低到高的顺序写出公式的各个层次。
(3)对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。
公式 A与 B具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考虑构造真值表的中间过程。
说明例 1.8
求下列公式的真值表，并求成真赋值和成假赋值。
(1)(┐ p∧q)→┐r
(2)(p∧┐p)?(q∧┐q)
(3)┐( p→q)∧q∧r
定义 1.10 重言式、永真式、可满足式设 A为任一命题公式
(1)若 A在它的各种赋值下取值均为真,则称 A是 重言式
(tautology)或 永真式 。
(2)若 A在它的各种赋值下取值均为假,则称 A是 矛盾式
(contradiction)或 永假式 。
(3)若 A不是矛盾式,则称 A是 可满足式（ satisfactable
formula） 。
定义 1.10的进一步说明
A是可满足式的等价定义是,A至少存在一个成真赋值。
重言式一定是可满足式，但反之不真。因而，若公式 A是可满足式，且它至少存在一个成假赋值，则称 A为非重言式的可满足式。
真值表可用来判断公式的类型,
– 若真值表最后一列全为 1，则公式为重言式。
– 若真值表最后一列全为 0，则公式为矛盾式。
– 若真值表最后一列中至少有一个 1，则公式为可满足式。
说明
n个命题变项共产生 2n个不同赋值
含 n个命题变项的公式的真值表只有 种不同情况n22
例题例题 1.9 下列各公式均含两个命题变项 p与 q,它们中哪些具有相同的真值表?
(1) p→q (4) (p→q)∧(q→p)
(2) p?q (5) ┐ q∨p
(3) ┐( p∧┐q)
哑元
设公式 A,B中共含有命题变项 p1,p2,…,pn，,而 A
或 B不全含有这些命题变项，比如 A中不含
pi,pi+1,…,pn,称这些命题变项为 A的 哑元,A的取值与哑元的变化无关，因而在讨论 A与 B是否有相等的真值表时，将 A,B都看成 p1,p2,…,pn的命题公式。
例题例 1.10 下列公式中,哪些具有相同的真值表?
(1)p→q
(2)┐ q∨r
(3)(┐ p∨q)∧((p∧r)→p)
(4)(q→r)∧(p→p)
本章主 要内容
命题与真值（或真假值）。
简单命题与复合命题。
联结词,┐,∧,∨,→,?。
命题公式（简称公式）。
命题公式的层次和公式的赋值。
真值表。
公式的类型：重言式（永真式），矛盾式（永假式）
，可满足式。
本章学习要求
在 5种联结词中，要特别注意蕴涵联结的应用，要弄清三个问题：
– p→q 的逻辑关系
– p→q 的真值
– p→q 的灵活的叙述方法
写真值表要特别仔细认真，否则会出错误。
深刻理解各联结词的逻辑含义。
熟练地将复合命题符号化。
会用真值表求公式的成真赋值和成假赋值。
本章典型习题
命题符号化
求复合命题的真值与命题公式的赋值
判断公式的类型例题：命题符号化
(1)我和他既是兄弟又是同学
p,我和他是兄弟,q,我和他是同学 。
故命题可符号化为,p∧q 。
(2)张三或李四都可以做这件事。
p,张三可以做这件事。 q,李四可以做这件事。
故命题可符号化为,p∧q 。
(3)仅当我有时间且天不下雨，我将去镇上。
对于,仅当,,实质上是,当,的逆命题。,当 A则 B”是
A→B,而,仅当 A则 B”是 B→A 。
p,我有时间。 q,天不下雨。 r,我将去镇上。
故命题可符号化为,r→(p∧q) 。
例题：命题符号化
(4)张刚总是在图书馆看书，除非图书馆不开门或张刚生病。
对于,除非,,只要记住,,除非,是条件。
p,张刚在图书馆看书,q,图书馆不开门,r,张刚生病。
故命题可符号化为,﹁ (q∨r)→p 。
(5)风雨无阻，我去上学。
可理解为,不管是否刮风、是否下雨，我都去上学,。
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)) 的真值表。
p q r
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
q∧r
0
0
0
1
0
0
0
1
p→(q∧r)
1
1
1
1
0
0
0
1
┐( p→(q∧r))
0
0
0
0
1
1
1
0
本章作业习题一
1,9,14,15,18,19
本章的主要内容
– 命题、联结词、复合命题
– 命题公式、赋值、命题公式的分类
本章与后续各章的关系
– 本章是后续各章的准备或前提
1.1 命题与联结词
数理逻辑研究的 中心问题 是 推理 。
推理的 前提 和 结论 都是 表达判断 的 陈述句 。
表达判断的陈述句构成了推理的 基本单位 。
1.1 命题与联结词
称能判断真假而不是可真可假的陈述句为 命题
（ proposition） 。
作为命题的陈述句所表达得的判断结果称为命题的 真值 。
真值只取两个,真与假 。
真值为真的命题称为 真命题 。
真值为假的命题称为 假命题 。
感叹句、疑问句、祈使句都不能称为命题。
判断结果不唯一确定的陈述句不是命题。
陈述句中的悖论不是命题 。
说明
(1)4是素数。
(2)
(3)x大于 y。
(4)充分大的偶数等于两个素数之和。
(5)今天是星期二。
(6)
(7)请不要吸烟！
(8)这朵花真美丽啊！
(9)我正在说假话。
例 1.1 判断下列句子是否为命题。
(1)是，假命题
(2)是，真命题
(3)不是，无确定的真值
(4)是，真值客观存在
(5)是，真值根据具体情况而定。
(6)不是，疑问句
(7)不是，祈使句
(8)不是，感叹句
(9)不是，悖论是无理数2
吗？大于 2?
命题和真值的符号化
用小写英文字母 p,q,r…,pi,qi,ri … 表示命题
用,1” 表示真，用,0” 表示假
r,充分大的偶数等于两个素数之和 。s,今天是星期二 。
是无理数2
p,4是素数。
q：
不能被分解成更简单的陈述句，称这样的命题为 简单命题 或 原子命题 。
由简单陈述句通过联结词而成的陈述句，称这样的命题为 复合命题 。
例 1.2
将下面这段陈述中所出现的原子命题符号化，并指出它们的真值，然后再写出这段陈述。
是有理数是不对的； 2是偶素数； 2或 4是素数；如果 2
是素数,则 3也是素数； 2是素数当且仅当 3也是素数 。2
p,是有理数
q,2是素数；
r,2是偶数
s,3是素数；
t,4是素数
2 0
1
1
1
0
非 p；
q并且 (与 )r；
q或 t；
如果 q,则 s；
q当且仅当 s。
例 1.2的讨论
半形式化形式
数理逻辑研究方法的主要特征是将论述或推理中的 各种要素都符号化 。即构造各种符号语言来代替自然语言 。
形式化语言,完全由符号所构成的语言。
将联结词（ connective）符号化，消除其二义性，对其进行严格定义。
例如,他 是 100米或 400米赛跑的冠军。
鱼香肉丝或锅包肉，加一碗汤。
定义 1.1 否定 (negation)
设 p为命题，复合命题,非 p”(或,p
的否定,)称为 p的否定式,记作 ┐ p，
符号 ┐ 称作 否定联结词,并规定 ┐ p
为真当且仅当 p为假 。
例如,p,哈尔滨 是一个大城市 。
┐ p,哈尔滨是一个不大城市。
┐ p,哈尔滨不是一个大城市。
p ┐ p
1 0
0 1
定义 1.2 合取 (conjunction)
设 p,q为二命题，复合命题,p
并且 q”(或,p与 q”)称为 p与 q
的 合取式,记作 p∧q,∧ 称作合取联结词,并规定 p∧q 为真当且仅当 p与 q同时为真 。
使用合取联结词时要注意的两点：
1) 描述合取式的灵活性与多样性。
自然语言中的,既 …… 又 ……,,,不但 …… 而且 ……,,
,虽然 …… 但是 ……,,,一面 …… 一面 ……,等联结词都可以符号化为 ∧ 。
2) 分清简单命题与复合命题。
不要见到,与,或,和,就使用联结词 ∧ 。
p q p∧ q
1 1 1
1 0 0
0 1 0
0 0 0
例 1.3 将下列命题符号化
(1)吴颖既用功又聪明 。
(2)吴颖不仅用功而且聪明 。
(3)吴颖虽然聪明,但不用功 。
(4)张辉与王丽都是三好学生 。
(5)张辉与王丽是同学 。
p,吴颖用功 。
q,吴颖聪明 。
r,张辉是三好学生 。
s,王丽是三好学生 。
t,张辉与王丽是同学 。
(1)p∧q
(2)p∧q
(3)q∧┐p
(4)r∧s
(5)t
解题要点：
正确理解命题含义 。
找出原子命题并符号化 。
选择恰当的联结词 。
合取举例
p,我们去看电影。
q,房间里有十张桌子。
p∧ q,我们去看电影并且房间里有十张桌子。
在数理逻辑中，关心的只是复合命题与构成复合命题的各原子命题之间的真值关系，即抽象的逻辑关系，并不关心各语句的具体内容 。
说明定义 1.3 析取 (disjunction)
设 p,q为二命题，复合命题,p
或 q”称作 p与 q的 析取式,记作
p∨ q,∨ 称作 析取联结词,并规定 p∨ q为假当且仅当 p与 q同时为假 。
自然语言中的,或,具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或 和 排斥或 (排异或 )。
说明
p q p∨ q
1 1 1
1 0 1
0 1 1
0 0 0
例 1.4 将下列命题符号化
(1)张晓静爱唱歌或爱听音乐。
(2)张晓静只能挑选 202或 203房间。
(3)张晓静是江西人或安徽人。
(4)他昨天做了二十或三十道习题。
(1)设 p,张晓静爱唱歌,q,张晓静爱听音乐。
相容或，符号化为 p∨ q
(2)设 t,张晓静挑选 202房间,u,张晓静挑选 203房间。
排斥或，符号化为,(t∧┐ u)∨(┐ t∧ u)
(3)设 r,张晓静是江西人,s,张晓静是安徽人。
排斥或，符号化为,r∨ s。
(排斥或 联结的两个命题事实上不可能同时为真 )
或符号化为,(r∧┐s)∨(┐r∧s)
(4)原子命题，因为,或,只表示了习题的近似数目。
定义 1.4 蕴涵 (implication)
设 p,q为二命题，复合命题,如果 p，
则 q”称作 p与 q的 蕴涵式,记作 p→ q，
并称 p是蕴涵式的 前件,q为蕴涵式的后件,→ 称作 蕴涵联结词,并规定 p→ q
为假当且仅当 p为真 q为假 。
说明
p→ q的逻辑关系表示 q是 p的必要条件。
q是 p的必要条件有许多不同的叙述方式
– 只要 p,就 q
– 因为 p,所以 q
– p仅当 q
– 只有 q才 p
– 除非 q才 p
– 除非 q,否则非 p
p q p → q
1 1 1
1 0 0
0 1 1
0 0 1
例 1.5 将下列命题符号化，并指出其真值
(1)如果 3+3＝ 6，则雪是白的。
(2)如果 3+3≠6,则雪是白的。
(3)如果 3+3＝ 6，则雪不是白的。
(4)如果 3+3≠6,则雪不是白的。
解：令 p,3+3＝ 6,p的真值为 1。
q,雪是白色的,q的真值也为 1。
(1) p→ q
(2)┐ p→ q
(3) p→┐ q
(4) ┐ p→┐ q
1
1
0
1
例 1.5 将下列命题符号化，并指出其真值以下命题中出现的 a是一个给定的正整数：
(5) 只要 a能被 4整除，则 a一定能被 2整除。
(6) a能被 4整除，仅当 a能被 2整除。
(7) 除非 a能被 2整除,a才能被 4整除。
(8) 除非 a能被 2整除，否则 a不能被 4整除。
(9)只有 a能被 2整除,a才能被 4整除。
(10)只有 a能被 4整除,a才能被 2整除。
解,令 r,a能被 4整除 s,a能被 2整除
(5)至 (9)五个命题均叙述的是 a能被 2整除是 a能被 4整除的必要条件,因而都符号化为 r→ s。 其真值为 1
在 (10)中,将 a能被 4整除看成了 a能被 2整除的必要条件,因而应符号化为 s→ r。 a值不定时，真值未知。
关于蕴含的进一步说明
作为一种规定，当 p为假时，无论 q是真是假,p→ q均为真
。也就是说，只有 p为真 q为假这一种情况使得复合命题
p→ q为假。称为 实质蕴含 。
例：如果 x>5,则 x>2。
(1) x=6 如果 6>5，则 6>2。
(2) x=3 如果 3>5，则 3>2。
(3) x=1 如果 1>5，则 1>2。
例：如果我有车，那么我去接你
常出现的错误，没有分清充分条件与必要条件。
定义 1.5 等价 (two-way-implication)
设 p,q为二命题，复合命题,p
当且仅当 q”称作 p与 q的 等价式
，记作 p?q,称作 等价联结词
，并规定 p?q为真当且仅当 p与
q同时为真或同时为假 。
说明
,当且仅当,（ if and only if）
p?q的逻辑关系为 p与 q互为充分必要条件。
(p→q)∧(q→p) 与 p?q的逻辑关系完全一致。
p q p?q
1 1 1
1 0 0
0 1 0
0 0 1
例 1.6 将下列命题符号化，并讨论它们的真值
(1) π 是无理数当且仅当加拿大位于亚洲。
(2) 2+3＝ 5的充要条件是 π 是无理数。
(3) 若两圆 A,B的面积相等，则它们的半径相等；反之亦然。
(4) 当王小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快 。
(1)设 p,π 是无理数,q,加拿大位于亚洲。
符号化为 p?q,真值为 0。
(2)设 p,2+3＝ 5,q,π 是无理数。
符号化为 p?q,真值为 1。
(3)设 p,两圆 A,B的面积相等,q,两圆 A,B的半径相等。
符号化为 p?q,真值为 1。
(4)设 p,王小红心情愉快,q,王小红唱歌。
符号化为 p?q,真值由具体情况而定。
关于基本联结词的说明
{┐,∧,∨,→,?}，称为一个联结词集。
由联结词集 {┐,∧,∨,→,?}中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题，可以称它们为 基本的复合命题 。
基本复合命题的真值见下表：
关于基本联结词的说明
多次使用联结词集中的联结词，可以组成更为复杂的复合命题。
求复杂复合命题的真值时，除依据上表外，还要规定联结词的优先顺序，将括号也算在内。
本书规定的联结词优先顺序为,( ),┐,∧,∨,→,
，对于同一优先级的联结词，先出现者先运算。
例 1.7
令 p,北京比天津人口多 。
q,2+2＝ 4.
r,乌鸦是白色的 。
求下列复合命题的真值：
(1)((┐ p∧q)∨(p∧┐q))→r
(2)(q∨r)→(p→┐r)
(3)(┐p∨r)?(p∧┐r)
解,p,q,r的真值分别为
1,1,0
(1) 1
(2) 1
(3) 0
我们关心的是复合命题中命题之间的真值关系，
而不关心命题的内容。
说明
1.2 命题公式及其赋值
简单命题是真值唯一确定的命题逻辑中最基本的研究单位，
所以也称简单命题为 命题常项 或 命题常元 。
(proposition constant)
称真值可以变化的陈述句为 命题变项 或 命题变元
(proposition variable)。也用 p,q,r,… 表示命题变项。
当 p,q,r,… 表示命题变项时，它们就成了取值 0或 1的变项，
因而 命题变项已不是命题 。
这样一来,p,q,r,… 既可以表示命题常项，也可以表示命题变项。在使用中，需要由上下文确定它们表示的是常项还是变项。
将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为 合式公式 或 命题公式 。
定义 1.6 合式公式 ( wff )
(1)单个命题变项是合式公式，并称为 原子命题公式 。
(2)若 A是合式公式，则 (┐ A)也是合式公式。
(3)若 A,B是合式公式，则 (A∧B),(A∨B),(A→B),
(A?B)也是合式公式。
(4)只有有限次地应用 (1)～ (3)形式的符号串才是合式公式。
合式公式也称为 命题公式 或 命题形式,并简称为 公式 。
设 A为合式公式,B为 A中一部分，若 B也是合式公式，则称
B为 A的 子公式 。
合式公式,Well Formed Formula
关于合式公式的说明
定义 1.6给出的合式公式的定义方式称为 归纳定义 或 递归定义方式。
定义中引进了 A,B等符号，用它们表示任意的合式公式，而不是某个具体的公式，这与 p,p∧q,(p∧q)→r 等具体的公式是有所不同的。
A,B等符号被称作元语言符号。 p,q等被称作对象语言符号。
所谓 对象语言 是指用来描述研究对象的语言，而 元语言 是指用来描述对象的语言，这两种语言是不同层次的语言。
例如中国人学习英语时，英语为对象语言，而用来学习英语的汉语则是元语言。
关于合式公式的说明
(┐ A),(A∧B) 等公式单独出现时，外层括号可以省去，写成
┐ A,A∧B 等。
公式中不影响运算次序的括号可以省去，
如公式 (p∨q)∨(┐r) 可以写成 p∨q∨┐r 。
合式公式的例子：
(p→q)∧(q? r)
(p∧q)∧┐r
p∧(q∧┐r)
不是合式公式的例子
pq→r
(p→(r→q)
定义 1.7 公式层次
(1)若公式 A是单个的命题变项，则称 A为 0层合式 。
(2)称 A是 n+1(n≥0) 层公式 是指下面情况之一：
(a) A＝ ┐B,B是 n层公式；
(b) A＝ B∧C,其中 B,C分别为 i层和 j层公式，且 n=max(i,j)；
(c) A＝ B∨C,其中 B,C的层次及 n同 (b)；
(d) A＝ B→C,其中 B,C的层次及 n同 (b)；
(e) A＝ B?C,其中 B,C的层次及 n同 (b)。
(3)若公式 A的层次为 k,则称 A是 k层公式 。
例如,(┐p∧q)→r,(┐(p→┐q))∧((r∨s)?┐p)
分别为 3层和 4层公式公式的解释
在命题公式中，由于有命题符号的出现，因而真值是不确定的。当将公式中出现的全部命题符号都解释成具体的命题之后，公式就成了真值确定的命题了。
(p∨q)→r
若 p,2是素数,q,3是偶数,r,π 是无理数，则 p与 r被解释成真命题,q被解释成假命题，此时公式 (p∨q)→r 被解释成：若 2是素数或 3是偶数，则 π 是无理数。（真命题）
r被解释为,π 是有理数，则 (p∨q)→r 被解释成：若 2是素数或 3是偶数，则 π 是有理数。（假命题）
将命题变项 p解释成真命题，相当于指定 p的真值为 1，解释成假命题，相当于指定 p的真值为 0。
定义 1.8 赋值或解释
设 p1,p2,…,pn是出现在公式 A中的全部命题变项，给
p1,p2,…,pn各指定一个真值，称为对 A的一个 赋值 或 解释 。若指定的一组值使 A的真值为 1，则称这组值为 A的成真赋值 ；若使 A的真值为 0，则称这组值为 A的 成假赋值 。
对含 n个命题变项的公式 A的赋值情况做如下规定：
(1)若 A中出现的命题符号为 p1,p2,…,pn,给定 A的赋值
α 1,α 2,…,α n 是指 p1＝ α 1,p2＝ α 2,…,pn＝ α n。
(2)若 A中出现的命题符号为 p,q,r...,给定 A的赋值
α 1,α 2,…,α n是指 p＝ α 1,q＝ α 2,…,最后一个字母赋值 α n。
上述 α i取值为 0或 1,i＝ 1,2,…,n。
赋值举例
在公式 (┐ p1∧┐p 2∧┐p 3)∨(p 1∧p 2)中，
000(p1＝ 0,p2＝ 0,p3＝ 0)，
110(p1＝ 1,p2＝ 1,p3＝ 0)都是成真赋值，
001(p1＝ 0,p2＝ 0,p3＝ 1)，
011(p1＝ 0,p2＝ 1,p3＝ 1)都是成假赋值。
在 (p∧┐q)→r 中，
011(p1＝ 0,p2＝ 1,p3＝ 1)为成真赋值，
100(p1＝ 1,p2＝ 0,p3＝ 0)为成假赋值。
重要结论：
含 n(n≥1) 个命题变项的公式共有 2n个不同的赋值。
定义 1.9 真值表
将命题公式 A在所有赋值下取值情况列成表，称作 A的 真值表 。
构造真值表的具体步骤如下：
(1)找出公式中所含的全体命题变项 p1,p2,…,pn (若无下角标就按字典顺序排列 )，列出 2n个赋值。本书规定，赋值从 00… 0
开始，然后按二进制加法依次写出各赋值，直到 11… 1为止。
(2)按从低到高的顺序写出公式的各个层次。
(3)对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。
公式 A与 B具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考虑构造真值表的中间过程。
说明例 1.8
求下列公式的真值表，并求成真赋值和成假赋值。
(1)(┐ p∧q)→┐r
(2)(p∧┐p)?(q∧┐q)
(3)┐( p→q)∧q∧r
定义 1.10 重言式、永真式、可满足式设 A为任一命题公式
(1)若 A在它的各种赋值下取值均为真,则称 A是 重言式
(tautology)或 永真式 。
(2)若 A在它的各种赋值下取值均为假,则称 A是 矛盾式
(contradiction)或 永假式 。
(3)若 A不是矛盾式,则称 A是 可满足式（ satisfactable
formula） 。
定义 1.10的进一步说明
A是可满足式的等价定义是,A至少存在一个成真赋值。
重言式一定是可满足式，但反之不真。因而，若公式 A是可满足式，且它至少存在一个成假赋值，则称 A为非重言式的可满足式。
真值表可用来判断公式的类型,
– 若真值表最后一列全为 1，则公式为重言式。
– 若真值表最后一列全为 0，则公式为矛盾式。
– 若真值表最后一列中至少有一个 1，则公式为可满足式。
说明
n个命题变项共产生 2n个不同赋值
含 n个命题变项的公式的真值表只有 种不同情况n22
例题例题 1.9 下列各公式均含两个命题变项 p与 q,它们中哪些具有相同的真值表?
(1) p→q (4) (p→q)∧(q→p)
(2) p?q (5) ┐ q∨p
(3) ┐( p∧┐q)
哑元
设公式 A,B中共含有命题变项 p1,p2,…,pn，,而 A
或 B不全含有这些命题变项，比如 A中不含
pi,pi+1,…,pn,称这些命题变项为 A的 哑元,A的取值与哑元的变化无关，因而在讨论 A与 B是否有相等的真值表时，将 A,B都看成 p1,p2,…,pn的命题公式。
例题例 1.10 下列公式中,哪些具有相同的真值表?
(1)p→q
(2)┐ q∨r
(3)(┐ p∨q)∧((p∧r)→p)
(4)(q→r)∧(p→p)
本章主 要内容
命题与真值（或真假值）。
简单命题与复合命题。
联结词,┐,∧,∨,→,?。
命题公式（简称公式）。
命题公式的层次和公式的赋值。
真值表。
公式的类型：重言式（永真式），矛盾式（永假式）
，可满足式。
本章学习要求
在 5种联结词中，要特别注意蕴涵联结的应用，要弄清三个问题：
– p→q 的逻辑关系
– p→q 的真值
– p→q 的灵活的叙述方法
写真值表要特别仔细认真，否则会出错误。
深刻理解各联结词的逻辑含义。
熟练地将复合命题符号化。
会用真值表求公式的成真赋值和成假赋值。
本章典型习题
命题符号化
求复合命题的真值与命题公式的赋值
判断公式的类型例题：命题符号化
(1)我和他既是兄弟又是同学
p,我和他是兄弟,q,我和他是同学 。
故命题可符号化为,p∧q 。
(2)张三或李四都可以做这件事。
p,张三可以做这件事。 q,李四可以做这件事。
故命题可符号化为,p∧q 。
(3)仅当我有时间且天不下雨，我将去镇上。
对于,仅当,,实质上是,当,的逆命题。,当 A则 B”是
A→B,而,仅当 A则 B”是 B→A 。
p,我有时间。 q,天不下雨。 r,我将去镇上。
故命题可符号化为,r→(p∧q) 。
例题：命题符号化
(4)张刚总是在图书馆看书，除非图书馆不开门或张刚生病。
对于,除非,,只要记住,,除非,是条件。
p,张刚在图书馆看书,q,图书馆不开门,r,张刚生病。
故命题可符号化为,﹁ (q∨r)→p 。
(5)风雨无阻，我去上学。
可理解为,不管是否刮风、是否下雨，我都去上学,。
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)) 的真值表。
p q r
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
q∧r
0
0
0
1
0
0
0
1
p→(q∧r)
1
1
1
1
0
0
0
1
┐( p→(q∧r))
0
0
0
0
1
1
1
0
本章作业习题一
1,9,14,15,18,19
