このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

ブール代数の公理

 ブール代数は0と1だけからなる代数系で、演算として∧、∨、 ̄が定義されている。これ以外の演算子を利用するとして公理化することができるが、この3つだけでそうした演算子をすべて導出できてしまうのである。公理はなるべく単純なほうがよいから、この3つの演算子からスタートするわけだ。

[公理]
(1)交換
A∧B=B∧A
A∨B=B∨A
(2)分配
A∧(B∨C)=(A∧B)∨(A∧C)
A∨(B∧C)=(A∨B)∧(A∨C)
(3)結合
A∧(B∧C)=(A∧B)∧C
A∨(B∨C)=(A∨B)∨C
(4)単位(0,1)
A∧1=A
A∨0=A
(5)相補
A∧ ̄A=0
A∨ ̄A=1

 ∧を×、∨を+に、 ̄Aを(1-A)に置き換えて考えると、四則演算に似ているはずだ。ただし、ブール代数は0と1の世界なので、1+1は1と考える。ただ、こうした考え方は厳密には正しくないので、計算のときにイメージとして活用する程度に考えておいてほしい。

 きちんとブール代数を定義しておこう。

[定義]
束(B;+,・)において、和の積に関する分配律と積の和に関する分配律とが共に成立し、かつ最大元と最小元が存在し、任意の元に補元が存在するとき、その代数系をブール束(ブール代数)という。

 ブール代数とU上の集合代数の演算を次のように対応させると、すべて成立する。

U←→I

φ←→O

∪←→+

∩←→・

( ̄)←→( ̄)

命題とブール代数

 命題の演算とブール代数の演算は対応付けされたが、演算で使う値はとして、ブール代数では0と1を使う。そこで、命題における真を1、偽を0に割り当てる。後は、真理表もTを1、Fを0に書き換えたものが成り立つ。

参考文献

  • 『工科系の論理数学入門』(カットシステム)
  • 『形式言語と有限オートマトン入門』(コロナ社)