Logikai algebra (struktúra)
A matematikában egy logikai algebra vagy néha logikai gyűrű olyan algebrai struktúra, amelyet különösen a matematikai logikában vizsgálnak . A Boole-algebra meghatározható egy adott rendezett szerkezetként , vagy egy adott algebrai szerkezetként, vagy egy (egységes) gyűrűként, amelynek minden eleme megegyezik a négyzetével.
Bármely halmaz esetében a részek halmaza egy logikai algebra, a társított sorrend az inklúzió, a gyűrűs törvények pedig a szimmetrikus különbség és a metszéspont . Egy másik példát adunk az egyenértékűségig (a klasszikus logika szerint) felvett propozíciós számítási képletek halmazából (az önkényes kardinalitás számos változójánál), a kapcsolódó sorrend a logikai következmény kapcsolata, a gyűrűs törvények pedig a kizárólagos diszjunkció és a kötőszó .
Definíciók
Boole-algebra, mint rács
Az E Boole-algebra egy nagyobb és kisebb elemeket tartalmazó rács , amelynek mindkét alsó és felső határú művelete mindegyike eloszlik a másikhoz képest, és amelynek minden elemének van kiegészítése. Más szavakkal :
- ( E , ≤) rendezett halmaz ;
- Két elem egy , b az E egy felső kötve, megjegyezte, a szekvenciában egy ∨ b , és egy alsó, Bound megjegyezte, a szekvenciában egy ∧ b (azaz ez egy rács );
- Van egy kisebb elem, amelyet a 0-as szekvenciában jegyeznek meg (gyakran megjegyzik is ), és egy nagyobb elem van, amelyet az 1-es szekvenciában jegyeznek fel (gyakran megjegyzik );
- A operation művelet disztributív a the műveleten, és a ∨ művelet disztributív a operation műveleten, azaz E összes a , b és c esetében :
- bármely elem egy az E , van olyan egy " a E , az úgynevezett komplement az E és kielégíti:
Tehát egy Boole-algebra egy disztribúciós, határolt (a legkisebb és legnagyobb elemmel) és kiegészített rács. Elég lenne megadni az egyik disztribúciós törvényt, az egyiket bevonva a másikat egy rácsba (lásd a kapcsolódó cikket).
Megmutatjuk, hogy minden elemnek egyedi kiegészítése van. Valóban, ha az 1 és a ' kiegészítései a-nak , akkor a komplementerek tulajdonságainak felhasználásával, a sorrendet és az elosztást kapjuk:
a 1 = ( a ∧ a ' ) ∨ a 1 = ( a ∨ a 1 ) ∧ ( a' ∨ a 1 ) = a ' ∨ a 1vagyis a ' ≤ a 1 . Ugyanígy a 1 = a ' ∧ a 1 , tehát a 1 ≤ a' , tehát az egyenlőség.
Azáltal egyediségét a kiegészítés a kérelmet, hogy a társított a komplementere involúció ( a ' = a ). 0-t és 1-et cserél . A komplementer egyediségével és disztributivitásával is megmutatjuk, hogy a komplementerre való átmenet ∧ és ∨, ezek De Morgan törvényei (lásd a következő bekezdést).
A sorrend-axiómákból arra következtetünk, hogy a ∧ és ∨ műveletek asszociatívak , kommutatívak , hogy 0 semleges ∨ és abszorbeálja ∧, hogy 1 semleges ∧ és abszorbeálja ∨, valamint hogy ezek a műveletek idempotensek .
Boole-algebra mint algebrai szerkezet
Az előző rendezett szerkezet egy rács , ezért lehetséges algebrai módon definiálni, közvetlenül az alsó és a felső határt jelentő két bináris művelet, a komplementnek való átadás unaráris művelete és a kettő szempontjából állandók, 0 és 1 Boole-algebra meghatározható ezután mint egy olyan struktúrát ( E , ∧, ∨, (.)”, 0, 1), amely megfelel az összes elemet egy , b és c a E :
| Elosztó rács kisebb és nagyobb elemekkel | |||
| ( a ∧ b ) ∧ c = a ∧ ( b ∧ c ) | és | ( a ∨ b ) ∨ c = a ∨ ( b ∨ c ) | (asszociativitás) |
| a ∧ b = b ∧ a | és | a ∨ b = b ∨ a | (kommutativitás) |
| a ∧ a = a | és | a ∨ a = a | (idempotencia) |
| 1 ∧ a = a | és | 0 ∨ a = a | (semleges elem) |
| 0 ∧ a = 0 | és | 1 ∨ a = 1 | (nedvszívó elem) |
| a ∧ ( b ∨ c ) = ( a ∧ b ) ∨ ( a ∧ c ) | és | a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c ) | (disztribúció) |
| Kiegészítés | |||
| a ∧ a ' = 0 | és | a ∨ a ' = 1 | (kiegészítés) |
| a '' = a | (kiegészíti az invutivitást) | ||
| ( a ∧ b ) '= a ' ∨ b ' | és | ( a ∨ b ) '= a ' ∧ b ' | (De Morgan törvényei) |
Az abszorpciós törvényeket a disztribúcióból a semleges, elnyelő elemek és a kommutativitás törvényei vezetik le ( a ∧ ( a ∨ b ) = ( a ∨ 0) ∧ ( a ∨ b ) = a ∨ (0 ∧ b ) = a ∨ 0 = a )
| a ∧ ( a ∨ b ) = a | és | a ∨ ( a ∧ b ) = a | (abszorpció) |
A sorrend összefüggése kétféleképpen határozható meg (a sorrend reflexivitása az idempotenciából, az antiszimmetria a kommutativitásból és az asszociativitás tranzitivitása következik a játékban lévő művelethez):
| a ≤ b egyenértékű a ∧ b = a -val | a ≤ b egyenértékű a ∨ b = b-vel |
Ez az axiómarendszer könnyen használható demonstrációkra, de nagyon felesleges. Amint a rács definícióját a rács axiómáinak sorrendviszonyai alapján találjuk meg, a többi axiómából levezetjük a komplement invutivitását, De Morgan törvényeit, valamint azt a tényt, hogy 0 és 1 abszorbeálódik, mint az előző bekezdésben. Az egyik lehetőség (többek között) az, hogy a semleges elem, a kiegészítés, a kommutativitás és a disztributivitás egyetlen axiómájára szorítkozik.
Az axiómarendszer szimmetriája kiemeli a kettősséget a Boole-algebrákban.
Boole-algebra, mint gyűrű
A logikai algebra ekvivalensen definiálható logikai gyűrűként is , vagyis olyan gyűrűként , amelyben minden elem idempotens . A szerkezet ( E , +, •, 0, 1) tehát Boole-gyűrű, ha kielégíti az azonosságokat:
| ( a + b ) + c = a + ( b + c ) | (asszociativitás +) |
| a + b = b + a | (kommutativitás +) |
| 0 + a = a | (semleges elem +) |
| Minden elem egy van egy szemközti , jelöljük -a : | |
| (- a ) + a = 0 | (szemben) |
| ( a • b ) • c = a • ( b • c ) | (asszociativitás •) |
| 1 • a = a | (semleges elem •) |
| a • ( b + c ) = a • b + a • c | (disztribúció a bal oldalon) |
| ( b + c ) • a = b • a + c • a | (jobb elosztó tulajdon) |
| a • a = a | (idempotencia) |
A termék idempotenciájából kétféle módon számolva ( a + a ) 2 (eloszlások) és leegyszerűsítve arra következtetünk, hogy mindegyik elem a saját ellentéte, vagyis hogy egy logikai gyűrű a 2. jellemző :
| a + a = 0 | (egy elem saját ellentéte) |
A gyűrű tehát algebra a kételemes mező fölött .
Az idempotencia alapján mindig két következtetéssel számolunk ( a + b ) 2 , hogy az a • b + b • a = 0, tehát a szorzás kommutativitása az előző tulajdonság szerint:
| a • b = b • a | (kommutativitás •) |
A gyűrűs törvények különböznek az előző bekezdés logikai algebrai törvényeitől, különösen az összeadásnál csak a szorzás elosztó.
Egy logikai algebrából ( E , ∧, ∨, 0, 1) egy logikai gyűrűt kapunk beállítással
- a • b = a ∧ b
- a + b = ( a ∧ b ' ) ∨ ( a' ∧ b )
a 0 és 1 konstansokat megtartjuk. A gyűrűazonosságok ellenőrzése közvetlenül az előző bekezdés Boole-algebra azonosságainak felhasználásával történik.
Ezzel szemben egy logikai gyűrűből ( E , +, •, 0, 1) egy logikai algebrát kapunk a következő beállítással:
- a ∧ b = a • b
- a ' = 1 + a
- a ∨ b = a + b + a • b
és annak ellenőrzése, hogy a 0 és 1 semleges elemek valóban a legkisebb és legnagyobb elemek. Különösen egy Boole-körben találjuk meg a struktúrát:
- a ≤ b akkor és csak akkor, ha a = a • b
Az algebra-azonosságok ellenőrzése itt is egyszerűen a logikai gyűrű-azonosságok felhasználásával történik (beleértve a kommutativitást és a 2. jellemzőt is).
Az alábbiakban algebrának vagy logikai gyűrűnek hívjuk az egyiket, mint a másik struktúrát.
Példák logikai algebrákra
Ha 0 = 1, akkor a Boolean algebra csak egy elemet tartalmaz, azt mondják, hogy degenerált vagy triviális .
Kételemes logikai algebra
Egy nem degenerált logikai algebra legalább két elkülönülő 0 és 1 elemet tartalmaz, és a legegyszerűbb logikai algebra a kételemes algebra. Láthatjuk, mint a klasszikus logika két igazságértékének {Hamis, Igaz} halmazát. Mivel a gyűrű Z / 2 Z , és a multiplikatív törvény idempotenciája miatt az egyetlen logikai gyűrű integrálódik , így az egyetlen test .
A halmaz részeinek logikai algebra
A szett részei bármely csoportja egy , a megrendelt felvétel, egy logikai algebra. Az alsó határ a metszéspont, a felső határ az egyesülés, a komplementer áthaladása az A-ban , az üres halmaz és A a semleges elemek, az összeadás a szimmetrikus különbség. Ha A üres, a logikai algebra degenerált. Amikor egy olyan egyke , azt látjuk, a két elem logikai algebra az előző bekezdésben.
Lindenbaum algebra
A logikai ekvivalencia relációval osztott propozíciós számítási képletek halmaza (két propozíciós képlet ekvivalens, ha ugyanaz az igazságtáblájuk van ), a deduktív relációval, mivel a rend reláció (a klasszikus logikában) Boole algebra.
Általánosságban elmondható, hogy a predikátumok bármely T elméletéhez az elmélet nyelvének állításainak (zárt képletek) halmaza, amelynek hányadosa a T ekvivalencia-relációja, és rendi relációként a T- ben levonási reláció, logikai algebra, algebra Lindenbaum elmélet T .
Az alsó határt a kötőszó, a felsőt a diszjunkció, a kiegészítést a tagadás adja. A mindig hamis állítás ekvivalenciaosztálya a diszjunkcióhoz semlegeset ad, a mindig igaz állítás ekvivalenciaosztálya pedig a kötőszóval semlegeset. Az összeadást a kizárólagos diszjunkció adja.
A végtelen, például megszámlálható változókra vonatkozó propozíciós számítás Lindenbaum-algebra különbözik a halmaz részeinek halmazától, mert minden elemnek nem nulla szigorú alsó határa van (egy olyan propozíciós változóval együtt, amely nem szerepel a formula), amely nem áll fenn a halmaz részhalmazának szingulettjeinél.
Kettősség
Mivel a logikai kifejezés írt az egyetlen állandók és algebrai rácsos műveletek (0, 1, ∧, ∨, () „), a kettős e kifejezés, hogy jutottunk, hogy felcseréltük a felső kötött ∨ és az alsó kötött ∧ a” a egyrészt 0 és 1 másrészt. Például itt van a Boole-gyűrűk összeadásának (szimmetrikus különbség) és kettős kifejezése:
az ( a ∧ b ' ) ∨ ( a' ∧ b ) kettője ( a ∨ b ' ) ∧ ( a' ∨ b )Ezt a definíciót állításokra általánosítják, helyettesítéssel. A második definíció, mint algebrai rács, a Boole-algebra axiómáit párban mutatjuk be, az egyik axióma a másik kettős állítása. Következésképpen a Boole algebrai bármely, ebben a nyelvben szereplő tételének kettős tétel felel meg: ez a kettősség elve a Boole algebrák számára.
Például az abszorpciós törvények kettősek egymás között: ezért elegendő bizonyítani az egyiket, és arra következtetünk, hogy a másik a kettősség alapján tétel.
A kettősség átalakítja a megbízás annak reciproka érdekében: a kettős forma egy ≤ b ( a ∧ b = a ) van egy ≥ b ( a ∨ b = a ).
Ellenőrizzük, hogy az f ( p 1 , ..., p n ) logikai kifejezés kettőse ( f ( p ' 1 , ..., p' n )) '.
Subalgebras
A Boole- részalgebra egy subring a Boole-algebra, mint egy egység gyűrűt, azaz (ebben az esetben) egy részhalmaza stabil hozzáadásával, szorzás és amelynek azonos elem multiplikatív semleges. Megmutatjuk, hogy a Boole-i alalgebrák a Boole-algebrák azon részhalmazai, amelyek 0-t és 1-et tartalmaznak, stabilak a felső határok, az alsó határok és a komplementerek (az a tény, hogy a subalgebra részgyűrűként ugyanaz a multiplikatív semleges, elengedhetetlen a stabilitáshoz a kiegészítésre való váltással biztosítani kell). Annak ellenőrzéséhez, hogy egy logikai algebra részhalmaza részalgebra, elegendő-e a stabilitást komplementerrel ellenőrizni a operations, operations két művelet egyikével, és hogy 0 vagy 1 tartozik-e az alkészletbe.
A végtelen halmaz részei halmazának logikai alalgebrájára példa ennek a halmaznak a véges és együttes véges (azaz véges komplementer) részei.
Ha F az E szigorú részhalmaza, akkor F részeinek halmaza egy Boole algebra, amely az E részek halmazának részhalmaza , de amely nem Boolean részalgebra, mert a maximális elemek ( E és F ) nem ugyanúgy, mint a kiegészítők.
Morfizmusok
A Boolean algebrai morfizmusok a Boolean gyűrűs szerkezet szokásos (egységes) gyűrűs morfizmusai .
Ezzel egyenértékűen a rácsmorfizmusok mennek át a komplementhez (ezután elegendő ellenőrizni, hogy a felső vagy az alsó határokat betartják-e De Morgan törvényei).
Komplett logikai algebra
A Boole-algebra minden véges részhalmazának van egy felső és egy alsó határa.
A Boole-algebra akkor mondható teljesnek, ha teljes rácsról van szó , vagyis ha minden részhalmazának (véges vagy végtelen) van felső és alsó határa (valójában a két hipotézis egyike elegendő).
Példák és ellenpéldák:
- bármely véges logikai algebra nyilvánvalóan teljes;
- A halmaz részeinek logikai algebra teljes: bármelyik részhalmaz-családnak van egy felső határa, amely ezen részhalmazok egyesülése, és egy alsó határa, amely ezen részhalmazok metszéspontja;
- A Boole-algebra véges vagy ko- véges részei egy végtelen halmaz nem teljes;
- a propozíciós számítás Lindenbaum-algebrája a változók végtelenje felett is.
- Bármely Boole algebra A egy teljes B Boolean algebra alalgebrája, oly módon, hogy B bármely eleme az A. részének felső határa. B-t az A befejezésének nevezzük . A közelben lévő izomorfizmusra egyedülálló.
Atomok
Egy logikai algebrában az atom fogalma az, amely megfelel a halmaz részének logikai algebrájában szereplő szinguletteknek. Ugyanakkor egy Boole-algebra nem feltétlenül tartalmaz atomokat.
Meghatározás
A Boole-algebra B atomja olyan elem, amelynek nincs 0-nál szigorúbb alsó korlátja:
egy olyan atom, ha, és csak akkor, ha bármely elem x a B , 0 ≤ x ≤ egy ⇒ ( x = 0, vagy X = a ).Az azonnali, hogy a szingulettek a halmaz részeinek logikai algebrai atomjai. Ez utóbbinak megvan az a tulajdonsága is, hogy bármely nem nulla elemet legalább egy atom redukál: egy ilyen Boole-algebráról azt mondják, hogy atom . Vannak atomok nélküli Boole-algebrák is, mint például a propozíciós számítás Lindenbaum-algebra a változók végtelenségén.
Véges logikai algebrák
Bármely véges logikai algebra izomorf a véges halmaz részhalmazával szemben, amely az algebra atomhalmaza. Kardinalitása tehát 2-es hatvány.
Ideálok és szűrők
A Boole-algebra ideálja az algebra mint kommutatív gyűrű ideálja . Az ideál stabilitása az algebra bármely elemével való szorzás eredményeként azt eredményezi, hogy az ideál a rendezett szerkezet kezdeti szakasza. Az ideálokat rács alapján jellemezhetjük ; a részhalmaza I az E ideális a Boole-algebra ( E , ≤, ∧, ∨, 0, 1), ha az megfelel:
- 0 ∈ I
- ∀ x , y ∈ I x ∨ y ∈ I ;
- ∀ x ∈ I ∀ y ∈ E ( y ≤ x ⇒ y ∈ I ).
A megfelelő ideál különbözik az egész algebrától, ideális esetben nem tartalmazza a maximális 1 elemet. Ezért nem tartalmazhat x elemet és annak kiegészítését 1 + x .
A megfelelő ideál kettős fogalma a szűrő : az algebra részhalmaza akkor szűrő, ha annak kiegészítőinek halmaza ideális. Több közvetlenül a részhalmazát F az E egy szűrő a Boole-algebra ( E , ≤, ∧, ∨, 0, 1), ha az megfelel:
- 1 ∈ F és 0 ∉ F ;
- ∀ x , y ∈ F x ∧ y ∈ F ;
- ∀ x ∈ F ∀ y ∈ E ( y ≥ x ⇒ y ∈ F ).
Az a hozzárendelés, amely egy x elemhez társítja az x ' kiegészítést, létrehoz egy bijekciót a szűrők és az ideálok között.
A maximális ideál maximális ideál a megfelelő ideálok közé való befogadás értelmében. A kettős fogalom az ultraszűrő fogalma : az ultraszűrő a befogadás szempontjából maximális szűrő, és a maximális ideál kiegészítőinek összessége is.
A maximális ideális tétel vagy Krull-tétel kimondja, hogy minden ideál egy maximális ideálba tartozik. A Boole-algebrák esetében a dualitás révén megadja az ultraszűrő tételét: bármilyen szűrő szerepel egy ultraszűrőben.
A logikai algebra maximális ideál hányadosa a két elemű {0, 1} mező, az egyetlen logikai gyűrű, amely egy mező, ezért a kapcsolódó kánoni morfizmusnak értéke van a (z) {0, 1} mezőben.
Általánosságban elmondható, hogy egy adott Boole-algebrában egyenértékű, ha ennek a Boole-algebrának a maximális ideálját, ultraszűrőjét vagy morfizmusát adjuk meg magának {0,1} -ben, az ilyen morfizmus magja maximális ideál, és az az 1. érték elemeinek ez a morfizmus ultraszűrő.
Stone tétele
Láttuk, hogy egy véges Boole-algebra izomorf a halmaz részeinek halmazához, jelen esetben atomjaihoz. A Stone ábrázolási tétele lehetővé teszi ennek az eredménynek az általánosítását bármely logikai algebra vonatkozásában, abban az értelemben, hogy általában egy logikai algebra izomorf a halmaz részhalmazának egy alalgebrájához képest.
Nagyon fontos figyelembe venni a szubalgebrákat: a propozíciós számítás Lindebaum-algebra a propozíciós változók végtelenjén, vagy izomorf módon, az elemek végtelenje által szabadon generált logikai algebra nem atomi (lásd fent ), ezért nem lehet izomorf a halmaz számára készlet részei.
A gyűrűelmélet közös megközelítését követve a szóban forgó halmaz választható a Boole-algebra A maximális ideáljainak halmazává , vagy Boole-algebrák esetében az algebra homomorfizmusainak S ( A ) halmazaként a következőben: {0 , 1}, az úgynevezett teret kőből az a . Ezután ellenőrizze, hogy az alábbi térkép egy injektív morfizmus az A a beállított ? ( S ( A )) részeinek Kő tér:
Ha S (A) -ot 2 A részhalmazának vesszük , akkor a termék topológiával felruházott A-ból származó függvényhalmaz {0} -ban , S (A) egy kőtér , vagyis egy teljesen szakaszos kompakt tér . Nyílt alapként ismeri el nyitott-zárt részeit (zárva). A morfizmus képe ekkor pontosan az S (A) nyitott-zárt halmaza.
Fordítva, ha X kőtér, akkor a szokásos halmazműveletekkel felruházott nyitott-zárt halmaza logikai algebra.
Erre a kettős levelezés Stone reprezentációs tétele létrehozza functorially egy ekvivalencia közötti kategóriában Boole algebrák és Stone terek.
Megjegyzések és hivatkozások
- Lásd: Cori és Lascar 1993 , p. 96 erre a jellemzésre.
- A Boolean algebrák ezen axiómarendszerét Givant és Halmos 2009 , p. 10.
- származó Givant és Halmos 2009 , p. A 10. ábra, lényegében EV Huntington (en) következménye , a logika algebrájára vonatkozó független posztulátumok halmazában , Transaction of the American Mathematical Society, vol. 5 (1904), p. 288–309 ; Huntington adott még néhányat.
- A logikai algebra meghatározása Cori és Lascar 1993-ban , p. 91.
- A "+" jelnek ez a használata ellentmond a logikai számítás bizonyos bemutatási hagyományának , amely megjegyzi a "+" műveletet a "∨" műveletet, a törvény itt megjegyezte, hogy a "+" körbe van írva , vagy megjegyezte az XOR-t.
- Givant és Halmos 2009 , p. 10.
- Cori és Lascar 1993 , p. 99.
- Givant és Halmos 2009 , p. 188-192, Cori és Lascar 1993 , p. 120-126.
Lásd is
Kapcsolódó cikkek
- Logikai algebra mentes (in)
- Kőtér
- Stone ábrázolási tétele
- A gondolat törvényei
- A logikai algebrához kapcsolódó témák listája
Bibliográfia
- René Cori és Daniel Lascar , Matematikai logika I. Propozíciószámítás, Boole-algebrák, predikátumszámítás ,1993[ a kiadások részlete ] , fej. 2.
- (en) Steven Givant és Paul Halmos , Boole- algebrasok bemutatása , Springer ,2009, 574 p. ( ISBN 978-0-387-40293-2 ).
- Daniel Ponasse, Matematikai logika , V. fejezet: Algebrai aspektus - logikai gyűrűszerkezet, OCDL szerkesztő, Párizs, 1967.