Boole cebiri - Boolean algebra

Gelen matematik ve matematiksel mantık , Boole cebri dalıdır cebir değerleri olan değişken olan gerçek değerleri doğru ve yanlış genellikle, sırası ile 1 ve 0 ile gösterilen,. Yerine temel cebir değişkenlerin değerleri sayıdır ve ana işlemler ve çarpma olup, Boole cebri ana işlemlerdir birlikte ( ve ) ∧ olarak ifade ayrılmasının ( veya ∨ olarak tanımlanır) ve olumsuzluk ( değil ) ¬ olarak gösterilir. Bu nedenle , temel cebirin sayısal işlemleri tanımlamasıyla aynı şekilde mantıksal işlemleri tanımlamak için bir formalizmdir .

Boole cebri George Boole tarafından ilk kitabı The Mathematical Analysis of Logic'de (1847) tanıtıldı ve An Investigation of the Laws of Thought (1854) adlı kitabında daha kapsamlı bir şekilde ortaya kondu . Huntington'a göre , "Boole cebiri" terimi ilk olarak 1913'te Sheffer tarafından önerildi , ancak Charles Sanders Peirce 1880'de "En Basit Matematik" in ilk bölümüne "Tek Sabitli Bir Boole Cebiri" başlığını verdi. dijital elektroniğin geliştirilmesinde temel olmuştur ve tüm modern programlama dillerinde sağlanır . Ayrıca küme teorisi ve istatistikte de kullanılır .

Tarih

Boole cebri bir öncü oldu Gottfried Leibniz 'in kavramların cebir . Leibniz'in kavram cebiri, Boolean kümeler cebirine tümdengelimsel olarak eşdeğerdir.

Boole'un cebiri, soyut cebir ve matematiksel mantıktaki modern gelişmelerden önce geldi ; ancak her iki alanın kökenlerine bağlı olarak görülür. Soyut bir ortamda, Boole cebri 19. yüzyılın sonlarında Jevons , Schröder , Huntington ve diğerleri tarafından modern bir (soyut) matematiksel yapı anlayışına ulaşana kadar mükemmelleştirildi . Örneğin, kümelerin cebirindeki ifadeleri Boole cebirindeki ifadelere çevirerek manipüle edebileceğine dair ampirik gözlem, modern terimlerle, kümelerin cebirinin bir Boole cebri olduğu söylenerek açıklanır ( belirsiz makaleye dikkat edin ). Aslında, MH Stone 1936'da her Boole cebrinin bir küme alanına eşbiçimli olduğunu kanıtladı .

1930'larda, anahtarlama devrelerini incelerken , Claude Shannon , Boole cebirinin kurallarının bu ortamda da uygulanabileceğini gözlemledi ve mantık kapıları açısından cebirsel yollarla devreleri analiz etmenin ve tasarlamanın bir yolu olarak anahtarlama cebirini tanıttı . Shannon zaten soyut matematiksel aygıta sahipti, bu nedenle anahtarlama cebirini iki elemanlı Boole cebiri olarak kullandı . Modern devre mühendisliği ayarlarında, diğer Boole cebirlerini dikkate almaya çok az ihtiyaç vardır, bu nedenle "anahtarlama cebiri" ve "Boole cebiri" genellikle birbirinin yerine kullanılır.

Verimli uygulama arasında Boole fonksiyonlarının temel bir sorundur tasarım ait birleşimsel mantık devreleri. VLSI devreleri için modern elektronik tasarım otomasyon araçları , mantık sentezi ve biçimsel doğrulama için genellikle (azaltılmış sıralı) ikili karar diyagramları (BDD) olarak bilinen Boolean fonksiyonlarının verimli bir temsiline dayanır .

Klasik olarak ifade edilebilir Mantık cümleler önermeler mantığı bir sahip eşdeğer ifadeyi Boolean cebir içinde. Bu nedenle, Boole mantığı bazen bu şekilde gerçekleştirilen önermeler hesabını belirtmek için kullanılır. Boole cebri, birinci dereceden mantıktakiler gibi niceleyiciler kullanan mantık formüllerini yakalamak için yeterli değildir .

Matematiksel mantığın gelişimi Boole'un programını takip etmese de , cebir ve mantık arasındaki bağlantı daha sonra diğer birçok mantığın cebirsel sistemlerini de inceleyen cebirsel mantık ortamında sağlam bir temele oturtulmuştur. Belirlenmesi problemi , belirli bir Boolean (önerme) formülünün değişkenleri aşağıdaki formüle etmek için böyle bir yolla tayin edilebilir adlandırılan gerçek olarak değerlendirilir Boole Satisfiability sorunu (SAT), ve bir önem taşımaktadır teorik bilgisayar biliminin olmak NP-tamamlanmış olarak gösterilen ilk sorun . Boolean devresi olarak bilinen yakından ilişkili hesaplama modeli (bir algoritmanın ) zaman karmaşıklığı ile devre karmaşıklığı arasında ilişki kurar .

değerler

İfadeler , temel cebirde esas olarak sayıları ifade ederken, Boolean cebrinde, false ve true doğruluk değerlerini ifade ederler . Bu değerler, 0 ve 1 gibi bitlerle (veya ikili rakamlarla) temsil edilirler . Bunlar , 1 + 1 = 2 olan 0 ve 1 tam sayıları gibi davranmazlar , ancak iki elemanlı alanın elemanları ile tanımlanabilirler. GF(2) , yani 1 + 1 = 0 olan tamsayı aritmetik modulo 2 . Toplama ve çarpma, daha sonra , x + yxy olarak tanımlanabilen xy (dahil-veya) ile sırasıyla XOR (dışlayıcı-veya) ve AND (bağlaç) Boolean rollerini oynar .

Boole cebri , değerleri {0, 1} kümesinde olan fonksiyonlarla da ilgilenir . Bu tür işlevler için yaygın olarak kullanılan bir bit dizisidir . Başka bir yaygın örnek bir dizi alt grupları olan E : bir alt kümesi F arasında E , tek bir tanımlayabilir gösterge fonksiyonu ile ilgili 1 değerini F dış ve 0 F . En genel örnek, bir Boole cebirinin öğeleridir ve yukarıdakilerin tümü bunların örnekleridir.

Temel cebirde olduğu gibi, teorinin tamamen denklemsel kısmı, değişkenler için açık değerler dikkate alınmadan geliştirilebilir.

Operasyonlar

Temel işlemler

Boole cebri temel operasyonlardır birlikte , ayrılma ve olumsuzluk . Bu Boolean işlemleri , topluca Boolean işleçleri olarak anılan , ilgili ikili işleçler AND , VEYA ve birli işleç DEĞİL ile ifade edilir .

x ve y değişkenleri üzerindeki temel Boole işlemleri aşağıdaki gibi tanımlanır:

Alternatif olarak, xy , xy ve ¬ x değerleri, değerleri doğruluk tablolarıyla aşağıdaki gibi tablolaştırılarak ifade edilebilir:

0 ve 1 doğruluk değerleri tam sayılar olarak yorumlanırsa, bu işlemler normal aritmetik işlemlerle (burada x + y toplamayı ve xy çarpmayı kullanır) veya minimum/maksimum işlevleriyle ifade edilebilir:

Bağlantıyı olumsuzlama ve ayrılma açısından tanımlamaya izin veren aşağıdaki özdeşlikler nedeniyle, yalnızca olumsuzlamanın ve diğer iki işlemden birinin temel olduğu düşünülebilir ve bunun tersi de geçerlidir ( De Morgan yasaları ):

ikincil işlemler

Yukarıda açıklanan üç Boole işlemine temel olarak atıfta bulunulur; bu, bunların , işlemlerin birleştirilme veya birleştirilme biçimiyle bileşim yoluyla bunlardan oluşturulabilecek diğer Boole işlemleri için temel alınabilecekleri anlamına gelir . Temel işlemlerden oluşan işlemler aşağıdaki örnekleri içerir:

