一、离散数学的定义

离散数学（Discrete Mathematics） 是研究离散对象的结构以及它们之间相互关系的一门数学学科

二、数理逻辑

数理逻辑（又称符号逻辑）是一门研究演绎推理的学科。 它研究的主要内容是推理，并且着重研究推理过程是否正确；它强调的是语句之间的关系，而不是只研究某个特定的语句是否正确，因此它是研究推理中前提和结论之间形式关系的一门科学。

三、命题与连接词

命题：判断结果唯一的陈述句

注：如果有唯一结果但是无法判断的陈述句，也是命题 如 2050年元旦下大雪. 是命题

1.命题的类型

• 简单命题（原子命题）：不能再分解成更简单的命题
• 复合命题：由简单命题和关联词构成的命题

2.简单命题符号化

• 用小写英文字母 \(p, q, r, …, p_i, q_i, r_i (i \ge 1)\)表示简单命题
• 用“1”表示真，用“0”表示假

3.复合命题的符号化

非

• 设 p为命题，复合命题“非\(p\)”(或“\(p\) 的否定”)称为\(p\) 的否定式，记作\(\lnot p\)，符号 \(\lnot\) 称作否定联结词
  • 规定 \(\lnot p\) 为真 当且仅当 \(p\) 为假 合取
• 设 p , q 为两个命题，复合命题“p 并且 q”(或“p 和 q”) 称为 p与q 的合取式，记作p∧q，∧称作合取联结词.
  • 规定：p∧q为真 当且仅当 p 与q 同时为真. 析取
• 设 p , q 为两个命题，复合命题“p 或 q”称作 p 与q 的析取式，记作p∨q，∨称作析取联结词
  • 规定p∨q为假 当且仅当 p与q同时为假. 蕴含
• 设 p , q 为两个命题，复合命题“如果 p, 则q”称作p与q的蕴涵式，记作 p\(\rightarrow\)q，并称p是蕴涵式的前件，q为蕴涵式的后件，\(\rightarrow\)称作蕴涵联结词.
  • p\(\rightarrow\)q为假 当且仅当 p为真q为假. 等价
• 设 p , q 为两个命题，复合命题“p当且仅当q”称作p与q的等价式，记作p\(\leftrightarrow\)q， \(\leftrightarrow\)称作等价联结词.
  • 规定：p\(\leftrightarrow\)q为真 当且仅当 p与q同时为真或同时为假.

注： 其实还有一个排斥或(异或)，由于我们学习的课本没有讲，这里就稍微提一下： 联结词 ∨ 是自然语言中的“或”、“或者”等的逻辑抽象。 自然语言中的“或”有“相容或”（即析取）、“排斥或”（即异或）两种。 严格来讲，析取联结词实际上代表相容或，异或有时会使用单独的异或联结词“\(\oplus\)”来表示。 区别就是当p，q为1时，相容或为1,而排斥或为0。(p , q 不能同时成立) 在电路中还有同或，同或和异或是“相反的”

四、连接词表述方法与计算

非

非，不，没有

合取

“既… 又…”、”不但… 而且… ”、”一面… 一面… “、”虽然… 但是… ”

析取

“或”、“或者”（不一定全是）

蕴含

等价

“等价”、“充分必要条件”、“当且仅当”

连接词运算顺序

先运算非，在按照合取，析取，蕴含，等价顺序计算

五、命题变项与合式公式

命题常项: 确指的或具体的命题。（非0即1，类似数学中的常量）

命题变项（命题变元）：不确指的或抽象的命题。（0或1，类似数学中的变量） 命题公式（合式公式/公式）: 将命题常项和命题变项用联结词和圆括号 按一定的逻辑关系 联结起来的符号串。

合式公式 的递归定义：

1. 单个命题常项和命题变项是合式公式, 称作原子命题公式。
2. 若A 是合式公式，则 (\(\lnot\)A)也是。
3. 若A, B 是合式公式，则(A∧B), (A∨B), (A\(\rightarrow\)B), (A\(\leftrightarrow\)B)也是。
4. 只有有限次地应用(1)—(3) 形成的符号串才是合式公式。

题型：公式的真值表，求成真，成假赋值

判断公式类型

类型：

• 重言式（永正式）
• 矛盾式（永假式）
• 非重言式的可满足式 方法：1.瞪眼法 2.真值表法 3.等值演算法

六、命题逻辑与等值演算

1.等值式

如果命题公式A与B在所有的赋值下的真值都相同，则称 A与B等值。 若等价式 A\(\leftrightarrow\)B 是永真公式，则称A与B等值，记作 A\(\Leftrightarrow\)B。 我们使用等价符号来进行等值演算\(\Leftrightarrow\) 注意和\(\leftrightarrow\) 区分。

2. 16组24条等值式

