离散数学拾遗

离散数学是什么?

离散数学(Discrete mathematics)是数学的几个分支的总称,研究基于离散空间而不是连续的数学结构。与连续变化的实数不同,离散数学的研究对象 —— 例如整数、图和数学逻辑中的命题 —— 不是连续变化的,而是拥有不等、分立的值。因此离散数学不包含微积分和分析等连续数学的内容。离散对象经常可以用整数来枚举。更一般地,离散数学被视为处理可数集合(与整数子集基数相同的集合,包括有理数集但不包括实数集)的数学分支。但是,离散数学不存在准确且普遍认可的定义。实际上,离散数学经常被定义为不包含连续变化量及相关概念的数学,甚少被定义为包含什么内容的数学。

基础知识

逻辑符号

原子命题

 $p,\, q,\, r,\, \ldots$ 表示原子命题(简单命题)

 1 表示命题的真值为真

 0 表示命题的真值为假

联结词

否定联结词

 $\neg$ 称为否定联结词

 $\neg p$ 称为 $p$ 的否定式

$p$ $\neg p$
0 1
1 0
合取联结词

 $\wedge$ 称为合取联结词(AND)

 $p\, \wedge\, q$ 称为 $p$ 与 $q$ 的合取式

$p$ $q$ $p\, \wedge\, q$
0 0 0
0 1 0
1 0 0
1 1 1

 可以将 $p\, \wedge\, q$ 理解为 $p \cdot q$

析取联结词

 $\vee$ 称为析取联结词(OR)

 $p\, \vee\, q$ 称为 $p$ 与 $q$ 的析取式

$p$ $q$ $p\, \vee\, q$
0 0 0
0 1 1
1 0 1
1 1 1

 可以将 $p\, \vee\, q$ 理解为 $p + q$

蕴涵联结词

 $\rightarrow$ 称为蕴涵联结词

 $p\, \rightarrow\, q$ 称为 $p$ 与 $q$ 的蕴含式

$p$ $q$ $p\, \rightarrow\, q$
0 0 1
0 1 1
1 0 0
1 1 1

 可以将 $p\, \rightarrow\, q$ 理解为 $p \leq q$

等价联结词

 $\leftrightarrow$ 称为等价联结词

 $p\, \leftrightarrow\, q$ 称为 $p$ 与 $q$ 的等价式

$p$ $q$ $p\, \leftrightarrow\, q$
0 0 1
0 1 0
1 0 0
1 1 1

 可以将 $p\, \leftrightarrow\, q$ 理解为 $p = q$

优先级

 分别是 $\neg$, $\wedge$ $\vee$, $\rightarrow$ $\leftrightarrow$

逻辑公式

命题公式

  • 单个命题变元(常元)是命题公式
  • 若 $A$ 是命题公式,则 $\neg A$ 也是
  • 若 $A,\, B$ 是命题公式,则 $A \wedge B$、$A \vee B$、$A \rightarrow B$ 和 $A \leftrightarrow B$ 也是
  • 只有有限次应用上述三个方式形成的字符串才是

真值表

$p$ $q$ $p \rightarrow q$ $p \wedge \neg p$ $p \wedge (p \vee q) \leftrightarrow p$
0 0 1 0 1
0 1 1 0 1
1 0 0 0 1
1 1 1 0 1
赋值 赋值 可满足式 矛盾式 or 永假式 重言式 or 永真式
真值表中结果数量是 2 的 n 次方(其中,n 为原子命题的数量)

等值式

 等值式 $A \Leftrightarrow B$ 表示 $A \leftrightarrow B$ 是永真式

$p$ $q$ $p \rightarrow q$ $\neg p \vee q$ $(p \rightarrow q) \leftrightarrow (\neg p \vee q)$
0 0 1 1 1
0 1 1 1 1
1 0 0 0 1
1 1 1 1 1

 $\therefore p \rightarrow q \Leftrightarrow \neg p \vee q$

基本等值式

幂等律

交换律

结合律

分配率

德摩根律

吸收率

零律

同一律

排中律

矛盾律

双重否定率

蕴涵等值式

等价等值式

可以理解为 A 是 B 的充分必要条件

等价否定等值式

假言易位

归谬论

对偶原理

 $\vee$ 和 $\wedge$ 互换,0 和 1 互换之后,等值式仍然成立

推理定律

 推理定律 $A \Rightarrow B$ 表示 $A \rightarrow B$ 是永真式

附加律

化简律

假言推理

拒取式

析取三段论

假言三段论

蕴涵的传递性

等价三段论

等价的传递性

构造性两难

LaTeX

离散数学 LaTeX 符号
否定 \neg $\neg$
合取 \wedge $\wedge$
析取 \vee $\vee$
蕴涵 \rightarrow $\rightarrow$
等价 \leftrightarrow $\leftrightarrow$
推出 \Rightarrow $\Rightarrow$
等值 \Leftrightarrow $\Leftrightarrow$
任意 \forall $\forall$
存在 \exists $\exists$

资料

Book

欢迎加入我们的技术群,一起交流学习

群名称 群号
人工智能(高级)
人工智能(进阶)
BigData
算法

欢迎关注我的其它发布渠道