1
$\begingroup$

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.

$\endgroup$
2
  • 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$ Jan 19, 2015 at 14:48
  • 1
    $\begingroup$ $\vDash \psi \Leftrightarrow sentence$ means that the two formulae $\psi$ and $sentence$ are logically equivalent. $\endgroup$ Jan 19, 2015 at 14:49

1 Answer 1

4
$\begingroup$

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.


Examples

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$.

$\endgroup$
6
  • $\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, 2015 at 15:19
  • $\begingroup$ @chibro2 - $\psi$ is a single formula, built-up from the $\phi_i$. I'll try with an example... $\endgroup$ Jan 19, 2015 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, 2015 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$ Jan 19, 2015 at 15:41
  • $\begingroup$ Very nice answer, @Mauro. (+1, of course.) $\endgroup$ Jan 19, 2015 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.