Boole cebri

Boole'un mantık cebri

1847 baharında Sir William Hamilton ile Augustus De Morgan arasında süren bir tartışma ilgisini çekince Boole, yıllar önce bıraktığı araştırmalara geri döndü ve sonuçlarını aynı yıl The Mathematical Analysis of Logic (Mantığın Matematiksel Çözümlemesi) adlı kısa kitabında yayımladı.^:iii De Morgan da aynı yıl Formal Logic (Biçimsel Mantık) adlı kitabını çıkardı. Burris ve Legris'e göre, mantığın matematiksel yapısını açık bir cebirsel sistemle ortaya koyan mantık cebri Boole'un bu kitabıyla başlar. De Morgan ise eşitlik için bir simge kullanmadığından denklemlere dayalı bir mantık cebri kuramamıştı.

Boole kitabında 1 simgesini, gerçekte var olsun ya da olmasın düşünülebilecek bütün sınıfları kapsayan evren için kullandı. x, y, z gibi simgeler, üzerinde işlem yaptıkları bir konudan X, Y ve Z sınıflarının üyelerini seçen işlemleri gösteriyordu. Boole bunlara seçici simgeler (İngilizce: elective symbols) adını verdi. xy çarpımı önce Y sınıfının, sonra bu sınıfın içinden X'lerin seçilmesiyle hem X hem Y olan üyelerin sınıfını veriyordu.^:14-15 Boole bu simgelerin uyduğu temel yasaları dağılma (${\displaystyle x(u+v)=xu+xv}$), değişme (${\displaystyle xy=yx}$) ve ${\displaystyle x^{n}=x}$ biçiminde yazdı. Sonuncusuna üs yasası (İngilizce: index law) adını verdi. Bir seçme işleminin art arda birçok kez yapılmasının sonucu değiştirmediğini anlatan bu yasanın seçici simgelere özgü olduğunu belirtti.^:16-17 X olmayanların sınıfını ${\displaystyle 1-x}$ ile gösterdi; "bütün X'ler Y'dir" önermesini ${\displaystyle x(1-y)=0}$, "hiçbir X Y değildir" önermesini ise ${\displaystyle xy=0}$ denklemiyle yazdı.^:20-21

Burris ve Legris'e göre Boole'un sisteme getirdiği tek yeni yasa, çarpmanın ${\displaystyle XX=X}$ biçimindeki etkisizlik yasasıydı ve bu mantık yasasını daha önce Leibniz de dile getirmişti. Boole toplamayı yalnız ortak üyesi olmayan sınıflar için, çıkarmayı da bir sınıftan kendi alt sınıfının çıkarılması için tanımlıyor, öteki durumları yorumlanamaz sayıyordu.

Boole 1854'te, Cork'taki Queen's College'da matematik profesörüyken An Investigation of the Laws of Thought (Düşünce Yasaları Üzerine Bir İnceleme) adlı ikinci kitabını yayımladı. Önsözüne göre bu kitap ilkinin yeni bir baskısı değildi. Aynı temel yasalar sistemiyle başlıyor, ancak daha genel yöntemler ve çok daha geniş uygulamalar içeriyordu.^{:i, iii} Boole, mantık simgelerinin ${\displaystyle x^{2}=x}$ yasasına uyduğunu, sayılardan ise yalnız 0 ile 1'in bu yasayı sağladığını belirtti. Değişkenlerin yalnız 0 ve 1 değerlerini aldığı bir cebrin yasalarının, aksiyomlarının ve işlemlerinin mantık cebrininkilerle bütünüyle aynı olduğunu, ikisini yalnız yorum farkının ayırdığını yazdı ve kitabın yöntemini bu ilkeye dayandırdı.^:26-27 Aynı yasadan ${\displaystyle x(1-x)=0}$ denklemini türeterek, bir varlığın bir niteliği aynı anda hem taşıyıp hem de taşımamasının olanaksız olduğunu söyleyen çelişmezlik ilkesini cebirsel olarak elde etti.^:34-35

"Ve" ile "veya" bağlaçlarının sınıfları birbirinden ayırma gücü taşıdığını savunan Boole, + işaretini birbirini dışlayan sınıflar için kullandı. Bu yüzden "ya x'ler ya y'ler" ifadesi iki sınıfa birden giren nesneleri de kapsayacaksa ${\displaystyle x+y(1-x)}$, kapsamayacaksa ${\displaystyle x(1-y)+y(1-x)}$ biçiminde yazılmalıydı.^:39-40 Kitabın beşinci bölümünde verdiği ${\displaystyle f(x)=f(1)\,x+f(0)\,(1-x)}$ açılımı, bir işlevi, değişken 0 ve 1 olduğunda aldığı değerlerle yeniden yazar.^:52-53 Brown, bu açılımın 19. yüzyıl mantıkçılarınca yaygın olarak kullanıldığını, bilgisayar tasarımı ve anahtarlama kuramı kitaplarında ise çoğu zaman Shannon'a mal edildiğini belirtir.^:36 Burris ve Legris de Boole'un 1854'teki sisteminin, bir çıkarımın doğruluğunu sınıf simgelerine yalnız 0 ve 1 değerleri verip sıradan aritmetik işlemlerle denetlemeye dayandığını belirtir ve bu ilkeye "0 ve 1 kuralı" adını verir.

Jevons, Peirce ve Schröder

Boole'un toplamayı yalnız ayrık sınıflar için tanımlaması ardıllarınca değiştirildi. De Morgan'ın öğrencisi olan Jevons, 1863'te Boole'a yazarak toplamanın kapsayan veya, bir başka deyişle sınıfların birleşimi olarak tanımlanmasını önerdi. Bu tanım ${\displaystyle X+X=X}$ yasasını getiriyordu. Boole öneriyi kesinlikle reddetti ve yazışmayı kesti. Jevons kendi sistemini 1864'te Pure Logic (Arı Mantık) adlı kitabında yayımladı; yıllar içinde geliştirdiği aksiyomlar ve çıkarım kuralları, değişken içermeyen terimler için özünde bugünkü Boole cebrine ulaştı.

Peirce de 1867 tarihli bir makalesinde Boole'un kısmi toplama işleminin yerine birleşimin konması gerektiği sonucuna Jevons'tan bağımsız olarak vardı. 1880'de yayımladığı "On the Algebra of Logic" (Mantık Cebri Üzerine) makalesinde eşitlik yerine, alt sınıf olma ya da gerektirme olarak yorumlanabilen kapsanma bağıntısını temel aldı. Toplama ve çarpmayı bu sıra bağıntısına göre en küçük üst sınır ve en büyük alt sınır olarak tanımladı ve bugün kafes denen yapıların denklemsel özelliklerini sıraladı.

Peirce dağılma yasasının da bu özelliklerden çıktığını, ancak kanıtının makaleye konamayacak kadar uzun olduğunu yazmıştı. Ernst Schröder bunu sorguladı ve Peirce 1885'te kanıtı veremediğini kabul etti. Huntington 1904 tarihli makalesinde Peirce'in Aralık 1903'te kendisine bir mektupla gönderdiği kanıtı yayımladı. Peirce mektubunda kanıtı 1880 makalesi için yazdığını, ama kanıtın sonradan metinden çıkarıldığını anlatıyordu.^:300-301 Burris ve Legris'e göre bu kanıt da açığı kapatmaz, çünkü dağılma yasası genel kafeslerde geçerli değildir ve kanıt tümleyene ilişkin ek bir varsayım kullanır. Schröder dağılma yasasının kafes özelliklerinden çıkmadığını gösteren karşı örnekler vermiş, Richard Dedekind de 1897'de beş elemanlı bir karşı örnek bulmuştu.

Schröder 1890-1905 yıllarında yayımlanan üç ciltlik Vorlesungen über die Algebra der Logik (Mantık Cebri Üzerine Dersler) adlı yapıtında mantık cebrini sistemleştirdi. Burris ve Legris, Boole'un ilk kitabından Alfred North Whitehead ile Bertrand Russell'ın Principia Mathematica (1910-1913) adlı yapıtının Birinci Dünya Savaşı'ndan sonra etkisini yaymasına kadar geçen dönemde mantık cebrinin, en çok da Schröder'in sunduğu biçimiyle, matematiksel mantığın en gelişmiş biçimi olduğunu belirtir.

Aksiyomlaştırma ve adlandırma

David Hilbert'in 1899'da Öklid geometrisini çizimlere dayanmayan aksiyomatik bir konu olarak sunması, matematikte aksiyom sistemlerine ilgiyi artırdı. Aksiyomların birbirinden bağımsız olup olmadığı ve hangi temel kavramların en yalın sistemi verdiği soruldu; Huntington bu soruyu mantık cebri için ele alan ilk kişilerden biriydi. Huntington 1904'te Transactions of the American Mathematical Society dergisinde yayımladığı makalesinde mantık cebri için üç aksiyom takımı verdi. Birincisi iki işlem, ikincisi Schröder'in kapsanma bağıntısı, üçüncüsü ise tek bir işlem üzerine kuruluydu. Huntington her takımın tutarlı ve aksiyomlarının birbirinden bağımsız olduğunu, üç takımın da birbirine denk olduğunu kanıtladı; makaledeki özgün katkısının esas olarak bu bağımsızlık kanıtları olduğunu belirtti.^:290-291 Birinci takımda Whitehead'in A Treatise on Universal Algebra (1898) adlı kitabındaki temel önermeleri izlemiş, ancak orada temel kabul edilen toplama ve çarpmanın birleşme yasalarını aksiyomlardan teorem olarak türetmişti.^:291

Henry M. Sheffer 1913'te Boole cebirleri için tek bir ikili işlem üzerine kurulu, yalnız beş aksiyomdan oluşan bir takım yayımladı. Önceki takımların her biri tek bir cebri değil bir cebirler sınıfını belirlediği için Boolean algebras terimini çoğul olarak kullandığını açıkladı; Whitehead'in, mantık cebrini bütün temel özellikleriyle Boole'un bulup olgunlaştırdığını yazdığını da gerekçeleri arasında saydı.^:481-482 Sheffer'in işlemi bugün Sheffer çizgisi adıyla anılır. Whitehead ve Russell, Principia Mathematicanın ikinci baskısının önsözünde bu işlemi kitabın ilk baskısından bu yana mantıktaki en büyük ilerleme saymıştır. Burris ve Legris, Schröder'in bu işlemin ikizinin de aynı özelliği taşıdığını onlarca yıl önce bulduğunu belirtir.

