第一章 命题逻辑 这章是以“命题”为中心 主要讨论： 命题的表示、命题的演算 命题演算中的公式，及其应用 命题逻辑推理

1-1. 命题与命题的真值 本节主要讨论三个问题： 命题的概念 命题的真值 原子命题与复合命题

一. 命题的概念 Statement 命题 是一个能确定是真的或是假的判断。 （判断都是用陈述句表示） 例1-1.1 判定下面这些句子哪些是命题。 ⑴ 2是个素数。 ⑵ 雪是黑色的。 ⑶ 2010年人类将到达火星。 ⑷ 如果 a>b且b>c，则a>c 。(a、b、c是确定实数) ⑸ x+y<5 ⑹ 请打开书！ ⑺ 您去吗？ ⑴⑵⑶⑷是命题

二.命题的真值 Truth 一个命题所作的判断有两种可能：是正确的判 断或者是错误的判断。 所以一个命题的真值有两个：“真”或“假”。 真值为真:一个命题所作的判断与客观一致，则 称该命题的真值为真,记作T (True)。 真值为假:一个命题所作的判断与客观不一致， 则称该命题的真值为假,记作F (False)。 例1-1.1中(1)(4)的真值为真,(2)的真值为假, (3)暂 时不能定，等到2010年确定。

三. 简单命题与复合命题 简单命题 (原子命题)：由最简单的陈述句 构成的命题 (该句再不能分解成更简单的句 子了)。通常用大写英字母表示。 例1-1.1中的(1)、(2)、(3)是原子命题。 复合命题 (分子命题)：由若干个原子命题 构成的命题。 例1-1.1中的(4)是由三个原子命题 (a>b、b>c、a>c) 构成的复合命题。

1-2 联结词 Connectives 复合命题的构成：是用“联结词”将原 子命题联结起来构成的。 归纳自然语言中的联结词，定义了六个 逻辑联结词，分别是： (1) 否定“” (2) 合取“∧” (3) 析取“∨” (4) 异或“ ” (5) 蕴涵“” (6) 等价“”

一. 否定“” Negation 表示：“…不成立”，“不…”。 用于：对一个命题P的否定，写成P，并 读成“非P”。 F T T F

二. 合取“∧”Conjunction 表示：“并且”、“不但…而且...”、 “既…又 ...”、“尽管…还… ” 例1-2.2 P：小王能唱歌。 Q：小王能跳舞。 P∧Q：小王能歌善舞。 P∧Q读成P合取Q。 P∧Q的真值为真，当且 仅当P和Q的真值均为真。 P Q P∧Q F F F F T F T F F T T T

三. 析取“∨”、异或“ ” 表示“或者” “或者”有二义性，看下面两个例子： 例1-2.3. 灯泡或者线路有故障。 三. 析取“∨”、异或“ ” 表示“或者” “或者”有二义性，看下面两个例子： 例1-2.3. 灯泡或者线路有故障。 例1-2.4. 第一节课上数学或者上英语。 例3中的或者是可兼取的或。即析取“∨” 例4中的或者是不可兼取的或，也称之为异 或、排斥或。即“ ”。

1. 析取“∨” Disjunction P：灯泡有故障。 Q：线路有故障。 例3中的复合命题可 表示为：P∨Q，读 P Q P∨Q P∨Q的真值为F，当 且仅当P与Q均为F。 P Q P∨Q F F F F T T T F T T T T

2. 异或“ ” Exclusive OR P：第一节上数学。 Q：第一节上英语。 P Q P Q 例4中的复合命题 F F F F T T T F T T T F P Q的真值为F， 当且仅当P与Q的真值相同。

3.“异或”的另一种表示 异或是表示两个命题不可能同时都成立。 命题“第一节课上数学或者上英语。”可以解 释为： “第一节课上数学而没有上英语或者第一节课 上英语而没有上数学。” 于是有 P Q 与 (P∧Q)∨(Q∧P ) 是一样的。 实际应用中必须注意“或者”的二义性。

四.条件(蕴涵)“” Conditional (Implication) 表示“如果… ，则 …”，“只要… ，就 …”, “只有… , 才…” , “ …. , 仅当 … ” 例1-2.5： P表示：缺少水分。 Q表示：植物会死亡。 PQ：如果缺少水分，植物就会死亡。 PQ：也称之为蕴涵式，读成“P蕴涵 Q”， “如果P则Q”。也说成P是PQ 的 前件，Q是 PQ的后件。还可以说P是Q的 充分条件，Q是 P的必要条件。

关于充分条件和必要条件的说明： 充分条件：就是只要条件成立，结论就成立， 则该条件就是充分条件。 上例中，“缺少水分”就是“植物会死亡” 的充分条件。在自然语言中表示充分条件的词 有 ： 如果 …则… ，只要… 就…，若…则… 必要条件：就是如果该条件不成立，那么结论 就不成立, 则该条件就是必要条件。 上例中，“植物死亡”就是“缺少水分”的必 要条件(植物未死亡，一定不缺少水分)。 在自然语言中表示必要条件的词有 ： 只有 …才… ； 仅当…，… ; …, 仅当…。

PQ的真值为假，当且仅当P为真，Q为假。注意：当前件P为假时， PQ为T。 P Q PQ 小王借钱不还 我替他还 （我给小王担保） F F T F T T T F F T T T

} } 举例：令：P：天气好。 Q：我去公园。 1.如果天气好，我就去公园。 2.只要天气好，我就去公园。 3.天气好，我就去公园。 4.仅当天气好，我才去公园。 5.只有天气好，我才去公园。 6.我去公园，仅当天气好。 } PQ } QP 可见“”既表示充分条件（即前件是后件的充分 条件）；也表示必要条件（即后件是前件的必要条 件）。这一点要特别注意!!!它决定了哪个作为前 件，哪个作为后件。

