lógica de proposiciones y de predicado · ut4: teoria de grafos y arboles universidad nacional de...

Franco D. Menendez

LABIA

FACET - UNT

Universidad Nacional de Tucumán

Facultad de Ciencias Exactas y Tecnología

Lógica de Proposiciones

y de Predicado

»Propiedad Conmutativa

(E1 E2) (E2 E1)

(E1 E2) (E2 E1)

»Propiedad Distributiva

E1 (E2 E3) (E1 E2) (E1 E3)

E1 (E2 E3) (E1 E2) (E1 E3)

»Propiedad Asociativa

E1 (E2 E3) (E1 E2) E3

E1 (E2 E3) (E1 E2) E3

»Leyes de De Morgan

(E1 E2) ( E1) ( E2)

(E1 E2) ( E1) ( E2)

»Doble Negación

( E1) (E1) 2

UT3: Lógica de Predicados



Cuantificadores

»Cuantificador Universal: Se utiliza para afirmar que TODOS los elementos de un conjunto, cumplen con una condición o propiedad determinada.

x [Plumas (x) Pájaro (x)]

»Cuantificador Existencial: se utiliza para indicar que existen uno o más elementos en el conjunto A que cumple(n) con una condición o propiedad determinada.

x [Pájaro (x)]

»Fórmulas Atómicas son definidos como predicados individuales con sus correspondientes argumentos.

»Literales son definidos como fórmulas atómicas y fórmulas atómicas negadas.

»Fórmulas Bien Formadas, o bien FBF, son definidas recursivamente de la siguiente forma:

⋄Los literales son fórmulas bien formadas (FBF).

⋄Fórmulas Bien Formadas conectadas a través de conectivos son también FBF.

⋄Fórmulas Bien Formadas afectadas por cuantificadores son también FBF. 3




Estructura Relacional

Definición: Sea D un conjunto de elementos. R es una relación n-aria en el Dominio D si R es una relación sobre Dn.

Sea R una relación n-aria sobre un dominio D. El predicado R asociado con la

relación R, está dado por la siguiente expresión:

R(d1, ......, dn) = T si y solo si {d1, ......, dn} R

Por ejemplo:

SQ(x, y) - el conjunto de pares ordenados (x, y), de forma tal que y es el

cuadrado de x.

{(1,1),(2,4),(3,9),(4,16), .....}

SQ(2, 1) = F; SQ(2, 2) = F; SQ(2, 3) = F; SQ(2, 4) = V4




Sintaxis de la Lógica de Predicado

(a) Un conjunto de Símbolos de Predicados, expresados de la siguiente forma :

P = {p1, p2, p3, .... }

(b) Un conjunto de Variables Individuales, expresados de la siguiente forma :

Var = {v1, v2, v3, .... }

(c) Un conjunto de Constantes Individuales, expresadas de la siguiente forma :

Cons = {c1, c2, c3, .... }

(d) Un conjunto de Símbolos de Función, expresados de la siguiente forma :

F = {f1, f2, f3, .... }

(e) Un conjunto de conectivos lógicos que incluyen a la negación, conjunción, disyunción, implicación o condicional y a la equivalencia o doble implicación,

5




(e) Un conjunto de conectivos lógicos que incluyen a la negación, conjunción, disyunción, implicación o condicional y a la equivalencia o doble implicación, representados a través del siguiente conjunto de símbolos:

S = { , , , , }

(f) Un conjunto de cuantificadores: Cuantificador Universal, , y el Cuantificador Existencial, .

(g) Conjunto de Símbolos de puntuación: Paréntesis (, ) y otros.

6




Ejemplo

Como ejemplo de un lenguaje en la lógica de predicados de primer orden, consideremos la siguiente definición informal de la sintaxis de un lenguaje lógico denominado L1:

(a) Símbolos de Predicado = {Edad, Novios}, donde ambos son binarios.

(b) Variables = {x, y, z}

(c) Constantes = {Susana, Roberto, Guillermo, 20, 30, 40, 50, 60}

(d) Conectivos = {, , , , }

(e) Cuantificador = {, }

(f) Puntuación = {( , ) , [ , ] }

(g) Símbolos de Función = {Doble}

El conjunto de términos del lenguaje L1 es el siguiente conjunto:

