Lógica proposicional

Definición 1.1
Interpretación de una fórmula.

Sea una fórmula $\phi$, una interpretación $I$ es un conjunto de asociaciones de la forma variable=valor, donde valor es T ó F. $I_1 = \{ P=T, Q=F, R=T \}$

También se la representa como el subconjunto de variables que tienen valor T, or ejemplo: $I_2 = \{ P, R \}$

Definición 1.2
Valor de verdad de un fórmula Dada una fórmula $\phi$ y una interpretación $I$, se dice que $\phi$ es verdad bajo la interpretación $I$ si para esos valores de las variables la fórmula se hace verdadera.

Cuando se tiene una tabla de verdad de una fórmula en lógica proposicional, si se busca el renglón de la tabla que corresponde a la combinación de valores de la interpretación, y se mira en el resultado de la fórmula. Si todos los renglones dan un resultado T, entonces la fórmula es verdadera para esa interpretación.

Ejercicio 1.1  

$\phi = ((P \rightarrow Q) \leftrightarrow (\neg Q \rightarrow \neg P))$

1. $I = \{ P, Q \}$
2. $I = \{ P \}$
3. $I = \{ \}$

Planteo la tabla de verdad para la fórmula $\phi$. Comienzo por poner todos los valores posibles para $P$ y para $Q$:

$$\begin{array}{\vert c\vert c\vert}\hline P & Q \\ \hline F & F \\ F & V \\ V & F \\ V & V \\ \hline \end{array}$$

Como vemos en $\phi$ que se usan las negaciones de $P$ y de $Q$, planteamos también las negaciones:

$$\begin{array}{\vert c\vert c\vert c\vert c\vert}\hline P & ... ...& F \\ V & F & F & V \\ V & V & F & F \\ \hline \end{array}$$

Para hacer más fáciles los cálculos, ponemos como columnas adicionales los resultados intermedios, en este caso $(P \rightarrow Q)$ y $(\neg P \rightarrow \neg Q)$:

$$\begin{array}{\vert c\vert c\vert c\vert c\vert c\vert c\ver... ... F & V & F & F \\ V & V & F & F & V & V \\ \hline \end{array}$$

Y ahora sólo nos queda calcular la columna de la fórmula $\phi$ completa:

$$\begin{array}{\vert c\vert c\vert c\vert c\vert c\vert c\ver... ... & F & F & V\\ V & V & F & F & V & V & V\\ \hline \end{array}$$

Ahora, para cada interpretación, que es un renglón en la tabla, me fijo si la columna de $\phi$ tiene T, entonces $\phi$ bajo la $I$ es verdadera. En caso contrario, se dice que es falsa.

En nuestro ejercicio, la columna de $\phi$ es verdadera para toda interpretación.

Definición 1.3
Interpretación que satisface una fórmula Dada una fórmula $\phi$ y una interpretación $I$, se dice que $I$ satisface a $\phi$ si el valor de verdad de $\phi$ bajo la interpretación $I$ es verdadero.

Definición 1.4
Interpretación que es modelo de una fórmula Sea una fórmula $\phi$ y una interpretación $I$. Se dice que $I$ es modelo de $\phi$ si $I$ satisface a $\phi$.

Definición 1.5
Interpretación que es modelo de un conjunto de fórmulas Sea un conjunto de fórmulas $\Sigma$, y una interpretación $I$. $I$ es modelo de $\Sigma$ si es modelo de todas las fórmulas de $\Sigma$.

Ejercicio 1.2   $\Sigma = \{ \underbrace{\neg P \rightarrow (Q \wedge R)}_{\phi_1}, \underbrace{(Q \wedge R)}_{\phi_2}, \underbrace{(P \vee Q \vee R)}_{\phi_3} \}$

1. $I = \{ P \}$
2. $I = \{ P, Q \}$
3. $I = \{ \}$

Ahora solamente construiremos los renglones que corresponden a las interpretaciones que solicita el ejercicio.

$$\begin{array}{\vert c\vert c\vert c\vert c\vert c\vert c\vert c\v... ...\\ V & V & F & F & F & V & V\\ F & F & F & V & F & F & F\\ \hline \end{array}$$

Entonces por ejemplo $I_1$ satisface $\phi_1$ y $\phi_3$, pero no $\phi_2$. Ninguna de las interpretaciones satisface todas las fórmulas del conjunto, y por lo tanto no son modelos del conjunto.

Definición 1.6
Consecuencia lógica Sea $\Sigma$ un conjunto de fórmulas, $\phi$ una fórmula.

$\Sigma \models \phi$, $\phi$ es consecuencia lógica de $\Sigma$ si todo modelo de $\Sigma$ es modelo de $\phi$.

Ejercicio 1.3  

1. $P \models P \vee Q$
   $$\begin{array}{\vert cc\vert c\vert}\hline P & Q & P \vee Q \\ \hline F & F & F \\ F & V & V \\ V & F & V \\ V & V & V \\ \hline \end{array}$$

   Aplicando la definición, todos los modelos de $\Sigma$ deben ser modelos de $\phi$. En nuestro caso $\Sigma = P$ y $\phi = P \vee Q$. Entonecs buscamos que para cada V en un renglón de $P$ , en ese mismo renglón en $P \vee Q$ también tenemos que encontrar un V. Esto es así en los dos últimos renglones de la tabla. Concluimos que es cierto que $P \vee Q$ es consecuencia lógica de $P$.

2. $P \vee Q \models P$

   Construimos la tabla completa para este caso, en el cual $\Sigma = P \vee Q$ y $\phi = P$:

   $$\begin{array}{\vert cc\vert c\vert}\hline P & Q & P \vee Q \\ \hline F & F & F \\ F & V & V \\ V & F & V \\ V & V & V \\ \hline \end{array}$$

   Los modelos de $\Sigma$ son los tres últimos renglones (ver columna $P \vee Q$). Ahora debemos buscar en la columna de $P$ para esos tres renglones. En el segundo renglón (que es un modelo de $P \vee Q$) nos encontramos que hay una F para $P$, con lo cual no es modelo de $P$. Concluimos que $P$ no es consecuencia lógica de $P \vee Q$).

Hosted by www.Geocities.ws