五.双条件 (等价）“” “ ” Biconditional (Equivalence)   表示“当且仅当”、“充分且必要” 例1-2.6： P：⊿ABC是等边三角形。 Q：⊿ABC是等角三角形。 PQ ：⊿ABC是等边三角形当且仅当 它是等角三角形。

PQ的真值： PQ的真值为真，当且仅当P与Q的真值相同。 P Q PQ F F T F T F T F F T T T

本节小结： 要熟练掌握这六个联结词在自然语言中 所表示的含义以及它们的真值表的定义。 P Q T T T T F T T P Q P∧Q P∨Q PQ PQ F F F F F T T F T F T T T F T F F T T F F T T T T F T T P Q

特别要注意“或者”的二义性，即要区 分给定的“或”是“可兼取的或”还是 “不可兼取的或”。 特别要注意“”的用法，它既表示 “充分条件”也表示“必要条件”，即要 弄清哪个作为前件，哪个作为后件。 下面做练习

练习：填空 已知P∧Q为T，则P为( )，Q为( )。 已知P∨Q为F，则P为( )，Q为( )。 已知P为F，则P∧Q为( )。 已知P为T，则P∨Q为( )。 已知P∨Q为T，且P为F ，则Q为( )。 已知PQ为F，则P为( )，Q为( )。 已知P为F，则PQ为( )。 已知Q为T，则PQ为( )。 已知 PQ为F，则P为( )， Q为( )。

已知P为T， PQ为T，则Q为( )。 已知Q为T, PQ为T，则P为( )。 已知PQ为T，P为T , 则Q为( )。 已知PQ为F，P为T , 则Q为( )。 PP 的真值为( )。 PP 的真值为( )。

1-3 命题公式及命题符号化 一.常值命题与命题变元 常值命题：即是我们前面所说的命题。它是有 具体含义 (真值)的。例如：“3是素数。”就是 常值命题。 命题变元：用大写的英字母如P、Q等表示任何 命题。称这些字母为命题变元。 对命题变元作指派(给命题变元一个解释)：将 一个常值命题赋予命题变元的过程，或者是直接 赋给命题变元真值“T”或“F”的过程。 注意：命题变元本身不是命题，只有给它一个 解释，才变成命题。

二.合式公式 ( wff ) (well formed formulas) 1.定义： ⑴ 单个命题变元是个合式公式。 ⑵ 若A是合式公式，则A是合式公式。 ⑶ 若A和B是合式公式，则(A∧B)， (A∨B)， (AB)和(AB)都是合式公式。 ⑷ 当且仅当有限次地应用⑴，⑵，⑶所得到的 含有命题变元、联结词和括号的符号串是合 式公式。 注意这个定义是递归的。(1)是递归的基础， 由(1)开始，使用规则(2)(3) ，可以得到任意的合

这里所谓的合式公式可以解释为合法的 命题公式之意，也称之为命题公式，有时 也简称公式。 下面的式子不是合式公式： P∧Q， PR， P∨Q∧R 下面的式子才是合式公式： (P∧Q)，(PR)，((P∨Q)∧R) 按照合式公式定义最外层括号必须写。 约定：为方便，最外层括号可以不写。 上面的合式公式可以写成： P∧Q，PR，(P∨Q)∧R

2. 命题公式的真值表 (Truth Table) 一个命题公式不是复合命题，所以它没 有真值，但是给其中的所有命题变元作指 派以后它就有了真值。可以以表的形式反 应它的真值情况，例如命题 公式 (PQ)∨Q 的真值表如下所示：  P Q P PQ (PQ)∨Q F F T F F F T T T T T F F T T T T F T T

由于对每个命题变元可以有两个真值(T,F)被指 派，所以有n个命题变元的命题公式 A(P1,P2,…,Pn) 的真值表有2n行。 为有序地列出A(P1,P2,…,Pn)的真值表，可将F看 成0、T看成1，按二进制数次序列表。 如A(P,Q)的真值表可按照如下次序指派： 00(FF)，01(FT)，10(TF)，11(TT) 如A(P,Q,R)的真值表可按照如下次序指派： 0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 FFF FFT FTF FTT TFF TFT TTF TTT

A(P1,P2,…,Pn)的真值表，按照二进制数 00…0 00…01 00…010 … 1 …10 11…1 0 1 2 … 2n -2 2n -1 即按照十进制的0，1，2，…. ，2n -1的次序 进行指派列真值表。

例如列出P(QR)的真值表 P Q R QR P(QR) 000 F F F T T 001 F F T T T 010 F T F F T 011 F T T T T 100 T F F T T 101 T F T T T 110 T T F F F T 111 T T T T

三.命题符号化 所谓命题符号化，就是用命题公式的符 号串来表示给定的命题。 命题符号化的方法 1.首先要明确给定命题的含义。 2.对于复合命题，找联结词，用联结词 断句，分解出各个原子命题。 3.设原子命题符号，并用逻辑联结词联 结原子命题符号，构成给定命题的符号表 达式。

例1.说离散数学无用且枯燥无味是不对的。 P：离散数学是有用的。 Q：离散数学是枯燥无味的。 该命题可写成：  (P∧Q) 例2.如果小张与小王都不去，则小李去。 P：小张去。 Q：小王去。 R：小李去。 该命题可写成： (P∧Q)R 如果小张与小王不都去，则小李去。 该命题可写成： (P∧Q)R 也可以写成： (P∨Q)R

该命题可写成：(PQ)∧(PQ) 例3. 仅当天不下雨且我有时间，才上街。 P：天下雨。Q：我有时间。R：我上街。 分析：由于“仅当”是表示“必要条件” 的，既“天不下雨且我有时间”，是“我上 街”的必要条件。所以 该命题可写成： R(P∧Q) 例4.人不犯我，我不犯人；人若犯我，我 必犯人。 P：人犯我。Q：我犯人。 该命题可写成：(PQ)∧(PQ) 或写成： PQ P是Q的必要条件 P是Q的充分条件 P是Q的充分且必要条件

例5 .若天不下雨，我就上街；否则在家。 P：天下雨。Q ：我上街。R：我在家。 该命题可写成： (PQ)∧(P R). 注意：中间的联结词一定是“∧”，而不是 “∨”，也不是“ ”。 因为原命题表示：“天不下雨时我做什么，天下 雨我又做什么”的两种作法，其中有一种作法是假 的，则我说的就是假话，所以中间的联结词一定是 “∧ ”。 如果写成 (PQ)∨(P R)，就表明两种作法都 是假的时候，我说的才是假话。这显然不对。

实际上, 公式(PQ)∨(P R) 的真值总是真的。 因为当P为T时， (PQ)为T， 当P为F时， (PR)为T， 所以(PQ)∨(P R) 的真值总是真的。而例5中命 题的真值不是总是真的。 若写成(PQ) (P R)：则表示两种作法一个是 真 , 另一个是假时，才是真的。 例如当P为F，Q为F时，即天没下雨而我没上街。 此时此话是假话，虽然(PQ) 是F，而(P R) 的真值是“T”。于是 表达式 (PQ) (P R) 的真值却是“T”。 所以这个表达式也不对。

本节重点掌握： 列命题公式的真值表 将给定命题符号化 作业题： 第8页：（3） 第12页：（5）、（7） 第17页：（1）a)、d)

1-4 重言式与重言蕴涵式 Tautology, Tautological Implications 一.重言式(永真式)与矛盾式(永假式) 1.例子 P P∨P P∧P F T F T T F 可见不论P取什么真值P∨P 的真值总是为真， P∧P的真值总是为假。故称 P∨P为重言式(永 真式)，称P∧P为矛盾式(永假式)。

2 .重言式(矛盾式)定义 A(P1,P2,…,Pn) 是含有命题变元P1,P2,…, Pn的 命题公式，如不论对P1, P2 , …, Pn作任何指派, 都使得A(P1,P2,…, Pn) 为真(假)，则称之为重言 式(矛盾式), 也称之为永真式 (永假式)。 3.重言式的证明方法 方法1：列真值表。 方法2：公式的等价变换，化简成“T”。 方法3：用公式的主析取范式。 其中方法2 和方法3 我们在以后讨论。

方法1. 列真值表。 例如，证明 (P∧(PQ))Q 为重言式。 P Q PQ P∧(PQ) (P∧(PQ))Q F F T F T F T T F T T F F F T T T T T T 永真式的真值表的最后一列全是“T”。

4. 永真式的性质 1) 如果A是永真式，则A是永假式。 2) 如果A，B是永真式，则(A∧B)、(A∨B)、(AB)和(AB)也都是永真式。 3) 如果A是永真式，则A的置换例式也是永真式。 置换例式： A(P1,P2,…,Pn) 是含有命题变元 P1,P2,…, Pn的命题公式，如果用合式公式X替换某 个Pi(如果Pi在A(P1,P2,…,Pn) 中多处出现，则各处 均用X替换 )，其余变元不变，替换后得到新的公 式B，则称B是A(P1,P2,…,Pn) 的置换例式。

例如： 公式A：P∨(P∧((PQ)R)) 用(DE)替换A中P得到A的置换例式 B： (DE)∨((DE)∧(((DE)Q)R)) 如果A是永真式，例如A为P∨P，用 (DE)替换A中P，得到A的置换例式 B：  (DE)∨(DE) ， 显然B也是永真式。 如果可以断定给定公式是某个永真式的置 换例式的话，则这个公式也是永真式。

二.重言(永真)蕴涵式 有些重言(永真)式，如(P∧(PQ))Q， 公式中间是“”联结词，是很重要的， 称之为重言蕴涵式。 1.定义：如果公式AB是重言式，则称A重 言(永真)蕴涵 B，记作AB。 上式可以写成 (P∧(PQ))Q 注意符号“”不是联结词，它是表示公 式间的“永真蕴涵”关系，也可以看成是 “推导”关系。即AB可以理解成由A可推 出B，即由A为真，可以推出B也为真。

2.重言(永真)蕴涵式证明方法 方法1.列真值表。(即列永真式的真值表) 这里就不再举例了。 下面讨论另外两种方法。 先看一看AB的真 A B A B F F T F T T T F F T T T 先看一看AB的真 值表，如果AB为 永真式，则真值表 的第三组指派不会 出现。于是有下面 两种证明方法。

