Relación 2b

2016-02-25T19:49:41Z

Edupalhid:

Edupalhid: /* Relación 2b: Sintaxis y semántica de la Lógica proposicional */

Relación 2a

2016-02-24T19:29:41Z

Edupalhid:

<source lang = "haskell">

-- SintaxisSemanticaProp.hs
-- Lógica proposicional: Sintaxis y semántica
-- José A. Alonso Jiménez <jalonso@us.es>
-- ---------------------------------------------------------------------

module SintaxisSemantica where

-- ---------------------------------------------------------------------
-- Librerías auxiliares --
-- ---------------------------------------------------------------------

import Data.List

-- ---------------------------------------------------------------------
-- Gramática de fórmulas prosicionales --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 1: Definir los siguientes tipos de datos:
-- * SímboloProposicional para representar los símbolos de proposiciones
-- * Prop para representar las fórmulas proposicionales usando los
-- constructores Atom, Neg, Conj, Disj, Impl y Equi para las fórmulas
-- atómicas, negaciones, conjunciones, implicaciones y equivalencias,
-- respectivamente.
-- ---------------------------------------------------------------------

type SimboloProposicional = String

data Prop = Atom SimboloProposicional
| Neg Prop
| Conj Prop Prop
| Disj Prop Prop
| Impl Prop Prop
| Equi Prop Prop
deriving (Eq,Ord)

instance Show Prop where
show (Atom p) = p
show (Neg p) = "no " ++ show p
show (Conj p q) = "(" ++ show p ++ " /\\ " ++ show q ++ ")"
show (Disj p q) = "(" ++ show p ++ " \\/ " ++ show q ++ ")"
show (Impl p q) = "(" ++ show p ++ " --> " ++ show q ++ ")"
show (Equi p q) = "(" ++ show p ++ " <--> " ++ show q ++ ")"

-- ---------------------------------------------------------------------
-- Ejercicio 2: Definir las siguientes fórmulas proposicionales
-- atómicas: p, p1, p2, q, r, s, t y u.
-- ---------------------------------------------------------------------

p, p1, p2, q, r, s, t, u :: Prop
p = Atom "p"
p1 = Atom "p1"
p2 = Atom "p2"
q = Atom "q"
r = Atom "r"
s = Atom "s"
t = Atom "t"
u = Atom "u"

-- ---------------------------------------------------------------------
-- Ejercicio 3: Definir la función
-- no :: Prop -> Prop
-- tal que (no f) es la negación de f.
-- ---------------------------------------------------------------------

no :: Prop -> Prop
no = Neg

-- ---------------------------------------------------------------------
-- Ejercicio 4: Definir los siguientes operadores
-- (/\), (\/), (-->), (<-->) :: Prop -> Prop -> Prop
-- tales que
-- f /\ g es la conjunción de f y g
-- f \/ g es la disyunción de f y g
-- f --> g es la implicación de f a g
-- f <--> g es la equivalencia entre f y g
-- ---------------------------------------------------------------------

infixr 5 \/
infixr 4 /\
infixr 3 -->
infixr 2 <-->
(/\), (\/), (-->), (<-->) :: Prop -> Prop -> Prop
(/\) = Conj
(\/) = Disj
(-->) = Impl
(<-->) = Equi

-- ---------------------------------------------------------------------
-- Símbolos proposicionales de una fórmula --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 5: Definir la función
-- símbolosPropFórm :: Prop -> [Prop]
-- tal que (símbolosPropFórm f) es el conjunto formado por todos los
-- símbolos proposicionales que aparecen en f. Por ejemplo,
-- símbolosPropFórm (p /\ q --> p) ==> [p,q]
-- ---------------------------------------------------------------------

simbolosPropForm :: Prop -> [Prop]
simbolosPropForm (Atom f) = [(Atom f)]
simbolosPropForm (Neg f) = simbolosPropForm f
simbolosPropForm (Conj f g) = union (simbolosPropForm f) (simbolosPropForm g)
simbolosPropForm (Disj f g) = union (simbolosPropForm f) (simbolosPropForm g)
simbolosPropForm (Impl f g) = union (simbolosPropForm f) (simbolosPropForm g)
simbolosPropForm (Equi f g) = union (simbolosPropForm f) (simbolosPropForm g)

