Kanonik olarak tanımlanmış Boole cebirleri - Boolean algebras canonically defined

Boole cebirleri, iki değerin denklem teorisinin modelleridir; bu tanım kafes ve halka tanımlarına eşdeğerdir.

Boole cebri , soyut cebirin matematiksel olarak zengin bir dalıdır . Gibi grup teorisi ile fiyatları grupları ve lineer cebir ile vektör uzayı , Boole cebir modellerdir equational teori iki değer (ki yorumlanması gerekir sayısal vermeye), 0 ve 1 arasında. Boole cebirleri, grupları ve vektör uzaylarında ortak olan, bir cebirsel yapı kavramıdır, belirli denklemleri karşılayan sıfır veya daha fazla işlem altında kapalı bir küme .

Bu tür bir grup gibi grupların örnekleri arasında, temel vardır gibi $Z$ bir tamsayı ve permütasyon grubu $S, n$ ve permütasyon arasında $N$ nesne, aynı zamanda, temel Boolean örnekleri aşağıdaki gibi cebri gibi vardır.

Ayrılma, birleşim ve olumsuzlama dahil olmak üzere mantıksal işlemler altındaki 0 ve 1 bitlerinin veya ikili rakamların cebiri . Uygulamalar önermeler hesabını ve dijital devreler teorisini içerir .
Kümeler cebiri dahil seti operasyonları altında birlik , kavşak ve tamamlayıcı . Uygulamalar, kümelerin doğal bir temel oluşturduğu herhangi bir matematik alanını içerir .

Boole cebri böylece yöntemlerini uygulayarak izin soyut cebir için matematiksel mantık , dijital mantık ve küme-teorik matematik temellerine .

Karmaşıklık ve çeşitlilik sergileyen ve birinci mertebeden teorisi sadece özel durumlarda kararlaştırılabilen sonlu mertebeden grupların aksine , tüm sonlu Boole cebirleri aynı teoremleri paylaşır ve karar verilebilir bir birinci mertebe teorisine sahiptir. Bunun yerine, Boole cebrinin karmaşıklıkları, sonsuz cebirlerin yapısı ile sözdizimsel yapılarının algoritmik karmaşıklığı arasında bölünür .

Tanım

Boole cebri , Boole prototipi olarak adlandırılan maksimal iki elemanlı sonlu cebirin denklem teorisini ve Boole cebri adı verilen bu teorinin modellerini ele alır . Bu terimler aşağıdaki gibi tanımlanır.

Bir cebir bir olan aile cebirin temel kümesi denilen bir sette operasyonların,. Boole prototipinin temel kümesini {0,1} olarak alıyoruz.

Bir cebir sonlucu iştiraklarının her sadece sonlu sayıda argüman alır zaman. Prototip için, bir işlemin her argümanı, işlemin sonucu olarak $0$ veya $1'dir$ . Bu tür cebir, {0,1} üzerindeki tüm sonlu işlemlerden oluşur.

Her işlem tarafından alınan argümanların sayısına işlemin aritesi denir . {0,1} arity $n$ veya $n$ -ary işlemi üzerinde bir işlem, $n$ bağımsız değişkeni için $2 n$ olası değerden herhangi birine uygulanabilir . Her bağımsız değişken seçimi için, işlem $0$ veya $1$ döndürebilir , bu nedenle $2$ $2$ $n$ $n$ -ary işlem vardır.

Prototip nedenle denilen hiçbir argüman alarak iki faaliyet göstermektedir zeroary veya nullary işlemler, yani sıfır ve bir. Dört tekli işlemi vardır , bunlardan ikisi sabit işlemler, diğeri kimliktir ve olumsuzlama adı verilen en sık kullanılanı argümanının tersini döndürür: $1$ if $0$ , $0$ if $1$ . On altı ikili işlemi vardır ; yine bunlardan ikisi sabittir, diğeri ilk argümanını döndürür, diğeri ikincisini döndürür, birine bağlaç denir ve her iki argüman da 1 ve aksi takdirde 0 ise 1 döndürür , diğerine disjunction denir ve her iki argüman da 0 ve aksi takdirde 1 ise 0 döndürür , ve bunun gibi. Sayısı $(n + 1)$ prototip -ary işlem sayısının kare $n$ böylece, orada -ary işlemleri $162 = 256$ üçlü işlemleri, $2562 = 65.536$ kuaterner işlemler, vb.

Bir aile , bir indeks seti tarafından indekslenir . Bir cebir oluşturan bir işlem ailesi durumunda, indislere o cebirin dilini oluşturan işlem sembolleri denir . Her sembolün indekslediği işleme , o sembolün anlamı veya yorumu denir . Her işlem sembolü, yorumunun aritesini belirtir, bu nedenle bir sembolün tüm olası yorumları aynı ariteye sahiptir. Genel olarak bir cebirin farklı sembolleri aynı işlemle yorumlaması mümkündür, ancak sembolleri işlemleriyle birebir örtüşen prototip için durum böyle değildir. Bu nedenle prototip , Boolean işlem sembolleri olarak adlandırılan ve Boole cebrinin dilini oluşturan $2$ $2$ $n$ $n$ -ary işlem sembolüne sahiptir . Yalnızca birkaç işlem, olumsuzlama için $\neg$ , bağlaç için $\land$ ve ayırma için $\lor$ gibi geleneksel simgelere sahiptir . Aşağıdaki doğruluk tabloları bölümünde yapıldığı gibi $i$ -inci $n$ -ary sembolünün $n$ $f$ $i$ olduğunu düşünmek uygundur .

Belirli bir dilde bir denklem teorisi , o dilin sembollerini kullanan değişkenlerden oluşturulan terimler arasındaki denklemlerden oluşur. Boole cebri dilinde tipik denklemler $x \land y = Y \land X$ , $X \land X = X$ , $X \land\neg x = y \land\neg y$ ve $x \land y = x$ .

Bir cebir , işlem sembolleri o cebir tarafından belirtildiği gibi yorumlandığında, denklem o cebirdeki değişkenlerinin tüm olası değerleri için geçerli olduğunda bir denklemi karşılar . Boole cebrinin yasaları, prototip tarafından karşılanan Boole cebri dilindeki denklemlerdir. Yukarıdaki örneklerin ilk üçü Boole yasalarıdır, ancak $1\land0 \neq 1'den$ beri dördüncü değil .

Equational teori bir cebir cebir memnun tüm denklemlerin kümesidir. Boole cebri yasaları bu nedenle Boole prototipinin denklem teorisini oluşturur.

Bir teorinin modeli, teorinin dilindeki işlem sembollerini yorumlayan ve teorinin denklemlerini sağlayan bir cebirdir.

Boole cebri, Boole cebri yasalarının herhangi bir modelidir.

Yani, bir Boole cebri, Boolean işlem sembollerini yorumlayan ve Boole prototipiyle aynı yasaları karşılayan bir küme ve bunun üzerindeki işlemler ailesidir.

Bir cebirin homologunu o cebirin denklem teorisinin bir modeli olarak tanımlarsak, o zaman Boolean cebiri prototipin herhangi bir homologu olarak tanımlanabilir.

Örnek 1 . Boole prototipi bir Boole cebiridir, çünkü önemsiz bir şekilde kendi yasalarını karşılar. Bu nedenle prototipik Boole cebiridir. Tanımda herhangi bir döngüsellik görünümünden kaçınmak için başlangıçta böyle demedik.

temel

İşlemlerin hepsinin açıkça belirtilmesi gerekmez. Bir baz kalan işlemler bileşim ile elde edilebilir olan herhangi bir kümesidir. Bir "Boole cebiri", birkaç farklı bazın herhangi birinden tanımlanabilir. Boole cebri için yaygın olarak kullanılan üç temel vardır: kafes temeli, halka temeli ve Sheffer vuruşu veya NAND temeli. Bu temeller özneye sırasıyla mantıksal, aritmetik ve cimri bir karakter kazandırır.