Malzeme koşullu :
Özel VEYA ( XOR ):
Mantıksal denklik :

Bu tanımlar, dört olası girdinin tümü için bu işlemlerin değerlerini veren aşağıdaki doğruluk tablolarına yol açar.

İkincil işlemler. tablo 1
0 0 1 0 1
1 0 0 1 0
0 1 1 1 0
1 1 1 0 1
Malzeme koşullu
İlk işlem, x  →  y veya C xy , malzeme çıkarımı olarak adlandırılır . Eğer X doğru, daha sonra değeri x  →  y bu olarak alınır y (örneğin eğer X doğru ve Y yanlış, daha sonra x  →  y da yanlıştır). Ancak x yanlışsa, y'nin değeri yok sayılabilir; ancak, işlemin bir miktar boole değeri döndürmesi gerekir ve yalnızca iki seçenek vardır. Yani tanım gereği x  →  y olduğu doğrudur x yanlış olduğunda. ( ilgi mantığı , yanlış bir öncülü olan bir imayı doğru veya yanlıştan farklı bir şey olarak görerek bu tanımı önerir .)
Özel VEYA ( XOR )
İkinci işlem, x  ⊕  y veya J xy , kapsayıcı tür olarak ayrılmadan ayırt etmek için dışlayıcı veya (genellikle XOR olarak kısaltılır) olarak adlandırılır . Her iki olasılığını hariç x ve y toplamı (örneğin, bakınız tablo) doğru: her ikisi de doğru sonra sonuç yanlış ise. Aritmetik olarak tanımlanır, mod 2'nin 1 + 1 = 0 olduğu yerde toplamadır.
mantıksal denklik
Üçüncü işlem, dışlayıcı veya tümleyeni, denklik veya Boole eşitliğidir: x  ≡  y veya E xy , x ve y aynı değere sahip olduğunda doğrudur . Dolayısıyla , tümleyeni olarak x  ⊕  y , x  ≠  y olarak anlaşılabilir , tam da x ve y farklı olduğunda doğrudur . Böylece, aritmetik mod 2'deki karşılığı x + y'dir . Aritmetik mod 2'de denkliğin karşılığı x + y + 1'dir.

Her biri iki olası değere sahip iki işlenen verildiğinde, 2 2 = 4 olası giriş kombinasyonu vardır. Her çıktının iki olası değeri olabileceğinden, toplam 2 4 = 16 olası ikili Boole işlemi vardır . Bu tür herhangi bir işlem veya işlev (ve daha fazla girdiye sahip herhangi bir Boole işlevi) yukarıdan temel işlemlerle ifade edilebilir. Böylece temel işlemler işlevsel olarak tamamlanmıştır .

kanunlar

Bir yasa Boole cebri bir bir kimlik gibi x (∨ yz ) = ( xy ) ∨ z bir iki mantıksal açısından arasında Boole süreli değişkenlerinden inşa bir ifade olarak tanımlanır ve sabitler 0 ve 1 kullanılarak ∧, ∨ ve ¬ işlemleri. Konsept, ⊕, → ve ≡ gibi diğer Boolean işlemlerini içeren terimlere genişletilebilir, ancak bu tür uzantılar, yasaların konulduğu amaçlar için gereksizdir. Bu tür amaçlar , Boole yasalarının herhangi bir modeli olarak bir Boole cebirinin tanımını ve x ∨ ( yz ) = x ∨ ( zy ) 'nin y ∧'den türetilmesinde olduğu gibi eskiden yeni yasalar türetmenin bir aracı olarak tanımını içerir. z = zy ( § Axiomatizing Boole cebirinde işlendiği gibi ).

monoton yasalar

Boole cebri, ∨ toplama ve ∧ çarpma ile eşleştirildiğinde, sıradan cebir ile aynı yasaların çoğunu karşılar. Özellikle aşağıdaki yasalar her iki cebir türü için ortaktır:

İlişkisellik :
İlişkisellik :
Değişebilirlik :
Değişebilirlik :
Dağılımı fazla :
Kimlik :
Kimlik :
için yok edici :

Aşağıdaki yasalar Boole cebirinde geçerlidir, ancak sıradan cebirde geçerli değildir:

için yok edici :
İmpotans :
İmpotans :
Emilim 1:
Absorpsiyon 2:
Dağılımı fazla :

Yukarıdaki üçüncü yasada x = 2 almak , 2 × 2 = 4 olduğundan bunun sıradan bir cebir yasası olmadığını gösterir . Kalan beş yasa, tüm değişkenler 1 alınarak adi cebirde tahrif edilebilir. Örneğin, Absorpsiyon Yasası 1'de sol taraf 1(1 + 1) = 2 iken sağ taraf 1 () olur. ve bunun gibi).

Şimdiye kadar ele alınan tüm yasalar birleşme ve ayrılma için olmuştur. Bu işlemler, herhangi bir argümanın değiştirilmesinin çıktıyı değiştirmeden bırakması veya çıktının girdiyle aynı şekilde değişmesi özelliğine sahiptir. Eşdeğer olarak, herhangi bir değişkeni 0'dan 1'e değiştirmek, hiçbir zaman çıktının 1'den 0'a değişmesiyle sonuçlanmaz. Bu özelliğe sahip işlemlerin monoton olduğu söylenir . Bu nedenle, şimdiye kadarki aksiyomların tümü monotonik Boole mantığı içindi. Monoton olmama, aşağıdaki gibi tamamlayıcı ¬ yoluyla girer.

monoton olmayan yasalar

Tamamlayıcı işlemi aşağıdaki iki yasa ile tanımlanır.

Aşağıdaki yasalar da dahil olmak üzere tüm olumsuzlama özellikleri, yalnızca yukarıdaki iki yasadan çıkar.

Hem sıradan hem de Boole cebrinde, olumsuzlama, eleman çiftlerinin değiş tokuşuyla çalışır, bu nedenle her iki cebirde de çifte olumsuzlama yasasını (involüsyon yasası olarak da adlandırılır) karşılar.

Ancak sıradan cebir iki yasayı karşılarken

Boole cebri, De Morgan yasalarını karşılar :

eksiksizlik

Yukarıda listelenen yasalar, konunun geri kalanını içermeleri anlamında Boole cebrini tanımlar. Yasalar tamamlama 1 ve 2 birlikte monoton yasalara, bu amaçla yeterli durumdadır ve bu nedenle bir sürede alınabilir komple kanun veya kümesi aksiyomlaştırılması Boole cebri. Boole cebrinin her yasası mantıksal olarak bu aksiyomlardan çıkar. Ayrıca, Boole cebirleri § Boole cebirlerinde işlendiği gibi bu aksiyomların modelleri olarak tanımlanabilir .

Açıklığa kavuşturmak için, Boole cebrinin daha fazla yasasını yazmak, bu aksiyomların herhangi bir yeni sonucunu doğuramaz ve bunların herhangi bir modelini dışlayamaz. Buna karşılık, aynı yasaların tümü olmasa da bazılarından oluşan bir listede, listedekilerden farklı olan Boole yasaları olabilirdi ve ayrıca listelenen yasaların Boole cebirleri olmayan modelleri olabilirdi.

Bu aksiyomlaştırma, hiçbir şekilde tek aksiyom değildir, hatta bazı aksiyomların diğerlerinden gelip gelmediğine dikkat etmediğimiz, ancak yeterli yasamız olduğunu fark ettiğimizde durmayı seçtiğimiz göz önüne alındığında, § Aksiyomlaştırma bölümünde daha ayrıntılı olarak ele alındığından, en doğal olanı değildir. Boole cebiri . Veya ara aksiyom kavramı, bir Boole yasasını doğrudan herhangi bir totoloji olarak tanımlayarak , 0 ve 1 üzerindeki değişkenlerinin tüm değerlerini tutan bir denklem olarak anlaşılarak, tamamen ortadan kaldırılabilir . Boole cebrinin tüm bu tanımlarının eşdeğer olduğu gösterilebilir.

dualite prensibi