方法2.假设前件为真，推出后件也为真。 例如求证： ((A∧B)C)∧D∧(C∨D)  A∨B 证明:设前件((A∧B)C)∧D∧(C∨D) 为 真。则((A∧B)C)、D、(C∨D)均真， D为T，则D为F 得C为F C∨D为T 得A∧B为F ((A∧B)C为T 如果A为F，则A为T，所以A∨B为T。 如果B为F，则B为T，所以A∨B 为T。 ((A∧B)C)∧D∧(C∨D)  A∨B

方法3.假设后件为假，推出前件也为假。 例如求证： ((A∧B)C)∧D∧(C∨D)  A∨B 证明:假设后件A∨B为F,则A与B均为T。 1.如C为F，则(A∧B)C为F，所以前件 ((A∧B)C)∧D∧(C∨D) 为F 2.如C为T，则⑴若D为T，则D为F，所以 前件((A∧B)C)∧D∧(C∨D) 为假 ⑵若D为F，则C∨D为F，所以 前件((A∧B)C)∧D∧(C∨D) 为假。 ((A∧B)C)∧D∧(C∨D)  A∨B

3.重要的重言蕴涵式(如教材第43页所示) I1.P∧QP I2. P∧QQ I3. PP∨Q I4. QP∨Q I5. PPQ I6. QPQ I7. (PQ)P I8. (PQ)Q I9. P,Q P∧Q I10. P∧(P∨Q)Q I11. P∧(PQ)Q I12. Q∧(PQ)P I13. (PQ)∧(QR)PR I14. (P∨Q)∧(PR)∧(QR)R I15. AB (A∨C)(B∨C) I16. AB (A∧C)(B∧C)

上述公式的证明都比较简单，可以用假设前件为 T，推出后件也为T的方法证明。 4. 性质 1) 有自反性：对任何命题公式A，有AA 2) 有传递性：若AB且BC，则AC 3) 有反对称性：若AB且BA，则AB 符号“”表示“等价”。 本节重点掌握：永真式及永真蕴涵式的定义、证 明方法、以及常用的公式。 作业：第23页: (2) b) 、(6)、(8) e)

1-5 等价公式 Equivalent Formulas 1. 例子 看下面三个公式的真值表 P Q PQ P∨Q QP F F T T T F T T T T T F F F F T T T T T 从真值表可以看出，不论对P、Q作何指 派，都使得PQ、P∨Q和QP的真 值相同，表明它们之间彼此等价。

2. 定义：A、B是含有命题变元P1,P2,…, Pn 的命题公式，如不论对P1, P2 , …, Pn作任何 指派，都使得A和B的真值相同，则称之为 A与B等价，记作AB。 显然 PQP∨QQP 3. 重要的等价公式 ⑴ 对合律 PP ⑵ 幂等律 P∨PP P∧PP ⑶ 结合律 P∨(Q∨R)(P∨Q)∨R P∧(Q∧R)(P∧Q)∧R ⑷交换律 P∨QQ∨P P∧QQ∧P

⑸分配律 P∨(Q∧R)(P∨Q)∧(P∨R) ⑹ 吸收律 P∨(P∧Q)P P∧(P∨Q)P ⑺底-摩根定律 (P∨Q)P∧Q (P∧Q)P∨Q ⑻ 同一律 P∨FP P∧TP ⑼ 零律 P∨TT P∧FF ⑽ 互补律 P∨PT P∧PF ⑾ PQP∨Q ⑿ PQQP ⒀ PQ (PQ)∧(QP) ⒁ PQ (P∨Q)∧(P∨Q) ⒂ PQ (P∧Q)∨(P∧Q )

为便于记忆，将等价公式(前10个)与集合论的公式比较，请看集合公式： ⑴ 对合律 ~~AA ~A表示A的绝对补集 ⑵ 幂等律 A∪AA A∩AA ⑶ 结合律 A∪(B∪C)(A∪B)∪C A∩(B∩C)(A∩B)∩C ⑷交换律 A∪BB∪A A∩BB∩A ⑸分配律 A∪(B∩C)(A∪B)∩(A∪C) A∩(B∪C)(A∩B)∪(A∩C) ⑹ 吸收律 A∪(A∩B)A A∩(A∪B)A ⑺底-摩根定律 ~(A∪B)~A∩~B ~(A∩B)~A∪~B ⑻ 同一律 A∪ΦA A∩EA E表示全集 ⑼ 零律 A∪EE A∩ΦΦ ⑽ 互补律 A∪~AE A∩~AΦ

4. 等价公式的证明方法 方法1：用列真值表。（不再举例） 方法2：用公式的等价变换.(用置换定律) 置换定律:A是一个命题公式，X是A中的一 部分且也是合式公式(A的子公式)，如果 XY，用Y代替A中的X得到公式B，则AB。 应用置换定律以及前面列出的等价公式 可以对给定公式进行等价变换。

例题1. 求证吸收律 P∧(P∨Q)P 证明 P∧(P∨Q)  (P∨F)∧(P∨Q) (同一律) P∨(F∧Q) (分配律) P∨F (零律) P (同一律)

例题2. 求证 (P∨Q)→(P∧Q) P 证明 (P∨Q)→(P∧Q) (P∨Q)∨(P∧Q) (公式E16)  (P∧Q)∨(P∧Q) (摩根定律)  (P∧Q)∨(P∧Q) (对合律) P∧(Q∨Q) (分配律) P∧T (互补律) P (同一律) 公式E16 ： PQP∨Q

例题3.化简(P∧Q)→(P∨(P∨Q)) 解： 原公式 (P∧Q)∨((P∨P)∨Q) (E16,结合) (P∧Q)∨(P∨Q) (对合律，幂等律) (P∧Q)∨(Q∨P) (交换律) ((P∧Q)∨Q)∨P (结合律) Q∨P (吸收律) 吸收律 P∨(P∧Q)P P∧(P∨Q)P

5. 性质 1) 有自反性：任何命题公式A，有AA。 2) 有对称性：若AB，则BA 3) 有传递性：若AB且BC，则AC 4) 如果A(P1,P2,…,Pn)B(P1,P2,…,Pn)，则 A(P1,P2,…,Pn)B(P1,P2,…,Pn) 例 A(P,Q)P→Q B(P,Q)P∨Q 于是有 A(P,Q)B(P,Q) A(P,Q)P→Q B(P, Q)P∨Q 可见 A(P,Q)B(P, Q)

6.等价公式的对偶性 (Duality) 从前面列出的等价公式看出，有很多是 成对出现的。这就是等价公式的对偶性。 ⑴ 对偶式：在一个只含有联结词  、∨、 ∧的公式A中，将∨换成∧，∧换成∨，T 换成F，F换成T，其余部分不变，得到另 一个公式A*，称A与A*互为对偶式。 例如: A A* P P Q∧R Q∨R (P∨T)∧Q (P∧F)∨Q

⑵ 用对偶式求公式的否定 定理1-5.1 令A(P1,P2,…,Pn)是一个只含有 联结词  、∨、∧的命题公式，则 A(P1,P2,…,Pn)A*(P1,P2,…,Pn) 此定理可以反复地使用底-摩根定律得以 证明。 下面我们验证一下。 令 A(P,Q)P∨Q A*(P,Q)P∧Q A(P,Q)(P∨Q) A*(P, Q)P∧Q 可见 A(P,Q)A*(P,Q) 推论:A(P1,P2,…,Pn)A*(P1,P2,…,Pn)

例如，利用上述求公式的否定公式求 (((P∧Q)∨(P∧Q))∨R) ((P∨Q)∧(P∨Q))∧R

⑶对偶原理(定理1-5.2)： 令A(P1,P2,…,Pn) 、B(P1,P2,…,Pn)是只含有 联结词、∨、∧的命题公式，则如果 A(P1,P2,…,Pn)B(P1,P2,…,Pn) 则 A*(P1,P2,…,Pn)B*(P1,P2,…, Pn) 证明：因为 A(P1,P2,…,Pn)B(P1,P2,…,Pn) 故 A(P1,P2,…,Pn)B(P1,P2,…,Pn) 而 A(P1,P2,…,Pn)A*(P1,P2,…,Pn) B(P1,P2,…,Pn)B*(P1,P2,…,Pn) 故 A*(P1,P2,…,Pn) B*(P1,P2,…,Pn) 所以 A*(P1,P2,…,Pn)B*(P1, P2,…, Pn)

下面我们验证一下对偶原理： P∨(Q∧R)(P∨Q)∧(P∨R) A B P∧(Q∨R)(P∧Q)∨(P∧R) A* B* P∨T T P∧F F A* B* 本节要求掌握等价公式的证明方法及记忆公式。 作业：第19页 (7) f) g) , (8) c)