{Susana, Roberto, Guillermo, 20, 30, 40, 50, 60, x, y, z, doble (0), doble Susana), doble (x), doble (doble (30)), etc.... } 7




Las fórmulas atómicas y las FBF de L1 están definidas de acuerdo a las reglas dadas anteriormente. Ejemplos de FBF de L1 son:

a)Novios (Susana, Roberto), y lo leemos de la siguiente forma : "Susana está de novia con Roberto".

b)Edad (Susana, 20), y se lee como "Susana tiene la edad de 20".

c)Edad (Guillermo, doble (20)), y se lee "Guillermo tiene una edad que es el doble de 20".

d) Novios (Susana, Guillermo), y lo leemos como "Susana no está de novia con Guillermo".

e)x y [Novios (x, y) Novios y, x)], y lo leemos de la siguiente forma : "Para todo x y para todo y, si x está de Novio con y, entonces y está de novio con x". Esto define la simetría del predicado Novios.

f)x Edad (x, 40), y lo leemos "Existe un x cuya edad es de 40 años".

g)Edad (x, y) , y lo leemos de la siguiente forma : "x tiene la edad y".

8




»DEFINICIÓN: es el cuantificador universal y se lee de la siguiente forma: "para todo". es el cuantificador existencial y se lee de la siguiente forma: al menos existe un".

»Para una fórmula Cuantificada, tal como (xA), x es denominada la variable cuantificada o la variable vinculada y A es denominado como la extensión (scope) de la variable cuantificada. Los cuantificadores (incluyendo la variable cuantificada) son operadores que tienen la misma precedencia que la negación. La siguiente fórmula:

(x(( (y p (x, y)) ( (y p (y, x)))))

y que puede ser escrita de la siguiente forma:

x(y p (x, y) y p (y, x))

9




Sustitución de Fórmula

DEFINICIÓN: Sean A una fórmula, x una variable y a una constante. La siguiente expresión

A [x a], representa la sustitución de a por x y está definida por la inducción:

* Si A = A1 , A [x a] = A1[x a].

* Si A = A1 op A2 , A [x a] = A1[x a] op A2[x a].

* Si A = xA1 , A [x a] = A. Similar para A = xA1.

* Si A = yA1 para y ≠ x, A[x a] = yA1[x a]. Similar para A = yA1.

DEFINICIÓN: Sea A una expresión, sea x una variable y sea t un término. Entonces SxtA representa la

expresión que se obtiene al sustituir todas las apariciones de x en A por t. SxtA es denominada como una

particularización (un caso, un ejemplo) de A, y se dice que t es un caso (instancia) de x.

Ejemplo: Syb (P(y) Q(y))

10




Cuadro Semántico

Recordemos que:

Una fórmula A es satisfactoria, si su valor es verdadero para alguna interpretación. Una interpretación satisfactoria es denominada como un Modelo de A. La notación empleada para un modelo es : = A

Una fórmula es Válida si su valor es verdadero para todas las interpretaciones.

Una fórmula lógica o proposición compuesta es Insatisfactoria o Contradictoria, si la misma no es satisfactoria, o sea que es FALSA (F) para todas sus interpretaciones.

Una fórmula lógica es Inválida o No Válida o Falsificable, si no es válida, o sea que su valor es FALSO (F)para alguna interpretación de sus valores de verdad.

11




»DEFINICIÓN: Un cuadro cuya construcción ha finalizado se lo denomina Cuadro Completo. Un cuadrocompleto se dice que está Cerrado si todas sus hojas están marcadas con la notación de cerrado, de otraforma o modo se dice que el cuadro está Abierto.

»TEOREMA: Sea T un cuadro semántico completo para una fórmula A. La expresión A es No Satisfactoriasi y solo si T es cerrado.

»COROLARIO: La expresión A es una expresión lógica satisfactoria si y solo si T está abierto.

»COROLARIO: La expresión A es una expresión lógica válida si y solo si el cuadro semántico para A escerrado.

12




Particularización Universal: regla de inferencia que permite la eliminación del cuantificador universal en una expresión.

x A(x)Sx

t A(x)Ejemplo:

x (gato (X) tiene cola (x))gato (Tom) tiene cola (Tom)

Particularización Existencial: regla de inferencia que permite la eliminación del cuantificador existencial en una expresión.

x A(x)SX

t A (x)Ejemplo:

x (ganocienmillones(X) esrico(x))ganocienmillones(Patricio) esrico(Patricio)

13




14

Grafo: Un grafo G = (V, A) es un conjunto no vacío V (de vértices) y un conjunto A (de

aristas) extraído de la colección de subconjuntos de dos elementos de V. Una arista de G

es pues, un subconjunto {a, b}, con a, b ∈ V, a b.

SubGrafo: Dado un grafo G = (V, A), formamos un grafo H = (V’, A’) de G seleccionando

algunos de los vértices de G (esto es, V’ ⊆ V ). Y, de las aristas que unieran vértices del

conjunto V’ en el grafo original G, nos quedamos con algunas de ellas (o todas).

Grafo Dirigido: Un grafo dirigido G = (V, A) consta de un conjunto no vacío V (de

vértices) y de un conjunto no vacío A (de aristas) que son pares ordenados de elementos

de V y de una función f definida de A en {(a, b), con a, b ∈ V}. Se dice que la arista e es un

bucle o lazo si se cumple que f(e) = (a, a) = (a) para algún a ∈ V. Son grafos en los cuales

se ha añadido una orientación a las aristas, representada gráficamente por una flecha.

UT4: TEORIA DE GRAFOS Y ARBOLES



15




Tabla1: Terminología en la Teoría de Grafos

16

Tipos Aristas Arista Múltiples Bucles

Grafo Simple No dirigido No No

Multigrafo No dirigido Si No

Pseudografo No dirigido Si Si

Grafo Dirigido Dirigido No Si

Multigrafo Dirigido Dirigido Si Si

SubGrafo Recubridor: Dado un grafo conexo y no dirigido, un árbol recubridor de un

grafo es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo

inicial.

SubGrafo Inducido: Dado un grafo conexo y no dirigido, un subgrafo inducido de un

grafo G es un subgrafo que tiene como junto de vertices a un cierto subconjunto de los

vertices de G y como conjunto de aristas a todas aquellas de G cuyos extremos sean dicho

subconjunto de vertices.




Figura 5: Grafo G del Problema 3

El conjunto de vértices de G es V(G) = {1, 2, 3, 4, 5}, mientras que el de las aristas es el siguienteconjunto A(G) = {{1, 2}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}}.