Kafes temeli çalışmasından 19. yüzyılda kökenli Boole , Peirce mantıksal düşünce süreçlerinin bir cebirsel kayıtlılığın arayan ve diğerleri.
Halka temeli çalışmasından 20. yüzyılda ortaya çıkan Zhegalkin ve Stone ve bir arka plandan konusuna gelmeden algebraists için seçim temeli haline soyut cebir . Boolean cebrinin çoğu tedavisi kafes tabanını kabul eder, dikkate değer bir istisna , lineer cebir arka planı ona halka tabanını sevdiren Halmos'tur [1963].
{0,1} tüm sonlucu işlemleri açısından tanımlanabilir yana Sheffer inme NAND (veya çift NOR), elde edilen, ekonomik temel analiz için tercih edilen bir temeli haline gelmiştir dijital devreler , özellikle kapı dizileri de dijital elektronik .

Kafes ve halka tabanlarının ortak elemanları, 0 ve 1 sabitleri ve kafes bazında $x$ $\land$ $y ile$ tanış ve halka bazında $xy$ çarpımı olarak adlandırılan bir ilişkisel değişmeli ikili işlemdir . Ayrım sadece terminolojiktir. Kafes taban ayrıca aşağıdaki işlemleri vardır birleştirme , $X$ $\lor$ $y$ ve tamamlayıcı , $\neg$ $x$ . Halka baz yerine aritmetik işlem vardır $X$ $\oplus$ $y$ ve ilave (sembol $\oplus$ tercih kullanılan $+$ ikinci zaman birleştirme Boole okuma verilmiştir için).

Temel olmak, herhangi iki bazın çevrilebilir olması gerektiğinden, bileşime göre tüm diğer işlemleri vermektir. Kafes baz çevirir $x \lor y$ gibi halka esasına $x \oplus y \oplus xy$ ve $\neg X$ olarak $x \oplus1$ . Tersine halka baz çevirir $X \oplus y$ olarak kafes esasına $(x \lor y) \land\neg (x \land y)$ .

Bu tabanların her ikisi de Boole cebirlerinin, Boole işlemlerinin denklem özelliklerinin bir alt kümesi aracılığıyla tanımlanmasına izin verir. Kafes temeli için, bir Boole cebrini, $x$ $\land\neg$ $x$ $= 0$ ve $x$ $\lor\neg$ $x$ $= 1'i$ sağlayan bir dağıtımlı kafes olarak tanımlamak yeterlidir , buna tümleyen dağıtımlı kafes denir . Halka tabanı, bir Boole cebrini bir Boole halkasına , yani $x$ $2$ $=$ $x'i$ sağlayan bir halkaya dönüştürür .