1-6.范式 Normal Form 范式就是命题公式形式的规范形式。这里 约定在范式中 只含有联结词、∨和∧。 一.析取范式与合取范式 1.合取式与析取式 合取式：是用“∧”联结命题变元或变元的 否定构成的式子。 如 P 、P 、P∧Q、P∧Q∧R 析取式：是用“∨” 联结命题变元或变元 的否定构成的式子。 如 P 、P 、P∨Q、P∨Q∨R 注:∵ P∨PP P∧PP ∴P是合(析)取式.

2.析取范式 公式A如果写成如下形式： A1∨A2∨...∨An (n≥1) 其中每个Ai (i=1,2,…,n)是合取式，称之为A的析取范式。 3.合取范式 A1∧A2∧...∧An (n≥1) 其中每个Ai (i=1,2,…,n)是析取式，称之为A的合取范式。 例如，PQ 的析取范式与合取范式： PQ (P∧Q)∨(P∧Q)----析取范式 PQ (P∨Q)∧(P∨Q)----合取范式

4.析取范式与合取范式的写法 ⑴先用相应的公式去掉和。 公式E16 PQP∨Q 公式E21 PQ (P∧Q)∨(P∧Q) 公式E20 PQ (PQ)∧(QP) 再用E16 PQ (P∨Q)∧(P∨Q) ⑵用公式的否定公式或摩根定律将后移到命题 变元之前。 A(P1,P2,…,Pn)A*(P1,P2,…,Pn) 底-摩根定律 (P∨Q)P∧Q (P∧Q)P∨Q ⑶用分配律、幂等律等公式进行整理，使之成 为所要求的形式。

例如求(PQ)R的析取范式与合取范式 ((P∨Q)∧(P∨Q))∨R 去  (P∧Q)∨(P∧Q)∨R 后移 ---析取范式 ((P∧Q)∨(P∧Q))∨R 去   ((P∨Q)∧(P∨Q))∨R 后移 (P∨Q∨R)∧(P∨Q∨R) 分配律 ---合取范式

二.主析取范式与主合取范式 一个公式的析取范式与合取范式的形式是不唯 一的。下面定义形式唯一的主析取范式与主合取 范式。 ㈠主析取范式 1.小项 Minterms ⑴定义：在一个有n个命题变元的合取式中， 每个变元必出现且仅出现一次，称这个合取式是 个小项。 例如，有两个变元的小项： P∧Q、P∧Q、 P∧Q、 P∧Q

⑵小项的性质 m3 m2 m1 m0 P Q P∧Q P∧Q P∧Q P∧Q 00 F F F F F T 01 F T F F T F 10 T F F T F F 11 T T T F F F a).有n个变元，则有2n个小项。 b).每一组指派有且只有一个小项为T。 为了记忆方便，可将各组指派对应的为T的小项 分别记作m0,m1,m2,…,m2n-1 上例中 m0P∧Q m1P∧Q m2P∧Q m3P∧Q

2.主析取范式定义 析取范式 A1∨A2∨...∨An, , 其中每个Ai (i=1,2,…,n)都是小项，称之为主析取范式。 3.主析取范式的写法 方法Ⅰ：列真值表 ⑴ 列出给定公式的真值表。 ⑵ 找出真值表中每个“T”对应的小项。 根据一组指派写对应的为“T”的小项： 如变元P被指派为T，P在小项中以P形式出现； 如变元P被指派为F，P在小项中以P形式出现。 (要保证该小项为T))。 ⑶ 用“∨”联结上述小项，即可。

例如求 PQ和PQ的主析取范式 P Q PQ PQ F F T T F T T F T F F F T T T T PQ m0∨m1∨m3 (P∧Q)∨(P∧Q)∨(P∧Q) PQm0∨m3  (P∧Q)∨(P∧Q) 思考题:永真式的主析取范式是什么样 ？

方法Ⅱ：用公式的等价变换 ⑴ 先写出给定公式的析取范式 A1∨A2∨...∨An 。 ⑵ 为使每个Ai都变成小项，对缺少变元的Ai 补全变元，比如缺变元R，就用∧联结永真 式(R∨R)形式补R。 ⑶ 用分配律、幂等律等公式加以整理。 PQP∨Q (P∧(Q∨Q))∨((P∨ P)∧ Q) (P∧Q)∨(P∧Q)∨(P∧Q)∨(P∧Q) (P∧Q)∨(P∧Q)∨(P∧Q)

㈡主合取范式 1.大项 Maxterms ⑴定义:在有n个命题变元的析取式中，每 个变元必出现且仅出现一次,称之为大项。 例如，有两个变元的大项及其真值表： M0 M1 M2 M3 P Q P∨Q P∨Q P∨Q P∨Q F F F T T T F T T F T T T F T T F T T T T T T F

⑵大项的性质 a).有n个变元，则有2n个大项。 b).每一组指派有且只有一个大项为F。 为了记忆方便，可将各组指派对应的为F 的大项分别记作M0,M1,M2,…,M2n-1 。 上例中 M0 P∨Q M1 P∨Q M2  P∨Q M3 P∨Q

2.主合取范式定义 合取范式 A1∧A2∧... ∧An, , 其中每个Ai (i=1,2,…,n)都是大项，称之为主合取范式。 3.主合取范式的写法 方法Ⅰ：列真值表 ⑴ 列出给定公式的真值表。 ⑵ 找出真值表中每个“F”对应的大项。 根据一组指派写对应的为“F”的大项： 如变元P被指派为F，P在大项中以P形式出现； 如变元P被指派为T，P在大项中以P形式出现。 (确保该大项为F)。 ⑶ 用“∧”联结上述大项，即可。

例如求 PQ和PQ的主合取范式 P Q PQ PQ F F T T F T T F T F F F T T T T PQ M2  P∨Q PQ M1∧M2  (P∨Q )∧(P∨Q)

课堂练习： 1.已知A(P,Q,R) 的真值表如图： 求它的主析取 和主合取范式。 2.已知A(P,Q,R)的主析取范式中含有小项m1, m3, m5, m7 求它的主合取范式。 3.已知A(P1,P2,…,Pn)的主合取范式中含有k个大 项，问它的主析取范式中有多少个小项？ P Q R A(P,Q,R) F F F T F F T F F T F F F T T T T F F T T F T F T T F T T T T T

练习答案： 1.A(P,Q,R)的主析取范式: A(P,Q,R) m0∨m3∨m4∨m6∨m7 (P∧Q∧R)∨(P∧Q∧R)∨ (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q ∧R) A(P,Q,R)的主合取范式： A(P,Q,R) M1∧M2∧M5 (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) 2. A(P,Q,R) M0∧M2∧M4 ∧M6 (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) ∧(P∨Q∨R) 3. A(P1,P2,…,Pn)的主析取范式中含有2n-k个小项.

方法Ⅱ：用公式的等价变换 ⑴先写出给定公式的合取范式 A1∧A2∧...∧An 。 ⑵为使每个Ai变成大项，对缺少变元的析取 式Ai补全变元，比如缺变元R，就用∨联结 永假式(R∧R)形式补R。 ⑶用分配律、幂等律等公式加以整理。

