命题逻辑

逻辑与推理

逻辑

--是研究人的思维的科学

1. 辩证逻辑：类似政治类的课程，思维中的辩证法

   具体问题具体分析

2. 形式逻辑：思维的形式和一般规律

   离散数学关心的是形式逻辑

   形式逻辑主要关注的是演绎推理

   概念（已知的事实） => 判断推理（客观规律和规则） => 推理（推出来的结论）

   概念清楚、判断正确

3. 数理逻辑：用数学方法研究形式逻辑

   数学方法：建立一套有严格定义的符号（），来研究形式逻辑

   又称为符号逻辑，通过符号系统

   我们这里只研究其中的命题逻辑和谓词逻辑

   命题逻辑，如

推理

推理：是有

推理方法：由个别事物推出个别结论。

• 类比推理：

• 归纳推理：由若干个个别事实推出一般结论。

  （类比和归纳推理是不严谨的）

• 演绎推理：由一般规律推出个别事实

1. 命题与命题的真值

问题

1. 命题的概念
2. 命题真值的概念
3. 命题的种类：原子命题、复合命题

命题

能确定是真的或是假的判断（到将来一个确切的时间点能确定是真是假的判断也是命题，如 2030 年人类讲到达火星，是命题）

x+y<5 不是命题、祈使句、疑问句等都不是（只有判断句才是）

真值：真或假

形式：原子命题，复合命题

• 原子命题（简单命题）：由最简单的陈述句构成的命题（不可再拆分的）。通常用大写英文字母表示，（一般写作大写字母）

  不包含任何联结词

• 复合命题（分子命题）：由若干个原子命题构成的命题（如若 a>b, b>c, 则 a>c 可以分成三个）

2. 联结词

否定、$\neg$

合取、$\wedge$，PQ 都为真才为真

既有...，又有...

不但...，还...

...并且...

虽然...，但是...

，

；

。

析取、$\vee$，PQ 都为假才为假

或者的意思（或者有二义性，如 A 或者 B 坏了（这个是析取），or，第一节上数学或者英语（这个是异或））

（以上这三个为原子联结词，用着三种可以表示出来任意逻辑）

异或、$\bar{\vee}$，只有两者取值互异的时候取真

$A\bar{\vee}B$，A 与 B 取值不相同时为真

注意冲突往往是同一时间做两件事导致的冲突

蕴含、$\rightarrow$，只有 P 为真、Q 为假时，$P \rightarrow Q$为假

如果 P 则 Q，P 是$P \rightarrow Q$​ 的前件、Q 是后件，还可以说 P 是 Q 的充分条件，Q 是 P 的必要条件

前件、后件：是针对蕴含关系而言的，只有这个方向$P\rightarrow Q$，必要条件是后件，充分条件是前件

充分条件：只要条件成立，结论就成立

1. 如果就，
2. 只要就，
3. P，就 Q，
4. Q，除非 P，$\neg P \rightarrow Q$

必要条件：如果条件不成立，则结论不成立

1. 只有 Q 才，
2. 仅当 Q 才，
3. Q，才 P

双条件，$\leftrightarrow$，当且 PQ 取值相等时，这个才为真

相当于同或，$\leftrightarrow \Leftrightarrow \neg\bar\vee$

有的时候”，“是（比如说作为同位语）小明，东北大学的一名同学

我们要好好学习、天天向上，为祖国建设而奋斗。

根据需要的情况，可以化成两种

1. $\neg \bar\vee$

Tricky parts

• 或者：或者具有二义性，根据具体语境不同，可能是析取也可能是异或

• 前件、后件：分别是充分条件、必要条件

植物死亡：必要条件

3. 命题公式及命题符号化

基本概念

常值命题

命题变元

P、Q 等表达任何命题

指派：讲常值命题赋予命题边缘，或直接赋给命题变元 T 或 F 的过程

合式公式 wff

1. 定义

   1. 单个命题变元是个合式公式

   2. 若 A 是合式公式，则非 A 是合式公式

   3. 若 A 和 B 是合式公式，则(A 析取 B)

      注意第三条都需要括号，但约定最外层的括号可以不写

   （实际上这是个递归定义）

2. 简称

   命题公式、或简称公式

1. 括号不匹配，如）（或（））
2. 没有规定运算符次序，如 A->B V C
3. 命题变元直接相连缺少联结词，如 AB V C