17




Vértice Adyacente: Dado un grafo G = (V, A), diremos que dos vértices v, w ∈ V son adyacentes o vecinos si {v, w} ∈ A.Si e = {v, w}, se dice que la arista e es incidente con los vértices v y w. También se dice que la arista e conecta v con w.Se dice que los vértices v y w son extremos de la arista e.

Grado de Vértice.- El grado de un vértice de un grafo es el número de aristas incidentes en el, exceptuando los bucles,cada uno de los cuales contribuye con dos unidades al grado de un vértice. El grado de un vértice v se denota por δ(v).

δ(v) = grado de v ≡ gr(v) = #{w ∈ V : {v, w} ∈ A(G)} .

Grafo complementario: el grafo complementario de G = (V, A) es el grafo G = (V, A), donde A = P2 (V ) − A representa el conjunto complementario de A; es decir, dos vertices diferentes u, v ∈ V son adyacentes en G si y solo si no lo son en G.

18




Grafo k-regular: Un grafo no dirigido es un grafo k-regular si todos los vértices del grafo tendrían grado k.

En un grafo siempre hay un número par de vértices de grado impar.

»No puede existir un grafo r-regular de s vertices si r y s son impares.

»El número de aristas de un grafo k-regular es (n*k)/2, y por ende, el número de aristas de un grafo completo de n vertices es (n*(n-1))/2

Grafo nulo: de orden n, que se denota por Nn, es un grafo que tiene n vertices y ninguna arista.

Grafo completo: de orden n, que se denota por Kn, es un grafo con n vertices, donde cada vertice es adyacente a todos los demas.

Grado de Entrada: En un grafo dirigido, el grado de entrada o grado negativo de un vértice v, es denotado por δ-(v), esel número de aristas que tienen a v como vértice final.

Grado de Salida: El grado de salida o grado positivo de un vértice v, denotado por δ(v), es el número de aristas quetienen a v como vértice inicial. (nótese que un bucle contribuye con una unidad tanto al grado de entrada como al gradode salida del vértice correspondiente).




