Presentation is loading. Please wait.

Presentation is loading. Please wait.

香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp 情報数学1 第5-2章 命題論理式の 同値変形とカルノー表 香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp.

Similar presentations


Presentation on theme: "香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp 情報数学1 第5-2章 命題論理式の 同値変形とカルノー表 香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp."— Presentation transcript:

1 香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp
情報数学1 第5-2章 命題論理式の 同値変形とカルノー表 香川大学工学部 富永浩之

2 概 要 ■ 論理演算の同値公式 ■ 論理式の同値変形 ■ 除法定理と整除演算 ■ カルノー表と選言標準形
概 要 ■ 論理演算の同値公式 交換律・結合律・冪等律 吸収律・分配律・反転律 対合律・同一律・相補律・境界律 ■ 論理式の同値変形 含意律 ■ 除法定理と整除演算 リテラル 節(リテラル積) 積和形式 ■ カルノー表と選言標準形 完全選言標準形 極小選言標準形

3 第01節 [1] 論理式の同値性 ● 論理式の同値性 ● 同値な論理式 論理式に現れる全ての命題変数に対して、
第01節 [1] 論理式の同値性 ● 論理式の同値性 論理式に現れる全ての命題変数に対して、 どのように真偽値の割当を与えても、常に真偽値が等しくなるような 2つの論理式 P,Q を同値[equivalent]な論理式といい、 P ⇔ Q と表す。 ● 同値な論理式 同値な論理式は、真偽値の計算において同一視できる。 2つの論理式の真偽値が一致するという関係としての同値 ⇔ と、 1つの論理式の中の論理演算としての同値 △ を混同しない。

4 第01節 [1] 論理式の同値性 ● カルノー表と論理式の同値性 2つの論理式の同値性を調べるには、
第01節 [1] 論理式の同値性 ● カルノー表と論理式の同値性 2つの論理式の同値性を調べるには、 真偽値表としてカルノー表を描いて、両者が一致することを確認すればよい。

5 第01節 [1] 論理式の同値変形 ● 論理式の同値変形 ある論理式を、それと同値な別の論理式に置き換えることを同値変形という。
第01節 [1] 論理式の同値変形 ● 論理式の同値変形 ある論理式を、それと同値な別の論理式に置き換えることを同値変形という。 論理式の性質は、真偽値のカルノー表から調べることができるが、 命題変数の個数が増え、論理式が複雑になると、非常に煩雑な処理となる。 同値変形により、真偽値が求めやすい同値式にすれば、処理が効率化される。 一般に、ある論理式中の部分式をそれと同値な論理式に 置き換えても、真偽値は全く変わらない。 すなわち、元の論理式と同値な論理式になっている。 したがって、基本的な同値変形の公式を見つけておけば、 それらを繰り返し適用することで、様々な同値変形が可能になる。

6 第01節 [2] 論理演算の基本的な同値公式 名称 連言・恒偽 選言・恒真 交換律 A∧B ⇔ B∧A A∨B ⇔ B∨A 結合律
第01節 [2] 論理演算の基本的な同値公式 名称 連言・恒偽 選言・恒真 交換律 commutative A∧B ⇔ B∧A A∨B ⇔ B∨A 結合律 associative A∧(B∧C) ⇔ (A∧B)∧C 括弧は省略可能 A∨(B∨C) ⇔ (A∨B)∨C 冪等律 idempotent A∧A ⇔ A A∨A ⇔ A 吸収律 absorptive A∧(A∧B) ⇔ A A∨(A∨B) ⇔ A 分配律 distributive A∧(B∨C) ⇔ (A∨B)∧(A∨C) A∨(B∧C) ⇔ (A∧B)∨(A∧C) 反転律 inversion ¬(A∧B) ⇔ (¬A)∨(¬B) ド・モルガン律 ¬(A∨B) ⇔ (¬A)∧(¬B) 対合律 involution ¬(¬A) ⇔ A 二重否定律 同一律 identity A∧⊥ ⇔ ⊥ A∧T ⇔ A 恒真は連言の単位元 A∨⊥ ⇔ A 矛盾は選言の単位元 A∨T ⇔ T 相補律 complemental A∧(¬A) ⇔ ⊥ 矛盾律 A∨(¬A) ⇔ T 排中律 境界律 boundary ¬⊥ ⇔ T ¬T ⇔ ⊥

