1

Prove/Disprove: $A, B$ are two formulas without common variables (meaning, $p$ is a variable of $A$ iff $p$ isn't variable of $B$, and vice-versa) and $\vDash A\to B$. Then, at least one of the following is true: $\vDash \lnot A$, $\vDash B$.

Now, as far as I understand $\vDash A\to B$ means that $A\to B$ is a tautology. Hence, it must be one of three:

  • $A=t, B=t$
  • $A=f, B=f$
  • $A=f, B=f$

So clearly $\lnot A$ can't be a tautology and so is $B$.

Am I getting it the wrong way?

Elimination
  • 3,150
  • 19
  • 42
  • Isn't $\vDash A\to B$ by definition equivalent to $\neg A \lor B$? Because then it follows automatically that $\vDash \neg A$ or $\vDash B$ is true. – Protawn Mar 25 '16 at 20:54
  • @Protawn - it the condition "$A,B$ are formulas without common variables: $p, \ldots$" is not satsified, the claim is not true. We have $\vDash \lnot p \lor p$ but neither $\vDash \lnot p$ nor $\vDash p$. – Mauro ALLEGRANZA Mar 25 '16 at 21:03
  • A duplicate of http://math.stackexchange.com/questions/1507059/if-models-phi-supset-psi-then-there-is-a-propositional-variable-variable (the contrapositive!), but OK. – BrianO Mar 25 '16 at 22:06
  • 1
    Your argument is not correct for the same reason of the above comment: we have $\vDash p \to p$ and this means that only two possibilities are left (considering your example with $p$ in place of both $A$ and $B$): $p=$ t or $p=$ f. Then at least one of the following is true: $\vDash ¬p$, $\vDash p$. – Mauro ALLEGRANZA Mar 26 '16 at 11:13

1 Answers1

3

at least one of the following is true: $\vDash \lnot A, \vDash B$.

Assume not: i.e. $\nvDash \lnot A$ and $\nvDash B$.

This means that there is a valuation $v_1$ such that $v_1(A)=$t and a valuation $v_2$ such that $v_2(B)=$f.

But the two formulae have no common propositional variables; thus we can consider the valuation $v=v_1 \cup v_2$ and we have:

$v(A \to B)=$f

contradicting the assumption: $\vDash A \to B$.

Mauro ALLEGRANZA
  • 94,169