离散数学【02324】_蔡建伟博客

# 数理逻辑
> 数理逻辑既是数学的一个分支，也是逻辑学的一个分支，而数理逻辑的两个重要组成部分就是命题演算与谓词演算

## 命题演算
### 推理与命题
由一个或多个已知的前提，推导出一个为止结论的思维过程叫做推理；推理的基本要素就是表达这些已知前提的陈述句，每个陈述句成立或者不成立(限定在某种场景下，一个陈述句不可能既成立也不成立)就被看作这个陈述句的一个属性，称为真值
* 当陈述句成立时，就说其真值为真，表示为T
* 当陈述句不成立时，就说其真值为假，表示为F

所以判断是不是命题的必备条件，一是陈述句，二是有唯一的真值（真值为真的命题为真命题，真值为假的命题为假命题）

> 悖论也不是命题（悖论只逻辑上可以推出与陈述句本身矛盾的陈述句，如我正在说谎）

### 命题符号化与命题标识符
在数理逻辑中，我们通常使用符号表示一个命题，这个过程称之为命题的符号化，而这个符号称之为命题标识符

命题标识符既可以是大写字母，也可以是小写字母如P或者p，有时候还使用字母加数字的形式表示，通常数字为下标P<sub>1</sub>，Q<sub>2</sub>，如：
* P: π是有理数
* Q: 所有的素数都是质数
* R: 6是一个合数

### 复合命题与联结词
像上述命题这样的不可在拆分的命题称之为原子命题或者简单命题，但实际生活中我们需要表达更丰富的信息，比如：如果母猪会上树，那么男人靠得住，这句话表示了两个含义：母猪会上树，男人靠得住，而且这两个含义还是有关联的，前一个是前提，后一个是结果

自然语言中，我们常使用连词来标识两个句子的关系，如上面提到的如果...那么...，在命题符号化时，这样的连词称之为联结词(每个联结词都有符号，下面会介绍)，而由原子命题通过联结词联结而成的命题称为复合命题

> 一般自然语言，一句话可能有二义性，比如张三借李四200块钱，但在数理逻辑中，为了能精准的推导，命题和联结词的含义必须是确定的
> 自然语言除了符合语法，还要有合适的语义，即要合乎情理，但在数理逻辑中，复合命题的多个原子命题可以没有任何关联，我们只关心复合命题里的各个原子命题的真值，可以忽略其语义

复合命题的值：复合命题也是命题，既是命题则必有唯一的真值，复合命题的真值根据所包含的各个原子命题的真值以及使用了何种联结词来确定，这个关系可以用一张表来表示，称之为真值表

在数理逻辑中，一般常用的联结词有五个
一、否定（逻辑否定）
定义：设P为命题，P的否定为一个复合命题，记为¬P，读作非P，符号¬称为否定联结词，对于否定命题¬P，有 P为T=> ¬P为F; P为F=> ¬P为T
> 自然语言的非，不是等代表否定，计算机语言使用!表示非，如!P

P | ¬P
---- | ----
T | F
F | T

二、合取（逻辑合取）
定义：设P,Q为两个命题，P和Q的合取为一个复合命题，记为P∧Q，读作P且Q，对于命题P∧Q，当且仅当P，Q都为T时，P∧Q为T，否则P∧Q为F

P | Q | P∧Q
---- | ---- | ----
T | T | T
T | F | F
F | T | F
F | F | F

> 自然语言的既又，不但而且，虽然但是 等代表合取，计算机使用&&代表且，如 p && q

三、析取（逻辑析取）
定义：设P,Q为两个命题，P和Q的析取为一个复合命题，记为P∨Q，读作P或Q，对于命题P∧Q，当且仅当P，Q都为F时，P∧Q为F，否则P∧Q为T

P | Q | P∨Q
---- | ---- | ----
T | T | T
T | F | T
F | T | T
F | F | F

> 自然语言的或代表析取，计算机使用||代表且，如 p || q
> 但是！！！析取的或代表的是同或，即两者并不互斥，可以同时成立，但是自然语言的或有时代表的是相斥的含义（称为异或），即使用或的两者不可能同时成立，这种语句，不能简单的使用析取表示

同或与异或
* 同或：即析取，两个命题可以同时成立
* 异或：两个命题只能有一个为T时，异或命题真值为T,否则真值为F，异或命题是更复杂的命题，表示为：(P∧¬Q)∨(¬P∧Q),异或的真值表如下：

P | Q | (P∧¬Q)∨(¬P∧Q)
---- | ---- | ----
T | T | F
T | F | T
F | T | T
F | F | F

四、条件（实质蕴涵）
定义：设P,Q为两个命题，P和Q的条件命题为一个复合命题，记为P→Q，读作如果P那么Q(若P则Q)，P为前件或前提，Q为后件或结论，对于命题P→Q，当且仅当P为T，Q为F时，P→Q为F，否则P→Q为T

P | Q | P→Q
---- | ---- | ----
T | T | T
T | F | F
F | T | T
F | F | T

> 条件复合命题表示的是，当前件成立时，后件是否成立，而如果前件不成立，那么后件是否成立不影响条件命题的真值

五、双条件（实质等价）
定义：设P,Q为两个命题，P和Q的双条件命题为一个复合命题，记为P⇔Q，读作当且仅当，对于命题P⇔Q，当P，Q真值相同时，P⇔Q为T，否则P⇔Q为F

P | Q | P⇔Q
---- | ---- | ----
T | T | T
T | F | F
F | T | F
F | F | T

不难看出，P⇔Q 等价于 (P→Q)∧(Q→P)

> ps:可以回想下初中学习的充分条件，必要条件，充分必要条件（充要条件）

### 复合复合命题的恒等式
由联结词的定义可以得出，有些复合命题不管原子命题值是真是假，复合命题的真值都恒为真或者恒为假

命题 | 恒等于
---- | ---- 
P∧¬P | F
-separator-