一个命题公式不是复合命题，所以它没有真值，但如果将其中所有命题变元作指派，以后他就有了真值，可以用真值表反映它的真值情况

为了有序地列出 A(P1,P2,...,Pn)的真值表，可以讲 F 看出 0，T 看成 1，按二进制数次序列真值表

一共是$2^n$行，为 0 到$2^n-1$

000

001

010

011

命题符号化

方法

1. 明确命题的含义

2. 对于复合命题，找自然语言的联结词，用联结词断句。分解出原子命题

   无、不看成联结词

   ；是合取，因为必须是每一句都是真话，这一整句话才是真的

3. 设原子命题的符号化

eg. 如果小张与小王都不去，则小李去

P：小张去，Q：小王去，R：小李去

$(\neg P \wedge \neg Q )\rightarrow R$

eg. 如果小张与小王不都去，则小李去

$\neg( P \wedge Q )\rightarrow R$

$(\neg P \vee \neg Q )\rightarrow R$ 德摩根律

仅当天，才

P：天下雨，Q：我有时间，R：我上街

$R\rightarrow (\neg P \wedge Q)$

人不犯我，我不犯人；人若犯我，我必犯人

P：人犯我，Q：我犯人

$P \leftrightarrow Q$

若天不下雨，我就上街；否则在家

P：天下雨，Q：我上街，R：我在家

$(\neg P \rightarrow Q)\wedge(P\rightarrow R)$

4. 重言式与重言蕴涵式 Implication

重言式（永真式）与矛盾式（永假式）

定义：

$A(P_1,P_2,...,P_n)$是含有命题变元

证明

• 真值表
• 公式的等价变化，化简成“T”
• 公式的主析取范式

性质

1. 如果 A 是永真式，则$\neg A$是永假式
2. 如果 A 是永真式，则 A 的置换例式是永真式

重言（永真）蕴含式

定义：

如果$A\rightarrow B$是重言式，则$A\Rightarrow B$

证明方法：

（看哪个件使得更多的变量为已知，如让蕴含式为假或合取为真）

• 真值表
• 假设前件为真，可以推出后件也为真
• 假设后件为假，可以推出前件也为假

重要的重言蕴含式（教材 43）16 个公式

1. $P \vee Q \Rightarrow P$

性质

1. 自反性：
2. 传递性：
3. 反对称性：


5. 等价公式 Equivalent

证明方法：

• 真值表相同，Eg.
• 置换定理

$P \rightarrow Q \Leftrightarrow P\vee\neg Q\Leftrightarrow \neg Q \rightarrow \neg P$

定义：

A、B 是含有命题变元 PPPPP 的命题公式，若不论 PPPP 如何指派，都使 A 和 B 真值相同，则称之为 A 与 B 等价，记作$A\Leftrightarrow B$

重要的等价公式

1. 对合律：$\neg\neg P\Leftrightarrow P$

2. 幂等律：$P\vee P\Leftrightarrow P, P\wedge P\Leftrightarrow P$

3. 结合律：

   （同种之间可以进行）

4. 交换律：

5. 分配率：$P\vee (Q\wedge R)\Leftrightarrow (P\vee Q)\wedge (P\vee R)$

   $P\wedge (Q\vee R)\Leftrightarrow (P\wedge Q)\vee (P\wedge R)$

   随便的二项析取的合取也符合类似普通的乘法分配率

6. 吸收率：$P\vee (P\wedge Q)\Leftrightarrow P, P\wedge (P\vee Q)\Leftrightarrow P$

7. 摩根律：

8. 同一律：$P\vee F\Leftrightarrow P, P\wedge T\Leftrightarrow P$

9. 零律 ：

10. 互补律：

11. $P\rightarrow Q\Leftrightarrow \neg P\vee Q$，以后看到蕴涵就改成这个

12. xxx

13. $P\leftrightarrow Q\Leftrightarrow P$

减少项的方法

1. 吸收率
2. 分配率

否定公式

证明等价公式的过程及化简的过程

1. 去条件：转化蕴含和双条件
2. 否定深入：
   1. 公式的否定公式
   2. 利用摩根律
   3. 分配率、幂等律等公式进行整理，使之成为
3. 整理：

证明方法

• 列真值表

• 置换定理

  A 是一个命题公式，

性质

1. 自反性：

2. 对称性：

3. 传递性：

