Lógica matemática y fundamentos (2017-18) - Contribuciones del usuario [es]

Relación 5

2018-04-15T08:33:32Z

Manberdel1:

=== Relación 5: Sintaxis y semántica de la Lógica de primer orden ===

----
'''Ejercicio 1.''' Formalizar el siguiente argumento (ejercicio 5 de LPO de
APPLI2), verificando la corrección de la solución:

* Todo aquel que entre en el país y no sea un VIP será cacheado por un aduanero.
* Hay un contrabandista que entra en el país y que solo podrá ser cacheado por contrabandistas.
* Ningún contrabandista es un VIP.
* Por lo tanto, algún aduanero es contrabandista.
----

'''Solución:'''

joslopjim4

*all x ( ( entra(x) & ( -vip(x) ) ) -> ( exists y (aduanero(y) & cachea(y,x) ) ) )
* exists x (contrabandista(x) & entra(x) & ( all y (cachea(y,x) & contrabandista(y))))
* all x (contrabandista(x) -> (- vip(x)))
*exists x (aduanero(x) & contrabandista(x))

manberdel1

* all x ((entra(x) & (-vip(x))) -> (exists y (aduanero(y) & cachea(y,x))))
* exists x (contrabandista(x) & entra(x) & (all y (cachea(y,x) -> contrabandista(y))))
* all x (contrabandista(x) -> -vip(x))
* exists x (aduanero(x) & contrabandista(x))
----
'''Ejercicio 2.''' Formalizar el siguiente argumento (ejercicio 15 de LPO de
APPLI2), verificando la corrección de la solución:

* Todos los robots obedecen a los amigos del programador jefe.
* Alvaro es amigo del programador jefe.
* Benito no obedece a Alvaro.
* Benito no es un robot.

----

'''Solución:'''

joslopjim4,manberdel1

*all x all y ((robot(x) & amigo(y)) -> obedece(x,y))
*amigo(Alvaro)
*-obedece(Benito,Alvaro)
*-robot(Benito)

----
'''Ejercicio 3.''' Formalizar el siguiente argumento (ejercicio 16 de LPO de
APPLI2), verificando la corrección de la solución:

* Hay algún pez x que para cualquier pez y, si el pez x no se come al pez y entonces existe un pez z tal que z es un tiburón o bien z protege al pez y.
* No hay ningún pez que se coma a todos los demás.
* Ningún pez protege a ningún otro.
* Por lo tanto, existe algún tiburón en la pecera.

----

'''Solución:'''

joslopjim4

*exists x ( all y ( -C(x,y) -> ( exists z ( T(z) | P(z,y) ) ) ) )
*all x (all y (-C( x , y ) ) )
*all x (all y (-P( x , y ) ) )
*exists x ( T(x))

manberdel1

* exists x (all y (-C(x,y) -> (exists z (T(z) | P(z,y)))))
* all x (exists y (-C(x,y)))
* all x all y (-P(x,y))
* exists x (T(x))

----
'''Ejercicio 4.''' Formalizar el siguiente argumento (ejercicio 21 de LPO de APPLI2), verificando la corrección de la solución:

* Carlos afeita a todos los habitantes de Las Chinas que no se afeitan a sí mismo y sólo a ellos.
* Carlos es un habitante de las Chinas.
* Por lo tanto, Carlos no afeita a nadie.

----

'''Solución:'''

joslopjim4,manberdel1

*all x ( chino(x) & ( -afeita(x,x) ) <-> afeita(Carlos,x) )
*chino(Carlos)
*all y ( -afeita(Carlos,y))

----
'''Ejercicio 5.'''
Sea F la fórmula P(x) → P (a) , donde a es un símbolo de constante. Dar un
ejemplo de una interpretación en la que F sea verdadera. Y un ejemplo de una
interpretación en la que F sea falsa.

----

'''Solución:'''

joslopjim4

*Verdadera

U={1}
I(P)={1}
I(a)=1

*Falsa

U={1,2}
I(P)={1}
I(a)=2

