Aljabar Boolean (struktur): Perbedaan antara revisi

Revisi terkini sejak 25 Agustus 2026 22.57

Dalam aljabar abstrak, sebuah aljabar Boolean atau kekisi Boolean adalah kelengkapan kekisi distributif. Jenis struktur aljabar ini menangkap sifat penting dari operasi himpunan dan operasi logika. Aljabar Boolean dapat dilihat sebagai generalisasi dari aljabar himpunan daya atau himpunan medan, atau elemennya dapat dilihat sebagai nilai kebenaran yang digeneralisasi. Ini juga merupakan kasus khusus dari aljabar De Morgan dan aljabar Kleene (dengan involusi).

Setiap aljabar Boolean tingkatan ke gelanggang Boolean, dan sebaliknya, dengan perkalian gelanggang yang sesuai dengan konjungsi atau pertemuan ∧, dan penambahan gelanggang ke disjungsi eksklusif atau perbedaan simetris (bukan disjungsi ∨). Namun, teori gelanggang Boolean memiliki asimetri yang melekat antara dua operator, sedangkan aksioma dan teorema aljabar Boolean menyatakan simetri teori yang dijelaskan oleh prinsip dualitas.

Sejarah

Istilah "aljabar Boolean" sebagai tanda jasa oleh George Boole (1815–1864), seorang matematikawan Inggris yang belajar sendiri. Ia memperkenalkan sistem aljabar awalnya dalam pamflet kecil dengan buku The Mathematical Analysis of Logic, diterbitkan pada tahun 1847 sebagai tanggapan atas kontroversi publik yang sedang berlangsung di antara Augustus De Morgan dan William Hamilton, dan kemudian sebagai buku yang lebih substansial, buku The Laws of Thought, diterbitkan pada tahun 1854. Rumus Boole berbeda dari yang dijelaskan di atas dalam beberapa hal penting. Misalnya, konjungsi dan disjungsi dalam Boole bukanlah operasi sepasang ganda. Aljabar Boolean muncul pada tahun 1860-an, dalam makalah yang ditulis oleh William Jevons dan Charles Sanders Peirce. Presentasi sistematis pertama dari aljabar Boolean dan kekisi distributif adalah berkat "Vorlesungen" 1890 dari Ernst Schröder. Perlakuan ekstensif pertama kali dari aljabar Boolean dalam bahasa Inggris adalah A. N. Whitehead 1898 Aljabar Universal. Aljabar Boolean sebagai struktur aljabar aksiomatik dalam pengertian aksiomatik modern dimulai dengan makalah tahun 1904 oleh Edward V. Huntington. Aljabar Boolean muncul sebagai matematika dengan karya Marshall Stone pada 1930-an, dan dengan Garrett Birkhoff 1940 yang memperkenalkan Teori Kekisi. Pada tahun 1960-an, Paul Cohen, Dana Scott, dan lainnya menemukan hasil baru yang mendalam dalam logika matematika dan teori himpunan aksiomatik menggunakan cabang aljabar Boolean, yaitu paksaan dan model kenilaian Boolean.

Definisi

Sebuah aljabar Boolean adalah enam-tupel yang terdiri dari himpunan A, dilengkapi dengan dua operasi biner ∧ (disebut "pertemuan" atau "dan"), ∨ (disebut "sambungan" atau "atau"), sebuah operasi uner ¬ (disebut "kelengkapan" atau "bukan") dan dua elemen 0 dan 1 di A (disebut elemen "bawah" dan "atas", atau "terkecil" dan "terbesar", yang dilambangkan dengan simbol ⊥ dan ⊤), sehingga untuk semua elemen a, b dan c dari A, aksioma berikut ini berlaku:

a ∨ (b ∨ c) = (a ∨ b) ∨ c	a ∧ (b ∧ c) = (a ∧ b) ∧ c	asosiatif
a ∨ b = b ∨ a	a ∧ b = b ∧ a	komutatifitas
a ∨ (a ∧ b) = a	a ∧ (a ∨ b) = a	serapan
a ∨ 0 = a	a ∧ 1 = a	identitas
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)	a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)	distribusitif
a ∨ ¬a = 1	a ∧ ¬a = 0	kelengkapan