Boole cebirlerinin genel yapısının incelenmesi 1920'lerin sonunda başladı ve Marshall Harvey Stone'un çalışmalarıyla kısa sürede ileri bir düzeye ulaştı. Hilbert uzayındaki simetrik dönüşümlerin spektral kuramı üzerinde çalışırken Boole cebirlerine yönelen Stone, 1936'da her Boole cebrinin bir sınıflar cebrine izomorf olduğunu kanıtladı. Aynı çalışmada Boole cebirlerinin, her elemanının karesi kendisine eşit olan birimli halkalarla özdeş olduğunu gösterdi.^:37-38 Ardından Boole cebirleri ile bugün Stone uzayları denen topolojik uzaylar arasında bir karşılık kurdu.

Anahtarlama devrelerine uygulanması

Boole cebrinin anahtarlama sistemlerinin tasarımında kullanılabileceğini ilk kez 1910'da fizikçi Paul Ehrenfest, Louis Couturat'nın The Algebra of Logic adlı kitabı üzerine bir Rus fizik ve kimya dergisinde yayımladığı eleştiride önerdi. Ehrenfest cebrin otomatik telefon santrallerinin tasarımında kullanılmasını salık verdi, ancak bunun nasıl yapılacağını göstermedi. Bu yolu ayrıntılı olarak gösteren çalışmalar 1936 ile 1938 arasında Japonya'da, Amerika Birleşik Devletleri'nde ve Sovyetler Birliği'nde birbirinden bağımsız olarak yayımlandı. Brown, bunlardan yalnız Sovyetler Birliği'nde V. I. Shestakov'un 1938'de Moskova Devlet Üniversitesi'nde sunduğu tezin Ehrenfest'in önerisine dayandığını belirtir.^:xiii

Japonya'da Akira Nakashima 1930'larda Boole cebrine karşılık gelen bir kuramı bağımsız olarak kurdu ve röle devrelerinin tasarımına uyguladı. Yamada'ya göre Nakashima 1935'te De Morgan yasalarını da içeren bir röle devresi kuramı yayımladı. 1936'da Masao Hanzawa ile birlikte anahtarlama devrelerini + ve × işaretleriyle mantıksal ifadeler olarak yazdı ve bu ifadelerin dönüştürülmesini ve sadeleştirilmesini de kapsayan bir anahtarlama kuramı ortaya koydu. Brown, Nakashima'nın 1937'de Japonya'da yayımlanan ve anahtarlama hesabını kümeler cebriyle özdeşleştiren makalesini, Boole cebrini anahtarlama kuramına uygulayan en erken çalışma sayar ve bu çalışmanın Amerika Birleşik Devletleri'nde pek fark edilmediğini belirtir.^:xiii Nakashima'nın İngilizce makalelerinin tümünü, doğumunun yüzüncü yılı olan 2008'de Finlandiya'daki Tampere Teknoloji Üniversitesi yeniden bastı.

Bu çalışmaların en etkilisi, Shannon'ın Massachusetts Teknoloji Enstitüsü'nde hazırladığı yüksek lisans tezine dayanan A Symbolic Analysis of Relay and Switching Circuits (Röle ve Anahtarlama Devrelerinin Simgesel Çözümlemesi) adlı makaledir.^:xiii Tezin özeti olan makale Haziran 1938'de Washington'daki AIEE yaz toplantısında sunuldu ve aynı yıl Transactions of the American Institute of Electrical Engineers dergisinde yayımlandı. Shannon makalede yüreklendirmeleri ve eleştirileri için Vannevar Bush ile MIT'den F. L. Hitchcock ve S. H. Caldwell'e teşekkür eder. Yalnız seri ve koşut bağlantılar içeren devreler için kurduğu hesabın önermeler hesabıyla tam olarak benzeştiğini gösterdi. Bu sayede önermeler hesabının her teoremi röle devreleri için de geçerli bir teorem oluyordu.

Sayısal bilgisayarların yaygınlaşmasıyla Boole cebri, devre sadeleştirme yöntemlerinin de temeli oldu. Willard Van Orman Quine 1952'den başlayarak yayımladığı makalelerle sadeleştirme kuramının temellerini attı.^:xii-xiii Maurice Karnaugh da 1953'te, Edward W. Veitch'in çizelgelerini yeniden düzenleyip genişleterek Boole işlevlerini bir harita üzerinde sadeleştirme yöntemini yayımladı.^:593

İki değerli Boole cebri

Boole cebirlerinin en yalın ve en çok kullanılan örneği, yalnız 0 ve 1 elemanlarından oluşan iki elemanlı Boole cebridir. Bu cebirde 0 yanlışa, 1 doğruya karşılık gelir ve Boole işlemleri mantıksal veya, mantıksal ve ile tümleme işlemlerinin alışılmış doğruluk tablolarını verir. Bir denklemin bütün Boole cebirlerinde geçerli olması için iki elemanlı Boole cebrinde geçerli olması yeter. Brown'un aktardığı bir ders kitabı, iki elemanlı Boole cebrini anahtarlama cebri (İngilizce: switching algebra) adıyla anar; kitaba göre bu cebir, Boole cebirlerinin en yararlısıdır ve sayısal sistemleri oluşturan anahtarlama devrelerinin çözümlenmesinin ve tasarımının matematiksel temelidir. Brown ise mantık tasarımında daha büyük Boole cebirlerinin de vazgeçilmez ve yararlı olduğunu savunur.^:61

Bir Boole değişkeni yalnız 0 ve 1 değerlerinden birini alır. Bu iki değer soyut simgelerdir; mantıkta yanlış ile doğruya, bir anahtarın açık ve kapalı durumlarına ya da bir CMOS devresinde alçak ve yüksek gerilime karşılık getirilebilir.^{:slayt 5} Sayısal devrelerde bir değişkenin ya da işlevin 1 değeri yüksek gerilim düzeyini, 0 değeri ise alçak gerilim düzeyini gösterebilir. 0 ve 1 değerleri doğru ve yanlışın yanı sıra var ile yok ya da olumlu ile olumsuz gibi iki durumlu her karşıtlığı gösterebilir.^{:slayt 5}

Temel işlemler

Boole cebrinin üç temel işlemi VE, VEYA ve DEĞİL işlemleridir. VE işlemi (İngilizce: AND), iki değişkenin de 1 olduğu durumda 1, öteki bütün durumlarda 0 sonucunu verir. VEYA işlemi (İngilizce: OR) değişkenlerden en az biri 1 olduğunda 1, ikisi de 0 olduğunda 0 verir. DEĞİL işlemi (İngilizce: NOT) ise tek değişkenli bir işlemdir ve değişkenin tümleyenini verir; 0'ın tümleyeni 1, 1'in tümleyeni 0'dır.^{:slayt 10-12:s. 35-36} Bu üç işlem birlikte her Boole işlevini kurmaya yeter.^{:slayt 9}

Boole cebrinde ${\displaystyle 1+1=1}$ olur. Shannon, iki değerli anahtarlama cebri için verdiği aksiyomlardan sıradan cebirden ayrılan tek eşitliğin bu olduğunu, ama bu farkın simgelerin işlenmesini büyük ölçüde kolaylaştırdığını belirtmişti. Bu biçimiyle VEYA işlemi, iki değişkenin de 1 olduğu durumu da kapsadığı için kapsayan veya (İngilizce: inclusive or) diye anılır. Değişkenlerden yalnız biri 1 olduğunda 1 veren işlem ise dışlayan VEYA'dır (özel veya diye de anılır). ⊕ işaretiyle gösterilen bu işlem ${\displaystyle x\oplus y={\overline {x}}y+x{\overline {y}}}$ eşitliğiyle temel işlemler cinsinden yazılır.^{:slayt 7-8}

Gösterim

Boole işlemleri için alana göre farklı işaretler kullanılır. Mantıkta VE için ∧, VEYA için ∨, DEĞİL için ¬ işaretleri yaygındır; kümeler cebrinde aynı işlemler kesişim (∩), birleşim (∪) ve tümleyen olarak yazılır.^:24-25 Sayısal tasarımda VE işlemi çarpma işaretiyle (·), VEYA işlemi toplama işaretiyle (+), DEĞİL ise değişkenin üzerine çizilen bir çizgiyle ya da değişkenin sağına konan kesme işaretiyle (′) gösterilir.^{:slayt 10-12} Örneğin ${\displaystyle {\overline {x}}}$ ya da x′ ifadesi "x’in değili" ya da "x’in tümleyeni" diye okunur. x = 1 ise x′ = 0, x = 0 ise x′ = 1 olur.^{:s. 35} x ve y değişkenlerinin VE işlemi ${\displaystyle x\cdot y}$, VEYA işlemi ise ${\displaystyle x+y}$ biçiminde yazılır.^{:slayt 11-12}

Başlıca gösterimler

İşlem	Mantık	Sayısal tasarım	Kümeler	C dili
VE	${\displaystyle x\land y}$	${\displaystyle x\cdot y}$, ${\displaystyle xy}$	${\displaystyle X\cap Y}$	x && y
VEYA	${\displaystyle x\lor y}$	${\displaystyle x+y}$	${\displaystyle X\cup Y}$	x || y
DEĞİL	${\displaystyle \lnot x}$	${\displaystyle {\overline {x}}}$, x′	tümleyen küme	!x
Dışlayan VEYA		${\displaystyle x\oplus y}$		x ^ y (bit düzeyinde)

C dilinde &&, || ve ! mantıksal işleçlerdir; &, |, ^ ve ~ ise aynı işlemleri bir sayının bitleri üzerinde tek tek yapan bit düzeyindeki işleçlerdir.^{:§ 6.5.3.3, 6.5.10-6.5.14} Python'da mantıksal işleçler and, or ve not sözcükleriyle yazılır.

Huntington 1904 tarihli makalesinde işlemleri, çevresine daire çizilmiş artı ve çarpı işaretleriyle ⊕ ve ⊙ biçiminde yazdı. Amacı bu işaretlerin yalnız aksiyomlarda belirtilen özellikleri taşıyan tanımsız simgeler olduğunu okura hatırlatmak, içlerindeki + ve × işaretleriyle de en yararlı yorumu akla getirmekti. Huntington, Leibniz'in de ⊕ işaretini aynı amaçla 1700 dolaylarında kullandığını belirtir.^:292 Bugünkü kaynaklarda ⊕ işareti dışlayan VEYA işlemini gösterir.^{:slayt 7}