İlke: Eğer {X, R} bir poz ise , o zaman {X, R(ters)} da bir pozdur.

Boole cebri değerleri için sembol seçiminin sihirli bir tarafı yoktur. 0 ve 1'i α ve β olarak yeniden adlandırabiliriz ve bu şekilde tutarlı bir şekilde yaptığımız sürece, bazı belirgin kozmetik farklılıklar olsa da yine de Boole cebri olacaktır.

Ancak, sırasıyla 0 ve 1'i 1 ve 0 olarak yeniden adlandırdığımızı varsayalım. O zaman yine Boole cebiri olurdu ve dahası aynı değerler üzerinde çalışırdı. Ancak orijinal Boole cebrimizle aynı olmayacaktı çünkü şimdi ∨'nin eskiden olduğu gibi davrandığını ve bunun tersini buluyoruz. Dolayısıyla, 0'ları ve 1'leri kullanmamıza rağmen, gösterimle uğraştığımızı göstermek için hala bazı kozmetik farklılıklar var.

Ancak, değerlerin adlarını değiştirmeye ek olarak, iki ikili işlemin adlarını da değiştirirsek, şimdi ne yaptığımıza dair hiçbir iz kalmaz. Son ürün, başladığımız üründen tamamen ayırt edilemez. Doğruluk tablolarındaki xy ve xy sütunlarının yer değiştirdiğini fark edebiliriz, ancak bu geçiş önemsizdir.

Değerler ve işlemler, tüm çiftler aynı anda değiştirildiğinde önemli olan her şeyi değişmeden bırakacak şekilde eşleştirilebildiğinde, her çiftin üyelerini birbirine ikili olarak adlandırırız. Böylece 0 ve 1 dualdir ve ∧ ve ∨ dualdir. Dualite Prensibi olarak da adlandırılan, De Morgan ikilik , tüm ikili çiftleri yerdeğiştirimiş zaman Boole cebri değişmeden olduğunu ileri sürer.

Bu değiş tokuşun bir parçası olarak yapmamız gerekmeyen bir değişiklik, tamamlamaktı. Tamamlayıcının kendi kendine ikili bir işlem olduğunu söylüyoruz . Özdeşlik veya hiçbir şey yapmama işlemi x (girdiyi çıktıya kopyalayın) ayrıca kendi kendine çifttir. Kendi kendine çift işlemin daha karmaşık bir örneği ( xy ) ∨ ( yz ) ∨ ( zx ) şeklindedir . Her iki argümanına da bağlı olan kendi kendine ikili ikili işlem yoktur. Self-dual operasyonların bir bileşimi, self-dual bir operasyondur. Örneğin, f ( x , y , z ) = ( xy ) ∨ ( yz ) ∨ ( zx ) ise , o zaman f ( f ( x , y , z ), x , t ) bir özdür -dört argümanın ikili işlemi x , y , z , t .

İkilik ilkesi, Boole polinomları kümesinin kendisine bire bir eşlemeleri ( otomorfizmler ) olan tam olarak dört işlevin olması gerçeğiyle grup teorisi perspektifinden açıklanabilir : özdeşlik işlevi, tamamlayıcı işlevi, ikili fonksiyon ve kontradual fonksiyon (tamamlanmış ikili). Bu dört fonksiyonları oluşturmak grubu altında işlev bileşiminin izomorf, Klein, dört grup , hareket Boole polinomların setinde. Walter Gottschalk dolayısıyla olay için daha uygun bir isim olur belirtti prensibi (ya da kare ) quaternality arasında .

diyagramatik gösterimler

Venn şemaları

Bir Venn şeması , gölgeli örtüşen bölgeleri kullanan bir Boolean işleminin temsili olarak kullanılabilir. Buradaki örneklerde tamamı dairesel olan her değişken için bir bölge vardır. Dahili ve bölgenin dış X değerlerine karşılık gelir, sırasıyla değişken için 1 (doğru) ve 0 (yanlış) x . Gölgelendirme, koyu 1 ve açık 0 ile her bölge kombinasyonu için işlemin değerini gösterir (bazı yazarlar zıt kuralı kullanır).

Şekilde üç Venn diyagramları aşağıda sırasıyla birlikte temsil xy , ayrılma xy tamamlayıcı ¬ ve X .

Şekil 2. Birleşim, ayrılma ve tamamlayıcı için Venn diyagramları

Bağlantı için, her iki değişken de 1 olduğunda xy'nin 1 olduğunu belirtmek için her iki dairenin içindeki bölge gölgelenir . Diğer bölgeler , diğer üç kombinasyon için xy'nin 0 olduğunu belirtmek üzere gölgelenmeden bırakılır .

İkinci diyagram, dairelerden birinin veya her ikisinin içinde kalan bölgeleri gölgeleyerek xy ayrılmasını temsil eder . Üçüncü diyagramı tamamlayıcı ¬ temsil X bölge gölgeleme ile değil daire içinde.

0 ve 1 sabitleri için Venn diyagramlarını göstermemiş olsak da, bunlar önemsizdir, sırasıyla beyaz bir kutu ve karanlık bir kutudur ve hiçbiri daire içermez. Ancak için bir çevre koymak x her biri bağımsız değişken, bir fonksiyonu ifade ederler, bu durumda bu kutularda, x bağımsız bir şekilde, aynı değeri verir, x sabit bir fonksiyonu olarak adlandırılır. Çıktıları söz konusu olduğunda, sabitler ve sabit fonksiyonlar ayırt edilemez; fark, bir sabitin sıfır veya sıfır işlemi adı verilen hiçbir argüman almaması , sabit bir işlevin ise yok saydığı bir argüman alması ve tekli bir işlem olmasıdır.

Venn diyagramları yasaları görselleştirmede yardımcı olur. ∧ ve ∨ için değişebilirlik yasaları diyagramların simetrisinden görülebilir: değişmeli olmayan bir ikili işlem simetrik bir diyagrama sahip olmaz çünkü x ve y'nin yer değiştirmesi diyagramı yatay olarak yansıtma etkisine sahip olur ve herhangi bir değişme hatası sonra simetri hatası olarak görünür.

∧ ve ∨'nin eşitsizliği , iki daireyi birlikte kaydırarak ve gölgeli alanın hem ∧ hem de ∨ için tüm daire haline geldiğine dikkat ederek görselleştirilebilir.

İlk absorpsiyon kanunu görmek için X ∧ ( xy ) = x , için ortada diyagram ile başlar xy ile ortak olarak gölgeli alanın kısmı olduğu ve kayda X dairesinin bütündür X daire . İkinci absorpsiyon yasası için, x ∨( xy ) = x , xy için soldaki diyagramla başlayın ve önceki gölgeleme içeride olduğundan, x dairesinin tamamının gölgelenmesinin yalnızca x dairesinin gölgelenmesiyle sonuçlandığını unutmayın. x grubu.

Çift olumsuzluk yasası ¬ üçüncü çizimde gölgeleme tamamlayarak görülebilir x olan gölgeler, X daire.

İlk De Morgan yasasını (¬ görselleştirmek için x ) ∧ (¬ y ) = ¬ ( xy ) için orta diyagram ile başlayan xy ve her iki çevreleri dışında bu tek bölge gölgeliyse böylece onun gölgeleme tamamladığı yasanın sağ tarafının tanımladığı şeydir. Sonuç, hem x dairesinin hem de y dairesinin dışındaki bölgeyi , yani yasanın sol tarafının tanımladığı gibi, dışlarının birleşimini gölgelediğimiz gibidir .

İkinci De Morgan yasası, (¬ x )∨(¬ y ) = ¬( xy ), birbirinin yerine geçen iki diyagramla aynı şekilde çalışır.

Birinci tümleyen yasası, x ∧¬ x = 0, x çemberinin iç ve dış kısımlarının örtüşmediğini söyler . İkinci tümleyen yasası, x ∨¬ x = 1, her şeyin x çemberinin içinde veya dışında olduğunu söyler .

Dijital mantık kapıları

