Ingeniería informática con énfasis en desarrollo de software

Universidad interamericana de panamá

Lic. En ingeniería informática con énfasis en desarrollo de software

Materia Inteligencia artificial

Examen final

Elaborado por:

Kadhir Antonio Araúz Atencio

Cedula: 8-818-2423

Profesor:

Ingeniero Markelov

1. Funciones lógicas de 2 variables, e funciones básicas:

En matemáticas, una función booleana es una función cuyo dominio son las palabras conformadas por los valores binarios 0 ó 1 ("falso" o "verdadero", respectivamente), y cuyo codominio son ambos valores 0 y 1.

Formalmente, son las funciones de la forma ƒ : Bn → B, donde B = {0,1} y n un entero no negativo correspondiente a la aridad de la función.

Definición: Un álgebra booleana es una látice complementada distributiva con al menos dos elementos. Esto excluye el caso trivial de un conjunto parcialmente ordenado con un solo elemento.

Ejemplo 1.

Si S diferente del vacío es un conjunto, el conjunto parcialmente ordenado A = P(S) bajo la relación de inclusión es un álgebra booleana.

Ejemplo 2.

Sea B el conjunto de valores de verdad de las proposiciones, es decir B={0,1}. Este conjunto ordenado por la relación de implicación, esto es, a ≤ b si y sólo si a ⇒ b es un álgebra de boole. En efecto, (B,≤) es una látice puesto que el único subconjunto con dos elementos, que es el mismo B, tiene mínima cota superior (1), y máxima cota inferior (0). La mínima cota superior es 1 porque 0 +1 = 1 y la máxima cota inferior es 0 porque 0• 1 = 0.

Lo dicho anteriormente, también se desprende del hecho de que 0 ≤ 1 y esto debido a que 0 ⇒ 1 es verdadero.

Esta látice es complementada porque 0’ = 1 y 1’ = 0, lo anterior debido a que la negación de una proposición falsa es una proposición verdadera y viceversa. La distributividad se puede verificar utilizando las tablas de verdad para la disyunción y la conjunción.

[pic 1]

Una aplicación importante del álgebra booleana es el álgebra de circuitos de conmutación. Un conmutador es un dispositivo con dos estados que son cerrado y abierto y que se denotarán respectivamente 1 y 0.

En esta forma, un álgebra de circuitos de conmutación no es más que un álgebra booleana con dos elementos a saber: 0 y 1.

1. Formas normales disyuntivas y conjuntivas

EXPRESIONES BOOLEANAS: para entender las formas normales disyuntivas y conjuntivas debemos saber sobre la expresiones boolenaas,

Definición: Una expresión booleana es una sucesión de símbolos que incluye 0,1, algunas variables y las operaciones booleanas.

Para ser más precisos definamos una expresión boolena en n variables x1, x2..., xn recursivamente como:

Los símbolos 0 y 1 y x1, x2,..., xn son expresiones booleanas en x1, x2,... xn.

Si E1 y E2 son expresiones booleanas en x1, x2,... xn también lo son E1 + E2; E1 E2 y E1í.

Ejemplo 1.

Las siguientes son cuatro expresiones booleanas en las tres variables x, y, z:

(x + y)(x + z).1.             x + y.

xíz + xíy + zí.                 z.

Es obvio que las expresiones del lado izquierdo involucran las tres variables, las del lado derecho dos y una variable respectivamente. Las expresiones booleanas 0 y 1 pueden verse como expresiones en cualquier número de variables.

El número de variables de una expresión booleana es el número de letras distintas que aparezcan en la expresión, sin tener en cuenta si están o no complementadas.

Forma normal disyuntiva (FND): Una expresión booleana está en forma normal disyuntiva en n variables x1, x2,... xn, si la expresión es una suma de términos del tipo E1 (x1) × E2( x2) × ... × En(xn), donde Ei(xi) = xi o xií para i = 1, 2,..., n, y ningún par de términos son idénticos. Además se dice que 0 y 1 están en F.N.D en una variable para todo n ≥ 0.

• Teorema(1): Toda expresión booleana que no contiene constantes es igual a una función en forma normal disyuntiva.