----
'''Ejercicio 6.'''
Sea L un lenguaje de primer orden con dos símbolos de predicado, P (de aridad
1), Q (de aridad 2) y un símbolo de función, f , de aridad 1. Sea I = ( U, I )
la estructura dada por:
U = { a, b, c, d } ;
I ( P ) = { a, b } ,
I ( Q ) = {( a, b ) , ( b, b ) , ( c, b )} ,
I ( f ) = {( a, b ) , ( b, b ) , ( c, a ) , ( d, c )} .
¿Cuál es el valor de cada una de las siguientes fórmulas en dicha estructura?
* P ( x ) → ∃ yQ ( y, x ) .
*. ∀ xQ ( f ( x ) , x ) .
* Q ( f ( x ) , x ) → Q ( x, x ) .
* Q ( x, y ) → P ( x ) .
----

'''Solución:'''

joslopjim4

*
A1(x)=a -> I(F)=0
A2(x)=b -> I(F)=1
A3(x)=c -> I(F)=1
A4(x)=d -> I(F)=1

*
I(F)=0 si x=a

*
A1(x)=a -> I(F)=1
A2(x)=b -> I(F)=1
A3(x)=c -> I(F)=1
A4(x)=d -> I(F)=1

*
A1(x)=a, A1(y)=a -> I(F)=1
A1(x)=a, A2(y)=b -> I(F)=1
A1(x)=a, A3(y)=c -> I(F)=1
A1(x)=a, A4(y)=d -> I(F)=1

A2(x)=b, A1(y)=a -> I(F)=1
A2(x)=b, A2(y)=b -> I(F)=1
A2(x)=b, A3(y)=c -> I(F)=1
A2(x)=b, A4(y)=d -> I(F)=1

A3(x)=c, A1(y)=a -> I(F)=1
A3(x)=c, A2(y)=b -> I(F)=0
A3(x)=c, A3(y)=c -> I(F)=1
A3(x)=c, A4(y)=d -> I(F)=1

A4(x)=d, A1(y)=a -> I(F)=1
A4(x)=d, A2(y)=b -> I(F)=1
A4(x)=d, A3(y)=c -> I(F)=1
A4(x)=d, A4(y)=d -> I(F)=1

----
'''Ejercicio 7.'''

En el lenguaje con igualdad L = { a, f } , siendo f un símbolo de función
de aridad 1 y a una constante, se consideran las siguientes fórmulas:
* F₁ : = ∀ x [ f ( x ) ≠ a ] ,
* F₂ : = ∀ x ∀ y [ f ( x ) = f ( y ) → x = y ] ,
* F₃ : = ∀ x [ x ≠ a → ∃ y [ f ( y ) = x ]] .

Probar que ninguna de estas fórmulas es consecuencia lógica de las dos restantes.
----

'''Solución:'''

joslopjim4

* Caso 1: F3 no consecuencia lógica de F1 y F2

U=naturales
I(a)=0
I(f)=x+2

----
'''Ejercicio 8.''' Dar una fórmula F, tal que todo modelo de F tenga al menos 3 elementos. Generalizarlo a n cualquiera.

----

'''Solución:'''

joslopjim4

exists x exists y exists z (x≠y & x≠z & y≠z)

Para un n cualquiera, se ponen n exists con n variable diferentes y luego se hacen sus distinciones mediante una combinación sin repetición de n elementos cogidos de dos en dos

Relación 5

2018-04-14T19:24:03Z

Manberdel1:

=== Relación 5: Sintaxis y semántica de la Lógica de primer orden ===

----
'''Ejercicio 1.''' Formalizar el siguiente argumento (ejercicio 5 de LPO de
APPLI2), verificando la corrección de la solución:

* Todo aquel que entre en el país y no sea un VIP será cacheado por un aduanero.
* Hay un contrabandista que entra en el país y que solo podrá ser cacheado por contrabandistas.
* Ningún contrabandista es un VIP.
* Por lo tanto, algún aduanero es contrabandista.
----

'''Solución:'''

joslopjim4

