离散数学 1. 符号表、集合和命题

一切没有判断内容的句子都不能作为命题,命题应该是一个陈述语句

设p为任意命题,非p称为p的否定式,记为﹁p。

p∧q 含义为 “p并且q”或“p与q” ; p∨q 含义为“p或q”,均为假才为假。

∧∨⊕ 相当于 or , and ,xor

p↔q 为 p与q 的等价式。q , p相同才为真。

所有连接词的优先级为:否定,合取,析取 , 蕴涵,等价。

- 同级按从左到右

公式g为可满足公式, 如果它不是永假。那么g当且仅当至少有一个解释i , 使g在 i 下为真。若g为永真 , 则g一定为可满足公式,反之则不满足 。

- 永假公式(矛盾式 ,永真公式为重言式)在它所有解释下其真值都为假,也可称为不可满足公式。

如果p↔q ,为永真式 , 则充分必要条件是p 和q称为逻辑等价 , p≡ q 。

结合律 :g∨( h v s) = (g v h) v s 同 换成 ∧

- 分配律 :

g ∨( h ∧ s ) = ( g∨ h ) ∧ (g ∨ s)

g ∧ ( h ∨ s ) = (g ∧ h )∨ (g ∧ s )

- 吸收律 :

g ∨ ( g ∧ h ) = g

g ∧ ( g ∨ h ) = g

- 德摩根律 :

﹁ ( g ∨ h) = ﹁ g ∧ ﹁ h

﹁ ( g ∧ h) = ﹁ g ∨ ﹁ h

- 蕴含式 :

g → h = ﹁ g∨ h

- 假言易位

g → h = ﹁ h → ﹁ g (逆否命题 )

- 等价式

g ↔ h = ( g → h ) ∧ ( h → g ) = ( ﹁ g ∨ h)∧ ( ﹁ h ∨ g)

- 等价否定式

g ↔ h =﹁ g ↔ ﹁ h

- 归谬论

(g → h )∧ ( g → ﹁ h) = ﹁ g