La manera de realizar esa transformación la ilustra el siguiente ejemplo.

Ejemplo 2

Escribir (xyí + xz)í + x' en F.N.D

Solución:

( xyí + xz)í + x' = (xyí)í(xz)í + x'

= (xí + y)(xí + zí) + xí

= (xí + y)xí + (xí + y)zí + xí

= xí + xíy + xízí + yzí + xí

= xí + yzí

= xí(y + yí)(z + zí) + yzí(x + xí)

= xí y z + xí y zí + xí yí z + xí yí zí + x y zí

Cualquier expresión booleana puede colocarse en forma normal disyuntiva en más de una forma. Basta cambiar el número de variables.

Ejemplo 3.

f = x y es una expresión booleana en dos variables en F.N.D. Si la multiplicamos por z + zí (que es 1), obtenemos f = x y z + x y zí la cual es una expresión booleana en tres variables escrita en F.N.D.

Se considerará, a menos que se diga otra cosa, que la F.N.D se refiere a aquella forma que contiene el menor número posible de variables. Con esta excepción, se puede demostrar que la F.N.D de una función está determinada unívocamente por la función.

Si se desea escoger sólo uno de los términos posibles en una F.N.D en n variables, es decir, escoger a x o a xí para cada una de las n variables xi, i = 1,2,...,n; hay exactamente 2n términos distintos que pueden aparecer.

La forma normal disyuntiva en n variables, que contiene 2n términos se llama forma normal disyuntiva completa en n variables.

• Teorema(2): Si a cada una de las n variables de una expresión booleana en la F.N.D se le asigna el valor 0 o 1 de una forma arbitraria pero fija, entonces exactamente un término de la F.N.D completa tendrá el valor 1, todos los demás términos tendrán el valor 0.

Demostración. Suponga que a1, a2,... an, representan los valores asignados a x1, x2,... xn, en ese orden, donde cada ai es 0 o 1. Escoja un término de la forma normal completa como sigue: Use xi si ai = 1, y use xií si ai = 0 para cada xi, i = 1,2,...,n. El término así escogido es un producto de n unos, y por lo tanto, es 1. Todos los otros términos contendrán por lo menos un factor 0, y en consecuencia, serán 0.

Una consecuencia de este teorema, es que la F.N.D completa sea identica a 1.

Ejemplo 4.

Sea f(x,y) = xí y + xí yí + x y + x yí. Si se asigna a x el valor de 0 y a y el valor 1 entonces se tendrá:

f(x,y) = 1.1 + 1.0 + 0.1 + 0.0

= 1 + 0 + 0 + 0 = 1.

• Teorema(3): Dos expresiones booleanas son iguales si y sólo si sus respectivas F.N.D son iguales.

• Teorema(4): Para establecer cualquier Identidad en álgebra booleana, es suficiente verificar el valor de cada función para todas las combinaciones de 0 y 1 que pueden asignarse a las variables.

Se concluye entonces, que una expresión booleana está completamente determinada por los valores que toma para cada asignación posible de 0 y 1 a las variables respectivas. Luego las funciones se pueden especificar completamente dando una tabla que represente estas propiedades.

En el diseño de circuitos, esta es precisamente la manera como las expresiones booleanas son construidas. Si tal tabla ha sido dada, entonces la expresión booleana en F.N.D puede escribirse por inspección. A cada conjunto de condiciones para los cuales la expresión booleana sea 1, corresponderá un término en la F.N.D escogida. La suma de estos términos da la función aunque no necesariamente en la forma más simple.

Forma normal conjuntiva. En esta forma cada función se representa como un producto de sumas, en lugar de una suma de productos.

Definición. Una función booleana está en F.N.C en n variables x1, x2,... xn, para n ≥ 0, si la función en un producto de factores del tipo E1 (x1) + E2( x2) + ... + En(xn), donde Ei(xi) = xi o xií para i = 1, 2, ..., n, y ningún par de factores son idénticos. Se dice también que 0 y 1 están en F.N.C en n variables para n ≥ 0.

Teorema. Toda función en un álgebra booleana que no contiene constantes es igual a una función en forma normal conjuntiva.

...