Lògica binària

De Viquipèdia
Dreceres ràpides: navegació, cerca
Per a altres significats vegeu «Lògica (desambiguació)».

La lògica binària estableix relacions lògiques entre dos valors possibles, associats als conceptes de "vertader" i "fals" o "1" i "0". El principi de doble semàntica afirma que cap proposició és, alhora, vertadera i falsa.

Una operació lògica assigna un valor (vertader o fals) a la combinació de condicions (certes o falses, apagades o enceses, obertes o tancades, etc.) d'un o més factors.

La lògica binària traballa tant amb variables binàries com també amb operacions lògiques

A continuació es descriuen les diferents operacions lògiques:

Semàntica algebraica[modifica | modifica el codi]

Article principal: Àlgebra de Boole

La semàntica algebraica de lògica clàssica directament dóna suport a bivalència en el cas finit: perquè cada Àlgebra de Boole finita és isomorfa a una àlgebra de powerset, els taula veritativa dos valorats expliquen sobre (finitary) lògica clàssica proposicional a la història sencera. El cas d'infinitary és més delicat, tanmateix. El teorema de representació de Pedra ens diu que en el cas general, algebras booleans són subalgebras de powerset algebras. Això significa que la intuïció que la lògica clàssica és al voltant d'un conjunt|joc d'alternatives veritables falses independents no està bé, però està projectant una independència entre alternatives Booleanament valorades que no té una base en semàntica.

Principi de dualitat[modifica | modifica el codi]

Totes les expressions booleanas es mantenen vàlides si s'intercambien els operadors "+" i "·", i els elements "0" i "1".

Així, per obtenir una expressió algebràica dual, s'intercambien el operadors AND i OR i es substitueixen uns per zeros i al revés.

És la base de la informàtica, ja que els 0 i els 1 es poden interpretar com a l'ausencia o l'existencia d'un impuls elèctric determinat. Val a dir, que no cal que sigui l'ausencia o existencia de un corrent, senzillament han de ser valors diferents d'intensitat.

Operacions amb un sol operand[modifica | modifica el codi]

L'única operació possible és la

  • Negació
Negació
a ¬ a
0 1
1 0
Donat un valor binari a, la seva negació ve definida per l'anterior taula de veritat


La logica binaria usa variables binàries i operacions lógiques. Les variables només poden ser dos valors discrets: V (verdader/cert) o bé F (fals), una notació numerica alternativa pot ser l'1 o bé 0, respectivament.

Operacions amb 2 operands[modifica | modifica el codi]

Les més importants i les més usades a la pràctica del càlcul són les dues següents:

  • Suma lògica o Unió
També coneguda com a OR binària. Correspon a la conjunció O: el resultat és cert si ho és l'un O l'altre dels operands.
Donats dos valors binaris a i b, la seva suma o unió ve definida per la següent taula de veritat


a b a+b
0 0 0
0 1 1
1 0 1
1 1 1

Resumint, el resultat serà sempre 1 si almenys una de les dos variables té per valor 1. Nota: Estrictament, entre les operacions de multiplicació i suma lògiques (AND i OR respectivament), només una de les dues es podria considerar fonamental, ja que una sempre es pot obtenir de l'altre combinades amb l'operació de negació (NOT) segons les lleis de Morgan. D'aquesta manera s'aconsegueix la simplificació de moltes operacions lògiques i facilita la resolució de sistemes.


  • Multiplicació o Intersecció
També coneguda com a AND binària. Correspon a la conjunció I: el resultat és cert si ho és l'un I l'altre dels operands.
Donats dos valors binaris a i b, la seva multiplicació o intersecció ve definida per la següent taula de veritat


a b a*b
0 0 0
0 1 0
1 0 0
1 1 1

Com que hi ha 16 maneres possibles de combinar els uns i zeros a la columna de resultats, es poden definir 16 operacions binàries, tot i que no totes tenen la mateixa importància o interès. Les següents són les més importants després de les ja indicades; s'usen molt sovint per definir la funció a realitzar per un circuit (portes lògiques)


  • Implicació
Correspon al concepte clàssic d'implicació o condició suficient: Si a és cert, b també ho és.
La implicació es pot expressar amb les operacions NOT i OR: a→b = |a + b
Donats dos valors binaris a i b, la seva implicació ve definida per la següent taula de veritat


a b a→b
0 0 1
0 1 1
1 0 0
1 1 1


  • Suma binària o Diferent