例如，求(PQ)R的主合取范式 (PQ)R (P∨Q)∨R (P∧Q)∨R (P∨R)∧(Q∨R)  (P∨(Q∧Q)∨R)∧((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)

三.范式的应用 范式在逻辑设计方面有广泛的应用。 例1. 加法器的设计，有两个n位二进制数a,b相加和为s(s=a+b)，a,b分别写成： a=an an-1…ai ... a2a1, + b=bn bn-1…bi ... b2b1 cn cn-1cn-2 …ci-1…c1 s= cn sn sn-1…si … s2 s1 其中si是第i位ai、bi及ci-1 (ci-1是第i-1位向第i位的 进位) 的和，si是ai、bi及ci-1的函数, 进位ci也是ai 、 bi及ci-1的函数, 分别写成si(ai,bi,ci-1)，ci(ai,bi,ci-1)。 它们与ai,bi,ci-1的关系如下表：

ai bi ci-1 si(ai,bi,ci-1) ci(ai,bi,ci-1) 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1

根据前边的表,列出si(ai,bi,ci-1)的主析取范式： 在电路逻辑设计中用如下逻辑部件： 非门 与门 或门 a b a∧b a∨b a 根据前边的表,列出si(ai,bi,ci-1)的主析取范式： si(ai,bi,ci-1)=(ai∧bi∧ci-1)∨(ai∧bi∧ci-1)∨ (ai ∧bi∧ci-1)∨(ai∧bi∧ci-1) 类似可以求出进位位ci(ai,bi,ci-1)的表达式。 (在指派001、010、100、111时si为1) 下面设计出si(ai,bi,ci-1)的线路图。

ai∧bi∧ci-1 ai ai ai∧bi∧ci-1 bi bi si(ai,bi,ci-1) ci-1 ai ∧bi∧ci-1 Ci-1 ai∧bi∧ci-1 si(ai,bi,ci-1)=(ai∧bi∧ci-1)∨(ai∧bi∧ci-1)∨ (ai ∧bi∧ci-1)∨(ai∧bi∧ci-1) ci(ai-1,bi-1,ci-2)的线路图与之类似。

a: s: b: S=cn sn sn -1… s2 s1 a与b的和s的图：由n个si的图与n个ci的图合并而成。 a1 a2 an …… cn sn cn-1 sn-1 c2 s2 c1 s1 s: …… b1 b2 bn-1 bn …… b: S=cn sn sn -1… s2 s1

例2. 安排课表，教语言课的教师希望将课 程安排在第一或第三节；教数学课的教师 希望将课程安排在第二或第三节；教原理 课的教师希望将课程安排在第一或第二节。 如何安排课表，使得三位教师都满意。 令L1、L2、L3分别表示语言课排在第一、 第二、第三节。 M1、M2、M3分别表示数学课排在第一、 P1、P2、P3分别表示原理课排在第一、

三位教师都满意的条件是： (L1∨L3)∧(M2∨M3)∧(P1∨P2 ) 为真。 将上式写成析取范式(用分配律)得： ((L1∧M2)∨(L1∧M3)∨(L3∧M2)∨ (L3∧M3))∧(P1∨P2) (L1∧M2∧P1)∨(L1∧M3∧P1)∨ (L3∧M2∧P1)∨(L3∧M3∧P1)∨ (L1∧M2∧P2)∨(L1∧M3∧P2)∨ (L3∧M2∧P2)∨(L3∧M3∧P2) 可以取(L3 ∧M2∧P1)、(L1∧M3∧P2)为T， 得到两种排法。

本节要掌握： 析取范式、合取范式、主析取范式、主合取范式的写法。 范式的应用。 作业 第39页：(2) d) , (3) d) , (4) d) , (7)

1-7. 命题逻辑推理 一.推理 推理就是根据一个或几个已知的判断得出一个 新的判断的思维过程。 称这些已知的判断为前提。得到的新的判断为 前提的有效结论。 实际上，推理的过程就是证明永真蕴含式的过 程，即令H1，H2，…，Hn是已知的命题公式(前 提)，若有 H1∧H2∧....∧Hn  C 则称C是H1，H2，…Hn的有效结论，简称结论。

规则P(引入前提规则)：在推理过程中，可以随时引入前提。 如何根据前提得到结论，需要有推理的规则。 二.推理规则 规则P(引入前提规则)：在推理过程中，可以随时引入前提。 规则T(引入结论规则)：在推理过程中，如果前边有一个或几个公式永真蕴涵公式S，则可将S纳入 推理过程中。 在推理过程中，还要应用教材43页表1-8.3中的 永真蕴涵式I1-I16和表1-8.4中等价公式E1-E22 (常用的公式要熟记) 下面主要介绍三种推理方法： 直接推理、条件论证及反证法

重要的重言蕴涵式(如教材第43页所示) I1.P∧QP I2. P∧QQ I3. PP∨Q I4. QP∨Q I5. PPQ I6. QPQ I7. (PQ)P I8. (PQ)Q I9. P,Q P∧Q I10. P∧(P∨Q)Q I11. P∧(PQ)Q I12. Q∧(PQ)P I13. (PQ)∧(QR)PR I14. (P∨Q)∧(PR)∧(QR)R I15. AB (A∨C)(B∨C) I16. AB (A∧C)(B∧C)

重要的等价公式: 对合律 E1 PP 交换律 E2 P∧QQ∧P E3 P∨QQ∨P 结合律 E4 P∧(Q∧R)(P∧Q)∧R E5 P∨(Q∨R)(P∨Q)∨R 分配律 E6 P∧(Q∨R)(P∧Q)∨(P∧R) E7 P∨(Q∧R)(P∨Q)∧(P∨R) 底-摩根定律 E8 (P∧Q)P∨Q E9 (P∨Q)P∧Q 幂等律 E10 P∨PP E11 P∧PP 同一律 E12 P∨FP E13 P∧TP 零律 E14 P∨TT E15 P∧FF E16 PQP∨Q E17  ( PQ)P∧Q E18 PQQP E19 P(QR)(P∧Q)R E20 PQ (PQ)∧(QP) E21 PQ (P∧Q)∨(P∧Q ) E22 (PQ) PQ 吸收律 P∨(P∧Q)P P∧(P∨Q)P 互补律 P∨PT P∧PF PQ (P∨Q)∧(P∨Q)

三.直接推理 直接推理：就是从前提直接推出结论。 上面讲到推理的过程实际上是证明永真 蕴含式的过程。只不过证明的过程采用另 外一种书写格式。 格式中包含：步骤号；给定前提或得出 的结论；推理时所用规则；此结论是从哪 几步得到的以及所用公式。 下面请看一些例子。

例题１求证 P→Q，Q→R，P  R 证明 (1) P P (2) PQ P (3) Q T (1)(2) I11 (4) Q→R P 序号 前提或结论 所用规则 从哪几步得到 所用公式 (1) P P (2) PQ P (3) Q T (1)(2) I11 (4) Q→R P (5) R T (3)(4) I11 （注公式I11为： P,P→Q  Q ）

例题２求证 (P∧Q)∧(Q∨R)∧R  P (1) Q∨R P (2) R P (3) Q T (1)(2) I10 (4) (P∧Q) P (5) P∨Q T (4) E8 (6) P T (3)(5) I10 公式I10为：  P, P∨Q  Q 公式E8为： (P∧Q)P∨Q

例题３ 用命题逻辑推理方法证明下面推理 的有效性： 如果我学习，那么我数学不会不及格。如 果我不热衷于玩朴克，那么我将学习。但 是我数学不及格。因此，我热衷于玩朴克。 解:设 P：我学习。 Q：我数学及格。 R：我热衷于玩朴克。 于是符号化为： P→Q，R→P，Q  R

P→Q，R→P，Q  R (1) P→Q P (2) Q P (3) P T (1)(2) I12 (4) R→P P (5) R T (3)(4) I12 (6) R T (5) E1 注：公式I12为： Q，P→Q  P 公式E1 为： RR 下面同学动手作练习 第46页 (1) b)

第46页 (1) b) J→(M∨N)，(H∨G)→J，H∨G  M∨N (1) H∨G P (2)(H∨G)→J P (3) J T (1)(2) I11 (4) J→(M∨N) P (5) M∨N T (3)(4) I11

例题４求证P→(Q→S),R∨P,Q R→S 证明(1) P→(Q→S) P (2) P∨(Q∨S) T (1) E16 (3) P∨(S∨Q) T (2) E3 (4) (P∨S)∨Q T (3) E5 (5) Q P (6) P∨S T (4)(5) I10 (7) P→S T (6) E16 (8) R∨P P (9) R→P T (8) E16 (10) R→S T (7)(9) I13

四.条件论证 定理1-7.1 如果H1∧H2∧...∧Hn∧RＳ， 则 H1∧H2∧...∧Hn  R→S 证明：因为H1∧H2∧...∧Hn∧ＲＳ 则 (H1∧H2∧...∧Hn∧R)S 是永真式。 根据结合律得 ((H1∧H2∧...∧Hn)∧R)→S 是永真式。根据公式E19得 (H1∧H2∧...∧Hn)(R→S)是永真式。 即 H1∧H2∧...∧Hn  R→S 定理得证。E19: P(Q→R)(P∧Q)→R