*all x ( ( entra(x) & ( -vip(x) ) ) -> ( exists y (aduanero(y) & cachea(y,x) ) ) )
* exists x (contrabandista(x) & entra(x) & ( all y (cachea(y,x) & contrabandista(y))))
* all x (contrabandista(x) -> (- vip(x)))
*exists x (aduanero(x) & contrabandista(x))

manberdel1

* all x ((entra(x) & (-vip(x))) -> (exists y (aduanero(y) & cachea(y,x))))
* exists x (contrabandista(x) & entra(x) & (all y (cachea(y,x) -> contrabandista(y))))
* all x (contrabandista(x) -> -vip(x))
* exists x (aduanero(x) & contrabandista(x))
----
'''Ejercicio 2.''' Formalizar el siguiente argumento (ejercicio 15 de LPO de
APPLI2), verificando la corrección de la solución:

* Todos los robots obedecen a los amigos del programador jefe.
* Alvaro es amigo del programador jefe.
* Benito no obedece a Alvaro.
* Benito no es un robot.

----

'''Solución:'''

joslopjim4,manberdel1

*all x all y ((robot(x) & amigo(y)) -> obedece(x,y))
*amigo(Alvaro)
*-obedece(Benito,Alvaro)
*-robot(Benito)

----
'''Ejercicio 3.''' Formalizar el siguiente argumento (ejercicio 16 de LPO de
APPLI2), verificando la corrección de la solución:

* Hay algún pez x que para cualquier pez y, si el pez x no se come al pez y entonces existe un pez z tal que z es un tiburón o bien z protege al pez y.
* No hay ningún pez que se coma a todos los demás.
* Ningún pez protege a ningún otro.
* Por lo tanto, existe algún tiburón en la pecera.

----

'''Solución:'''

joslopjim4

*exists x ( all y ( -C(x,y) -> ( exists z ( T(z) | P(z,y) ) ) ) )
*all x (all y (-C( x , y ) ) )
*all x (all y (-P( x , y ) ) )
*exists x ( T(x))

manberdel1

* exists x (all y (-C(x,y) -> (exists z (T(z) | P(z,y)))))
* all x (exists y (-C(x,y)))
* all x all y (-P(x,y))
* exists x (T(x))

----
'''Ejercicio 4.''' Formalizar el siguiente argumento (ejercicio 21 de LPO de APPLI2), verificando la corrección de la solución:

* Carlos afeita a todos los habitantes de Las Chinas que no se afeitan a sí mismo y sólo a ellos.
* Carlos es un habitante de las Chinas.
* Por lo tanto, Carlos no afeita a nadie.

----

'''Solución:'''

joslopjim4,mannberdel1

*all x ( chino(x) & ( -afeita(x,x) ) <-> afeita(Carlos,x) )
*chino(Carlos)
*all y ( -afeita(Carlos,y))

----
'''Ejercicio 5.'''
Sea F la fórmula P(x) → P (a) , donde a es un símbolo de constante. Dar un
ejemplo de una interpretación en la que F sea verdadera. Y un ejemplo de una
interpretación en la que F sea falsa.

----

'''Solución:'''

joslopjim4

*Verdadera

U={1}
I(P)={1}
I(a)=1

*Falsa

U={1,2}
I(P)={1}
I(a)=2

----
'''Ejercicio 6.'''
Sea L un lenguaje de primer orden con dos símbolos de predicado, P (de aridad
1), Q (de aridad 2) y un símbolo de función, f , de aridad 1. Sea I = ( U, I )
la estructura dada por:
U = { a, b, c, d } ;
I ( P ) = { a, b } ,
I ( Q ) = {( a, b ) , ( b, b ) , ( c, b )} ,
I ( f ) = {( a, b ) , ( b, b ) , ( c, a ) , ( d, c )} .
¿Cuál es el valor de cada una de las siguientes fórmulas en dicha estructura?
* P ( x ) → ∃ yQ ( y, x ) .
*. ∀ xQ ( f ( x ) , x ) .
* Q ( f ( x ) , x ) → Q ( x, x ) .
* Q ( x, y ) → P ( x ) .
----

