离散数学基础笔记

完美的数学终于“自我相关”
数理逻辑 — 用计算的方法代替人们思维中的逻辑推理过程
命题演算、谓词演算
悖论不能作为命题 — 真值不存在 — “这句话是错的”
命题非真即假 — 这是个基本假设
排中律 — 具有属性 / 不具有属性
反证法就是利用的排中律 — 非假即真
有穷事物可以逐个验证来判断真假 — 但是无穷事物无法逐一检验
原子命题、复合命题、逻辑连接词
形式化的第一步 — 抽象 — 仅关注命题的本质属性(真值)
异或 — p xor q == $(p \land \lnot q) \lor (\lnot p \land q)$
p 蕴含 q — 仅在 p真q假 时为假
命题公式用来把真值连接 可以看做是一个真值函数
自然语言命题的形式化 — 经过抽象形式化为命题公式
假言易位 — 逆否命题 — $a\to b <=> \lnot b \to \lnot a$
归谬论 — $(a\to b) \land (a\to \lnot b) <=> \lnot a$
重言式代入原理 — 将重言式A的某个变元p替换为B 仍然是重言式
命题公式的替换原理 — 将子公式的部分出现替换为逻辑等价的公式 得到的新命题公式和原来的逻辑等价
证明逻辑等价式和逻辑蕴含式 — 真值表法、对赋值进行讨论、推演法(利用已知的,运用代入原理和替换原理)
范式 — 把蕴含这个连接词去掉
范式用于重言式和矛盾式的识别
重言式识别:合取范式的每个析取子句都包含了至少一个互补文字对
矛盾式识别:析取范式的每个析取子句都包含了至少一个互补文字对
p蕴含q 利用蕴含等值式变成 $\lnot p \lor q$
p双向蕴含q 利用等价等值式变为$(\lnot p \lor q)\land(p \lor \lnot q)$或者$(p\land q) \lor (\lnot p\land\lnot q)$
利用德摩根律把否定词放到括号里(作用于文字)
最后再用分配律
一个公式的析取范式或合取范式都不是唯一的
析取范式也可以同时是合取范式
最为规范的范式 — 唯一性 — 主范式
主析取范式 — 每个合取子句均恰好出现一次
主合取范式 — 每个析取子句均恰好出现一次
极小项只有唯一的成真赋值
主析取范式包含的极小项的成真赋值也是主析取范式的成真赋值
具有相同主析取范式的公式是等值的 — 属于同一个等值类
主合取范式对应极大项和成假赋值
等值类与真值函数一一对应
功能完备集去掉冗余连接词得到极小的功能完备集 — 可以表示所有的真值函数
Peirce记号 — $p \downarrow q = \lnot (p \lor q)$
形式系统 — 符号体系
证明是演绎在公式集合为空集的时候的特例
命题演算形式系统(PC)的公理

  • $A1:A\to (B\to A)$

  • $A2:(A\to (B\to C))\to ((A\to B)\to (A\to C))$

  • $A3:(\lnot A\to \lnot b)\to (B\to A)$

推理规则 — 分离规则
$A, A\to B / B$ 即A成立且已知A蕴含B时可以得到B成立
PC的定理 — 有一个证明序列 — 是重言式
演绎结果 — 存在演绎结果
元(meta)定理

  • 演绎公理 — $\gamma \vdash A \to B \iff \gamma \bigcup {A} \vdash B$

  • 归谬定理 — $\gamma \bigcup {\lnot A} \vdash B, r \bigcup {\lnot A} \vdash \lnot B$,那么$\gamma \vdash A$

  • 穷举定理 — $\gamma \bigcup {\lnot A} \vdash B, \gamma \bigcup {A} \vdash B$,那么$\gamma \vdash B$成立