-- ---------------------------------------------------------------------
-- Interpretaciones --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 6: Definir el tipo de datos Interpretación para
-- representar las interpretaciones como listas de fórmulas atómicas.
-- ---------------------------------------------------------------------

type Interpretacion = [Prop]

-- ---------------------------------------------------------------------
-- Significado de una fórmula en una interpretación --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 7: Definir la función
-- significado :: Prop -> Interpretación -> Bool
-- tal que (significado f i) es el significado de f en i. Por ejemplo,
-- significado ((p \/ q) /\ ((no q) \/ r)) [r] ==> False
-- significado ((p \/ q) /\ ((no q) \/ r)) [p,r] ==> True
-- ---------------------------------------------------------------------

significado :: Prop -> Interpretacion -> Bool
significado (Atom f) i = (elem (Atom f) i)
significado (Neg f) i = not (significado f i)
significado (Conj f g) i = (significado f i)&&(significado g i)
significado (Disj f g) i = (significado f i)||(significado g i)
significado (Equi f g) i = (significado f i)==(significado g i)
significado (Impl f g) i
|((significado f i)==True)&&((significado g i))==False=False
|otherwise = True

{-Otra opción:
esAtomica :: Prop -> Bool
esAtomica (Atom _) = True
esAtomica f = False
significado f y | esAtomica f = elem f y
significado (Neg x) xs = not (significado x xs)
significado (Disj x y) xs = not (all (==False) [significado x xs,
significado
y xs])
significado (Conj x y) xs = all(==True) [significado x xs, significado y xs]
significado (Impl x y) xs |significado x xs == True && significado y xs
== False = False
|otherwise = True
significado (Equi x y) xs = significado x xs == significado y xs
-}
-- ---------------------------------------------------------------------
-- Interpretaciones de una fórmula --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 8: Definir la función
-- subconjuntos :: [a] -> [[a]]
-- tal que (subconjuntos x) es la lista de los subconjuntos de x. Por
-- ejmplo,
-- subconjuntos "abc" ==> ["abc","ab","ac","a","bc","b","c",""]
-- ---------------------------------------------------------------------

subconjuntos :: [a] -> [[a]]
subconjuntos [] = [[]]
subconjuntos (x:xs) = (map (x:) (subconjuntos xs))++(subconjuntos xs)

-- ---------------------------------------------------------------------
-- Ejercicio 9: Definir la función
-- interpretacionesForm :: Prop -> [Interpretación]
-- tal que (interpretacionesForm f) es la lista de todas las
-- interpretaciones de f. Por ejemplo,
-- interpretacionesForm (p /\ q --> p) ==> [[p,q],[p],[q],[]]
-- ---------------------------------------------------------------------

interpretacionesForm :: Prop -> [Interpretacion]
interpretacionesForm f = subconjuntos (simbolosPropForm f)

{- Otra opción:
interpretacionesForm = subconjuntos.simbolosPropForm
-}

-- ---------------------------------------------------------------------
-- Modelos de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 10: Definir la función
-- esModeloFormula :: Interpretacion -> Prop -> Bool
-- tal que (esModeloFormula i f) se verifica si i es un modelo de f. Por
-- ejemplo,
-- esModeloFormula [r] ((p \/ q) /\ ((no q) \/ r)) ==> False
-- esModeloFormula [p,r] ((p \/ q) /\ ((no q) \/ r)) ==> True
-- ---------------------------------------------------------------------

esModeloFormula :: Interpretacion -> Prop -> Bool
esModeloFormula i f = significado f i

-- ---------------------------------------------------------------------
-- Ejercicio 11: Definir la función
-- modelosFormula :: Prop -> [Interpretacion]
-- tal que (modelosFormula f) es la lista de todas las interpretaciones
-- de f que son modelo de F. Por ejemplo,
-- modelosFormula ((p \/ q) /\ ((no q) \/ r))
-- ==> [[p,q,r],[p,r],[p],[q,r]]
-- ---------------------------------------------------------------------

