Bu makale genel bir liste içerir Referanslar, ancak büyük ölçüde doğrulanmamış kalır çünkü yeterli karşılık gelmiyor satır içi alıntılar. Lütfen yardım edin geliştirmek bu makale tanıtım daha kesin alıntılar.(Temmuz 2013) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)
Her Boole cebri yol açmaktadır bir Boole halkası ve tam tersi, halka çarpımına karşılık gelir bağlaç veya buluşmak ∧ ve halka eklenmesi münhasır ayrılma veya simetrik fark (değil ayrılma ∨). Bununla birlikte, Boole halkaları teorisi iki operatör arasında doğal bir asimetriye sahipken, Boole cebirinin aksiyomları ve teoremleri, tarafından tanımlanan teorinin simetrisini ifade eder. dualite ilkesi.[1]
"Boole cebri" terimi, George Boole (1815–1864), kendi kendini yetiştirmiş bir İngiliz matematikçi. O tanıttı cebirsel sistem başlangıçta küçük bir broşürde, Mantığın Matematiksel Analiziarasında devam eden bir kamu tartışmasına cevaben 1847'de yayınlandı Augustus De Morgan ve William Hamilton ve daha sonra daha sağlam bir kitap olarak, Düşünce Kanunları, 1854'te yayınlanmıştır. Boole'nin formülasyonu, bazı önemli açılardan yukarıda tarif edilenden farklıdır. Örneğin, Boole'deki birleşme ve ayrılma, ikili bir işlem çifti değildi. Boole cebri, 1860'larda, William Jevons ve Charles Sanders Peirce. Boole cebirinin ilk sistematik sunumu ve dağıtım kafesleri 1890'a borçludur Vorlesungen nın-nin Ernst Schröder. Boole cebirinin İngilizce'deki ilk kapsamlı tedavisi A. N. Whitehead 1898 Evrensel Cebir. Modern aksiyomatik anlamda aksiyomatik bir cebirsel yapı olarak Boole cebri, 1904 tarihli bir makaleyle başlar. Edward V. Huntington. Boole cebri, ciddi matematik olarak yaşlandı. Marshall Stone 1930'larda ve Garrett Birkhoff 1940 Kafes Teorisi. 1960'larda, Paul Cohen, Dana Scott ve diğerleri şurada derin yeni sonuçlar buldu matematiksel mantık ve aksiyomatik küme teorisi Boole cebirinin dallarını kullanarak, yani zorlama ve Boole değerli modeller.
Tanım
Bir Boole cebri altıdırdemet oluşan AyarlamakBiriki ile donatılmış ikili işlemler ∧ ("buluşma" veya "ve" olarak adlandırılır), ∨ ("katıl" veya "veya" olarak adlandırılır), a tekli işlem ¬ ("tamamlayıcı" veya "değil" olarak adlandırılır) ve iki öğe 0 ve 1'de Bir ("alt" ve "üst" olarak adlandırılır veya "en az" ve "en büyük" öğe, sırasıyla ve ⊤ sembolleriyle de gösterilir), öyle ki tüm öğeler için a, b ve c nın-nin Bir, aşağıdaki aksiyomlar ambar:[2]
Bununla birlikte, soğurma yasasının ve hatta birliktelik yasasının, diğer aksiyomlardan türetilebilecekleri için aksiyomlar kümesinden çıkarılabileceğini unutmayın (bkz. Kanıtlanmış özellikler ).
Sadece bir elemente sahip bir Boole cebri, a önemsiz Boole cebri veya a dejenere Boole cebri. (Daha eski çalışmalarda, bazı yazarlar 0 ve 1'in farklı Bu durumu dışlamak için öğeler.)[kaynak belirtilmeli ]
Yukarıdaki son üç aksiyom çiftinden (özdeşlik, dağıtım ve tamamlayıcılar) veya soğurma aksiyomundan şu sonuç çıkar:
a = b ∧ a ancak ve ancak a ∨ b = b.
≤ ile tanımlanan ilişki a ≤ b bu eşdeğer koşullar geçerliyse, bir kısmi sipariş en az öğe 0 ve en büyük öğe 1 ile a ∧ b ve birleşim a ∨ b iki öğenin infimum ve üstünlük ≤ ile ilgili olarak sırasıyla.
İlk beş aksiyom çiftinden herhangi bir tamamlayıcının benzersiz olduğu sonucu çıkar.
Aksiyomlar kümesi öz-ikili bir aksiyomda biri ∨ ile ∧ ve 0'ı 1 ile değiştirirse, sonuç yine bir aksiyom olur. Bu nedenle, bu işlemi bir Boole cebirine (veya Boole kafesine) uygulayarak, kişi aynı elemanlarla başka bir Boole cebri elde eder; buna onun denir çift.[3]
Örnekler
En basit, önemsiz olmayan Boole cebri, iki elemanlı Boole cebri, 0 ve 1 olmak üzere yalnızca iki öğeye sahiptir ve kurallarla tanımlanır:
∧
0
1
0
0
0
1
0
1
∨
0
1
0
0
1
1
1
1
a
0
1
¬a
1
0
İçinde uygulamaları var mantık, 0 olarak yorumlanıyor yanlış, 1 olarak doğru, ∧ olarak ve, ∨ olarak veyave ¬ as değil. Değişkenleri ve Boolean işlemlerini içeren ifadeler, ifade formlarını temsil eder ve bu tür iki ifadenin, yukarıdaki aksiyomlar kullanılarak eşit olduğu gösterilebilir, ancak ve ancak karşılık gelen ifade formları mantıksal olarak eşdeğer.
İki elemanlı Boole cebri, aynı zamanda devre tasarımı için de kullanılır. elektrik Mühendisliği;[4] burada 0 ve 1, birinin iki farklı durumunu temsil eder bit içinde dijital devre, genellikle yüksek ve düşük Voltaj. Devreler, değişkenler içeren ifadelerle açıklanır ve bu tür iki ifade, ancak ve ancak karşılık gelen devreler aynı giriş-çıkış davranışına sahipse, değişkenlerin tüm değerleri için eşittir. Ayrıca, olası her girdi-çıktı davranışı uygun bir Boole ifadesi ile modellenebilir.
İki elemanlı Boole cebri, Boole cebirlerinin genel teorisinde de önemlidir, çünkü birkaç değişken içeren bir denklem genellikle tüm Boole cebirlerinde doğrudur, ancak ve ancak iki elemanlı Boole cebirinde doğruysa ( önemsiz kaba kuvvet az sayıda değişken için algoritma). Bu, örneğin aşağıdaki yasaların (Konsensüs teoremleri) genellikle tüm Boole cebirlerinde geçerlidir:
(a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) ≡ (a ∨ b) ∧ (¬a ∨ c)
(a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) ≡ (a ∧ b) ∨ (¬a ∧ c)
Gücü ayarla herhangi bir boş olmayan kümenin (tüm alt kümelerin kümesi) S bir Boole cebri oluşturur, bir kümelerin cebiri ∨: = ∪ (birleşim) ve ∧: = ∩ (kesişme) iki işlemle. En küçük eleman 0, boş küme ve en büyük eleman 1 kümedir S kendisi.
İki elemanlı Boole cebirinden sonra, en basit Boole cebiri, Gücü ayarla iki atom:
İle başlayan önermeler hesabı κ cümle sembolleri ile Lindenbaum cebiri (yani, önerme analizindeki cümle kümesi modulo mantıksal eşdeğerlik ). Bu yapı bir Boole cebri verir. Aslında ücretsiz Boole cebri κ jeneratörlerde. Önerme analizinde bir doğruluk ataması, bu cebirden iki elemanlı Boole cebirine bir Boole cebri homomorfizmidir.
Herhangi bir doğrusal sıralı Ayarlamak L en az elemanla, aralık cebiri, alt kümelerinin en küçük cebiridir. L tüm yarı açık aralıkları içeren [a, b) öyle ki a içinde L ve b ya içinde L veya ∞'a eşittir. Aralık cebirleri, Lindenbaum – Tarski cebirleri; her sayılabilir Boole cebri bir aralık cebiri için izomorfiktir.
Herhangi doğal sayın, her şeyden olumlu bölenler nın-nin n, tanımlama a≤b Eğer abölerb, oluşturur dağıtıcı kafes. Bu kafes bir Boole cebiridir, ancak ve ancak n dır-dir karesiz. Bu Boole cebirinin alt ve üst elemanı doğal 1 sayısıdır ve n, sırasıyla. Tamamlayıcısı a tarafından verilir n/a. Buluşmak ve birleşmek a ve b tarafından verilir en büyük ortak böleni (gcd) ve en küçük ortak Kat (lcm) / a ve b, sırasıyla. Yüzük ilavesi a+b lcm ile verilir (a,b) / gcd (a,b). Resim bir örnek gösterir n = 30. Karşı örnek olarak, karesiz olmayan n= 60, 30'un en büyük ortak böleni ve onun tamamlayıcısı 2 2 olurken, alt öğe 1 olmalıdır.
Boole cebirlerinin diğer örnekleri, topolojik uzaylar: Eğer X topolojik bir uzaydır, ardından tüm alt kümelerin toplanmasıdır X hangileri hem açık hem de kapalı ∨: = ∪ (birlik) ve ∧: = ∩ (kesişme) işlemleriyle bir Boole cebri oluşturur.
Eğer R keyfi yüzük ve setini tanımlıyoruz merkezi idempotentler tarafından Bir = { e ∈ R : e2 = e, eski = xe, ∀x ∈ R } sonra set Bir işlemlerle bir Boole cebri olur e ∨ f := e + f - ef ve e ∧ f := ef.
Homomorfizmler ve izomorfizmler
Bir homomorfizm iki Boole cebri arasında Bir ve B bir işlevif : Bir → B öyle ki herkes için a, b içinde Bir:
f(a ∨ b) = f(a) ∨ f(b),
f(a ∧ b) = f(a) ∧ f(b),
f(0) = 0,
f(1) = 1.
Daha sonra bunu takip eder f(¬a) = ¬f(a) hepsi için a içinde Bir. sınıf tüm Boole cebirlerinin bu morfizm kavramı ile birlikte, tam alt kategori of kategori kafesler.
Bir izomorfizm iki Boole cebri arasında Bir ve B bir homomorfizmdir f : Bir → B ters bir homomorfizm, yani bir homomorfizm ile g : B → Bir öyle ki kompozisyong ∘ f: Bir → Bir ... kimlik işlevi açık Birve kompozisyon f ∘ g: B → B kimlik işlevi açık mı B. Boole cebirlerinin bir homomorfizmi bir izomorfizmdir ancak ve ancak önyargılı.
Her Boole cebri (Bir, ∧, ∨) bir yüzük (Bir, +, ·) Tanımlayarak a + b := (a ∧ ¬b) ∨ (b ∧ ¬a) = (a ∨ b) ∧ ¬(a ∧ b) (bu işleme simetrik fark setler durumunda ve ÖZELVEYA mantık durumunda) ve a · b := a ∧ b. Bu halkanın sıfır elemanı Boole cebirindeki 0 ile çakışır; halkanın çarpımsal özdeşlik elemanı Boole cebirinin 1'idir. Bu yüzüğün özelliği var a · a = a hepsi için a içinde Bir; bu özelliğe sahip yüzüklere Boole halkaları.
Tersine, eğer bir Boole halkası Bir verildiğinde, tanımlayarak onu bir Boole cebirine dönüştürebiliriz x ∨ y := x + y + (x · y) ve x ∧ y := x · y.[5][6]Bu iki yapı birbirinin tersi olduğundan, her Boole halkasının bir Boole cebirinden kaynaklandığını ve bunun tersi olduğunu söyleyebiliriz. Ayrıca bir harita f : Bir → B Boole cebirlerinin bir homomorfizmidir ancak ve ancak Boolean halkalarının bir homomorfizmi ise. kategoriler Boole halkaları ve Boole cebirleri eşdeğerdir.[7]
Hsiang (1985) bir kurala dayalı algoritma -e Kontrol iki rastgele ifadenin her Boole halkasında aynı değeri gösterip göstermediği. Daha genel olarak, Boudet, Jouannaud ve Schmidt-Schauß (1989), denklemleri çözmek Boole halkaları ve Boole cebirlerinin benzerliğini kullanan her iki algoritmanın da uygulamaları vardır. otomatik teorem kanıtlama.
Bir ideal Boole cebirinin Bir bir alt kümedir ben öyle ki herkes için x, y içinde ben sahibiz x ∨ y içinde ben ve herkes için a içinde Bir sahibiz a ∧ x içinde ben. Bu ideal kavramı, ideal halka Boole halkasında Bir. İdeal ben nın-nin Bir denir önemli Eğer ben ≠ Bir ve eğer a ∧ b içinde ben her zaman ima eder a içinde ben veya b içinde ben. Dahası, herkes için a ∈ Bir bizde var a ∧ -a = 0 ∈ ben ve daha sonra a ∈ ben veya -a ∈ ben her biri için a ∈ Bir, Eğer ben asal. İdeal ben nın-nin Bir denir maksimum Eğer ben ≠ Bir ve tek ideal uygunsa ben dır-dir Bir kendisi. Bir ideal için ben, Eğer a ∉ ben ve -a ∉ ben, sonra ben ∪ {a} veya ben ∪ {-a} başka bir idealde uygun şekilde J. Bu nedenle, bu bir ben maksimal değildir ve bu nedenle asal ideal ve maksimal ideal kavramları Boole cebirlerinde eşdeğerdir. Dahası, bu kavramlar, halka teorik olanlarla örtüşmektedir. birincil ideal ve maksimum ideal Boole halkasında Bir.
İkili ideal bir filtre. Bir filtre Boole cebirinin Bir bir alt kümedir p öyle ki herkes için x, y içinde p sahibiz x ∧ y içinde p ve herkes için a içinde Bir sahibiz a ∨ x içinde p. Bir ikilisi maksimum (veya önemli) ideal Boole cebirinde ultra filtre. Ultrafiltreler alternatif olarak şu şekilde tanımlanabilir: 2 değerli morfizmler itibaren Bir iki elemanlı Boole cebirine. İfade Boole cebirindeki her filtre bir ultra filtreye genişletilebilir denir Ultrafilter Teoremi ve kanıtlanamaz ZF, Eğer ZF dır-dir tutarlı. ZF içinde, kesinlikle daha zayıftır. seçim aksiyomu Ultrafilter Teoreminin birçok eşdeğer formülasyonu vardır: her Boole cebirinin bir ultrafiltresi vardır, Bir Boole cebirindeki her ideal, bir asal ideale genişletilebilir, vb.
Beyanlar
Gösterilebilir ki her sonlu Boole cebri, sonlu bir kümenin tüm alt kümelerinin Boole cebirine izomorfiktir. Bu nedenle, her sonlu Boole cebirinin eleman sayısı bir ikinin gücü.
Genel olarak Boole kafeslerinin / cebirlerinin ilk aksiyomatizasyonu İngiliz filozof ve matematikçi tarafından verildi. Alfred North Whitehead 1898'de.[8][9]Dahil aksiyomların üstünde ve ayrıca x∨1 = 1 ve x∧0 = 0. 1904'te Amerikalı matematikçi Edward V. Huntington (1874–1952),, ∨, ¬'ye dayalı muhtemelen en cimri aksiyomatizasyonu vermiş, hatta birleşim yasalarını kanıtlamıştır (kutuya bakınız).[10]Ayrıca bu aksiyomların bağımsız birbirinden.[11]1933'te Huntington, Boole cebri için aşağıdaki zarif aksiyomatizasyonu ortaya koydu. Yalnızca bir ikili işlem + ve bir tekli işlevsel semboln, aşağıdaki yasaları karşılayan 'tamamlayıcı' olarak okunmalıdır:
(1), (2) ve (4) Boole cebri için bir temel oluşturur mu? (1), (2) ve (4) a Robbins cebirisorusu şu olur: Her Robbins cebiri bir Boole cebiri midir? Bu soru ( Robbins varsayımı ) onlarca yıldır açık kaldı ve en sevilen soru haline geldi Alfred Tarski ve öğrencileri. 1996 yılında William McCune -de Argonne Ulusal Laboratuvarı Larry Wos, Steve Winker ve Bob Veroff'un önceki çalışmalarına dayanarak, Robbins'in sorusuna olumlu yanıt verdi: Her Robbins cebiri bir Boole cebiridir. McCune'un kanıtı için çok önemli olan, otomatik muhakeme programıEQP o tasarladı. McCune'un ispatının basitleştirilmesi için bkz. Dahn (1998).
Boole cebirinin aksiyomlarından bir birimin varlığı gerekliliğini kaldırmak, "genelleştirilmiş Boole cebirleri" verir. Resmen, bir dağıtıcı kafesB genelleştirilmiş bir Boole kafesidir, eğer en küçük 0 öğesine sahipse ve herhangi bir öğe için a ve b içinde B öyle ki a ≤ bbir eleman var x öyle ki a ∧ x = 0 ve a ∨ x = b. A ∖ b'yi benzersiz olarak tanımlama x öyle ki (a ∧ b) ∨ x = a ve (a ∧ b) ∧ x = 0, yapının (B, ∧, ∨, ∖, 0) bir genelleştirilmiş Boole cebri(B, ∨, 0) ise bir genelleştirilmiş Boole semilattice. Genelleştirilmiş Boole kafesleri tam olarak idealler Boole kafesleri.
İki dağıtım aksiyomu dışında Boole cebirleri için tüm aksiyomları karşılayan bir yapıya ortocomplemented kafes. Ortocomplemented lattisler doğal olarak kuantum mantığı ayrılabilir için kapalı alt uzayların kafesleri olarak Hilbert uzayları.
^Kesinlikle, elektrik mühendisleri, yüksek empedans gibi diğer devre koşullarını temsil etmek için ek durumlar kullanma eğilimindedir - bkz. IEEE 1164 veya IEEE 1364.
Dahn, B. I. (1998), "Robbins Algebras are Boolean: A Revision of McCune's Computer-Generated Solution of the Robbins Problem", Cebir Dergisi, 208 (2): 526–532, doi:10.1006 / jabr.1998.7467.
