离散数学（一）知识梳理
逻辑和证明部分
命题逻辑题型
命题符号化问题
将自然语言转为符号化逻辑命题
用命题变量来表示原子命题
用命题联结词来表示连词
命题公式的类型判断
判断命题公式是否是永真式、矛盾式、可能式
利用真值表判断
利用已知的公式进行推理判断
利用主析取和合取范式判断
定理：A为含有n个命题变元的命题公式，若A的主析取
范式含有2^n个极小项，则A为重言式，若极小项在0到
2^n之间，则为可满足式，若含有0个极小项，则A为矛
盾式；若A的主合取范式含有2^n个极大项，则A为矛盾
式，若极小项在0到2^n之间，则为可满足式，若含有0
个极小项，则A为重言式
翻译：一个命题公式化成主范式后，若所有项都分布
在主析取范式中（主合取范式为1）则为重言式；若所
有项都分布在主合取范式中（主析取范式为0）则为矛
盾式；若均有分布，则为可满足式。【思想来源：真
值表法求主范式】
一个质析取式是重言式的充要条件是其同时含有某个
命题变元及其否定式；一个质合取式是矛盾式的充要
条件是其同时含有某个命题变元及其否定式
一个析取范式是矛盾式当且仅当它的每项都是矛盾
式；一个合取范式是重言式当且仅当它的每项都是重
言式
求（主）析取或合取范式
等值演算法
1. 利用条件恒等式消除条件（蕴含和双条件）联结
词，化简得到一个范式
2. 在缺项的质项中不改变真值地添加所缺项，化简得
到一个主范式
3. 出包含所有命题变元排列中剩余项，凑出另一个
主范式（思想上类似于真值表法）
真值表法
1. 画出命题公式真值表
2. 根据真值表结果求出主范式
主析取范式：真值为1的所有项，每一项按对应01
构成极小项
主合取范式：真值为0的所有项，每一项按对应01
构成极大项
形式证明与命题推理
利用推理规则构造一个命题公式的序列，证明结论形式证明：命题逻辑的论证是一个命题公式的序列，其中每个公式或者是前提，或者是由它之前的公式作为前提推得的结论，序列的最后一个是待证的结论，这样的论证也称为形式证明。
核心方法
把非条件语句全部转为条件语句
利用条件的逆否命题和双条件的拆分
利用重言式/矛盾式来不改变真值地添项
蕴含证明规则：A1,A2, …, An⇒ A → B 等价于A1,A2, …,
An,A⇒ B【意义：使用结论的前提时应标为附加前提】
（适用：结论为条件语句）
反证法：若要证A1,A2, …, An⇒ B，将ØB加入前提，通
过证明：A1,A2, …, An, ØB⇒ C, ØC完成证明。（适用：
结论仅单命题）
根据已知命题构造满足一定真值组合条件的命题表达式
真值表的应用
画出逻辑命题的真值表，注意n个命题变元的真值表有2^n行谓词逻辑题型
涉及谓词的命题符号化问题
注意论域与量词的表示方法
特性谓词
存在量词/全称量词
判断谓词公式的真值/谓词公式关系式对错判断
对于一个谓词逻辑公式，给每个谓词符号指定一个具体谓
词，每个自由变量取定其个体域中的个体，称为这个谓词
逻辑公式的一个解释。一个谓词逻辑公式，如果它在每个
解释的真值均为真，则称其为永真式。
A≡ B当且仅当A↔B为永真式；；A⇒B当且仅当A→B为永真
式。
谓词逻辑推理证明的检错和纠错
推理规则（将量词去掉，将谓词逻辑的推理化作命题逻辑
的推理）
全称示例US：∀xA(x) ⇒A(x)
全称生成UG：A(x)⇒ ∀xA(x)
存在示例ES：∃xA(x) ⇒A(c) （c为特定解释）
存在生成EG：A(c)⇒ ∃xA(x)
基础知识
逻辑运算符/联结词
合取（Conjunction）：交集，且运算
第一范式正则化不能产生稀疏解
析取（Disjunction）：并集，或运算
异或
否定/非
条件
双条件
命题公式分类
重言式/永真式
命题公式的逻辑等价
双条件为永真式
命题公式的蕴含关系
蕴含为永真式
矛盾式
可满足式/可能式
范式（Normal Form）【判断：看最外层的运算符】原子命题：不能继续拆分的命题（包括否命题）质XX式
质合取式：若干原子命题的合取
质析取式：若干原子命题的析取
XX范式
析取范式：质合取式的析取
合取范式：质析取式的合取
主范式
普通范式不具有唯一性，主范式具有唯一性最小项：包含所有项的合取式
最大项：包含所有项的析取式
主析取范式：每项质合取式都是最小项
主合取范式：每项质析取式都是最大项命题运算律
交换律
结合律
分配律
p∨ (q∧r) ≡ (p ∨q) ∧(p ∨r)
p∧(q ∨r) ≡ (p ∧q) ∨(p ∧r)
p→ q≡ ¬p∨ q
p↔ q≡ (p ∧ q)∨ (¬p∧ ¬q)
推理规则
假言推理：p → q, p ⇒ q
取拒式：p → q, Øq ⇒ Øp
假言三段论：p → q, q→ r ⇒ p → r
析取三段论：p ∨ q, Øp ⇒ q
附加律：p ⇒ p ∨ q
化简律：p ∧ q ⇒ p
合取律：p, q⇒ p ∧ q
消解律：p ∨ q, Øp ∨ r ⇒ q ∨ r
谓词和量词
与函数对比：y=f(x)
谓词：定义运算关系f
量词：定义x取值范围（论域）
二者共同决定真值y
由上述元素构成命题函数
量词种类
全称量词
特称量词/存在量词
唯一性量词
命题函数表示方式
大写字母表示谓词
小写字母表示个体（命题函数中个体出现的次序很重
要）
论域与特性谓词
引入特性谓词来代替论域声明
特性谓词和普通谓词应用不同的字母体系来表示
特性谓词表示方式
∀xP(x)  ⇝  ∀x(A(x)→ P(x))
∃xP(x)  ⇝  ∃x(A(x)∧ P(x))

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。