7 第01節 [2] 論理演算の基本的な同値公式 ● 同値変形の過程 論理式の同値変形においては、数式の等式変形と同様に、
第01節 [2] 論理演算の基本的な同値公式 ● 同値変形の過程 論理式の同値変形においては、数式の等式変形と同様に、 どの部分式に着目し、どの同値公式を用いるかを間違えないようにする。 同値変形の過程を示すときは、適用した同値公式を明記する。 より詳細には、どの部分式を抜き出したか、部分式をどう置き換えたか、 結果を元の式にどう戻したか、も確認する。 また、交換律や結合律、括弧の省略と補足による同値変形も書き出してみる。 P∧Q∧(R∨P∨S) ⇔ ; 交換律 Q∧P∧(P∨R∨S) ⇔ ; 結合律 Q∧(P∧(P∨(R∨S))) ⇔ Q∧P ; 吸収律 Q∧(P∧(P∨(R∨S))) P∧(P∨(R∨S)) ; 吸収律 P Q∧ P P∧(P∨(R∨S)) A≡P, B≡R∨S とおく 吸収律 A∧(A∨B) ⇔ A P A≡P に戻して

8 第05節 [1] 論理式の同値変形 ● 標準化と標準形 ● カルノー表からの論理式の構成
第05節 [1] 論理式の同値変形 ● 標準化と標準形 命題論理式の真偽値の判定などを容易に行うため、扱い易い形式に同値変形する。 これを標準形[normal form]といい、標準形への変換を標準化[normalization]という。 標準形には、数式の展開に相当する選言標準形と、 因数分解に相当する連言標準形の2通りがある。通常は、選言標準形を考える。 さらに、完全選言標準形と極小選言標準形がある。 なお、標準形は式の意味を考える上で便利な形であり、 必ずしも最も簡単な式であるとは限らない。 論理式の標準化は、論理代数における簡単化と同等の操作である。 ● カルノー表からの論理式の構成 命題変数のカルノー表が与えられたとき、 それが表す命題論理式を選言標準形で求める問題を考える。 カルノー表の矩形領域が、命題変数に対するドントケア表記に対応する ことを利用する。

9 第07節 [1] 環和に対する同値性 ● 環和の換言律と対角律 ● 環和の否定 ● 環和の交換律と結合律
第07節 [1] 環和に対する同値性 ● 環和の換言律と対角律 ○ 換言律 A▽B ⇔ (A∧¬B)∨(¬A∧B) ○ 対角律 A▽B ⇔ (A∨B)∨(¬A∨¬B) ○ 含意による表現 A▽B ⇔ (A→¬B)∧(¬A→B) ● 環和の否定 ○ 環和の否定 ¬(A▽B) ⇔ (A∧B)∨(¬A∧¬B) ○ 環和の否定 ¬(A▽B) ⇔ (¬A∨B)∧(A∨¬B) ○ 含意による表現 ¬(A▽B) ⇔ (A→B)∧(B→A) ● 環和の交換律と結合律 ○ 交換律 A▽B ⇔ B▽A ○ 結合律 A▽(B▽C) ⇔ (A▽B)▽C A▽B▽C ⇔ (A∧¬B∧¬C)∨(¬A∧B∧¬C) ∨(¬A∧¬B∧C)

10 第07節 [2] 環和に対する同値性 ● 環和と命題定数 ● 環和の否定 ● 環和の交換律と結合律 ○ 冪等律 A▽A ⇔ ⊥
第07節 [2] 環和に対する同値性 ● 環和と命題定数 ○ 冪等律 A▽A ⇔ ⊥ ○ 相補律 A▽¬A ⇔ T ○ 同一律 A▽⊥ ⇔ A A▽T ⇔ ¬A ● 環和の否定 ○ 吸収律 A▽(A▽B) ⇔ A ○ 反転律 ¬(A▽B) ⇔ ¬A▽B ⇔ A▽¬B ● 環和の交換律と結合律 ○ 肯定分配律 (A∧B)▽(A∧C) ⇔ A∧(B▽C) ○ 否定分配律 (A∨B)▽(A∨C) ⇔ ¬A∧(B▽C) A 0 A 1 C 0 C 1 B 0 1 B 1 A 0 A 1 C 0 C 1 B 0 1 B 1

11 第09節 [1] 環和と同値の引数による分解 環和 同値 |P▽Q|=1 OR |P∧¬Q|=1 |¬P∧Q|=1 AND AND
OR OR |P|=0 |¬Q|=0 |¬P|=0 |Q|=0 |Q|=1 |P|=1 |P△Q|=0 AND |P∧Q|= |¬P∧¬Q|=0 OR OR |P|=0 |Q|=0 |¬P|=0 |¬Q|=0 |P|=1 |Q|=1


Download ppt "香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp 情報数学1 第5-2章 命題論理式の 同値変形とカルノー表 香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp."

Similar presentations


Ads by Google