ISOMORFISMO: Sean G y G’ dos grafos, con conjuntos de vértices y aristas (V, A) y (V’, A’), respectivamente. Decimosque una aplicación biyectivaφ: V V’ es un isomorfismo de grafos si:

{v, w} ∈ A {φ(v), φ(w)} ∈ A’.

Es decir, si φ conserva las relaciones de vecindad entre vértices. Dos grafos se dicen isomorfos si existe unaaplicación biyectiva entre sus conjuntos de vértices (un cambio de nombres, de etiquetas) que conserve las relacionesde vecindad: si dos vértices son adyacentes con el primer conjunto de etiquetas, tendrían que seguir siéndolo con elsegundo

En el caso de los dos grafos con los que abríamos esta subsección, el lector podría comprobar que la aplicación

φ: {1, 2, 3, 4} {1, 2, 3, 4}

dada por φ(1) = 1, φ(2) = 4, φ(3) = 2 y φ(4) = 3 es un isomorfismo entre los dos grafos

20




Sin embargo, para decidir que dos grafos no son isomorfos contamos con ciertas propiedades de un grafo que se hande conservar por isomorfismos:

1. Ambos grafos han de tener el mismo número de vértices (si no lo tienen, no podremos construir una aplicaciónbiyectiva entre los conjuntos de vértices).

2. Cada vértice ha de mantener sus relaciones de vecindad. En particular, si G = (V, A) y G´ = (V´, A´) son dos grafosisomorfos mediante φ, entonces, para cada v ∈ V :

δ (v) = δ (φ(v)).

3. Con más generalidad, si dos grafos son isomorfos, entonces han de tener la misma sucesión de grados. Sinembargo, el que dos grafos tengan la misma sucesión de grados no garantiza que sean isomorfos

4. La sucesión de grados ha de conservarse, y como sabemos que en todo grafo la suma de los grados coincide con(dos veces) el número de arista, deducimos que dos grafos isomorfos han de tener el mismo número de aristas.

21




ISOMORFISMO DE GRAFOS

Síntesis

un isomorfismo entre dos grafos G y H es una biyección f entre los conjuntos de sus vértices que preserva la relación deadyacencia. Es decir, cualquier par de vértices u y v de G son adyacentes si y solo si lo son sus imágenes, f(u) y f(v),en H.

A pesar de su diferente aspecto, los dos grafos que se muestran a continuación son isomorfos:

22




CLASES DE GRAFOS

GRAFO LINEAL: Diremos que un grafo es un Ln, un grafo lineal con n vértices (n ≥ 2) si tiene n vértices (dos de grado 1y el resto, si los hay, de grado 2) y es isomorfo a:

GRAFO CIRCULAR: Otra clase de grafos muy relevante son los llamados grafos circulares con n vértices (todos degrado 2), para n ≥ 3, que denotaremos por Cn:

GRAFO COMPLETO: Si un grafo con n vértices tiene todas las (n ≥ 2) combinaciones de posibles aristas, diremos queestamos ante el grafo completo con n vértices, Kn:

23

Figura 11: Grafo Lineal




CLASES DE GRAFOS

Bipartito: Un Grafo G = (V, A) es bipartito si V = V1 V2 y V1 V2 = y cada arista de G es de la forma [a, b] con a ∈V1 y con b ∈ V2. Si cada vértice de V1está unido con los vértices de V2 se tiene un grafo bipartito completo.

24




CONEXIÓN DE GRAFOS

Camino: Sean x, y vértices (no necesariamente distintos) de un grafo G = (V, A). Un camino x – y en G es una sucesiónalternada finita (sin lazos):