Perhatikan, pada hukum serapan dan bahkan hukum asosiatif dapat dikeluarkan dari himpunan aksioma karena mereka dapat diturunkan dari aksioma lainnya (lihat Sifat pembuktian).

Aljabar Boolean dengan hanya satu elemen disebut aljabar Boolean trivial atau aljabar Boolean degenerasi (catatan: dalam karya-karya yang lebih tua, beberapa penulis mengharuskan 0 dan 1 menjadi elemen "berbeda" untuk mengecualikan kasus ini).

Ini mengikuti dari tiga pasang aksioma terakhir di atas (identitas, distributif dan komplemen), atau dari aksioma penyerapan, bahwa

a = b ∧ a jika dan hanya jika a ∨ b = b.

Relasi ≤ yang didefinisikan oleh a ≤ b jika kondisi ekuivalen ini berlaku, adalah urutan parsial dengan elemen terkecil 0 dan elemen terbesar 1. Pertemuan a ∧ b dan sambungan a ∨ b dari dua elemen bertepatan dengan infimum dan supremum yang sehubungan dengan ≤.

Empat pasang aksioma pertama merupakan definisi dari kekisi terbatas.

Dari lima pasang aksioma pertama, setiap komplemen adalah unik.

Himpunan aksioma adalah hasil ganda dalam arti bahwa jika seseorang bertukar ∨ dengan ∧ dan 0 dengan 1 dalam aksioma yang hasilnya adalah aksioma. Oleh karena itu, dengan menerapkan operasi ini ke aljabar Boolean (atau kekisi Boolean), satu memperoleh aljabar Boolean lain dengan elemen yang sama; yang disebut juga sebagai dual.

Contoh

Aljabar Boolean non-trivial sederhana, dan aljabar Boolean dua elemen hanya memiliki dua elemen 0 dan 1, dan didefinisikan oleh aturan:

∧	0	1
0	0	0
1	0	1

∨	0	1
0	0	1
1	1	1

a	0	1
¬a	1	0

Ini memiliki aplikasi dalam logika, menafsirkan 0 sebagai salah, 1 sebagai benar, ∧ sebagai dan, ∨ sebagai atau, dan ¬ sebagai bukan. Ekspresi yang melibatkan variabel dan operasi Boolean mewakili bentuk pernyataan, dan dua ekspresi tersebut dapat ditunjukkan sama dengan menggunakan aksioma di atas jika dan hanya jika bentuk pernyataan yang sesuai adalah ekuivalen secara logi5.

Aljabar Boolean dua elemen juga digunakan untuk desain sirkuit di teknik elektro; di sini 0 dan 1 mewakili dua status berbeda dari satu bit dalam sirkuit digital, biasanya tegangan tinggi dan rendah. Sirkuit dijelaskan oleh ekspresi yang mengandung variabel, dan dua ekspresi tersebut sama untuk semua nilai variabel jika dan hanya jika sirkuit yang sesuai memiliki perilaku input-output yang sama. Selanjutnya, setiap perilaku input-output yang mungkin dimodelkan dengan ekspresi Boolean.

Aljabar Boolean dua elemen juga penting dalam teori umum aljabar Boolean, karena persamaan yang melibatkan beberapa variabel umumnya benar dalam semua aljabar Boolean jika dan hanya jika benar dalam aljabar Boolean dua elemen (apabila memeriksa dengan algoritma paksa brute trivial untuk sejumlah kecil variabel). Ini misalnya dapat digunakan untuk menunjukkan bahwa hukum berikut (Teorema konsensus) umumnya berlaku di semua aljabar Boolean:
- (a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) ≡ (a ∨ b) ∧ (¬a ∨ c)
- (a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) ≡ (a ∧ b) ∨ (¬a ∧ c)

Himpunan daya (himpunan dari semua himpunan bagian) dari himpunan tak kosong S dalam bentuk aljabar Boolean, sebuah aljabar himpunan, dengan dua operasi ∨ := ∪ (gabungan) and ∧ := ∩ (persimpangan/irisan). Elemen terkecil 0 adalah himpunan kosong dan elemen terbesar 1 adalah himpunan S sendiri.

Setelah aljabar Boolean dua elemen, aljabar Boolean sederhana adalah yang didefinisikan oleh himpunan daya dari dua atom:

∧	a	b	1
0	0	0	0
a	a	0	a
b	0	b	b
1	a	b	1