Sayısal mantık, 0 ve 1 Boole cebrinin bir devre şeması oluşturacak şekilde bağlanmış mantık kapılarından oluşan elektronik donanıma uygulanmasıdır . Her kapı bir Boolean işlemi uygular ve işlemi gösteren bir şekil ile şematik olarak gösterilir. Birleşim (AND-geçitleri), ayrılma (OR-geçitleri) ve tamamlayıcı (invertörler) için kapılarla ilişkili şekiller aşağıdaki gibidir.

Soldan sağa: AND , OR ve NOT kapıları.

Her geçidin solundaki çizgiler, giriş kablolarını veya bağlantı noktalarını temsil eder . Girişin değeri, uçtaki bir voltaj ile temsil edilir. "Aktif-yüksek" olarak adlandırılan mantık için 0, sıfıra yakın bir voltaj veya "toprak" ile temsil edilirken 1, besleme voltajına yakın bir voltaj ile temsil edilir; aktif-düşük bunu tersine çevirir. Her geçidin sağındaki çizgi, normalde giriş portlarıyla aynı voltaj kurallarını izleyen çıkış portunu temsil eder.

Tamamlayıcı bir invertör kapısı ile gerçekleştirilir. Üçgen, girdiyi çıktıya basitçe kopyalayan işlemi belirtir; çıktıdaki küçük daire, girişi tamamlayan gerçek ters çevirmeyi belirtir. Herhangi bir bağlantı noktasına böyle bir daire koyma kuralı, bu bağlantı noktasından geçen sinyalin, ister giriş ister çıkış bağlantı noktası olsun, yolda tamamlandığı anlamına gelir.

Duallik veya De Morgan yasaları , iddia olarak anlaşılabilir aşağıda Şekil 4'te gösterildiği gibi, bir OR tersi kapısı ve yardımcısı bir AND kapısının dönüştürerek her üç port tamamlayıcı. Ancak bir invertörün her iki portunu tamamlamak, işlemi değiştirmeden bırakır.

DeMorganGates.GIF

Daha genel olarak, bir VE veya VEYA geçidinin üç bağlantı noktasının sekiz alt kümesinden herhangi biri tamamlanabilir. Ortaya çıkan on altı olasılık, yalnızca sekiz Boole işlemine, yani doğruluk tablolarında tek sayıda 1'e sahip olanlara yol açar. Sekiz tane vardır, çünkü "tek bit-çıkışı" 0 veya 1 olabilir ve doğruluk tablosundaki dört konumdan herhangi birine gidebilir. On altı ikili Boole işlemi olduğu için, bu, doğruluk tablolarında çift sayılı 1'li sekiz işlem bırakmalıdır. Bunlardan ikisi, 0 ve 1 sabitleridir (her iki girişini de yok sayan ikili işlemler olarak); Dört tam nontrivially üzerindeki iki giriş, yani biri bağlı işlemlerdir x , y , ¬ X ve ¬ y ; ve kalan ikisi xy (XOR) ve onun tamamlayıcısı xy .

Boole cebirleri

"Cebir" terimi, hem bir özneyi, yani cebirin öznesini hem de bir nesneyi, yani cebirsel bir yapıyı belirtir . Yukarıdakiler Boole cebri konusunu ele alırken, bu bölüm Boole yasalarının herhangi bir modeli olarak tam genel olarak tanımlanan Boole cebri adı verilen matematiksel nesnelerle ilgilenir. Kavramın yasalara atıfta bulunmadan tanımlanabilen özel bir durumuyla, yani somut Boole cebirleriyle başlıyoruz ve sonra genel kavramın biçimsel tanımını veriyoruz .

Beton Boole cebirleri

Bir beton Boole cebri veya kümelerin alan belirli bir dizi alt kümelerinin herhangi boş olmayan kümesidir X kümesi operasyonları kapsamında kapalı birlik , kavşak ve tamamlayıcı göre X .

(Bir yana, tarihsel olarak X'in kendisinin de dejenere veya tek elemanlı Boole cebirini hariç tutmak için boş olmaması gerekiyordu; bu, dejenere cebir her denklemi karşıladığı için tüm Boole cebirlerinin aynı denklemleri sağladığı kuralının tek istisnasıdır. Bununla birlikte, bu hariç tutma, tercih edilen tamamen denklemsel "Boole cebiri" tanımıyla çelişir, yalnızca denklemleri kullanarak tek elemanlı cebiri dışlamanın bir yolu yoktur - 0 ≠ 1, olumsuzlanmış bir denklem olduğu için sayılmaz. Boole cebri ve X'in boş olmasına izin verin .)

Örnek 1. gücü ayarlanır 2 X ve X her oluşan alt kümeleri arasında , X . Burada X herhangi bir küme olabilir: boş, sonlu, sonsuz ve hatta sayılamayan .

Örnek 2. Boş küme ve X . Bu iki elemanlı cebir, somut bir Boole cebrinin sonsuz bir kümenin alt kümelerinden oluştuğunda bile sonlu olabileceğini gösterir. X'in alt kümelerinin her alanının boş kümeyi ve X'i içermesi gerektiği görülebilir . Bu nedenle herhangi bir küçük örnek, alma ile elde edilen dejenere cebir dışında mümkündür X boş seti ve kılacak şekilde boş olduğu X- örtüşmektedir.

Örnek 3. Sonlu ve kosonlu tamsayı kümeleri kümesi, burada bir kosonlu küme, yalnızca sonlu sayıda tamsayı atlayan bir kümedir. Bu açıkça tamamlayıcı altında kapalıdır ve birleşim altında kapalıdır, çünkü bir kosonlu kümenin herhangi bir kümeyle birleşimi kosonluyken, iki sonlu kümenin birleşimi sonludur. Kesişim, "sonlu" ve "kofinite" değiş tokuşu ile birleşme gibi davranır.

Örnek 4. Örnek 2 yolu ile yapılan noktasının daha basit örnekte, bir dikkate Venn diyagramı ile oluşturulan N kapalı eğriler bölümleme 2 içine diyagramı n bölgeleri ve izin X, ilgili düzlemde tüm noktalarının (sonsuz) grubu vermeye herhangi bir eğri, ancak diyagramın içinde bir yerde. Her bölgenin iç böylece sonsuz bir alt kümesi , X , ve her bir nokta , X , tam olarak bir bölgede yer almaktadır. Daha sonra, tüm 2 2 n bölge birleşimlerinin tümü (boş bölgelerin birleşimi olarak elde edilen boş küme ve 2 n bölgesinin tümünün birleşimi olarak elde edilen X dahil ) aşağıdakilere göre birleşim, kesişim ve tümleyen altında kapatılır. X ve bu nedenle somut bir Boole cebiri oluşturur. Yine, somut bir Boole cebri oluşturan bir sonsuz kümenin sonlu sayıda alt kümesine sahibiz, Örnek 2, eğri olmaması durumunda n = 0 olarak ortaya çıkıyor.

Bit vektörleri olarak alt kümeler