Emil Post , bir dizi işlemin sıfırdan farklı Boolean işlemleri için temel olması için gerekli ve yeterli koşulu verdi. Bir nontrivial özellik bir temel oluşturan bazı tümünü değil operasyonlarda tarafından paylaşılan biridir. Post , her biri kompozisyonla korunan beş Post sınıfıyla tanımlanabilen, işlemlerin önemsiz olmayan beş özelliğini listeledi ve her bir özellik için küme bu özellikten yoksun bir işlem içeriyorsa, bir işlem kümesinin bir temel oluşturduğunu gösterdi. (Post'un teoreminin, "eğer"i " eğer ve sadece eğer"e genişleten tersi, aday bazında her işlemin bu beş tutmasından bir özelliğin, o adaydan kompozisyon tarafından oluşturulan her işlemi de tutacağının kolay gözlemidir. , bu özelliğin önemsizliği nedeniyle aday bir temel teşkil edemez.) Post'un beş özelliği şunlardır:

monoton , 0-1 giriş geçişi olmaması 1-0 çıkış geçişine neden olabilir;
afin , bilineer veya daha yüksek terimlerden yoksun Zhegalkin polinomlarıyla temsil edilebilir , örneğin $x \oplus y \oplus1$ ama $xy$ değil ;
self-dual , böylece tüm girdilerin tamamlanması, $x$ , medyan operatör $xy \oplus yz \oplus zx$ veya bunların olumsuzlamalarında olduğu gibi çıktıyı tamamlar ;
katı (tamamen sıfır girdisini sıfıra eşleme);
costrict (hepsini bire eşleme).

NAND (ikili olarak NOR) işlemi böylece tek başına bir temel oluşturan tüm bu yoksundur.

doğruluk tabloları

{0,1} üzerindeki sonlu işlemler doğruluk tabloları olarak gösterilebilir , 0 ve 1 doğruluk değerleri false ve true olarak düşünülür . Bunları tek tek adlandırmamıza veya en azından numaralandırmamıza izin veren tek tip ve uygulamadan bağımsız bir şekilde düzenlenebilirler. Bu adlar, Boolean işlemleri için uygun bir kısayol sağlar. $n$ -ary işlemlerinin adları $2 n$ bitlik ikili sayılardır . Böyle $2 2 n$ işlem olduğu için, daha özlü bir isimlendirme istenemez. Her sonlu işlemin bir anahtarlama işlevi olarak adlandırılabileceğini unutmayın .

Bu düzen ve ilgili operasyonların adlandırılması, burada 0'dan 2'ye kadar olan ariteler için tam olarak gösterilmektedir.

2'ye kadar olan Boolean işlemleri için doğruluk tabloları

sabitler
${}^{0}\!f_{0}$	${\görüntüleme stili {}^{0}\!f_{1}}$
0	1

tekli işlemler
${\görüntüleme stili x_{0}}$	${}^{1}\!f_{0}$	${\görüntüleme stili {}^{1}\!f_{1}}$	${}^{1}\!f_{2}$	${}^{1}\!f_{3}$
0	0	1	0	1
1	0	0	1	1

ikili işlemler
${\görüntüleme stili x_{0}}$	${\görüntüleme stili x_{1}}$	${}^{2}\!f_{1}$	${}^{2}\!f_{2}$	${}^{2}\!f_{3}$	${}^{2}\!f_{4}$	${}^{2}\!f_{5}$	${}^{2}\!f_{6}$	${}^{2}\!f_{7}$	${}^{2}\!f_{8}$	${}^{2}\!f_{9}$	${}^{2}\!f_{10}$	${}^{2}\!f_{11}$	${}^{2}\!f_{12}$	${}^{2}\!f_{13}$	${}^{2}\!f_{14}$	${}^{2}\!f_{15}$
0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
0	1	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	1	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

Bu tablolar ile daha yüksek arities devam $2 N$ Arity içinde sıralar $, n$ , her satır bir değerleme veren ya da bağlanma $, n$ değişkenleri $X 0, ... x, n -1$ ve her sütun başlı $N f i$ değerini veren $N f i (x 0, ..., x, n -1)$ arasında $i$ inci $n$ bu değerleme -ary işlem. İşlemler, örneğin, değişkenleri içeren $1 f 2$ olduğu $X 0$ ise $2 f, 10$ olan $X 0$ (ikisi, tekli muadili kopyaları gibi) ve $2 f 12$ olan $x 1$ (bir tekli muadili ile). Eksi işareti ya da tamamlayıcı $\neg x 0$ görünür olarak $1 f 1$ ve tekrar olarak $2 f 5$ ile birlikte, $2 f 3$ ( $\neg x 1$ , Arity 1 görünür değil), ayrılma ya da birlik $x 0 \lor x 1$ olarak $2 f, 14$ , birlikte veya kavşak $x 0 \land x 1$ olarak $2 f, 8$ , içerim $x 0 \to x 1 olarak 2 f 13$ , özel veya simetrik fark $x 0 \oplus x 1$ olarak $2 f, 6$ , ayar fark $x 0 - x 1$ olarak $2 f 2$ , ve bunun gibi.

İçeriğinden çok biçiminden daha önemli olan küçük bir ayrıntı olarak, bir cebirin işlemleri geleneksel olarak bir liste halinde düzenlenir. Burada {0,1} üzerindeki sonlu işlemlerle bir Boole cebrinin işlemlerini indeksliyor olmamıza rağmen, yukarıdaki doğruluk tablosu sunumu tesadüfen işlemleri ilk olarak arity ve ikinci olarak her arity için tabloların düzeni ile sıralar. Bu, tüm Boolean işlemleri kümesinin geleneksel liste biçiminde düzenlenmesine izin verir. Belirli bir aritenin işlemleri için liste sırası aşağıdaki iki kuralla belirlenir.

(i) Tablonun sol yarısındaki

i

-inci satır,

i'nin

en az anlamlısı veya

0

-inci biti solda olacak şekilde ikili gösterimidir ("küçük-endian" düzeni, orijinal olarak Alan Turing tarafından önerilmiştir , yani Turing düzeni olarak adlandırmak mantıksız olmaz).

(ii)

j

tablonun sağ yarısında inci kolon ikili temsilidir

j

küçük endian sırada yeniden. Aslında operasyonun alt simge olduğunu o operasyonun doğruluk tablosu. Hesaplanabilir fonksiyonların Gödel numaralandırmasına benzetilerek , Boole işlemlerinin bu numaralandırılması Boole numaralandırması olarak adlandırılabilir.

C veya Java'da programlama yaparken, bit düzeyinde ayrılma belirtilir x | y, bağlaç x ve y, ve olumsuzlama ~ x. Bu nedenle bir program, örneğin $x \land(y \lor z) işlemini$ bu dillerde şu şekilde temsil edebilir:x &( y | z ), önceden ayarlanmış x = 0xaa, y = 0xcc, ve z = 0xf0 (NS "0x", aşağıdaki sabitin, değişkenlere atanarak veya makrolar olarak tanımlanarak onaltılık veya taban 16'da okunacağını belirtir. Bu bir baytlık (sekiz bit) sabitler, uzantıdaki giriş değişkenleri için sütunlara karşılık gelir. Bu teknik, görüntüleri birleştirmek ve maskelemek için esnek çeşitli yollar sağlamak için raster grafik donanımında neredeyse evrensel olarak kullanılır, tipik işlemler üçlüdür ve kaynak, hedef ve maske bitleri üzerinde aynı anda hareket eder.

Örnekler

Bit vektörleri

Örnek 2 . Belirli bir uzunluktaki tüm bit vektörleri , "noktasal" bir Boole cebrini oluşturur; bu, herhangi bir $n$ -ary Boole işleminin bir seferde bir bit konumunda $n$ bit vektörlerine uygulanabileceği anlamına gelir . Örneğin, her biri uzunluk 4 olan üç bit vektörünün üçlü $OR'si$ , dört bit konumunun her birinde üç bitin $oringlenmesiyle$ oluşturulan uzunluk 4 bit vektörüdür, dolayısıyla $0100~1000~1001 = 1101$ . Diğer bir örnek, sütunlarının tümü $2$ $n$ uzunluğundaki bit vektörleri olan ve bu nedenle $n$ -ary işlemlerinin bir Boole cebrini oluşturduğu noktadan birleştirilebilir olan $n$ -ary işlemleri için yukarıdaki doğruluk tablolarıdır . Bu, sonlu ve sonsuz uzunluktaki bit vektörleri için eşit derecede iyi çalışır, tek kural, "karşılık gelen konumun" iyi tanımlanabilmesi için bit konumlarının hepsinin aynı küme tarafından indekslenmesidir.

Atomları , böyle bir cebir tam olarak bir 1. Bir Boole cebri atomuna, genel olarak ihtiva eden bit vektörleri olan elemanlardır $x$ öyle ki $X \land y$ sadece iki değeri vardır $x$ ya da $0$ .

Güç kümesi cebiri

Örnek 3 . Güç grubu cebri , grubu $2 B$ , belirli bir resim her altkümelerinin $W$ . Bu sadece kılık değiştirmiş Örnek 2'dir ve $W$ , bit konumlarını indekslemeye hizmet eder. Herhangi bir alt kümesi, $X'in$ bir $W$ elemanları tarafından dizine sadece bu bit konumu 1 's olan bit vektörü olarak izlenebilir $X$ . Bu nedenle, tümü-sıfır vektörü, $W'nin$ boş alt kümesi iken, tümü-birler vektörü $W'nin$ kendisidir, bunlar sırasıyla güç kümesi cebirinin 0 ve 1 sabitleridir. Ayrılma bölgesinin karşılık $X \lor y$ birlik $X \cup Y$ , birlikte bu ise $X \land y$ kesişimidir $X \cap Y$ . Eksi işareti $\neg x$ olur $~ x$ , göre tamamlayıcı $W$ . Ayrıca $X ∖ Y = X \cap~ Y$ , simetrik fark $(X ∖ Y)\cup(Y ∖ X)$ , üçlü birleşim $X \cup Y \cup Z$ vb. Buradaki atomlar tekillerdir, tam olarak bir element içeren alt kümelerdir.

Örnek 2 ve 3 özel cebir denilen genel bir yapının durumlardır doğrudan ürüne vb herhangi aile doğrudan ürüne sadece Bole cebirleri için geçerli, ancak cebir dahil grupların her türlü, yüzük, $B i$ nerede Boole Cebirlerin $i$ üzerinde durulurken bazı indeks kümesi $I$ (sonlu veya hatta sayılabilir olması gerekmez $)$ , $i$ -inci öğesi $B$ $i$ öğesinden alınan tüm $I-$ tuplelerinden $(... x i,...)$ oluşan bir Boole cebridir . Doğrudan bir çarpımın işlemleri, kendi koordinatları içinde hareket eden kurucu cebirlerin karşılık gelen işlemleridir; Özellikle işlemde $N$ $f$ $j$ ürünün çalışır $n$ $I$ işlemi uygulanarak -tuples $N$ $f$ $j$ arasında $B$ $i$ için $, n$ elemanların $i$ koordinatı inci $n$ tüm, küpe $i$ içinde $I$ .

Tüm cebiri bu şekilde bir araya çarpıldıktan sonra aynı cebir $A$ biz doğrudan ürüne diyoruz doğrudan güç arasında $A$ . Tüm 32-bit bit vektörlerinin Boole cebri, 32. kuvvete yükseltilmiş iki elemanlı Boole cebri veya 32 elemanlı bir setin $232$ ile gösterilen kuvvet kümesi cebridir . Tüm tamsayı kümelerinin Boole cebri $2 Z'dir$ . Şimdiye kadar sergilediğimiz tüm Boole cebri, iki elemanlı Boole cebrinin doğrudan kuvvetleriydi ve "kuvvet kümesi cebri" adını haklı çıkardı.

temsil teoremleri

Her sonlu Boole cebrinin, bazı kuvvet kümesi cebrine eşbiçimli olduğu gösterilebilir . Dolayısıyla, sonlu bir Boole cebrinin kardinalitesi (eleman sayısı) $2'nin$ bir $kuvvetidir,$ yani $1,2,4,8,...,2$ $n$ $,...$ Bu, fikir verdiği için temsil teoremi olarak adlandırılır. kuvvet kümesi cebirleri olarak temsillerini vererek sonlu Boole cebirlerinin doğasına iner.

Bu temsil teoremi sonsuz Boole cebirlerini kapsamaz: her kuvvet kümesi cebri bir Boole cebri olsa da, her Boole cebrinin bir kuvvet kümesi cebrine eşbiçimli olması gerekmez. Özellikle, sayılabilir sonsuz kuvvet kümesi cebiri olamazken (en küçük sonsuz kuvvet kümesi cebiri, Cantor tarafından sayılamaz olarak gösterilen $2 N$ doğal sayı kümesinin kuvvet kümesi cebiridir ), çeşitli sayılabilir sonsuz Boole cebirleri vardır.

Kuvvet kümesi cebirlerinin ötesine geçmek için başka bir yapıya ihtiyacımız var. Bir alt cebiri bir cebir bir $A$ herhangi bir alt kümesi olup $, A$ işlemleri altında kapalı $A$ . Bir Boole cebri her alt cebiri $A$ hala tutma denklemleri yerine getirmelidir $A$ herhangi ihlali için ihlalini teşkil edeceğini, çünkü $A$ kendisi. Dolayısıyla bir Boole cebrinin her alt cebiri bir Boole cebridir.

Bir kuvvet kümesi cebirinin bir alt cebirine kümeler alanı denir ; eşdeğer setleri alan bir dizi alt-kümesidir $W$ boş dizi de dahil olmak üzere $W$ ve benzerleri ile ilgili sonlu birlik ve tamamlayıcı altında kapalı $W$ (sonlu kesişme altında bu nedenle de ve benzeri). Birkhoff'un [1935] Boole cebirleri için temsil teoremi, her Boole cebirinin bir kümeler alanına eşbiçimli olduğunu belirtir. Şimdi Birkhoff HSP teoremi çeşitleri için söylenebilir gibi bir sınıf denklemsel teorisinin modellerinin her sınıf $C$ cebirlerin a Homomorfik görüntüdür alt cebiri a direkt Ürününün ait Cebirlerin $C$ . Normalde H, S ve P'nin üçüne de ihtiyaç vardır; Bu iki Birkhoff teoreminden ilkinin gösterdiği şey, Boole cebirlerinin çeşitliliğinin özel durumu için Homomorfizmin İzomorfizm ile değiştirilebileceğidir . Genel olarak çeşitler için Birkhoff'un HSP teoremi, bu nedenle , Boole cebirlerinin çeşitliliği için Birkhoff'un ISP teoremi olur .

Diğer örnekler

Bir dizi X doğal sayı hakkında konuşurken , onu $x 0, x 1, x 2,...$ bit dizisi olarak görmek , $x i = 1$ ise ve sadece $i \in X$ ise kullanışlıdır . Bu bakış açısı daha kolay bahsetmek yapacak alt cebirlerine kuvvet kümesi cebiri içinde $2 N$ bu bakış açısı uçları her dizilerin Boolean matematiği yapar. Aynı zamanda doğruluk tablosunun sütunlarıyla da iyi uyum sağlar: bir sütun yukarıdan aşağıya okunduğunda bir dizi bit oluşturur, ancak aynı zamanda bu değerlemeler kümesi olarak da görülebilir (soldaki değişkenlere atamalar). sütunun temsil ettiği fonksiyonun 1 olarak değerlendirildiği tablonun yarısı).

