Un par de pruebas de deducción natural.

Question

Tengo dos pruebas que yo no puedo averiguar cómo empezar.

a) p ├ (p ∨ p) & q

b) p ∨ q, p→q Ⱶ (p→q)→(q ∧ p)

para q ├ (p ∨ p) y q solo me suponer que yo podría tratar de demostrar indirectamente:

1)q (Asunción)
2)mostrar (p ∨ p) & q
3) mostrar| p ∨ p
4)||(p ∨ p) (Suponga para la Prueba Indirecta)
5)||???

Y en realidad eso es lo más que puedo averiguar cómo llegar. No sé lo que podría hacer con línea de 4 o con q para obtener mucho más...
Mi otra idea era de extracción o en la p ∨ p, pero no veo una manera de mostrar que p→p para hacer ese trabajo...

Para p ∨ q, p→q Ⱶ (p→q)→(q ∧ p) pensé que un buen primer paso sería o extracción de p ∨ q, pero no puede conseguir más allá del primer paso de esa...

1)p ∨ q (Asunción)
2)p→q (Asunción)
3)(p→q)→(q ∧ p)
4) mostrar|p → q
5)||p (Asumir Condicional de la Prueba)
6)||???

Así que sí. Supongo que estoy un poco fuera de mi liga en ambos de estos. Cualquier tipo de ayuda sería de gran ayuda para he estado mirando estos dos problemas por cerca de una hora.

Answer 1

(a) es un estándar poco de "bookwork" para demostrar que, a partir de suposiciones, $(p \lor \neg p)$ y usted debe asegurarse de que usted sabe cómo hacerlo en su favorito de la deducción natural del sistema. He aquí la estrategia.

¿Qué más se puede hacer, pero asumir el opuesto y el objetivo de una contradicción, por lo que se empieza por hacer el temporal de la asunción

$\quad\quad | \quad \neg(p \lor \neg p)$

Ahora, ¿qué puedes hacer? No hay reglas estándar puede ser usado para extraer nada de esto, por lo que tendremos que hacer otra suposición de proceder. pero, ¿qué? Así, con sensatez, no queremos introducir una nueva variable. Por lo tanto, algo que involucran a $p$. Vamos a probar la opción más sencilla (porque tan rápidamente conduce a una contradicción!), así, obtenemos

$\quad\quad | \quad \neg(p \lor \neg p)$

$\quad\quad | \quad\quad | \quad p$

$\quad\quad | \quad\quad | \quad (p \lor \neg p)$

$\quad\quad | \quad\quad | \quad \bot$

donde hemos utilizado o-introducción y golpeado inmediatamente contradicción! Así que ahora podemos utilizar reductio y descarga la suposición. Así, para continuar en la misma línea ...

$\quad\quad | \quad \neg p$

$\quad\quad | \quad (p \lor \neg p)$

$\quad\quad | \quad \bot$

Y he aquí! Nuestra suposición original ha sido reducido al absurdo y podemos descargarla para obtener

$\neg\neg(p \lor \neg p)$

que clásicamente se supone

$(p \lor \neg p)$.

Los ejercicios. Cambiar el estilo de esta prueba en su favorito de la deducción natural del sistema. A continuación, enchufe el resultado a utilizar para completar el ejercicio dado.

(b) La segunda prueba debe escribir a sí mismo si usted piensa estratégicamente. Usted sabe que usted tiene que empezar así:

$ (p \lor q)$

$ (p \to \neg q)$

$\quad \quad | \quad (p \to q)$

Que las dos premisas, y puesto que queremos demostrar a $(p \to q) \to (q \land \neg p)$ utilizamos la táctica estándar para probar la existencia de una obligación de resultado, es decir, asumir el antecedente, y el objetivo es derivar el consecuente, ok? Por lo tanto, hacer el temporal adicional suposición $p \to q$, y el objetivo es demostrar $q \land \neg p$.

Ok, ahora nota que tienen tanto $p \to q$$p \to \neg q$. Ah hah! Eso significa que $p$ conduce a una contradicción y debe ser falsa! Así que .... vamos a usar eso!

$ (p \lor q)$

$ (p \to \neg q)$

$\quad \quad | \quad (p \to q)$

$\quad \quad | \quad\quad | \quad p $

$\quad \quad | \quad\quad | \quad q $

$\quad \quad | \quad\quad | \quad \neg q$

$\quad \quad | \quad\quad | \quad \bot$

$\quad \quad | \quad\neg p $

De modo que la mitad de lo que queremos! Pero ahora tenemos a $\neg p$ $p \lor q$ y que nos da la $q$ por disyuntiva silogismo, que va a ser una regla básica de su deducción natural del sistema, o un poco de bookwork conseguir tus reglas. Usted sólo tiene que seguir, rellenar como sea necesario ...

$\quad \quad | \quad\vdots $

$\quad \quad | \quad q $

$\quad \quad | \quad (q \land \neg p)$

$(p \to q) \to (q \land \neg p)$

donde en la última etapa de la asumimos que la suposición de vuelta en la línea 3 por el condicional de la prueba. Todo hecho!