∨	0	a	b	1
0	0	a	b	1
a	a	a	1	1
b	b	1	b	1
1	1	1	1	1

x	0	a	b	1
¬x	1	b	a	0

Himpunan (dari semua himpunan bagian) dari S hingga atau kofinit adalah aljabar Boolean, sebuah aljabar himpunan.
Dimulai dengan kalkulus proposisional dengan simbol kalimat κ, bentuk aljabar Lindenbaum (yaitu, himpunan kalimat dalam modulo kalkulus proposisional ekuivalen logika). Konstruksi ini menghasilkan sebagai aljabar Boolean. Sebenarnya aljabar Boolean bebas adalah generator. Penugasan kebenaran dalam kalkulus proposisi adalah homomorfisme aljabar Boolean dari aljabar ini ke aljabar Boolean dua elemen.
Diberikan setiap urutan linearitas pada himpunan L dengan elemen terkecil, aljabar interval adalah aljabar terkecil dari himpunan bagian L yang berisi semua interval setengah terbuka [a, b) sehingga a apabila L dan b adalah L atau sama dengan ∞. Aljabar interval berguna dalam mempelajari aljabar Lindenbaum–Tarski; setiap aljabar Boolean yang dapat dihitung adalah isomorfik terhadap aljabar interval.

Untuk sembarang bilangan asli n, himpunan semua pembagian positif dari n, mendefinisikan a≤b jika a membagi b, dalam bentuk kekisi distributif. Kekisi ini adalah aljabar Boolean jika dan hanya jika n adalah persegi bebas. Elemen bawah dan elemen atas aljabar Boolean ini masing-masing adalah bilangan asli 1 dan n. Kekomplemen dari a diberikan oleh n/a. Pertemuan dan sambungan dari a dan b diberikan oleh faktor persekutuan terbesar (fpb) dan kelipatan persekutuan terkecil (kpt) dari a dan b. Penambahan gelanggang a+b diberikan oleh fpb(a,b)/kpt(a,b). Citra menunjukkan contoh untuk n = 30. Sebagai contoh tandingan, dengan mempertimbangkan non-persegi-bebas n=60, faktor persekutuan terbesar dari 30 dan komplemennya 2 adalah 2, sementara itu harus menjadi elemen terbawah 1.
Contoh lain dari aljabar Boolean muncul dari ruang topologi: jika X adalah ruang topologi, maka kumpulan semua himpunan bagian X maupun terbuka dan tertutup dalam bentuk aljabar Boolean dengan operasi ∨ := ∪ (gabungan) dan ∧ := ∩ (persimpangan/irisan).
Jika R adalah gelanggang sebarang dan kami mendefinisikan himpunan idempoten sentral dengan
A = { e ∈ R : e² = e, ex = xe, ∀x ∈ R }
maka himpunan A sebagai aljabar Boolean dengan operasi e ∨ f := e + f - ef dan e ∧ f := ef.

Homomorfisme dan isomorfisme

Sebuah homomorfisme antara dua aljabar Boolean A dan B adalah fungsi f : A → B sedemikian rupa sehingga untuk semua a, b di A:

f(a ∨ b) = f(a) ∨ f(b),

f(a ∧ b) = f(a) ∧ f(b),

f(0) = 0,

f(1) = 1.

Maka mengikuti bahwa f (¬a) = ¬f(a) untuk semua a di A. kelas dari semua aljabar Boolean, bersama dengan gagasan morfisme ini, dalam bentuk subkategori penuh dari kekisi kategori.

Sebuah isomorfisme antara dua aljabar Boolean A dan B adalah homomorfisme f : A → B dengan homomorfisme invers, yaitu homomorfisme g : B → A sedemikian rupa sehingga komposisi g ∘ f: A → A adalah fungsi identitas pada A, dan komposisi f ∘ g: B → B adalah fungsi identitas pada B. Homomorfisme aljabar Boolean adalah isomorfisme jika dan hanya jika bijektif.

Gelanggang Boolean

