# discrete-mathematics

**Repository Path**: bmft001/discrete-mathematics

## Basic Information

- **Project Name**: discrete-mathematics
- **Description**: 离散数学笔记
- **Primary Language**: Unknown
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-10-14
- **Last Updated**: 2020-12-20

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 一、离散笔记

> catelog目录:
>
> 1. 命题逻辑-基本的概念
> 2. 命题逻辑-等值演算
> 3. 命题逻辑-推理理论
> 4. 谓词逻辑
> 5. 集合代数
> 6. 二元关系
> 7. 图的基本概念
> 8. 欧拉图和哈密顿图
> 9. 树

### 1. 命题逻辑-基本概念

#### 一、命题的定义：

**能判断其真假的陈述句**

* 1.能判断真假
* 2.陈述句

#### 例题一：

**例题一:判断下来语句是否为命题，如果是命题，真值如何？**

> （1）北京是中国的首都

是 （真） 1 ，T

> （2）圆周率π是一个无理数。

是 （ 真）， 1，T

> （3）小张是个大学生 

是陈述句且**能判断真假**，所以这个**是一个命题**

但是我们无法判断这个的真值，这个**真值是暂时未定的**

**是（？）**

> （4）地球之外的星球上有人

是命题，但是无法判断是否为真

**是（？）**

> （5）2200年的元旦是晴天

是（？）



> （5）请关门

不是命题

**否（..)**

> （6) $2x +4  \geq 10$

这不是命题

**==命题的真值唯一==**

> （7）我现在正在说谎话

**这是一个非常有名的悖论**

#### 二、命题连接词

**命题连接词就是在==组合原子命题==**

| 联结词 | 非              | 并且，and,&& | 或者 or \|\| | 如果...则...(充分条件) | 当且仅当（充要条件）    |
| ------ | --------------- | ------------ | ------------ | ---------------------- | ----------------------- |
| 符号   | $\neg x$        | $\wedge$     | $\vee$       | $\to$                  | $\leftrightarrow$       |
| 含义   | negation 逻辑非 | and          | or           | to                     | leftrightarrow 充要条件 |



**（重要，基础）各种符号的真值表：**

> 1.非 **$ \neg$** 

| P    | $\neg P$ |
| ---- | -------- |
| 0    | 1        |
| 1    | 0        |

> 2.and $\wedge$ 

| P    | Q    | P $\wedge$ Q |
| ---- | ---- | ------------ |
| 0    | 0    | 0            |
| 0    | 1    | 0            |
| 1    | 0    | 0            |
| 1    | 1    | ==**1**==    |

> 3.or $\vee$

| P    | Q    | P $\vee$ Q |
| ---- | ---- | ---------- |
| 0    | 0    | ==**0**==  |
| 0    | 1    | 1          |
| 1    | 0    | 1          |
| 1    | 1    | 1          |

> 4.to 充分条件 **如果... 则...** $\to$

| P    | Q    | P $\to$ Q |
| ---- | ---- | --------- |
| 0    | 0    | 1         |
| 0    | 1    | 1         |
| 1    | 0    | **==0==** |
| 1    | 1    | 1         |

> 5.充要条件 当且仅当 $\leftrightarrow$
>
> **这个要区别于 充分条件to**

| P    | Q    | P $\leftrightarrow$ Q |
| ---- | ---- | --------------------- |
| 0    | 0    | 1                     |
| 0    | 1    | **==0==**             |
| 1    | 0    | **==0==**             |
| 1    | 1    | 1                     |

#### 例题二：

**例题二：将下列命题符号化**

> 1. $\sqrt{2}$ 是无理数

这就是一个原子命题，

令 P：$\sqrt{2}$ 是无理数

> 2.$\sqrt{2}$ 和 $\sqrt{5}$都是无理数

令

P: $\sqrt{2}是无理数$

Q：$\sqrt{5}是无理数$

符号化： P $\wedge$ Q

> 3.$\sqrt{2} 和 \sqrt{5} 的乘积是无理数$

令P：为 $\sqrt{2}和\sqrt{5}的乘积是无理数$

因为这个主语只有一个

> 4.小丽喜欢唱歌或喜欢跳舞

令

P：小丽喜欢唱歌

Q：小丽喜欢跳舞

或者 ：$\vee$

符号化： P $\vee$ Q

> 5.今天晚上小丽看书或者打球

令

P：小丽今天晚上看书

Q：小丽今天晚上打球

**因为小丽今天晚上只能看书或者打球，所以看书和打球是不兼容的**

小丽今天晚上看书不能打球：$P \wedge \neg Q$

小丽今天晚上打球不看书：$Q \wedge \neg P$

总合的符号化：$(P \wedge \neg Q) \vee (Q \wedge \neg P)$

> 6.如果天气好我就去公园

