复习（数理逻辑部分）

第1章 命题逻辑的基本概念

一：基本概念：

1.称能判断真假而不是可真可假的陈述句为命题。 2.真值为真的命题称为真命题。 3.真值为假的命题称为假命题。 4.简单命题(原子命题)。

5.由简单命题通过联结词而成的陈述句，称这样的命题为复合命题。 例1 判断下列句子是否为命题。

(1)4是素数。 (2)x大于y。

(3)充分大的偶数等于两个素数之和。 (4)北京是中国的首都。 (5)请不要吸烟！ (6)我正在说假话。

6.合式公式: 命题符号与联结词组成

不是合式公式的例子：pq→r；(p→(r→q) 7.公式的类型：重言式、永真式、可满足式 重言式(永真式)：都是1 矛盾式(永假式)：都是0 可满足式：有1，也有0 二. 联结词：

否定 ： ┐p 非p

合取： p∧q p并且q(或“p与q”) 析取： p∨q p或q

蕴涵： p→q 如果p，则q 等价： p?q p当且仅当q

本书规定的联结词优先顺序为：( )，┐，∧，∨，→， ?，对于同一优先级的联结词，先出现者先运算。

例2令 p：北京比天津人口多。 q：2+2＝4.

r：乌鸦是白色的。 求下列复合命题的真值： (1)(q∨r)→(p→┐r) (2)(┐p∨r)?(p∧┐r) 解：p、q、r的真值分别： 1、1、0

(1) 1 (2) 0

例3 求下列公式的真值表，并求成真赋值和成假赋值。判断公式类型 (1)(p∧┐p)?(q∧┐q) (2)(┐p∧q)→┐r (3)┐(p→q)∧q∧r 解：先做真值表

（1） 是永真式，00，01，10，11是成真赋值，没有成假赋值。 （2） 是可满足式，011是成假赋值，其余是成真赋值。 （3） 是永假式，都是成假赋值，没有成真赋值。

第2章 命题逻辑等值演算

一：验证两个公式是否等值： 方法一：真值表 方法二：等值演算

1.双重否定律 A ? ┐┐A 2.幂等律 A ? A∨A, A ? A∧A 3.交换律 A∨B ? B∨A， A∧B ? B∧A 4.结合律 (A∨B)∨C ? A∨(B∨C)

(A∧B)∧C ? A∧(B∧C) 5.分配律 A∨(B∧C) ? (A∨B)∧(A∨C) （∨对∧的分配律） A∧(B∨C) ? (A∧B)∨(A∧C) （∧对∨的分配律）

6.德·摩根律 ┐(A∨B) ? ┐A∧┐B ┐(A∧B) ? ┐A∨┐B

7.吸收律 A∨(A∧B) ? A，A∧(A∨B) ? A 8.零律 A∨1 ? 1,A∧0 ? 0 9.同一律 A∨0 ? A，A∧1 ? A 10.排中律 A∨┐A ? 1 11.矛盾律 A∧┐A ? 0 12.蕴涵等值式 A→B ? ┐A∨B 13.等价等值式 A?B ? (A→B)∧(B→A) 例1.用等值演算法验证等值式 (p∨q)→r ? (p→r)∧(q→r) 解：方法一：真值表

方法二：等值演算：(p→r)∧(q→r) ? (┐p∨r)∧(┐q∨r) (蕴含等值式) ? (┐p∧┐q)∨r (分配律) ? ┐(p∨q)∨r (德摩根律) ? (p∨q)→r (蕴含等值式) 二：基本概念（理解）：

1. 在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式不同时出现，而二者之一必出现且仅出现一次，称这样的简单合取式（简单析取式）为极小项（极大项）。

2. 定理2.4 设mi与Mi是命题变项p1,p2,…,pn形成的极小项和极大项，则 ┐mi ? Mi， ┐Mi ? mi

3. 极小项构成的析取范式称为主析取范式。 极大项构成的合取范式称为主合取范式。

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

表 p,q,r形成的极小项与极大项

三. 范式的求法（计算） 方法一、等值演算法

(1)消去联结词→、?(若存在)。 A→B ? ┐A∨B

A?B ? (┐A∨B)∧(A∨┐B)

(2)否定号的消去(利用德摩根律)。 (3)利用分配律：

A∧(B∨C) ? (A∧B)∨(A∧C)求析取范式， A∨(B∧C) ? (A∨B)∧(A∨C)求合取范式。 并化成极小（大）项.

(4)表示成主析取（合取）范式. 方法二、真值表法 (1)写出A的真值表，

(2)找出成真（假）赋值，得到极小（大）项， (3)表示成主析取（合取）范式.

例2 求命题公式 p→q 的主析取范式和主合取范式。 解：方法一：等值演算 (1)求主合取范式

p→q ? ┐p∨q ? M2 (2)求析取范式

p→q ? ┐p∨q ? （┐p∧（┐q∨q）） ∨ （(┐p∨p)∧q） ? (┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) ? (┐p∧┐q)∨(┐p∧q)∨(p∧q) ? m0∨m1∨m3 方法二：真值表 2.主析取范式：

成真赋值有：00，01，11

p 0 0 1 1

q 0 1 0 1

p →q

所以：p→q ? m0∨m1∨m3 3.主合取范式： 成假赋值：10

所以： p→q ? ┐p∨q ? M2

1 1 0 1

第3章 命题逻辑的推理理论

一.判断推理是否正确的方法：

? 真值表法 ? 等值演算法 ? 主析取范式法