此定理告诉我们，如果要证明的结论是 蕴涵式(R→S)形式，则可以把结论中蕴涵 式的前件R作为附加前提，与给定的前提一 起推出后件S即可。 我们把上述定理写成如下规则： 规则CP( Conditional Ｐroof)： 如果H1∧H2∧...∧Hn∧R  S，则 H1∧H2∧...∧Hn  R→S 下面我们用条件论证方法求证例题４ P→(Q→S),R∨P,Q  R→S

例题５ 用条件论证，证明例题４ P→(Q→S),R∨P,Q  R→S 证明 (1) R P(附加前提) (2) R∨P P (3) P T (1)(2) I10 (4) P→(Q→S) P (5) Q→S T (3)(4) I11 (6) Q P (7) S T (5)(6) I11 (8) R→S CP 与例题４相比，因为它增加了一个附加前提，所 以推理就容易些。

例题６ 用命题逻辑推理方法证明下面推理 的有效性： 如果体育馆有球赛,青年大街交通就拥挤。 在这种情况下，如果小王不提前出发，就会 迟到。因此，小王没有提前出发也未迟到， 则体育馆没有球赛。 证明 先将命题符号化。 设 P：体育馆有球赛。 Q：青年大街交通拥挤。 R：小王提前出发。 S：小王迟到。 P→Q，(Q∧R)→S (R∧S)→P

P→Q，(Q∧R)→S (R∧S)→P 证明 (1) R∧S P(附加前提) (2) R T (1) I1 (3) S T (1) I2 (4) (Q∧R)→S P (5) (Q∧Ｒ) T(3)(4) I12 (6) Q∨R T (5) E8 (7) Q T (2)(6) I10 (8) P→Q P (9) P T (7)(8) I12 (10)(R∧S)→P CP

下面同学动手作练习 用条件论证证明 第47页 (2) a) A∨B, C→B  A→C 证明 (1) A P(附加前提) (2) A∨B P (3) B T (1)(2) I10 (4) C→B P (5) C T (3)(4) I12 (6) A→C CP

五.反证法 反证法的主要思想是：假设结论不成立，可以 推出矛盾的结论(矛盾式)。 下面先介绍有关概念和定理。 定义：设H1，H2，...，Hn是命题公式，P1，P2, …,Pm是公式中的命题变元，如果对所有命题变元 至少有一种指派，使得H1∧H2∧...∧Hn 的真值 为T，则称公式集合{H1,H2,…Hn}是相容的(也称 是一致的)；如果对所有命题变元每一种指派， 都使得H1∧H2∧...∧Hn的真值为F，则称公式集 合{H1,H2,…Hn}是不相容的(也称是不一致的)。

定理1-7.2 若要证明相容的公式集合 {H1,H2,... Hn}可以推出公式C，只要证明 H1∧H2∧...∧Hn∧C是个矛盾式即可。 证明 设H1∧H2∧...∧Hn∧C 是矛盾式，则 (H1∧H2∧...∧Hn∧C)是个永真式。 上式 (H1∧H2∧...∧Hn)∨C (H1∧H2∧...∧Hn)→C 所以 H1∧H2∧...∧Hn  C 实际上，要证明H1∧H2∧...∧Hn  C，只要证明 H1∧H2∧...∧Hn∧C可推出矛盾式即可，即 H1∧H2∧...∧Hn∧C  R∧R

例７ P→Q,(Q∨R)∧R, (P∧S)S (1) S P(假设前提) (2) S T (1) E1 (3) (P∧S) P (4) P∨S T (3) E8 (5) P T (2)(4) I10 (6) P→Q P (7) Q T (5)(6) I11 (8) (Q∨R)∧R P (9) Q∨R T (8) I1 (10) R T (8) I2 (11) R T (7)(9) I10 (12) R∧R T (10)(11) I9

下面同学动手作练习 用反证法证明 第47页 (4) a) R→Q , R∨S , S→Q ,P→Q  P 证明 (1) P P(假设前提) (2) P T (1) E1 (3) P→Q P (4) Q T (2) (3) I11 (5) R→Q P (6) R T (4) (5) I12 (7) R∨S P (8) S T (6) (7) I10 (9) S→Q P (10) Q T (8) (9) I12 (11) Q∧Q T (4) (10) I9

本节要掌握三种推理方法，按照所要求格式正确地书写推理过程。 作业 第47页：(1) b) , (2) b) , e) (3) b) , c) (4) a) , c) (5) c)

*1-8 联结词的全功能集(完备集) 前面定义了六个逻辑联结词，分别是： (1)否定“” (2) 合取“∧” (1)否定“” (2) 合取“∧” (3) 析取“∨” (4) 异或“ ” (5) 蕴涵“” (6) 等价“” 可以用这些联结词表示任何命题公式。而且我们 已经知道，有些联结词可以用其它联结词表示。 比如：PQP∨Q P Q  (P∧Q)∨(P∧Q) PQ (P∧Q)∨(P∧Q) PQ (PQ)∧(QP) PQ (P∨Q)∧(P∨Q)

一. 与非, 或非 在逻辑设计中还定义两个联结词“与非”、“或 非”： 与非：设P、 Q是命题，复合命题“P∧Q的否定” 称为P与Q的与非，记作PQ， 称为与非联结词。 PQ (P∧Q) 或非：设P、 Q是命题，复合命题“P∨Q的否定” 称为P与Q的或非，记作PQ，称作或非联结词。 PQ (P∨Q) 在一个形式系统中定义多少个联结词“合适”？

二. 形式系统中联结词的个数问题 在自然推理系统中联结词可以多一些； 在公理系统中联结词越少越好。 公理系统(Axiomatic system):是数理逻辑的基本概 念。为了避免循环，数学中的概念的定义必须假 定有不加定义的原始概念（如几何中的“点”、“直 线”）。同样，数学中定理的证明，也必须假定有 不加证明的公理（如平行公理）。 在某个数学分支，由这些原始概念和一些公理 为依据，就得到该数学分支的公理系统。 这里就是讨论命题逻辑公理系统“最少”需要多 少个联结词。

联结词无论是多还是少，它必须具备一定功能， 就是用这些联结词能够表达所有的命题公式。那 么如何证明能表达所有命题公式呢？ 我们知道有很多公式表面形式不同，但是它们 的真值表相同，我们说它们是等价公式(即相同的 公式)，所以不同真值表的个数＝公式的个数。 有n个命题变元，共有2n个可能的赋值，对于每 个赋值命题公式的真值都有两个(T、F) ，于是可 以构成 个不同的真值表(命题公式)。 比如，有两个命题变元P、Q，可以构成24=16 个命题公式，如下F0, F1, …, F15所示：

实际上F0,是个矛盾式；F1,F2,F4 ,F8是只含有一个小 项的公式； F3,F5 ,F6 ,F9 ,F10,F12是含有二个小项的 P Q F0 F1 F2 F3 F4 F5 F6 F7 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 实际上F0,是个矛盾式；F1,F2,F4 ,F8是只含有一个小 项的公式； F3,F5 ,F6 ,F9 ,F10,F12是含有二个小项的 公式； F7, F11, F13,F14是含有三个小项的公式；F15 是含四个小项的公式。 P Q F8 F9 F10 F11 F12 F13 F14 F15 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1

下面就讨论公理系统“最少”需要多少个联结词。 三. 联结词的全功能集和极小全功能集 定义：在一个联结词集合中，如果一个联结词可 由集合中的其它联结词定义，则称此联结词是冗 余的联结词，否则称此联结词是独立的联结词。 如{, ∧, ∨, , }中与是冗余的, {, ∧, ∨}中∨也是冗余的, 因为P∨Q (P∧Q)， {, ∧}或者{,∨}中就无冗余的联结词。

定义：给定一个联结词集合，如果任何一个命题 公式都可以用此集合中的联结词表示，则称为此 联结词集合是全功能集。如果一个联结词的全功 能集中不含有冗余的联结词，则称它是极小全功 能集。 如{, ∧, ∨, ,  ,, } 、{, ∧, ∨, ,  } {, ∧, ∨}、{, ∧}、 {,∨}都是全功能集。 {, ∧}、 {,∨}是极小全功能集。 而{}{∧}{∧,∨}都不是全功能集。

