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

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

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

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

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

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

第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 に戻して

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

第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)

第07節 [2] 環和に対する同値性 ● 環和と命題定数 ● 環和の否定 ● 環和の交換律と結合律 ○ 冪等律 A▽A ⇔ ⊥ 第07節 [2] 環和に対する同値性 ● 環和と命題定数 ○ 冪等律 A▽A ⇔ ⊥ ○ 相補律 A▽￢A ⇔ Ｔ ○ 同一律 A▽⊥ ⇔ A A▽Ｔ ⇔ ￢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