离散数学 note

离散数学

• 第一章：逻辑与证明
• • 1.命题逻辑
  • • 1.1 条件语句（蕴含）
    • 1.2 命题
    • 1.3 复合命题的真值表
    • 1.4 逻辑运算符的优先级
    • 1.5 逻辑运算与位运算
  • 2.命题等价式

第一章：逻辑与证明

1.命题逻辑

1.1 条件语句（蕴含）

定义：p→q（如果p，则q），p真q假时，条件语句为假，否则为真

注意：结果为假时，条件不能真；条件为假时，结果可真可假

（真推不出假，假可推出真）

p→q的几种表示方法：

• “p是q的充分条件”
• “q是p的必要条件”
• “如果p，则q”
• “q由p得出”
• “p蕴含q”
• “q仅当p”
• “q每当p”
• “q当p”
• “q除非┐p”

条件命题：p→q

逆命题：q→p（条件与结果交换）

逆否命题：┐q→┐p（条件与结果交换并都取非）

反命题：┐p→┐q（条件与结果都取非）

1.2 命题

命题是一个陈述语句，它或真或假，但不能既真又假

• 命题的否定：┐p（非p），其真值与p的真值相反
• 合取：p∧q（p并且q），全真为真，否则为假
• 析取：p∨q（p或q），全假为假，否则为真
• 异或：p⊕q，p和q中恰好只有一个为真时命题为真，否则为假
• 双条件语句（双蕴含）：p↔q（p当且仅当q），全真/全假时为真，否则为假

p↔q的几种表示方法：

• “p是q的充分必要条件”
• “如果p那么q，反之亦然”
• “p当且仅当q”（If and only if）用“iff”表示

1.3 复合命题的真值表

• 含有n个变量的命题公式的命题表有22行

1.4 逻辑运算符的优先级

1.5 逻辑运算与位运算

• 用OR、AND、XOR表示∨、∧、⊕

2.命题等价式

• 永真式（重言式）：真值永远是真的复合命题（不管其中出现的命题变量的真实是什么）
• 矛盾式：真值永远是假的复合命题
• 可能式：既不是永真式又不是矛盾式
• 可满足式：非矛盾式的命题公式

逻辑等价式：如果p↔q是永真式，则称p与q逻辑等价，记为p≡q或p⇔q

德·摩根律

• ┐(A∧B) ⇔ ┐A∨┐B
• ┐(A∨B) ⇔ ┐A∧┐B

分配律

• A∨(B∧C) ⇔ (A∨B)∧(A∨C)
• A∧(B∨C) ⇔ (A∧B)∨(A∧C)

吸收率

• A∨(A∧B) ⇔ A
• A∧(A∨B) ⇔ A

条件命题的逻辑等价式

• A→B ⇔ ┐A→ ┐B
• A→B ⇔ ┐A∨B
• A∨B ⇔ ┐A→B
• A∧B ⇔ ┐(A→ ┐B)
• ┐(A→B) ⇔ A∧┐B
• (A→B)∧(A→C) ⇔ A→(B∧C)
• (A→C)∧(B→C) ⇔ (A∨B)→C
• (A→B)∨(A→C) ⇔ A→(B∨C)
• (A→C)∨(B→C) ⇔ (A∧B)→C

双条件命题的逻辑等价式

• A↔B ⇔ (A→B)∧(B→A)
• A↔B ⇔ ┐A↔ ┐B
• A↔B ⇔ (A→B)∨(┐A↔ ┐B)
• ┐(A↔B) ⇔A↔ ┐B

归谬论：(A→B)∧(A→ ┐B) ⇔ ┐A

证明永真式：证明命题逻辑上等价于T