命题逻辑导图笔记

命题逻辑导图笔记，知识内容有命题、逻辑连接词、命题公式、逻辑推理、主范式、范式、等值演算等，希望梳理的内容对你有所帮助！

命题逻辑

• 命题
  • 命题：能判断真假的陈述句
    • 原子命题：不可再分解的简单陈述句
    • 复合命题：几个简单陈述句通过联结词结合而成的命题
  • 命题的判断结果
    • 真或假, 分别用1和0来表示。 真值为1的命题称为真命题; 真值为0的命题称为假命题
• 逻辑联结词
  • 否定式：┐
  • 合取式：∧
  • 析取式：∨
  • 蕴涵式：→
  • 等价式：↔
  • 对应的真值表
• 命题公式
  • 命题变量
  • 合式公式（命题公式）
    • 原子命题公式通过有限次应用否定、合取、析取、蕴涵、等价的操作组合而成的公式
  • 赋值
    • 成真赋值
    • 成假赋值
  • 分类
    • 永远为真的命题公式：重言式
    • 永远为假的命题公式：矛盾式
    • 不是矛盾式：可满足式
• 逻辑推理
  • 数学模型
  • 推理规则
    • 置换规则；假言推理规则；附加规则；化简规则；拒取式规则
    • 假言三段论规则；析取三段论规则；构造性二难推理规则；破坏性二难推理规则；合取引入规则
  • 附加前提证明法
  • 归谬证明法
• 联结词完备集
  • 任何命题公式都能由完备集中的联结词表示
  • 极小完备集
    • {┐, ∨}（或非）和{┐, ∧}（与非）
  • 证明某集合是完备集
    • 证明集合中的联结词可以表示出极小完备集
• 主范式
  • 简单合取式
    • 文字：由命题变量及其否定构成
    • 由有限个文字构成的合取式
  • 定义
    • 简单合取式全部为极小项，构成析取范式
  • 极小项
    • 在简单合取式中，每个命题变量或其否定都出现且仅出现一个
    • 用m0,m1等字母表示，其中m的下标计算：找使极小项为真的一组数据，按照二进制的方法计算
  • 极大项
    • 和极小项类似
  • 计算方法
    • 通过等值推演将所给的命题公式化为析取范式(合取范式)
    • 补齐变量，同一律和排中律
    • 消去重复和矛盾，化简成m表示
• 范式
  • 合取范式
    • 简单析取式构成
    • A=A1 A2… An, 其中 Ai (i=1,…,n)是简单合取式
  • 析取范式
    • 简单合取式构成
    • A=A1 A2 …  An, 其中 Ai (i=1,…,n)是简单析取式
  • 求取步骤
    • 1.消→和↔ (蕴涵和等价恒等式); 2.┐消去(双重否定)或内移(德摩根律); 3.利用∨对∧的分配律求合取范式; 利用∧对∨的分配律求析取范式。
  • 范式存在定理
    • 任一命题公式都存在着与之等值的析取范式与合取范式。
• 等值演算
  • 等值
    • A、B为两个命题公式，对AB任意赋值都取相同真值，则A=B
  • 置换规则
    • 与演算定律相结合
  • 对偶原则
    • 不含蕴涵和等价的运算
    • 将析取,合取,0,1分别替换成合取,析取,1,0
  • 演算定律
• (p→q)↔r =(┐p∨q)↔ r =((┐p∨q)→ r)∧(r→(┐p∨q)) =(┐(┐p∨q)∨r)∧(┐r∨(┐p∨q)) =((p∧┐q)∨r)∧(┐p∨q∨┐r) =(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)
• 证明：首先由蕴含等值式和等价等值式可知： A→B= ┐A∨B, A↔B=(┐A∨B)∧(A∨┐B) 由双重否定律和德摩根律可知： ┐┐A=A, ┐(A∧B)=┐A∨┐B, ┐(A∨B)=┐A∧┐B 利用分配律, 可得: A∧(B∨C)=(A∧B)∨(A∧C) A∨(B∧C)=(A∨B)∧(A∨C) 使用这些等值式, 便可将任一公式化成与之等值的析取范式或合取范式。
• 真值表定义：将命题公式A在所有赋值下的取值情况列成表, 称为A的真值表
• 判断命题真假：是否为陈述句+是否能判断真假