FICHA DE APRENDIZAJE, TEMA 6

1. ¿Qué significa que un vertice de un grafo alcance a otro vértice del grafo? .

Sea G=(V,A) un grafo dirigido.

Sean x_i,x_j ∈V, diremos que x_{j es alcanzable desde} x_{i o que xi alzanza a xj, si existe un camino dirigido de x}i <sub>a xj.

2. ¿Cuántas matrices Ri aparecen en la sucesión del algoritmo de Warshall para calcular la matriz de accesibilidad R de un grafo de 5 vértices? Tendremos 6 matrices, R0, R1, R2, R3, R4, R5.

3. Escribe una condición necesaria para que un grafo sea conexo.
Un grafo es conexo si todo par de vértices está conectado. Si existe un camino entre cualquier par de vértices.

4. Representa grafica y matemáticamente un grafo dirigido no simple que tenga un tour y un camino euleriano.

Grafo que tiene un tour Euleriano.

Representación gráfica:</sub>

Expresión matemática:

G=(V,A)
V={1,2,3,4,5}
A={e1(1,2), e2(2,5), e3(5,3), e4(3,2), e5(2,3), e6(3,4), e7(4,5), e8(5,1)}
T:1,2,5,3,2,3,4,5,1

Grafo con un camino Euleriano.

Expresión gráfica:

Expresión matemática:

G=(V,A)
V={1,2,3,4,5}
A={e1(1,2), e2(2,5), e3(5,3), e4(3,2), e5(2,3), e6(3,4), e7(4,5)}
T:1,2,5,3,2,3,4,5

5. Si G es un grafo no dirigido con unos vértices de grado par y otros de grado impar ¿Cuándo podemos asegurar que G tiene un camino euleriano?

Es condición necesaria que el grafo tenga dos vértices de grado impar para tenr un camino euleriano, pero no es condición suficiente.

FICHA DE APRENDIZAJE, TEMA 5

1. ¿Qué significa que un grafo sea K3,2 ?.

Km,n es el grafo compuesto de un grupo de 3 vértices y otro de 2, tal que cada vértice del primer grupo está conectado con cada del segundo, y no hay más aristas.

Es un grafo no dirigido, bipartido y completo.



2. Explica qué es un grafo bipartido y bipartido completo.

Un grafo bipartido es un grafo cuyos vértices se pueden separa en dos conjuntos disjuntos V1 y V2 y las aristas siempre unen vértices de un conjunto con vértices de otro.

El grafo es bipartido completo cuando todos los vérices del conjunto V1 está unido con todos los vértices del conjunto V2 y viceversa.

3. Representa grafica y matemáticamente un grafo no dirigido conexo con al menos 4 vértices.

G(V,A)

V={a,b,c,d}

A= {e1={a,b}, e2={a,c}, e3={a,d}, e4={d,b}, e5={c,d}}

Un grafo es conexo cuando existe un camino para unir cualquiera de sus vértices.


4. Representa grafica y matemáticamente un grafo dirigido que no sea conexo pero que sea débilmente conexo.

G(V,A)

V={a,b,c,d}

A= {e1=(a,b), e2=(b,a), e3=(a,c), e4=(c,a), e5=(a,d), e6=(b,d), e7=(c,d)}


5. Escribe una condición necesaria para que un grafo sea conexo.

Es necesario que todo par de vértices esté conectado.

6. ¿Cómo calcularías el grado de un vértice de un grafo dirigido a partir de la matriz de adyacencia ?

La suma de los elementos de una columna nos dan el grado de entrada de ese vértice, la suma de los elementos de una fila nos da el grado de salida del vértice.

FICHA DE APRENDIZAJE, TEMA 3

Respuestas (breve) a las siguientes preguntas:

1. ¿Qué significa interpretar una fórmula lógica? ¿y un razonamiento?.

Significa que se interpretan las fórmulas lógicas que se obtiene de la formalización de sentencias, que se extraen del lenguaje natural mediante el lenguaje de la lógica de primer orden.

En resumen: Traducimos las sentencias del lenguaje natural al lenguaje de la lógica de primer orden.

Cuando interpretamos un razonamiento, siempre que esté bien formado, concluiremos si es cierto o falso, pero nunca ambas cosas a la vez.

2. Explica la relación que hay entre demostrar que el conjunto C = {cláusulas – premisas, cláusulas ‐ negación – Conclusión } es insatisfacible y la validez de un razonamiento.

Un razonamiento R: P1, P2,… Pn ⇒ Q es correcto si y sólo si, el conjunto de fórmulas C = {P1, P2,… Pn, ¬Q} es insatisfacible.