modelosFormula :: Prop -> [Interpretacion]
modelosFormula f = [i|i <-(interpretacionesForm f), esModeloFormula i f]

-- ---------------------------------------------------------------------
-- Fórmulas válidas, satisfacibles e insatisfacibles --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 12: Definir la función
-- esValida :: Prop -> Bool
-- tal que (esValida f) se verifica si f es válida. Por ejemplo,
-- esValida (p --> p) ==> True
-- esValida (p --> q) ==> False
-- esValida ((p --> q) \/ (q --> p)) ==> True
-- ---------------------------------------------------------------------

esValida :: Prop -> Bool
esValida f = null((interpretacionesForm f)\\( modelosFormula f))

{- Otra opción:
esValida f = length(modelosFormula f)==length(interpretacionesForm f)
-}
-- ---------------------------------------------------------------------
-- Ejercicio 13: Definir la función
-- esInsatisfacible :: Prop -> Bool
-- tal que (esInsatisfacible f) se verifica si f es insatisfacible. Por
-- ejemplo,
-- esInsatisfacible (p /\ (no p)) ==> True
-- esInsatisfacible ((p --> q) /\ (q --> r)) ==> False
-- ---------------------------------------------------------------------

esInsatisfacible :: Prop -> Bool
esInsatisfacible f = null (modelosFormula f)

{- Otra opción:
esInsatisfacible = null. modelosFormula
-}

-- ---------------------------------------------------------------------
-- Ejercicio 14: Definir la función
-- esSatisfacible :: Prop -> Bool
-- tal que (esSatisfacible f) se verifica si f es satisfacible. Por
-- ejemplo,
-- esSatisfacible (p /\ (no p)) ==> False
-- esSatisfacible ((p --> q) /\ (q --> r)) ==> True
-- ---------------------------------------------------------------------

esSatisfacible :: Prop -> Bool
esSatisfacible f = not( null (modelosFormula f))

{- Otra opción:
esSatisfacible = not.esInsatisfacible
-}

-- ---------------------------------------------------------------------
-- Símbolos proposicionales de un conjunto de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 15: Definir la función
-- unionGeneral :: Eq a => [[a]] -> [a]
-- tal que (unionGeneral x) es la unión de los conjuntos de la lista de
-- conjuntos x. Por ejemplo,
-- unionGeneral [] ==> []
-- unionGeneral [[1]] ==> [1]
-- unionGeneral [[1],[1,2],[2,3]] ==> [1,2,3]
-- ---------------------------------------------------------------------

unionGeneral :: Eq a => [[a]] -> [a]
unionGeneral [] = []
unionGeneral (xs:xss) = union xs (unionGeneral xss)
-- ---------------------------------------------------------------------
-- Ejercicio 16: Definir la función
-- simbolosPropConj :: [Prop] -> [Prop]
-- tal que (simbolosPropConj s) es el conjunto de los símbolos
-- proposiciones de s. Por ejemplo,
-- simbolosPropConj [p /\ q --> r, p --> s] ==> [p,q,r,s]
-- ---------------------------------------------------------------------

simbolosPropConj :: [Prop] -> [Prop]
simbolosPropConj s = unionGeneral [simbolosPropForm f|f<-s]

{- Otra Opción:
simbolosPropConj =nub.concat.map(simbolosPropForm)
-}
-- ---------------------------------------------------------------------
-- Interpretaciones de un conjunto de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 17: Definir la función
-- interpretacionesConjunto :: [Prop] -> [Interpretacion]
-- tal que (interpretacionesConjunto s) es la lista de las
-- interpretaciones de s. Por ejemplo,
-- interpretacionesConjunto [p --> q, q --> r]
-- ==> [[p,q,r],[p,q],[p,r],[p],[q,r],[q],[r],[]]
-- ---------------------------------------------------------------------