La longitud de un camino es n, el número de aristas que hay en el camino. (Si n = 0, no existen aristas, x = y, y el caminose denomina trivial.

DEFINICIÓN 17.- Consideremos un camino x – y en un grafo no dirigido G = (V, A):

Si no se repite ninguna arista en el camino x – y, entonces el camino es un recorrido x – y. Un recorrido cerrado es uncircuito.

Cuando ningún vértice del camino x – y se presenta más de una vez,el camino es un camino simple x – y. El término ciclose usa para describir un camino simple cerrado x – y.

25




CONEXIÓN DE GRAFOS

Los términos que utilizamos aquí, paseo, camino, etc., podrían no coincidir con los usados en otros textos. Para ungrafo dirigido utilizaremos el adjetivo dirigido, como se usa, por ejemplo, en caminos dirigidos, caminos simplesdirigidos y ciclos dirigidos.

Cuello: Si G es un grafo, se llama cuello del grafo G al mínimo de las longitudes de los ciclos de G.

Tabla 2: Terminología de caminos en la Teoría de Grafos

26

Vértices Repetidos

Aristas Repetidas

Abierto Cerrado Nombres

Si Si Si Camino

Si Si Si Camino Cerrado

Si No Si Recorrido

Si No Si Circuito

No No Si Camino Simple

No No Si Ciclo




CONEXIÓN DE GRAFOS

TEOREMA 3: Sea G = (V, A) un grafo no dirigido, con a, b ∈ V, con a b. Si existe un recorrido (en G) de a a b, entoncesexiste un camino simple (en G) de a a b.

Conexo: Sea G = (V, A) un grafo no dirigido. Diremos que G es conexo si existe un camino simple entre cualesquiera dosvértices distintos de G.

LEMA 1.- Si G es un grafo conexo y a es una arista puente de G, entonces G \ {a} tiene exactamente dos componentesconexas.

PROPOSICIÓN 1.- Si G es un grafo conexo, entonces

|A(G)| ≥ |V (G)| − 1.

PROPOSICIÓN 2.- Si G es un grafo con k componentes conexas, entonces |A| ≥ |V | − k. 27




CAMINOS EULERIANOS Y HAMILTONIANOS

DEFINICIÓN: Sea G = (V, A), un grafo o multigrafo no dirigido sin vértices aislados. Entonces G tiene un circuitoeuleriano si existe un circuito de G que recorra cada arista del grafo exactamente una vez. Si existe un recorrido abiertode x a y en G que recorra cada arista de G exactamente una vez, este recorrido se denominara recorrido euleriano. Uncamino euleriano es un camino simple que contiene todas las aristas de G.

un camino euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es uncamino cerrado que recorre cada arista exactamente una vez

DEFINICION: Un camino hamiltoniano, en el campo matemático de la teoría de grafos, es un camino de un grafo, unasucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitadoes adyacente al primero, el camino es un ciclo hamiltoniano.

28Figura 22: Grafos no dirigidos G1, G2 y G3




GRAFOS PLANOS

TEOREMA DE DIRAC: Sea G = (V, A) un grafo simple con n vértices para n 3, tal que todos los vértices de G tienengrado mayor o igual a n/2. Entonces G contiene un circuito hamiltoniano.

TEOREMA DE ORE: Sea G = (V, A) un grafo simple con n vértices para n 3, tal que (u) + (v) n, para cada par devértices no adyacentes u y v de G. Entonces G tiene un circuito hamiltoniano..

Grafo Plano: Un grafo G = (V, A), es plano si podemos dibujar a G en el plano de modo que sus aristas se intersequensólo en los vértices de G. Este dibujo de G se conoce como una inmersión (embebido o encaje) de G en el plano

Figura 24: Grafos Planos G1 y G229




GRAFOS PLANOS

TEOREMA: Sea G = (V, A) un grafo o multigrafo plano conexo con V = y A = a. Sea r el número de regiones en elplano determinadas por una inmersión (o representación) plana de G, una de estas regiones tiene unárea infinita y se conoce como región infinita. Entonces: – a + r = 2

COROLARIO: Sea G = (V, A) un grafo o multigrafo plano conexo sin lazos con los valores V = y A = a > 2. y rregiones. Entonces se deben cumplir las siguientes condiciones 3r 2a y a 3 - 6.

Ejemplo: El grafo K5 no tiene lazos y es conexo con 10 aristas y cinco vértices. En consecuencia: 3 - 6 = 15 – 6 = 9 < 10= a. Por lo tanto por el Corolario 5.2, vemos que K5 no es plano.

30




ARBOLES: DEFIINICION Y CARACTERISTICAS

DEFINICIÓN 1.- Un árbol es un grafo conexo y sin ciclos. Un grafo G es un árbol (un conexo sin ciclos) Es conexoy tiene la propiedad de que al eliminar una arista cualquiera del grafo, éste deja de ser conexo.

PROPOSICIÓN 3.-Un grafo G es un árbol (un conexo sin ciclos) Es conexo y se cumple que: |A(G)| = |V (G)| − 1.

TEOREMA 1: Todo árbol con |V | ≥ 2 tiene, al menos, dos vértices de grado 1.

31




Tabla 1: Árboles No Isomorfos Y Distintos

TEOREMA 4.- (Cayley) El número de árboles distintos que se pueden formar con el conjunto de vértices {1, . . . , n} esnn−2.

32

n Árboles no isomorfos Árboles distintos

2 1 1 = 20

3 1 3 = 31

4 2 16 = 42

5 3 125 = 53

6 6 1296 = 64

7 11 16807 = 75

8 23 32768 = 86




ARBOLES CON RAIZ

Todo árbol posee una altura. Recorriendo el mismo en forma de grafo dirigido y considerando que las áristas partendesde los vértices hacia algún otro vértice o hacia alguna hoja, de forma tal que todo camino inicia en la raíz y terminaen una hoja, puede afirmarse que el árbol posee una altura h. Dicha altura será igual a la longitud del camino con másaristas.

DEFINICIÓN: Si G es un grafo no dirigido, entonces G es un árbol dirigido si el grafo no dirigido asociado con G es unárbol. Si G es un árbol dirigido, G es un árbol con raíz si existe un único vértice r en G, llamado raíz, tal que el grado deentrada de r es igual a E (r) = 0 y para todos los demás vértices v, el grado de entrada es E (r) = 1

Los parámetros que manejaremos en un árbol con raíz serán

»el número de vértices, n;

»la altura del árbol, a;

»el número de hojas, h;

»y el tipo de árbol, definido por el entero positivo q (podría ser q-ario o casi q-ario).33




ARBOLES RECUBRIDORES

DEFINICIÓN 3.- Consideremos un grafo G = (V, A). Diremos que un árbol H es árbol recubridor o recubridor de G sicumple que:

V (H) = V (G) (tiene los mismos vértices que G).

A(H) A(G) (tiene algunas—o todas— las aristas de G).

Es decir, es un subgrafo recubridor del grafo inicial que, además, es un árbol. Asegurémonos primero de que talesárboles existen si, como es razonable, partimos de un grafo conexo.

TEOREMA 5.- Un grafo G es conexo si y sólo si tiene, al menos, un árbol recubridor.

34




ARBOL BINARIO

DEFINICIÓN: Un árbol con raíz es binario si para cada vértice v, el grado del mismo es (v)=0, 1 o 2; es decir, si v tienecuando mucho dos hijos. Si (v)= 0 o 2 para todo v, entonces el árbol con raíz es un árbol binario completo.

Ejemplo 12: Ejemplo 13:

35

3ba5/a7

*

/

- - 5 + 3

7 a a b

Figura 6.4.1

– a / 3 +

b 5 Figura 6.4.2

5b/3a




OPERACION BINARIA

DEFINICIÓN: Una operación binaria * tiene tres formas de representación:

⋄1. Notación infija: a * b

⋄2. Notación prefija ( o polaca) : * a b

⋄3. Notación postfija: a b *

DEFINICIÓN: Sea T = (V, A) un árbol con raíz r. Si T no tiene otros vértices, entonces la misma raíz el recorrido en ordenprevio y posterior de T. Si |V| >1. Sean T1, T2, T3,. . ., Tn, los subárboles de T, de izquierda a derecha, entonces:

⋄1. El recorrido de orden previo de T visita primero r y después recorre todos los vértices de T1, en orden previo,después los vértices de T2 en orden previo y así sucesivamente hasta recorrer los vértices de TK en orden previo.

⋄2. El recorrido de orden posterior de T recorre en orden posterior los vértices de los subárboles T1, T2, T3,. . ., TK paradespués llegar a la raíz.,

36




Ejemplo 14: El recorrido en orden previo de los vértices de esteárbol es: 1, 2, 5, 11, 12, 13, 14, 3, 6, 7, 4, 8, 9, 10, 15, 16, 17.

El recorrido en orden posterior visita los vértices en el orden:11, 12, 13, 14, 5, 2, 6, 7, 3, 8, 9, 15, 16, 17, 10, 4, 1

37

DEFINICIÓN 7.-Recorrido en orden simétrico. Sea T = (V, E) un árbol binario con raíz, donde r es la raíz.

1) Si | V | = 1, entonces el vértice r es el recorrido en orden simétrico de T.