'''Solución:'''

joslopjim4

*
A1(x)=a -> I(F)=0
A2(x)=b -> I(F)=1
A3(x)=c -> I(F)=1
A4(x)=d -> I(F)=1

*
I(F)=0 si x=a

*
A1(x)=a -> I(F)=1
A2(x)=b -> I(F)=1
A3(x)=c -> I(F)=1
A4(x)=d -> I(F)=1

*
A1(x)=a, A1(y)=a -> I(F)=1
A1(x)=a, A2(y)=b -> I(F)=1
A1(x)=a, A3(y)=c -> I(F)=1
A1(x)=a, A4(y)=d -> I(F)=1

A2(x)=b, A1(y)=a -> I(F)=1
A2(x)=b, A2(y)=b -> I(F)=1
A2(x)=b, A3(y)=c -> I(F)=1
A2(x)=b, A4(y)=d -> I(F)=1

A3(x)=c, A1(y)=a -> I(F)=1
A3(x)=c, A2(y)=b -> I(F)=0
A3(x)=c, A3(y)=c -> I(F)=1
A3(x)=c, A4(y)=d -> I(F)=1

A4(x)=d, A1(y)=a -> I(F)=1
A4(x)=d, A2(y)=b -> I(F)=1
A4(x)=d, A3(y)=c -> I(F)=1
A4(x)=d, A4(y)=d -> I(F)=1

----
'''Ejercicio 7.'''

En el lenguaje con igualdad L = { a, f } , siendo f un símbolo de función
de aridad 1 y a una constante, se consideran las siguientes fórmulas:
* F₁ : = ∀ x [ f ( x ) ≠ a ] ,
* F₂ : = ∀ x ∀ y [ f ( x ) = f ( y ) → x = y ] ,
* F₃ : = ∀ x [ x ≠ a → ∃ y [ f ( y ) = x ]] .

Probar que ninguna de estas fórmulas es consecuencia lógica de las dos restantes.
----

'''Solución:'''

joslopjim4

* Caso 1: F3 no consecuencia lógica de F1 y F2

U=naturales
I(a)=0
I(f)=x+2

----
'''Ejercicio 8.''' Dar una fórmula F, tal que todo modelo de F tenga al menos 3 elementos. Generalizarlo a n cualquiera.

----

'''Solución:'''

joslopjim4

exists x exists y exists z (x≠y & x≠z & y≠z)

Para un n cualquiera, se ponen n exists con n variable diferentes y luego se hacen sus distinciones mediante una combinación sin repetición de n elementos cogidos de dos en dos

Relación 1

2018-02-18T12:28:50Z

Manberdel1:

=== Relación 1: Sintaxis y semántica de la lógica 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:'''
josrodjim2, jescammor1, inmbenber,josgarfer12,antnavcue,sarolizap,manberdel1

D -> C. ¬C |= ¬D

----
'''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:'''
josrodjim2, jescammor1,josgarfer12,antnavcue,sarolizap,manberdel1

(V v P) -> (R ∧ F). (F v N) -> A. V |= A

inmbenber

(V v P) -> (R v F), (F v N) -> A |= (V -> A)
----
'''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:'''
josrodjim2, jescammor1, inmbenber,,josgarfer12,antnavcue,sarolizap,manberdel1

(T ∧ P) -> ¬L. T |= (L -> ¬P)
----
'''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:'''
josrodjim2,sarolizap

(A ∧ ¬B) -> M. A v B. ¬B |= M

jescammor1

(A ∧ ¬B) -> M, (A v B) |= (¬B -> M)

inmbenber,manberdel1

A -> (M <-> ¬B), A v B |= (¬B -> M)

josgarfer12
(A ∧ ¬B) <-> M, A v B-> ¬B|=M

antnavcue

A -> (M <-> ¬B) , A v B-> ¬B|=M
----
'''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)
----

'''Solución:'''
josrodjim2, jescammor1, inmbenber,sarolizap

