Lompat ke isi

Aljabar Boolean (struktur)

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas

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.[1]

Kekisi Boolean pada himpunan bagian

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 diantara 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.

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:[2]

a ∨ (bc) = (ab) ∨ c a ∧ (bc) = (ab) ∧ c asosiatif
ab = ba ab = ba komutatifitas
a ∨ (ab) = a a ∧ (ab) = a serapan
a ∨ 0 = a a ∧ 1 = a identitas
a ∨ (bc) = (ab) ∧ (ac)   a ∧ (bc) = (ab) ∨ (ac)   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).[butuh rujukan]

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

a = ba     jika dan hanya jika     ab = b.

Relasi ≤ yang didefinisikan oleh ab jika kondisi ekuivalen ini berlaku, adalah urutan parsial dengan elemen terkecil 0 dan elemen terbesar 1. Pertemuan ab dan sambungan ab 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.[3]

  • 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;[catatan 1] disini 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:
    • (ab) ∧ (¬ac) ∧ (bc) ≡ (ab) ∧ (¬ac)
    • (ab) ∨ (¬ac) ∨ (bc) ≡ (ab) ∨ (¬ac)
  • 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:
0 a b 1
0 0 0 0 0
a 0 a 0 a
b 0 0 b b
1 0 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.
Diagram Hasse dari aljabar Boolean dari pembagi 30.
  • Untuk sembarang bilangan asli n, himpunan semua pembagian positif dari n, mendefinisikan ab 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 = { eR : e2 = e, ex = xe, ∀xR }
    maka himpunan A sebagai aljabar Boolean dengan operasi ef := e + f - ef dan ef := ef.

Homomorfisme dan isomorfisme

[sunting | sunting sumber]

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

f(ab) = f(a) ∨ f(b),
f(ab) = 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 : AB dengan homomorfisme invers, yaitu homomorfisme g : BA sedemikian rupa sehingga komposisi gf: AA adalah fungsi identitas pada A, dan komposisi fg: BB adalah fungsi identitas pada B. Homomorfisme aljabar Boolean adalah isomorfisme jika dan hanya jika bijektif.

Gelanggang Boolean

[sunting | sunting sumber]

Setiap aljabar Boolean (A, ∧, ∨) diberikan gelanggang (A, +, ·) dengan mendefinisikan a + b := (a ∧ ¬b) ∨ (b ∧ ¬a) = (ab) ∧ ¬(ab) (operasi ini disebut perbedaan simetris dalam kasus himpunan dan XOR dalam kasus logika) dan a · b := ab). 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 xy := x + y + (x · y) dan xy := x · y.[4][5] Karena kedua konstruksi ini adalah invers, apabila setiap gelanggang Boolean sebagai dari aljabar Boolean, dan sebaliknya. Selanjutnya, peta f : AB adalah homomorfisme aljabar Boolean jika dan hanya jika itu adalah homomorfisme gelanggang Boolean. Kategori gelanggang Boolean dan aljabar Boolean adalah ekuivalen.[6]

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

[sunting | sunting sumber]

Sebuah ideal dari aljabar Boolean A adalah himpunan bagian I sehingga untuk semua x, y di I maka memiliki xy di I dan untuk semua a di A maka memiliki ax di I. Gagasan ideal ini bertepatan dengan gagasan ranah gelanggang dalam gelanggang Boolean A. Sebuah ideal I dari A disebut juga prima jika IA dan jika ab in I selalu menyiratkan a di A atau b di A. Selanjutnya, untuk setiap aA memiliki a itu ∧ -a = 0 ∈ I dan maka aI atau -aI untuk setiap aA, 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 aI dan -aI, 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 xy di p dan untuk semua a di A kami memiliki ax 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.

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

[sunting | sunting sumber]

Aksiomatisasi pertama kekisi/aljabar Boolean secara umum diberikan oleh filsuf dan matematikawan Inggris Alfred North Whitehead pada tahun 1898.[7][8] 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).[9] Ia juga membuktikan bahwa aksioma-aksioma ini independen satu sama lain.[10] Pada tahun 1933, Huntington menetapkan aksiomatisasi elegan berikut untuk aljabar Boolean.[11] Ini hanya membutuhkan satu operasi biner + dan simbol fungsional uner n, untuk dibaca sebagai 'kelengkapan', yang memenuhi hukum berikut:

  1. Komutatif: x + y = y + x.
  2. Asosiatif: (x + y) + z = x + (y + z).
  3. 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

[sunting | sunting sumber]

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 ab, 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

[sunting | sunting sumber]
  1. ^ Sebenarnya, insinyur listrik cenderung menggunakan status tambahan untuk mewakili kondisi sirkuit lain seperti impedansi tinggi—lihat IEEE 1164 atau IEEE 1364.

Referensi

[sunting | sunting sumber]
  1. ^ Givant & Halmos 2009, hlm. 20.
  2. ^ Davey & Priestley 1990, hlm. 109, 131, 144.
  3. ^ Goodstein 2012, hlm. 21ff.
  4. ^ Stone 1936.
  5. ^ Hsiang 1985, hlm. 260.
  6. ^ Cohn 2003, hlm. 81.
  7. ^ Padmanabhan & Rudeanu 2008, hlm. 73.
  8. ^ Whitehead 1898, hlm. 37.
  9. ^ Huntington 1904, hlm. 292-293.
  10. ^ Huntington 1904, hlm. 296.
  11. ^ Huntington 1933a.

Referensi umum

[sunting | sunting sumber]

Templat:Insufficient inline citations

  • Brown, Stephen; Vranesic, Zvonko (2002), Fundamentals of Digital Logic with VHDL Design (edisi ke-2nd), McGraw–Hill, ISBN 978-0-07-249938-4 . See Section 2.5.
  • Boudet, A.; Jouannaud, J.P.; Schmidt-Schauß, M. (1989). "Unification in Boolean Rings and Abelian Groups". Journal of Symbolic Computation. 8 (5): 449–477. doi:10.1016/s0747-7171(89)80054-9. 
  • Cori, Rene; Lascar, Daniel (2000), Mathematical Logic: A Course with Exercises, Oxford University Press, ISBN 978-0-19-850048-3 . See Chapter 2.
  • Dahn, B. I. (1998), "Robbins Algebras are Boolean: A Revision of McCune's Computer-Generated Solution of the Robbins Problem", Journal of Algebra, 208 (2): 526–532, doi:10.1006/jabr.1998.7467 .

Pranala luar

[sunting | sunting sumber]