La Matematica Dell'algebra Booleana

Sommario:

La Matematica Dell'algebra Booleana
La Matematica Dell'algebra Booleana

Video: La Matematica Dell'algebra Booleana

Video: La Matematica Dell'algebra Booleana
Video: Algebra di Boole 2024, Marzo
Anonim

Questo è un file negli archivi della Stanford Encyclopedia of Philosophy.

La matematica dell'algebra booleana

Pubblicato per la prima volta venerdì 5 luglio 2002; revisione sostanziale ven 27 feb 2009

L'algebra booleana è l'algebra della logica a due valori con solo connettivi sentenziali, o equivalentemente di algebre di insiemi sotto unione e complementazione. Il concetto rigoroso è quello di un certo tipo di algebra, analogo alla nozione matematica di un gruppo. Questo concetto ha radici e applicazioni nella logica (algebre di Lindenbaum-Tarski e teoria dei modelli), teoria degli insiemi (campi degli insiemi), topologia (spazi di Hausdorff compatti totalmente disconnessi), fondamenti della teoria degli insiemi (modelli con valori booleani), teoria delle misure (misura algebre), analisi funzionale (algebre di proiezioni) e teoria degli anelli (anelli booleani). Lo studio delle algebre booleane ha diversi aspetti: teoria della struttura, teoria dei modelli delle algebre booleane, domande di decidibilità e indecidibilità per la classe di algebre booleane e applicazioni indicate. Inoltre,sebbene non sia spiegato qui, ci sono connessioni ad altre logiche, la sussunzione come parte di tipi speciali di logica algebrica, algebre booleane finite e teoria dei circuiti di commutazione e matrici booleane.

  • 1. Definizione e proprietà semplici
  • 2. La teoria algebrica elementare
  • 3. Classi speciali di algebre booleane
  • 4. Teoria della struttura e funzioni cardinali sulle algebre booleane
  • 5. Domande di decidibilità e indecidibilità
  • 6. Algebre di Lindenbaum-Tarski
  • 7. Modelli con valori booleani
  • Bibliografia
  • Altre risorse Internet
  • Voci correlate

1. Definizione e proprietà semplici

Un'algebra booleana (BA) è un insieme A insieme a operazioni binarie + e · e un'operazione unaria - e gli elementi 0, 1 di A tali che valgono le seguenti leggi: leggi commutative e associative per addizione e moltiplicazione, leggi distributive sia per moltiplicazione per addizione e per addizione per moltiplicazione e le seguenti leggi speciali:

x + (x · y) = x

x · (x + y) = x

x + (−x) = 1

x · (−x) = 0

Queste leggi sono meglio comprese in termini dell'esempio di base di un BA, costituito da una raccolta A di sottoinsiemi di un insieme X chiuso sotto le operazioni di unione, intersezione, complementazione rispetto a X, con i membri ∅ e X. Si possono facilmente trarre molte leggi elementari da questi assiomi, tenendo presente questo esempio di motivazione. Ogni BA ha un ordine parziale naturale ≤ definito su di esso dicendo che x ≤ y se e solo se x + y = y. Ciò corrisponde nel nostro esempio principale a ⊆. Di particolare importanza è il BA a due elementi, formato prendendo l'insieme X per avere un solo elemento. Il BA a due elementi mostra la connessione diretta con la logica elementare. I due membri, 0 e 1, corrispondono rispettivamente alla falsità e alla verità. Le operazioni booleane esprimono quindi le normali tabelle di verità per disgiunzione (con +), congiunzione (con ·) e negazione (con -). Un importante risultato elementare è che un'equazione è valida in tutte le BA se e solo se contiene la BA a due elementi. Successivamente, definiamo x ⊕ y = (x · - y) + (y · - x). Quindi A insieme a ⊕ e ·, insieme a 0 e 1, forma un anello con identità in cui ogni elemento è idempotente. Viceversa, dato un tale anello, con aggiunta ⊕ e moltiplicazione, definire x + y = x ⊕ y ⊕ (x · y) e - x = 1 ⊕ x. Questo rende l'anello in un BA. Questi due processi sono invertiti l'uno con l'altro e mostrano che la teoria delle algebre booleane e degli anelli con identità in cui ogni elemento è idempotente sono equivalentemente definitivi. Ciò pone la teoria delle BA in un oggetto standard di ricerca in algebra. Un atomo in un BA è un elemento diverso da zero a tale che non vi è alcun elemento b con 0 <b <a. Un BA è atomico se ogni elemento diverso da zero è al di sopra di un atomo. I BA finiti sono atomici, ma lo sono anche molti BA infiniti. Nell'ordine parziale ≤ sopra, x + y è il limite inferiore minimo di xey, e x · y è il limite inferiore maggiore di xey. Possiamo generalizzare questo: Σ X è il limite inferiore minimo di un insieme X di elementi, e Π X è il limite inferiore massimo di un insieme X di elementi. Questi non esistono per tutti i set in tutte le algebre booleane; se esistono sempre, si dice che l'algebra booleana è completa.si dice che l'algebra booleana sia completa.si dice che l'algebra booleana sia completa.

