PUERTA | GATE-CS-2016 (Conjunto 2) | Pregunta 11

Considere las siguientes expresiones:
(i) falso
(ii) Q
(iii) verdadero
(iv) P ∨ Q
(v) ¬Q ∨ P
El número de expresiones anteriores que están implícitas lógicamente en P ∧ (P ⇒ Q) es ______________

[Esta pregunta era originalmente una pregunta para completar los espacios en blanco]
(A) 2
(B) 3
(C) 4
(D) 5

Respuesta: (C)
Explicación:  

Esta solución es aportada por .

Explicación alternativa:
la respuesta es 4. Aquí está la solución

Si, por ejemplo, X está ‘implícito lógicamente’ por [ P ∧ (P ⇒ Q) ] entonces
[ P ∧ (P ⇒ Q) ] ⇒ X siempre es cierto, es decir, es una tautología
, por lo que si la expresión anterior es una tautología
entonces podemos decir que X está lógicamente implícito en P ∧ (P ⇒ Q)

Entonces necesitamos encontrar X para el cual [ P ∧ (P ⇒ Q) ] ⇒ X será siempre cierto para todos los valores de P, Q y X.
Mire la siguiente tabla

P....Q...(P ⇒ Q)...[P ∧ (P ⇒ Q)].......X.......[ P ∧ (P ⇒ Q) ] ⇒ X
0....0.....1............0.............1/0............1......
0....1.....1............0.............1/0....  ......1......
1....0.....0..... ......0.............1/0............1......
1....1.....1............1..............1.............1.......

observe que el valor de X no importa si la premisa de la expresión, es decir, la
premisa de [P ∧ (P ⇒ Q)] ⇒ X, es decir, [P ∧ (P ⇒ Q)] es 0,
lo que significa que la expresión final sería una tautología para todos los valores de X si [ P ∧ (P ⇒ Q) ] es 0

pero si la premisa es 1 (como en la última fila), entonces X debe ser 1 para que la implicación final, es decir, [ P ∧ (P ⇒ Q) ] ⇒ X sea verdadera para todos los valores.

si reemplaza X por las 5 opciones, encontrará que
para X = Q, Verdadero, P ∨ Q, ¬Q ∨ P dicha expresión siempre sería verdadera
para X = Falso, la expresión no sería una tautología
Por lo tanto, # de expresión es 4
———————————————————————

Note: 
An important inference rule called "modus ponenes" 
says this [ P ∧ (P ⇒ Q) ] ⇒ Q is a tautology
we noted that if we replace X by Q then it is 
indeed a tautology meaning Q is implied by 
[ P ∧ (P ⇒ Q) ] 

Cuestionario de esta pregunta