离散数学

作者: 王兴岭 | 来源:发表于2020-03-14 14:55 被阅读0次

命题

等价公式的定义

定义: 给定两个命题公式A和B，设P1,P2,…, Pn为所有出现在A、B中的原子命题，若给P1,P2,…, Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的，记A B或
A＝B。
等值定理：AB当且仅当AB是永真式

等价公式

对合律 : $\neg\neg P = P$
幂等律 : $P\vee P = P$ , $P\wedge P = P$
结合律 : $(P\wedge Q)\wedge R = P\wedge (Q\wedge R)$ , $(P\wedge Q)\wedge R = P\wedge (Q\wedge R)$
交换律 : $P\vee Q= Q\vee P,P\wedge Q = Q\wedge P$
分配律 : $P\vee (Q\wedge R) = (P\vee Q)\wedge(P\vee R)$ , $P\wedge (Q\vee R) = (P\wedge Q)\vee (P\wedge R)$
吸收律 : $P\vee (P\wedge R) = P$ , $P\wedge (P\vee Q)=P$
德摩根律 : $\neg (P\vee Q) = \neg P\wedge \neg Q$ , $\neg (P\wedge Q) = \neg P\vee \neg Q$
同一律 : $P\vee F = P$ , $P\wedge T = P$
零律 : $P\vee T = T$ , $P\wedge F = F$
否定律: $P\vee F = P$ , $P\vee F = P$

$P\rightarrow Q \Leftrightarrow \neg P \vee Q$
$P\rightarrow Q \Leftrightarrow \neg Q \rightarrow \neg P$
$P\leftrightarrow Q \Leftrightarrow (P\rightarrow Q)\wedge (Q\rightarrow P)$
$P\leftrightarrow Q \Leftrightarrow \neg Q\leftrightarrow \neg P$
$P\leftrightarrow Q \Leftrightarrow (Q\wedge P)\vee (\neg Q\wedge \neg P)$

重言(永真)蕴含式

定义: 如果公式 $A\rightarrow B$ 是重言式,则称A重言(永真)蕴含式B 记作 $A \Rightarrow B$ .

重要的重言蕴含式

$P\wedge Q \Rightarrow P$ , $P\wedge Q \Rightarrow Q$
$P\Rightarrow P\wedge Q$ , $P\Rightarrow P\vee Q$
$\neg P\Rightarrow P\rightarrow Q$ , $Q\Rightarrow P\rightarrow Q$
$\neg (P\rightarrow Q) \Rightarrow P$ , $\neg (P\rightarrow Q) \Rightarrow \neg Q$
$P, Q \Rightarrow P\wedge Q$ , $\neg P(P \vee Q) \Rightarrow Q$
$P\wedge(P\rightarrow Q) \Rightarrow Q$ , $\neg Q\wedge(P\rightarrow Q) \Rightarrow \neg P$
$(P\rightarrow Q) \wedge (Q\rightarrow R) \Rightarrow P\rightarrow R$
$(P\vee Q)\wedge (P\rightarrow R) \wedge (Q\rightarrow R) \Rightarrow R$
$(A\rightarrow B) \Rightarrow (A\vee C)\rightarrow (B\vee C)$
$(A\rightarrow B) \Rightarrow (A\wedge C)\rightarrow (B\wedge C)$

谓词逻辑

个体词: 指研究对象中可以独立存在的具体或抽象的个体
个体域(论域): 个体变项的取值范围
谓词: 刻画个体词的性质以及个体之间相互关系的词
量词: $\exists$ (存在量词), $\forall$ (全称量词)

消去量词等值式

个体域有限, $D =\lbrace a_1,a_2,\cdots ,a_n \rbrace$
$\forall xA(x) \Leftrightarrow A(a_1)\wedge A(a_2)\wedge \cdots \wedge A(a_n)$
$\exists xA(x) \Leftrightarrow A(a_1)\vee A(a_2)\vee \cdots \vee A(a_n)$

量词否定等值式

$\neg \forall xP(x) \Leftrightarrow \exists x \neg P(x)$
$\neg \exists xP(x) \Leftrightarrow \forall x\neg P(x)$

量词分配律

$\forall x(A(x) \wedge B(x))\Leftrightarrow \forall \wedge xA(x) \wedge B(x)$
$\exists x(A(x) \vee B(x))\Leftrightarrow \exists \wedge xA(x) \vee B(x)$

