Booleana algebro

De Wikipedio
Irez ad: pilotado, serchez

Booleana algebro esas la paro di matematiko, di logiko, e di elektroniko qua interesas su da operacioni e functioni pri la logika varindi.

Per l' algebra strukturo, videz ulo.

La nomo devenas de George Boole, Britana matematikisto, qua dum la mezo di 19ma yarcento restrukturis komplete la logiko en formala sistemo.

Hodie, la booleana algebro trovas multi aplikaji en informo-teorio ed en la konceptajo di elektronika cirkuiti. Ulo esis uzata unesma foye per la cirkuiti di telefonica komutado da Claude Shannon.

Ulo expresas « stando » en funciono di kondicioni: Per exemplo :

Verda = Blua e Flava KAD havas dil blua e dil flava.
desakrochar = (envidio de respondar E sonifo) O envidio di apelar.

Booleana algebro di verat-valori[redaktar | edit source]

On apelas B l'ensemblo konstitucata di du elementi nomizata valori de verata {VERA, FALSA}. Ica ensemblo esas anke notata

  • B = {1 , 0}
  • B = \{\top , \perp \}.

On privilejos dop la noteso B = {1 , 0}.

Sur ica ensemblo on povas definar du legi (od operanta o funcionesi), la legi E ed O e transformanta apelata la komplemento, l'inversigo o la kontreajo.

La lego E[redaktar | edit source]

Olu esas definata del sequa maniero : a E b esas VERA sed e sole sed a esas VERA e b esas VERA. Ta lego esas anke notata

  • \cdot \,
  • \wedge.
  • « & » o « && » en kelka lingui de programeso (Perl, C...)
  • « ∧ » en kelka algebra notizi, od en APL

On privilijos dop la notizo \cdot \,

tabelo del lego .
b\a 0 1
0 0 0
1 0 1

La lego O[redaktar | edit source]

Olu esas definata del sequa maniero : a O b esas VERA sed e sole sed a esas VERA o b esas VERA (o amba esas VERA). Ta lego esas anke notata

  • + \,
  • « | » o « || » en kelka lingui de programeso
  • « ∨ » en kelka algebra notizi, od en APL.

On privilejos dop la noteso + \, ma on prenos garda ke ta lego ne havas raporte kon l'adiciono ke on konocas.

tabelo del lego +
b\a 0 1
0 0 1
1 1 1
hi

La kontreajo[redaktar | edit source]

La kontreajo di "a" esas VERA sed e sole sed a esas FALSA. La kontreajo di a esas notita

  • ne-a
  • \bar{a}
  • \neg (a)
  • « ! » en kelka lingui de programeso
  • « ~ » en kelka algebra notizi, od en APL.

On privilejos dop la noteso \bar{a}.

On obtenas lore \bar{0}=1 e \bar{1}=0

Proprieti[redaktar | edit source]

Asociativata[redaktar | edit source]

Kun la habitala operacioni, certa parentesi esas neutila:
( a + b ) + c = a + (b + c) = a + b + c
( a . b ) . c = a . (b . c) = a . b . c

Comutativata[redaktar | edit source]

L'ordino esas sen importanta. a + b = b + a
a . b = b . a

dispozivata[redaktar | edit source]

Kun la habitala operacioni, esas posibla di disdonar:
a . ( b + c ) = a . b + a . c
Atencez: admise diferanta per raporto ad operacanti + e * habitala:
a + ( b . c ) = ( a + b ) . ( a + c )

Samajibeto[redaktar | edit source]

a + a + a [...] = a
a . a . a [...] = a


komplementivata[redaktar | edit source]

a = \overline{\overline{a}}

(« La lumo esas acendata » = « la lumo ne esas neacendata »)

a + \overline{a} = 1

(« VERA » SED lumo acendata O lumo neacendata → sempre la kazo → sempre VERA)

a . \overline{a} = 0

(« VERA » SED lumo acendata E lumo neacendata → ne-posibla → sempre FALSA)

Strukturo[redaktar | edit source]

On retrovas lore multi la proprieti ke konferas ye B une strukturo.

Priora[redaktar | edit source]

Per faciligar lia kontenajo, olu esis decidata ke ta operacii esus submizanta a mem normi ke l'operacii « de multi la dii », la funciono E (logika multipliko) esas tale priora per raporto ala funciono O (logika sumo) ; on povas, per helpar su, pozar di parentesi en l'operacii

Exemplo :
{ a = 0 ; b = 1 ; c = 1 }
On serchas a . b + c = ???
Unesme on kalkulas a . b:
a . b = 0 . 1
0 . 1 = 0
Pose, on kalkulas 0 + c:
0 + c = c
c = 1
Le fina rezulto esas do:
a . b + c = 1

Teorio de De Morgan[redaktar | edit source]

\overline{ a + b } = \overline{a} . \overline{b}

En la du kazo, l'expreso esas VERA sed a esas falsa E b esas falsa.

\overline{ a . b } = \overline{a} + \overline{b}

En la du kazo, l'expreso esas VERA sed a esas falsa O b esas falsa.

Logika funcioni[redaktar | edit source]

En elektroniko, logika funciono esas nigra boxo ke recevas en eniro certa nombro di logika varindo e ke retrodonas en ekiro logika varindo di enira varindi. L'artiklo logika funciono precizas qual konstruktas la nigra boxi di kelka fundamentala funcioni.

Tabulo di verata permisas di precizar la stato di l'ekiro en funciono di eniri-stati.