interpretacionesConjunto :: [Prop] -> [Interpretacion]
interpretacionesConjunto s = subconjuntos.simbolosPropConj

-- ---------------------------------------------------------------------
-- Modelos de conjuntos de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 18: Definir la función
-- esModeloConjunto :: Interpretacion -> [Prop] -> Bool
-- tal que (esModeloConjunto i s) se verifica si i es modelo de s. Por
-- ejemplo,
-- esModeloConjunto [p,r] [(p \/ q) /\ ((no q) \/ r), q --> r]
-- ==> True
-- esModeloConjunto [p,r] [(p \/ q) /\ ((no q) \/ r), r --> q]
-- ==> False
-- ---------------------------------------------------------------------

esModeloConjunto :: Interpretacion -> [Prop] -> Bool
esModeloConjunto i s = and [esModeloFormula i f|f<-s]

-- ---------------------------------------------------------------------
-- Ejercicio 19: Definir la función
-- modelosConjunto :: [Prop] -> [Interpretacion]
-- tal que (modelosConjunto s) es la lista de modelos del conjunto
-- s. Por ejemplo,
-- modelosConjunto [(p \/ q) /\ ((no q) \/ r), q --> r]
-- ==> [[p,q,r],[p,r],[p],[q,r]]
-- modelosConjunto [(p \/ q) /\ ((no q) \/ r), r --> q]
-- ==> [[p,q,r],[p],[q,r]]
-- ---------------------------------------------------------------------

modelosConjunto :: [Prop] -> [Interpretacion]
modelosConjunto s = [i|i<-interpretacionesConjunto s, esModeloConjunto i s]

-- ---------------------------------------------------------------------
-- Conjuntos consistentes e inconsistentes de fórmulas --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 20: Definir la función
-- esConsistente :: [Prop] -> Bool
-- tal que (esConsistente s) se verifica si s es consistente. Por
-- ejemplo,
-- esConsistente [(p \/ q) /\ ((no q) \/ r), p --> r]
-- ==> True
-- esConsistente [(p \/ q) /\ ((no q) \/ r), p --> r, no r]
-- ==> False
-- ---------------------------------------------------------------------

esConsistente :: [Prop] -> Bool
esConsistente s = not.null.modelosConjunto

-- ---------------------------------------------------------------------
-- Ejercicio 21: Definir la función
-- esInconsistente :: [Prop] -> Bool
-- tal que (esInconsistente s) se verifica si s es inconsistente. Por
-- ejemplo,
-- esInconsistente [(p \/ q) /\ ((no q) \/ r), p --> r]
-- ==> False
-- esInconsistente [(p \/ q) /\ ((no q) \/ r), p --> r, no r]
-- ==> True
-- ---------------------------------------------------------------------

esInconsistente :: [Prop] -> Bool
esInconsistente s = not.esConsistente

-- ---------------------------------------------------------------------
-- Consecuencia lógica --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 22: Definir la función
-- esConsecuencia :: [Prop] -> Prop -> Bool
-- tal que (esConsecuencia s f) se verifica si f es consecuencia de
-- s. Por ejemplo,
-- esConsecuencia [p --> q, q --> r] (p --> r) ==> True
-- esConsecuencia [p] (p /\ q) ==> False
-- ---------------------------------------------------------------------

esConsecuencia :: [Prop] -> Prop -> Bool
esConsecuencia s f = and[esModeloFormula i f|i<- modelosConjunto s]

</source>

Relación 2

2016-02-23T16:27:25Z

Edupalhid: /* Relación 1(b): Representación del conocimiento proposicional */

=== Relación 1(b): Representación del conocimiento proposicional ===

----
'''Ejercicio 1.''' Formalizar el siguiente argumento
<blockquote>
''Siempre que un número x es divisible por 10, acaba en 0. El número x no acaba en 0. Por lo tanto, x no es divisible por 10.''
</blockquote>
Usando los símbolos D: el número es divisible por 10 y C: el número acaba en cero.
----

