El álgebra booleana o cálculo booleano, es la parte de las matemáticas que trata con un enfoque algebraico de la vista lógica en términos de variables , de operadores y funciones sobre variables lógicas, que permite utilizar técnicas algebraicas para tratar expresiones bivaluadas del cálculo de proposiciones . Fue iniciado en 1854 por el matemático británico George Boole . Hoy en día, el álgebra de Boole encuentra muchas aplicaciones en la informática y en el diseño de circuitos electrónicos .
Fue utilizado por primera vez para circuitos de conmutación telefónica por Claude Shannon .
El álgebra de Boole de funciones lógicas permite modelar el razonamiento lógico , expresando un "estado" en función de condiciones. Por ejemplo, si estudiamos la expresión Comunicación y la expresión Recoger;
Comunicación = transmisor Y receptor
La comunicación sería "VERDADERA" si las variables Remitente Y Receptor estuvieran activas (esta es una función lógica dependiendo de las variables Remitente y Receptor )Contestar = (timbre Y decisión de contestar) O decisión de llamar
Para recoger sería “TRUE” o bien si escucha el sonar de forma simultánea y que decida respuesta , o ( O ) si simplemente decide llamar .Siendo el álgebra booleana un dominio común a tres disciplinas, nos encontramos con diferentes notaciones para designar el mismo objeto. En el resto del artículo indicaremos las distintas notaciones, pero privilegiaremos una para mantener cierta homogeneidad.
Llamamos B al conjunto formado por dos elementos llamados valores de verdad {VERDADERO, FALSO}. Este conjunto también se anota
con para y para .
La notación se verá favorecida en lo siguiente .
En este conjunto podemos definir dos leyes (u operaciones) binarias, las leyes Y y O, y una operación unaria, la negación (o el complemento).
Para todos los siguientes ejemplos y propiedades,
Tabla de leyes ET | ||
b \ a | 0 | 1 |
0 | 0 | 0 |
1 | 0 | 1 |
Se define de la siguiente manera: a Y b es VERDADERO si y solo si a es VERDADERO yb es VERDADERO.
Esta ley también se observa:
A continuación, se favorecerá la notación “ ”.
La tabla de esta ley (análogo a una adición o multiplicación tabla ) no es una tabla de verdad .
Tabla de la ley O | ||
b \ a | 0 | 1 |
0 | 0 | 1 |
1 | 1 | 1 |
Se define de la siguiente manera: a O b es VERDADERO si y solo si a es VERDADERO ob es VERDADERO. (En particular, si a es verdadero y b también es cierto, entonces a OR b es verdadero).
Esta ley también se observa:
Se dará preferencia en la siguiente notación , pero se tendrá cuidado de que esta ley no es la adición habitual en Z / 2 Z . Por eso, en matemáticas y en lógica matemática , la notación no se usa para designar el "o inclusivo": se reserva para el " o exclusivo ", operación que (unida al "y") hace que cualquier álgebra de Boole un anillo booleano , en particular un Z / 2 Z - álgebra .
La negación de a es VERDADERA si y solo si a es FALSO.
Se nota la negación de a:
La notación se verá favorecida en lo siguiente .
Luego obtenemos y .
Los operadores se ven afectados por varias propiedades comunes:
Además, cada operador tiene un elemento neutro y un elemento absorbente :
Son posibles simplificaciones como:
el teorema del consenso se aplica a los operadores del álgebra de Boole:
Finalmente, siguen el principio de complementariedad:
Luego encontramos todas las propiedades que le dan a B una estructura de álgebra de Boole .
PrioridadPara simplificar las escrituras, es habitual que las operaciones booleanas estén sujetas a las mismas reglas de prioridad que las operaciones aritméticas habituales: la función Y (multiplicación lógica) tiene prioridad sobre la función O (suma lógica). Entonces :
Todavía es posible colocar paréntesis en los cálculos para cambiar el orden de prioridad de las operaciones.
Teorema de de Morgan
Primera ley de De Morgan (negación de disyunción)
se expresa por la siguiente igualdad
En ambos casos, la expresión sólo será TRUE |
Segunda ley de De Morgan (negación de la conjunción)
En ambos casos, la expresión sólo será falsa |
Matemáticamente, una función lógica o operador lógico es una aplicación que B n en B .
En electrónica , una función lógica es una caja negra que recibe un cierto número de variables lógicas como entrada y que genera una variable lógica en función de las variables de entrada. La función lógica del artículo explica cómo construir las cajas negras de algunas funciones fundamentales.
Una tabla de verdad permite especificar el estado de la salida según los estados de las entradas. Caracteriza la función lógica.
Cualquier tabla de verdad, y por lo tanto cualquier función lógica, se puede describir utilizando las tres operaciones básicas:
También probamos que hay funciones exactamente lógicas de los parámetros. De hecho, basta con considerar todas las tablas de verdad posibles, o considerar el desarrollo de una función de parámetros.
Vienen de las tres operaciones básicas y luego definen
|
|
|
|
Estas son las funciones lógicas de dos variables. Entre estos, hay algunos lo suficientemente interesantes como para que se les dé un nombre.
Disyunción exclusivaTabla de verdad XOR | ||
a | B | a b |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
El IO estudiado hasta ahora debe entenderse de la siguiente manera: "uno o el otro o ambos". También se le llama "OR inclusivo". El OR exclusivo (o XOR para 'e X clusive OR' ) se entiende como: "uno u otro, pero no ambos".
a XOR bTambién podemos definirlo con un módulo sobre una suma ordinaria:
El "exclusivo o" a veces se denota con el signo aritmético ( diferente de ). Funcionalmente, se utiliza también un + rodeada: .
Propiedad : cualquier tabla de verdad, cualquier función lógica, se puede describir utilizando la constante 1 y las dos operaciones: disyunción exclusiva y conjunción, porque:, y
EquivalenciaTabla de verdad EQV | ||
a | B | a b |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
La equivalencia (indicada EQV o XNOR) es verdadera si las dos entradas tienen el mismo valor y falsa en caso contrario. Es la negación del "o exclusivo".
La equivalencia se puede escribirLa equivalencia a menudo se indica mediante el signo . También se puede notar “==” en ciertos lenguajes (C, C ++, PHP…) y “⊙” en electrónica.
IntervenciónTabla de verdad IMP | ||
a | B | a b |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
Esta operación no es conmutativa . a es una condición suficiente para b, que es una condición necesaria para a.
Pero
Dibujo :
De la declaración “SI vivo en Francia (metropolitana), ENTONCES vivo en Europa. » , Podemos deducir « SI no vivo en Europa, ENTONCES no vivo en Francia. » Pero no « SI no vivo en Francia, ENTONCES no vivo en Europa. » Porque puedo vivir en Europa en otro lugar que no sea Francia, sin contradecir la afirmación inicial.
InhibiciónTabla de verdad INH | ||
a | B | |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | 0 |
Si a es VERDADERO, la expresión es VERDADERO, EXCEPTO si b es VERDADERO.
Esta operación no es conmutativa.
Mesa de la verdad para desenganchar | ||||||||||||||||||||||||||||||||||||||||||
a | B | vs | 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 |
Legalidad Contestar = (timbre Y decisión de contestar) O decisión de llamar traduce la siguiente situación práctica: Descuelgamos un teléfono cuando decidimos llamar a alguien o cuando suena el teléfono y decidimos contestar .
Se compone de tres variables:
la variable d = "Recoger" es una función lógica de las 3 anteriores y se puede escribir d = ab + c
La tabla de verdad de esta función d es entonces la siguiente (a la derecha):
Tabla de la verdad de stall2 | ||||||||||||||||||||||||||||||||||||||||||
a | B | vs | 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 |
La tabla indica una situación absurda: cuando decides llamar a alguien y suena el teléfono sin que quieras contestar, contesta de todos modos. Una modificación de la tabla como opuesta corregiría este absurdo. Esta tabla corresponde a una función lógica Pick up d2 o d2 que se puede determinar y simplificar mediante .
Función lógica de cuatro variablesUn buen estudiante se pregunta si es prudente salir una noche. Debe decidir según cuatro variables:
Este estudiante podrá salir si:
Por tanto, la expresión lógica para salir según el estado de las variables a, b, cyd se puede escribir de la siguiente manera:Salir =
Se puede determinar una función lógica
Ejemplo: En el ejemplo de "Pick up2", la lectura de la tabla muestra que es igual a cuando o o o .Esto hace posible definir d2 por
Es posible encontrar una expresión que minimice el número de términos y el número de letras de cada término. Este es el objetivo de algunos técnicos como el método Quine-McCluskey , los diagramas de Karnaugh , el método de consenso , la polarización dual ...
Ejemplo (continuación): la suma anterior se puede reducir mediante la factorización de los dos primeros términos por y la factorización de los dos últimos términos por
Las expresiones lógicas a menudo se representan en informática como una estructura de árbol .
Varios subárboles (o ramas) se adjuntan a un primer vértice (raíz). Los vértices del callejón sin salida se llaman hojas.
Cada vértice interno corresponde a un selector booleano "si entonces de lo contrario ", que reduce una pregunta a dos subpreguntas más simples, posiblemente reducidas a 1 / verdadero o 0 / falso.
La evaluación de una función f en función de una variable q elegida para la primera pregunta es entonces , lo que da lugar a dos expresiones independientes de .
Cualquiera ; podemos escribir
Los árboles en función de la expresión y el orden de las preguntas, para una misma expresión algunos cuestionarios serán más sencillos que otros.