I have a very thin background in logic and I am attempting the first problem in first chapter of the book "Model Theory" by Marker. The problem is reproduced below:

Suppose $\phi_1,\ldots,\phi_n$ are $\mathcal{L}$-formulas and $\psi$ is a Boolean combination of $\phi_1,\ldots,\phi_n$. Then there is $S \subseteq \mathcal{P}(\{1,\ldots,n\})$ such that

$$\models \psi \Leftrightarrow \bigvee_{X \in S} \left(\bigwedge_{i \in X} \phi_i \wedge \bigwedge_{i \notin X} \neg \phi_i \right)$$

My issues are:

  1. I do not understand how to parse what $\mathcal{P}$ is in this context:

$$S \subseteq \mathcal{P}(\{1,\ldots,n\})$$

  1. I do not know how to parse this

$$\models \psi \Leftrightarrow sentence$$

  1. Finally, could someone provide a proof of this problem?

Note, this is not assigned as homework. I am doing this to "catch up" to the rest of the class.

  • 1
    $\begingroup$ $\mathcal P( \{ 1,\ldots,n \})$ is the power-set of $\{ 1,\ldots,n \}$, i.e. the set of all subset of $\{ 1,\ldots,n \}$. Thus, $S \subset \{ 1,\ldots,n \}$ is a a set of subset of ... and $X \in S$ is a subset of ... $\endgroup$ – Mauro ALLEGRANZA Jan 19 '15 at 14:48
  • 1
    $\begingroup$ $\vDash \psi \Leftrightarrow sentence$ means that the two formulae $\psi$ and $sentence$ are logically equivalent. $\endgroup$ – Mauro ALLEGRANZA Jan 19 '15 at 14:49

Basically, we can base a proof of this fact building a truth-table for $\psi$ in terms of the sub-formulae : $\phi_1, \ldots, \phi_n$.

We have to pick-up the rows of the t-t for which $\psi$ is evaluated to $TRUE$ and then write a "long" conjunction with $\phi_i$ : if in that row it has the value $TRUE$, and $\lnot \phi_i$ : if in that row it has the value $FALSE$.

This account for :

$$\left(\bigwedge_{i \in X} \phi_i \wedge \bigwedge_{i \notin X} \neg \phi_i \right).$$

Each row corresponding to $TRUE$ under $\psi$ account for one of the "long" concjunctions above and we have to build a "long" disjunction with all them.

This account for :

$$\bigvee_{X \in S}$$

See Disjunctive normal form.


1) Consider $\psi := \lnot (\phi_1 \rightarrow \lnot \phi_2)$ and build-up the t-t :

\begin{array}{cc|cc|c}\phi_1&\phi_2&\lnot \phi_2&\phi_1 \to \lnot \phi_2&\psi\\\hline T&T&F&F&T\\T&F&T&T&F\\F&T&F&T&F\\F&F&T&T&F\end{array}

You can see that :

$\psi \Leftrightarrow (\phi_1 \land \phi_2)$.

In this trivial case we have : $n=2$ and thus $\mathcal P( \{1,2 \}) = \{ \emptyset, \{ 1 \}, \{ 2 \}, \{ 1, 2 \} \}$.

$X= \{ 1, 2 \}$ is the only element of $S$, because we have only one row of the t-t evaluated to $TRUE$.

Thus, the only "long" concjunction is made with all the sub-formulae which in that row are evaluated to $TRUE$.

2) Consider insted $\psi := \phi_1 \rightarrow \lnot \phi_2$; now we have that $\psi$ is evaluated to $TRUE$ in three rows of the above t-t.

Thus we have :

$\psi \Leftrightarrow [(\phi_1 \land \lnot \phi_2) \lor (\lnot \phi_1 \land \phi_2) \lor (\lnot \phi_1 \land \lnot \phi_2)]$.

In this case we have that $S$ has three elements (we have three $Xs$) : $S = \{ \{ 1 \}, \{ 2 \}, \emptyset \}$.

You can try a slightly more complex case, with a boolean combination of $\phi_1, \phi_2, \phi_3$.

  • $\begingroup$ So is it correct to say that the "sentence" on the RHS is enumerating all possible disjunctive normal forms? Additionally I am a bit unclear about the 2nd paragraph you wrote, is is necessary here that all possible $\psi$'s has to evaluate to TRUE? $\endgroup$ – chibro2 Jan 19 '15 at 15:19
  • $\begingroup$ @chibro2 - $\psi$ is a single formula, built-up from the $\phi_i$. I'll try with an example... $\endgroup$ – Mauro ALLEGRANZA Jan 19 '15 at 15:23
  • $\begingroup$ Oh I apologize, I did not keep in mind that the sentence on the RHS is for one $S \subseteq \mathcal{P}(1,\ldots,n)$. But I am still confused about the necessary "truthiness" of $\psi$. $\endgroup$ – chibro2 Jan 19 '15 at 15:32
  • 1
    $\begingroup$ @chibro2 - please, see the example; we have some rows where $\psi$ is evaluated to $T$, according to the boolean combination and the rules for the connectives. We have to choose only those rows... $\endgroup$ – Mauro ALLEGRANZA Jan 19 '15 at 15:41
  • $\begingroup$ Very nice answer, @Mauro. (+1, of course.) $\endgroup$ – Brian M. Scott Jan 19 '15 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.