双重否定律\[\lnot\lnot A\Leftrightarrow A \] 幂等律\[\begin{align*} A\land A \Leftrightarrow A\\ A\lor A \Leftrightarrow A \end{align*}\]交换律 \[ \begin{align*} A\land B \Leftrightarrow B\land A\\ A\lor B\Leftrightarrow B \lor A \end{align*} \] 结合律\[\begin{align*} (A\land B)\land C \Leftrightarrow A\land (B\land C)\\ (A\lor B)\lor C \Leftrightarrow A\lor (B\lor C) \end{align*}\] 分配率 \[\begin{align*} A\land(B\lor C)\Leftrightarrow (A\land B)\lor (A\land C)\\ A\lor(B\land C)\Leftrightarrow(A\lor B)\land (A\lor C) \end{align*}\] 德摩根律 \[ \begin{align*} \lnot (A\land B)\Leftrightarrow \lnot A \lor \lnot B\\ \lnot (A\lor B) \Leftrightarrow \lnot A \land \lnot B \end{align*} \] 吸收律 \[ \begin{align*} A\land (A\lor B)\Leftrightarrow A\\ A\lor (A\land B) \Leftrightarrow A \end{align*} \] 零律 \[ \begin{align*} A\land 0\Leftrightarrow0\\ A \lor 1 \Leftrightarrow1 \end{align*} \] 同一律 \[ \begin{align*} A\land 1 \Leftrightarrow A\\ A \lor 0 \Leftrightarrow A \end{align*} \] 排中律 \[ A\lor \lnot A \Leftrightarrow1 \] 矛盾律 \[ A \land \lnot A \Leftrightarrow0 \] 蕴含等值式 \[ A \rightarrow B \Leftrightarrow \lnot A\lor B \] 等价等值式 \[ A \leftrightarrow B \Leftrightarrow (A\rightarrow B)\land (B\rightarrow A) \] 假言易位（ohno!妈咪何意味？) \[ A \rightarrow B \Leftrightarrow \lnot B \rightarrow\lnot A \] 等价否定等值式 \[ A \leftrightarrow B \Leftrightarrow\lnot A \leftrightarrow\lnot B \] 归谬论 \[ (A \rightarrow B )\land (A \rightarrow \lnot B ) \Leftrightarrow \neg A \]

3.检验两个公式等值的方法

• 真值表法
• 等值演算法

4.用等值演算法判断公式类型

• A为矛盾式当且仅当A \(\Leftrightarrow\) 0
• A为重言式当且仅当A \(\Leftrightarrow\) 1
• A为可满足式当且仅当 A \(\Leftrightarrow\) 含变元公式

5.用等值式解决实际问题

• 先设命题，根据命题写下每个人的判断
• 比如有三个人其中一个全对，一人说对一半，一人全错。
• 把这几种排列组合，每一种组合里面用合取，不同组合用或相连，然后演算。
• 演算为0说明这个组合内部是矛盾的。若有多个组合保留。带入语义判断。
• 最后得出正确的结论。

七、析取范式与合取范式

范式

是命题公式的一种标准形式

我们为了统一等值的命题公式的形式，就像管理身份证一样，管理不同命题公式。 我们引入范式这个概念。

命题公式\(\rightarrow\) 范式（析取范式，合取范式）\(\rightarrow\)主范式（主析取范式，主合取范式） 这一部分会按照这个思路来。

基本概念

• 文字：变项或变项的否定
• 简单析取式：由有限个文字的析取组成的析取式
• 简单合取式：由有限个文字的合取组成的合取式 注意，一个文字，即使简单析取式又是简单合取式
• 析取范式：由有限个简单合取式组成的析取式
• 合取范式：由有限个简单析取式组成的合取式 注意，单个简单析取式是合取范式，单个简单合取式是析取范式
• 范式：析取范式和合取范式的总称

任何式子都存在与之等值的析取范式和合取范式

一个简单析取式是重言式 当且仅当 它同时含有某个命题变相 \(p\) 和 \(\lnot p\) 一个简单合取式是矛盾式 当且仅当 它同时含有某个命题变相 \(p\) 和 \(\lnot p\)

一个析取范式是矛盾式 当且仅当 它每个简单合取式都是矛盾式 一个合取范式是重言式 当且仅当 它每个简单析取式都是重言式

范式的计算

1. （若存在）去除公式A中的 \(\rightarrow\) 和\(\leftrightarrow\) 连接词
2. （若存在）否定连接词\(\lnot\) ，内移或消去，直至\(\lnot\) 直接作用于命题变项（成为文字）
3. 不断使用分配率

需要注意的是，范式不唯一，为了一个唯一的，我们要把范式进一步规范化成为主范式 为了规范化，我们引入极小项和极大项

极小项和极大项

极小项和极大项的定义比较绕口， 我就不用书面语言表述了 ，讲一下我自己的理解。