Örnek 4 . Sonuçta sabit diziler . Nihai olarak sabit dizilerin herhangi bir Boole kombinasyonu nihai olarak sabittir; dolayısıyla bunlar bir Boole cebiri oluşturur. Bunları, nihai olarak sıfır dizileri negatif olmayan ikili sayılar ( dizinin $0$ biti düşük dereceli bittir) ve nihai olarak bir dizileri negatif ikili sayılar olarak görüntüleyerek tamsayılarla tanımlayabiliriz ( ikinin tümleyen aritmetiğini tüm- olanlar dizisi $-1$ ). Bu, tamsayıları bir Boole cebri yapar, birleşim bit düzeyinde VEYA ve tamamlayıcı $-x-1 olur$ . Yalnızca sayılabilir sayıda tamsayı vardır, dolayısıyla bu sonsuz Boole cebri sayılabilirdir. Atomlar iki kuvvettir, yani 1,2,4,.... Bu cebiri tanımlamanın başka bir yolu, tüm sonlu ve ortak sonlu doğal sayı kümelerinin kümesi olarak, nihai olarak hepsi-birler dizileri kosonluya karşılık gelir. kümeler, yalnızca sonlu sayıda doğal sayıyı atlayan kümeler.

Örnek 5 . Periyodik sıra . Tüm $i$ $\geq 0$ için $x$ $i$ $=$ $x$ $ben$ $+$ $n$ olacak şekilde , $n$ $> 0$ gibi bir sayı varsa , bir dizi periyodik olarak adlandırılır ve periyodikliğe tanık denir . Periyodik bir dizinin periyodu en az tanığıdır. Olumsuzlama, periyodu değiştirmeden bırakırken, iki periyodik dizinin ayrılması periyodiktir ve periyot, iki argümanın periyotlarının en az ortak katıdır (periyot , herhangi bir dizinin birleşiminde olduğu gibi $1$ kadar küçük olabilir ve onun Tamamlayıcı). Dolayısıyla periyodik diziler bir Boole cebiri oluşturur.

Örnek 5, sayılabilir olması bakımından Örnek 4'e benzer, ancak atomsuz olması bakımından farklıdır. İkincisi, sıfır olmayan herhangi bir periyodik $x$ dizisinin daha büyük bir periyot dizisiyle birleşiminin ne $0$ ne de $x olmasıdır$ . Tüm sayılabilir sonsuz atomsuz Boole cebirlerinin izomorfik olduğu gösterilebilir, yani izomorfizme kadar böyle bir cebir vardır.

Örnek 6 . Periyodun iki katı olan periyodik dizi . Bu, uygun bir bir alt cebiri (uygun bir alt cebiri onun cebri ile kendini kesişim eşittir), Örnek 5. Bunlar, böyle bir dizinin ilk periyodu temsil ettiği işlemin doğruluk tablosunu veren sonlu işlemler olarak anlaşılabilir. Örneğin, ikili işlemler tablosundaki $x 0$ doğruluk tablosu , yani $2 f 10$ , ikili işlemlerden 12'sinin $4$ periyodu olmasına rağmen $2.$ periyoda sahiptir (ve dolayısıyla sadece ilk değişkeni kullanıyor olarak kabul edilebilir) . Periyot $2$ $n olduğunda$ , işlem yalnızca ilk $n$ değişkene bağlıdır, bu da işlemin sonlu olduğu anlamına gelir. Bu örnek aynı zamanda sayılabilir sonsuz atomsuz bir Boole cebridir. Bu nedenle Örnek 5, kendisinin uygun bir alt cebirine eşbiçimlidir! Örnek 6 ve dolayısıyla Örnek 5, sayılabilir sayıda üreteç üzerinde serbest Boole cebrini oluşturur; bu, sayılabilir sonsuz bir üreteç veya değişken kümesi üzerindeki tüm sonlu işlemlerin Boole cebri anlamına gelir.

Örnek 7 . Nihai olarak periyodik diziler , başlangıçtaki sonlu bir kanunsuzluk nöbetinden sonra periyodik hale gelen diziler. Sabit diziler birinci periyotla periyodik olduğundan , Örnek 5'in (Örnek 5'in Örnek 7'nin uygun bir alt cebiri olduğu anlamına gelir ) ve ayrıca Örnek 4'ün uygun bir uzantısını oluştururlar . Diziler, ne zaman yerleştiklerine göre değişebilir, ancak herhangi bir sonlu dizi dizisinin tümü, sonunda, en yavaş yerleşen elemanlarından daha geç olmayacak şekilde, sonuçta periyodik diziler tüm Boolean işlemleri altında kapatıldığından ve böylece bir Boole cebiri oluşturur. Bu örnek, Örnek 4 ile aynı atomlara ve kotomlara sahiptir, bu nedenle atomsuz değildir ve dolayısıyla Örnek 5/6'ya göre izomorf değildir. Bununla birlikte, sonsuz atomsuz bir alt cebir , yani Örnek 5 içerir ve bu nedenle, her bir alt cebiri, sonlu kümelerin ve bunların tamamlayıcılarının ve dolayısıyla atomik bir Boolean cebiri olması gereken Örnek 4'e eşbiçimli değildir . Bu örnek, Örnek 4 ve 5'in doğrudan ürününe eşbiçimlidir ve bunun başka bir tanımını sağlar.

Örnek 8 . Periyodik Dizinin (Örnek 5) herhangi bir sonlu ancak önemsiz olmayan Boole cebiriyle doğrudan ürünü . (Önemsiz tek elemanlı Boole cebiri, benzersiz sonlu atomsuz Boole cebiridir.) Bu, hem atomlara hem de atomsuz bir alt cebire sahip olması bakımından Örnek 7'ye benzer , ancak yalnızca sonlu sayıda atoma sahip olması bakımından farklılık gösterir. Örnek 8 aslında sonsuz bir örnek ailesidir, her olası sonlu atom sayısı için bir tane.

Bu örnekler, sayılabilir olanlar dahil, olası Boole cebirlerini hiçbir şekilde tüketmez. Gerçekten de, Jussi Ketonen'in [1978] tamamen belirli kalıtsal olarak sayılabilir kümeler tarafından temsil edilebilen değişmezler cinsinden sınıflandırdığı, sayılamayacak kadar çok sayıda izomorfik olmayan sayılabilir Boole cebiri vardır.

Boole işlemlerinin Boole cebirleri

