离散数学笔记(1)——命题逻辑(1)

离散数学笔记(1)——命题逻辑(1)

命题逻辑

命题

非真即假,不可兼($T/F$)

语句算不算命题
哥德巴赫猜想
悖论(我正在说谎)不算
昨天很冷不算

原子命题与复合命题

复合命题 = 原子命题 + 联结词

联结词符号
否定$\lnot$
合取$\land$
析取$\lor$
异或$\overline{\lor}$
蕴涵$\rightarrow$
等价$\leftrightarrow$

一些对应的真值

$P$$Q$$P \land Q$$P \lor Q$$P \rightarrow Q$$P \leftrightarrow Q$
$F$$F$$F$$F$$T$$T$
$F$$T$$F$$T$$T$$F$
$T$$F$$F$$T$$F$$F$
$T$$T$$T$$T$$T$$T$

命题公式

命题常量即命题

命题变元:用大写英文字母表示任何命题,称这些字母为命题变元

对命题变元作指派(给命题变元一个解释):将一个常值命题赋予命题变元的过程,或者是直接赋给命题变元真值 $T$ 或 $F$ 的过程。

合式公式

(1)单个命题变元是个合式公式。

(2)若 $A$ 是合式公式,则 $\lnot A$ 是合式公式。

(3)若 $A$ 和 $B$ 是合式公式,则 $(A \land B)$,$(A \lor B)$,$(A \rightarrow B)$ 和 $(A \leftrightarrow B)$ 都是合式公式。

(4)当且仅当有限次地应用(1),(2),(3)所得到的含有命题变元、联结词和括号的符号串是合式公式。

运算次序优先级:$\lnot , \land , \lor , \rightarrow , \leftrightarrow$

相同的运算符按从左至右次序计算,否则要加上括号,括号最外层圆括号可省去。

命题符号化(翻译)

所谓命题符号化,就是用命题公式的符号串来表示给定的命题。

命题符号化的方法:

  1. 明确给定命题的含义。

  2. 对复合命题,找联结词,分解出各个原子命题。

  3. 设原子命题符号,并用逻辑联结词联结原子命题符号,构成给定命题的符号表达式。

重言式(永真式)与矛盾式(永假式)

不论对 $P_1,\cdots,P_n$ 做任何指派,一个命题公式都是真(假),就称为重言式(矛盾式)。

若 $A$ 是永真式,则 $A$ 的置换式也是永真式。

置换式:用合式公式代替 $P_i$ 得到的新的命题公式。

等价公式

不论对 $P_1,\cdots,P_n$ 做任何指派,两个命题公式 $A$ 和 $B$ 真值总是相同,那么称 $A$ 和 $B$ 是逻辑等价,记为 $A=B$ 或者 $A \Leftrightarrow B$。

等价定理:$A \Leftrightarrow B$ 当且仅当 $A \leftrightarrow B$ 为永真式。

常见等价公式:略

$P \rightarrow Q \Leftrightarrow \lnot P \lor Q$

$P \rightarrow Q \Leftrightarrow \lnot Q \rightarrow \lnot P$

$P \leftrightarrow Q \Leftrightarrow (P \rightarrow Q) \land (Q \rightarrow P)$

置换定律:等价的置换还等价

重言蕴涵式

重言式 $A \rightarrow B$ 是个永真式,则称 $A$ 永真蕴涵 $B$,记作 $A \Rightarrow B$。

证明 $1$:假设前件为真,推出后件为真。

证明 $2$:假设后件为假,推出前件为假。

 

点赞 4

No Comments

Add your comment