极小项是一个简单合取式 每一个命题变项都只出现一次（取正或否） 而且是按照顺序出现的 同理，极大项就是一个简单合取式，每一个命题变项只出现一次，并且按照顺序出现

比如说 有p，q两个命题变项 极小项有四个 p∧q（m3），p∧¬q（m2），¬p∧q（m1)，¬p∧¬q(m0) 极大项也有四个 p∨q（M0），p∨¬q（M2），¬p∨q（M1)，¬p∨¬q(M0)

后面这个mi，Mi是极大项，极小项的名称 规定 mi 是第i个极小项，i 是该极小项成真赋值的十进制 规定 Mi 是第i个极大项，i 是该极大项成假赋值的十进制

要怎么记忆？（我自己的记忆法，不一定正确） 首先是 合取 对应 极小项 ，为什么，因为越合取值越小。 因为是 极小项 所以 用小写字母 m。 因为赋值会变小 所以成真就珍贵，越真越大 成真赋值（十进制）就是下标

同理，析取对应极大项，因为越析取越可能变成1 因为是 极大项，所以用字母M 因为越可能变成小 ，成假赋值越发珍贵，越假越大，成假赋值（十进制）就是下标

“小 m 合取极小项，唯一成真是下标。
大 M 析取极大项，唯一成假是下标。”

我们发现有如下关系 \[ \lnot m_{i} \Leftrightarrow M_{i}\space ,\lnot M_{i}\Leftrightarrow m_i \]

公式到范式到主范式的转化

主合取范式：由极大项组成的合取范式 主析取范式：由极小项组成的析取范式

任何公式都存在与之等值的主析取和主合取范式，并且是唯一的

范式到主范式的转化步骤

1. 求出A的范式
2. 若不是极小项，引入1或0把不含有的变项添加进去
3. 直到所有的项都满足极大项/极小项
4. 删除重复的项
5. 用m/M按照下标从小到大排序

主范式的作用

1. 求公式的成真赋值和成假赋值
2. 判断公式的类型
3. 判断两个公式是否等值
4. 解决实际问题

两个主范式的替换 字母大小写变化，下标数字互补

八、连接词的完备集

定义：一个联结词集合S，若由其形成的命题公式可以产生所有可能的真值表，则称S 为联结词完备集 常见的完备集 \[ \begin{align*} \{\lnot,\land,\lor\},\{\lnot,\lor\},\{\lnot,\land\},\{\lnot,\rightarrow\},\{\uparrow\},\{\downarrow\} \end{align*} \] \(\uparrow\):与非 \(\downarrow\):或非 一个连接词完备集的母集是连接词完备集

九、命题逻辑的推理

推理的定义： 就是根据一个或几个已知判断得出一个新的判断的思维过程

推理正确的定义：若对于每一组赋值，若\(A_{1} \land A_{2}\land\cdots\land A_{k}\) 为假 或 当\(A_{1} \land A_{2}\land\cdots\land A_{k}\) 为真时，B也为真。 则称由前提\(A_{1} \land A_{2}\land\cdots\land A_{k}\) 推出结论B的推理是正确的或有效的 记作：\(A_{1} \land A_{2}\land\cdots\land A_{k}\Rightarrow B\) 并称B是有效结论

注意：推理正确但是结论不一定正确。

证明推理的方法

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

推理系统

推理的规则（定律）

附加律 \[ A\Rightarrow(A\lor B) \] 简化律 \[ (A \land B)\Rightarrow A \] 假言推理 \[ (A\rightarrow B) \land A\Rightarrow B \] 拒取式（否定前提） \[ (A\rightarrow B)\land \neg B \Rightarrow \neg A \] 析取三段论 \[ (A \lor B)\land \neg B\Rightarrow A \] 假言三段论 \[ (A\rightarrow B)\land (B\rightarrow C)\Rightarrow (A\rightarrow C) \] 等价三段论 \[ (A\leftrightarrow B)\land(B\leftrightarrow C)\Rightarrow(A\leftrightarrow C) \] 构造性二难 \[ (A\rightarrow B)\land(C\rightarrow D)\land(A\lor C)\Rightarrow(B\lor D) \] 构造性二难 \[ (A\rightarrow B)\land(\neg A\rightarrow B)\Rightarrow B \] 破坏性二难 \[ (A\rightarrow B)\land (C\rightarrow D)\land (\neg B\lor \neg D)\Rightarrow(\neg A\lor \neg C) \]

推理的证明

直接证明：

1. 设出简单命题
2. 把前提和结论符号化
3. 按照上面的推理规则和等值式进行推理

间接证明法:

1. 如果证明结构为\((A_{1}\land A_{2}\land \dots \land A_{k})\rightarrow(A\rightarrow B)\) 采用证明形式\((A_{1}\land A_{2}\land \dots \land A_{k}\land A)\rightarrow B\) 其中\(A\) 称为附加前提
2. 归谬法 将结论的否定作为附加前提引入，最后推出矛盾式0