离散数学-526互联

数理逻辑分为命题逻辑和谓词逻辑两部分

命题逻辑

命题的真值只有两个：“真”或者“假”
命题的表示：用大写字母表示

逻辑连接词

复合命题由若干个连结词、标点符号及原子命题复合构成的命题

非 $\neg$

合取 $\land$

表示：并且、不但而且
定义：两个命题 P和 Q的合取是一个复合命题，记作P$\land$Q。当且仅当P和Q的真值均为 T 时P$\land$Q的真值为 T，其它情况下，P$\land$Q的真值均为F。
真值表：

析取 $\lor$

P$\lor$Q，即P和Q二者可以同时发生
当P和Q都为F时，$P\lor Q$为F，否则为$T$

异或 $\oplus$

当P和Q的真值相同时，异或的真值为F，真值不同时为T。

条件 $\rightarrow$

$P \rightarrow Q$,若P则Q
P是Q的充分条件，Q是P的必要条件

善意规定：规定P为F时，$P\rightarrow Q$的真值为T。
当且仅当 P为T，Q为F是，$P \rightarrow Q$的真值为F，其他情况皆为T。

等价 $\leftrightarrow$

表示：当且仅当、充分必要
当且仅当P与Q的真值相同时，$P \leftrightarrow Q$
真值表：

真值表

命题符号化

命题常项: 即命题的真值。
常值命题: 即具体命题。
命题变元: 用大写字母表示的任一命题。
将一个命题常项或常值命题赋予命题变元的过程称为给命题变元赋值，也称为对命题变元作指派。

合式公式

合式公式(合法的命题公式) 定义:

单个命题变元、常值命题及命题常项是合式公式
A是合式公式，则$\neg A$是合式公式。
若A和B是合式公式，则($A\land B$)，($A\lor B$)，($A\rightarrow B$)($A\leftrightarrow B$)都是合式公式。
当且仅当有限次地应用(1)，(2)，(3)所得到的符号串是合式公式。

为了简化命题公式，约定:
(1)最外层括号可省;
(2)不影响运算次序的括号可省
运算次序由高到低为：$\neg , \land ,\lor , \leftarrow , \leftrightarrow$

构造真值表

命题公式的等价

$P \rightarrow Q \iff \neg P \lor Q \iff \neg Q \rightarrow \neg P$

命题等价的定义

A、B是含有命题变元$P_1,P_2;...,P_n$的命题公式，如不论$P_1,P_2;...,P_n$作何种赋值，A和B的真值均相同，则称命题公式A与B等价，记作$A\iff B$。

真值表相同，两个命题公式等价。

基础等价公式

等价公式证明方法

方法1：列真值表
方法2：用等价公式变换（用置换定律）
置换定律:A是一个命题公式，X是A中的一部分且也是合式公式，如果$X\iff Y$，用Y代替A中的X得到公式B，则$A\iff B$。

对偶式:
在一个只含有联结词$\lnot\lor\land$的公式A 中,
把$\land$换成$\lor$，$\lor$换成$\land$，T换成F, F换成T,其余部分不变, 得到另一个公式 $A^$, 称 A 与 $A^$ 互为对偶式。

定理：
令$A(\mathsf{P}_1,\mathsf{P}_2,...,\mathsf{P}_n)$是一个只含有连结词$\lnot\lor\land$的命题公式，则
$$
\neg\mathsf{A}(\mathsf{P}_1,\mathsf{P}_2,...,\mathsf{P}_n)\Leftrightarrow\mathsf{A}^*(\neg\mathsf{P}_1,\neg\mathsf{P}_2,\ldots,\neg\mathsf{P}_n)
$$
等价
等价“$\Leftrightarrow$”是关系符号，不是运算符号，它表明的是两个命题公式之间的关系。
性质：

有自反性：对任何命题公式A，均有 $A\Leftrightarrow A$。
有对称性：若$A\Leftrightarrow A$，则$B\Leftrightarrow A$
有传递性：$若A\Leftrightarrow B且B\Leftrightarrow C,则A\Leftrightarrow C。$

重言式

重言式\永真式：T
矛盾式\永假式： F

定理：设A,B为两个命题公式,${A}\Leftrightarrow{B}$当且仅当 $A\leftrightarrow B$是一个重言式。

重言蕴含式
定义：当且仅当$A \leftrightarrow B$是重言式，则称A重言（永真）蕴含B，记作$A \Rightarrow B$
即：若$A \rightarrow B \Leftrightarrow T$,则$A \Rightarrow B$

证明方法：

假设前件A为真，证后件B为真，即$A \Rightarrow B$成立
假设后件B为假，证前件A为假，即$A \Rightarrow B$成立

例题：

基础重言蕴含式

重言蕴含性质

定理：设$A, B$ 为任意两个命题公式，$A \Leftrightarrow B$的充要条件是$A \Rightarrow B$且 $B \Rightarrow A$

若$\neg A \Leftrightarrow \neg B$,有$A \leftrightarrow B$
但是, 若$\neg A \Rightarrow \neg B$不能推出$A \Rightarrow B$,而是$B \Rightarrow A$

析取范式与合取范式

析取范式

例: $P \leftrightarrow Q \Leftrightarrow (P \land Q)\lor (\neg P \land \neg Q)$
$(P \land Q)\lor (\neg P \lor \neg Q)$ 为 $P \leftrightarrow Q$的析取范式

合取范式

例:${P}\leftrightarrow{Q}\Leftrightarrow(\neg{P}\lor{Q})\land({P}\lor\neg{Q})$

只含有非合取析取

析取范式和合取范式的写法

去掉$\rightarrow$和$\leftrightarrow$
将$\neg$移到命题变元前,用公式$\neg\mathsf{A}(\mathsf{P}_1,\mathsf{P}_2,...,\mathsf{P}_n)\Leftrightarrow\mathsf{A}^*(\neg\mathsf{P}_1,\neg\mathsf{P}_2,\ldots,\neg\mathsf{P}_n)$
用分配律,幂等律整理公式
例题: