6.- Algebra de Boole

 El álgebra de Boole está formada por un conjunto de variables booleanas, 

$x\in \{0,1\}$. Es decir variables que sólo pueden tomar dos valores: 0 ó 1, verdadero o falso, abierto o cerrado, encendido o apagado, etc.

Un literal l es una variable o su negada. Existen dos tipos: literales con signo positivo cuando representan el valor ‘1’ de la variable ($l=x$), y con signo negativo cuando representa el valor ‘0’ ($l=\overline{x}$).

Una cláusula (o término C) está formada por un conjunto de literales enlazados mediante conectivas lógicas.

Una fórmula lógica $\varphi$ está formada por conjuntos de cláusulas enlazadas mediante conectivas lógicas. Matemáticamente, toda fórmula lógica $\varphi$ de n variables puede verse también como una función multivariable, esto es $\varphi :\{0,1{\}}^n\to \{0,1\}$. En este texto emplearemos indistintamente los términos de función y fórmula.

Una interpretación de una fórmula lógica $\varphi$ es el valor lógico de la fórmula cuando se le asignan valores de verdad (TRUE / FALSE) a sus variables. En consecuencia, existirán tantas interpretaciones como combinaciones de asignaciones posibles.

Se dice que una fórmula lógica es satisfacible cuando existe al menos una interpretación que la hace verdadera.

Una tabla de verdad, o tabla de valores de verdades, es una tabla que muestra el valor de verdad de una cláusula o fórmula lógica, para cada combinación de verdad que se pueda asignar a sus literales