Setiap aljabar Boolean (A, ∧, ∨) diberikan gelanggang (A, +, ·) dengan mendefinisikan a + b := (a ∧ ¬b) ∨ (b ∧ ¬a) = (a ∨ b) ∧ ¬(a ∧ b) (operasi ini disebut perbedaan simetris dalam kasus himpunan dan XOR dalam kasus logika) dan a · b := a ∧ b). Elemen nol dari gelanggang ini bertepatan dengan 0 dari aljabar Boolean; elemen identitas perkalian dari gelanggang adalah 1 dari aljabar Boolean. Gelanggang ini memiliki sifat bahwa a · a = a untuk semua a di A; gelanggang dengan sifat ini disebut gelanggang Boolean.

Sebaliknya, jika diberikan gelanggang Boolean A, kita dapat mengubahnya menjadi aljabar Boolean dengan mendefinisikan x ∨ y := x + y + (x · y) dan x ∧ y := x · y. Karena kedua konstruksi ini adalah invers, apabila setiap gelanggang Boolean sebagai dari aljabar Boolean, dan sebaliknya. Selanjutnya, peta f : A → B adalah homomorfisme aljabar Boolean jika dan hanya jika itu adalah homomorfisme gelanggang Boolean. Kategori gelanggang Boolean dan aljabar Boolean adalah ekuivalen.

Hsiang (1985) memberikan algoritma berbasis aturan ke pemeriksaan apakah dua ekspresi sebarang menunjukkan nilai yang sama di setiap gelanggang Boolean.

Secara umum, Boudet, Jouannaud, dan Schmidt-Schauß (1989) diberikan algoritma untuk menyelesaikan persamaan antara ekspresi gelanggang Boolean berubah. Menggunakan kesamaan gelanggang Boolean dan aljabar Boolean, kedua algoritma memiliki aplikasi dalam pembuktian teorema otomatis.

Ideal dan filter

Sebuah ideal dari aljabar Boolean A adalah himpunan bagian I sehingga untuk semua x, y di I maka memiliki x ∨ y di I dan untuk semua a di A maka memiliki a ∧ x di I. Gagasan ideal ini bertepatan dengan gagasan ranah gelanggang dalam gelanggang Boolean A. Sebuah ideal I dari A disebut juga prima jika I ≠ A dan jika a ∧ b in I selalu menyiratkan a di A atau b di A. Selanjutnya, untuk setiap a ∈ A memiliki a itu ∧ -a = 0 ∈ I dan maka a ∈ I atau -a ∈ I untuk setiap a ∈ A, jika A adalah bilangan prima. Sebuah I ideal dari A disebut juga maksimal jika I'' ≠ A dan jika satu-satunya ideal I adalah A. Untuk "I" yang ideal, jika a ∉ I dan -a ∉ I, maka I ∪ {a} or I ∪ {-a} yang terkandung dalam ideal lain J. Oleh karena itu, bahwa "I" tak maksimal dan oleh karena itu gagasan tentang ideal prima dan ideal maksimal setara dalam aljabar Boolean. Selain itu, gagasan ini bertepatan dengan teori gelanggang ranah prima dan ranah maksimal dalam gelanggang Boolean A.

Kesamaan dari ideal adalah filter. Sebuah filter dari aljabar Boolean A adalah himpunan bagian p sehingga untuk semua x, y di p memiliki x ∧ y di p dan untuk semua a di A kami memiliki a ∨ x di p. Ganda dari maksimal (atau prima) ideal dalam aljabar Boolean adalah ultrafilter. Ultrafilter sebagai alternatif dapat digambarkan sebagai morfisme nilai-2 dari A ke aljabar Boolean dua elemen. Pernyataan setiap filter dalam aljabar Boolean apabila diperluas ke ultrafilter disebut teorema ultrafilter dan tidak dapat dibuktikan dalam ZF, jika ZF adalah konsisten. Teorema ultrafilter memiliki banyak rumus ekuivalen: setiap aljabar Boolean memiliki ultrafilter, setiap ranah dalam aljabar Boolean apabila diperluas ke ranah prima, dll.

Wakilan

Dapat ditunjukkan bahwa setiap aljabar Boolean hingga adalah isomorfik terhadap aljabar Boolean dari semua himpunan bagian dari himpunan hingga. Oleh karena itu, jumlah elemen dari setiap aljabar Boolean hingga adalah pangkat dua.

Stone's merayakan teorema wakilan untuk aljabar Boolean menyatakan bahwa setiap aljabar Boolean A isomorfik dengan aljabar Boolean dari semua himpunan tertutup di beberapa (kompak urutan terputus Hausdorff.

