Given are these $3$ propositional formulas:

$\varphi_1 := (A_1 \wedge 0)$

$\varphi_2 := (\neg (A_0 \rightarrow \neg A_1) \rightarrow A_1)$

$\varphi_3 := ((A_o \vee A_1) \rightarrow (A_o \wedge A_1))$

and $\Phi := \left\{\varphi_1, \varphi_2\right\}$

Do we have that $\Phi \vDash \varphi_3$ ?

I think what I need to do is create truth table for each formula and then check if all models of $\varphi_1$ and $\varphi_2$ are included in $\varphi_3$?

Table for $\varphi_1$:

A1   0   (A1∧0)
 0   0      0
 1   0      0

Table for $\varphi_2$:

A0   A1   ¬(A0 → ¬A1)   ¬(A0 → ¬A1) → A1
 0    0         0               1
 0    1         0               1
 1    0         0               1
 1    1         1               1

Table for $\varphi_3$:

A0   A1   A0∨A1   A0∧A1   (A0∨A1)→(A0∧A1)
 0    0     0       0            1
 0    1     1       0            0
 1    0     1       0            0
 1    1     1       1            1

So now we need to check if every model of $\varphi_1$ and $\varphi_2$ is also a model in $\varphi_3$ ? Then $\varphi_2$ is already fine because every combination is true there. $\varphi_1$ is fine too because for $A_1=0$ we have a model in $\varphi_3$ and for $A_1=1$ we have a model as well.

Is it correct like that?

  • 1
    $\begingroup$ What model satisfies $A_1\wedge 0$ ? $\endgroup$ – Graham Kemp Nov 5 '17 at 8:55

Your method is correct, however your conclusion is a bit off.

$\Phi \models \varphi_3 \iff \forall M:M\models \Phi \implies M \models \varphi_3$ with $M\models \Phi \iff (M\models \varphi_1 \land M\models \varphi_1$)

So you basically need to show that every model for $\Phi$ is a model for $\varphi_3$ as well.

Notice that $\varphi_1$ has no models at all, as it always results in false. Therefore $\Phi$ has no model as well. Hence $\Phi \models P$ for every propositional formula $P$. Even $\Phi \models \bot$.

| cite | improve this answer | |
  • $\begingroup$ So this means that we don't have $\Phi \vDash \varphi_3$ because not all models in $\varphi_2$ are in $\varphi_3$, namely the second and third row of truth table $\varphi_2$? $\endgroup$ – cnmesr Nov 5 '17 at 9:49
  • 1
    $\begingroup$ We DO have $\Phi \models \varphi_3$, because "all" models, that evaluate $\varphi_1$ AND $\varphi_2$ to true (there are no such models), also evaluate $\varphi_3$ to true. You're right that not all models of $\varphi_2$ are models $\varphi_3$, which means $\varphi_2 \not\models \varphi_3$. This does not say anything about $\Phi$ tho. In terms of truth tables, you need to search for the assignments of your variables $A_1$ and $A_2$ that satisfy $\varphi_1$ AND $\varphi_2$ and make sure that those assignments also satisfy $\varphi_3$. If that's the case then $\Phi \models \varphi_3$ $\endgroup$ – PattuX Nov 5 '17 at 19:29

$\{\varphi_1, \varphi_2\}\models \varphi_3$ means that in all interpretations* in which statements $\varphi_1$ and $\varphi_2$ are mutually true, then $\varphi_3$ will also be true.

(* that is, basically, the truth assignments for $A_0$ and $A_1$)

So, which interpretation are both statements true?   What does that mean?

| cite | improve this answer | |
  • $\begingroup$ In $\varphi_1$ we don't have any model but in $\varphi_2$, every row of the truth table is a model. Now in order we have $\Phi \vDash \varphi_3$, all the models of $\varphi_2$ must be a model for $\varphi_3$ as well? This isn't the case because second and third row in $\varphi_3$ are false. Thus we don't have that $\Phi \vDash \varphi_3$. Is it correct like that? $\endgroup$ – cnmesr Nov 5 '17 at 9:55
  • $\begingroup$ Hint: Vacuous Truths. @cnmesr Are there any models that make $\varphi_1$ and $\varphi_2$ both true but that make $\varphi_3$ false? $\endgroup$ – Graham Kemp Nov 6 '17 at 8:54

You have $\Phi \vDash \varphi_3$ if and only if the following statement is true:

For all valuations $v$ (a valuation $v$ is an assignment of truth-values to the atomic statements involved ... basically a valuation corresponds to a row in the truth-table):

$$\text{If $v$ sets all statements in $\Phi$ to true, then $v$ sets $\varphi_3$ to true}$$

Well, as you saw, there actually isn't any valuation that sets all statements in $\Phi$ to true (in fact, no valuation will set $\varphi_1$ by itself to true)

Put differently, for any valuation $v$, the statement that $v$ sets all statements in $\Phi$ to true is False. Hence, the 'if' part of the above statement is False, but that means that the whole statement is true. In other words, it is true that for all valuations $v$:

$$\text{If $v$ sets all statements in $\Phi$ to true, then $v$ sets $\varphi_3$ to true}$$

And therefore $\Phi \vDash \varphi_3$

| cite | improve this answer | |

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.