Supongamos que $n$ es un número entero positivo y $X_n = \{(x_1,\ldots ,x_n) \colon x_i ∈ \{T,F\}\}$ es el conjunto de $n$ - tuplas de $\{T,F\}$ . Supongamos que $f\colon X_n \to \{T,F\}$ es una función y $f(x) = T$ para algunos $x \in X_n$ . Al considerar $\{x \in X_n \colon f(x) = T\}$ , demuestre que existen fórmulas proposicionales $\psi_1,\ldots ,\psi_r$ en variables $p_1, \ldots , p_n$ tal que:
(i) cada $\psi_i$ es de la forma ${{q_i}_1} \land \ldots \land{{q_i}_n}$ donde ${{q_i}_j}$ es $p_j$ o $(¬p_j)$ ;
(ii) la función de verdad de la fórmula $\phi$ dado por $\psi_1\lor \ldots \lor\psi_r$ es $f$ .
Esta es una pregunta que aparece en muchos exámenes anteriores del módulo de Lógica que estoy cursando. Creo que podría estar pidiendo una prueba de las notas, pero no estoy seguro de cómo utilizar la prueba para responder a las 2 partes individuales de esta pregunta y si es realmente lo que la pregunta está pidiendo, ya que no estoy seguro de que el teorema se trata de la misma cosa que la Q. Sentí que la pregunta está pidiendo, como, la prueba de la forma normal disyuntiva?
Teorema 1.5.1
Para cualquier función $f\colon X_n \rightarrow \{T,F\}$ existe una fórmula $\phi$ cuya función de verdad viene dada por $f$ . La fórmula $\phi$ puede tomarse para usar conectivos en $\{\lor,\land,\neg\}$ .
Y tengo la siguiente prueba:
Si $f$ siempre tiene valor $F$ entonces deja que $\phi$ sea la fórmula $(p_1)∧(¬p_1))$ . De lo contrario, deja que $v_1, v_2, \ldots ,v_n \in X_n$ sean los lugares, es decir, las filas de la tabla de verdad, donde $f$ toma el valor $T$ . Así que cada $v_i=({{v_i}_1}, {{v_i}_2}, \ldots,{{v_i}_n})$ donde ${{v_i}_j}\in \{T,F\}$ .
Dejemos que $p_1,p_2, \ldots ,p_n$ sean variables proposicionales y que ${{q_i}_j}=\begin{cases} p_j, &\text{if }{{v_i}_j}=T\\ ¬p_j, &\text{if }{{v_i}_j}=F\end{cases}$ .
Dejemos que $\psi_i={{q_i}_1}\land {{q_i}_2}\land \ldots \land{{q_i}_n}$ entonces $\psi_i$ tiene valor $T$ si y sólo si $p_1$ tiene valor ${{v_i}_1},\, p_2$ tiene valor ${{v_i}_2}\ldots $ y $p_n$ tiene valor ${{v_i}_n}$ . Sea $\phi$ sea $\psi_1\lor \psi_2\lor \ldots \lor \psi_r$ Entonces, para cualquier asignación $\omega$ de valores de verdad tenemos que $\omega(\phi)=T$ si y sólo si $\omega(\psi_i)=T$ para algunos $\psi_i$ si y sólo si $\omega$ da $p_1,p_2,\ldots ,p_n$ valores como en $v_i$ para algunos $i$ mayor o igual que $r$ . Por lo tanto, la función de verdad de $\phi$ es exactamente $f$ .
Casi sigo la prueba pero no estoy seguro de cómo dividirla para responder correctamente a las 2 preguntas de los exámenes anteriores. ¿La primera parte (i) podría terminar en "Let $p_1,p_2,…,p_n$ sean variables proposicionales y que ${{q_i}_j}$ = { $p_j$ si ${{v_i}_j}$ =T o $¬p_j$ si ${{v_i}_j}$ =F}" y la parte (ii) comienza después de esto? No estoy seguro de cómo eso lo ha "demostrado" en lugar de limitarse a decir que es cierto.
Gracias