Aksiomatik

Sifat pembuktian

UId₁		Jika x ∨ o = x untuk semua x, maka o = 0
Bukti:		If x ∨ o = x, maka
		0
	=	0 ∨ o	dengan asumsi
	=	o ∨ 0	dengan Cmm₁
	=	o	dengan Idn₁

UId₂ [dual] Jika x ∧ i = x untuk semua x, maka i = 1

Idm₁		x ∨ x = x
Bukti:		x ∨ x
	=	(x ∨ x) ∧ 1	dengan Idn₂
	=	(x ∨ x) ∧ (x ∨ ¬x)	dengan Cpl₁
	=	x ∨ (x ∧ ¬x)	dengan Dst₁
	=	x ∨ 0	dengan Cpl₂
	=	x	dengan Idn₁

Idm₂ [dual] x ∧ x = x

Bnd₁		x ∨ 1 = 1
Bukti:		x ∨ 1
	=	(x ∨ 1) ∧ 1	dengan Idn₂
	=	1 ∧ (x ∨ 1)	dengan Cmm₂
	=	(x ∨ ¬x) ∧ (x ∨ 1)	dengan Cpl₁
	=	x ∨ (¬x ∧ 1)	dengan Dst₁
	=	x ∨ ¬x	dengan Idn₂
	=	1	dengan Cpl₁

Bnd₂ [dual] x ∧ 0 = 0

Abs₁		x ∨ (x ∧ y) = x
Bukti:		x ∨ (x ∧ y)
	=	(x ∧ 1) ∨ (x ∧ y)	dengan Idn₂
	=	x ∧ (1 ∨ y)	dengan Dst₂
	=	x ∧ (y ∨ 1)	dengan Cmm₁
	=	x ∧ 1	dengan Bnd₁
	=	x	dengan Idn₂

Abs₂ [dual] x ∧ (x ∨ y) = x

UNg		Jika x ∨ x_n = 1 dan x ∧ x_n = 0, maka x_n = ¬x
Bukti:		Jika x ∨ x_n = 1 dan x ∧ x_n = 0, maka
		x_n
	=	x_n ∧ 1	dengan Idn₂
	=	x_n ∧ (x ∨ ¬x)	dengan Cpl₁
	=	(x_n ∧ x) ∨ (x_n ∧ ¬x)	dengan Dst₂
	=	(x ∧ x_n) ∨ (¬x ∧ x_n)	dengan Cmm₂
	=	0 ∨ (¬x ∧ x_n)	dengan asumsi
	=	(x ∧ ¬x) ∨ (¬x ∧ x_n)	dengan Cpl₂
	=	(¬x ∧ x) ∨ (¬x ∧ x_n)	dengan Cmm₂
	=	¬x ∧ (x ∨ x_n)	dengan Dst₂
	=	¬x ∧ 1	dengan asumsi
	=	¬x	dengan Idn₂

DNg		¬¬x = x
Bukti:		¬x ∨ x = x ∨ ¬x = 1	dengan Cmm₁, Cpl₁
	and	¬x ∧ x = x ∧ ¬x = 0	dengan Cmm₂, Cpl₂
	karenanya	x = ¬¬x	dengan UNg

A₁		x ∨ (¬x ∨ y) = 1
Bukti:		x ∨ (¬x ∨ y)
	=	(x ∨ (¬x ∨ y)) ∧ 1	dengan Idn₂
	=	1 ∧ (x ∨ (¬x ∨ y))	dengan Cmm₂
	=	(x ∨ ¬x) ∧ (x ∨ (¬x ∨ y))	dengan Cpl₁
	=	x ∨ (¬x ∧ (¬x ∨ y))	dengan Dst₁
	=	x ∨ ¬x	dengan Abs₂
	=	1	dengan Cpl₁

A₂ [dual] x ∧ (¬x ∧ y) = 0

B₁		(x ∨ y) ∨ (¬x ∧ ¬y) = 1
Bukti:		(x ∨ y) ∨ (¬x ∧ ¬y)
	=	((x ∨ y) ∨ ¬x) ∧ ((x ∨ y) ∨ ¬y)	dengan Dst₁
	=	(¬x ∨ (x ∨ y)) ∧ (¬y ∨ (y ∨ x))	dengan Cmm₁
	=	(¬x ∨ (¬¬x ∨ y)) ∧ (¬y ∨ (¬¬y ∨ x))	dengan DNg
	=	1 ∧ 1	dengan A₁
	=	1	dengan Idn₂

