离散数学笔记_第一章:逻辑和证明(3)

简介: 离散数学笔记_第一章:逻辑和证明(3)

1.3.1 逻辑等价式


定义1


永真式(重言式): 一个真值永远为真的复合命题。(无论其中出现的命题变量的真值是什么)

矛盾式(永假式): 一个真值永远为假的复合命题。

可能式: 既不是永真式也不是矛盾式的复合命题。


永真和矛盾的例子:

p∧¬p

p∨¬p

矛盾

永真

定义2


逻辑等价: 如果p↔q是永真式,则复合命题p和q称为是逻辑等价的。记作p≡q 或 p⇔q


注意不要写成等号 " = " !


注:符号 ≡ 和 ⇔ 不是逻辑联结词,p≡q 不是一个复合命题,而是代表 “p↔q是永真式” 这个语句

等价式

名称

p∧T ≡ p ;p∨F ≡ p

恒等律

p∨T ≡ T ; p∧F ≡ F

支配律

p∨p ≡ p ;p∧p ≡ p

幂等律

¬( ¬p) ≡ p

双重否定律

p∨q ≡ q ∨ p ;p∧q ≡ q ∧ p

交换律

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) ; (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

结合律

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) ;p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

分配律(改变优先级)

¬ ( p∧q ) ≡ ¬ p∨¬ q ;¬ ( p∨q ) ≡ ¬ p∧¬ q

德·摩根律(去括号)

p ∨(p ∧ q) ≡ p ; p ∧(p ∨ q) ≡ p

吸收律

p∧¬p ≡ F ;p∨¬p ≡ T

否定律


1.3.2 条件命题和双条件命题的逻辑等价式


→ ≡ ¬ ∧ ∨

条件命题的逻辑等价式(常用)

p → q ≡ ¬ p ∨ q

p → q ≡ ¬ q → ¬ p (原命题 ≡ 逆否命题 )

(p → q) ∧ (p → r) ≡ p → (q∧ r)

(p → q) ∨ (p → r) ≡ p → (q∨ r)

双条件命题的逻辑等价式

p ↔ q ≡ (p → q) ∧ (q → p)

¬( p ↔ q) ≡ p ↔ ¬ q

p ↔ q ≡ ¬ p ↔ ¬ q

p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)


1.3.3 德·摩根律


德·摩根律 (De Morgan’s law)

德·摩根律


¬ ( p∧q ) ≡ ¬ p∨¬ q

≡ p ↑ q

¬ ( p∨q ) ≡ ¬ p∧¬ q

≡ p ↓ q

德·摩根律告诉我们如何取合取、析取的否定。


1.3.4 可满足性


可满足的

一个复合命题是可满足的,当且仅当存在一个对其变量的真值赋值使其为真。(即当它是一个永真式or可满足式时)


不可满足的

一个复合命题是不可满足的,当且仅当它的否定是可满足的。


可满足性问题的解

当我们找到一个特定的使得复合命题为真的真值赋值时(就证明了它是可满足 的),这样的一个赋值称为这个特定的可满足问题的一个解


1.3.5析取范式(基本积之和),合取范式(基本和之积)


1.3.6合式公式


1.定义

命题逻辑的合式公式 (wff, well‐formed formula)


• 1)一个命题变量 p 是一个 wff;

• 2)若 A 是 wff,则 (¬A) 也是 wff;

• 3)若 A, B 是 wff,则 (A∧B), (A∨B), (A→B), (A↔B) 也是wff;

• 4)当且仅当有限次使用上述规则得到的公式才是 wff。


上述定义是归纳定义:1)是归纳基始,2) 3)是归纳步,4)是最小化规则

命题逻辑的合式公式简称为公式或命题公式 。


⌛一般一个命题公式的真值是不确定的,只有当用确定的命题去取代命题

公式中的命题变元(变元 = 变量),或对命题变元进行真值指派时,命题公式才成为具有确定真值的命题。所以, 命题公式不是命题。


2.等价转换成主析(合)取范式

任何命题公式都可以等价地转换成它的主析取范式,也可以等价地转换成它的主合取范式


┐((P→Q)∧(R→P))∨┐((R→┐Q)→┐P)


≡ ┐((┐P∨Q)∧(┐R∨P))∨┐(┐(┐R∨┐Q)∨┐P)

≡ (┐(┐P∨Q)∨┐(┐R∨P))∨(┐┐(┐R∨┐Q)∧┐┐P)

≡ (P∧┐Q)∨(R∧┐P)∨((┐R∨┐Q)∧P)

≡ (P∧┐Q)∨(R∧┐P)∨(┐R∧P)∨(┐Q∧P)

≡ (P∧┐Q∧R)∨(P∧┐Q∧┐R)∨(R∧Q∧┐P)∨(R∧┐Q∧┐P)∨

 ∨(┐R∧Q∧P)∨(┐R∧┐Q∧P)∨(R∧┐Q∧P)∨(┐R∧┐Q∧P)

≡ (P∧┐Q∧R)∨(P∧┐Q∧┐R)∨(┐P∧Q∧R)∨(┐P∧┐Q∧R)∨(P∧Q∧┐R)

≡ m5∨m4∨m3∨m1∨m6 (主析取范式)

≡ M0∧M2∧M7 (主合取范式)

相关文章
|
7月前
【错题集-编程题】春游(模拟 - 分情况讨论)
【错题集-编程题】春游(模拟 - 分情况讨论)
|
运维 监控 架构师
第二章 软件过程与思想 第一节 基础
第二章 软件过程与思想 第一节 基础
|
算法 关系型数据库 Java
数据库原理第四章课后题答案(第四版)
数据库原理第四章课后题答案(第四版)
292 0
|
SQL 存储 自然语言处理
数据库原理第三章课后题答案(第四版)
数据库原理第三章课后题答案(第四版)
237 0
|
SQL 存储 数据挖掘
数据库原理第六章课后题答案(第四版)
数据库原理第六章课后题答案(第四版)
480 0
|
存储 数据库 数据安全/隐私保护
数据库原理第五章课后题答案(第四版)
数据库原理第五章课后题答案(第四版)
117 0
|
自然语言处理 索引
离散数学笔记_第一章:逻辑和证明(2 )
离散数学笔记_第一章:逻辑和证明(2 )
129 0
离散数学笔记_第一章:逻辑和证明(1)(下)
离散数学笔记_第一章:逻辑和证明(1)(下)
125 0
离散数学笔记_第一章:逻辑和证明(1)(上)
离散数学笔记_第一章:逻辑和证明(1)(上)
113 0
数学知识补充(一)度量空间
数学知识补充(一)度量空间
77 0