Una fórmula lógica es insatisfacible si y sólo si, es falsa para todas sus interpretaciones.

Luego si encontramos, al menos una interpretación verdadera para el conjunto de fórmulas (P1 ∧ P2 ∧ Pn ∧ ¬Q)
La fórmula sería satisfacible y el razonamiento no sería correcto.

3. Si una fórmula lógica A tiene 2³ interpretaciones de las cuales 3 son modelos y 5 contraejemplo ¿cómo se interpreta A para una de las interpretaciones modelo? ¿Para una de las interpretaciones contraejemplo? ¿Y para las 2³ interpretaciones?

Se dice que Ι es una interpretación modelo de una fbf A, si v(A)_I = V.

Se dice que Ι es una interpretación contraejemplo de una fbf A, si v(A)_I = F.

Luego las interpretaciones modelo son Verdaderas y las contraejemplo Falsas.

4. Si en un razonamiento R: P1,…Pn ⇒ Q, de 2ⁿ interpretaciones de sus fbf componentes, se interpretan a) las premisas como verdaderas y la conclusión como falsa para 2ⁿ / 2 interpretaciones y b) para las otras 2ⁿ / 2 restantes se interpretan las premisas y la conclusión como verdaderas ¿Podemos asegurar que el razonamiento R no es correcto para el caso a) pero sí lo es para el caso b)? ¿o es correcto R ya que se da a) y b)? ¿o no es correcto R ya que se da a) y b)? Explica las respuestas.

Para que un razonamiento no sea correcto, basta con encontrar un contraejemplo.
El contraejemplo consiste en que todas las premisas sean ciertas y la conclusión es falsa.
a) Se ha encontrado al menos un contraejemplo, luego el razonamiento no es correcto.
b) Con encontrar un solo contraejemplo en las 2ⁿ restantes (el caso a)) basta para decir que el razonamiento no es correcto.

Escribe la solución de algún ejercicio, de los que hay propuestos, de estudio de validez de razonamiento.

Estudiar la validez del siguiente razonamiento usando el método de contraejemplo.

El inspector Lógicus se encuentra a un ahogado en un charco de 3 cm de profundidad y razona:

“Si una persona se ahoga en un charco así, o estaba inconsciente y boca abajo o se le estaba quemando el bigote e intentaba apagarlo. La persona estaría inconsciente sólo si la hubiesen drogado, pero no tenía síntomas de haber sido drogada, luego está claro que... se le quemaba el bigote”.

1º MC. {aho: persona ahogada, inc: inconsciente, ba: boca abajo, qb: quemaba el bigote, drg: drogado}.

2º Formalización:

aho --> (inc ∧ ba) v qb, inc --> drg, ¬ drg ⇒ qb

FICHA DE APRENDIZAJE, TEMA 2

Respuesta breve a las siguientes pregunta:

Diferencias entre el lenguaje proposicional y el predicativo.

El lenguaje proposicional lo utilizamos para representar conocimientos en donde no sea necesario formalizar propiedades entre individuos o relaciones entre ellos.
Por ejemplo: En lenguaje proposicional, "Algunos alumnos prefieren dormir" se representaría por p, sin embargo esta espresión no nos proporciona información a cerca de los alumnos que prefieren dormir. Lo mismo ocurre con la proposición "Todos los alumnos prefieren dormir", se representaría por la proposición q, por ejemplo y tampoco nos permite referirnos a todos los elementos de un dominio.


El lenguaje de predicados, generaliza el lenguaje proposicional introduciendo nuevos elementos del lenguaje con los que se describen con más detalle los elementos sintácticos de una proposición; ésta se formaliza atendiendo a los individuos, sus propiedades y relaciones, dentro de un conjunto de referencia.

En este ejemplo se visualiza las ventajas del lenguaje de predicados frente al proposicional.

P1. Todas las máquinas transforman energía.
P2. El coche es una máquina.
Q. El coche transforma energía.

Formalizando el conocimiento con el lenguaje de proposiciones, lo primero que hay que hacer es definir un Marco Conceptual, ¿Qué es el Marco Conceptual?

El conjunto de símbolos que elijamos para formalizar las proporciones y se representa con MC. En MC estarán todas las proposiciones atómicas que aparecen en el problema.

M.C.={p: Todas las máquinas transforman energía, q: El coche es una máquina, r: El coche transforma energía.}

El razonamiento p , q ⇒ r

Este razonamiento no es correcto porque desde un punto de vista sintáctico no existe una conexión entre las premisas y la conclusión.