2) Si | V | > 1, sean TI y TD los subárboles izquierdo y derecho de T. El recorrido en orden simétrico de T

recorre primero los vértices de TI, en orden simétrico, después visita la raíz y luego recorre, en el orden

simétrico, los vértices de TD.




Ejemplo 15: La lista en orden simétrico es: p, j , q , f , c , k , g , a , d , r , b , h , s , m , e , i , t , n , u

38




Definición

“Un Sistema Experto es un programa de computación inteligente que usa conocimiento yprocesos de inteligencia para resolver problemas que son lo suficientemente difícilescomo para requerir significativa experiencia humana para su solución”.

(Feingenbaum, 1982).

El esquema muestra el funcionamiento de un Sistema Experto basado en el conocimiento, y en donde el Usuario aporta los hechos o información al sistema y recibe de este un consejo o experiencia como respuesta.



UT5 : SISTEMAS EXPERTOS

Los sistemas expertos se conforman por tres componentes principales:»La Base de Conocimientos (Knowledge Database) almacena la totalidad de lainformación específica relativa al campo del saber deseado. Esta escrita en un lenguajeespecífico de representación de los conocimientos que contiene, y en el cual el expertohumano puede definir su propio vocabulario técnico. La información se representamediante reglas de producción o de redes semánticas, en donde la semántica se la puederepresentar mediante Grafos.»La Base de Hechos (Fact Database) almacena los datos propios correspondientes a losproblemas que se desean tratar con la ayuda del sistema. Cumple con la misión dememorizar todos los resultados intermedios, permitiendo conservar el rastro de losrazonamientos llevados a cabo.»El Motor de Inferencias es un programa que, mediante el empleo de los conocimiento,puede resolver el problema que esta especificado. Lo resuelve gracias a los datos quecontiene la base de hechos del sistema experto. Su principal función es la de seleccionar,validar y activar algunas reglas que permiten obtener finalmente la solucióncorrespondiente al problema planteado.