B₂ [dual] (x ∧ y) ∧ (¬x ∨ ¬y) = 0

C₁		(x ∨ y) ∧ (¬x ∧ ¬y) = 0
Bukti:		(x ∨ y) ∧ (¬x ∧ ¬y)
	=	(¬x ∧ ¬y) ∧ (x ∨ y)	dengan Cmm₂
	=	((¬x ∧ ¬y) ∧ x) ∨ ((¬x ∧ ¬y) ∧ y)	dengan Dst₂
	=	(x ∧ (¬x ∧ ¬y)) ∨ (y ∧ (¬y ∧ ¬x))	dengan Cmm₂
	=	0 ∨ 0	dengan A₂
	=	0	dengan Idn₁

C₂ [dual] (x ∧ y) ∨ (¬x ∨ ¬y) = 1

DMg₁		¬(x ∨ y) = ¬x ∧ ¬y
Bukti:		dengan B₁, C₁, dan UNg

DMg₂ [dual] ¬(x ∧ y) = ¬x ∨ ¬y

D₁		(x∨(y∨z)) ∨ ¬x = 1
Bukti:		(x ∨ (y ∨ z)) ∨ ¬x
	=	¬x ∨ (x ∨ (y ∨ z))	dengan Cmm₁
	=	¬x ∨ (¬¬x ∨ (y ∨ z))	dengan DNg
	=	1	dengan A₁

D₂ [dual] (x∧(y∧z)) ∧ ¬x = 0

E₁		y ∧ (x∨(y∨z)) = y
Bukti:		y ∧ (x ∨ (y ∨ z))
	=	(y ∧ x) ∨ (y ∧ (y ∨ z))	dengan Dst₂
	=	(y ∧ x) ∨ y	dengan Abs₂
	=	y ∨ (y ∧ x)	dengan Cmm₁
	=	y	dengan Abs₁

E₂ [dual] y ∨ (x∧(y∧z)) = y

F₁		(x∨(y∨z)) ∨ ¬y = 1
Bukti:		(x ∨ (y ∨ z)) ∨ ¬y
	=	¬y ∨ (x ∨ (y ∨ z))	dengan Cmm₁
	=	(¬y ∨ (x ∨ (y ∨ z))) ∧ 1	dengan Idn₂
	=	1 ∧ (¬y ∨ (x ∨ (y ∨ z)))	dengan Cmm₂
	=	(y ∨ ¬y) ∧ (¬y ∨ (x ∨ (y ∨ z)))	dengan Cpl₁
	=	(¬y ∨ y) ∧ (¬y ∨ (x ∨ (y ∨ z)))	dengan Cmm₁
	=	¬y ∨ (y ∧ (x ∨ (y ∨ z)))	dengan Dst₁
	=	¬y ∨ y	dengan E₁
	=	y ∨ ¬y	dengan Cmm₁
	=	1	dengan Cpl₁

F₂ [dual] (x∧(y∧z)) ∧ ¬y = 0

G₁		(x∨(y∨z)) ∨ ¬z = 1
Bukti:		(x ∨ (y ∨ z)) ∨ ¬z
	=	(x ∨ (z ∨ y)) ∨ ¬z	dengan Cmm₁
	=	1	dengan F₁

G₂ [dual] (x∧(y∧z)) ∧ ¬z = 0

H₁		¬((x∨y)∨z) ∧ x = 0
Bukti:		¬((x ∨ y) ∨ z) ∧ x
	=	(¬(x ∨ y) ∧ ¬z) ∧ x	dengan DMg₁
	=	((¬x ∧ ¬y) ∧ ¬z) ∧ x	dengan DMg₁
	=	x ∧ ((¬x ∧ ¬y) ∧ ¬z)	dengan Cmm₂
	=	(x ∧ ((¬x ∧ ¬y) ∧ ¬z)) ∨ 0	dengan Idn₁
	=	0 ∨ (x ∧ ((¬x ∧ ¬y) ∧ ¬z))	dengan Cmm₁
	=	(x ∧ ¬x) ∨ (x ∧ ((¬x ∧ ¬y) ∧ ¬z))	dengan Cpl₁
	=	x ∧ (¬x ∨ ((¬x ∧ ¬y) ∧ ¬z))	dengan Dst₂
	=	x ∧ (¬x ∨ (¬z ∧ (¬x ∧ ¬y)))	dengan Cmm₂
	=	x ∧ ¬x	dengan E₂
	=	0	dengan Cpl₂