Bir alt-kümesi , Y ve X , bir ile tespit edilebilir endeksli ailesi olan bit dizini grubu X bit tarafından dizine sahip, XX olup olmamasına göre 1 veya 0 olan xY . (Bu, bir altkümenin sözde karakteristik fonksiyon kavramıdır.) Örneğin, 32 bitlik bir bilgisayar kelimesi, {0,1,2,...,31} kümesi tarafından 0 ve 31 ile indekslenen 32 bitten oluşur. sırasıyla düşük ve yüksek dereceli bitlerin indekslenmesi. Daha küçük bir örnek için, eğer X = { a,b,c } burada a, b, c soldan sağa bu sırada bit konumları olarak görülüyorsa, sekiz alt küme {}, { c }, { b }, { b , c }, { a }, { a , c }, { a , b } ve { a , b , c } X ilgili bit vektörleri 000, 001, 010, 011, 100, 101 ile tanımlanabilir, doğal sayılar kümesinin endeksli 110, ve 111 bit vektörleri sonsuzdur sekansları tarafından dizine olanlar ise, bit reals içinde birim aralıkta [0,1], geleneksel yazmak mümkün ama yine de iyi-oluşturmak için çok yoğun paketlenir tanımlanmış indekslenmiş aileler ([0,1] aralığının her noktasını bağımsız olarak siyah veya beyaz renklendirdiğini hayal edin; siyah noktalar daha sonra [0,1]'in keyfi bir alt kümesini oluşturur).

Bu bit vektörü bakış açısından, bir somut Boole cebri eşdeğer olarak tümü aynı uzunlukta (daha genel olarak, aynı küme tarafından indekslenir) ve bitsel ∧, ∨ ve bit vektörü işlemleri altında kapatılan boş olmayan bir bit vektörleri kümesi olarak tanımlanabilir. ¬, 1010∧0110 = 0010, 1010∨0110 = 1110 ve ¬1010 = 0101'de olduğu gibi, sırasıyla kesişim, birleşim ve tümleyenin bit vektörü gerçekleşmeleri.

Prototipik Boole cebiri

{0,1} kümesi ve onun Boolean işlemleri, yukarıda ele alındığı şekliyle, bir uzunluktaki bit vektörlerinin özel durumu olarak anlaşılabilir; bu, bit vektörlerinin alt kümelerle tanımlanmasıyla, bir tek elemanın iki alt kümesi olarak da anlaşılabilir. Ayarlamak. Buna , aşağıdaki gözlemle doğrulanan prototipik Boole cebiri diyoruz .

Tüm dejenere olmayan somut Boole cebirlerinin sağladığı yasalar, prototipik Boole cebrinin sağladığı yasalarla örtüşür.

Bu gözlem aşağıdaki gibi kolayca kanıtlanabilir. Kesinlikle, tüm somut Boolean cebirleri tarafından sağlanan herhangi bir yasa, somut olduğu için prototip olan tarafından karşılanır. Tersine, bazı somut Boole cebri için başarısız olan herhangi bir yasa, belirli bir bit konumunda başarısız olmuş olmalıdır, bu durumda bu konum kendi başına bu yasaya bir bitlik bir karşı örnek teşkil eder. Dejenere olmama, yalnızca bir boş bit vektörü olduğu için en az bir bit konumunun varlığını sağlar.

Bir sonraki bölümün nihai amacı, yukarıdaki gözlemden "somut"u çıkarmak olarak anlaşılabilir. Ancak bu amaca, izomorfizme kadar tüm Boole cebirlerinin somut olduğuna dair şaşırtıcı derecede güçlü gözlem yoluyla ulaşacağız.

Boole cebirleri: tanım

Şimdiye kadar gördüğümüz Boole cebirlerinin tümü, bit vektörlerinden veya eşdeğer olarak bir kümenin alt kümelerinden oluşan somuttu. Böyle bir Boole cebri, Boole cebri yasalarını karşıladığı gösterilebilen bir küme ve bu küme üzerindeki işlemlerden oluşur .

Bunun yerine Boole yasalar yerine getirdiğinin gösteren, bunun yerine bir dizi Sürebilirdik X , iki ikili operasyonlar X ve bir tek terimli operasyon ve ihtiyaç bu operasyonlar Boole cebri kanunlarını tatmin söyledi. X'in öğelerinin bit vektörleri veya alt kümeleri olması gerekmez, ancak herhangi bir şey olabilir. Bu, daha genel soyut tanımlamaya yol açar .

Bir Boole cebri ikili operasyonlar ∧ ve herhangi seti ∨ ve Boole yasaları tatmin eden tek terimli operasyon ¬ onun üzerindekilere.

Bu tanımın amaçları bakımından, ister fiat ister ispat yoluyla olsun, işlemlerin kanunları nasıl karşıladığı önemsizdir. Tüm somut Boole cebirleri, yasaları karşılar (fiat yerine ispat yoluyla), bu nedenle her somut Boole cebri, tanımlarımıza göre bir Boole cebridir. Bir Boole cebrinin bu aksiyomatik tanımı, belirli yasaları veya aksiyomları fiat ile karşılayan bir küme ve belirli işlemler olarak , modern veya soyut cebirin karakteristiği olan grup , halka , alan vb. soyut tanımlarına tamamen benzerdir .

Boole cebrinin herhangi bir tam aksiyomlaştırılması, örneğin tümleyen bir dağıtım kafesi için aksiyomlar verildiğinde , bu tür bir cebirsel yapının tüm Boole yasalarını karşılaması için yeterli bir koşul, sadece bu aksiyomları sağlamasıdır. Bu nedenle aşağıdaki eşdeğer bir tanımdır.

Bir Boole cebri bir tamamlanmaktadır dağıtıcı kafes olduğunu.

Aksiyomlaştırmayla ilgili bölüm , herhangi biri eşdeğer bir tanımın temeli yapılabilen diğer aksiyomlaştırmaları listeler.

Temsil edilebilir Boole cebirleri

Her somut Boole cebri bir Boole cebri olmasına rağmen, her Boole cebrinin somut olması gerekmez. Let , n bir olmak kare içermeyen bir tamsayı karesi ile bir bölünemeyen bir pozitif tam sayı, örneğin 30, ancak 12. işlemleri büyük ortak bölen , en az ortak katı halinde ve bölme n , alışılagelen ( X = N / x ), argümanları n'nin pozitif bölenleri arasında değiştiğinde tüm Boole yasalarını karşıladığı gösterilebilir . Dolayısıyla bu bölenler bir Boole cebiri oluşturur. Bu bölenler ait bölenler yapma dizisi alt gruplarının, olmayan n Tanımlarımıza göre beton olmayan bir Boole cebir.

Bununla birlikte, n'nin her bölenini asal faktörler kümesiyle temsil edersek, bu somut olmayan Boole cebrinin, n'nin tüm asal faktörleri kümelerinden oluşan somut Boole cebriyle izomorf olduğunu ve birleşimin en küçük ortak kata , kesişimine karşılık geldiğini buluruz. en büyük ortak bölene ve n'ye bölmenin tümleyenine . Dolayısıyla bu örnek teknik olarak somut olmasa da en azından "ahlaki olarak" bu temsil yoluyla somuttur , buna izomorfizm denir . Bu örnek, aşağıdaki kavramın bir örneğidir.

Bir Boole cebri, somut bir Boole cebrine eşbiçimli olduğunda temsil edilebilir olarak adlandırılır .

Bir sonraki bariz soru şu şekilde olumlu yanıtlanır.

Her Boole cebri temsil edilebilir.

Yani, izomorfizme kadar soyut ve somut Boole cebirleri aynı şeydir. Bu oldukça önemsiz sonuç , seçim aksiyomundan biraz daha zayıf bir seçim ilkesi olan Boolean asal ideal teoremine bağlıdır ve Stone'un Boole cebirleri için temsil teoremi makalesinde daha ayrıntılı olarak işlenir . Bu güçlü ilişki, önceki alt bölümdeki gözlemi, temsil edilebilirliğin aşağıdaki kolay sonucuyla güçlendiren daha zayıf bir sonuç anlamına gelir.

Tüm Boole cebri tarafından sağlanan yasalar, prototip Boole cebri tarafından sağlanan yasalarla örtüşür.

Kendi başına temsil edilebilirliği ima etmemesi anlamında daha zayıftır. Boole cebri burada özeldir, örneğin bir ilişki cebri , ek yapıya sahip bir Boole cebridir, ancak her ilişki cebrinin, ilişki cebirlerine uygun anlamda temsil edilebilir olması söz konusu değildir.

Boole cebirinin aksiyomlaştırılması

Bir küme olarak soyut bir Boole cebrinin yukarıdaki tanımı ve "" Boole yasalarını karşılayan işlemler, bu yasalar nelerdir? Basit bir cevap, 0 ve 1 Boole cebri için geçerli olan tüm denklemler olarak tanımlanabilen "tüm Boole yasaları"dır. sonraki soru: Tutmak için yalnızca sınırlı sayıda yasaya ihtiyaç duymak yeterli mi?

Boole cebri durumunda cevap evettir. Özellikle yukarıda sıraladığımız sonlu sayıdaki denklemler yeterlidir. Boole cebrinin sonlu olarak aksiyomlanabilir veya sonlu tabanlı olduğunu söylüyoruz .

Bu liste daha da kısaltılabilir mi? Cevap yine evet. Başlangıç ​​olarak, yukarıdaki yasalardan bazıları diğerleri tarafından ima edilmektedir. Yukarıdaki yasaların yeterli bir alt kümesi, birleşme, değişme ve soğurma yasaları çiftlerinden, ∧ bölü ∨'nin dağıtılabilirliği (veya diğer dağıtım yasası - bir tanesi yeterlidir) ve iki tamamlayıcı yasadan oluşur. Aslında bu, Boole cebrinin tamamlayıcı bir dağıtım kafesi olarak geleneksel aksiyomlaştırılmasıdır .

Yukarıda sıralanmayan ek kanunlar getirerek, listeyi daha da kısaltmak mümkün hale gelir; örneğin, Sheffer vuruş işlemini temsil eden dikey çubukla , tek aksiyom Boole cebirini tamamen aksiyomlaştırmak için yeterlidir. Daha geleneksel işlemler kullanarak daha uzun tekli aksiyomlar bulmak da mümkündür; bkz . Boole cebri için minimal aksiyomlar .

önerme mantığı

Önerme mantığı ,Boole cebriyle yakından bağlantılıbir mantıksal sistemdir . Boole cebrinin birçok sözdizimsel kavramı, notasyon ve terminolojide sadece küçük değişikliklerle önerme mantığına taşınırken, önerme mantığının semantiği, Boole cebirleri aracılığıyla, önerme mantığının totolojileri (teoremleri) Boole cebrinin denklem teoremlerine karşılık gelecek şekilde tanımlanır. .

Sözdizimsel olarak, her Boole terimi , önerme mantığının bir önerme formülüne karşılık gelir . Boole cebri ve önerme mantığı arasındaki bu çeviride, Boole değişkenleri x,y ... önerme değişkenleri (veya atomlar ) olur P,Q ,..., xy gibi Boole terimleri önerme formülleri olur PQ , 0 yanlış olur veya ve 1 doğru veya T olur . Yunan harfleri kullanmak jenerik önermeler bahsederken O Φ, Ψ, ... metavariables olarak (konuşurken önermeler mantığı dili dışında değişkenler, kullanılan uygundur ilgili önermeleri göstermek için önermeler mantığı).

Önerme mantığının semantiği, doğruluk atamalarına dayanır . Doğruluk atamasının temel fikri, önerme değişkenlerinin sabit bir Boole cebrinin öğeleriyle eşlenmesidir ve daha sonra bu harfleri kullanan bir önerme formülünün doğruluk değeri , değerinin hesaplanmasıyla elde edilen Boole cebrinin öğesidir. Formüle karşılık gelen Boole terimi. Klasik anlambilimde, yalnızca iki elemanlı Boole cebri kullanılırken, Boolean değerli semantikte keyfi Boole cebirleri dikkate alınır. Bir totoloji , önerme değişkenlerinin keyfi bir Boole cebrine (veya eşdeğer olarak, iki Boole cebrine her doğruluk atamasına) her doğruluk ataması tarafından doğruluk değeri 1 olarak atanan bir önerme formülüdür .

Bu anlambilim, önerme mantığının totolojileri ile Boole cebirinin denklem teoremleri arasında bir çeviriye izin verir. Önerme mantığının her totolojisi Φ, Boole cebrinin bir teoremi olacak olan Boole denklemi Φ = 1 olarak ifade edilebilir. Tersine, Boole cebirinin her Φ = Ψ teoremi (Φ∨¬Ψ) ∧ (¬Φ∨Ψ) ve (Φ∧Ψ) ∨ (¬Φ∧¬Ψ) totolojilerine karşılık gelir. → eğer dilde ise, bu son totolojiler (Φ→Ψ) ∧ (Ψ→Φ) veya iki ayrı teorem Φ→Ψ ve Ψ→Φ olarak da yazılabilir; ≡ varsa, tek totoloji Φ ≡ Ψ kullanılabilir.

Uygulamalar

Önermeler hesabının motive edici bir uygulaması, doğal dilde önermelerin ve tümdengelimli argümanların analizidir. Önerme ise "ise X = 3 daha sonra x + 1 = 4" e "halinde + ve 1, önerme gibi ifadelerin anlamları bağlıdır X sonra = 3 x = 3" değildir; sadece yapısı nedeniyle doğrudur ve " x = 3" yerine " x = 4" veya "ay yeşil peynirden yapılmış" olsun, doğru kalır . Bu totolojinin genel veya soyut şeklidir "eğer P ardından P " veya Boole cebri, "dilinde PP ".

Değiştirilmesi P ile x = 3 ya da başka bir önerme olarak adlandırılır örneğinin bir P bu önerme ile. Soyut bir önermede P'yi somutlaştırmanın sonucuna, önermenin bir örneği denir . Böylece " x = 3 → x = 3", soyut " PP " totolojisinin bir örneği olması nedeniyle bir totolojidir . Px = 3 veya x = 3 → x = 4 gibi saçmalıklardan kaçınmak için, somutlaştırılan değişkenin tüm oluşumları aynı önerme ile somutlaştırılmalıdır .

Önermeler hesabı, dikkati, Boolean işlemlerini kullanarak önerme değişkenlerinden oluşturulan soyut önermelere sınırlar. Destekleme önermeler mantığı içinde değil, sadece bu başlatmasını gibi soyut önermeler ile önerme değişkenleri başlatmasını tarafından hala mümkündür Q ile Q'nunP içinde P → ( SP örneği elde etmek için) P → (( Sp →) P ).

(Önermeler hesabı mekanizmasının bir parçası olarak somutlaştırmanın mevcudiyeti, önermeler hesabının dilinde üstdeğişkenlere olan ihtiyacı ortadan kaldırır, çünkü sıradan önerme değişkenleri dil içinde keyfi önermeleri belirtmek için düşünülebilir. Üstdeğişkenlerin kendileri somutlaştırmanın erişiminin dışındadır, önermeler hesabı dilinin bir parçası olmayıp, daha ziyade bu cümlenin yazıldığı şey hakkında konuşmak için aynı dilin bir parçası olmak, burada önerme değişkenlerini ve bunların örneklerini farklı sözdizimsel varlıklar olarak ayırt edebilmemiz gerekir.)

Önerme mantığı için tümdengelim sistemleri

Önermeler hesabının aksiyomlaştırılması, aksiyom adı verilen bir dizi totoloji ve eskiden yeni totolojiler üretmek için bir veya daha fazla çıkarım kuralıdır. Bir aksiyom sistemi A'daki bir ispat , her biri ya A aksiyomunun bir örneği olan veya ispatta daha önce görünen önermelerden bazı A kuralı tarafından takip edilen (böylece dairesel akıl yürütmeye izin vermeyen) sonlu, boş olmayan bir önerme dizisidir . Son önerme, ispatla ispatlanan teoremdir . Bir ispatın her boş olmayan ilk parçasının kendisi bir ispattır, bu nedenle ispattaki her önermenin kendisi bir teoremdir. Bir aksiyomlaştırılması olan ses her teoremi bir totoloji olduğunu ve ne zaman tam her totolojidir bir teoremi olduğunda.

sıralı hesap

Önermeli taşı yaygın olarak düzenlenmiş Hilbert sistemi olan işlemler gibi olan teoremi Boole totolojilerdir Boole cebri kişilerce ve benzerleri, Boole terimler Boole sabit 1. diğer bir şekli için eşit olan, izleyen taşı sıradan olarak iki tür bir öneri bulunmaktadır, önermeler hesabı ve AB , AC ,... A , BC ,... gibi diziler adı verilen önerme listeleri çiftleri. Bir dizinin iki yarısına sırasıyla öncül ve ardıl denir. Bir öncülü veya bunun bir kısmını gösteren alışılmış metadeğişken Γ'dir ve bir sonraki Δ için; bu nedenle Γ, A Δ, ardılı Δ listesi ve öncülü bir liste Γ olan bir diziyi, ardından ek bir A önermesi ekleyen bir diziyi belirtir . Önceki kendi önermeler bağlantılı olarak, önermeler ayrılmasının olarak succedent ve aynı sequent kendisi olarak yorumlanır gerektirme öncülün succedent arasında.

Gerektirme, imadan farklıdır, çünkü ikincisi bir Boole cebrinde bir değer döndüren ikili bir işlem iken, birincisi, geçerli olan veya olmayan bir ikili ilişkidir . Bu anlamda gerektirme olarak bir olduğunu harici harici olmak ve yorumlama ve bazı Boole cebir öncellerini ve succedents karşılaştırarak olarak sequent ait okuyucunun düşünerek Boole cebir dış anlamına içerme formu. Doğal yorumlanması ile tanımlanan Boole cebri kısmi sırayla ≤ gibidir xy sadece Xy = Y . Bu dış çıkarım ve iç çıkarımı → tek bir mantıkta karıştırma yeteneği, ardışık hesap ile önermeler hesabı arasındaki temel farklardan biridir.

Uygulamalar

Boole cebri, iki değerin hesabı olarak bilgisayar devreleri, bilgisayar programlama ve matematiksel mantık için temeldir ve ayrıca küme teorisi ve istatistik gibi matematiğin diğer alanlarında da kullanılır.

bilgisayarlar

20. yüzyılın başlarında, birkaç elektrik mühendisi, Boole cebrinin belirli elektrik devrelerinin davranışına benzer olduğunu sezgisel olarak anladı. Claude Shannon , 1937'de yazdığı A Symbolic Analysis of Relay and Switching Circuits adlı yüksek lisans tezinde bu tür davranışların mantıksal olarak Boole cebrine eşdeğer olduğunu resmen kanıtladı .

Günümüzde tüm modern genel amaçlı bilgisayarlar işlevlerini iki değerli Boolean mantığı kullanarak gerçekleştirmektedir; yani elektrik devreleri, iki değerli Boole mantığının fiziksel bir tezahürüdür. Bunu çeşitli yollarla başarırlar : yüksek hızlı devrelerdeki ve kapasitif depolama aygıtlarındaki kablolardaki voltajlar, ferromanyetik depolama aygıtlarındaki manyetik alanın yönelimleri, delikli kartlardaki veya kağıt bantlardaki delikler vb. (Bazı eski bilgisayarlar, iki değerli mantık devreleri yerine ondalık devreler veya mekanizmalar kullandı.)

Elbette, herhangi bir ortamda ikiden fazla sembolü kodlamak mümkündür. Örneğin, bir tel üzerinde dört sembollü bir alfabeyi veya delikli bir kartta farklı boyutlardaki delikleri kodlamak için sırasıyla 0, 1, 2 ve 3 volt kullanılabilir. Uygulamada, yüksek hız, küçük boyut ve düşük güç gibi sıkı kısıtlamalar, gürültüyü önemli bir faktör haline getirmek için bir araya gelir. Bu, tek bir sitede meydana gelebilecek birkaç olası sembol olduğunda, semboller arasında ayrım yapmayı zorlaştırır. Dijital tasarımcılar, bir kablodaki dört voltajı ayırt etmeye çalışmak yerine, kablo başına yüksek ve düşük olmak üzere iki voltaja karar verdiler.

Bilgisayarlar, yukarıdaki nedenlerle iki değerli Boolean devreleri kullanır. En yaygın bilgisayar mimarileri, 32 veya 64 değerden oluşan, bit adı verilen sıralı Boole değerleri dizilerini kullanır, örneğin 01101000110101100101010101001011. Makine kodunda , montaj dilinde ve diğer bazı programlama dillerinde programlama yaparken, programcılar, sistemin düşük seviyeli dijital yapısıyla çalışır. veri kayıtları . Bu kayıtlar, sıfır voltun Boolean 0'ı temsil ettiği ve bir referans voltajının (genellikle +5 V, +3.3 V, +1.8 V) Boolean 1'i temsil ettiği voltajlarda çalışır. Bu tür diller hem sayısal işlemleri hem de mantıksal işlemleri destekler. Bu bağlamda "sayısal", bilgisayarın bit dizilerini ikili sayılar (temel iki sayı) olarak ele aldığı ve toplama, çıkarma, çarpma veya bölme gibi aritmetik işlemleri yürüttüğü anlamına gelir . "Mantıksal", bir dizideki her bitin diğer dizideki karşılığıyla basit bir şekilde karşılaştırıldığı, iki bit dizisi arasındaki ayrılma, birleşme ve olumsuzlamanın Boole mantıksal işlemlerini ifade eder. Bu nedenle programcılar, gerektiğinde sayısal cebir veya Boolean cebirinin kurallarında çalışma ve uygulama seçeneğine sahiptir. Bu işlem aileleri arasındaki temel ayırt edici özellik , birincide taşıma işleminin var olması, ikincisinde olmamasıdır.

İki değerli mantık

İki değerin iyi bir seçim olduğu diğer alanlar ise hukuk ve matematiktir. Günlük rahat konuşmalarda, "belki" veya "sadece hafta sonu" gibi nüanslı veya karmaşık cevaplar kabul edilebilir. Hukuk mahkemesi veya teorem temelli matematik gibi daha odaklı durumlarda, ancak soruları basit bir evet veya hayır cevabını kabul edecek şekilde çerçevelemek avantajlı kabul edilir - davalı suçlu mu suçsuz mu, önerme doğru mu yanlış mı - ve başka herhangi bir cevaba izin vermemek. Bu, pratikte davalı için ne kadar deli gömleği olursa olsun, basit evet-hayır sorusu ilkesi, hem yargısal hem de matematiksel mantığın merkezi bir özelliği haline geldi ve iki değerli mantığı kendi başına örgütlenmeyi ve çalışmayı hak ediyor.

Küme teorisinin merkezi bir kavramı üyeliktir. Artık bir kuruluş, acemi, ortak ve tam üyelik gibi birden çok üyelik derecesine izin verebilir. Ancak kümelerde bir eleman ya içeride ya da dışarıdadır. Bir kümeye üyelik adayları, tıpkı dijital bir bilgisayardaki teller gibi çalışır: her bir aday, her telin yüksek veya düşük olması gibi, üyedir veya üye değildir.

Cebir, matematiksel işleme uygun herhangi bir alanda temel bir araç olduğundan, bu düşünceler, bilgisayar donanımı, matematiksel mantık ve küme teorisi için temel öneme sahip iki değerin cebirini yapmak için birleşir.

İki değerli mantık , özellikle {0, 1} Boole etki alanını [0,1] birim aralığıyla değiştirerek, çok değerli mantığa genişletilebilir ; bu durumda, yalnızca 0 veya 1 değerlerini almak yerine, ve arasındaki herhangi bir değeri alır. 0 ve 1 dahil kabul edilebilir. Cebirsel olarak, olumsuzlama (NOT) 1 - x ile değiştirilir  , bağlaç (VE) çarpma ( ) ile değiştirilir ve ayrılma (OR) De Morgan yasası ile tanımlanır . Bu değerleri mantıksal doğruluk değerleri olarak yorumlamak , bulanık mantık ve olasılıklı mantık için temel oluşturan çok değerli bir mantık verir . Bu yorumlarda, bir değer, doğruluğun "derecesi" olarak yorumlanır - bir önermenin ne ölçüde doğru olduğu veya önermenin doğru olma olasılığı.

Boole işlemleri

Boolean işlemleri için orijinal uygulama , bireysel formüllerin doğru veya yanlış doğruluk değerlerini birleştirdiği matematiksel mantıktı .

Doğal lisan

İngilizce gibi doğal diller, özellikle bağlaç ( ve ), ayırma ( veya ), olumsuzlama ( değil ) ve ima ( ima eder ) olmak üzere çeşitli Boolean işlemleri için sözcüklere sahiptir . Ama değil ve değil ile eş anlamlıdır . Safça doğru ya da yanlış olan "blok masanın üzerinde" ve "kediler süt içer" gibi durumsal iddiaları birleştirmek için kullanıldığında, bu mantıksal bağlaçların anlamları genellikle mantıksal karşılıklarının anlamını taşır. Bununla birlikte, "Jim kapıdan yürüdü" gibi davranış açıklamalarıyla, örneğin "Jim kapıyı açtı" ile "Jim kapıdan yürüdü" ifadesinin birleşimi gibi değişkenlik başarısızlığı gibi farklılıklar fark edilmeye başlar. diğer sıradaki bağlaçlarına eşdeğer değildir, çünkü ve genellikle bu gibi durumlarda ve sonra anlamına gelir . Sorular benzer olabilir: "Gökyüzü mavi mi ve gökyüzü neden mavi?" ters sıralamadan daha mantıklı. Davranışla ilgili birleşik komutlar, giyin ve okula git gibi davranışsal iddialar gibidir . Beni sev ya da bırak ya da balık tut ya da yemi kes gibi ayrık komutlar , bir alternatifin daha az tercih edildiği ima yoluyla asimetrik olma eğilimindedir. Çay ve süt gibi birleşik isimler genellikle kümelemeyi, çay veya süt bir seçim iken küme birliği ile tanımlar . Bununla birlikte , seçimlerinizde kahve ve çay olduğu gibi bağlam bu duyuları tersine çevirebilir, bu da genellikle seçimlerinizin kahve veya çay (alternatifler) ile aynı anlama gelir . "Sütü sevmiyorum"da olduğu gibi çifte olumsuzlama nadiren kelimenin tam anlamıyla "süt severim" anlamına gelir, daha ziyade üçüncü bir olasılığın olduğunu ima ediyormuş gibi bir tür riskten korunma sağlar. "P değil", gevşek bir şekilde "kesinlikle P" olarak yorumlanabilir ve P mutlaka " P değil" anlamına gelse de, sezgisel mantıkta olduğu gibi İngilizce'de de tersi şüphelidir . Doğal dillerde bağlaçların son derece kendine özgü kullanımı göz önüne alındığında, Boole cebri, onları yorumlamak için güvenilir bir çerçeve olarak kabul edilemez.

Dijital mantık

Boolean işlemleri, dijital mantıkta , bireysel teller üzerinde taşınan bitleri birleştirmek ve böylece onları {0,1} üzerinden yorumlamak için kullanılır. Her biri n bitlik iki bit vektörünü birleştirmek için n özdeş ikili kapıdan oluşan bir vektör kullanıldığında , bireysel bit işlemleri toplu olarak 2 n elemanlı bir Boole cebrindeki değerler üzerinde tek bir işlem olarak anlaşılabilir .

Naif küme teorisi

Naif küme teorisi, Boole işlemlerini belirli bir X kümesinin alt kümeleri üzerinde hareket ediyor olarak yorumlar . Daha önce gördüğümüz gibi, bu davranış, iki bit vektörünün ayrılmasına tekabül eden iki kümenin birleşimi ile bit vektörlerinin koordinat bazındaki kombinasyonlarıyla tam olarak paraleldir.

ekran kartları

Üç jeneratör üzerindeki 256 elemanlı serbest Boole cebri, piksellerden oluşan tüm bölgeleri işlemek için bit blit kullanan raster grafiklere dayalı bilgisayar ekranlarında konuşlandırılır ve kaynak bölgenin hedefle, tipik olarak nasıl birleştirilmesi gerektiğini belirtmek için Boolean işlemlerine dayanır. maske adı verilen üçüncü bir bölge yardımıyla . Modern video kartları  , bu amaç için tüm 2 2 3 = 256 üçlü işlemi sunar ve işlem seçimi bir bayt (8-bit) parametredir. SRC = 0xaa veya 10101010, DST = 0xcc veya 11001100 ve MSK = 0xf0 veya 11110000 sabitleri, (SRC^DST)&MSK (kaynak ve hedef XOR ve ardından VE maske ile sonuç anlamına gelir) gibi Boole işlemlerinin yazılmasına izin verir. doğrudan derleme zamanında hesaplanan bir baytı gösteren bir sabit olarak, (SRC^DST)&MSK örneğinde 0x60, yalnızca SRC^DST ise 0x66, vb. Çalışma zamanında video kartı, baytı orijinal ifadeyle belirtilen tarama işlemi olarak yorumlar dikkate değer ölçüde az donanım gerektiren ve ifadenin karmaşıklığından tamamen bağımsız olarak zaman alan tek tip bir şekilde.

Modelleme ve CAD

Bilgisayar destekli tasarım için katı modelleme sistemleri , diğer nesnelerden nesneler oluşturmak için çeşitli yöntemler sunar; Boolean işlemleri bunlardan biridir. Bu yöntemde ana kadar hangi nesnelerin uzay kümesi olarak anlaşılır S ve voksel ve şekillerde (iki boyutlu grafik piksel üç boyutlu analog) alt kümeleri olarak tanımlanan S nesneleri birliği ile set olarak birleştirilebilir sağlayan, kavşak, vb. Açık bir kullanım, basit şekillerden karmaşık bir şekil oluşturmak, basitçe ikincisinin birleşimi olarak oluşturmaktır. Başka bir kullanım, malzemenin çıkarılması olarak anlaşılan yontma işlemidir: Fiziksel makinelerle fiziksel malzemeler üzerinde gerçekleştirilebilen herhangi bir taşlama, frezeleme, yönlendirme veya delme işlemi, bilgisayarda Boolean işlemi x  ¬ ¬ y veya x  −  y ile simüle edilebilir , grubu fark resim teoride olan unsurları kaldırmak y olanlardan x . Böylece, biri işlenecek ve diğeri çıkarılacak malzeme olmak üzere iki şekil verildiğinde, ikincisini çıkarmak için birincinin işlenmesinin sonucu basitçe bunların set farkı olarak tanımlanır.

Boole aramaları

Arama motoru sorguları ayrıca Boole mantığını kullanır. Bu uygulama için İnternet'teki her web sayfası bir "küme"nin "öğesi" olarak kabul edilebilir. Aşağıdaki örnekler, Google tarafından desteklenen bir sözdizimi kullanır .

  • Çift tırnak, boşlukla ayrılmış kelimeleri tek bir arama teriminde birleştirmek için kullanılır.
  • Boşluk, arama terimlerini birleştirmek için varsayılan operatör olduğundan mantıksal VE belirtmek için kullanılır:
"Search term 1" "Search term 2"
  • OR anahtar sözcüğü, mantıksal OR için kullanılır:
"Search term 1" OR "Search term 2"
  • Mantıksal NOT için ön ekli bir eksi işareti kullanılır:
"Search term 1" −"Search term 2"

Ayrıca bakınız

Referanslar

Kaynaklar

daha fazla okuma

  • J. Eldon Whitesitt (1995). Boole cebri ve uygulamaları . Kurye Dover Yayınları. ISBN'si 978-0-486-68483-3. Uygulamalı alanlarda öğrenciler için uygun tanıtım.
  • Dwinger, Philip (1971). Boole cebirlerine giriş . Würzburg: Fizik Verlag.
  • Sikorski, Roman (1969). Boole Cebirleri (3/e ed.). Berlin: Springer-Verlag. ISBN'si 978-0-387-04469-9.
  • Bochenski, Józef Maria (1959). Matematiksel Mantığın Bir Précis . Otto Bird tarafından Fransızca ve Almanca baskılardan çevrilmiştir. Dordrecht, Güney Hollanda: D. Reidel.

Tarihi bakış açısı

Dış bağlantılar