令

P：天气好

Q：去公园

天气好一定去公园，

去公园不一定天气好

所以这里是 **充分条件**

符号化：$P \to Q$

> 6.1.只要天气好，我就去公园

同理6.

符号化：$P \to Q$

> 6.2 只要天气好，我才会去公园.

天气好不一定去公园，

去公园一定你天气好，

所以这里是必要条件

符号化：$Q \to P$

> 6.3 仅当天气好，我才去公园

同理 6.2

> 7.经一事，长一智，并且不经一事，不长一智。

P：经一事

Q：长一智

经一事长一智是如果.. 则的关系 就是 to $\to$

不经一事，不长一智，同理

并且是 and 关系 $\wedge$

总合符号化：$(P \to Q) \wedge ( \neg P \to \neg Q)$

> 天津市是直辖市的充要条件是 $2 + 3 = 5$

P： 天津市是直辖市

Q：2+2=5

符号化：$P \leftrightarrow Q$

#### 三、真值表

详情看例题

#### 例题三：

> 判断公式的类型：
>
> * 1.满足式（恒为1）
> * 2.矛盾式（恒为0）
> * 3.可满足式，不是矛盾式就行，包含满足式

> 1.$P \wedge R \wedge \neg (Q \to P)$

使用真值表解法

| $P$  | $Q$  | $R$  | $Q \to P$ | $\neg (Q \to P)$ | $P \wedge R$ | $P \wedge R \wedge \neg (Q \to P)$ |
| ---- | ---- | ---- | --------- | ---------------- | ------------ | ---------------------------------- |
| 0    | 0    | 0    | 1         | 0                | 0            | 0                                  |
| 0    | 0    | 1    | 1         | 0                | 0            | 0                                  |
| 0    | 1    | 0    | **0**     | **1**            | 0            | 0                                  |
| 0    | 1    | 1    | 0         | 1                | 0            | 0                                  |
| 1    | 0    | 0    | 1         | 0                | 0            | 0                                  |
| 1    | 0    | 1    | 1         | 0                | 0            | 0                                  |
| 1    | 1    | 0    | 1         | 0                | 0            | 0                                  |
| 1    | 1    | 1    | 1         | 0                | **1**        | 0                                  |

* $Q \to P$ 这里的Q是条件.只有条件为1，结论为0 的时候才能为 0 其他时候都是 1

所以这个公式的值恒为 0 ，因此这是一个 **矛盾式**

> 2.$(P \to Q) \to (\neg Q \to \neg P)$

| $P$  | $Q$  | $P \to Q$ | $ \neg P$ | $\neg Q$ | $(\neg Q \to \neg P)$ | $(P \to Q) \to (\neg Q \to \neg Q)$ |
| ---- | ---- | --------- | --------- | -------- | --------------------- | :---------------------------------: |
| 0    | 0    | 1         | 1         | 1        | 1                     |                  1                  |
| 0    | 1    | 1         | 1         | 0        | 1                     |                  1                  |
| 1    | 0    | 0         | 0         | 1        | 0                     |                  1                  |
| 1    | 1    | 1         | 0         | 0        | 1                     |                 11                  |

因为这个是恒定为1的式子，所以这是**满足式，同时也是可满足式**



> 3.$(\neg P\wedge Q) \to \neg R$

| $P$   | $Q$   | $R$   | $\neg P$ | $(\neg P \wedge Q)$ | $\neg R$ | $(\neg P \wedge Q) \to \neg R$ |
| ----- | ----- | ----- | -------- | ------------------- | -------- | ------------------------------ |
| 0     | 0     | 0     | 1        | 0                   | 1        | 1                              |
| 0     | 0     | 1     | 1        | 0                   | 0        | 1                              |
| 0     | 1     | 0     | 1        | 1                   | 1        | 1                              |
| **0** | **1** | **1** | **1**    | **1**               | **0**    | **0**                          |
| 1     | 0     | 0     | 0        | 0                   | 1        | 1                              |
| 1     | 0     | 1     | 0        | 0                   | 0        | 1                              |
| 1     | 1     | 0     | 0        | 0                   | 1        | 1                              |
| 1     | 1     | 1     | 0        | 0                   | 0        | 1                              |

因为这个式子存在1 和 0 ，所以这个式子是 **可满足式**

> 4.求公式 $(\neg P\wedge Q) \to \neg R$ 的成真赋值和成假赋值
>
> * 成真赋值：最后结果为 1（True）的参数（P,Q,R）的值
> * 成假赋值：最后结果为0 （False）的参数（P,Q,R)的值。

这个式子的真值表如上所示 ，

* **P = 0**  **Q =1**  **R = 1** 时候公式的值为 0 ，为假
* 其他7种情况-公式的值为 1 ，为成真赋值.