H₂ [dual] ¬((x∧y)∧z) ∨ x = 1

I₁		¬((x∨y)∨z) ∧ y = 0
Bukti:		¬((x ∨ y) ∨ z) ∧ y
	=	¬((y ∨ x) ∨ z) ∧ y	dengan Cmm₁
	=	0	dengan H₁

I₂ [dual] ¬((x∧y)∧z) ∨ y = 1

J₁		¬((x∨y)∨z) ∧ z = 0
Bukti:		¬((x ∨ y) ∨ z) ∧ z
	=	(¬(x ∨ y) ∧ ¬z) ∧ z	dengan DMg₁
	=	z ∧ (¬(x ∨ y) ∧ ¬z)	dengan Cmm₂
	=	z ∧ ( ¬z ∧ ¬(x ∨ y))	dengan Cmm₂
	=	0	dengan A₂

J₂ [dual] ¬((x∧y)∧z) ∨ z = 1

K₁		(x ∨ (y ∨ z)) ∨ ¬((x ∨ y) ∨ z) = 1
Bukti:		(x∨(y∨z)) ∨ ¬((x ∨ y) ∨ z)
	=	(x∨(y∨z)) ∨ (¬(x ∨ y) ∧ ¬z)	dengan DMg₁
	=	(x∨(y∨z)) ∨ ((¬x ∧ ¬y) ∧ ¬z)	dengan DMg₁
	=	((x∨(y∨z)) ∨ (¬x ∧ ¬y)) ∧ ((x∨(y∨z)) ∨ ¬z)	dengan Dst₁
	=	(((x∨(y∨z)) ∨ ¬x) ∧ ((x∨(y∨z)) ∨ ¬y)) ∧ ((x∨(y∨z)) ∨ ¬z)	dengan Dst₁
	=	(1 ∧ 1) ∧ 1	dengan D₁,F₁,G₁
	=	1	dengan Idn₂

K₂ [dual] (x ∧ (y ∧ z)) ∧ ¬((x ∧ y) ∧ z) = 0

L₁		(x ∨ (y ∨ z)) ∧ ¬((x ∨ y) ∨ z) = 0
Bukti:		(x ∨ (y ∨ z)) ∧ ¬((x ∨ y) ∨ z)
	=	¬((x∨y)∨z) ∧ (x ∨ (y ∨ z))	dengan Cmm₂
	=	(¬((x∨y)∨z) ∧ x) ∨ (¬((x∨y)∨z) ∧ (y ∨ z))	dengan Dst₂
	=	(¬((x∨y)∨z) ∧ x) ∨ ((¬((x∨y)∨z) ∧ y) ∨ (¬((x∨y)∨z) ∧ z))	dengan Dst₂
	=	0 ∨ (0 ∨ 0)	dengan H₁,I₁,J₁
	=	0	dengan Idn₁

L₂ [dual] (x ∧ (y ∧ z)) ∨ ¬((x ∧ y) ∧ z) = 1

Ass₁		x ∨ (y ∨ z) = (x ∨ y) ∨ z
Bukti:		dengan K₁, L₁, UNg, DNg

Ass₂ [dual] x ∧ (y ∧ z) = (x ∧ y) ∧ z

Singkatan
UId	Unique Identity (Indentitas unik)
Idm	Idempotence (Idempotensi)
Bnd	Boundaries (Berbatas)
Abs	Absorption law
UNg	Unique Negation (Negasi Unik)
DNg	Denegation unique (Denegasi unik)
DMg	Hukum De Morgan
Ass	Asosiatif

Aksioma aljabar Boolean Huntington 1904

Idn₁

x ∨ 0 = x

Idn₂

x ∧ 1 = x

Cmm₁

x ∨ y = y ∨ x

Cmm₂

x ∧ y = y ∧ x

Dst₁

x ∨ (y∧z) = (x∨y) ∧ (x∨z)

Dst₂

x ∧ (y∨z) = (x∧y) ∨ (x∧z)