Una Regla es una afirmación lógica que relaciona dos o más objetos e incluye dos partes,la premisa y la conclusión. Cada una de estas partes consiste en una expresión lógicacon una o más afirmaciones objeto-valor conectadas mediante los operadores lógicos«y», «o» o «no».

Forma de Representar el conocimiento de manera naturalSI premisa ENTONCES consecuente

Premisa: Conjunciones de atributos de un mismo dominio.Consecuente: Atributo que pasaran a ser conocidos para el sistema.




Estrategias de Encadenamiento de Inferencias

En un sistema basado en reglas, el mecanismo de inferencia determina cuales

antecedentes de regla, si hay alguno, queda satisfecho por los hechos.

»Método de Encadenamiento hacia adelante: Implica el razonamiento desde los hechos

hacia las conclusiones que resultan de ellos. CLIPS esta diseñado para el

encadenamiento hacia adelante.

»Encadenamiento hacia atrás: Implica el razonamiento en reversa desde una hipótesis,

que habrá de comprobar una posible conclusión, a los hechos que la sustentan. De esta

forma observemos que la hipótesis puede verse como un hecho cuya veracidad esta en

duda y necesita establecerse, siendo esta un objetivo a probar




Preguntas

18/06/2017LABIA 2015

43



BIBLIOGRAFIA»ESTRUCTURAS DE MATEMÁTICAS DISCRETAS. Bernard Kolman. Robert Busby & Sharon Ross. –2003.

»MATEMÁTICA DISCRETA Y LÓGICA. Roberto H. Fanjul – 2005.

»MATEMÁTICAS DISCRETAS - SEXTA EDICIÓN Richard Johnsonbaugh - PRENTICE HALL INC. –2005.

»LÓGICA COMPUTACIONAL. Roberto H. Fanjul. Autor y Editor. Primera Edición – 2005.

»MATEMÁTICAS DISCRETA Y COMBINATORIA Ralph P. Grimaldi- Addison Wesley Longman – 2001.



¡GRACIAS!Preguntas?

» [email protected]



lógica de proposiciones y de predicado · ut4: teoria de grafos y arboles universidad nacional de...

Documents