命题逻辑
- 命题 确定&陈述
- T F
- 逻辑符号
- 命题变元
- 原子命题 原子命题变元
- 不可兼或 同时性
- 条件命题 $P \to Q = \neg P \vee Q$ 前件 后件 $1 \to$ 假
- 条件否定
- 双条件命题 同或 当且仅当 充分必要
- 联结词表示真值的联系 $\not =$ 实际逻辑关系
- 优先级 $\neg \wedge \vee \to \leftrightarrow$
- 合适公式 = 公式
- 命题公式 ⇒ 命题函数
- 指派
- 真值表
- 永真式 矛盾式 可满足公式
- $P \vee \left(P \wedge Q \right) \Leftrightarrow P \Leftrightarrow P \wedge \left(P \vee Q\right)$
- De Morgan律
- 对偶公式 $A^* ⇒ \vee \wedge T\space F$ 取反
- 功能完备集 最小功能完备集 普遍采用的功能完备集
- 有限个句节析取 ⇒ 子句，有限个子句 ⇒ 合取范式
- 单个句节，既是子句也是短语，也是合取范式和析取范式 单个子句&单个短语，既是合取范式也是析取范式
- 主合取范式 由极大项组成 永真式无 主析取范式 由极小项组成 矛盾式无 所有命题变元出现 将未出现的用 $A \wedge \neg A$ 表示，再通过分配律转化
- 命题公式的蕴涵
- $A \Rightarrow B, B \Rightarrow C 等价 A \Rightarrow B \wedge C A \Rightarrow C, B \Rightarrow C 则 A \vee B \Rightarrow C$
- 前提 逻辑结果
- 直接法 CP规则法 反证法
- 推理方法：P, T I, T E, CP
- 消解法：前提+结论否定 ⇒ 合取范式 再消除
一阶谓词逻辑
表示更普遍的规律 比命题更抽象一级
- 个体词 → 个体常量 个体变量 个体域 ⇒ 单个对象
- 谓词 → 谓词常量 谓词变量 ⇒ n元 → 关系，一元 → 特性
- 零元谓词 → 命题
- 量词 区分个体和全体
- 辖域
- 自由变元 约束变元
- $\forall \to \wedge, \exists \to \vee$
- 论域
- 改名规则
- 指导变元
- 辖域 收缩 & 扩张 不含指导变元的域 随意包住 & 排除 除了 $\to$ 这个 等价的时候任意和存在互换
- 否定 放进去 or 提出来 量词改变
- $A \vee B 和 A \wedge B$ 既是合取范式又是析取范式
- 分配律
- $\forall \wedge 和 \exists \vee$ 可以直接拆
- $(\exists x)(P(x) \to Q(x)) \Leftrightarrow (\forall x)P(x) \to (\exists x)Q(x)$
- 其他的要改不同变量名
- 多个相同量词可以换位置 不同量词不行
- 蕴含 1 ⇒ 1 规律类似
- 双量词
- 消去规则
- $US \forall \to y, c$
- $ES \exists \to c$
- $UG y \to \forall$
- $EG y, c \to \exists$
- Skolem范式 + 消解法
- 把所有量词提到最前面 变量改名
- $\exists$： 第一个代换成 a，其他的代换为 f(其他变元)
- 消解时 将 消 $\exists$ 时设的变量代换
Tips
- 考虑特殊情况 0 1
- 蕴涵 vs. 联结词
- 命题逻辑推理为逻辑推逻辑 是在逻辑层面的
- 谓词公式蕴含是逻辑推结论 实际化
- 常量 abc… 变量 xyz…
- 证明时写 “P（附加条件）”
- 化简的时候看清楚 辖域！！
题型
- 命题 → 符号逻辑 设P: …, Q: …
- 化简类 化简 or 真值表
- 永真式 矛盾式 可满足公式？
- 证明等价式
- 证明蕴含式
- 把 $\Rightarrow$ 变成 $\rightarrow$
- 再化简看是否永真…
- 不成立直接举例
- 演绎证明蕴含式 一步步 写清楚 P 还是附加条件 TI TE
- 用消解法证明蕴含式
- 将结论的否加入 转合取范式
- 写子句集合S = { …… }
- 一步步写 P 或是 _ _ 消
- 把命题翻译成谓词公式
- 设 一元？二元？
- 符号化 写式子 \forall \to, \exists \wedge
- 多句话多个\wedge
- 可以有否定
- 给论域 把公式用不含量词的公式表示
- $\forall$ 用合取，$\exists$ 用析取 （式子之间！！）
- 多层就括号 加清楚
- 证明蕴含式成立 同理 一步步等价，最后适当时候蕴含一下
- 证明推理 （演绎证明）
- P, TI, TE, US, ES, UG, EG
- 需要同时用 US 和 ES 构造相同变量消去的时候，先 ES 再 US，要不然写不成一个变量
Show Comments