2. La teoria algebrica elementare

Diverse costruzioni algebriche hanno definizioni ovvie e proprietà semplici per le BA: subalgebre, omomorfismi, isomorfismi e prodotti diretti (anche di un'infinità di algebre). Alcune altre costruzioni algebriche standard sono più peculiari delle BA. Un ideale in un BA è un sottoinsieme I chiuso sotto +, con 0 come membro e tale che se a ≤ b ∈ I, quindi anche a ∈ I. Anche se non immediatamente ovvio, questo è lo stesso del concetto di teoria degli anelli. Esiste una duplice nozione di filtro (senza controparte negli anelli in generale). Un filtro è un sottoinsieme F chiuso sotto ·, con 1 come membro e tale che se a ≥ b ∈ F, quindi anche a ∈ F. Un ultrafiltro su A è un filtro F con le seguenti proprietà: 0 ∉ F, e per ogni a ∈ A, a ∈ F o - a ∈ F. Per ogni ∈ A, S (a) = {F: F è un ultrafiltro su A e a F}. Quindi S è un isomorfismo su una BA di sottoinsiemi dell'insieme X di tutti gli ultrafiltri su A. Ciò stabilisce il teorema di base della rappresentazione della Pietra e chiarisce l'origine delle BA come algebre concrete di insiemi. Inoltre, gli insiemi S (a) possono essere dichiarati come base per una topologia su X, e questo trasforma X in uno spazio compatto e completamente disconnesso di Hausdorff. Ciò stabilisce una corrispondenza individuale tra la classe di BA e la classe di tali spazi. Di conseguenza, usato molto nella teoria delle BA, molti teoremi e concetti topologici hanno conseguenze per le BA. Se x è un elemento di un BA, lasciamo 0 x = - xe 1 x = x. Se (x (0),… x (m - 1)) è una sequenza finita di elementi di un BA A, allora ogni elemento della sottoalgebra di A generato da {x (0), …,x (m - 1)} può essere scritto come una somma di monomi e (0) x (0) ·… · e (m - 1) x (m - 1) per e in un insieme di funzioni che mappano m = {0,…, M - 1} in 2 = {0, 1}. Questa è un'espressione algebrica del teorema disgiuntivo della forma normale della logica sentenziale. Una funzione f da un insieme X di generatori di un BA A in un BA B può essere estesa a un omomorfismo se e solo se e (0) x (0) ·… · e (m - 1) x (m - 1) = 0 implica sempre che e (0) f (x (0)) ·… · e (m - 1) f (x (m - 1)) = 0. Questo è il criterio di estensione di Sikorski. Ogni BA A può essere incorporato in un BA B completo in modo tale che ogni elemento di B sia il limite inferiore minimo di un insieme di elementi di A. B è unico fino ad A-isomorfismo ed è chiamato il completamento di A. Se f è un omomorfismo da un BA A in un BA B completo e se A è una subalgebra di C,allora f può essere esteso a un omomorfismo di C in B. Questo è il teorema delle estensioni di Sikorski. Un'altra nozione algebrica generale che si applica alle algebre booleane è la nozione di algebra libera. Questo può essere concretamente costruito per BA. Vale a dire, la BA libera su κ è la BA di sottoinsiemi aperti-aperti dello spazio discreto dei due elementi elevato alla potenza κ.

3. Classi speciali di algebre booleane

Esistono molte classi speciali di algebra booleana che sono importanti sia per la teoria intrinseca delle BA che per le applicazioni:

  • Atomic BAs, già menzionato sopra.
  • BA Atomless, che sono definiti BA senza atomi. Ad esempio, qualsiasi BA libero infinito è senza atom.
  • BA completi, definiti sopra. Questi sono particolarmente importanti nelle basi della teoria degli insiemi.
  • Algebre a intervalli. Questi sono derivati da insiemi ordinati in modo lineare (L, <) con un primo elemento come segue. Uno prende l'algebra più piccola dei sottoinsiemi di L contenente tutti gli intervalli semiaperti [a, b) con a in L e b in L o uguale a ∞. Questi BA sono utili nello studio delle algebre di Lindenbaum-Tarski. Ogni BA numerabile è isomorfo a un'algebra ad intervallo, e quindi un BA numerabile può essere descritto indicando un insieme ordinato in modo tale che sia isomorfo all'algebra a intervallo corrispondente.
  • Algebre sugli alberi. Un albero è un insieme parzialmente ordinato (T, <) in cui l'insieme dei predecessori di qualsiasi elemento è ben ordinato. Dato un tale albero, si considera l'algebra dei sottoinsiemi di T generati da tutti gli insiemi della forma {b: a ≤ b} per alcuni a in T.
  • BA Superatomici. Questi sono BA che non sono solo atomici, ma sono tali che ogni subalgebra e immagine omomorfa sono atomiche.

4. Teoria della struttura e funzioni cardinali sulle algebre booleane

Gran parte della teoria più profonda delle algebre booleane, raccontando la loro struttura e classificazione, può essere formulata in termini di determinate funzioni definite per tutte le algebre booleane, con infiniti cardinali come valori. Definiamo alcune delle più importanti di queste funzioni cardinali e dichiariamo alcuni dei fatti strutturali noti, formulati principalmente in termini di essi

  1. La cellularità c (A) di un BA è il supremo delle cardinalità di insiemi di elementi disgiunti a coppie di A.
  2. Un sottoinsieme X di un BA A è indipendente se X è un insieme di generatori liberi della sottoalgebra che genera. L'indipendenza di A è il supremo delle cardinalità di sottoinsiemi indipendenti di A.
  3. Un sottoinsieme X di un BA A è denso in A se ogni elemento diverso da A è ≥ un elemento diverso da X. Il peso π di A è la cardinalità più piccola di un sottoinsieme denso di A.
  4. Due elementi x, y di A sono incomparabili se nessuno dei due è ≤ l'altro. Il supremo di cardinalità del sottoinsieme X di A costituito da elementi incomparabili a coppie è l'incomparabilità di A.
  5. Un sottoinsieme X di A è irrilevante se nella subalgebra non è presente alcun elemento di X generato dagli altri.

Un fatto importante per quanto riguarda la cellularità è il teorema di Erdos-Tarski: se la cellularità di una BA è un cardinale singolare, allora esiste effettivamente un insieme di elementi disgiunti di quella dimensione; per il limite regolare di cellularità (inaccessibile), ci sono controesempi. Ogni BA completo infinito ha un sottoinsieme indipendente delle stesse dimensioni dell'algebra. Ogni BA infinito A ha un sottoinsieme incomparabile irriducibile la cui dimensione è il peso π di A. Ogni algebra di intervallo ha indipendenza numerabile. Un'algebra superatomica non ha nemmeno un sottoinsieme infinito indipendente. Ogni algebra degli alberi può essere incorporata in un'algebra a intervalli. Un BA con solo l'automorfismo identitario è chiamato rigido. Esistono BA rigidi completi, anche algebre a intervalli rigidi e algebre di alberi rigidi.

5. Domande di decidibilità e indecidibilità

Un risultato di base di Tarski è che la teoria elementare delle algebre booleane è decidibile. Anche la teoria delle algebre booleane con un ideale distinto è decidibile. D'altra parte, la teoria di un'algebra booleana con una subalgebra distinta è indecidibile. Sia i risultati di decidibilità che quelli di indecidibilità si estendono in vari modi alle algebre booleane in estensioni della logica del primo ordine.

6. Algebre di Lindenbaum-Tarski

Una costruzione molto importante, che trasporta molte logiche e molte algebre diverse dalle algebre booleane, è la costruzione di un'algebra booleana associata alle frasi in qualche logica. Il caso più semplice è la logica sentenziale. Qui ci sono simboli di frasi e connettivi comuni che creano loro frasi più lunghe: disgiunzione, congiunzione e negazione. Dato un insieme A di frasi in questa lingua, due frasi s e t sono equivalenti al modulo A se e solo se la bicondizionale tra loro è una conseguenza logica di A. Le classi di equivalenza possono essere trasformate in BA in modo tale che + corrisponda alla disgiunzione, · alla congiunzione e - alla negazione. Qualsiasi BA è isomorfo a uno di questo modulo. Si può fare qualcosa di simile per una teoria del primo ordine. Sia T una teoria del primo ordine in una lingua del primo ordine L. Chiamiamo formule φ e ψ equivalenti a condizione che T ⊢ φ ↔ ψ. La classe di equivalenza di una frase φ è indicata da [φ]. Sia A la raccolta di tutte le classi di equivalenza in questa relazione di equivalenza. Possiamo trasformare A in una BA con le seguenti definizioni, che sono facilmente giustificate:

[φ] + [ψ] = [φ ∨ ψ]
[φ] · [ψ] = [φ ∧ ψ]
- [φ] = [¬φ]
0 = [F]
1 = [T]

Ogni BA è isomorfo di un'algebra di Lindenbaum-Tarski. Tuttavia, uno degli usi più importanti di queste algebre classiche di Lindenbaum-Tarski è descriverle per importanti teorie (generalmente teorie decidibili). Per le lingue numerabili questo può essere fatto descrivendo le loro algebre di intervallo isomorfo. Generalmente ciò fornisce una conoscenza approfondita della teoria. Alcuni esempi sono:

Teoria Algebra isomorfa ad intervallo
(1) teoria essenzialmente indecidibile Q, i razionali
(2) BAs
Naturale
Naturale

×

Naturals
Naturals

quadrato degli interi positivi, ordinato lessicograficamente

(3) ordini lineari

A × Q ordinato antilexicograficamente, dove A è

Naturals
Naturals

al

Naturals
Naturals

potere nel suo solito ordine

(4) gruppi abeliani (Q + A) × Q

7. Modelli con valori booleani

Nella teoria dei modelli, si possono assumere valori in qualsiasi BA completo piuttosto che nella BA a due elementi. Questa teoria dei modelli di valore booleano è stata sviluppata intorno al 1950-1970, ma da allora non è stata molto lavorata. Ma un caso speciale, i modelli di valore booleano per la teoria degli insiemi, è molto all'avanguardia dell'attuale ricerca nella teoria degli insiemi. In realtà costituisce un modo equivalente di guardare alla costruzione forzata di Cohen e presenta alcuni vantaggi e svantaggi tecnici. Filosoficamente sembra più soddisfacente del concetto di forzatura. Descriviamo qui questo caso di teoria degli insiemi; diventerà quindi evidente perché vengono prese in considerazione solo le BA concorrenti. Sia B un BA completo. Per prima cosa definiamo l'universo valorizzato booleano V (B). L'universo ordinario set-teorico può essere identificato con V (2), dove 2 è il BA a 2 elementi. La definizione è per ricorsione transfinita, dove α,β sono ordinali e λ è un limite ordinale:

V (B, 0) =
V (B, α + 1) = l'insieme di tutte le funzioni f in modo tale che il dominio di f sia un sottoinsieme di V (B, α) e l'intervallo di f sia un sottoinsieme di B
V (B, λ) = l'unione di tutti V (B, β) per β <λ.

L'universo valutato in B è la classe V (B) corretta che è l'unione di tutte queste V s. Successivamente, si definisce da una ricorsione transfinita piuttosto complicata su insiemi ben fondati il valore di una formula set-teorica con elementi dell'universo valorizzato booleano assegnati alle sue variabili libere

|| x ∈ y || = Σ {(|| x = t || · y (t)): t ∈ dominio (y)}
|| x ⊆ y || = Π {- x (t) + || t ∈ y ||: t ∈ dominio (x)}
|| x = y || = || x ⊆ y || · || y ⊆ x ||
|| ¬φ || = - || φ ||
|| φ ∨ ψ || = || φ || + || ψ ||
|| ∃ x φ (x) || = Σ {|| φ (a) ||: a ∈ V (B)}

Bibliografia

  • Halmos, P., 1963, Lezioni frontali sulle algebre booleane, Princeton: Van Nostrand
  • Heindorf, L. e Shapiro, L., 1994, Algebre booleane quasi proiettive, Dispense in Matematica n. 1596, Berlino: Springer-Verlag
  • Jech, T., 1997, Set Theory, 2nd corrected edition, Berlino, New York: Springer-Verlag
  • Monk, JD e Bonnet, R., (a cura di), 1989, Manuale delle algebre booleane, 3 volumi, Amsterdam: Olanda settentrionale.

Altre risorse Internet

[Si prega di contattare l'autore con suggerimenti.]

Raccomandato: