Boole cebri (yapı) - Boolean algebra (structure)

Gelen soyut cebir , bir Boole cebri veya Boole kafes isimli bir tümler dağıtıcı kafes . Bu tür cebirsel yapı , hem küme işlemlerinin hem de mantık işlemlerinin temel özelliklerini yakalar . Bir Boole cebri, bir kuvvet kümesi cebirinin veya kümeler alanının bir genellemesi olarak görülebilir veya öğeleri, genelleştirilmiş doğruluk değerleri olarak görülebilir . Aynı zamanda bir De Morgan cebirinin ve bir Kleene cebirinin (involüsyonlu) özel bir durumudur .

Her Boole cebri , bir Boolean halkasına yol açar ve bunun tersi, halka çarpımı birleşime karşılık gelen veya ∧ ile buluşur ve özel ayrılma veya simetrik farka halka eklenmesi ( ayrılma ∨ değil ) ile birlikte. Bununla birlikte, Boolean halkalarının teorisi, iki operatör arasında doğal bir asimetriye sahipken, Boole cebrinin aksiyomları ve teoremleri, dualite ilkesi tarafından açıklanan teorinin simetrisini ifade eder .

Alt kümelerin Boole kafesi

Tarih

"Boole cebiri" terimi , kendi kendini yetiştirmiş bir İngiliz matematikçi olan George Boole'u (1815-1864) onurlandırır . O tanıtıldı cebirsel sistem küçük broşürde, başlangıçta Mantık Matematik Analiz arasında devam eden kamu tartışmalara cevaben 1847 yılında yayınlanan, Augustus De Morgan ve William Hamilton , daha sonra bir daha önemli kitap olarak, Düşünce Kanunları , yayınlanan 1854. Boole'un formülasyonu, bazı önemli açılardan yukarıda açıklanandan farklıdır. Örneğin, Boole'daki birleşme ve ayrılma ikili bir işlem çifti değildi. Boole cebri 1860'larda William Jevons ve Charles Sanders Peirce tarafından yazılan makalelerde ortaya çıktı . Boole cebirinin ve dağıtımlı kafeslerin ilk sistematik sunumu , Ernst Schröder'in 1890 Vorlesungen'ine borçludur . Boole cebrinin İngilizce'deki ilk kapsamlı tedavisi AN Whitehead'in 1898 Evrensel Cebiridir . Modern aksiyomatik anlamda bir aksiyomatik cebirsel yapı olarak Boole cebiri, Edward V. Huntington'ın 1904 tarihli bir makalesiyle başlar . Boole cebri , 1930'larda Marshall Stone'un çalışmaları ve Garrett Birkhoff'un 1940 Kafes Teorisi ile ciddi bir matematik olarak olgunlaştı . 1960'larda Paul Cohen , Dana Scott ve diğerleri, matematiksel mantık ve aksiyomatik küme teorisinde Boole cebrinin dallarını, yani zorlama ve Boolean değerli modelleri kullanarak derin yeni sonuçlar buldular .

Tanım

Bir Boole cebri bir altı olan demet aşağıdakilerden oluşan grubu A , iki ile donatılmış ikili işlemler , ∨ ( "birleştirme" olarak adlandırılan veya "veya") ∧ (sözde "karşılamak" veya "ve"), bir tekli işlemi "olarak adlandırılan ¬ ( tamamlayıcı" veya "değil") ve A'daki 0 ve 1 öğeleri ("alt" ve "üst" olarak adlandırılır veya "en küçük" ve "en büyük" öğe, ayrıca sırasıyla ⊥ ve ⊤ sembolleriyle gösterilir), öyle ki tüm elemanlar bir , b ve c ve a , aşağıdaki aksiyonları tutma:

bir ∨ ( bc ) = ( birb ) ∨ c bir ∧ ( bc ) = ( birb ) ∧ c çağrışım
birb = bbir birb = bbir değişebilirlik
bir ∨ ( ab ) = bir bir ∧ ( ab ) = bir emilim
bir ∨ 0 = bir bir ∧ 1 = bir Kimlik
bir ∨ ( bc ) = ( birb ) ∧ ( birc )   bir ∧ ( bc ) = ( birb ) ∨ ( birc )   DAĞILMA
Bir ∨ ¬ bir = 1 bir ∧ ¬ bir = 0 tamamlar

