Skip to content

Logic and Proofs

:material-circle-edit-outline: 约 602 个字 :material-clock-time-two-outline: 预计阅读时间 2 分钟

命题

Proposition 命题能判断真假，不过不能两个都是

tautology : 同义反复，即命题的左右式本质上是一样的

连接词

  • 我们需要五个连接词来描述复合命题

    • negation：¬
    • conjunction：∧，合取符号
    • disjunction：∨，析取符号
    • implication：→
    • biconditional：p ↔ q: p if and only if q
      • ≡
    • 优先级 1. 否定优先 2. 交并次之 3. 推断最后

公式

Propositional Formula / well formed formula，wff

  1. 每一个命题变量都是公式
  2. 两个公式通过上面的五个连接词拼一起，还是公式
  3. 通过有限次的1，2规则得到的都是公式

公式的分类

  • tautology，永真式，例如 p → p ∨ q
  • contradiction，永假式，一看就懂
  • contingence，不是上面两种就是这种

Propositional Equivalence

两个命题的 biconditional 是 tautology 的就是等价的

image-20240601211304430

image-20240601211613062

image-20240601211629540

注意结合律只能同类型符号

image-20240601211840034

Propositional Normal Forms

任何公式都能转化为下面两种范式：

  • 析取范式（disjunctive normal form (DNF)） 先 ∧ 再 ∨
    • 对应极小项
  • 合取范式（ conjunctive normal form (CNF)） 先 ∨ 再 ∧ 。

两种范式里面最小单元叫 literal，包括否定符号和原子命题，否定只能放在原子命题上，不能加在公式上

full disjunctive form/ disjunction of minterms

完全析取形式即转化为最小项的形式

image-20240601214440095

  • 获取极小值公式步骤
    1. 先求范式
    2. 再用双重否定和分配律凑，如下图

image-20240601214809789

image-20240601214850287

反证法

image-20240601220020916

image-20240601220111410

image-20240601220134313

Predicates and Quantifiers

一个包含未知数的公式，本身不是命题，但是带入未知数的值后就是命题了，这个包含未知数的公式就是一个 Predicate 谓词

Predicate 其实是一个布尔函数，取值要么是T要么是F

谓词可以通过量词的量化变成命题，量词为谓语提供了一个范围

一个全称量词，一个存在量词

image-20240601220426678

谓语和量词不能交换次序，谓语和谓语、量词和量词才可以

Banding Varibles

被量词限制的变量就是 Banding Varibles ，是 bound 的，否则就是 free 的

显然存在 free 变量的公式肯定不是命题函数，命题函数的所有变量都应该被 bound

等价谓词公式

image-20240602110954083

image-20240602111250087

image-20240602111610284

Prenex NF

前缀范式，就是把公式里所有的量词全部放前面

image-20240602112016230

注意全称量词只能在合取时取出，存在量词只能在析取时取出

Methods of proof

牛皮，看这个例题

image-20240602112833053

image-20240602112924151