コンピュータ科学の基礎論理演算法則集

コンピュータ基礎理論
論理演算法則集
http://els.ai-plus.com/
論理演算の法則
• 同一の法則
A＋A＝A A・A＝A A＋A＝0
• 交換の法則
B＋A＝A＋B B・A＝A・B
• 分配の法則
A・(B＋C)＝(A・B)＋(A・C)
A＋(B・C)＝(A＋B)・(A＋C)
• 結合の法則
A＋(B＋C)＝(A＋B)＋C
A・B・C＝A・B・C
http://els.ai-plus.com
※計算順序は、（）内、否定、積、和の順
論理演算の法則（続き）
• 吸収の法則
A＋(A・B)＝A A・(A＋B)＝A
A＋(A・B)＝A＋B (A・B)＋B＝A＋B
• 復元の法則
A＝A
• 定数との演算
A＋1＝1 A＋0＝A A＋A＝1
A・1＝A A・0＝0 A・A＝0
• ド・モルガンの公式
A・B＝A＋B A＋B＝A・B
http://els.ai-plus.com
※計算順序は、（）内、否定、積、和の順
論理演算の法則（続き）
• 排他的論理和の公式
A＋B＝(A・B)＋(A・B)＝(A・B)・(A＋B)
http://els.ai-plus.com
※計算順序は、（）内、否定、積、和の順
同一の法則
• 同じ条件の論理和、論理積は、条件を1つだけにし
ても同じ
– 例）条件Aを女性であるとしたとき
A＋A＝A （女性または女性は、やっぱり女性）
A・A＝A （女性かつ女性は、やっぱり女性）
• 同じ条件の排他的論理和は、条件を満たすことが
絶対にないので偽(0)
– 例）条件Aを女性であるとしたとき
A＋A＝0
http://els.ai-plus.com
A
A
この部分が、女性
かつ女性でない人
ということになる
そんな人はいない
交換の法則
• 論理和、論理積の左右を入れ替えても、結果
は同じ
– 例）条件Aを男性である、条件Bを成年であるとし
たとき
B＋A＝A＋B
B・A＝A・Ｂ
A
B
男性または成年なら条件を満た
すということなので、結局同じ
http://els.ai-plus.com
A
B
男性かつ成年なら条件を満た
すということなので、結局同じ
分配の法則
• 例）条件Aを男性である、条件Bを成年である、条件C
を学生であるとしたとき
A・（B＋C）＝（A・B）＋（A・C）
A・（B＋C）は、男性であるという条件と、成年ま
たは学生という条件を共に満たすということ
A
B
A
C
B
A
C
年齢と職業はともか性別はともかく、成年
く、男性である
または学生である
A
B
http://els.ai-plus.com
（A・B）＋（A・C）は、男性かつ成年であるという条
件と、男性かつ学生という条件のどちらかを満た
すということ
C
上記の条件を共に
満たす
B
A
C
B
C
職業はともかく、男性年齢はともかく、男性
かつ成年である
かつ学生である
A
B
C
上記の条件のどち
らかを満たす
分配の法則（続き）
• 例）条件Aを男性である、条件Bを成年である、条件C
を学生であるとしたとき
A＋（B・C）＝（A＋B）・（A＋C）
A＋（B・C）は、男性であるという条件と、成年か
つ学生という条件のどちらかを満たすというこ
と
A
B
A
C
B
A
C
年齢と職業はともか性別はともかく、成年
く、男性である
かつ学生である
A
B
http://els.ai-plus.com
（A＋B）・（A＋C）は、男性または成年であるという
条件と、男性または学生という条件を共に満たす
ということ
C
上記の条件のどち
らかを満たす
B
A
C
B
C
職業はともかく、男性年齢はともかく、男性
または成年である
または学生である
A
B
C
上記の条件を共に
満たす
結合の法則
• 論理演算子が同じであれば、（）はどこにあっても同じ
– 例)条件Aを男性である、条件Bを成年である、条件Cを学生であるとし
たとき
A＋（B＋C）＝（A＋B）＋C
A
B
A
B
C
年齢と職業はとも
かく、男性である
A
C
性別はともかく、成年
または学生である
B
A
C
B
職業はともかく、男性性別と年齢はともか
または成年である
く、学生である
A
B
A
C
A＋（B＋C）とは、上記の2つの条件の
どれかを満たすこと
http://els.ai-plus.com
C
B
C
（A＋B）＋Cとは、上記の2つの条件の
どれかを満たすこと
結合の法則（続き）
• 論理演算子が同じであれば、（）はどこにあっても同じ
– 例)条件Aを男性である、条件Bを成年である、条件Cを学生であるとし
たとき
A・（B・C）＝（A・B）・C
A
B
A
B
C
年齢と職業はとも
かく、男性である
A
C
性別はともかく、成
年かつ学生である
B
A
C
B
職業はともかく、男性性別と年齢はとも
かつ成年である
かく、学生である
A
B
A
C
A・（B・C）とは、上記の2つの
条件を共に満たすこと
http://els.ai-plus.com
C
B
C
（A・B）・Cとは、上記の2つの
条件を共に満たすこと
吸収の法則
• 例）条件Aを女性である、条件Bを成年である
としたとき
A＋（A・B）＝A
A
B
A
年齢はともかく、女性
A
A・（A＋B）＝A
B
女性かつ成人
B
年齢を問わず女性であれば、上記
のうちいずれかを満たす
http://els.ai-plus.com
A
B
年齢はともかく、女性
A
A
B
女性または成人
B
上記の条件を共に満たすのは、
年齢を問わず女性
吸収の法則（続き）
• 例）条件Aを女性である、条件Bを成年である
としたとき
（A・B）＋B＝A＋B
A＋（A・B）＝A＋B
A
B
A
B
年齢はともかく、女性女性ではない成人
A
B
女性または成人なら、上記のうち
いずれかを満たす
http://els.ai-plus.com
A
B
A
B
女性だが成人では性別はともかく、成人
ない
A
B
女性または成人なら、上記のうち
いずれかを満たす
復元の法則
• 否定の否定は、肯定
– 例）条件Aを女性であるとしたとき
A＝A（女性でないという条件を満たさないのは、
やっぱり女性）
http://els.ai-plus.com
A
A
A
女性である
女性ではない
女性であるという
条件を満たさない
定数との演算
• 1は真（絶対に条件を満たす）、0は偽（絶対に条件
を満たさない）
例）条件Aを男性であるとしたとき
A＋1＝1
A＋0＝A
A
A
1
男性である
1
絶対に条件を
満たす
http://els.ai-plus.com
A
男性である
この2つのうちどちらか
を満たせばいいので、
絶対に条件を満たす
0
絶対に条件を
満たさない
この2つのうちどちらか
を満たせばいいので、
男性ならば条件を満た
す
定数との演算（続き）
• 1は真（絶対に条件を満たす）、0は偽（絶対に条件
を満たさない）
例）条件Aを男性であるとしたとき
A＋A＝1
A・1＝A
A
A
1
男性である
A
男性ではない
http://els.ai-plus.com
A
男性である
この2つのうちどちらか
を満たせばいいので、
絶対に条件を満たす
1
絶対に条件を
満たす
この2つを共に満たさな
ければならないので、
男性ならば条件を満た
す
定数との演算（続き）
• 1は真（絶対に条件を満たす）、0は偽（絶対に条件
を満たさない）
例）条件Aを男性であるとしたとき
A・0＝0
A・A＝0
A
A
0
男性である
0
絶対に条件を
満たさない
http://els.ai-plus.com
0
男性である
この2つを共に満たさな
ければならないので、
絶対に条件を満たさな
い
A
男性ではない
この2つを共に満たさな
ければならないので、
絶対に条件を満たさな
い
ド・モルガンの法則
• 例）条件Aを女性である、条件Bを成年であるとしたと
き
– A・B＝A＋B
A・Bとは、A・Bではないということ
http://els.ai-plus.com
A
B
女性かつ成人である
A
B
上記の条件を満たさない
A＋Bとは、Aではないか、Bではないということ
A
B
A
B
年齢はともかく、女性性別はともかく、成年
ではない
ではない
A
B
上記の条件のいずれかを満たす
ド・モルガンの法則（続き）
• 例）条件Aを女性である、条件Bを成年であるとしたと
き
– A＋B＝A・B
A＋Bとは、A＋Bではないということ
http://els.ai-plus.com
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
女性ではない成年
である
A
http://els.ai-plus.com
B
B
成年ではない女性
である
上記の条件の
うち、いずれ
かを満たす
A
B
A
女性かつ成年という
条件を満たさない
A
B
B
女性または成年
である
上記の条件を
共に満たす

Download Report