注意: 全称量词对合取分配, 存在量词对析取分配!

量词的扩展/收缩律

$\forall (P \vee B(x)) \Leftrightarrow P \vee \forall xB(x)$
$\forall (P \wedge B(x)) \Leftrightarrow P \wedge \forall xB(x)$
$\exists (P \vee B(x)) \Leftrightarrow P \vee \exists xB(x)$
$\exists (P \wedge B(x)) \Leftrightarrow P \wedge \exists xB(x)$
P是不包括个体变量 $x$ 的任意谓词公式

$\forall (A(x) \rightarrow B) \Leftrightarrow \exists xA(x) \rightarrow B$
$\exists (A(x) \rightarrow B) \Leftrightarrow \forall xA(x) \rightarrow B$

$\forall (B \rightarrow A(x)) \Leftrightarrow B \rightarrow \forall xA(x)$
$\exists (B \rightarrow A(x)) \Leftrightarrow B \rightarrow \exists xA(x)$

前束范式(PNF)

A为一阶逻辑公式, 若A具有形式:
$Q_1x_1Q_2x_2\cdots Q_kx_kB$
且 $Q_i$ 为全称量词或存在量词, B为不含量词的公式

集合

集合的运算

并 $A\bigcup B = \lbrace x|x \in A \vee x\in B \rbrace$
交 $A\bigcap B = \lbrace x|x \in A \wedge x\in B \rbrace$
相对补 $A-B = \lbrace x|x \in A \wedge x\notin B \rbrace$
对称差 $A \bigoplus B = (A-B) \vee (B-A)$
绝对补 $\sim A = E - A$

只涉及一个运算的算律

	$\bigcup$	$\bigcap$	$\bigoplus$
交换	$A\bigcup B = B\bigcup A$	$A\bigcap B = B\bigcap A$	$A\bigoplus B = B\bigoplus A$
结合	$(A\bigcup B)\bigcup C$ = $A\bigcup (B\bigcup C)$	$(A\bigcap B)\bigcap C$ = $A\bigcap (B\bigcap C)$	$(A\bigoplus B)\bigoplus C$ = $A\bigoplus (B\bigoplus C)$
幂等	$A\bigcup B = A$	$A\bigcap B = A$

只涉及两个运算的算律

	$\bigcup$ 与 $\bigcap$	$\bigcap$ 与 $\bigoplus$
分配	$A\bigcup (B\bigcap C) = (A\bigcup B)\bigcap (A\bigcup C)$ , $A\bigcap (B\bigcup C) = (A\bigcap B)\bigcup (A\bigcap C)$	$A\bigcap (B\bigoplus C) = (A\bigcap B)\bigoplus (A\bigcap C)$
吸收	$A\bigcup (A\bigcap B) = A$ , $A\bigcap (A\bigcup B) = A$

设计补运算的算律

	$-$	$\sim$
D.M律	$A-(B \bigcup C) = (A-B) \bigcap (A-C)$ , $A-(B \bigcap C) = (A-B) \bigcup (A-C)$	$\sim (A \bigcup B) = \sim A \bigcap \sim B$ , $\sim (A \bigcap B) = \sim A \bigcup \sim B$
双重否定		$\sim \sim A = A$

涉及全集和空集的算律

	$\emptyset$	$E$
补元律	$A \bigcap \sim A= \emptyset$	$A \bigcup \sim A= E$
零律	$A \bigcap \emptyset = \emptyset$	$A \bigcup E =E$
同一律	$A \bigcup \emptyset = A$	$A \bigcap E = A$
否定律	$\sim \emptyset = E$	$\sim E = \emptyset$

有序对和笛卡尔积

逆 $R^{-1} =\lbrace<y,x>|<x,y>\in R\rbrace$
合成 $R\circ S =\lbrace <x,z>|\exists y(<x,y>\in R \wedge <y,z> \in R) \rbrace$

$(F \circ G) \circ H = F \circ (G \circ H)$
$(F \circ G)^{-1} = G^{-1} \circ F^{-1}$
$F \circ (G \bigcup H) = F\circ G \bigcup F\circ H$
$(G \bigcup H) \circ F = G\circ F \bigcup H\circ F$
$(F \circ (G \bigcap H) \subseteq F\circ G \bigcap F\circ H$
$(G \bigcap H) \circ F \subseteq G\circ F \bigcap H\circ F$