网站建设产品经理职责,四川建筑人员证书查询官网,招投标信息查询平台,杭州外贸网站多少钱1.3 命题等价式1.3.1 逻辑等价式 1.3.2 条件命题和双条件命题的逻辑等价式 1.3.3 德摩根律 1.3.4 可满足性 可满足的 不可满足的 可满足性问题的解 1.3.5析取范式#xff08;基本积之和#xff09;#xff0c;合取范式#xff08;基本和之积#xff09;1.3.6合式公式1…1.3 命题等价式 1.3.1 逻辑等价式 1.3.2 条件命题和双条件命题的逻辑等价式 1.3.3 德·摩根律 1.3.4 可满足性 可满足的 不可满足的 可满足性问题的解 1.3.5析取范式基本积之和合取范式基本和之积1.3.6合式公式1.定义2.等价转换成主析合取范式1.3.1 逻辑等价式
定义1
永真式重言式 一个真值永远为真的复合命题。无论其中出现的命题变量的真值是什么 矛盾式永假式 一个真值永远为假的复合命题。 可能式 既不是永真式也不是矛盾式的复合命题。
永真和矛盾的例子
p∧¬pp∨¬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 ∨ qp → 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 ↔ ¬ qp ↔ 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 (主合取范式)