*nv(F)= 1 si F atomica, nv(G) si F es ¬G, nv(G)+nv(H) si F es (G*H)

* prof(F)= 0 si F atomica, 1+prof(G) si F es ¬G, 1+max{prof(G),prof(H)} si F es (G*H)

* Caso base: F atomica. 1 = nv(F) <= 2^prof(F) = 2^0 = 1. Se cumple.

* Supongo que se cumple para F y G.

nv(¬F) = nv(F) <= 2^prof(F) <= 2^(1+prof(F)) = 2^prof(¬F)

nv(F*G) = nv(F) + nv(G) <= 2^prof(F) + 2^prof(G) <= 2^(1 + max{prof(F),prof(G)}) = 2^prof(F*G)

----
'''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:'''
josrodjim2, jescammor1

Sea S = { F1= ¬(P v ¬P), F2= P ∧ ¬P, F3= P}

F3 es sastifacible I(P) = 1.

Pero cualquiera de sus subformulas incluida ella misma, son inconsistente por construccion o usando el ejercicio 9 apartado primero.

inmbenber

Sí, basta tomar S un conjunto que tenga una fórmula satisfacible y las otras insatisfacibles, así solo el subconjunto formado por la fórmula satisfacible es consistente. Pongamos un ejemplo:

S = {F,G,H} donde F = p <-> q, G = p ^ ¬p, H = (p <-> q)^(p -> ¬q)^p. Se comprueba que F es satisfacible (un modelo es I(p)=I(q)=1) y que G y H son insatisfacibles. Se ve que de todos los subconjuntos posibles de S, el único que es consistente es S1={F}

----
'''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:'''
josrodjim2, jescammor1

Si F -> G es satisfacible y F es satisfacible para el mismo modelo, entonces existe I(¬F v G) = 1, I(F)=1.

Que I(¬F v G) = 1 implica que I(¬F) = 0 o bien I(G)=1, como ya tenemos I(F) = 1. La unica posibilidad es que I(G) = 1. Por lo tanto G es satisfacible.

inmbenber

G no es necesariamente satisfacible, ya que si es una contradicción (falsa en todas sus interpretaciones), existen interpretaciones para las que F->G es cierta (cuando I(F)=0). Por ejemplo, F = ¬p y G = p ^ ¬p. Al hacer su tabla de verdad, notamos que F y F->G son satisfacibles, en cambio, G es insatisfacible (es una contradicción).

Si F y F->G son safistacibles a la vez, es decir, existe una interpretación I tal que I(F)=I(F->G)=1, entonces sí tendríamos que G es satisfacible, ya que sabiendo que I(F)=I(F->G)=1, la única opción que tenemos es que I(G)=1.

----
'''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:'''

javdelcru, jescammor1

* 1) Falso. (p -> ¬p) -> p es satisfacible, pero la subformula p -> ¬p no lo es
* 2) Falso. Todas las formulas tienen al menos una subformula que es atómica y no es válida ya que puede ser falsa.

josrodjim2, inmbenber

* 1) Falso. (P ∧ ¬P) es insatisfacible, cual es una subformula de la tautologia ¬(P ∧ ¬P).

----
'''Ejercicio 9.'''
Sean S y T conjuntos de fórmulas. Demostrar o refutar las siguientes
afirmaciones:
* Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
* Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
* Si S es consistente y T es inconsistente, entonces S ∪ T es inconsistente.
* Si S es consistente y T es inconsistente, entonces S ∩ T es consistente.
----

'''Solución:'''
josrodjim2, inmbenber

* 1. Por reducción al absurdo, supongamos que S v T es consistente.
Significa que existe I modelo para todas sus fórmulas, pero el subconjunto de formulas T es inconsistente, por lo que no tiene modelo. Contradcción.

* 2. S ∩ T puede ser vacío cual es consistente.
S ∩ T si no es vacío es S o un subconjunto suyo el cual es consistente por hipótesis.

inmbenber