'''Solución:'''
<math>D \to C \qquad \lnot C \to \lnot D</math>
----
'''Ejercicio 2.''' Formalizar el siguiente argumento
<blockquote>
''Si la válvula está abierta o la monitorización está preparada, entonces se envía una señal de reconocimiento y un mensaje de funcionamiento al controlador del ordenador. Si se envía un mensaje de funcionamiento al controlador del ordenador o el sistema está en estado normal, entonces se aceptan las órdenes del operador. Por lo tanto, si la válvula está abierta, entonces se aceptan las órdenes del operador.''
</blockquote>
Usando los símbolos V: La válvula está abierta, P: La monitorización está preparada, R: Envía una señal de reconocimiento, F: Envía un mensaje de funcionamiento, A: Se aceptan órdenes del operador y N: El sistema está en estado normal.
----

'''Solución:'''
<math>
(V \vee P \to R \wedge F) \quad
(F \vee N \to A) \quad \vDash V\to A</math>

----
'''Ejercicio 3.''' Formalizar el siguiente argumento
<blockquote>
''Cuando tanto la temperatura como la presión atmosférica permanecen contantes, no llueve. La temperatura permanece constante. Por lo tanto, en caso de que llueva, la presión atmosférica no permanece constante.''
</blockquote>
Usando los símbolos T: La temperatura permanece constante, P: La presión atmosférica permanece constante y L: Llueve
----

'''Solución:'''
<math> (T \wedge P) \to \lnot L </math> 
<math> T \vDash L \to \lnot P </math>

Falta un detalle en la solución

<math> ((T \wedge P) \to \lnot L) \quad T \quad \vDash L \to \lnot P </math>
----
'''Ejercicio 4.''' Formalizar el siguiente argumento
<blockquote>
''En cierto experimento, cuando hemos empleado un fármaco A, el paciente ha mejorado considerablemente en el caso, y sólo en el caso, en que no se haya empleado también un fármaco B. Además, o se ha empleado el fármaco A o se ha empleado el fármaco B. En consecuencia, podemos afirmar que si no hemos empleado el fármaco B, el paciente ha mejorado considerablemente.''
</blockquote>
Usando los símbolos A: Hemos empleado el fármaco A, B: Hemos empleado el fármaco B y M: El paciente ha mejorado notablemente.
----

'''Solución:'''
<math> (A \to (M \leftrightarrow \lnot B)) \wedge (A \vee B) \quad \vDash \lnot B \to M </math>
----
'''Ejercicio 5.''' Definir por recursión sobre fórmulas las siguientes funciones

* nv(F) que calcula el número variables proposicionales que ocurren en la fórmula F. Por ejemplo,
: nv(p → p ∨ q) = 3.
* prof(F) que calcula la profundidad del árbol de análisis de la fórmula F. Por ejemplo,
: prof(p → p ∨ q) = 2.

Demostrar por inducción, que para toda fórmula F,
: nv(F) ≤ 2^prof(F)
----
<math>
nv(F)=
\begin{cases}
1 \quad si \quad F Atomica \\
nv(G) \quad si \quad F= \lnot G \\
nv(G)+nv(H) \quad si \quad F=(G*H)
\end{cases}
</math>

<math>
prof(F)=
\begin{cases}
0 \quad si \quad F Atomica \\
1+prof(G) \quad si \quad F= \lnot G \\
1+ max(prof(G),prof(H)) \quad si \quad F=(G*H)
\end{cases}
</math>

Demostración por inducción: 
Se comprueba para lo que consideramos nuestro caso base, cuando F es atómica 
<math>
F \quad atomica \to nv(F)=1 \leqslant 2^{prof(F)}=2^1
</math> 
Posteriormente suponemos que la desigualdad se da para <math>nv(F) < n+1</math>, y lo comprobamos para <math>nv(F)=n+1</math>: 
<math>nv(F)=n+1 \to F=(G*H) \to n(F)=nv(G)+nv(H) \quad </math> .Pero <math>(nv(G)<n+1) \wedge (nv(H)<n+1) \to nv(F)=nv(G)+nv(H) \leqslant 2^{prof(G)}+2^{prof(H)} \leqslant 2^{prof(F)} </math>