$N$ -ary Boolean işlemleri kendilerini güç grubu cebir teşkil $2 W$ , yani zaman, $W$ grubu olarak alınır $2 N$ değerlemesinin $N$ girişlerine. İşlemlerin adlandırma sistemi açısından $, n f i$ $i$ ikili bir doğruluk tablosundaki bir sütundur, sütunlar diğer sütunlar tablosunda mevcut üretmek için herhangi bir Arity Boole işlemleri ile kombine edilebilir. Olduğunu, biz Arity herhangi Boole işlemi uygulayabilirsiniz $m$ için $m$ Arity Boole işlemleri $n$ Arity bir Boole işlemi verecek şekilde $n$ herhangi biri için, $m$ ve $n$ .

Bu kuralın hem yazılım hem de donanım için pratik önemi, $n$ -ary Boolean işlemlerinin uygun uzunluktaki kelimeler olarak temsil edilebilmesidir. Örneğin, 256 üçlü Boole işleminin her biri imzasız bir bayt olarak temsil edilebilir. AND ve OR gibi mevcut mantıksal işlemler daha sonra yeni işlemler oluşturmak için kullanılabilir. Biz alırsak $x$ , $y$ ve $z$ için (şimdilik indisli değişkenlerle dağıtma) $10101010$ , $11.001.100$ ve $11110000$ (170, 204, ve ondalık bölgesi 240, sırasıyla $0xAA$ , $0xCC$ ve $0xf0$ , bunların ikili bağlaçlar olan onaltılı) $x \land y = 10001000$ , $y \land z = 11000000$ ve $z \land x = 10100000$ , ikili ayrımları ise $x \lor y = 11101110$ , $y \lor z = 11111100$ ve $z \lor x = 11111010'dur$ . Üç $bağlacın$ ayrımı $11101000'dir$ ve bu aynı zamanda üç ayrılığın birleşimidir. Bayt üzerinde bir düzine kadar mantıksal işlemle, iki üçlü işlemin

(x\land y)\lor (y\land z)\lor (z\land x)

ve

(x\lor y)\land (y\lor z)\land (z\lor x)

aslında aynı işlemdir. Yani, denklemsel özdeşliği kanıtladık.

(x\land y)\lor (y\land z)\lor (z\land x)=(x\lor y)\land (y\lor z)\land (z\lor x)

,

iki elemanlı Boole cebri için. "Boole cebri" tanımına göre bu özdeşlik bu nedenle her Boole cebrinde yer almalıdır.

Bu üçlü işlem tesadüfen Grau'nun [1947] bu işlem ve olumsuzlama açısından aksiyomlaştırdığı üçlü Boole cebirlerinin temelini oluşturdu. İşlem simetriktir, yani değeri $3'ten$ bağımsızdır $!$ $=$ Argümanlarının $6$ permütasyonu. $11101000$ doğruluk tablosunun iki yarısı $\lor$ , $1110$ ve $\land$ , $1000$ için doğruluk tablolarıdır , bu nedenle işlem sanki $z$ sonra $x \lor y$ başka $x \land y$ gibi ifade edilebilir . Simetrik olduğu için, if $x$ sonra $y \lor z$ else $y \land z$ veya if $y$ o zaman $z \lor x$ başka $z \land x şeklinde ifade edilebilir$ . 8 köşeli 3 küpün bir etiketi olarak bakıldığında, üst yarı 1 ve alt yarı 0 olarak etiketlenir; bu nedenle , herhangi bir tek sayıdaki değişkene açık bir genelleme ile medyan operatörü olarak adlandırılmıştır (değişkenlerin tam olarak yarısı 0 olduğunda bağdan kaçınmak için tek).

Boole cebirlerini aksiyomlaştırma

Boole cebrinin bir özdeşliğini kanıtlamak için az önce kullandığımız teknik , Boole mantığının denklem yasalarının sağlam ve eksiksiz bir aksiyomatizasyonu veya aksiyomatik sistemi olarak alınabilecek sistematik bir şekilde tüm kimliklere genelleştirilebilir . Bir aksiyom sisteminin geleneksel formülasyonu, aksiyomlardan ve daha önce kanıtlanmış özdeşliklerden kalan kimlikleri çıkarmak için bir dizi çıkarım kuralıyla birlikte bazı başlangıç kimlikleriyle "pompayı hazırlayan" bir aksiyom kümesinden oluşur. Prensipte, sonlu sayıda aksiyomun olması arzu edilir; ancak pratik bir mesele olarak gerekli değildir, çünkü burada izlediğimiz yaklaşım, her biri bir ispatta kullanıldığında yasal bir örnek olarak kolayca doğrulanabilen sonsuz sayıda örneğe sahip sonlu bir aksiyom şemasına sahip olmak kadar etkilidir .

Boolean kimlikler önesürümleri oluştururlar $s = t$ burada $s$ ve $t$ olan $, n$ burada değişkenler sınırlandırıcı terimler anlamına gelir hangi -ary terimler, $x 0$ ile $x, n-1$ . Bir $n$ -ary terimi ya bir atom ya da bir uygulamadır. Bir uygulama $m f i (t 0,..., t m -1)$ bir $m$ -ary işlemi $m f i$ ve bir liste veya $m -$ tuple $(t 0,..., t m -1$ $)$ içeren bir çifttir. $)$ ait $m, n$ adı -ary açısından işlenen .

Her terimle ilişkili, yüksekliği olarak adlandırılan doğal bir sayıdır . Atomlar sıfır yükseklikteyken, uygulamalar bir artı en yüksek işlenenin yüksekliğindedir.

Şimdi atom nedir? Geleneksel olarak, bir atom ya da bir sabit (0 ya da 1) ya da değişken $x i$ $0 \leq i < n$ . Burada izolasyon tekniği için olması yerine atomuna tanımlamak için uygun olan $, n$ -ary işlemleri $n f ı$ , ki atomuna yine aynen olağan koşulları ile aynı anlama olarak değerlendirilmektedir, ancak $n, f ı (x 0, ..., x n -1)$ (değişkenlerin tekrar veya atlama olmaksızın gösterilen sırada listelenmesi gerektiği için kesin). Bu bir kısıtlama değildir, çünkü bu formdaki atomlar tüm sıradan atomları, yani burada her $n$ için $n$ $f$ $0$ ve $n$ $f$ $-1$ gibi $n$ -ary işlemler olarak ortaya çıkan 0 ve 1 sabitlerini içerir (kısaltma $2$ $2$ $n$ $-1$ için $-1$ ) ve değişkenler $x$ $0$ $, ...,$ $x$ $, n$ $-1$ gerçek tablolardan görülebileceği gibi, burada $x$ $0$ tekli işlemi hem de görünür $1$ $f$ $, 2$ ve ikili işlem $2$ $f$ $10$ ise $x$ $1$ görünene olarak $2$ $f$ $12$ .

Aşağıdaki aksiyom şeması ve üç çıkarım kuralı, n -ary terimlerin Boole cebrini aksiyomatikleştirir .

A1 .

m f i (n f j 0,..., n f j m -1) = n f i o ĵ

burada

(i o ĵ) v = ben ĵ v

,

ĵ

j

devrik olmak üzere ,

(ĵ v) ile

tanımlanır

u

= (

j

u

)

v

.

R1 . Öncül olmadan

t = t

çıkarımı yapılır .

R2 . Kaynaktan

s = U

ve

t = u

anlaması

s = t

burada

s

,

t

ve

u

olan

N

-ary şartlar.

R3 . Kaynaktan

s 0 = t 0, ..., s m -1 = t m -1

anlaması

m f i'nin (s 0, ..., s m -1) = m f I (t 0, ..., t m -1)

, tüm terimler burada

s ı, t i

vardır

, n

-ary.

Yan durumun anlamı A1 olmasıdır $i O ĵ$ olduğu $2 N$ olan -bit numarası $V$ inci biraz $ĵ hacim$ arasında inci bit $i$ her miktar aralıkları olan, $u : m$ , $hacim : 2 n-$ , $j u : 2 2 n$ ve $ĵ v : 2 m$ . (Yani $j$ bir olan $m$ ve -tuple $2 n-$ bitlik sayı ise $ĵ$ bir devrik olarak $j$ a, $2, n$ bir -tuple $m$ bitlik sayı. Hem $j$ ve $ĵ$ nedenle içeren $m 2, n$ bit).