* 1. Sean S={F1, F2,..., Fn} consistente y T={G1, G2,..., Gm} inconsistente. Por ser S consistente, existe I modelo de S, entonces I(F1^F2^...^Fn)=1. Como T es inconsistente, entonces no tiene ningún modelo, es decir, I(G1^G2^...^Gm)=0 para cualquier interpretación I. Se tiene entonces que (F1^...^Fn^G1^...^Gm)=(F1^...^Fn)^(G1^...^Gm). Por tanto no existe modelo para (F1^...^Fn)^(G1^...^Gm). Lo que implica que S ∪ T es inconsistente.

----
'''Ejercicio 10.'''
Da un ejemplo de tres fórmulas F₁ , F₂ , y F₃ tales que F₁ ∧ F₂ ∧ F₃ sea
insatisfactible y donde cualquier conjunción de todas ellas menos una sea
satisfactible. Generalízalo a n fórmulas.
----

'''Solución:'''

javdelcru, josrodjim2, jescammor1

F_1 = p; F_2 = q; F_3 = ¬(p ∧ q)
F_1 ∧ F_2 ∧ F_3 es insatisfacible pero dos a dos si son satisfacible.

Generalizamos a n formulas
F_1 = p_1, F_2=p_2 ... F_(n-1) = p_(n-1), F_n = ¬(p_1 ∧ p_2 ∧ .... ∧ p_(n-1))
Igual que en el caso de 3 formulas, la conjunción de todas en insatisfacible ya que F_n es verdadera solo si las anteriores son falsas y las conjunciones de todas menos una (k) son satisfacibles con la interpretación I(p_t)= 1 para todos los t distintos de k y I(p_k) = 0.

inmbenber

<math>F_{1}</math> = ¬p, <math>F_{2}</math> = ¬q, <math>F_{3}</math> = p v q

Generalizamos a n formulas:
<math>F_{1}</math> = ¬<math>p_{1}</math>, <math>F_{2}</math> = ¬<math>p_{2}</math>,..., <math>F_{n-1}</math> = ¬<math>p_{n-1}</math>, <math>F_{n}</math> = <math>p_{1}</math> v <math>p_{2}</math> v ... v <math>p_{n-1}</math>

----
'''Ejercicio 11.'''
* Probar que la fórmula (((p → q) → p) → p) es una tautología
* Si definimos recursivamente A(0) = (p → q) y A(n+1) = (A(n) → p), ¿para qué valores de n es A es una tautología?
----

'''Solución:'''
josrodjim2

* 1. Se puede escribir la formula como ¬(¬(¬P v Q) v P) v P

Aplico tabla de verdad

Para I(P)=1 y I(Q) cualquiera, se ve que siempre es verdad.

Veamos los demas casos.

I(P)=0,I(Q)=0 se tiene ¬(¬(1 v 0)) v 0 ----> ¬(¬1) v 0 ---->1 v 0 ---->1 es verdad

I(P)=0,I(Q)=1 se tiene ¬(¬(1 v 1)) v 0 ----> ¬(¬1) v 0 ---->1 v 0 ---->1 es verdad

Entonces la formula es tautologia.

* 2. Para n >= 2 A(n)=p, teniendose ¬P v P cual es tautologia.

jescammor1

* 2. Estudiando los casos básicos podemos generalizar fácilmente. Como ya se ha dicho si I(P)=1 siempre es válida de n=1 en adelante así que nos ocupamos del caso I(P)=0. En A(1) esta interpretación nos da 1->0 independientemente del valor de Q (es decir, no es tautología). Por otro lado, A(2) nos da 0->1 en la misma interpretación, lo que nos da la tautología.

Está claro que si seguimos el proceso tenemos que A(3) no es tautología (1->0), A(4) si (0->1),... Luego es tautología para los n pares.

inmbenber

* 1. Haciendo su tabla de verdad tenemos que (((p → q) → p) → p) es una tautología, ya que para cualquier interpretación se tiene que I(F) = 1 con F = (((p → q) → p) → p)
* 2. A partir de su tabla de verdad, es fácil comprobar que es tautología para n par