Ahora formalizaré el conocimiento utilizando el lenguaje de los predicados.
M.C.{c: coche, M(x) :x es una máquina. E(x): x transforma energía}

∀x [M(x) -> E(x)], M(c) ⇒ E(c)

- Un par de ejemplos de razonamiento en lenguaje natural, y formalizados en lenguaje de proposiciones.

Hoy cenamos con tus padres pero la semana que viene vendrás con los míos.

M.C.{p: Hoy cenamos con tus padres. q: la semana que viene vendrás con los míos.}

p ^ q

Si mañana vamos de excursión tomaremos el sol.

M.C. {p: mañana vamos de excursión. q: tomaremos el sol.}

p -> q

- Un par de ejemplos de razonamientos en lenguaje natural, y formalizados en lenguaje de predicados.

Todos los alumnos estudian un Grado.

M.C. {Alu(x): x es alumno, Gra(x): x es un grado.}

∀x [Alu(x) -> Gra(x)]

Algunos alumnos son extranjeros

M.C. {Alu(x): x es Alumno, Ex(x): x es extranjero.}


∃x[Alu(x) ^ Ex(x)]

- Un ejemplo de conjunto formado por la unión de otros tres.

Los estudiantes de la comunidad Valenciana forman un conjunto unión de otros tres, los estudiantes Alicantinos, los Castellonenses y los Valencianos.

- Escribe soluciones a los ejercicios propuestos, ver entrada de la bitácora con ejercicios propuestos del tema 2.

INTERPRETACIÓN DE LOS RAZONAMIENTOS LÓGICOS

Método de la tabla de la verdad y del contraejemplo.

Una tabla de verdad es una tabla que muestra el valor semántico de una fbf molecular a partir de todas las combinaciones de valores de verdad que se puedan asignar a sus componentes lógicas. Dicho valor semántico aparece en la última columna de la tabla.
Usada para estudiar la validez de un razonamiento la tabla permite comprobar cómo se interpreta la conclusión cuando todas las premisas son verdaderas.

El método de la Tabla de Verdad consiste en hacer una tabla en donde se interpreta cada fórmula del razonamiento a partir de sus componentes básicas. Cada fila de la tabla es una interpretación.
Se buscan filas en donde las premisas sean verdaderas y se comprueba cómo se interpreta la conclusión. Si la conclusión se interpreta como verdadera el argumento es correcto, si la conclusión es falsa, el argumento es no correcto. Las otras interpretaciones no nos interesan.

El método del contraejemplo supone que el razonamiento dado no es correcto admitiendo la existencia de una interpretación que interprete a las fórmulas premisas como verdaderas y a la fórmula conclusión como falsa; con esta hipótesis se interpretan todas las subfómulas del razonamiento. Si no aparece ninguna contradicción al interpretarlas el razonamiento admite una interpretación contraejemplo y por lo tanto no es correcto, por el contrario, si aparece contradicción el razonamiento es correcto (no admite la hipótesis del contraejemplo).

Ejemplo de clase de teoría, 25/10/11

P1. La lógica no les gusta a los alumnos a menos que sea difícil.

P2. La lógica es difícil sólo si las matemáticas no lo son.

Q. Es suficiente que a los alumnos les gusta la lógica para que las matemáticas no sean difíciles.

P1.
MC.
glo: Gusta lógica
dlo: difícil lógica

Chuleta: "a menos que" siempre niega el antecedente.

fbf. ¬(¬glo)⇒ dlo "es lo mismo que" glo ⇒ dlo

P2
MC.
dlo: difícil lógica
dma: matemáticas difíciles

chuleta: "solo si" acompaña al consecuente.

fbf. dlo ⇒ ¬dma


Q
MC.
dlo: difícil ldlo: difícil lógica
dma: matemáticas difícil

chuleta: "es necesario" acompaña al antecedente.

fbf. glo ⇒ ¬dma

Nota: la tabla ha sido rectificada.

En esta tabla de la verdad no encontramos contradicción, puesto que siempre que las dos proposiciones son verdaderas también lo es la conclusión.

Fórmulas Clausales

¿Qué es la forma Clausal?

Primero habrá que saber lo que entendemos por cláusula (en el argot de la lógica matemática).

Una clausula es un disyunción de literales, ¿Y qué demonios es un literal?. Un literal, en lógica, es una fórmula atómica afirmada o negada.

p, q, ¬p Son ejemplos de literales.

¬p v q v P(a) Es un ejemplo de cláusula.

En este ejercicio intentaré hallar la fórmula Clausal, desde ahora FC, a partir de fórmulas bien formadas (Fbf).