On demonstras ke omna logika funciono povas deskriptar su ye helpo di tre operacioni di bazo.

  • +\,
  • \cdot\,
  • \bar{}\,

Logika fondamentala funcioni[redaktar | edit source]

Ol esas ekirinta di tre operacioni di bazo e definas lore

  • funciono di B en B : komplemento o l'inversigo
  • du funcioni di B2 en B ke esas la sumo (od O) e la produkto (od E)
Tabulo di verata de l'inversigo
a \bar a
0 1
1 0
Tabulo di verata del sumo
a b a + b
0 0 0
0 1 1
1 0 1
1 1 1
Tabulo di verata del produkto
a b a.b
0 0 0
0 1 0
1 0 0
1 1 1

Logika komposatala funcioni[redaktar | edit source]

Ta esas la logika funcioni a du varindi. Inter to, on kontas certa sufice interesanta per ke on lia donas nomo.


Exkluziva O[redaktar | edit source]

L' O studiata tala prezento devas komprenar su del segun maniero: « l'un o l'altra o la du ». Ol esas egale apelata « exkluziva O ». L' exkluziva O (o XOR) komprenas su kom : « l'un o l'altra ma ne la du ».

Ol compozas su del segun maniero :

a\ XOR\ b = (a+b).\overline{(a.b)}
Tabulo di verata di XOR
a b a ⊕ b
0 0 0
0 1 1
1 0 1
1 1 0


L' « exkluziva O » esas kelka-foye notata per l' aritmetika signo diferanta di, a qua ol esas equivalanta. Foncione, on uzas anke + cirklata: a ⊕ b.

Equivalante[redaktar | edit source]

L'equivalante (notata EQV) esas VERA se la du eniri havas la sama valoro e FALSA se ne. Ol kompozesas quale sequas :

a\ EQV\ b = \overline{(a+b)}+(a.b)

On povas anke dicas ke :

a\ EQV\ b = \overline{a\ XOR\ b}
Tabulo di verata di EQV
a b a \Leftrightarrow b
0 0 1
0 1 0
1 0 0
1 1 1

Ol advenas ke l'equivalante esas notata per la signo « = », quankam ta selekto ne esas rekomendata enskribata di altra posibla sensi ligata ye ta signo.

Impliko[redaktar | edit source]

L'impliko (notata IMP) skribesas sequante: a\ IMP\ b = \overline{a}+b

Tabulo di verata di IMP
a b a \Rightarrow b
0 0 1
0 1 1
1 0 0
1 1 1

Inhibo[redaktar | edit source]

L'inhibo (notata INH) komposesas sequante :

a\ INH\ b = a.\overline{b}

Ta operacio ne esas komutativa.

Tabulo di verata di INH
a b a.\overline{b}
0 0 0
0 1 0
1 0 1
1 1 0

Exemplo di logika funcioni a tre o quar varindi[redaktar | edit source]

logika funcioni a tre varindi[redaktar | edit source]

Kad on riprenas l'exemplo di telefono, on trovas su koram 3 varindi:

  • a = "telefono sonas"
  • b = "on havas envidio de respondar"
  • c = "on havas envidio d'apelar kelku"

varindo d = "on desakrochas" esas logika funciono di 3 ante-lasti. On skribus ke

Tabulo di verata di desakrochar
a b c d
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

L'observo di tablo indikas ke nua unesma analizo admisis absurda situo : kal la tefono sonas e ke on ne havas envidio de respondar, on ne desakrochas mem kal on havas envidio di apelar kelku.

Ol oportas do modifikar la tabulo di verata tale :

Tabulo di verata di desakrochar2
a b c d2
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1

logika funcioni a quar varindi[redaktar | edit source]

Lernanto questionas su kal ol esas saja di ekirar vespero. Il devas decidar en funciono di quar propozi:

  • a = il havas sat pekunio
  • b = il havas finata sua devi
  • c = la komuna transporto esas strikanta
  • d = l'automobilo de sua patro esas disponebla

Lernanto povus ekirar kal:

  • a = il havas sat pekunio, a = vera
  • b = il havas finata sua devi, do b = vera
  • c = la komuna transporto esas strikanta, do c = falsa
  • d = l'automobilo de sua patro esas disponebla, do d = vera

Do la logika expreso di ekirar en funciono del stato di varindi a, b, c e d ; ed ol povas skribas su tale :

ekirar =  a.b.({\bar c}+d)

mikreganta di expreso[redaktar | edit source]

Logika funciono povas esar determinata

  • sive sub formo di expreso iganta eventar li 3 operi (+\, , \cdot\, , \bar{}\,)
  • sive sub formo di sua tabulo di verata. En ta kazo ol esos sempre posiblar di skribar ta funciono kom sumo de produkti.

Exemplo: En l'exemplo di "desakrochar2", on remarkas ke la rezulto esas a 1 kande (a, b , c) = (0 , 0 , 1) o (0 , 1 , 1) o (1 , 1 , 0) o (1 , 1 , 1).

To permezas di definar d2 per d2 =\bar a.\bar b.c + \bar a.b.c + a.b.\bar c + a.b.c

Ol esas lore interesanta di trovar expreso mikreganta la nombro di termi e la nombro di leteri en omna termo.

To esas l'objektivo di ta tekniki kom la metodo de Quine-Mc Cluskey, Karnaugh-tabulo ....

Exemplo (dop): l'ante-lasta sumo povas esar reduktata en

d2 =\bar a.c + a.b

per faktoreso di du unesma termi per \bar a.c e per faktoreso di du lasta termi per  a.b \,