İşlem önceliği

Sıradan cebirde olduğu gibi Boole cebrinde de çarpma işareti çoğunlukla yazılmaz; ${\displaystyle x\cdot y}$ yerine ${\displaystyle xy}$ yazılır. Parantez sayısını azaltmak için VE işleminin VEYA işleminden önce yapıldığı kabul edilir. Bu yüzden ${\displaystyle (x\cdot y)+z}$ ifadesi kısaca ${\displaystyle xy+z}$ biçiminde yazılabilir.^:24 Birleşme yasası sayesinde ikiden çok terimin toplamında ve çarpımında parantez kullanmak da gerekmez.

Programlama dillerinde öncelik dilin kurallarıyla belirlenir. C dilinin dilbilgisinde mantıksal VE ifadesi mantıksal VEYA ifadesinin bir parçası olarak tanımlandığından && işleci || işlecinden önce uygulanır.^{:§ 6.5.13-6.5.14} Python'da Boole işlemleri artan öncelik sırasıyla or, and ve not'tur. not işleci Boole işleci olmayan işleçlerden daha düşük öncelikli olduğu için not a == b ifadesi not (a == b) olarak yorumlanır.

Huntington'ın aksiyomları

Huntington'ın 1904'teki birinci takımı bir eleman sınıfı ile bu sınıf üzerinde tanımlı iki birleştirme kuralına dayanır ve on aksiyomdan oluşur. Huntington birim elemanları Λ ve V simgeleriyle yazmıştı; çizelgede bugünkü gösterimle verilmiştir.^:292-293

Huntington'ın 1904'teki birinci aksiyom takımı

Aksiyom	VEYA (+) biçimi	VE (·) biçimi
Kapalılık (Ia, Ib)	a ile b sınıftaysa ${\displaystyle a+b}$ de sınıftadır	a ile b sınıftaysa ${\displaystyle a\cdot b}$ de sınıftadır
Birim elemanlar (IIa, IIb)	Her a için ${\displaystyle a+0=a}$ olan bir 0 elemanı vardır	Her a için ${\displaystyle a\cdot 1=a}$ olan bir 1 elemanı vardır
Değişme (IIIa, IIIb)	${\displaystyle a+b=b+a}$	${\displaystyle a\cdot b=b\cdot a}$
Dağılma (IVa, IVb)	${\displaystyle a+(b\cdot c)=(a+b)\cdot (a+c)}$	${\displaystyle a\cdot (b+c)=(a\cdot b)+(a\cdot c)}$
Tümleyen (V)	0 ve 1 tekse her a için ${\displaystyle a+{\overline {a}}=1}$ ve ${\displaystyle a\cdot {\overline {a}}=0}$ olan bir ${\displaystyle {\overline {a}}}$ elemanı vardır
En az iki eleman (VI)	Sınıfta birbirinden farklı en az iki eleman vardır

Huntington aksiyomların tutarlı olduğunu, hepsini sağlayan iki sistem göstererek kanıtladı. Birincisinde elemanlar düzlemdeki bölgelerdir; boş bölge ve bütün düzlem de bunlara katılır, iki bölgenin toplamı ikisini de kapsayan en küçük bölge, çarpımı ise ikisinin de içinde kalan en büyük bölgedir. İkincisi, yalnız 0 ve 1'den oluşan ve Huntington'ın en yalın sistem dediği iki elemanlı sınıftır.^:292-293 Aksiyomların bağımsızlığını göstermek için de her aksiyoma karşılık, o aksiyom dışındaki dokuzunu sağlayan bir sistem kurdu. Örneğin VI. aksiyomun ötekilerden çıkmadığı, tek elemanlı bir sınıfla gösterilir.^:296

Huntington bu aksiyomlardan etkisizlik yasasını, ${\displaystyle a+1=1}$ eşitliğini, soğurma yasasını, tümleyenin tek olduğunu, De Morgan yasalarını ve birleşme yasalarını teorem olarak türetti. De Morgan yasalarının toplama ile çarpma arasındaki ikiliği kurduğunu ve bu yasalarla işlemlerden birinin ötekiyle tümleme cinsinden tanımlanabileceğini belirtti.^:293-294 Makalenin ekinde, sonlu her Boole cebrinin eleman sayısının 2'nin bir kuvveti olduğunu kanıtladı.^:309

Başka aksiyom takımları

Ders kitaplarında Huntington'ın takımının yalınlaştırılmış biçimleri kullanılır. Brown, Huntington'dan uyarladığı takımda değişme, dağılma, birim eleman ve tümleyen aksiyomlarını 0 ile 1'in farklı elemanlar olması koşuluyla yeterli sayar ve tümleyenin tek olduğunun bunlardan kolayca gösterilebileceğini belirtir.^:23-24 Monk'un tanımı ise toplama ve çarpmanın birleşme yasalarını ve soğurma yasalarını da aksiyomlar arasında sayar.

Sheffer'in 1913'teki takımı, tek bir ikili işlem üzerine kuruludur. Sheffer bu işlemi ${\displaystyle a\mid b}$ biçiminde yazdı ve ${\displaystyle a'=a\mid a}$ tanımıyla şu beş aksiyomu verdi:^:482

1. En az iki farklı eleman vardır.
2. a ile b sınıftaysa ${\displaystyle a\mid b}$ de sınıftadır.
3. ${\displaystyle (a')'=a}$
4. ${\displaystyle a\mid (b\mid b')=a'}$
5. ${\displaystyle (a\mid (b\mid c))'=(b'\mid a)\mid (c'\mid a)}$

Sheffer bu takımın Huntington'ın birinci takımına denk olduğunu kanıtladı. Mantıkta işlemi "ne p ne q" olarak yorumladı ve ikilik ilkesi gereği aynı sonuçların, işlem ${\displaystyle {\overline {a}}+{\overline {b}}}$ olarak yorumlandığında da geçerli kaldığını belirtti.^:486-487 İlk yorum bugünkü VEYA DEĞİL, ikincisi ise VE DEĞİL işlemine karşılık gelir.^{:slayt 13}

Huntington 1933'te yeni aksiyom takımları önerdi. Bunlardan biri yalnız üç denklemden oluşuyordu:

${\displaystyle a+b=b+a,\qquad (a+b)+c=a+(b+c),\qquad (a'+b')'+(a'+b)'=a}$

Kısa süre sonra Herbert Robbins üçüncü denklemin daha yalın olan ${\displaystyle [(a+b)'+(a+b')']'=a}$ denklemiyle değiştirilebileceği sanısını ortaya attı. Ne Huntington ne Robbins bunu kanıtlayabildi; sanı Alfred Tarski ve öğrencilerinin çabalarına da direndi. Robbins sanısını ancak 1996'da, Winker'in kısmi sonuçları üzerine, Argonne Ulusal Laboratuvarı'ndan William McCune'un tasarladığı EQP adlı otomatik teorem kanıtlayıcısı kanıtladı.

İki değerli cebrin işlem eşitlikleri

İki elemanlı Boole cebrinde işlemlerin bütün sonuçları on eşitlikle sayılabilir. Bu eşitlikler VE, VEYA ve DEĞİL işlemlerinin doğruluk tablolarının satırlarıdır.^{:slayt 10-12}

VE		VEYA		DEĞİL
${\displaystyle 0\cdot 0=0}$	${\displaystyle 1\cdot 1=1}$	${\displaystyle 0+0=0}$	${\displaystyle 1+1=1}$	${\displaystyle {\overline {0}}=1}$
${\displaystyle 0\cdot 1=0}$	${\displaystyle 1\cdot 0=0}$	${\displaystyle 0+1=1}$	${\displaystyle 1+0=1}$	${\displaystyle {\overline {1}}=0}$

Shannon 1938'de anahtarlama devreleri için kurduğu cebirde VE ve VEYA işlemlerine ait sekiz eşitliği, her değişkenin her an ya 0 ya da 1 olduğunu söyleyen bir ek aksiyomla birlikte aksiyom olarak aldı; tümleyeni ise ayrıca tanımladı. Aksiyomları ikişer ikişer düzenleyerek her çiftte 0 ile 1 ve toplama ile çarpma yer değiştirdiğinde birinden ötekinin elde edildiğini gösterdi. Bu işlem tabloları yalnız iki elemanlı Boole cebrini tanımlar. Brown'un örnekleri arasında bu cebrin yanında altkümelerle, önerme işlevleriyle ve bir sayının bölenleriyle kurulan başka Boole cebirleri de vardır.^:24-27

Değişme yasası

${\displaystyle x+y=y+x}$

${\displaystyle x\cdot y=y\cdot x}$

Değişkenlerin yazılış sırası VE ile VEYA işlemlerinin sonucunu değiştirmez. Bu yasalar doğrudan işlemlerin tanımından çıkar.^{:s. 40-41} Boole 1854'te toplamanın değişme yasasını "erkekler ve kadınlar" ile "kadınlar ve erkekler" ifadelerinin aynı anlama gelmesiyle örneklemişti.^:23

Birleşme yasası

${\displaystyle x+(y+z)=(x+y)+z=x+y+z}$

${\displaystyle x\cdot (y\cdot z)=(x\cdot y)\cdot z=x\cdot y\cdot z}$

Birleşme yasaları sayesinde ikiden çok terimin toplamında ve çarpımında parantez kullanmak gerekmez. Devrelerde bunun karşılığı, iki girişli iki VE kapısının yerine üç girişli tek bir VE kapısının, iki girişli iki VEYA kapısının yerine de üç girişli tek bir VEYA kapısının kullanılabilmesidir.^{:s. 41} Huntington'ın birinci takımında bu yasalar aksiyom değil, aksiyomlardan türetilen teoremlerdir.^{:291, 294}

Etkisizlik yasası

${\displaystyle x+x=x}$

${\displaystyle x\cdot x=x}$

Bir değişken kendisiyle VE ya da VEYA işlemine girdiğinde değeri değişmez.^{:slayt 17} Yasa aynı terimin istenildiği kadar yinelenebileceğini de gösterir; ${\displaystyle x=x+x+x}$ ve ${\displaystyle x=x\cdot x\cdot x}$ eşitlikleri de geçerlidir. Değişkenin yerine 0 ve 1 konduğunda ${\displaystyle 0+0=0}$, ${\displaystyle 0\cdot 0=0}$ ve ${\displaystyle 1\cdot 1=1}$ gibi eşitlikler elde edilir. Çarpmadaki biçimi, Boole'un üs yasası ${\displaystyle x^{2}=x}$ ile aynıdır.^:16-17

Birim eleman ve yutma yasaları

${\displaystyle x+0=x\qquad x\cdot 1=x}$

${\displaystyle x+1=1\qquad x\cdot 0=0}$

0, VEYA işleminin; 1 ise VE işleminin birim elemanıdır. Bir değişkenle birim elemanın işlemi değişkenin kendisini verir. Öte yandan 1, VEYA işleminde; 0 ise VE işleminde yutan eleman gibi davranır. Hangi değişkenle işleme girerlerse girsinler sonuç kendileri olur.^{:slayt 17} Bu eşitliklerden ${\displaystyle x\cdot 1=x}$ ile ${\displaystyle x\cdot 0=0}$ VE işleminin, ${\displaystyle x+1=1}$ ile ${\displaystyle x+0=x}$ ise VEYA işleminin davranışını özetler. Shannon ${\displaystyle 1\cdot x=x}$ eşitliğini, x'in 0 ya da 1 olduğu iki durumu ayrı ayrı inceleyerek kanıtlamış, ${\displaystyle 0+x=x}$ eşitliğini ise ikilik ilkesiyle elde etmişti.

Tümleme yasası

${\displaystyle x+{\overline {x}}=1}$

${\displaystyle x\cdot {\overline {x}}=0}$

Bir değişkenle tümleyeninin VEYA işlemi her zaman 1, VE işlemi her zaman 0 verir.^{:slayt 18} Anahtar devrelerinde bunun karşılığı, bir anahtarın tersine çalışan bir anahtarla koşut bağlanmasının her zaman kapalı, seri bağlanmasının ise her zaman açık bir devre vermesidir; çünkü iki anahtardan biri her an kapalı, biri her an açıktır.^{:s. 40} Boole'un çelişmezlik ilkesi olarak yorumladığı ${\displaystyle x(1-x)=0}$ denklemi, bu yasanın VE biçimine karşılık gelir.^:34-35

Soğurma yasası

${\displaystyle x+x\cdot y=x}$

${\displaystyle x\cdot (x+y)=x}$

Huntington bu eşitliklere soğurma yasası (İngilizce: law of absorption) adını verir.^:293 Yasa, birim eleman, dağılma ve yutma yasalarından kolayca kanıtlanır:^{:slayt 27}

${\displaystyle x+xy=x\cdot 1+xy=x(1+y)=x\cdot 1=x}$

İkiz biçim de ${\displaystyle x(x+y)=xx+xy=x+xy=x}$ yoluyla elde edilir. Aynı yoldan türetilen yakın bir özdeşlik, ${\displaystyle x+{\overline {x}}y=x+y}$ eşitliğidir. ${\displaystyle xy+x{\overline {y}}=x}$ eşitliği ile ikizi ${\displaystyle (x+y)(x+{\overline {y}})=x}$ ise yalnız bir değişkende ayrılan iki terimi tek bir terimde toplar.^{:slayt 27} Bu eşitlik, çarpımlar toplamı biçimindeki ifadeleri kısaltmanın temel adımlarından biridir.^{:slayt 5}

Dağılma yasası

${\displaystyle x\cdot (y+z)=x\cdot y+x\cdot z}$

${\displaystyle x+y\cdot z=(x+y)\cdot (x+z)}$

İlk yasa sıradan cebirdeki dağılma yasasıyla aynıdır ve çarpımların açılmasına, ortak çarpanların parantez dışına alınmasına olanak verir. İkincisi sıradan cebirde geçerli değildir.^{:slayt 26} İkinci yasa öteki yasalardan şöyle türetilir:^{:slayt 26}

${\displaystyle {\begin{aligned}(x+y)(x+z)&=xx+xz+yx+yz\\&=x+xz+xy+yz\\&=x(1+z+y)+yz\\&=x+yz\end{aligned}}}$

Boole 1854'te ilk yasayı, "Avrupalı erkekler ve kadınlar" ifadesinin "Avrupalı erkekler ve Avrupalı kadınlar" ifadesiyle aynı anlama gelmesiyle örneklemişti.^:23

Çift tümleme yasası

${\displaystyle {\overline {\overline {x}}}=x}$

Bir değişkenin tümleyeninin tümleyeni değişkenin kendisidir.^{:slayt 18} Yasa yalnız tek değişkenler için değil her ifade için geçerlidir; örneğin ${\displaystyle {\overline {\overline {x+y}}}=x+y}$ olur.^{:slayt 18}

De Morgan yasaları

${\displaystyle {\overline {x+y}}={\overline {x}}\cdot {\overline {y}}}$

${\displaystyle {\overline {x\cdot y}}={\overline {x}}+{\overline {y}}}$

De Morgan yasaları bir toplamın ya da çarpımın tümleyenini, terimlerin tümleyenleri cinsinden verir. İki terim için bütün değer birleşimleri denenerek kolayca doğrulanır ve matematiksel tümevarımla herhangi sayıda terime genişletilir:

${\displaystyle {\overline {x_{1}+x_{2}+\cdots +x_{n}}}={\overline {x}}_{1}\cdot {\overline {x}}_{2}\cdots {\overline {x}}_{n}\qquad {\overline {x_{1}\cdot x_{2}\cdots x_{n}}}={\overline {x}}_{1}+{\overline {x}}_{2}+\cdots +{\overline {x}}_{n}}$

Huntington bu yasaları birinci aksiyom takımından teorem olarak türetmiş ve toplama ile çarpma arasındaki ikilik ilkesinin dayanağı saymıştı.^:294 Yasalar, VE DEĞİL ve VEYA DEĞİL kapılarıyla kurulan devrelerin çözümlenmesinde de kullanılır; çok girişli bir VE DEĞİL kapısının çıkışı girişlerin tümleyenlerinin VEYA'sına, çok girişli bir VEYA DEĞİL kapısının çıkışı ise tümleyenlerin VE'sine eşittir.^{:slayt 13}

Konsensüs teoremi

${\displaystyle x\cdot y+{\overline {x}}\cdot z+y\cdot z=x\cdot y+{\overline {x}}\cdot z}$

${\displaystyle (x+y)\cdot ({\overline {x}}+z)\cdot (y+z)=(x+y)\cdot ({\overline {x}}+z)}$

İlk eşitlikte ${\displaystyle y\cdot z}$ terimi, ${\displaystyle x\cdot y}$ ile ${\displaystyle {\overline {x}}\cdot z}$ terimlerinin konsensüsüdür ve ifadeden atılabilir; ikinci eşitlik bunun ikizidir. Shannon da bu iki eşitliği 1938'de röle devrelerini sadeleştirmede yararlı teoremler arasında saymıştı.

Aksiyomlardan kanıt

Boole cebrinin yasaları aksiyomlardan adım adım türetilebilir. Huntington'ın etkisizlik yasası için verdiği kanıt, birim eleman, tümleyen ve dağılma aksiyomlarını sırayla kullanır:^:294

${\displaystyle a+a=(a+a)\cdot 1=(a+a)(a+{\overline {a}})=a+a{\overline {a}}=a+0=a}$

Burada ilk adımda ${\displaystyle a\cdot 1=a}$ birim eleman aksiyomu, ikinci adımda ${\displaystyle a+{\overline {a}}=1}$ tümleyen aksiyomu, üçüncü adımda VEYA'nın VE üzerine dağılma aksiyomu, dördüncü adımda ${\displaystyle a{\overline {a}}=0}$ ve son adımda ${\displaystyle a+0=a}$ kullanılır. Ötekiler de benzer biçimde kanıtlanır.^:294

Doğruluk tablosuyla kanıt

${\displaystyle xy+z=(x+z)(y+z)}$ özdeşliğinin doğruluk tablosuyla kanıtı. Son iki sütun sekiz satırın hepsinde aynıdır.

x	y	z	xy + z	(x + z)(y + z)
0	0	0	0	0
0	0	1	1	1
0	1	0	0	0
0	1	1	1	1
1	0	0	0	0
1	0	1	1	1
1	1	0	1	1
1	1	1	1	1

İki değerli cebirde her değişken yalnız 0 ya da 1 olabildiği için bir özdeşlik, değişkenlerin bütün değer birleşimlerinde iki yanın aynı değeri aldığı gösterilerek de kanıtlanabilir. Shannon bu yönteme tam tümevarım (İngilizce: perfect induction) adını verdi ve teoremlerin önceki teoremlerden daha zarif biçimde kanıtlanabileceğini kabul etmekle birlikte, bu yöntemin evrenselliği nedeniyle yeğlenmesi gerektiğini yazdı. Doğruluk tablosu bir Boole işlevini tek türlü belirlediği için iki işlevin eşdeğer olduğunu göstermenin de bir yoludur.^{:slayt 15-16} Örneğin ${\displaystyle xy+z=(x+z)(y+z)}$ özdeşliği, üç değişkenin sekiz değer birleşiminin hepsinde iki yan hesaplanarak doğrulanır.^{:slayt 16}

Bu yöntem yalnız iki elemanlı cebir için değil, bütün Boole cebirleri için geçerli özdeşlikleri kanıtlamaya da yeter. Löwenheim-Müller doğrulama teoremi adı verilen sonuca göre Boole ifadeleriyle yazılmış bir özdeşlik, ancak ve ancak iki elemanlı Boole cebrinde geçerliyse her Boole cebrinde geçerlidir.^:44 Teorem yalnız özdeşlikler için geçerlidir. Örneğin "${\displaystyle x+y=1}$ ise x ya da y 1'dir" önermesi iki elemanlı cebirde doğrudur ama daha büyük Boole cebirlerinde doğru değildir.^{:27, 44}

İki değişkenli işlevler

İki değişkenli bir işlevin doğruluk tablosu dört satırlıdır ve çıkış sütununa yazılabilecek 16 farklı dizilim, iki değişkenli 16 Boole işlevini verir. Bunların ikisi sabit, dördü tek bir değişkene ya da onun tümleyenine bağlıdır; geri kalanların çoğunun kendi adı vardır.^{:25, 45:slayt 7-10:slayt 13}

İki değişkenli 16 Boole işlevi. Çıkış sütunu sırasıyla (x, y) = (0, 0), (0, 1), (1, 0) ve (1, 1) girişlerindeki değerleri gösterir.

Çıkış	İfade	Adı
0000	${\displaystyle 0}$	sabit 0
0001	${\displaystyle xy}$	VE
0010	${\displaystyle x{\overline {y}}}$
0011	${\displaystyle x}$	x
0100	${\displaystyle {\overline {x}}y}$
0101	${\displaystyle y}$	y
0110	${\displaystyle x\oplus y=x{\overline {y}}+{\overline {x}}y}$	dışlayan VEYA
0111	${\displaystyle x+y}$	VEYA
1000	${\displaystyle {\overline {x+y}}}$	VEYA DEĞİL
1001	${\displaystyle xy+{\overline {x}}\,{\overline {y}}}$	eşdeğerlik (dışlayan VEYA DEĞİL)
1010	${\displaystyle {\overline {y}}}$	y'nin tümleyeni
1011	${\displaystyle x+{\overline {y}}}$	içerme (${\displaystyle y\rightarrow x}$)
1100	${\displaystyle {\overline {x}}}$	x'in tümleyeni
1101	${\displaystyle {\overline {x}}+y}$	içerme (${\displaystyle x\rightarrow y}$)
1110	${\displaystyle {\overline {xy}}}$	VE DEĞİL
1111	${\displaystyle 1}$	sabit 1

İçerme işlevi önermeler mantığındaki "x ise y" koşullu önermesine karşılık gelir. Brown, koşullu önermenin bütün doğruluk değerleri için ${\displaystyle \lnot P\lor Q}$ önermesiyle aynı değeri alacak biçimde tanımlandığını belirtir.^:25

Dışlayan VEYA ve eşdeğerlik

Dışlayan VEYA işlemi ${\displaystyle x\oplus y={\overline {x}}y+x{\overline {y}}=(x+y)({\overline {x}}+{\overline {y}})}$ biçiminde yazılır. İşlem değişme ve birleşme yasalarına uyar, VE işlemi de onun üzerine dağılır. Ayrıca ${\displaystyle x\oplus 0=x}$, ${\displaystyle x\oplus 1={\overline {x}}}$, ${\displaystyle x\oplus x=0}$ ve ${\displaystyle x\oplus {\overline {x}}=1}$ özdeşlikleri geçerlidir.^{:slayt 8} Dışlayan VEYA'nın tümleyeni, ${\displaystyle {\overline {x\oplus y}}=x\oplus {\overline {y}}={\overline {x}}\oplus y=xy+{\overline {x}}\,{\overline {y}}}$ biçiminde yazılan eşdeğerlik işlemidir. Eşdeğerlik, iki değişken aynı değeri aldığında 1 verir.^{:slayt 8-11}

Üç değişkenin dışlayan VEYA'sı ${\displaystyle x\oplus y\oplus z}$, girişlerdeki 1'lerin sayısı tek olduğunda 1 değerini alan eşlik işlevidir.^{:slayt 9} VE işlemi dışlayan VEYA üzerine dağılır ve ${\displaystyle x(y\oplus z)=xy\oplus xz}$ olur. VEYA işlemi için bunun karşılığı geçerli değildir; ${\displaystyle x+(y\oplus z)}$ ile ${\displaystyle (x+y)\oplus (x+z)}$ genel olarak eşit değildir.^{:slayt 9}

Çarpımlar toplamı ve toplamlar çarpımı

Değişkenlerden ya da tümleyenlerinden oluşan çarpım terimlerinin VEYA işlemiyle birleştirilmesine çarpımlar toplamı (İngilizce: sum of products) denir. ${\displaystyle a{\overline {b}}c+{\overline {a}}bd}$ bu biçimdedir, ${\displaystyle a(b+c)+{\overline {a}}bd}$ ise değildir. Mantıkta aynı biçime ayrık normal biçim (İngilizce: disjunctive normal form) adı verilir. Değişkenlerden ya da tümleyenlerinden oluşan toplam terimlerinin VE işlemiyle birleştirilmesine ise toplamlar çarpımı (İngilizce: product of sums) ya da mantıktaki adıyla birleşim normal biçimi (İngilizce: conjunctive normal form) denir. Her Boole işlevi bu iki biçimden biriyle yazılabilir.^{:slayt 29}

Bu biçimler iki düzeyli devrelere doğrudan karşılık gelir. Çarpımlar toplamı, birinci katı VE kapılarından, ikinci katı bir VEYA kapısından oluşan bir devreyle; toplamlar çarpımı ise önce VEYA, sonra VE kapılarıyla gerçekleştirilir. İfadedeki terim ve değişken sayısının azalması, devredeki kapı ve kapı girişi sayısının azalması demektir.^{:slayt 5} Monk, bir Boole cebrinde sonlu sayıda elemanın ürettiği alt cebrin her elemanının bu elemanlardan ve tümleyenlerinden kurulan çarpımların toplamı olarak yazılabildiğini ve bunun önermeler mantığındaki ayrık normal biçim teoreminin cebirsel ifadesi olduğunu belirtir.

Mini terimler ve maksi terimler

n değişkenin her birinin ya kendisi ya da tümleyeni olarak tam bir kez geçtiği çarpım terimine mini terim (İngilizce: minterm), toplam terimine ise maksi terim (İngilizce: maxterm) denir. Doğruluk tablosunun bir satırına ait mini terimde, o satırda 1 olan değişken kendi hâliyle, 0 olan değişken tümleyeniyle yer alır. Maksi terimde ise tersi yapılır. Mini terim, ait olduğu satırda 1, öteki bütün satırlarda 0 değerini alır; maksi terim ise ait olduğu satırda 0 değerini alır.^{:slayt 9} Satır numarası, değişkenlerin değerlerinin oluşturduğu ikili sayıdır ve mini terimler m_i, maksi terimler M_i biçiminde numaralanır. Aynı satırın mini terimiyle maksi terimi birbirinin tümleyenidir ve ${\displaystyle {\overline {m_{i}}}=M_{i}}$ olur.^{:slayt 9}

Üç değişkenin mini terimleri ve maksi terimleri

Satır	x y z	Mini terim	Maksi terim
0	000	${\displaystyle m_{0}={\overline {x}}\,{\overline {y}}\,{\overline {z}}}$	${\displaystyle M_{0}=x+y+z}$
1	001	${\displaystyle m_{1}={\overline {x}}\,{\overline {y}}\,z}$	${\displaystyle M_{1}=x+y+{\overline {z}}}$
2	010	${\displaystyle m_{2}={\overline {x}}\,y\,{\overline {z}}}$	${\displaystyle M_{2}=x+{\overline {y}}+z}$
3	011	${\displaystyle m_{3}={\overline {x}}\,y\,z}$	${\displaystyle M_{3}=x+{\overline {y}}+{\overline {z}}}$
4	100	${\displaystyle m_{4}=x\,{\overline {y}}\,{\overline {z}}}$	${\displaystyle M_{4}={\overline {x}}+y+z}$
5	101	${\displaystyle m_{5}=x\,{\overline {y}}\,z}$	${\displaystyle M_{5}={\overline {x}}+y+{\overline {z}}}$
6	110	${\displaystyle m_{6}=x\,y\,{\overline {z}}}$	${\displaystyle M_{6}={\overline {x}}+{\overline {y}}+z}$
7	111	${\displaystyle m_{7}=x\,y\,z}$	${\displaystyle M_{7}={\overline {x}}+{\overline {y}}+{\overline {z}}}$

Mini terim ve maksi terim açılımları

Bir işlev, 1 değerini aldığı satırların mini terimlerinin toplamı olarak yazılabilir. Bu yazılışa mini terim açılımı ya da standart çarpımlar toplamı denir. Örneğin A, B ve C girişlerinin oluşturduğu ${\displaystyle N=4A+2B+C}$ ikili sayısı 3 ya da daha büyük olduğunda 1, öteki durumlarda 0 veren işlev, doğruluk tablosunda 1 olduğu beş satırdan

${\displaystyle f={\overline {A}}BC+A{\overline {B}}\,{\overline {C}}+A{\overline {B}}C+AB{\overline {C}}+ABC=m_{3}+m_{4}+m_{5}+m_{6}+m_{7}=\textstyle \sum m(3,4,5,6,7)}$

biçiminde yazılır. Aynı işlev, 0 olduğu satırların maksi terimlerinin çarpımı olarak da yazılabilir. Standart toplamlar çarpımı da denen bu maksi terim açılımı ${\displaystyle f=(A+B+C)(A+B+{\overline {C}})(A+{\overline {B}}+C)=\textstyle \prod M(0,1,2)}$ biçimindedir. İfade sadeleştirildiğinde ${\displaystyle f=A+BC}$ elde edilir.^{:slayt 7-10}

Mini terim ve maksi terim açılımları kurallı (İngilizce: canonical, kanonik diye de anılır) gösterimlerdir. İki işlev, ancak ve ancak mini terim ve maksi terim açılımları aynıysa eşdeğerdir. Bir işlevin tümleyeninin mini terimleri, işlevin açılımında yer almayan mini terimlerdir; örnekteki işlevin tümleyeni ${\displaystyle {\overline {f}}=\textstyle \sum m(0,1,2)}$ olur.^{:slayt 11-12}

Boole'un açılım teoremi

Bir işlevin kurallı biçime getirilmesi, Boole'un açılım teoremine dayanır:^:36

${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})={\overline {x}}_{1}\cdot f(0,x_{2},\ldots ,x_{n})+x_{1}\cdot f(1,x_{2},\ldots ,x_{n})}$

Rosenbloom'un Boole cebrinin temel teoremi diye andığı bu açılım, Boole'un Laws of Thought kitabının beşinci bölümünde ele alınmıştı. Brown, mini terim kurallı biçiminin de ilk kez Boole'un bu kitabının beşinci bölümünde tartışıldığını belirtir.^{:36, 39} Shannon 1938'de açılımı ikiziyle birlikte verdi:

${\displaystyle f(X_{1},\ldots ,X_{n})=[\,f(0,X_{2},\ldots ,X_{n})+X_{1}\,]\cdot [\,f(1,X_{2},\ldots ,X_{n})+{\overline {X}}_{1}\,]}$

Shannon bu açılımları sonsuz küçükler hesabındaki Taylor açılımına benzetti. Açılım bütün değişkenler için yinelendiğinde işlev, katsayıları işlevin o girişteki değeri olan mini terimlerin toplamı olarak yazılır. Shannon'ın dikkat çektiği gibi bir işlev bir değişkene göre açıldığında o değişken devrede en çok iki kez, bir kez normalde açık, bir kez de normalde kapalı bir röle kontağı olarak yer alır.

Mini terim biçiminin dışında başka kurallı biçimler de vardır. Blake'in kurallı biçimi bir işlevin bütün asal kapsayanlarının toplamıdır.^:74 Zhegalkin'e dayanan ve Amerika Birleşik Devletleri'nde Reed-Muller biçimi diye bilinen kurallı biçim ise Boole halkası üzerine kuruludur.^:39

Cebirsel sadeleştirme

Temel yasalar kullanılarak bir ifade adım adım kısaltılabilir. Yalnız bir değişkende ayrılan iki terim ${\displaystyle xy+x{\overline {y}}=x}$ eşitliğiyle birleştirilir, fazla terimler ise konsensüs teoremiyle atılır.^{:slayt 5} Örneğin

${\displaystyle {\overline {A}}BC+A{\overline {B}}\,{\overline {C}}+A{\overline {B}}C+AB{\overline {C}}+ABC}$

ifadesinde ${\displaystyle A{\overline {B}}\,{\overline {C}}+A{\overline {B}}C=A{\overline {B}}}$ ve ${\displaystyle AB{\overline {C}}+ABC=AB}$ olur. ${\displaystyle A{\overline {B}}+AB=A}$ olduğundan ifade ${\displaystyle {\overline {A}}BC+A}$ biçimine, oradan da ${\displaystyle x+{\overline {x}}y=x+y}$ özdeşliğiyle ${\displaystyle A+BC}$ biçimine iner.^{:slayt 7:slayt 27} Cebirsel sadeleştirme sistematik bir yöntem değildir ve ulaşılan ifadenin en yalın biçim olup olmadığını denetlemek de güçtür.^{:slayt 4}

Karnaugh haritası

Karnaugh 1953'te, n değişkenin ${\displaystyle 2^{n}}$ giriş durumunu kareler biçiminde gösteren ve yan yana iki karenin yalnız bir değişkenin değerinde ayrılacağı biçimde düzenlenen harita yöntemini yayımladı. Dört değişkenli haritada satır ve sütunların karşılıklı uçları da komşu sayılır; Karnaugh bunu haritanın bir simidin yüzeyine çizilmesine benzetir.^:593 Karnaugh'a göre Harvard Hesaplama Laboratuvarı'nda geliştirilen sadeleştirme çizelgesinin en büyük sakıncası, beş değişkenli sorunlarda 1.024, altı değişkenli sorunlarda 4.096 girişin yazılıp izlenmesini gerektirmesiydi. Veitch'in önerdiği yöntem ise benzer sonuçları yalnız ${\displaystyle 2^{n}}$ girişli bir diziden daha hızlı elde ediyordu. Karnaugh'un harita yöntemi, Veitch'in çizelgelerinin yeniden düzenlenmesini, üç boyutlu dizilere genişletilmesini ve diyot ile röle devreleri için özel teknikleri içeriyordu.^:593 Karnaugh haritası genellikle beş ya da daha az değişkenli işlevlerde kullanılır.^{:slayt 4}

Quine-McCluskey algoritması

Bir işlevin kapsayanı, işlevin 0 olduğu hiçbir mini terimi içermeyen bir çarpım terimidir. Başka hiçbir kapsayanın içinde kalmayan kapsayana asal kapsayan, başka hiçbir asal kapsayanın kapsamadığı bir mini terimi içeren asal kapsayana da temel asal kapsayan denir.^:13 Bir çarpım teriminin maliyeti, onu içine alan bir çarpım teriminin maliyetinden düşük olmadıkça, yalnız asal kapsayanlardan oluşan en yalın bir çözüm her zaman vardır; bu yüzden aramada asal kapsayanlarla yetinilebilir.^:15

En yalın iki düzeyli biçimi bulan ilk algoritmaları Quine önermiş, McCluskey geliştirmiştir. Bu yöntemler önce işlevin bütün asal kapsayanlarını üretir, sonra işlevi kapsayan en küçük asal kapsayan kümesini seçer. Rudell'e göre bu kesin yöntemler on girişten çok olan birçok sorunu çözemez.^{:4, 15} Bir işlevin asal kapsayanlarının sayısı, en küçük çözümdeki terim sayısına göre üstel olarak büyüyebilir. En küçük kapsama sorunu NP-tam olduğundan bu eniyileme sorununu verimli olarak çözen bir algoritma da bilinmemektedir.^:15-16

Sezgisel sadeleştiriciler

Quine-McCluskey gibi kesin yöntemlerin sınırları, sonucun niteliğini güvence altına almayan ama büyük işlevleri de sadeleştirebilen yaklaşık yöntemlerin geliştirilmesine yol açtı. MINI programıyla başlayan bu yöntemler bir denklemler kümesini yinelemeli olarak iyileştirir. Bu yaklaşımın en bilinen örneği olan Espresso, elli girişli ve elli çıkışlı programlanabilir mantık dizilerinin eniyilenmesinde kullanılmıştır.^:4-5

Shannon'ın anahtarlama cebri

Shannon 1938'deki makalesinde yalnız röle kontakları ve anahtarlar içeren elektrik devrelerini ele aldı. Böyle bir devrede iki uç arasındaki yol her an ya açık (sonsuz empedans) ya da kapalıdır (sıfır empedans). Shannon her iki uçlu devreye, engel (İngilizce: hindrance) adını verdiği bir değişken karşılık getirdi. Kapalı devrenin engeli 0, açık devreninki 1'di. Toplama işaretini iki devrenin seri bağlanması, çarpma işaretini ise koşut bağlanması için kullandı ve bu seçimin engellerle yapılan işlemleri sıradan cebre çok benzettiğini belirtti. Bir rölenin normalde açık kontağının engeli X ise aynı rölenin normalde kapalı kontağının engeli X′ olur.

Shannon, toplama, çarpma ve tümleme işlemleriyle kurulan her ifadenin yalnız seri ve koşut bağlantılardan oluşan bir devreyi doğrudan gösterdiğini ve ifadedeki her harfin bir röle kontağına ya da bir anahtar ucuna karşılık geldiğini belirtti. Bu yüzden en az kontaklı devreyi bulmak, ifadeyi en az harfle yazılan biçime getirmek demektir. Makalede değişkenlerinin yer değiştirmesiyle değeri değişmeyen simetrik işlevler için genel bir devre kurma yöntemi de verdi. Bu yöntemin bir sonucu, bir lambayı n ayrı noktadan yakıp söndürmeye yarayan bilinen anahtar devresidir. Yöntemin uygulamaları arasında beş düğmeli bir elektrikli şifreli kilit ile iki ikili sayıyı yalnız röle ve anahtarlarla toplayan bir toplayıcı da vardı.

Ders kitaplarındaki gösterim

Bugünkü ders kitaplarında açık anahtara 0, kapalı anahtara 1 değeri verilir. Buna göre seri bağlı iki anahtar ancak ikisi de kapalıyken yolu tamamlar ve VE işlemine karşılık gelir; koşut bağlı iki anahtar ise biri kapalıyken yolu tamamlar ve VEYA işlemine karşılık gelir.^{:s. 36-37:slayt 19-20} Shannon da bir dipnotta, devrenin engeli yerine "devre açıktır" önermesiyle çalışılabileceğini ve bu durumda bütün simgelerin doğrudan önerme olarak yorumlanacağını belirtmişti. Aynı anahtar devreleri yasaların sezgisel bir açıklamasını da verir. Örneğin aynı değişkenle denetlenen iki anahtar her zaman birlikte açılıp kapandığı için, bu iki anahtarın seri ya da koşut bağlanması tek bir anahtarla aynı işi görür; bu, etkisizlik yasasının devredeki karşılığıdır.^{:s. 39:slayt 21}

Diyotlu kapılar

VE ve VEYA kapıları yalnız diyotlar ve dirençlerle de kurulabilir. Diyot, anot ucu katot ucundan daha artı gerilimdeyken doğru yönde kutuplanır ve kısa devre gibi davranır; ters yönde kutuplandığında ise bir yalıtkan gibi açık devre oluşturur. Kapı kurulurken her diyodun bir ucu bir dirençle besleme gerilimine ya da toprağa, öteki ucu ise mantık değerini taşıyan girişe bağlanır.^:1

Diyotlu VE kapısında diyotların katotları girişlere, anotları ortak çıkışa bağlıdır ve çıkış bir dirençle +5 V beslemeye bağlanır. Girişlerden biri 0 V olduğunda o girişin diyodu doğru yönde kutuplanır; akım dirençten ve bu diyottan geçer ve çıkış 0 V'a iner. Bütün girişler +5 V olduğunda diyotların hepsi ters yönde kutuplanır ve iletmez, çıkış da direnç üzerinden +5 V'ta kalır. Böylece çıkış yalnız bütün girişler 1 olduğunda 1, girişlerden herhangi biri 0 olduğunda 0 olur.^:3

Diyotlu VE kapısının gerilimlerle ve mantık değerleriyle doğruluk tablosu. 0 V mantık 0'a, +5 V mantık 1'e karşılık gelir. Gerilim Mantık değeri A B C A B C 0 V 0 V 0 V 0 0 0 0 V +5 V 0 V 0 1 0 +5 V 0 V 0 V 1 0 0 +5 V +5 V +5 V 1 1 1

Diyotlu VEYA kapısında ise diyotların anotları girişlere, katotları ortak çıkışa bağlıdır ve çıkış bir dirençle toprağa bağlanır. Girişlerden biri +5 V olduğunda o girişin diyodu doğru yönde kutuplanır ve iletir, +5 V çıkışta görülür. Bütün girişler 0 V olduğunda diyotların hiçbiri iletmez ve çıkış direnç üzerinden 0 V olur.^:4

Diyotlu VEYA kapısının gerilimlerle ve mantık değerleriyle doğruluk tablosu. Gerilim Mantık değeri A B C A B C 0 V 0 V 0 V 0 0 0 0 V +5 V +5 V 0 1 1 +5 V 0 V +5 V 1 0 1 +5 V +5 V +5 V 1 1 1

Bu örneklerde 0 V mantık 0'ı, +5 V mantık 1'i gösterir. Gerçek kapılarda her mantık değerine bir gerilim aralığı karşılık gelir. Örneğin TTL ailesinden SN7400 yongasında, çıkışın 1 sayılması için gerilimin en az 2,4 V, 0 sayılması için en çok 0,4 V olması gerekir.^:6

Birleşik devre tasarımı

Çıkışları yalnız o andaki girişlerine bağlı olan devrelere birleşik devre (İngilizce: combinational circuit) denir. Tek çıkışlı bir birleşik devre tasarlanırken önce istenen davranış, sözel tanımdaki her doğru ya da yanlış olabilen öbeğe bir Boole değişkeni karşılık getirilerek bir anahtarlama işleviyle ifade edilir. Sonra işlev sadeleştirilir ve eldeki mantık öğeleriyle gerçekleştirilir.^{:slayt 4} İkili toplayıcı ve çıkarıcılar bu yolla tasarlanan birleşik devrelerin başlıca örnekleridir.^{:slayt 3}

Bazı giriş birleşimleri hiç oluşmuyorsa ya da o girişlerde çıkışın değeri önemli değilse işlev eksik belirlenmiş olur. Bu girişlerdeki çıkış değeri önemsenmeyen durum (İngilizce: don't care) olarak işaretlenir ve 0 ya da 1 olabilir.^{:slayt 22}

Önermeler mantığı

Önerme, doğru ya da yanlış olan ama ikisi birden olamayan bir bildirimdir. Önermeler bağlaşım (VE), ayrıklık (VEYA) ve değilleme (DEĞİL) işlemleriyle birleştirilir. n değişkenli önerme işlevlerinin kümesi, ayrıklık ve bağlaşım işlemleriyle, her zaman yanlış olan çelişki 0 ve her zaman doğru olan totoloji 1 alınarak bir Boole cebri oluşturur.^:25 Peirce'in kapsanma bağıntısı da önermeler arasında gerektirme olarak yorumlanabilir.

Önermeler mantığının Boole cebriyle ilişkisi Lindenbaum-Tarski cebirleriyle de kurulur. Bir önermeler mantığı dilinde, verilen bir önermeler kümesine göre birbirine denk olan önermeler denklik sınıflarına ayrılır. Bu sınıflar, toplamanın ayrıklığa, çarpmanın bağlaşıma, tümlemenin değillemeye karşılık geldiği bir Boole cebri oluşturur ve her Boole cebri bu biçimde kurulan bir cebre izomorftur. Aynı yapı birinci dereceden kuramlar için de kurulabilir. Monk, bu yolla Alfred Tarski'nin de adını taşıyan Lindenbaum-Tarski cebirlerinin önemli kuramları betimlemekte kullanıldığını belirtir.

Küme cebri

Bir S kümesinin bütün altkümelerinin oluşturduğu kuvvet kümesi, birleşim ve kesişim işlemleriyle, boş küme 0 ve S'nin kendisi 1 alınarak bir Boole cebri oluşturur.^:24-25 Bu cebirde Boole cebrinin sıra bağıntısı kümelerin içerilme bağıntısına karşılık gelir. Boole'un, Lewis Carroll'ın ve John Venn'in de aralarında olduğu 19. yüzyıl mantıkçılarının mantık cebri sınıflar üzerine kuruluydu. Carroll'ın "kümes hayvanlarım" ya da "timsahla başa çıkabilen şeyler" gibi sınıflar içeren soruları bugün de sevilen mantık bulmacalarıdır.^:25

Bir Boole işlevi, 1 değerini aldığı mini terimlerin kümesiyle özdeşleştirilebilir. Bu bakışla kümelerin kesişimi işlevlerin VE'sine, birleşimi VEYA'sına, tümleyeni de işlevin tümleyenine karşılık gelir; bir kümenin elemanları ikili kodlarla gösterildiğinde küme işlemleri Boole işlemleriyle yapılabilir.^{:slayt 18-20}

Küme işlemleri şemalarla da gösterilir. Huntington düzlem bölgeleriyle kurduğu örnekte okuru Euler şemalarına gönderir.^:292 Venn şemalarında iki kümeyi gösteren temel şema kümeler arasında herhangi bir bağıntı bildirmez; Euler şemalarından temel farkı budur. Evrensel önermeler Venn'in 1881'de önerdiği gibi ilgili bölgeler taranarak gösterilir ve taranan bölge boş küme olarak yorumlanabilir.

Tanım

Evrensel cebirde Boole cebri, iki ikili işlem, tümleme denen bir tekli işlem ve iki sabitle donatılmış ${\displaystyle \langle B,\lor ,\land ,{}',0,1\rangle }$ biçiminde bir cebirdir. Bu cebirde ${\displaystyle \langle B,\lor ,\land \rangle }$ dağılımlı bir kafestir ve

${\displaystyle x\land 0=0,\qquad x\lor 1=1,\qquad x\land x'=0,\qquad x\lor x'=1}$

özdeşlikleri sağlanır.^{:25, 116-117} Tanım yalnız özdeşliklerden oluştuğu için Boole cebirleri, denklemlerle tanımlanabilen bir cebir sınıfı oluşturur.^:117 Sınırlı ve dağılımlı bir kafeste bir elemanın en çok bir tümleyeni olabilir ve her elemanı tümleyenli olan dağılımlı kafesler, Boole cebirleriyle aynı yapıyı taşır.^:27 Monk ise Boole cebrini, toplama ve çarpmanın değişme, birleşme ve iki yönlü dağılma yasalarına, soğurma yasalarına ve tümleme yasalarına uyduğu bir yapı olarak tanımlar.

Örnekler

Boole cebirlerinin temel örneği, bir X kümesinin birleşim, kesişim ve X'e göre tümleme işlemleri altında kapalı olan, boş kümeyi ve X'i içeren altküme aileleridir. İki elemanlı Boole cebri bu örneğin özel bir durumudur ve X tek elemanlı alındığında elde edilir. Brown'un saydığı örnekler arasında altkümeler ve önerme işlevlerinin yanında aritmetik Boole cebirleri de vardır. Örneğin 30'un bölenlerinden oluşan {1, 2, 3, 5, 6, 10, 15, 30} kümesi, en küçük ortak kat toplama, en büyük ortak bölen çarpma yerine alındığında bir Boole cebri oluşturur. Bu cebirde 1 sayısı 0 elemanının, 30 sayısı ise 1 elemanının yerini tutar; ${\displaystyle 6+15=30}$ ve ${\displaystyle 6\cdot 15=3}$ olur.^:26 Brown, bu tür aritmetik Boole cebirlerine ilk kez Bunitskiy'nin dikkat çektiğini belirtir.^:26

Sıra bağıntısı

Her Boole cebrinde, ${\displaystyle x+y=y}$ olduğunda ${\displaystyle x\leq y}$ diye tanımlanan doğal bir kısmi sıra bağıntısı vardır. Küme örneğinde bu bağıntı içerilmeye (${\displaystyle \subseteq }$) karşılık gelir. Bu sıraya göre ${\displaystyle x+y}$, x ile y'nin en küçük üst sınırı, ${\displaystyle x\cdot y}$ ise en büyük alt sınırıdır. Huntington da sıra bağıntısını ${\displaystyle a+b=b}$, ${\displaystyle a\cdot b=a}$, ${\displaystyle {\overline {a}}+b=1}$ ya da ${\displaystyle a\cdot {\overline {b}}=0}$ koşullarından biriyle tanımlamış ve bu tanımların birbirine denk olduğunu belirtmişti.^:294 Bir eleman kümesinin en küçük üst sınırı ve en büyük alt sınırı her zaman var olmayabilir. Bu sınırlar her alt küme için var olan Boole cebirlerine tam Boole cebri denir.

Atomlar ve sonlu Boole cebirleri

Bir Boole cebrinde 0'dan farklı olan ve kendisiyle 0 arasında başka hiçbir eleman olmayan elemana atom denir. Sıfırdan farklı her elemanının altında bir atom olan Boole cebrine atomlu Boole cebri denir. Sonlu Boole cebirlerinin hepsi atomludur; birçok sonsuz Boole cebri de atomludur. Hiç atomu olmayan atomsuz Boole cebirleri de vardır; örneğin sonsuz her serbest Boole cebri atomsuzdur.

Huntington 1904'te sonlu her Boole cebrinin eleman sayısının bir m doğal sayısı için ${\displaystyle 2^{m}}$ olduğunu kanıtladı. Böyle bir cebirde ikişer ikişer çarpımları 0, toplamları 1 olan ve indirgenemez dediği m eleman vardır. 0 dışındaki her eleman bunların bir bölümünün toplamıdır. Huntington ayrıca eleman sayısı 2'nin bir kuvveti olan her kümenin, işlemleri uygun biçimde tanımlanarak özünde tek bir yolla Boole cebrine dönüştürülebileceğini gösterdi.^:309 Brown'un aktardığı teoreme göre sonlu her Boole cebri, sonlu bir kümenin bütün altkümelerinden oluşan Boole cebrine izomorftur. Bu yüzden sonlu Boole cebirlerinde, soyut işlemler yerine birleşim, kesişim ve tümleme gibi somut küme işlemleriyle akıl yürütmek genelliği bozmaz.^:27-28

Boole halkaları

Bir Boole cebrinde ${\displaystyle x\oplus y=x\cdot {\overline {y}}+y\cdot {\overline {x}}}$ işlemi tanımlandığında, ${\displaystyle \oplus }$ toplama ve ${\displaystyle \cdot }$ çarpma olmak üzere cebir, her elemanın karesinin kendisine eşit olduğu birimli bir halka oluşturur. Tersine böyle bir halkada ${\displaystyle x+y=x\oplus y\oplus xy}$ ve ${\displaystyle {\overline {x}}=1\oplus x}$ tanımlarıyla bir Boole cebri elde edilir. Bu iki dönüşüm birbirinin tersidir; bu yüzden Boole cebirleri kuramı ile her elemanı kendi karesine eşit olan birimli halkalar kuramı tanımca denktir. Bu bağ, Boole cebirlerinin incelenmesini cebrin köklü alanlarından biri olan halka kuramıyla ilişkilendirir.

Stone 1936'da bu halkalara Boole halkası adını verdi ve halka toplamasının kümeler arasında ikisinden yalnız birine ait olan elemanlardan oluşan simetrik farka, halka çarpmasının da kesişime karşılık geldiğini belirtti. Stone, birimi olmayan halkaları da kapsamak için incelemesini birim elemanı olmayabilen bu genelleştirilmiş Boole cebirleri üzerine kurdu.^:38 Boole cebirlerindeki ideal kavramı halka kuramındaki ideal kavramıyla aynıdır. Halkalarda karşılığı olmayan ikiz kavram ise filtredir; bir filtre 1'i içeren, çarpma altında kapalı ve kendi elemanlarından büyük elemanları da içeren bir alt kümedir. Stone, Boole cebirleriyle bu halkaların özdeşliği konusunda Zhegalkin'in 1928 tarihli bir çalışmasını da kaynak gösterir.^:38

Stone gösterim teoremi

Stone 1936'daki makalesinde verilen bir Boole cebrini sınıflar cebirleriyle gösterme sorununu ele aldı. Her Boole cebrinin ona izomorf bir sınıflar cebriyle gösterilebildiğini kanıtladı ve bu sonucu, her soyut grubun ona izomorf bir permütasyon grubuyla gösterilebileceğini söyleyen teoremin tam bir benzeri olarak niteledi.^:37-38 Stone'a göre bu sonuçlar gruplardaki karşılıklarından çok daha çetindi. Gösterimdeki sınıfların elemanları cebrin kendi elemanları değil, cebirdeki asal idealler olarak alınmak zorundaydı. Asal ideallerin varlığı da genel durumda ancak Zermelo varsayımına başvurularak kanıtlanabiliyordu.^:38

Monk teoremi filtreler üzerinden anlatır. 0'ı içermeyen ve her a elemanı için a'yı ya da tümleyenini içeren filtreye ultrafiltre denir. A Boole cebrindeki her a elemanına, a'yı içeren bütün ultrafiltrelerin kümesi karşılık getirilir. Bu eşleme A'yı, A üzerindeki bütün ultrafiltrelerin kümesinin altkümelerinden oluşan bir Boole cebrine izomorf olarak taşır. Bu kümeler bir topolojinin tabanı olarak alındığında ultrafiltreler kümesi tamamen bağlantısız, tıkız bir Hausdorff uzayı olur. Böylece Boole cebirleri sınıfı ile bu tür uzaylar sınıfı arasında birebir bir karşılık kurulur. Burris ve Sankappanavar, Stone'un 1930'ların ortasında bulduğu Boole cebirleri ile Boole uzayları arasındaki bu ikiliği büyük bir atılım olarak niteler. Her Boole cebri bir kümeler cebriyle gösterilebildiği için Boole cebirleri sınıfı bazen yalın sayılır; oysa karar verilebilirlik, katılık ve doğrudan çarpımlar gibi konularda elde edilen bazı sonuçlar alanın en zorlu sonuçları arasındadır.^:116

Sonlu durumda teorem çok daha yalındır ve her sonlu Boole cebrinin sonlu bir kümenin bütün altkümelerinden oluşan cebre izomorf olduğunu söyler. Stone sonsuz Boole cebirlerinin de birer kümeler cebrine izomorf olduğunu, ancak bunun bir evrensel kümenin bütün altkümelerinden oluşan cebir olmayabileceğini göstermiştir.^:27 Tarski'nin temel bir sonucuna göre Boole cebirlerinin birinci dereceden kuramı karar verilebilirdir. Belirli bir ideali olan Boole cebirlerinin kuramı da karar verilebilirdir, buna karşılık belirli bir alt cebri olan Boole cebirlerinin kuramı karar verilemezdir.

Boole veri türü

C ve Python gibi programlama dillerinde yalnız doğru ve yanlış değerlerini alan bir Boole veri türü vardır. C dilinin 2011 tarihli standardının taslağına göre _Bool türündeki bir nesne 0 ve 1 değerlerini saklayabilecek büyüklüktedir. <stdbool.h> başlık dosyası bool adını _Bool türüne, true adını 1 tamsayı sabitine, false adını da 0 tamsayı sabitine karşılık getirir.^{:§ 6.2.5, 7.18} Python'da bool türü tamsayı türü int'in bir alt sınıfıdır ve sayısal işlemlerin çoğunda False ile True değerleri 0 ve 1 tamsayıları gibi davranır; belgeler buna güvenmek yerine açık dönüşüm yapılmasını önerir.

Python'da Boole işlemlerinin ve denetim deyimlerinin bağlamında False, None, bütün sayısal türlerin sıfırı ve boş dizgiler ile boş kaplar yanlış sayılır; öteki bütün değerler doğrudur. C dilinde de mantıksal işleçler işlenenlerinin 0'a eşit olup olmadığına bakar.^{:§ 6.5.3.3, 6.5.13-6.5.14}

Mantıksal işleçler

C dilinde && işleci iki işleneni de 0'dan farklıysa 1, öteki durumlarda 0 verir. || işleci işlenenlerinden biri 0'dan farklıysa 1 verir. ! işlecinin sonucu, işleneni 0'dan farklıysa 0, 0'a eşitse 1'dir; !E ifadesi (0 == E) ifadesine denktir. Üç işlecin de sonucu int türündedir.^{:§ 6.5.3.3, 6.5.13-6.5.14} Python'da not işleci işleneni yanlışsa True, doğruysa False verir. and ile or ise sonucu False ya da True ile sınırlamaz, son değerlendirilen işleneni döndürür. Örneğin s boş bir dizgiyse s or 'foo' ifadesi 'foo' değerini verir.

Kısa devre değerlendirme

C ve Python'da mantıksal VE ile VEYA işleçleri işlenenlerini soldan sağa değerlendirir ve sonuç ilk işlenenden belli oluyorsa ikinci işleneni değerlendirmez. Bu davranışa kısa devre değerlendirme (İngilizce: short-circuit evaluation) denir. C standardına göre && işleci, bit düzeyindeki & işlecinden farklı olarak soldan sağa değerlendirmeyi güvence altına alır ve ilk işlenen 0'a eşitse ikinci işlenen hiç değerlendirilmez. || işlecinde de ilk işlenen 0'dan farklıysa ikinci işlenen değerlendirilmez.^{:§ 6.5.13-6.5.14} Örneğin b != 0 && a / b > 1 ifadesinde b sıfırsa bölme işlemi hiç yapılmaz. Python'da da x and y ifadesinde önce x değerlendirilir ve x yanlışsa y'ye bakılmaz; x or y ifadesinde x doğruysa y değerlendirilmez.

Her dil bu güvenceyi vermez. PostgreSQL belgeleri, SQL'deki AND ve OR işleçlerinin değişme özelliği taşıdığını, ancak sol işlenenin sağ işlenenden önce değerlendirileceğinin güvence altında olmadığını belirtir.

Bit düzeyindeki işlemler

Boole işlemleri bir sayının bütün bitlerine tek tek de uygulanabilir. C dilinde bu işlemler & (VE), | (VEYA), ^ (dışlayan VEYA) ve ~ (tümleme) işleçleriyle yapılır.^{:§ 6.5.3.3, 6.5.10-6.5.12} Python'da tamsayılar üzerindeki bit düzeyindeki işlemler, sayılar sonsuz sayıda işaret biti taşıyan ikiye tümleyen gösterimindeymiş gibi hesaplanır. Bu işleçler iki bool değerine uygulandığında mantıksal VE, VEYA ve dışlayan VEYA işlemlerine denk bir bool değeri verir; ancak bu amaçla mantıksal işleçlerin kullanılması önerilir. bool değerlerine ~ işlecinin uygulanması Python 3.12'den bu yana önerilmemektedir ve belgelere göre Python 3.16'da hata verecektir.

Boole sorguları

Bilgi erişimde Boole erişim modeli, sorguların terimlerin VE, VEYA ve DEĞİL işleçleriyle birleştirilmesinden oluşan Boole ifadeleri olarak yazıldığı bir modeldir. Model her belgeyi bir sözcükler kümesi olarak ele alır.^:4 Manning, Raghavan ve Schütze, Shakespeare'in oyunları üzerinde Brutus AND Caesar AND NOT Calpurnia sorgusunu örnek verir. Her terim için, terimin hangi oyunlarda geçtiğini 1 ve 0'larla gösteren bir vektör tutulur. Calpurnia vektörü tümlenip üç vektöre bit düzeyinde VE işlemi uygulandığında 110100 AND 110111 AND 101111 = 100100 elde edilir ve sorguya Antonius ve Kleopatra ve Hamlet oyunları yanıt olarak döner.^:3-4 Büyük belge derlemlerinde bu matris yerine ters indeks kullanılır. VE sorgusu, iki terimin belge listelerinin kesişimi alınarak, liste uzunlukları toplamıyla orantılı sürede yanıtlanır.^:10-11

Boole erişim modelini kullanan sistemler, World Wide Web'in ortaya çıktığı 1990'ların başına kadar otuz yıl boyunca büyük ticari bilgi sağlayıcılarının ana ya da tek arama seçeneği oldu. Bu sistemler temel Boole işlemlerinin yanında, iki terimin belgede birbirine yakın geçmesini isteyen yakınlık işleçleri gibi ek işleçler de içeren genişletilmiş Boole modelleri kullanıyordu.^:14-15 1975'te hizmete giren hukuk arama hizmeti Westlaw'da Boole araması 2005'te de varsayılan arama biçimiydi; sıralı serbest metin araması ise 1992'de eklenmişti. Boole sorgularında VE işleci kesinliği (İngilizce: precision) yüksek ama geri çağırması (İngilizce: recall) düşük, VEYA işleci ise geri çağırması yüksek ama kesinliği düşük aramalar verir ve ikisi arasında doyurucu bir orta yol bulmak zordur.^:15 Boole modelinin karşıtı, kullanıcının işleç kullanmadan sözcükler yazdığı ve sistemin belgeleri uygunluğa göre sıraladığı vektör uzay modeli gibi sıralı erişim modelleridir.^:14

Veri tabanları

SQL dilinde AND, OR ve NOT mantıksal işleçleri vardır. Ancak SQL doğru ve yanlışa ek olarak "bilinmeyen" anlamına gelen null değerini de içeren üç değerli bir mantık kullanır. Bu mantıkta TRUE AND NULL ifadesinin değeri NULL, FALSE AND NULL ifadesinin değeri FALSE, TRUE OR NULL ifadesinin değeri TRUE ve NOT NULL ifadesinin değeri NULL olur. Bu yüzden iki değerli Boole cebrinin tümleme yasası gibi bazı özdeşlikleri SQL'de her zaman geçerli değildir; örneğin bir sütun NULL değerini taşıdığında x OR NOT x ifadesi doğru değil, bilinmeyen değerini alır.