Algebra booleana

[the.track]

Dovrei dimostrare il teorema di De Morgan in modo possibilmente abbastanza formale.

Se opero in questo modo è corretto? Ha fatto così anche il mio professore, ma mi sembra un po' campata in aria come dimostrazione

Il teorema dice:

[math]\bar{a \cup b}=\bar{a} \cap \bar{b}[/math]

e

[math]\bar{a\cap b}=\bar{a}\cup \bar{b}[/math]

Suppongo che questo teorema valga, allora:

[math]\(a \cup b \) \cap \( \bar{a\cup b}\)=\\
\\
[/math]

[math]
(a \cup b)\cap \( \bar{a} \cap \bar{b}\)= \\
\\
\bar{b}\[ \(a\cap \bar{a}\) \cup \(\bar{a}\cap b\) \]=\\
\\
\bar{b}\cap \bar{a}\cap b =\\
\\
\bar{a}\cap b \cap \bar{b}=0[/math]

Funziona se dico così?

Mi pare un cane che si morde la coda.

[Aleksej]

spero che sia quello che ti serve.
clicca qui

c'è una breve introduzione e poi al punto 1.3 spiega i teoremi di de morgan

[xico87]

l'algebra booleana è una sestupla:
{A,+,*,',1,0}

- A è il supporto dell'algebra, ossia contiene i valori assunti dalle variabili (che nell'algebra di commutazione sono 1 e 0).
- 0 e 1 sono rispettivamente l'elemento neutro della somma logica (unione) e del prodotto logico (intersezione).
- + (unione) e * (intersezione) sono operatori duali, cioè hanno bisogno di due operandi ("*" si può omettere, come nei normali prodotti)
- ' è il simbolo di negato ed è un'operatore unario (l'equivalente del complementare)

ad occhio ha fatto un'operazione ignota al terzo passaggio (il b' cosa fa? moltiplica?)

con le convenzioni dei segni sopra descritte, sfruttando la distributività, dal secondo passaggio diventa così:

(a+b)(a'b') = aa'b' + a'b'b = 0

questa è una prova a posteriori (conosci il risultato e fai vedere che deve funzionare: se (a+b)' fosse diverso da a'b', allora quest'ultimo non sarebbe il complementare di (a+b), quindi non otterresti 0 come risultato)

[the.track]

Capito. Grazie ad entrambi, risolto il problema. :)

Chiudo anche il thread. :)

[ciampax]

Mi permetto di aggiungere una dimostrazione insiemistica:

[math]x\in\overline{A\cup B}\quad\Leftrightarrow\quad x\notin A\cup B\quad\Leftrightarrow\quad x\notin A\quad\wedge\quad x\notin B\quad\Leftrightarrow\quad\\ x\in\overline{A}\quad\wedge\quad x\in\overline{B}\quad\Leftrightarrow\quad x\in\overline{A}\cap\overline{B}[/math]

Spero sia utile.