A1 , bir belit şema yerine içeren sayesinde bir aksiyomu metavariables , yani $m$ , $ı$ , $n$ ve $j, 0$ ile $j m-1$ . Aksiyomlaştırmanın gerçek aksiyomları, metadeğişkenleri belirli değerlere ayarlayarak elde edilir. Örneğin, alırsak $m = n = i = j 0 = 1$ , biz, iki bit hesaplayabilir $i O ĵ$ gelen $i 1 = 0$ ve $I 0 = 1$ , yani $i o ĵ = 2$ (ya da $10$ ile yazıldığında iki bitlik bir sayı). Elde edilen örneği, yani $1 f 1 (1 f 1) = 1 f 2$ , bilinen aksiyomu ifade $\neg\neg x = x$ çift olumsuzlamanın. Kural R3, daha sonra anlaması bize sağlar $\neg\neg\neg X = \neg x$ alarak $s 0$ olduğu $1 f 1 (1 f 1)$ ya da $\neg\neg x 0$ , $t 0$ olduğu $1 f, 2$ ya da $X, 0$ ve $m, f i$ için olmak $1 f 1$ veya $\neg$ .

Her $m$ ve $n$ için A1'i somutlaştıran yalnızca sonlu sayıda aksiyom vardır , yani $2 2 m \times (2 2 n) m$ . Her örnek $2 m + m 2 n$ bit ile belirtilir.

R1'i , öncülleri olmayan bir aksiyom gibi görünse de, bir çıkarım kuralı olarak ele alıyoruz , çünkü bu, gruplar, halkalar veya diğer herhangi bir türden tüm denklemsel aksiyomlar için ortak olan R2 ve R3 ile birlikte alandan bağımsız bir kuraldır . Boole cebirlerine özgü tek varlık, aksiyom şeması A1'dir . Bu şekilde, farklı denklem teorilerinden bahsederken, belirli teorilerden bağımsız olarak kuralları bir tarafa itebilir ve elimizdeki belirli denklem teorisini karakterize eden aksiyom sisteminin tek parçası olarak aksiyomlara dikkat çekebiliriz.

Bu aksiyomlaştırma tamamlanmıştır, yani her Boole yasası $s = t$ bu sistemde kanıtlanabilir. Yüksekliğine indüksiyonu ile bir birinci gösterir $s$ olan her Boole hakları olduğunu $t$ atomik kullanılarak kanıtlanabilir olan R1 (farklı atomlar eşit asla çünkü) temel durum için ve A1 ve R3 indüksiyon adım için ( $s$ bir uygulama). Bu ispat stratejisi, bir atom elde etmek için $s'yi$ değerlendirmek için özyinelemeli bir prosedür anlamına gelir . Daha sonra , $t'nin$ bir uygulama olabileceği genel durumda $s = t'yi$ kanıtlamak için, $s$ $=$ $t$ bir özdeşlik ise, o zaman $s$ ve $t'nin$ aynı atomu değerlendirmek zorunda olduğu gerçeğini kullanın, buna $u$ deyin . O halde önce $s$ $=$ $u$ ve $t$ $=$ $u'yu$ yukarıdaki gibi kanıtlayın , yani $s$ ve $t'yi$ A1 , R1 ve R3 kullanarak değerlendirin ve ardından $s$ $=$ $t$ sonucunu çıkarmak için R2'yi çağırın .

Olarak A1 , biz dizi görüntülemek eğer $n m$ fonksiyon tipi olarak $m \to n$ ve $m, n$ , uygulama olarak $m (n)$ , sayıları yeniden yorumlayan olabilir $i$ , $j$ , $j$ , ve $i O ĵ$ çeşidine göre $I : (m \to2)\to2$ , $j : m \to((n \to2)\to2)$ , $ĵ : (n \to2)\to(m \to2)$ , ve $ben o ĵ : (n \to2)\to2$ . Tanımı $(i O ĵ) v = i'nin ĵ v$ içinde A1 sonra çevirir $(i O ĵ) (v) = i (ĵ (h))$ , olduğu, $i O ĵ$ bileşimi olarak tanımlanır $i$ ve $ĵ$ anlaşılır fonksiyonlar olarak. İçeriği Böylece A1 esas bileşimi vadeli uygulama tanımlayan tutarındadır, devrik ihtiyacını modulo $m$ -tuple $j$ tip bileşim için uygun bir maç yapmak için. Bu bileşim, Lawvere'in daha önce bahsedilen güç kümeleri ve işlevleri kategorisindeki bileşimdir. Bu şekilde, Boole cebirlerinin denklem teorisi olarak bu kategorinin yer değiştirme diyagramlarını , o özel bileşim yasasının mantıksal temsili olarak A1'in denklemsel sonuçlarına çevirdik .

Temel kafes yapısı

Her Boole cebri Dayanak $B$ a, kısmi sıralı grubu ya da poşet $(B, \leq)$ . Kısmi sıralama ilişki ile tanımlanır $x \leq Y$ sadece $x = x \land y$ eşit ya da $Y = X \lor y$ . Verilen bir dizi $X,$ bir Boole cebri elemanlarının, bir üst sınırı ile $X$ bir elemandır $Y$ bu şekilde her eleman için $, x$ ve $X$ , $X \leq Y$ , bir alt üzerine bağlanmış ise $, X$ bir elemandır $Y$ bu şekilde her eleman için $, x$ ve $X$ , $y \leq x$ .

Bir destek arasında $, X$ , bir en küçük üst üzerine bağlanmış olan $, X$ , yani bir üst bağlı, $X$ az bir veya her üst üzerine bağlanmış e eşit olduğu $, X$ . İkili olarak bir ( inf ) arasında $X$ ile bağlı düşük bir en büyük olduğu $, X$ . Sup $x$ ve $y$ , her zaman olduğu, bir Boole cebri altında yatan poşet var $x \lor y$ , ve aynı şekilde bunların inf, yani var olan $X \land y$ . Boş destek 0'dır (alt öğe) ve boş inf 1'dir (üst). Her sonlu kümenin hem bir sup hem de bir inf'ye sahip olduğu sonucu çıkar. Bir Boole cebrinin sonsuz alt kümeleri bir sup ve/veya bir inf'ye sahip olabilir veya olmayabilir; bir güç kümesi cebirinde her zaman yaparlar.

Her $x$ $,$ $y$ eleman çiftinin hem bir sup hem de bir inf'ye sahip olduğu herhangi bir poz $(B,\leq)$ kafes olarak adlandırılır . Sup için $x$ $\lor$ $y$ , inf için $x$ $\land$ $y$ yazarız . Boole cebrinin altında yatan poz her zaman bir kafes oluşturur. Kafes olduğu söylenir dağıtım zaman $X$ $\land ($ $y$ $\lor$ $z$ $) = ($ $x$ $\land$ $y$ $) \lor ($ $x$ $\land$ $Z$ $)$ , veya eşdeğer $x$ $\lor ($ $y$ $\land$ $z$ $) = ($ $x$ $\lor$ $y$ $) \land ($ $x$ $\lor$ $z$ $)$ , çünkü her iki yasa da diğerini bir kafes içinde ima eder. Bunlar Boole cebrinin yasalarıdır ve Boole cebrinin altında yatan poz, bir dağıtım kafesi oluşturur.

Alt elemanı 0 ve üst elemanı 1 olan bir kafes verildiğinde, $x$ $\land$ $y$ $= 0$ ve $x$ $\lor$ $y$ $= 1$ olduğunda bir $x, y$ eleman çifti tamamlayıcı olarak adlandırılır ve sonra $y'nin$ $x$ ve mengenenin bir tamamlayıcısı olduğunu söyleriz tersi. Üstü ve altı olan bir dağıtım kafesinin herhangi bir $x$ elemanı en fazla bir tümleyene sahip olabilir. Bir kafesin her elemanının bir tümleyeni varsa, kafes tümleyen olarak adlandırılır. Tümleyen bir dağıtım kafesinde, bir öğenin tümleyeni her zaman var olur ve benzersizdir, tümleci tekli bir işlem yapar. Ayrıca, her tamamlayıcı dağıtım kafesi bir Boole cebiri oluşturur ve bunun tersine her Boole cebri, tümleyen bir dağıtım kafesi oluşturur. Bu, Boole cebrinin alternatif bir tanımını sağlar, yani herhangi bir tamamlayıcı dağıtım kafesi olarak. Bu üç özelliğin her biri sonlu sayıda denklemle aksiyomlaştırılabilir, bu nedenle bu denklemler birlikte alındığında Boole cebirlerinin denklem teorisinin sonlu bir aksiyomizasyonunu oluşturur.

Bir denklem kümesinin tüm modelleri olarak tanımlanan bir cebir sınıfında, genellikle sınıfın bazı cebirlerinin, yalnızca onları sınıf için nitelendirmek için gerekenlerden daha fazla denklemi sağlaması söz konusudur. Boole cebri sınıfı, tek bir istisna dışında, her Boole cebrinin tam olarak Boole kimliklerini karşılaması ve daha fazlasını sağlamaması bakımından olağandışıdır. Bunun istisnası, $x = y$ bile olsa her denklemi zorunlu olarak karşılayan tek elemanlı Boole cebiridir ve bu nedenle bazen tutarsız Boole cebiri olarak adlandırılır.

Boole homomorfizmaları

A Boolean homomorfizmi , $A$ $,$ $B$ Boole cebirleri arasında $h : A \to B$ bir fonksiyondur $,$ öyle ki her Boole işlemi için $m$ $f$ $i$ :

h(^{m}\!f_{i}(x_{0},...,x_{m-1}))={}^{m}\!f_{i}(h(x_ {0},...,x_{m-1}))

Kategori Bool Boole cebirlerinin tüm Boole cebirlerini nesneleri ve aralarındaki Morfizm olarak Boole homomorfizmler olarak bulunur.

İki elemanlı Boole cebri 2'den her Boole cebrine benzersiz bir homomorfizma vardır , çünkü homomorfizmalar iki sabiti korumalıdır ve bunlar 2'nin tek elemanlarıdır . Bu özelliğe sahip bir Boole cebri, ilk Boole cebri olarak adlandırılır . Böylece kadar isomorphism için bir ilk iki Boole cebir izomorfik olduğu gösterilebilir 2 olan ilk Boole cebri.

Diğer yönde, bir Boole cebri birçok homomorfizmleri var olabileceği $B$ için 2 . Böyle bir homomorfizmi bölümleri $B$ 1 ve 0 altkümesi için bu eşlenen bu elemanlar halinde $B$ önceki oluşan adlandırılır ultrasüzgeç arasında $B$ . Tüm $B$ onun ultrasüzgeçler atomlarındaki ile çifti sonlu olduğu; bir atom 1 eşleştirilir ve 0 olarak geri kalan her ultrafiltre $B$ , böylece bir atomundan oluşan $B$ ve üzerindeki tüm elemanları; dolayısıyla $B$ elementlerinin tam olarak yarısı ultrafiltrededir ve atomlar kadar çok ultrafiltre vardır.

Sonsuz Boole cebirleri için ultrafiltre kavramı önemli ölçüde daha hassas hale gelir. Bir atomdan daha büyük veya eşit olan elementler her zaman bir ultrafiltre oluşturur, ancak diğer birçok küme de öyle; örneğin, sonlu ve ortak sonlu tamsayı kümelerinin Boole cebrinde, eş sonlu kümeler, hiçbiri atom olmasa da bir ultrafiltre oluşturur. Aynı şekilde, tamsayıların güç kümesi, ultrafiltreleri arasında, belirli bir tamsayıyı içeren tüm alt kümelerin kümesine sahiptir; tamsayıların kendileriyle tanımlanabilecek bu "standart" ultrafiltrelerin sayılabilir bir çoğu vardır, ancak sayılamayacak kadar çok "standart olmayan" ultrafiltre vardır. Bunlar , sonsuz küçükler ve delta fonksiyonları gibi klasik olarak tutarsız nesneler için temsiller sağlayarak standart olmayan analizin temelini oluşturur .

sonsuz uzantılar

Boole cebrinin altta yatan kısmi düzeniyle ilgili yukarıdaki bölümden sup ve inf tanımlarını hatırlayın. Bir tam Boole cebri bir sup ve bir inf, hatta sonsuz alt kümeleri hem sahip olduğu her alt kümesidir. Gaifman [1964] ve Hales [1964] bağımsız olarak sonsuz serbest tam Boole cebirlerinin olmadığını gösterdiler . Bu, küme-boyutlu sonsuz işlemlere sahip bir mantığın sınıf-çok terime sahip olabileceğini gösterir - tıpkı sonlu işlemlere sahip bir mantığın sonsuz sayıda terime sahip olabileceği gibi.

Bununla birlikte, sonsuz Boole işlemlerini tanıtmanın başka bir yaklaşımı daha vardır: Boole cebri tanımından "sonlu" ifadesini çıkarmanız yeterlidir. Cebir denklemsel teorisinin bir model tüm modelin kardinalitesi için Arity yukarı {0,1} üzerinde operasyonlar tam bir atom Boole cebir veya denir Caba . (Arity üzerindeki bu garip kısıtlamanın yerine, imzanın herhangi bir kümeden, yani uygun bir sınıftan daha büyük olacağı, farklı bir beceriksizliğe yol açan herhangi bir ariteye izin verebiliriz. İkinci yaklaşımın bir yararı, farklı kardinaliteye sahip CABA'lar arasındaki homomorfizmin tanımı .) Böyle bir cebir, eşdeğer olarak , atom olan tam bir Boole cebiri olarak tanımlanabilir , yani her element bir atom kümesinin toplamıdır. Ücretsiz Cabas kümesi tüm kardinallikleri için var $V$ arasında jeneratörler , yani güç ayarlamak cebir $2$ $2$ $V$ bu sonlu serbest Boole Cebirlerin bariz genelleme olmak. Bu, sonsuz Boole mantığını Gaifman-Hales sonucunun ona emanet ettiği gibi göründüğü kaderden düzgün bir şekilde kurtarır.

Olmayışını ücretsiz tam Boole Cebirlerin uygun komple Boole cebir tanımında özellikle infinitary birlikte ve ayrılmalara ilişkin distributivity ihmal tutun gereken tüm yasalara Boole mantık denklemleri uzatmak için başarısızlık kadar izlenebilir. Tam bir Boole cebri, keyfi bağlaçlar keyfi ayrılmalar üzerinde dağıtıldığında ve bunun tersi olduğunda , tamamen dağılma olarak adlandırılır . Bir Boole cebri, ancak ve ancak tam ve tamamen dağıtıcıysa ve CABA'nın üçüncü bir tanımını veriyorsa bir CABA'dır. Dördüncü bir tanım, herhangi bir Boole cebrinin, bir kuvvet kümesi cebrine izomorfiktir.

Tam bir homomorfizma, sadece sonlu miktarları değil, aynı şekilde inf'ler için de var olan tüm miktarları koruyan bir homomorfizmadır. Kategori CABA tüm Cabas ve bunların tam homomorfizması o kategorinin karşısında (bütün morfizimler ters kaynaklanan kategorisinde) eşdeğerdir, yani setleri ve bunların fonksiyonları kategorisine ikili olduğunu. Marshall Stone'un fiilen gösterdiği Bool of Boole cebirleri ve homomorfizmaları kategorisi için (ikiliği açık hale getirmek için hem dilden hem de kavramsal çerçeveden yoksun olmasına rağmen) tamamen bağlantısız kompakt Hausdorff kategorisine ikili olması için işler o kadar basit değildir . boşluklar , daha sonra Taş boşluklar olarak adlandırılır .

Boole cebirleri ve tam Boole cebirleri arasındaki bir başka sonsuz sınıf ara , bir sigma cebiri kavramıdır . Bu, Boole cebirlerini tamamlamak için benzer şekilde tanımlanır, ancak sups ve inf'ler sayılabilir arite ile sınırlıdır. Yani, bir sigma cebri, tüm sayılabilir sups ve inf'leri olan bir Boole cebridir. Sups ve infs sınırlı kardinaliteye sahip olduklarından, tam Boole cebirlerindeki durumun aksine , Gaifman-Hales sonucu geçerli değildir ve serbest sigma cebirleri mevcuttur. Bununla birlikte, CABA'ların durumundan farklı olarak, sayılabilir olarak üretilen serbest sigma cebri, bir kuvvet kümesi cebri değildir.

Boole cebrinin diğer tanımları

İki elemanlı cebirin denklem teorisinin bir modeli olarak, tümleyen bir dağıtım kafesi olarak, bir Boole halkası olarak ve belirli bir kategoriden (Lawvere) ürün koruyucu bir işlev olarak Boole cebrinin birçok tanımıyla daha önce karşılaşmıştık. Bahsetmeye değer iki tanım daha:

Taş (1936): Boole cebri, bir topolojik uzayın tüm clopen kümelerinin kümesidir . Uzayın tamamen bağlantısız bir kompakt Hausdorff uzayı veya Stone uzayı olmasını istemek bir sınırlama değildir , yani her Boole cebri izomorfizme kadar bu şekilde ortaya çıkar . Ayrıca, iki Stone uzayının klopen kümeleri olarak oluşturulan iki Boole cebri izomorfik ise, Stone uzaylarının kendileri de öyledir, bu keyfi topolojik uzaylar için geçerli değildir. Bu, Boole cebirlerinden Stone uzaylarına daha önce bahsedilen dualitenin tam tersidir . Bu tanım, bir sonraki tanımla detaylandırılmıştır.

Johnstone (1982): Bir Boole cebiri, sonlu Boole cebirlerinin filtrelenmiş bir colimitidir .

(Bu tanımdaki döngüsellik, "sonlu Boole cebri"nin, güç kümeleri için standart olarak yorumlanan Boolean işlemleriyle donatılmış "sonlu güç kümesi" ile değiştirilmesiyle ortadan kaldırılabilir.)

Bunu perspektife koymak için, sonsuz kümeler, sonlu kümelerin filtrelenmiş sınırları olarak, sonsuz CABA'lar sonlu kuvvet kümesi cebirlerinin filtrelenmiş sınırları olarak ve sonlu kümelerin filtrelenmiş sınırları olarak sonsuz Taş uzayları ortaya çıkar. Bu nedenle, sonlu kümelerle başlayıp bunların sonsuz nesnelere nasıl genelleştirildiği sorulursa, iki yol vardır: onları "eklemek" sıradan veya tümevarımsal kümeler verir, "çarpmak" ise Taş uzayları veya sonlu kümeler verir . Aynı seçim, sonlu kümelerin dualleri gibi sonlu güç kümesi cebirleri için de mevcuttur: Toplama, endüktif nesneler olarak Boole cebirlerini verirken, çarpma, sonlu nesneler olarak CABA'ları veya güç kümesi cebirlerini verir.

Karakteristik bir ayırt edici özelliği olması için böylece belirlenen zaman nesnelerin alttaki topolojisi, yani imal olmasıdır Hausdorff olup, kesikli endüktif nesneler için ve kompakt profinite nesneler için. Sonlu Hausdorff uzaylarının topolojisi her zaman hem ayrık hem de kompakttır, oysa sonsuz uzaylar için "ayrık" ve "kompakt" birbirini dışlar. Bu nedenle, sonlu cebirleri (yalnızca Boolean değil) sonsuz olanlara genelleştirirken, "ayrık" ve "kompakt" kısım şirkettir ve kişi hangisini koruyacağını seçmelidir. Hem sonlu hem de sonsuz cebirler için genel kural, sonlu cebirlerin ayrık olduğu, ikililerin ise kompakt olduğu ve sonsuz işlemler içerdiğidir. Bu iki uç arasında, topolojisi ne ayrık ne de kompakt olan birçok ara sonsuz Boole cebiri vardır.

Ayrıca bakınız

Referanslar

Birkhoff, Garrett (1935). "Soyut cebirlerin yapısı üzerine". Proc. Camb. Phil. Soc . 31 (4): 433–454. Bibcode : 1935PCPS...31..433B . doi : 10.1017/s0305004100013463 . ISSN 0008-1981 .
Boole, George (2003) [1854]. Düşünce Yasalarının İncelenmesi . Prometheus Kitapları. ISBN'si 978-1-59102-089-9.
Dwinger, Philip (1971). Boole cebirlerine giriş . Würzburg: Fizik Verlag.
Gaifman, Haim (1964). "Sonsuz Boole Polinomları, I" . Temel Matematik . 54 (3): 229–250. doi : 10.4064/fm-54-3-229-250 . ISSN 0016-2736 .
Givant, Steven; Halmos, Paul (2009). Boole Cebirlerine Giriş . Matematikte Lisans Metinleri . Springer. ISBN'si 978-0-387-40293-2.
Grau, AA (1947). "Üçlü Boole cebiri" . Boğa. NS. Matematik. Soc . 33 (6): 567–572. doi : 10.1090/S0002-9904-1947-08834-0 .
Hales, Alfred W. (1964). "Özgür Tam Boole Cebirlerinin Yokluğu Üzerine" . Temel Matematik . 54 : 45-66. doi : 10.4064/fm-54-1-45-66 . ISSN 0016-2736 .
Halmos, Paul (1963). Boole Cebirleri Üzerine Dersler . van Nostrand. ISBN'si 0-387-90094-2.
Givant, Steven; Halmos, Paul (1998). Cebir olarak mantık . Dolciani Matematiksel Sergisi. Amerika Matematik Derneği . ISBN'si 978-0-883-85327-6.
Johnstone, Peter T. (1982). Taş Boşluklar . Cambridge, Birleşik Krallık: Cambridge University Press. ISBN'si 978-0-521-33779-3.
Ketonen, Jussi (1978). "Sayılabilir Boole cebirlerinin yapısı". Matematik Annals . 108 (1): 41-89. doi : 10.2307/1970929 . JSTOR 1970929 .
Koppelberg, Sabine (1989) Monk, J. Donald ve Bonnet, Robert, eds., Handbook of Boolean Algebras, Vol. 1 . Kuzey Hollanda. ISBN 978-0-444-70261-6 .
Peirce, CS (1989) Charles S. Peirce'in Yazıları: Bir Kronolojik Baskı: 1879–1884 . Kloesel, CJW, ed. Indianapolis: Indiana University Press. ISBN 978-0-253-37204-8 .
Lawvere, F. William (1963). "Cebirsel teorilerin işlevsel semantiği" . Ulusal Bilimler Akademisi Bildirileri . 50 (5): 869-873. Bibcode : 1963PNAS...50..869L . doi : 10.1073/pnas.50.5.869 . PMC 221940 . PMID 16591125 .
Schröder, Ernst (1890-1910). Vorlesungen über die Cebir der Logik (exakte Logik), I–III . Leipzig: BG Teubner.
Sikorski, Roman (1969). Boole Cebirleri (3. baskı). Berlin: Springer-Verlag. ISBN'si 978-0-387-04469-9.
Taş, MH (1936). "Boole Cebirleri için Temsil Teorisi". Amerikan Matematik Derneği'nin İşlemleri . 40 (1): 37–111. doi : 10.2307/1989664 . ISSN 0002-9947 . JSTOR 1989664 .
Tarski, Alfred (1983). Mantık, Semantik, Metamathematics , Corcoran, J., ed. Hackett. 1956 1. baskı JH Woodger, Oxford Uni tarafından düzenlendi ve çevrildi. Basmak. Aşağıdaki iki makalenin İngilizce çevirilerini içerir:
- Tarski, Alfred (1929). "Sur les sınıfları, belirli operasyonlar élémentaires ile par uyumunu kapatır". Temel Matematik . 16 : 195–97. ISSN 0016-2736 .
- Tarski, Alfred (1935). "Zur Grundlegung der Booleschen Cebiri, I" . Temel Matematik . 24 : 177-98. doi : 10.4064/fm-24-1-177-198 . ISSN 0016-2736 .
Vladimirov, DA (1969). булевы алгебры (Boole cebirleri, Rusça, Almanca çeviri Boolesche Algebren 1974) . Nauka (Almanca çeviri Akademie-Verlag).

Languages

In other projects