Bien, ¿y cómo se convierte una Fbf en FC? ¿Hay algún truco? Más bien lo que tenemos es un método.

1º.- Eliminar implicadores: A ⇒ B = ¬A v B
2º.- Reducir negación : ¬¬A = A
L. Morgan: ¬(A v B) = ¬A v ¬B; ¬(A v B) = ¬A v ¬B;
3º.- Cada cuantificador con Variables diferentes.
4º.- Eliminar c. existenciales aplicando Skolem.
5º.- Poner los c. universales en cabeza de fórmula.
6º.- Distributiva: A v (B v C) = (A v B) v ( A v C)
7º.- Extraer las cláusulas de la fórmula.
8º.- Cláusulas con argumentos variables diferentes. Constantes
pueden coincidir.

Problema Propuesto. Hallar la fórmula Cláusal.

1- Carlos es modelo.
2- Todos los modelos tienen buen tipo aunque los que no lo son, son atractivos.
3- Para que un sujeto tenga buen tipo es necesario que está macizo.
4- Aunque para que esté macizo es suficiente que sea atractivo

(Nota: No me he vuelto gay, es que tengo una profesora de Lógica.

Voy a intentarlo...

Primero el MC (Marco conceptual).

Mod(carlos): Carlos es modelo.
Bt(x): x es buen tipo.
At(x): x es atractivo.
Ma(x); x está Macizo.

Ahora las Fbf

1- Mod(carlos)
2- ∀x [Mod(x) ⇒ Bt(x) ^ ¬Mod(x) ⇒ At(X) ]
3- Ma(x)⇒ Bt(x)
4- At(x) ⇒ Ma(x)
La fórmula 3 y 4 se unen por una conjunción.

Y Ahora las Clausales

2- ∀x [¬Mod(x) v Bt(x) ^ ¬¬Mod(x)v At(X) ] Paso1
∀x [¬Mod(x) v Bt(x) ^ Mod(x)v At(X) ] Paso 2
Cl1: ¬Mod(x) v Bt(x)
Cl2: Mod(x)v At(X)

3- ¬Ma(x) v Bt(x) Paso 1
4- ¬At(X) v Ma(x) Paso 1

¿Carlos está Macizo? ¿?

Lógica de predicados, Ejercicios

Hoy en vez de hacer un resumén de la clase. No veo muy práctico el copiar los 5 folios de apuntes. Haré los ejercicios propuestos en las transparencias del tema 2.

1º. – Luis, que es alumno de M1, es feliz
2º.- Luis y Ana, que son alumnos de M1 son felices.
3º.- Todos los alumnos de M1 son felices.
4º.- Todos los alumnos de M1 que son felices son amigos de Maripuri.
5º.- Algunos alumnos de M1 son felices y amigos de Maripuri

Escribiré con una fórmula bien formada las siguientes sentencias:

1º Luis, que es alumno de M1, es feliz.

M.C. (Marco conceptual):
lu: Luis
m1: Matematicas 1
Fe: Feliz
Alu: Alumno

Donde Luis y M1 son sujetos
Fe y Alu son predicados

Fbf (fórmula bien formada): Fe(lu)^Alu(lu,m1)

2º.- Luis y Ana, que son alumnos de M1 son felices.

M.C. (Marco conceptual):
lu: Luis
ana: Ana
m1: Matematicas 1
Fe: Feliz
Alu: Alumno

Donde Luis, Ana y M1 son sujetos
Fe y Alu son predicados

Fbf (fórmula bien formada): Fe(lu)^Fe(ana)^Alu(lu,m1)^Alu(ana,m1)


3º.- Todos los alumnos de M1 son felices.

M.C. (Marco conceptual):

m1: Matematicas 1
Fe: Feliz
Alu: Alumno

Fbf: ∀x [Alu (x,m1) ⇒ Fe (x)]


4º.- Todos los alumnos de M1 que son felices son amigos de Maripuri.

M.C:
ma: Maripuri
m1: Matematicas 1
Fe: Feliz
Alu: Alumno
Ami(x,y): x es amigo de y


Fbf: ∀x [Alu (x,m1) ^ Fe (x)⇒ Ami(x,ma) ]

5º.- Algunos alumnos de M1 son felices y amigos de Maripuri

M.C:
ma: Maripuri
m1: Matematicas 1
Fe: Feliz
Alu: Alumno
Ami(x,y): x es amigo de y

Fbf: ∃x [Alu(x,m1) ^ Fe(x) ^ Ami(x,ma)]