在工程上有时需要考虑联结词最少的全功能集。 下面看看{}和{}是不是全功能集。就是 看看是否用“”或者“”表示, ∧, ∨： (1) PP( P∧P)  P (2) (PQ)(PQ)(PQ) (P∧Q) (3) (PP)(QQ)PQ (P∧Q )P∨Q 所以{}是个极小全功能集。 在数字逻辑中，就有“与非门”逻辑组件，只用 它就可以设计出任何逻辑线路。

再看 ： (1) PP( P∨P) P (2) (PP)(QQ)PQ(P∨Q) (P∧Q) (3) (PQ)(PQ) (PQ) P∨Q 所以{}也是个极小全功能集。 求证{, }是全功能集。因为 PQP∨Q (PQ)( P∨Q) P∧Q

第一章 小结 知识网络： 命 题 原子命题 复合命题 联结词 命题公式 永真式 永真蕴涵式 等价公式 范式 命题逻辑推理 条件论证 直接推理 第一章 小结 知识网络： 命 题 原子命题 复合命题 联结词 命题公式 析取 永真式 合取 永真蕴涵式 等价公式 范式 主析取 主合取 命题逻辑推理 条件论证 直接推理 间接推理 反证法

本章的重点内容、及要求： １.要熟练掌握联结词的真值表定义以及它们在自然语言 中的含义。其中特别要注意“∨”和“→”的用法。 ２.会命题符号化。 ３.掌握永真式的证明方法： (1).真值表。 (2).等价变换，化简成Ｔ。 (3).主析取范式。 ４.掌握永真蕴含式的证明方法，熟练记忆并会应用 43页中表1-8.3中的永真蕴含式。 ５.掌握等价公式的证明方法，熟练记忆并会应用 43页表1-8.4中的等价公式。 ６.熟练掌握范式的写法及其应用。 ７.熟练掌握三种推理方法。

下面上第一章的习题课

第一章 习题课 一.命题符号化 注意讲过的命题符号化方法。 P8习题(3) P:天下雪。Q:我将去镇上。R:我有时间。 第一章 习题课 一.命题符号化 注意讲过的命题符号化方法。 P8习题(3) P:天下雪。Q:我将去镇上。R:我有时间。 如果天不下雪且我有时间，那么我将去镇上。 (P∧R)→Q 只有天不下雪且我有时间，我才去镇上。 Q→(P∧R) b) 我将去镇上，仅当我有时间。 Q→R d) 天下雪，那么我不去镇上。 P→Q

P12习题(5) a) 或者你没有给我写信，或者它在途中丢失了。 显然这里的“或者”是“不可兼取的或”。 令 P:你给我写信。Q:信在途中丢失了。 表达式为: P Q 或 (P∧Q)∨(P∧Q) c) 我们不能既划船又跑步。 令 P:我们划船。Q:我们跑步。 表达式为 (P∧Q) d)如果你来了，那么他唱不唱歌将看你是否为他 伴奏而定。 令 P:你来了。Q:你为他伴奏。 R:他唱歌。 表达式为: P→((Q→R)∧(Q→R)) 也可以写成： P→(QR)

P12习题(7) a) 假如上午不下雨，我去看电影，否则就在家里 读书或看报。 令 P:上午下雨。 Q:我去看电影。 R:我在家里读书。S:我在家里看报。 表达式为: (P→Q)∧(P→(R S)) 不可以写成：(P→Q)∨(P→(R S)) (P→Q)∨(P→(R S)) (P∨Q)∨(P∨(R S)) (P∨Q)∨(P∨(R S)) P∨Q∨P∨(R S) P∨P ∨Q∨(R S) T

(A→B)∧(A→((C→E)∧(C→D))) 令 P:我今天进城。Q:今天下雨。 表达式为: Q→P c) 仅当你走我将留下。 令 P:你走。Q:我留下。 表达式为: Q→P 或者 P→Q 补充题：请将下面流程图 写成符号表达式 A C B D E T F 开始 (A→B)∧(A→((C→E)∧(C→D)))

P23 (2)证明(P→Q)→(P→(P∧Q))是重言式。 方法1: 二.重言式的证明方法 方法1：列真值表。 方法2：公式的等价变换，化简成“T”。 方法3：用公式的主析取范式。 P23 (2)证明(P→Q)→(P→(P∧Q))是重言式。 方法1: P Q P→Q P→(P∧Q) (P→Q)→(P→(P∧Q)) F F T T T F T T T T T F F F T T T T T T

方法2: (P→Q)→(P→(P∧Q)) (P∨Q)∨(P∨(P∧Q)) (E16) (P∧Q)∨((P∨P)∧(P∨Q)) 摩根，分配 (P∧Q)∨(T∧(P∨Q)) 互补 (P∧Q)∨(P∨Q) 同一 (P∨(P∨Q) )∧(Q∨(P∨Q) 分配 ((P ∨P)∨Q) )∧(Q∨(Q∨P) 结合、交换 (T∨Q) )∧((Q∨Q)∨P) 互补、结合 T∧(T∨P) 零律、互补  T∧T 零律  T 幂等

方法3 (P→Q)→(P→(P∧Q)) (P∨Q)∨(P∨(P∧Q)) 去→ (P∧Q)∨P∨(P∧Q) 后移 (P∧Q)∨(P∧(Q∨Q))∨(P∧Q) 补变元Q (P∧Q)∨(P∧Q)∨(P∧Q)∨(P∧Q) 分配  (P∧Q)∨(P∧Q)∨(P∧Q)∨(P∧Q)整理  m3∨m2∨m1∨m0 可见，该公式的主析取范式含有全部(四个)小项， 这表明(P→Q)→(P→(P∧Q))是永真式。

三.重言蕴涵式的证明方法 方法1.列真值表。(即列永真式的真值表) (略) 方法2.假设前件为真，推出后件也为真。 方法3.假设后件为假，推出前件也为假。 P12(8)e)证明 (A(B∨C) )∧(D∨E)∧((D∨E)A)  B∨C 方法2 证明： 设前件(A(B∨C) )∧(D∨E)∧((D∨E)A) 为真，则A(B∨C) , D∨E, (D∨E)A 均为 真。由D∨E, (D∨E)A 均为真用I11得A为真, 又由A(B∨C)为真，得B∨C为真。所以得

(A(B∨C) )∧(D∨E)∧((D∨E)A)B∨C 方法3 证明：设后件B∨C为 F，则 B与C均为 F， 1. 如果D∨E 为 T，则 1).若A为T，则A为F，则(D∨E)A为F，于是 前件(A(B∨C) )∧(D∨E)∧((D∨E)A)为F。 2). 若A为 F，则 A为T，于是A(B∨C) 为F， 故前件(A(B∨C) )∧(D∨E)∧((D∨E)A)为F。 2.如果D∨E 为 F，则 前件 (A(B∨C) )∧(D∨E)∧((D∨E)A) 为F。 综上所述

四. . 等价公式的证明方法 方法1：用列真值表。（不再举例） 方法2：用公式的等价变换.(用置换定律) P19(7)h)证明 ((A∧B)→C)∧(B→(D∨C))(B∧(D→A))→c 左式((A∧B)∨C)∧(B∨(D∨C)) E16 ((A∨B)∨C)∧(B∨(D∨C)) 摩根 ((B ∨A)∨C)∧((B∨D)∨C) 交换 结合 ((B ∨A)∧(B∨D))∨C 分配 (B ∨(A∧D))∨C 分配  (B∧(A∨D))∨C 摩根 (B∧(D→A))→C E16

