Basics of Boolean algebraブール代数だいすう

document_iddoc_f2c1125c4185993d00a57c7b4f3e09detitleブール代数の基本講義type講義content_typelecturedate2026-07-01categorymathdescription命題論理、集合演算、べき集合の束をつなぐブール代数の基本を説明する。prerequisites集合演算 / 論理演算 / 半順序関係 / 束の基本

Boolean algebraブール代数だいすう is a structure for treating logic論理ろんり and set operations集合演算しゅうごうえんざん in the same formal shape. The propositional operations “and,” “or,” and “not” correspond to intersection共通部分きょうつうぶぶん, union和集合わしゅうごう, and complement補集合ほしゅうごう of sets集合しゅうごう.

data/lecture/math/discrete-math/propositions-predicates-and-quantifiers.lecture.n.md data/lecture/math/discrete-math/lattice-basics.lecture.n.md

1Terms and definition

Let the lattice束そく $(B, \lor, \land)$ have a least element $0$ and a greatest element $1$ . Suppose that for every $x, y, z \in B$ it satisfies both distributive laws分配律ぶんぱいりつ:

x \land (y \lor z) = (x \land y) \lor (x \land z),

x \lor (y \land z) = (x \lor y) \land (x \lor z) .

If every $x \in B$ has a complement補元ほげん $x^{'}$ satisfying

x \land x^{'} = 0, x \lor x^{'} = 1,

then $(B, \lor, \land,^{'}, 0, 1)$ is a Boolean algebraブール代数だいすう. Thus a Boolean algebra is a bounded distributive lattice有界分配束ゆうかいぶんぱいそく equipped with a complement for every element. We will prove below that these axioms make the complement unique.

2Correspondence with truth sets of predicates

Fix a universal set全体集合ぜんたいしゅうごう $U$ and predicates $P (x), Q (x)$ on $U$ . Let the truth set真理集合しんりしゅうごう of $P$ be

S_{P} = {x \in U ∣ P (x)} .

Similarly, let $S_{Q} = {x \in U ∣ Q (x)}$ .

Then logical operations and set operations correspond as follows.

Formula	Truth set
$P \land Q$	$S_{P} \cap S_{Q}$
$P \lor Q$	$S_{P} \cup S_{Q}$
$\neg P$	$U ∖ S_{P}$
$P \Rightarrow Q$	$(U ∖ S_{P}) \cup S_{Q}$
$P \Leftrightarrow Q$	$(S_{P} \cap S_{Q}) \cup ((U ∖ S_{P}) \cap (U ∖ S_{Q}))$

This correspondence lets us read transformations of logical formulas as set operations集合演算しゅうごうえんざん. In particular, $P \Rightarrow Q$ is true for every $x \in U$ exactly when $S_{P} \subseteq S_{Q}$ , and $P \Leftrightarrow Q$ is true for every $x \in U$ exactly when $S_{P} = S_{Q}$ .

3A power set冪集合べきしゅうごう is a Boolean algebraブール代数だいすう

For any set $U$ , the power set冪集合べきしゅうごう $[PARSE ERROR: Undefined("Command(\"mathcal\")")] P (U)$ becomes a Boolean algebra using the inclusion order, union, intersection, and complement.

X \lor Y = X \cup Y

X \land Y = X \cap Y

X^{'} = U ∖ X

Here $\lor$ denotes join結むすび, $\land$ denotes meet交まじわり, and $'$ denotes complementation. Thus the logical operations $\lor, \land, \neg$ correspond in this example to $\cup, \cap, U ∖ (-)$ , respectively.

Here $0 = [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ and $1 = U$ . Union and intersection satisfy both distributive laws, and $X^{'} = U ∖ X$ satisfies $X \cap X^{'} = [PARSE ERROR: Undefined("Command(\"varnothing\")")]$ and $X \cup X^{'} = U$ . Thus every part of the definition of a Boolean algebra is satisfied.

data/lecture/math/discrete-math/power-set-basics.lecture.n.md

4De Morgan's lawsド・モルガンの法則

De Morgan's lawsド・モルガンの法則 say that negation interchanges “and” and “or.”

In logic,

\neg (P \land Q) \Leftrightarrow (\neg P) \lor (\neg Q)

\neg (P \lor Q) \Leftrightarrow (\neg P) \land (\neg Q)

and for sets,

U ∖ (A \cap B) = (U ∖ A) \cup (U ∖ B)

U ∖ (A \cup B) = (U ∖ A) \cap (U ∖ B) .

5What is being abstracted

Boolean algebraブール代数だいすう temporarily ignores whether the objects are propositions or sets, and focuses only on the laws satisfied by the operations. The preserved structure concerns joins結むすび, meets交まじわり, complements補元ほげん, greatest elements, and least elements.

This abstraction lets logical circuits, families of sets, conditional branches, and search conditions be handled by the same formal rules.

The point is that even after replacing concrete propositions命題めいだい or sets集合しゅうごう, calculations use the same laws for joins結むすび, meets交まじわり, and complements補元ほげん. We are looking at the structure preserved by the operations, not at the objects themselves.

6Proof supplement: uniqueness of complements補元ほげん

In a Boolean algebraブール代数だいすう, the complement補元ほげん of $x$ is unique. Suppose $y$ and $z$ are both complements of $x$ , meaning

x \land y = 0, x \lor y = 1, x \land z = 0, x \lor z = 1.

Then

y = y \land 1 = y \land (x \lor z) = (y \land x) \lor (y \land z) = 0 \lor (y \land z) = y \land z [PARSE ERROR: Undefined("Command(\"le\")")] z .

The same argument gives $z [PARSE ERROR: Undefined("Command(\"le\")")] y$ , so antisymmetry反対称性はんたいしょうせい implies $y = z$ .

7Proof supplement: De Morgan's lawsド・モルガンの法則

Using uniqueness of complements補元ほげん, De Morgan's lawsド・モルガンの法則 can be proved cleanly. For example, it is enough to show that $x^{'} \lor y^{'}$ is a complement of $x \land y$ .

(x \land y) \land (x^{'} \lor y^{'}) = ((x \land y) \land x^{'}) \lor ((x \land y) \land y^{'}) = 0,

(x \land y) \lor (x^{'} \lor y^{'}) = (x \lor x^{'} \lor y^{'}) \land (y \lor x^{'} \lor y^{'}) = 1.

Therefore uniqueness of complements gives

(x \land y)^{'} = x^{'} \lor y^{'} .

The same method gives $(x \lor y)^{'} = x^{'} \land y^{'}$ .

8Exercise link and summary

data/exercise/math/discrete-math/order-isomorphisms-and-boolean-algebras.exercise.n.md

Boolean algebraブール代数だいすう is a structure connecting logic論理ろんり and set operations集合演算しゅうごうえんざん. A power set冪集合べきしゅうごう is a standard example of a Boolean algebra, and De Morgan's lawsド・モルガンの法則 are central calculation laws in it.