'''Solución:'''

----
'''Ejercicio 6.''' ¿Existe un conjunto S de tres fórmulas tal que de todos los subconjuntos de S sólo uno es consistente?
----

'''Solución:'''
No entiendo bien la pregunta, pero doy una "posible" respuesta: 
Si <math>S=\{ F_1 , F_2,F_3 \}, \quad </math> tendríamos los subconjuntos siguientes <math>\{F_1\},\{F_2\},\{F_3\},\{F_1,F_2\},\{F_1,F_3\},\{F_2,F_3\},S</math> 
Luego, si tomamos <math>F_1 \quad</math> una tautología y <math>F_2,F_3 \quad</math> contradicciones, sólo el subconjunto <math>\{F_1\} \quad</math> sería consistente. 
Por ejemplo: <math>F_1=(p\wedge q)\to (p\vee r), \quad F_2=(p\vee q) \leftrightarrow \lnot (p \vee q), \quad F_3=(p\to q)\wedge \lnot (p \to q)</math>

----
'''Ejercicio 7.''' ¿Es cierto que si F → G y F son satisfacibles, entonces G es satisfacible? Si es cierto, dar una explicación. Si no es cierto, dar un contraejemplo.
----

'''Solución:'''
Dado que <math>F \quad</math> es satisfacible y <math>F\to F</math> también lo es, para cada una de ellas existe una interpretación para la que sean ciertas. Luego, la tabla de verdad de todas las combinaciones posibles (para las que <math>F\to G</math> es cierta) serán: 
<math>
\begin{array}{|c|c||c|} F & G & F\to G \\
\hline
1&1&1\\
0&0&1\\
0&1&1\\
\end{array}
</math>
Por lo tanto, no necesariamente <math>G \quad</math> es satisfacible, pues si es una contradicción, aún existen interpretaciones para las que <math>F\to G \quad </math> es cierta. 
Si <math>F\quad</math> y <math>F\to G \quad</math> deben ser satisfacibles de forma simultánea, entonces sí tendríamos que <math>G \quad</math> es satisfacible.

Como contraejemplo podemos tomar las fórmulas <math>F = \neg p</math> y <math>G = (p \wedge \neg p)</math>. Tenemos que <math>F</math> es satisfacible (<math>I(p)=0</math> es modelo de <math>F</math>) y que <math>F \to G</math> también es satisfacible (<math>I(p)=1</math> es modelo de <math>\neg p \to (p \wedge \neg p)</math>) pero <math>G</math> es insatisfacible.
----
'''Ejercicio 8.''' Demostrar o refutar las siguientes proposiciones:

# Si F es una fórmula satisfacible, entonces todas las subfórmulas de F son satisfacibles.
# Existen fórmulas válidas tales que todas sus subfórmulas son válidas.
----

'''Solución:'''
# Damos un contraejemplo para probar que no se cumple. La fórmula <math>F =\neg (p \wedge \neg p )</math> es una tautología, es decir, toda interpretación es modelo de <math>F</math>. En cambio, su subfórmula <math>G = p \wedge \neg p</math>, por la definición de interpretación (<math>I(F)=H_{\neg}(I(G))</math>) es una contradicción, o sea, que ninguna interpretación es modelo de <math>G</math> y por lo tanto es una subfórmula de <math>F</math> insatisfacible.
# Una fórmula válida es una tautología. Luego queda probado si encontramos algun ejemplo de tautología en la que toda subfórmula sea tautología o refutado si demostramos que no es posible. La considero falsa pues en primer lugar, las fórmulas atómicas son subfórmulas y pueden tomar interpretaciones ciertas o falsas. Y en segundo lugar, las subfórmulas más simples que pueden componer la tautología (que no sean atómicas), están formadas por la combinación de fórmulas atómicas y conectivas lógicas, las cuales no son tautologías (si formamos una fórmula empleando una única conectiva).

Relación 2

2016-02-22T21:40:27Z

Edupalhid: /* Relación 1(b): Representación del conocimiento proposicional */