Cpl₁

x ∨ ¬x = 1

Cpl₂

x ∧ ¬x = 0

Singkatan
Idn	Identitas
Cmm	Commutativity (Komutatif)
Dst	Distribusi
Cpl	Complements (Kekomplemen)

Aksiomatisasi pertama kekisi/aljabar Boolean secara umum diberikan oleh filsuf dan matematikawan Inggris Alfred North Whitehead pada tahun 1898. Itu termasuk di atas aksioma dan tambahan x∨1=1 dan x∧0=0. Pada tahun 1904, matematikawan Amerika Edward V. Huntington (1874–1952) memberikan aksiomatisasi yang pelit berdasarkan ∧, ∨, ¬, bahkan membuktikan hukum asosiatif (lihat kotak). Ia juga membuktikan bahwa aksioma-aksioma ini independen satu sama lain. Pada tahun 1933, Huntington menetapkan aksiomatisasi elegan berikut untuk aljabar Boolean. Ini hanya membutuhkan satu operasi biner + dan simbol fungsional uner n, untuk dibaca sebagai 'kelengkapan', yang memenuhi hukum berikut:

Komutatif: x + y = y + x.
Asosiatif: (x + y) + z = x + (y + z).
PERSAMAAN Huntington: n(n(x) + y) + n(n(x) + n(y)) = x.

Herbert Robbins segera bertanya: Jika persamaan Huntington diganti dengan dualnya, yaitu:

4. Persamaan Robbins: n(n(x + y) + n(x + n(y))) = x,

apakah (1), (2), dan (4) dalam bentuk basis untuk aljabar Boolean? Menyebut (1), (2), dan (4) sebuah Aljabar Robbins, pertanyaannya kemudian menjadi: Apakah setiap aljabar Robbins merupakan aljabar Boolean? Pertanyaan ini (yang kemudian dikenal sebagai konjektur Robbins) tetap terbuka selama beberapa dekade, dan menjadi pertanyaan favorit Alfred Tarski dan murid-muridnya. Pada tahun 1996, William McCune di Laboratorium Nasional Argonne, berdasarkan pekerjaan sebelumnya oleh Larry Wos, Steve Winker, dan Bob Veroff, menjawab pertanyaan Robbins dengan tegas: Setiap aljabar Robbins adalah aljabar Boolean. Penting bagi bukti McCune adalah program penalaran otomatis EQP yang dia rancang. Untuk penyederhanaan bukti McCune, lihat Dahn (1998).

Pekerjaan lebih lanjut telah dilakukan untuk mengurangi jumlah aksioma; lihat Aksioma minimal untuk aljabar Boolean.

Generalisasi

Menghapus persyaratan keberadaan unit dari aksioma aljabar Boolean menghasilkan "aljabar Boolean umum". Secara formal, kekisi distributif B adalah kekisi Boolean umum, jika memiliki elemen terkecil 0 dan untuk setiap elemen a dan b di B sehingga a ≤ b, apabila terdapat elemen x sehingga a ∧ x = 0 dan a ∨ x = b. Mendefinisikan a ∖ b sebagai unik x sehingga (a ∧ b) ∨ x = a dan (a ∧ b) ∧ x = 0, maka katakan bahwa struktur (B,∧,∨,∖,0) adalah "aljabar Boolean umum", sedangkan (B,∨,0) adalah Boolean umum semikekisi. Kekisi Boolean umum adalah ranah dari kekisi Boolean.

Struktur yang memenuhi semua aksioma aljabar Boolean kecuali dua aksioma distributif disebut kekisi ortokomplemenkan. Ortokomplemenkan muncul secara asli dalam logika kuantum sebagai kekisi subruang tertutup untuk ruang Hilbert yang dipisahkan.

Lihat pula

Catatan

Pranala luar

Stanford Encyclopedia of Philosophy: "The Mathematics of Boolean Algebra," by J. Donald Monk.
McCune W., 1997. Robbins Algebras Are Boolean JAR 19(3), 263—276
"Boolean Algebra" by Eric W. Weisstein, Wolfram Demonstrations Project, 2007.
Burris, Stanley N.; Sankappanavar, H. P., 1981. A Course in Universal Algebra. Springer-Verlag. .

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 28531817 (2025-11-18T09:46:54Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

Maintenance script (bicara | kontrib)