P19(8)c)化简(A∧B∧C)∨(A∧B∧C） 上式 (A∨A)∧(B∧C） 分配 T∧(B∧C） 互补 B∧C 同一 提示：化简时注意使用下面使式子变短的公式： 分配律 E6 P∧(Q∨R)(P∧Q)∨(P∧R) E7 P∨(Q∧R)(P∨Q)∧(P∨R) 用分配律时，是提取公因式。 幂等律 E10 P∨PP E11 P∧PP 同一律 E12 P∨FP E13 P∧TP 零律 E14 P∨TT E15 P∧FF 吸收律 P∨(P∧Q)P P∧(P∨Q)P 互补律 P∨PT P∧PF

补充题3. 令P表示小张去，Q表示小李去，用最 简捷的语言说明下面公式 (Ｐ∧Ｑ)→(Ｐ∨(Ｐ∨Ｑ)) 表达的含义。 解 ：将上面公式化简 原公式 (Ｐ∧Ｑ)∨((Ｐ∨Ｐ)∨Ｑ) (Ｅ16，结合) (Ｐ∧Ｑ)∨(Ｐ∨Ｑ) (双否律，幂等律) (Ｐ∧Ｑ)∨(Ｑ∨Ｐ) (交换律) ((Ｐ∧Ｑ)∨Ｑ)∨ Ｐ (结合律) Ｑ∨ Ｐ (吸收律) Ｐ→Ｑ 上面公式表示：如果小张去，则小李也去。

P39(4)d)写出(P(Q∧R))∧(P(Q∧R))的主析取范式和主合取范式 五.范式的写法及应用 P39(4)d)写出(P(Q∧R))∧(P(Q∧R))的主析取范式和主合取范式 方法1，用真值表 令A(P,Q,R)(P(Q∧R))∧(P(Q∧R)) 它的真值 表见 下页。 A(P,Q,R)m0∨ m7 (P∧Q∧R)∨(P∧Q∧R) A(P,Q,R) M1∧M2∧M3∧M4∧M5∧M6 (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧ (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)

A(P, Q, R)的主析取范式中含有小项m0 , m7。 主合取范式中含有大项M1,M2 ,M3 ,M4 ,M5 ,M6 。 P Q R P(Q∧R) P(Q∧R ) A(P, Q, R) 0 F F F T T T 1 F F T T F F 2 F T F T F F 3 F T T T F F 4 T F F F T F 5 T F T F T F 6 T T F F T F 7 T T T T T T

方法2.等价变换 (P(Q∧R))∧(P(Q∧R))  (P∨(Q∧R))∧(P∨(Q∧R)) E16  (P∧P)∨(P∧Q∧R)∨ (P∧Q∧R)∨ ((Q∧R)∧(Q∧R)) 分配 F∨(P∧Q∧R)∨(P∧Q∧R)∨F 互补 (P∧Q∧R)∨(P∧Q∧R) 同一

(P(Q∧R))∧(P(Q∧R))  (P∨Q)∧(P∨R))∧(P∨Q)∧(P∨R)  (P∨Q∨(R∧R))∧(P∨(Q∧Q)∨R)) ∧(P∨Q∨(R∧R))∧(P∨(Q∧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))∧ (P∨Q∨R)∧(P∨Q∨R)∧ (P∨Q∨R)∧(P∨Q∨R)

范式的应用 P39(7)A,B,C,D四个人中要派两个人出差，按下述三个条 件有几种派法？ ①若A去则C和D中要去一个人。 ②B和C不能都去。 ③C去则D要留下。 解.设A,B,C,D分别表示A去，B去，C去，D去。 ①A((C∧D)∨(C∧D)) A∨ (C∧D)∨(C∧D) ② (B∧C) B∨C ③ CD C∨D 总的条件为： (A∨ (C∧D)∨(C∧D) )∧(B∨C) ∧(C∨D) 令此式为真。

将(A∨ (C∧D)∨(C∧D) )∧(B∨C) ∧(C∨D) 化成析取范式。 (C∨(B∧D)) (A∧C)∨ (C∧D∧C)∨(C∧D∧C)∨ (A∧B∧D)∨ (C∧D∧B∧D) ∨(C∧D∧B∧D) (A∧C)∨F∨(C∧D)∨(A∧B∧D)∨ (C∧D∧B)∨F 可以取A∧C为T，得B和D去。 取C∧D为T，得A和D去，或者 B和D去。 取C∧D∧B为T，得A和C去 。 最后得三种派法： A和C去、A和D去、B和D去。

*补充题：有工具箱A、B、C、D，各个箱内装的工具如 下表所示。试问如何携带数量最少工具箱，而所包含的 工具种类齐全。 解：设A、B、C、D分别表示带A、B、C、D箱。 则总的条件为： (A∨C)∧(A∨B∨D)∧(B∨C)∧(B∨D) 为真。 改锥 扳手 钳子 锤子 工具 箱 改 锥 扳 手 钳 子 锤 子 A 有 有 B 有 有 有 C 有 有 D 有 有

将(A∨C)∧(A∨B∨D)∧(B∨C)∧(B∨D)写成析取范式， 上式((A∨C)∧(B∨C))∧((A∨(B∨D))∧(B∨D)) (交换 ) ((A∧B)∨C))∧(B∨D) (分配(提取C)、吸收) (A∧B∧B )∨(C∧B )∨(A∧B∧D)∨(C∧D) (分配) (A∧B)∨(C∧B )∨(A∧B∧D)∨(C∧D) 分别可以取(A∧B)、(C∧B )、(C∧D)为真。 于是可以得到三种携带方法： 带A和B箱， 带B和C箱，带C和D箱。

六. 逻辑推理 熟练掌握三种推理方法。 P47(2)c) (A∨B)(C∧D), (D∨E)F  AF 1.直接推理 ⑴ (A∨B)(C∧D) P ⑵ (A∨B)∨(C∧D) T ⑴ E16 ⑶ (A∧B)∨(C∧D) T ⑵ E9 ⑷ (A∨C)∧(B∨C)∧(A∨D)∧(B∨D) T ⑶ E7 ⑸ A∨D T ⑷ I2 ⑹ AD T ⑸ E16 ⑺ (D∨E)F P ⑻ (D∨E)∨F T ⑺ E16 ⑼ (D∧E)∨F T ⑻ E9 ⑽ (D ∨F) ∧(E∨F) T ⑼ E7 ⑾ D∨F T ⑽ I1 ⑿ DF T ⑾ E16 ⒀AF T ⑹⑿ I13

P47(2)c) (A∨B)(C∧D), (D∨E)F  AF 2.条件论证 ⑴　A P (附加前提)　 ⑵ A∨B T ⑴ I3 ⑶ (A∨B)(C∧D) T ⑷ C∧D T ⑵⑶ I11 ⑸ D T ⑷ I2 ⑹ D∨E T ⑸ I3 ⑺ (D∨E)F P ⑻ F T ⑹⑺ I11 ⑼ AF CP 显然此方法比直接推理简单。

P47(2)c) (A∨B)(C∧D), (D∨E)F  AF 3.反证法 ⑴ (AF) P (假设前提) ⑵ (A∨F) T ⑴ E16 ⑶ A∧F T ⑵ E9 ⑷ A T ⑶ I1 ⑸ A∨B T ⑴ I3 ⑹ (A∨B)(C∧D) T ⑺ C∧D T ⑵⑶ I11 ⑻ D T ⑷ I2 ⑼ D∨E T ⑸ I3 ⑽ (D∨E)F P ⑾ F T ⑹⑺ I11 ⑿ F T ⑶ I2 ⒀ F∧F T ⑾ ⑿ I9 可见此法也比较简单

补充题：请根据下面事实，找出凶手： 1. 清洁工或者秘书谋害了经理。 2. 如果清洁工谋害了经理，则谋害不会发生在午夜前。 3.如果秘书的证词是正确的，则谋害发生在午夜前。 4.如果秘书的证词不正确，则午夜时屋里灯光未灭。 5. 如果清洁工富裕，则他不会谋害经理。 6.经理有钱且清洁工不富裕。 7.午夜时屋里灯灭了。 令A:清洁工谋害了经理。 B:秘书谋害了经理。 C:谋害发生在午夜前。 D:秘书的证词是正确的. E:午夜时屋里灯光灭了。H:清洁工富裕. G:经理有钱. 命题符号为： A∨B,AC,DC,DE,HA,G∧H,E ?

A∨B,AC,BC, DC DE,HA,G∧H,E ? ⑴ E P ⑵ DE P ⑶ D T ⑴⑵ I ⑷ D T ⑶ E ⑸ DC P ⑹ C T ⑷⑸ I ⑺ AC P ⑻ A T ⑹⑺ I ⑼ A∨B P ⑽ B T⑻⑼ I 结果是秘书谋害了经理。

第一章 命题逻辑 到此结束