Bununla birlikte, absorpsiyon yasasının ve hatta çağrışım yasasının, diğer aksiyomlardan türetilebildikleri için aksiyomlar kümesinden hariç tutulabileceğine dikkat edin (bkz. Kanıtlanmış özellikler ).

Sadece bir elemanlı bir Boole cebri, önemsiz Boole cebri veya dejenere Boole cebri olarak adlandırılır . (Daha eski çalışmalarda, bazı yazarlar bu durumu hariç tutmak için 0 ve 1'in farklı öğeler olmasını gerektirmiştir .)

Yukarıdaki son üç aksiyom çiftinden (özdeşlik, dağılım ve tamamlayıcılar) veya absorpsiyon aksiyomundan şu sonucu çıkar:

a = ba     ancak ve ancak     ab = b ise .

Tarafından tanımlanan ilişki ≤ birb Bu eşdeğer koşullar geçerli olursa, a, kısmi sıralama en azından eleman 0 ve en büyük elemanı 1. karşılamak ile birb ve birleştirme birb iki eleman kendi denk infimum ve Supremum sırasıyla, ≤ ile ilgili olarak.

İlk dört aksiyom çifti, sınırlı bir kafesin tanımını oluşturur .

İlk beş aksiyom çiftinden herhangi bir tamamlayıcının benzersiz olduğu sonucu çıkar.

Aksiyomlar kümesi, bir aksiyomda ∨ ile ∧ ve 0'ı 1 ile değiştirirse, sonuç yine bir aksiyom olduğu anlamında kendi kendine çifttir. Bu nedenle, bu işlemi bir Boole cebrine (veya Boole kafesine) uygulayarak, aynı elemanlara sahip başka bir Boole cebri elde edilir; onun ikilisi denir .

Örnekler

  • Önemsiz olmayan en basit Boole cebri, iki elemanlı Boole cebri , yalnızca iki elemana, 0 ve 1'e 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
¬ bir 1 0
  • 0'ı yanlış , 1'i doğru , ∧ as ve , ∨ veya değil ve ¬ değil olarak yorumlayarak mantıkta uygulamaları vardır . 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, ancak ve ancak karşılık gelen ifade formlarının mantıksal olarak eşdeğer olması durumunda gösterilebilir .
  • İki elemanlı Boole cebri, elektrik mühendisliğinde devre tasarımı için de kullanılır ; burada 0 ve 1 , bir dijital devredeki bir bitin tipik olarak yüksek ve alçak gerilim olmak üzere iki farklı durumunu temsil eder . Devreler, değişkenleri içeren ifadelerle tanımlanır ve bu tür iki ifade, ancak ve ancak karşılık gelen devrelerin aynı giriş-çıkış davranışına sahip olması durumunda, 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şkeni içeren bir denklem, ancak ve ancak iki elemanlı Boole cebrinde doğruysa (bu, aşağıdakiler tarafından kontrol edilebilir) tüm Boole cebirlerinde genellikle doğrudur. az sayıda değişken için önemsiz bir kaba kuvvet algoritması). Bu, örneğin aşağıdaki yasaların ( Consensus teoremleri ) genel olarak tüm Boole cebirlerinde geçerli olduğunu göstermek için kullanılabilir :
    • ( birb ) ∧ (¬ birc ) ∧ ( bc ) ≡ ( birb ) ∧ (¬ birc )
    • ( birb ) ∨ (¬ birc ) ∨ ( bc ) ≡ ( birb ) ∨ (¬ birc )
  • Kuvvet kümesi verilen herhangi bir boş olmayan kümesinin (bütün alt kümelerinin kümesi) S oluşturmasını Boole cebir, bir setlerinin cebir = ∪ (birlik) ve ∧: = ∩ (kesişim) iki operasyonlar ∨ ile. En küçük eleman 0 boş kümedir ve en büyük eleman 1 S kümesinin kendisidir.
  • İki elemanlı Boole cebrinden sonra, en basit Boole cebri, iki atomun güç kümesiyle tanımlanandır :
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
  • Tüm alt kümelerinin kümesi S ya sonlu ya vardır Cofinite bir Boole cebiri, bir olan kümeler cebiri .
  • κ cümle sembolleri ile önermeler hesabından başlayarak , Lindenbaum cebirini (yani, önermeler hesabı modulo mantıksal eşdeğerlikteki cümleler kümesini ) oluşturun. Bu yapı bir Boole cebiri verir. Aslında κ üreteçlerinde serbest Boole cebridir. Önermeler hesabındaki bir doğruluk ataması, bu cebirden iki elemanlı Boole cebrine bir Boole cebri homomorfizmidir.
  • Herhangi bir verilen doğrusal sıralı grubu L , bir en elemanı ile, aralık cebir ait alt kümelerin küçük cebir L yarı açık aralıklarda [tümünü içeren bir , b şekilde) bir olduğu L ve b ya bir L ya da eşit ∞. Aralık cebirleri, Lindenbaum-Tarski cebirlerinin incelenmesinde faydalıdır ; her sayılabilir Boole cebri, bir aralık cebrine eşbiçimlidir.
