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

コンピュータ基礎理論
論理演算法則集
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・B
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
女性または成年
である
上記の条件を
共に満たす