1.1 命题与连接词#

数理逻辑是研究形式推理的数学分支，形式推理由一系列的陈述句组成。

作为命题的陈述句所表达的判断结果成为命题的真值。真值只取2个值：真/假。

真值为真即为真命题。真值为假的为假命题。真命题表达判断正确，假命题表达判断错误。任何命题的真值都是唯一的。

” 因为3$>$2,所以3$\neq$2“由连个更简单的命题“3$>$2”和“3$\neq$2”组成。“3$>$2”和“3$\neq$2”不能分解为更简单的命题称为简单命题或原子命题。有简单命题通过联结词联结而成的命题成为复合命题。

判断一个给定句子是否为命题要分为两步：

1，判断他是否为陈述句。

2，判断他是否有唯一的真值。

1.2 命题公式及其赋值#

上一节中讨论的是简单命题（原子命题）和复合命题以及他们的符号表达的一些笔记下一部分是关于真值表的一些知识。

1，将命题变项用连接词和圆括号按一定的逻辑关系联结起来的符号串称为合式公式。

(1)单个命题变项是合式公式，并称其为原子命题公式。

(2)A是合式公式 则$\neg A$也是合式公式。

(3)若A，B是合式公式，则（$A \wedge B$）,（$A \vee B$）,（$A \rightarrow B$）（$A \leftrightarrow B$）是合式公式 。

(4)有限次地应用(1)~(3)形成的符号串是合式公式，

合式公式也称为命题公式简称公式。

若p₁ ,p₂,…, p_n 是出现在公式A中的全部命题变项，给p₁,p₂,…,p_n各指定一个真值，称为对A的一个赋值或解释。若指定的一组值使A为1，则称这组值为A的成真赋值；若使A为0，则称这组值为A的成假赋值。

2.1 命题等价证明#

定义2.1：设A，B是两个命题公式，若A，B构成的等价式$A \leftrightarrow B$ 为重言式，则称A与B是等值的，记作$A \Leftrightarrow B$

**怎么证明两个公式A，B等价？ **

(1)列真值表证明

(2)公式法:利用已知的等价公式及等价置换进行证明。

这一章节学习的等价公式有（公式的名字并不重要，重要的是记住并理解公式本身）：

(1)双重否定率: $A \Leftrightarrow \neg \neg A$

(2)幂等律：$A \Leftrightarrow A\vee A$ ， $A \Leftrightarrow A \wedge A$

(3)交换律：$A \vee B \Leftrightarrow B \vee A$ , $A \wedge B \Leftrightarrow B \wedge A$

(4)结合律： $(A \vee B) \vee C \Leftrightarrow A \vee (B \vee C)$

​ $(A \wedge B) \wedge C \Leftrightarrow A \wedge (B \wedge C)$

(5)分配律: $A \vee (B \wedge C) \Leftrightarrow (A \vee B) \wedge (A \vee C)$

​ $A \wedge (B \vee C) \Leftrightarrow (A \wedge B) \vee (A \wedge C)$

(6)德摩根律：$\neg (A \wedge B) \Leftrightarrow \neg A \vee \neg B$ , $\neg (A \vee B) \Leftrightarrow \neg A \wedge \neg B$

(7)吸收率：$A \vee (A \wedge B) \Leftrightarrow A$ , $A \wedge (A \vee B) \Leftrightarrow A$

(8)零律：$A \vee 1 \Leftrightarrow 1$ $A \wedge 0 \Leftrightarrow 0$

(9)同一律：$A \vee 0 \Leftrightarrow A$ $A \wedge 1 \Leftrightarrow A$

(10)排中律：$A \vee \neg A \Leftrightarrow 1$

(11)矛盾律：$A \wedge \neg A \Leftrightarrow 0$

(12)蕴涵等值式： $A \rightarrow B \Leftrightarrow \neg A \vee B$

(13)等价等值式：$A \leftrightarrow B \Leftrightarrow (A \rightarrow B)\wedge(B \rightarrow A)$

(14)假言易位：$A \rightarrow B \Leftrightarrow \neg B \rightarrow \neg A$

(15)等价否定等值式：$A \leftrightarrow B \Leftrightarrow \neg A \leftrightarrow \neg B$

(16)归缪论：$(A \rightarrow B) \wedge (A \rightarrow \neg B) \Leftrightarrow \neg A$

2.2 析取范式合取范式#

析取式：形如$A_1 \vee A_2 \vee \cdots \vee A_n (n\geq 1)$ 的命题公式叫做析取范式。

e.g : ${\left( {P \land Q}\right) \vee \left( {\neg P \land \neg Q}\right) }$

合取式：形如 ${A}_{1} \land {A}_{2} \land \cdots \land {A}_{n}\left( {n \geq 1}\right)$ 的命题公式叫做合取范式.

其中 ${Ai}\left( {1 \leq i \leq n}\right)$ 是由命题变元或其否定所取组成的式子.

e.g. : ${\left( {P \land Q}\right) \wedge \left( {\neg P \land \neg Q}\right) }$

怎样求范式：

1. 先用等价变换将公式A转变成仅含有否定、合取、析取的式子。

2. 用德摩根定律将不定符号移到括号内。

3. 用分配律求相应的范式

例：求 $\neg \left( {P \rightarrow Q}\right) \vee {R}$ 的合取. 析取范式

解： $\neg \left( {P \rightarrow Q}\right) {\vee R}$

$\Leftrightarrow \neg \left( {\neg {P \vee Q}}\right) \vee {R}$

$\Leftrightarrow \left( {{P\land } \neg Q}\right) \vee {R}$ (析取范式)

$\Leftrightarrow \left( {P \vee R}\right) \wedge \left( {\neg Q \vee R}\right) \;\left( {\text{ 合取范式 }}\right)$

主析取范式，主合取范式，可以用公式法等值演算或真值表来进行求解。

主析取范式: 成真赋值，极小项 (本身为1，否定为0)

主合取范式：成假赋值，极大项（本身为0，否定为1）