30'un bölenlerinin Boole cebrinin Hasse diyagramı .
  • Herhangi biri için bir doğal sayı , n , tüm pozitif grubu bölenler arasında n tanımlayan birB ise bir bölme b , bir oluşturan dağıtım kafes . Bu kafes bir Boole cebir ancak ve ancak n olan kare içermeyen . Bu Boole cebrinin alt ve üst elemanı sırasıyla doğal sayı 1 ve n'dir . Tamamlayıcısı bir tarafından verilir , n / a . Karşılamak ve birleştirme bir ve b ile verilir büyük ortak bölen (gcd) ve en sık birden arasında (LCM) , bir ve b sırasıyla. a + b halka eklemesi lcm( a , b )/gcd( a , b ) ile verilir. Resimde n = 30 için bir örnek gösterilmektedir . Karşı örnek olarak, karesiz n =60 göz önüne alındığında, 30'un en büyük ortak böleni ve tümleyeni 2, alt eleman 1 olmalıdır.
  • Boole cebirlerinin diğer örnekleri topolojik uzaylardan kaynaklanır : eğer X bir topolojik uzay ise, o zaman X'in hem açık hem de kapalı olan tüm alt kümelerinin toplanması, ∨ := ∪ (birleşim) ve ∧ := ∩ işlemleriyle bir Boole cebiri oluşturur. (kavşak).
  • Eğer R, isteğe bağlı bir halka olduğu ve kümesini tanımlayan merkezi İdempotentler göre
    A = { ER  : E 2 = e , ex = Xe , ∀ xR }
    o grubu bir işlem ile bir Boolean cebir olur Ef  := e + f - ef ve ef  := ef .

Homomorfizmalar ve izomorfizmler

Bir homomorfizmi iki cebir Boolean arasında A ve B a, fonksiyon f  : AB gibi tüm bu a , b de A :

f ( birb ) = f ( bir ) ∨ f ( b ),
f ( birb ) = f ( bir ) ∧ f ( b ),
f (0) = 0,
f (1) = 1.

Daha sonra bu, aşağıdaki fbir ) = ¬ f ( a tüm) a içinde A . Sınıf araya morfizma bu anlayışla tüm Boole cebiri, bir oluşturur tam alt kategoriyi ait kategorisine kafeslerin.

Bir izomorfizm cebir iki Boolean arasında A ve B , bir homomorfizma f  : AB , bir homomorfizma ters homomorfizmasının ile gr  : BA , öyle ki bir bileşim grf : Abir olan kimlik fonksiyonu ile A , ve fg : BB bileşimi , B üzerindeki özdeşlik fonksiyonudur . Boole cebirlerin bir homomorfizması bir izomorfizması ancak ve ancak o takdirde ise bijective .

Boole halkaları

Her Boole cebri ( A , ∧, ∨), a + b  := ( a ∧ ¬ b ) ∨ ( b ∧ ¬ a ) = ( ab ) ∧ ¬ tanımlayarak bir halka ( A , +, ·) verir. ( ab ) (bu işleme kümeler durumunda simetrik fark ve mantık durumunda XOR denir ) ve a · b  := ab . Bu halkanın sıfır elemanı, Boole cebirinin 0'ı ile çakışmaktadır; halkanın çarpımsal kimlik elemanı Boole cebrinin 1'idir. Bu halka, bu özelliğe sahip bir · bir = bir tüm a içinde A ; bu özelliğe sahip halkalara Boole halkaları denir .

Tersine, bir Boole halkası A verilmişse, xy  := x + y + ( x · y ) ve xy  := x · y tanımlayarak onu Boole cebirine dönüştürebiliriz . Bu iki yapı birbirinin tersi olduğu için, her Boolean halkasının bir Boole cebrinden ortaya çıktığını ve bunun tersini söyleyebiliriz. Ayrıca, bir f  : AB haritası, ancak ve ancak Boole halkalarının bir homomorfizmiyse, Boole cebirlerinin bir homomorfizmidir. Kategoriler Boole yüzük ve Boole cebirlerinin eşdeğerdir.