=== Relación 1(b): Representación del conocimiento proposicional ===

----
'''Ejercicio 1.''' Formalizar el siguiente argumento
<blockquote>
''Siempre que un número x es divisible por 10, acaba en 0. El número x no acaba en 0. Por lo tanto, x no es divisible por 10.''
</blockquote>
Usando los símbolos D: el número es divisible por 10 y C: el número acaba en cero.
----

'''Solución:'''
<math>D \to C \qquad \lnot C \to \lnot D</math>
----
'''Ejercicio 2.''' Formalizar el siguiente argumento
<blockquote>
''Si la válvula está abierta o la monitorización está preparada, entonces se envía una señal de reconocimiento y un mensaje de funcionamiento al controlador del ordenador. Si se envía un mensaje de funcionamiento al controlador del ordenador o el sistema está en estado normal, entonces se aceptan las órdenes del operador. Por lo tanto, si la válvula está abierta, entonces se aceptan las órdenes del operador.''
</blockquote>
Usando los símbolos V: La válvula está abierta, P: La monitorización está preparada, R: Envía una señal de reconocimiento, F: Envía un mensaje de funcionamiento, A: Se aceptan órdenes del operador y N: El sistema está en estado normal.
----

'''Solución:'''
<math>
(V \vee P \to R \wedge F) \quad
(F \vee N \to A) \quad \vDash V\to A</math>

----
'''Ejercicio 3.''' Formalizar el siguiente argumento
<blockquote>
''Cuando tanto la temperatura como la presión atmosférica permanecen contantes, no llueve. La temperatura permanece constante. Por lo tanto, en caso de que llueva, la presión atmosférica no permanece constante.''
</blockquote>
Usando los símbolos T: La temperatura permanece constante, P: La presión atmosférica permanece constante y L: Llueve
----

'''Solución:'''
<math> (T \wedge P) \to \lnot L </math> 
<math> T \vDash L \to \lnot P </math>

Falta un detalle en la solución

<math> ((T \wedge P) \to \lnot L) \quad T \quad \vDash L \to \lnot P </math>
----
'''Ejercicio 4.''' Formalizar el siguiente argumento
<blockquote>
''En cierto experimento, cuando hemos empleado un fármaco A, el paciente ha mejorado considerablemente en el caso, y sólo en el caso, en que no se haya empleado también un fármaco B. Además, o se ha empleado el fármaco A o se ha empleado el fármaco B. En consecuencia, podemos afirmar que si no hemos empleado el fármaco B, el paciente ha mejorado considerablemente.''
</blockquote>
Usando los símbolos A: Hemos empleado el fármaco A, B: Hemos empleado el fármaco B y M: El paciente ha mejorado notablemente.
----

'''Solución:'''
<math> (A \to (M \leftrightarrow \lnot B)) \wedge (A \vee B) \quad \vDash \lnot B \to M </math>
----
'''Ejercicio 5.''' Definir por recursión sobre fórmulas las siguientes funciones

* nv(F) que calcula el número variables proposicionales que ocurren en la fórmula F. Por ejemplo,
: nv(p → p ∨ q) = 3.
* prof(F) que calcula la profundidad del árbol de análisis de la fórmula F. Por ejemplo,
: prof(p → p ∨ q) = 2.

Demostrar por inducción, que para toda fórmula F,
: nv(F) ≤ 2^prof(F)
----
<math>
nv(F)=
\begin{cases}
1 \quad si \quad F Atomica \\
nv(G) \quad si \quad F= \lnot G \\
nv(G)+nv(H) \quad si \quad F=(G*H)
\end{cases}
</math>

<math>
prof(F)=
\begin{cases}
1 \quad si \quad F Atomica \\
prof(G) \quad si \quad F= \lnot G \\
1+ max(prof(G),prof(H)) \quad si \quad F=(G*H)
\end{cases}
</math>

