Una fórmula $\phi$ es lógicamente equivalente a otra fórmula que sólo contiene variables proposicionales y las conectivas $\wedge$ y $\to$

Question

Dejemos que $v_0$ sea la valoración que asigna verdadero ( $T$ ) a cada variable proposicional.

Estoy tratando de mostrar que cualquier fórmula $\phi$ es lógicamente equivalente a uno con sólo variables proposicionales y las conectivas binarias $\wedge$ y $\to$ si y sólo si la extensión natural de $v_0$ , $v$ digamos, asigna el valor $T$ a $\phi$ .

Si $\phi$ puede ser expresado de tal manera entonces claramente $v(\phi)=T$ de las tablas de verdad de $\wedge$ y $\to$ . Ahora tengo problemas para demostrar lo contrario formalmente. Creo que puedo creer que es verdad mirando diferentes tablas de verdad pero no puedo poner mis pensamientos en orden.

¿Podríais decirme cómo lo haríais vosotros para que pueda entenderlo? Te lo agradecería mucho.

Answer 1

La otra dirección: Supongamos que $v(\phi) = 1$ . Escriba $\phi$ en forma normal conjuntiva, por lo que es una conjunción de cláusulas, cada una de las cuales es una disyunción de variables proposicionales o sus negaciones. Sea $p_1, \dotsc, p_m$ sean todas las variables proposicionales que aparecen en $\phi$ . La fórmula resultante $\phi_{cnf}$ es $$ \phi_{cnf} = \bigwedge_{i=1}^n \bigvee_{j=1}^m a_{ij} $$ donde cada $a_{ij}$ es $p_j$ o $\overline{p_j}$ (la negación de $p_j$ ). Si $m = 1$ entonces cada cláusula es sólo la única variable proposicional o su negación.

Ahora, $\phi \iff \phi_{cnf}$ Así que $v(\phi_{cnf}) = 1$ . Así, $v$ tiene que asignar $1$ a toda disyunción $\bigvee_{j=1}^m a_{ij}$ por lo que en cada cláusula disyuntiva, al menos uno de los $a_{ij}$ debe ser $p_j$ y no $\overline{p_j}$ (por lo demás $v$ asignaría $0$ a esa cláusula y, por tanto, a toda la fórmula). Por tanto, cada disyunción es de la forma $$ \overline{p_{j_1}} \vee \cdots \vee \overline{p_{j_k}} \vee p_{j_{k+1}} \vee \cdots \vee p_{j_m} $$ para alguna permutación $j_1,\dotsc, j_m$ de $1,\dotsc,m$ y algunos $k$ con $0\le k < m$ por lo que cada una de ellas puede escribirse de forma equivalente como $$ (p_{j_1} \wedge \cdots \wedge p_{j_k}) \to (p_{j_{k+1}} \vee \cdots \vee p_{j_m}). $$ Sólo queda demostrar que $\vee$ puede expresarse en términos de $\wedge$ y $\to$ . He aquí cómo: $$ (p\vee q) \iff ((p\to q)\to q). $$