离散数学笔记

# Table of Contents ------------------- - [命题逻辑](#%e5%91%bd%e9%a2%98%e9%80%bb%e8%be%91) - [基本概念](#%e5%9f%ba%e6%9c%ac%e6%a6%82%e5%bf%b5) - [集合](#%e9%9b%86%e5%90%88) - [函数](#%e5%87%bd%e6%95%b0) - [自然数集的归纳定义](#%e8%87%aa%e7%84%b6%e6%95%b0%e9%9b%86%e7%9a%84%e5%bd%92%e7%ba%b3%e5%ae%9a%e4%b9%89) - [数学归纳法](#%e6%95%b0%e5%ad%a6%e5%bd%92%e7%ba%b3%e6%b3%95) - [论域](#%e8%ae%ba%e5%9f%9f) - [自然数公理](#%e8%87%aa%e7%84%b6%e6%95%b0%e5%85%ac%e7%90%86) - [自然数理论](#%e8%87%aa%e7%84%b6%e6%95%b0%e7%90%86%e8%ae%ba) - [形式语言](#%e5%bd%a2%e5%bc%8f%e8%af%ad%e8%a8%80) - [专用公理](#%e4%b8%93%e7%94%a8%e5%85%ac%e7%90%86) - [命题和联结词](#%e5%91%bd%e9%a2%98%e5%92%8c%e8%81%94%e7%bb%93%e8%af%8d) - [命题](#%e5%91%bd%e9%a2%98) - [简单命题](#%e7%ae%80%e5%8d%95%e5%91%bd%e9%a2%98) - [复合命题](#%e5%a4%8d%e5%90%88%e5%91%bd%e9%a2%98) - [联结词](#%e8%81%94%e7%bb%93%e8%af%8d) - [抽象表示](#%e6%8a%bd%e8%b1%a1%e8%a1%a8%e7%a4%ba) - [逻辑联结词](#%e9%80%bb%e8%be%91%e8%81%94%e7%bb%93%e8%af%8d) - [定义](#%e5%ae%9a%e4%b9%89) - [逻辑域](#%e9%80%bb%e8%be%91%e5%9f%9f) - [关系](#%e5%85%b3%e7%b3%bb) - [计数关系](#%e8%ae%a1%e6%95%b0%e5%85%b3%e7%b3%bb) - [公式与真值赋值](#%e5%85%ac%e5%bc%8f%e4%b8%8e%e7%9c%9f%e5%80%bc%e8%b5%8b%e5%80%bc) - [合式公式](#%e5%90%88%e5%bc%8f%e5%85%ac%e5%bc%8f) - [命题逻辑语言](#%e5%91%bd%e9%a2%98%e9%80%bb%e8%be%91%e8%af%ad%e8%a8%80) - [公式复杂度](#%e5%85%ac%e5%bc%8f%e5%a4%8d%e6%9d%82%e5%ba%a6) - [联结词优先级](#%e8%81%94%e7%bb%93%e8%af%8d%e4%bc%98%e5%85%88%e7%ba%a7) - [真值赋值函数](#%e7%9c%9f%e5%80%bc%e8%b5%8b%e5%80%bc%e5%87%bd%e6%95%b0) - [合式公式、真值赋值](#%e5%90%88%e5%bc%8f%e5%85%ac%e5%bc%8f%e7%9c%9f%e5%80%bc%e8%b5%8b%e5%80%bc) - [等价真值赋值](#%e7%ad%89%e4%bb%b7%e7%9c%9f%e5%80%bc%e8%b5%8b%e5%80%bc) - [可满足性、有效性](#%e5%8f%af%e6%bb%a1%e8%b6%b3%e6%80%a7%e6%9c%89%e6%95%88%e6%80%a7) - [代换和替换](#%e4%bb%a3%e6%8d%a2%e5%92%8c%e6%9b%bf%e6%8d%a2) - [等值演算](#%e7%ad%89%e5%80%bc%e6%bc%94%e7%ae%97) - [演算规则](#%e6%bc%94%e7%ae%97%e8%a7%84%e5%88%99) - [零律](#%e9%9b%b6%e5%be%8b) - [幂等律](#%e5%b9%82%e7%ad%89%e5%be%8b) - [吸收律](#%e5%90%b8%e6%94%b6%e5%be%8b) - [同一律](#%e5%90%8c%e4%b8%80%e5%be%8b) - [双重否定](#%e5%8f%8c%e9%87%8d%e5%90%a6%e5%ae%9a) - [矛盾律](#%e7%9f%9b%e7%9b%be%e5%be%8b) - [排中律](#%e6%8e%92%e4%b8%ad%e5%be%8b) - [假言易位](#%e5%81%87%e8%a8%80%e6%98%93%e4%bd%8d) - [德摩根律](#%e5%be%b7%e6%91%a9%e6%a0%b9%e5%be%8b) - [交换律](#%e4%ba%a4%e6%8d%a2%e5%be%8b) - [结合律](#%e7%bb%93%e5%90%88%e5%be%8b) - [分配律](#%e5%88%86%e9%85%8d%e5%be%8b) - [规定](#%e8%a7%84%e5%ae%9a) --------------------- # 命题逻辑 ## 基本概念 ### 集合 唯一性 无序性 确定性 外延原则：由元素唯一确定 概括原则：每一性质/谓词产生一个集合 集合外延：元素全体 集合内涵：共有性质 集合差：$A-B$ 或 $A\setminus B$ - $\{x|x\in A\wedge x\not\in B\}$ 笛卡尔积：$A\times B = \{(x,y)|x\in A, y\in B\}$ ### 函数 对应关系 若 $f$ 是 $A^n$ 到 $B$ 的函数，则称 $f(x_1, x_2, \ldots, x_n)$ 为 $A$ 上的 $n$ 元函数，也称 $A$ 上的 $n$ 元运算。 $A^n=\underbrace{A\times A \times \cdots \times A}_{n 个}$ ### 自然数集的归纳定义 $n'$ 是 $n$ 的唯一后继 $N$ 是满足以下条件中的 $N'$ 中的最小集合 - $0\in N$，且 $0$ 不是任何数 $n$ 的后继 - $\forall n$，$n\in N'\Rightarrow n'\in N'$ ### 数学归纳法 1. 归纳基础 $R(0)$ 2. 归纳假设 $\forall k\in N, R(k)$ 3. 证明 $R(k')$ 4. 结论 $\forall n\in N, R(n)$ ### 论域 一个数学系统，记为 $D$ consists of: 1. a non empty object set $S$ 2. a function set $F$ on $D$ 3. a relation set $T$ on $D$ ### 自然数公理 1. 0 是自然数 2. 每个自然数都有后继 3. 0 不是任何自然数的后继 4. 后继相等的自然数相等 5. 若某集合含 0，且其中每一对象的后继也在集合里，则该集合包含所有自然数 ### 自然数理论 #### 形式语言 $\mathscr{L}=\lang=,+,\circ,s,0\rang$，$=$ 为等词，$s$ 是一元函词（后继），$+$，$\circ$ 是二元函词（加 / 乘），0 为常元 #### 专用公理 - $\forall x(s(x)\neq x)$ - $\forall x\forall y(x\neq y\rightarrow s(x)\neq s(y))$ - $\forall x(x+0=x)$ - $\forall x\forall y(x+s(y)=s(x+y))$ - $\forall x(x\circ 0=0)$ - $\forall x\forall y(x\circ s(y)=x\circ y+x)$ - $(Q(0)\wedge\forall x(Q(x)\rightarrow Q(s(x))))\rightarrow \forall x Q(x)$ 其中 $Q(x)$ 是任意公式 ## 命题和联结词 ### 命题 具有确定真假意义的陈述句。 #### 简单命题 由简单陈述句表述，不可再进一步分析 #### 复合命题 用联结词联结命题得到 #### 联结词 并且、或、否定、若则、当且仅当、既不也不 #### 抽象表示 假命题：0 真命题：1 ### 逻辑联结词 #### 定义 $n>0,$ 称 $\{0,1\}^n$ 到 $\{0,1\}$ 的函数为 $n$ 元函数，真值函数也称联结词。 $n=0$，则称 $0$ 元函数。 0 元：$0, 1$ 1 元：$\lnot$ 2 元：$\wedge, \vee, \rightarrow, \leftrightarrow, \oplus$ 非 $\lnot$ 且 $\land$（合取） 或 $\lor$（析取） 蕴涵 $p \rightarrow q$（p 则 q） 等值 $p \leftrightarrow q$（p 当且仅当 q） 异或 $p \oplus q$ （p 异或 q） ### 逻辑域 #### 关系 $R_{=}=\{<0, 0>, <1, 1>\}$ $R_{\models}=\{<0, 0>, <0, 1>, <1, 1>\}$ #### 计数关系 变量数 $n$ 变量组合数 $2^n$ 运算符数 $2^{2^n}$ ## 公式与真值赋值 ### 合式公式 （Well-formed Formula） **原子公式：命题变元** 1. 常元 0, 1 是合式公式 2. 命题变元是合式公式 3. 若 $Q, R$ 是合式公式，则 $\lnot Q, (Q\land R), (Q\lor R), (Q\rightarrow R), (Q\leftrightarrow R), (Q\oplus Q)$ 是合式公式 4. 只有有限次应用规则 1-3 构成的公式是合式公式 **由 S 生成的公式** 1. 0 元联结词是 2. 原子公式是 3. 取S中任意联结词，递归定义 ### 命题逻辑语言 所有的命题合式公式集合构成了命题逻辑语言，记为 $\mathscr{L}$。 ### 公式复杂度 1. $FC(0) = FC(0) = 0$ 2. $FC(p) = 0$ 3. $FC(\lnot A) = FC(A) + 1$ 4. $FC(A \circ B) = \max\{FC(A), FC(B)\} + 1$ ### 联结词优先级 $\lnot, \land, \lor, \oplus, \rightarrow, \leftrightarrow$ ### 真值赋值函数 从合式公式到逻辑集合 $\{0, 1\}$ 的函数称为真值赋值函数。 $p^v$ 表示 $v$ 赋给 $p$ 的真值。 ### 合式公式、真值赋值 就是把真值赋值函数给的值往里代入 ### 等价真值赋值 赋给公式 $Q$ 中每个命题变元的真值都相等时，两个真值赋值函数对 $Q$ 的真值指派相等。 ### 可满足性、有效性 $\mathbf{Def.\;\; 1.7}$ 1. 若真值赋值 $v$ 使得 $v(Q) = 1$，称 $v$ 满足 $Q$。 2. 每个真值赋值都满足 $Q$，称其为有效式、永真式 3. 都不满足，称其为永假式，矛盾式。 4. 存在满足，称可满足式。 ### 代换和替换 $\mathbf{Def.\;\; 1.8}$ 用公式 $B_1, ..., B_n$ 代换 $Q$ 中不同命题变元得到的公式记为 $[p_1/B_1, ..., p_n/B_n]Q$ 或 $Q^{p_1, ..., p_n}_{B_1, ..., B_n}$，称为 $Q$ 的代换实例。 用公式 $B_1, ..., B_n$ 代换 $Q$ 中不同合式公式得到的公式记为 $[Q_1/B_1, ..., Q_n/B_n]Q$ 或 $Q^{Q_1, ..., Q_n}_{B_1, ..., B_n}$，称为 $Q$ 的替换实例。 $\mathbf{Th.\;\; 1.2}$ 先代换后求值 = 先求值再代换再求值 $\mathbf{Th.\;\; 1.3}$ 永真式的所有代换示例依旧是永真式 永假式的所有代换示例依旧是永假式 ## 等值演算 $\mathbf{Def.\;\; 1.9}$ 对所有真值赋值 $v$ 均有相同真值的公式称等值，或称逻辑等价，记 $Q\Leftrightarrow R$ ### 演算规则 #### 零律 $Q\lor 1\iff 1$ $Q\land 0\iff 0$ #### 幂等律 $Q\lor Q\iff Q$ $Q\land Q\iff Q$ #### 吸收律 $Q\lor (Q\land R)\iff Q$ $Q\land (Q\lor R)\iff Q$ #### 同一律 $Q\land 1\iff Q$ $Q\lor 0\iff Q$ $Q\oplus 0\iff Q$ ### 双重否定 $\lnot \lnot Q\iff Q$ ### 矛盾律 $Q\land \lnot Q\iff 0$ ### 排中律 $Q\lor \lnot Q\iff 1$ ### 假言易位 $P\rightarrow Q\iff \lnot Q\rightarrow \lnot P$ ### 德摩根律 $\lnot (Q\lor R)\iff \lnot Q\land \lnot R$ $\lnot (Q\land R)\iff \lnot Q\lor \lnot R$ ### 交换律 $Q\lor R\iff R\lor Q$ $Q\land R\iff R\land Q$ $Q\oplus R\iff R\oplus Q$ ### 结合律 $(A\lor B)\lor C\iff A\lor (B\lor C)$ $(A\land B)\land C\iff A\land (B\land C)$ $(A\oplus B)\oplus C\iff A\oplus (B\oplus C)$ ### 分配律 $A\lor (B\land C) \iff (A\lor B)\land (A\lor C)$ $A\land (B\lor C) \iff (A\land B)\lor (A\land C)$ $A\land (B\oplus C) \iff (A\land B)\oplus (A\land C)$ ### 规定 $A\oplus A\iff 0$ $A\oplus 1\iff \lnot A$ $A\rightarrow B\iff \lnot A\lor B$ $A\leftrightarrow B\iff (A\rightarrow B)\land (B\rightarrow A)$ $A\oplus B\iff (\lnot A\land B)\lor(A\land \lnot B)$ $A\oplus B\iff \lnot(A\leftrightarrow B)$