També coneguda com a OR exclusiu. Correspon a la taula de la suma aritmètica si els sumands estan escrits en base 2, i es defineix dient que el resultat és cert si ho és l'un O l'altre dels operands, però no tots dos. Observeu que això vol dir que els dos operands han de ser diferents.
Donats dos valors binaris a i b, l'OR exclusiu ve definida per la següent taula de veritat


a b a/b
0 0 0
0 1 1
1 0 1
1 1 0


  • Igual o NOR exclusiu
És la negació de l'OR exclusiu: el resultat és cert si tots dos operands són certs o tots dos falsos, és a dir són iguals.
Donats dos valors binaris a i b, la seva igualtat ve definida per la següent taula de veritat


a b a=b
0 0 1
0 1 0
1 0 0
1 1 1


  • NOR o Ni
És la negació de l'OR: el resultat és cert només si cap dels dos operands és cert, és a dir no és cert NI l'un NI l'altre.


Donats dos valors binaris a i b, l'operació NI ve definida per la següent taula de veritat


a b a|b
0 0 1
0 1 0
1 0 0
1 1 0


  • NAND
És la negació de l'AND: el resultat és cert només si algun dels dos operands és fals, és a dir no són tots dos certs.


Donats dos valors binaris a i b, l'operació NAND ve definida per la següent taula de veritat


a b a†b
0 0 1
0 1 1
1 0 1
1 1 0

Cal dir que totes aquestes operacions es poden escriure les unes en funció de les altres i usualment s'usen només les tres primeres: NO, OR, i AND. Però es poden posar de forma més condensada (encara que evidentment menys pràctica); en particular es pot treballar únicament amb l'OR exclusiu.

El coneixement a fons de les diverses comportes lògiques és indispensable en el treball d'investigació, estudis de enginyries i reparacions electròniques de laboratori.

Les regles de la manipulació formal d'aquests signes constitueixen l'anomenada Àlgebra de Boole

Axiomes[modifica | modifica el codi]

Propietats que defineixen les regles precises per transformar unes expressions en altres equivalents. Els axiomes són propietats primitives.

Propietat commutativa

A + B= B + A \,\!
A \cdot B=B\cdot A

Propietat associativa

A+(B+C)=(A+B)+C=A+B+C \,\!
A \cdot (B\cdot C)=(A \cdot B) \cdot C=A \cdot B \cdot C \,\!

Propietat distributiva

A \cdot (B+C)=A\cdot B+A\cdot C
A+(B \cdot C)=(A + B) \cdot (A + C)

Altres propietats

  • 0\cdot A=0
  • 1\cdot A=A
  • 0+A=A \,\!
  • 1+A=1 \,\!
  • \overline{\overline{A} \;} \;=A
  • A + A= A \,\!
  • A\cdot \; A= A
  • A+ \overline{A} \;=1
  • A\cdot \;\overline{A} \;=0
  • A+(A \cdot B)=A
  • A \cdot (A + B)=A
  • A+(\overline{A} \cdot B)=A+B
  • A \cdot (\overline{A} + B)=A \cdot B

Lleis de De Morgan

  • \overline{(A+B)} \;= \overline{A} \;\cdot \;\overline{B} \;
  • \overline{(A\cdot \;B)} \;= \overline{A} \;+\overline{B} \;


Operadors no Fundamentals XOR, XNOR e IMPLIES

Els operadors no fundamentals poden expressar-se a partir de los operadors fundamentals


  • XOR:
A \oplus \; B= \overline{A} \;\cdot \;B +\overline{B} \;\cdot \;A
0\oplus \;0=0 \,\!
0\oplus \;1=1 \,\!
1\oplus \;0=1 \,\!
1\oplus \;1=0 \,\!

XOR es coneix com a “OR exclusiva”


  • XNOR:
A \bigodot \; B=A \cdot \; B +\overline{B} \; \cdot \; \overline{A} \;
0\bigodot \;0=1 \,\!
0\bigodot \;1=0 \,\!
1\bigodot \;0=0 \,\!
1\bigodot \;1=1 \,\!


XNOR equival a “sí i només si”


  • IMPLIES:
A \rightarrow \; B = \overline{A} \; + B \,\!
0\rightarrow \;0=1 \,\!
0\rightarrow \;1=1 \,\!
1\rightarrow \;0=0 \,\!
1\rightarrow \;1=1 \,\!
IMPLIES equival a “si llavors”