(1985) hsiang bir verdi kurala dayalı bir algoritma için kontrol rasgele iki ifadeleri her Boole halkada aynı değeri göstermek olup. Daha genel olarak, Boudet, Jouannaud ve Schmidt-Schauß (1989), keyfi Boolean halka ifadeleri arasındaki denklemleri çözmek için bir algoritma verdiler . Boole halkaları ve Boole cebirlerinin benzerliğini kullanan her iki algoritmanın da otomatik teorem ispatında uygulamaları vardır .

İdealler ve filtreler

Bir İdeal Boole cebri ait A bir alt kümesidir ben böyle herkes için o x , y de I elimizdeki xy de I ve herkes için a içinde A Elimizdeki birx içinde I . Bu ideal kavramı , Boole A halkasındaki halka ideali kavramıyla örtüşür . İdeal ben bir A denir asal olmadığını benA ve eğer birb içinde I hep ima bir de I veya b içinde I . Ayrıca, her aA için a-a = 0 ∈ I ve sonra her aA için aI veya -aI var , eğer ben asal ise. A'nın ideal bir I'i , eğer IA ise ve I'i tam olarak içeren tek ideal A'nın kendisiyse , maksimal olarak adlandırılır . İdeal bir I için , eğer aI ve -aI ise , o zaman I ∪ { a } veya I ∪ { -a } başka bir J idealinde düzgün bir şekilde yer alır . Dolayısıyla, bir I maksimal değildir ve bu nedenle asal ideal ve maksimal ideal kavramları Boole cebirlerinde eşdeğerdir. Ayrıca, bu kavramlar , Boolean halka A'daki asal ideal ve maksimal idealin halka teorik olanlarıyla örtüşür .

Bir idealin ikilisi bir filtredir . Bir filtre Boole cebri bir A bir alt kümesidir s tüm bu tür x , y olarak p Elimizdeki xy olarak p ve tüm a içinde A Elimizdeki birX in p . Boole cebrindeki bir maksimal (veya asal ) idealin duali ultrafiltredir . Ultrasüzgeçlerin alternatif olarak tanımlanabilir 2-değerli Morfizm gelen A , iki eleman Boole cebire. İfadesi bir Boole cebir her filtre bir ultra uzatılabilir denir Ultrafilter Teoremi ve ispat edilemez ZF eğer, ZF olduğunu tutarlı . ZF içinde , seçim aksiyomundan kesinlikle daha zayıftır . Ultrafilter Teoreminin birçok eşdeğer formülasyonu vardır: her Boole cebrinin bir ultrafiltresi vardır , Boole cebrindeki her ideal bir asal ideale genişletilebilir , vb.

temsiller

Her sonlu Boole cebrinin, sonlu bir kümenin tüm alt kümelerinin Boole cebrine eşbiçimli olduğu gösterilebilir . Bu nedenle, her sonlu Boole cebri elemanların sayısı olan iki güç .

Stone'un Boole cebirleri için ünlü temsil teoremi , her Boole cebri A'nın , bazı ( kompakt, tamamen bağlantısız Hausdorff ) topolojik uzaydaki tüm clopen kümelerinin Boole cebrine eşbiçimli olduğunu belirtir .

aksiyomatik

Boolean kafeslerinin/cebirlerinin genel olarak ilk aksiyomizasyonu , 1898'de İngiliz filozof ve matematikçi Alfred North Whitehead tarafından verildi . Yukarıdaki aksiyomları ve ayrıca x ∨1=1 ve x ∧0=0'ı içeriyordu. 1904'te Amerikalı matematikçi Edward V. Huntington (1874–1952) ∧, ∨, ¬'ye dayalı muhtemelen en cimri aksiyomatizasyonu yaptı, hatta çağrışım yasalarını kanıtladı (kutuya bakınız). Ayrıca bu aksiyomların birbirinden bağımsız olduğunu kanıtladı . 1933'te Huntington, Boole cebri için aşağıdaki zarif aksiyomizasyonu başlattı. Aşağıdaki yasaları karşılayan 'tamamlayıcı' olarak okunması için yalnızca bir ikili işlem + ve bir tekli işlevsel sembol n gerektirir :

  1. Değişebilirlik : x + y = y + x .
  2. İlişkilendirme : ( x + y ) + z = x + ( y + z ).
  3. Huntington denklemi : n ( n ( x ) + y ) + n ( n ( x ) + n ( y )) = x .

Herbert Robbins hemen sordu: Huntington denklemi ikilisiyle değiştirilirse, yani:

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

(1), (2) ve (4) Boole cebri için bir temel oluşturur mu? (1), (2) ve (4) bir Robbins cebiri olarak adlandırıldığında , soru şu hale gelir: Her Robbins cebiri bir Boolean cebiri midir? Bu soru ( Robbins varsayımı olarak bilinir ) onlarca yıl açık kaldı ve Alfred Tarski ve öğrencilerinin favori sorusu haline geldi . 1996'da Argonne Ulusal Laboratuvarı'ndan William McCune , Larry Wos, Steve Winker ve Bob Veroff'un daha önceki çalışmalarına dayanarak Robbins'in sorusunu olumlu yanıtladı: Her Robbins cebri bir Boole cebridir. McCune'un kanıtı için çok önemli olan, tasarladığı EQP bilgisayar programıydı . McCune'un ispatının basitleştirilmesi için Dahn'a (1998) bakınız.

Aksiyomların sayısını azaltmak için daha fazla çalışma yapılmıştır; bkz . Boole cebri için minimal aksiyomlar .

genellemeler

Boole cebrinin aksiyomlarından bir birimin var olma şartının kaldırılması "genelleştirilmiş Boole cebri" verir. Biçimsel olarak, bir dağıtım kafes B bir küçük elemanı 0 vardır ve herhangi bir elemanı için genelleştirilmiş bir Boole kafes olan bir ve B içinde B , öyle ki birb , bir elemanın vardır x bir ∧ x = 0 ve ∨ x, = b. a ∖ b'yi (a ∧ b) ∨ x = a ve (a ∧ b) ∧ x = 0 olacak şekilde benzersiz x olarak tanımlayarak , (B,∧,∨,∖,0) yapısının genelleştirilmiş bir Boolean olduğunu söyleriz cebir , (B,∨,0) ise genelleştirilmiş bir Boole yarı örgüsüdür . Genelleştirilmiş Boole kafesleri, tam olarak Boole kafeslerinin idealleridir .

İki dağıtım aksiyomu dışında Boole cebri için tüm aksiyomları karşılayan bir yapıya orto-tümlemeli kafes denir . Orto-tümlemeli kafesler, kuantum mantığında , ayrılabilir Hilbert uzayları için kapalı alt uzayların kafesleri olarak doğal olarak ortaya çıkar .

Ayrıca bakınız

Notlar

Referanslar

Atıfta bulunulan eserler

  • Davey, BA; Priestley, HA (1990). Kafeslere Giriş ve Düzen . Cambridge Matematik Ders Kitapları. Cambridge Üniversitesi Yayınları.
  • Cohn, Paul M. (2003), Temel Cebir: Gruplar, Halkalar ve Alanlar , Springer, pp. 51, 70–81, ISBN 9781852335878
  • Givant, Steven; Halmos, Paul (2009), Boole Cebirlerinin giriş , Matematik Lisans Metinler , Springer , ISBN 978-0-387-40293-2.
  • Goodstein, RL (2012), "Bölüm 2: Aksiyomların self-dual sistemi" , Boolean Algebra , Courier Dover Publications, pp. 21ff, ISBN 9780486154978
  • Huntington, Edward V. (1904). "Mantık Cebiri için Bağımsız Postülalar Kümeleri" . Amerikan Matematik Derneği'nin İşlemleri . 5 (3): 288–309. doi : 10.1090/s0002-9947-1904-1500675-4 . JSTOR  1986459 .
  • Padmanabhan, Ranganathan; Rudeanu, Sergiu (2008), kafesler ve boole cebirleri için aksiyomlar , World Scientific, ISBN 978-981-283-454-6.
  • Taş, Marshall H. (1936). "Boole Cebiri için Temsil Teorisi" . Amerikan Matematik Derneği'nin İşlemleri . 40 : 37-111. doi : 10.1090/s0002-9947-1936-1501865-8 .
  • Whitehead, AN (1898). Evrensel Cebir Üzerine Bir İnceleme . Cambridge Üniversitesi Yayınları. ISBN'si 978-1-4297-0032-0.

Genel referanslar

Dış bağlantılar