Demostración por inducción: 
Se comprueba para lo que consideramos nuestro caso base, cuando F es atómica 
<math>
F \quad atomica \to nv(F)=1 \leqslant 2^{prof(F)}=2^1
</math> 
Posteriormente suponemos que la desigualdad se da para <math>nv(F) < n+1</math>, y lo comprobamos para <math>nv(F)=n+1</math>: 
<math>nv(F)=n+1 \to F=(G*H) \to n(F)=nv(G)+nv(H) \quad </math> .Pero <math>(nv(G)<n+1) \wedge (nv(H)<n+1) \to nv(F)=nv(G)+nv(H) \leqslant 2^{prof(G)}+2^{prof(H)} \leqslant 2^{prof(F)} </math>

'''Solución:'''

----
'''Ejercicio 6.''' ¿Existe un conjunto S de tres fórmulas tal que de todos los subconjuntos de S sólo uno es consistente?
----

'''Solución:'''
No entiendo bien la pregunta, pero doy una "posible" respuesta: 
Si <math>S=\{ F_1 , F_2,F_3 \}, \quad </math> tendríamos los subconjuntos siguientes <math>\{F_1\},\{F_2\},\{F_3\},\{F_1,F_2\},\{F_1,F_3\},\{F_2,F_3\},S</math> 
Luego, si tomamos <math>F_1 \quad</math> una tautología y <math>F_2,F_3 \quad</math> contradicciones, sólo el subconjunto <math>\{F_1\} \quad</math> sería consistente. 
Por ejemplo: <math>F_1=(p\wedge q)\to (p\vee r), \quad F_2=(p\vee q) \leftrightarrow \lnot (p \vee q), \quad F_3=(p\to q)\wedge \lnot (p \to q)</math>

----
'''Ejercicio 7.''' ¿Es cierto que si F → G y F son satisfacibles, entonces G es satisfacible? Si es cierto, dar una explicación. Si no es cierto, dar un contraejemplo.
----

'''Solución:'''
Dado que <math>F \quad</math> es satisfacible y <math>F\to F</math> también lo es, para cada una de ellas existe una interpretación para la que sean ciertas. Luego, la tabla de verdad de todas las combinaciones posibles (para las que <math>F\to G</math> es cierta) serán: 
<math>
\begin{array}{|c|c||c|} F & G & F\to G \\
\hline
1&1&1\\
0&0&1\\
0&1&1\\
\end{array}
</math>
Por lo tanto, no necesariamente <math>G \quad</math> es satisfacible, pues si es una contradicción, aún existen interpretaciones para las que <math>F\to G \quad </math> es cierta. 
Si <math>F\quad</math> y <math>F\to G \quad</math> deben ser satisfacibles de forma simultánea, entonces sí tendríamos que <math>G \quad</math> es satisfacible.
----
'''Ejercicio 8.''' Demostrar o refutar las siguientes proposiciones:

# Si F es una fórmula satisfacible, entonces todas las subfórmulas de F son satisfacibles.
# Existen fórmulas válidas tales que todas sus subfórmulas son válidas.
----

'''Solución:'''
# Dada una fórmula F, podemos crear un conjunto de fórmulas formadas por aquellos elementos que se obtienen al aplicar la función subfórmula definida en clase. Y hemos demostrado que un conjunto de fórmulas es consistente si cada fórmula que la compone tiene una interpretación para la que es verdadera, es decir, que sea satisfacible. Por lo tanto para que F sea satisfacible, sus subfórmulas deben serlo también.
# Una fórmula válida es una tautología. Luego queda probado si encontramos algun ejemplo de tautología en la que toda subfórmula sea tautología o refutado si demostramos que no es posible. La considero falsa pues en primer lugar, las fórmulas atómicas son subfórmulas y pueden tomar interpretaciones ciertas o falsas. Y en segundo lugar, las subfórmulas más simples que pueden componer la tautología (que no sean atómicas), están formadas por la combinación de fórmulas atómicas y conectivas lógicas, las cuales no son tautologías (si formamos una fórmula empleando una única conectiva).

Relación 2

2016-02-21T11:18:42Z

2016-02-19T14:10:06Z

Edupalhid: /* Relación 1(b): Representación del conocimiento proposicional */