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.

...