4. 对偶性：

   把析取变为合取，合取变为析取，T 变 F，F 变 T，得到 A*，称 A 与 A*

   否定公式

   用对偶式求公式的否定

   $\neg A(P_1,P_2,...,P_n)\Leftrightarrow \neg A^*(\neg P_1,\neg P_2, ...,\neg P_n)$

   对偶原理：（可以利用对偶原理记公式）

   如果$AB$等价，则 A*B*等价

例题：求证吸收率$P\wedge(P\vee Q)$，（同一律 F 加分配率）

$\Leftrightarrow $

（其他逻辑词不讲）

6. 范式 (Paradigm)

析取式、合取式

合取式：用$\wedge$联结命题变元或变元的否定构成的式子

如：$P,\neg P,P\wedge \neg Q, P\wedge \neg Q\wedge\neg R$

析取式：

析取范式、合取范式

析取范式：用析取联结起来合取式

合取范式：用合取联结起来析取式

形式不唯一

写法

1. 去条件： 2. 转化蕴含 3. 双条件
2. 否定深入
3. 转化

主析取范式

小项（类似最小项表达式）

在 n 个变元的合取式中，每个变元都有且仅有一次出现，合取式

每一组指派有且仅有一个小项为 T。

方便记忆记作，$m_0,m_1,m_2,...,m_{2^n-1}$

主析取范式定义（类似最小项表达式）

析取范式$A_1\vee A_2\vee...\vee A_n$，其中每一个$A_i$都是小项，

$P\rightarrow Q$和$P\leftrightarrow Q$的主析取范式

永真式的主析取范式$\Leftrightarrow$包含所有小项的析取

写法

1. 真值表，然后列出来
2. 公式的等价变换
   1. 给定公式的析取范式
   2. 为使每个 Ai 变成小项，一个补全变元，用$\wedge$连接($R\vee\neg R$)
   3. 用分配率等公式加以整理

主析合取式

大项（类似最大项表达式）

在 n 个变元的析取式中，每个变元都有且仅有一次出现，析取式

每一组指派有且仅有一个大项为 F。

方便记忆记作，$M_0,M_1,M_2,...,M_{2^n-1}$

性质

1. n 个变元，有${2^n-1}$个大项
2. F

主析合取式定义（类似最小项表达式）

析取范式$A_1\wedge A_2\wedge...\wedge A_n$，其中每一个$A_i$都是大项，

$P\rightarrow Q$和$P\leftrightarrow Q$的主析合取式

永假式的主析取范式$\Leftrightarrow$包含所有大项的合取

写法

• 真值表，然后列出来

  最快还是把角标转化成二进制再写大项或小项

• 公式的等价变换

  1. 给定公式的合取范式

     1. 去条件
     2. 否定后移
     3. 整理成合取联结的析取式

  2. 为使每个 Ai 变成大项，一个补全变元，用$\vee$连接($R\wedge\neg R$)

     析取永假式

  3. 用分配率等公式加以整理

  4. 用幂等律去重

范式的应用

电路逻辑设计

1. 考虑线的交叉减少
2. 化简使逻辑门变少

根据需求安排问题

1.7 命题逻辑推理

证明永真蕴含式的过程

推理规则

规则 P：在推理过程中，可以随时引入前提

规则 T：在推理过程中，如果前边有一个或几个公式永真蕴含公式 S，则可讲 S 纳入推理过程中

重要的重言蕴含：公式 I10、11、12、13、14

• $I_{10}:\neg P\wedge(P\vee Q)\Rightarrow Q$
• $I_{11}: P\wedge(P\rightarrow Q)\Rightarrow Q$

重要的等价公式：E19

直接推理

前提直接推出结论

步骤号+前提或结论+所用规则+从哪几步得到+所用公式

（不用说出来是 I 几，考试的时候写出来是 I 还是 E 就行）

PQR

条件论证

$H_1\wedge H_2\wedge ... \wedge H_n\wedge R\Rightarrow S$，则

$H_1\wedge H_2\wedge ... \wedge H_n\Rightarrow R\rightarrow S$

最开始 P(附加前提)，最后 CP

反证法

思想类似于证明永真蕴含式的过程

相容、不相容

相容：存在一组指派让集合为真

不相容：不存在一组指派让集合为真

条件引入

范式的应用：

派人的方法

分配率展开，可以引入多个条件