Es $[p \land (p \to q)] \to q$ una tautología?

Question

Soy nuevo en las matemáticas discretas, y estoy tratando de simplificar esta declaración. Estoy usando una tabla de equivalencias lógicas, pero parece que no puedo encontrar nada que realmente ayude a reducir esto.

¿Cuál de estos me ayudaría a resolver este problema? Me doy cuenta de que puedo encubrir $p \to q$ en $ \lnot p \lor q$ pero estoy atascado después de ese paso. Cualquier empujón en la dirección correcta sería genial.

Answer 1

¿Es una tautología? Sí

¿Por qué? Basta con dibujar la tabla de verdad y ver que el valor de verdad de la implicación principal es siempre 'verdadero'. Aquí, digo que '0' es 'falso' y '1' es verdadero:

╔═══╦═══╦═══════╦═══════════╦═══════════════╗
║ p ║ q ║ p → q ║ p^(p → q) ║ (p^(p→q)) → q ║
╠═══╬═══╬═══════╬═══════════╬═══════════════╣
║ 0 ║ 0 ║ 1     ║ 0         ║ 1             ║
║ 0 ║ 1 ║ 1     ║ 0         ║ 1             ║
║ 1 ║ 0 ║ 0     ║ 0         ║ 1             ║
║ 1 ║ 1 ║ 1     ║ 1         ║ 1             ║
╚═══╩═══╩═══════╩═══════════╩═══════════════╝

Edición: también se puede decir \begin {align}p \land (p \to q) & \equiv p \land ( \lnot p \lor q) \\ & \equiv (p \land \lnot p) \lor (p \land q ) \\ & \equiv \text {falso} \lor (p \land q) \\ & \equiv p \land q, \end {align}

que implica $q $ .

Edición 2: este método de inferencia se llama modus ponens y es la más sencilla.

Por ejemplo, digamos $p = $ llueve, $g = $ Me mojo.

Entonces, si sabemos que la implicación si llueve, me mojo es verdadera (es decir, $p\to q $ ) y Llueve ( $p $ ), ¿qué podemos deducir? Es evidente que Me mojo ( $q $ ).

Tenga en cuenta que, aunque $p \land (p\to q) $ no se verifica, ya que $p\land (p\to q) \to q$ La implicación principal se verifica.

Answer 2

Un enfoque es simplemente empezar a escribir una tabla de verdad - después de todo, sólo hay cuatro casos. Y esto se puede reducir: Si $q$ es verdadera, la afirmación es verdadera (se trata de dos casos). Si $p$ es falsa, la afirmación es verdadera porque

$$p \wedge (p \to q)$$

es falso. El único caso que queda es cuando $p$ es verdadera y $q$ es falsa, y te dejo que verifiques que la proposición es verdadera también en este caso.

Answer 3

\begin {align} (p \land (p \implies q)) \implies q & \equiv \lnot (p \land (p \implies q)) \lor q \\ & \equiv \lnot (p \land ( \lnot p \lor q)) \lor q \\ & \equiv ( \lnot p \lor \lnot ( \lnot p \lor q)) \lor q \\ & \equiv ( \lnot ( \lnot p \lor q) \lor \lnot p) \lor q \\ & \equiv \lnot ( \lnot p \lor q) \lor ( \lnot p \lor q) \\ & \equiv \lnot w \lor w \quad \text {donde}\\Nse trata de una situación en la que se puede ver a la gente en la calle. \equiv ( \lnot p \lor q) \\ & \equiv T \end {align}

Answer 4

Comienza con el enunciado dado,

$$ [p \land (p \rightarrow q)] \rightarrow q.$$

Como has notado, a partir de la primera equivalencia lógica de la Tabla 7 se puede sustituir la parte entre paréntesis para obtener el enunciado equivalente

$$ [p \land (\lnot p \lor q)] \rightarrow q.$$

Por la ley distributiva, esto equivale a:

$$ [(p \land \lnot p) \lor (p \land q)] \rightarrow q.$$

Ley de Negación:

$$ [\mathbf F \lor (p \land q)] \rightarrow q.$$

¿Puede continuar a partir de ahí?

Answer 5

Parece que en sus tablas falta una regla importante, tan importante que tiene un nombre, que es " modus ponens". . Se puede decir que $p \land (p \rightarrow q) \equiv p \land q$ . Se puede derivar de la primera regla de la Tabla 7, y de varias leyes de la Tabla 6:

$$\begin{align} p \land (p \rightarrow q) &\equiv p \land (\neg p \lor q) \\ &\equiv (p \land \neg p) \lor (p \land q) & \textrm{(distribution)}\\ &\equiv p \land q & \textrm{(negation and identity)} \end{align}$$

Así que su declaración inicial se convierte en $$ (p \land q) \rightarrow q$$ que es claramente una tautología, pero se puede demostrar formalmente utilizando la ley de Morgan:

$$\begin{align} (p \land q) \rightarrow q &\equiv \neg (p \land q) \lor q \\ &\equiv \neg p \lor \neg q \lor q & \textrm{(de Morgan and associativity)}\\ &\equiv \neg p \lor T & \textrm{(negation)}\\ &\equiv T & \textrm{(domination)} \end{align}$$