1
$\begingroup$

I have a question, I am doing this exercise but I am a bit lost, it is the following:

Let $\Sigma = \{\phi_1,...,\phi_n\}$ and $\varphi$ a proposition. Show that $\Sigma \vDash\varphi \iff \left(\phi_1,...,\phi_n\right)\rightarrow\phi$ is a tautology.

I am trying to prove that by contradiction, first proving it from left to right, this is what I have:

Let suppose that $\Sigma \vDash \varphi \land \left(\phi_1,...,\phi_n\right)\rightarrow\phi$ is not a tautology, then we have:

$(\forall$ valuation $V, (V(\Sigma)=1 \land V(\varphi) = 1)) \land \exists V_0, (V_0(\phi)=0\land V_0(\Sigma) = 1)$

I am stuck on that part. I don't know if the problem statement is wrong and it is really $\left(\phi_1,...,\phi_n\right)\rightarrow\varphi$, because is that were the case and I were good in my reasoning, it would be easy to reach a contradiction. Could someone give me a hand?

$\endgroup$
4
  • $\begingroup$ What kind of thing is $\Sigma$? What are the $\phi_i$s? $\endgroup$
    – hmakholm left over Monica
    Aug 21, 2015 at 2:25
  • $\begingroup$ Yes, it does help to define the nature of the symbols. $\endgroup$
    – Graham Kemp
    Aug 21, 2015 at 2:28
  • $\begingroup$ MY BAD I have corrected it $\endgroup$
    – dpalma
    Aug 21, 2015 at 2:42
  • $\begingroup$ You have to rewrite your condition as : $(∀V(V(Σ)=1 → V(\varphi)=1)) \quad ∧ \quad ∃V_0(V_0(Σ)=1∧V_0(\varphi)=0)$; in this way, the contradiction is clear, because the right conjunct is the negation of the left one : $\lnot (p \to q) \equiv (p \land \lnot q)$. $\endgroup$
    – Mauro ALLEGRANZA
    Aug 23, 2015 at 16:39

1 Answer 1

Reset to default
0
$\begingroup$

Note: $$A\Leftrightarrow B \qquad\equiv\qquad (A\wedge B) \vee (\neg A\wedge\neg B)$$

$$A\nLeftrightarrow B \qquad\equiv\qquad (A\wedge \neg B) \vee (\neg A\wedge B)$$

What you are to prove is a tautology is: $$\Sigma \vDash\varphi \iff (\phi_1, \ldots,\phi_n)\to\varphi$$

This is not (necessarily): $\Sigma \vDash\varphi \wedge (\phi_1, \ldots,\phi_n)\to\varphi$

$\endgroup$
4
  • $\begingroup$ I am trying to do a proof by contradiction (making the proofs from left to right and then from right to left), so I supposed that the first fact is true and the second is false, but that is a first step on the entire proof. $\endgroup$
    – dpalma
    Aug 21, 2015 at 2:08
  • $\begingroup$ @dpalma That is what you need to do. That is not what you did. $\endgroup$
    – Graham Kemp
    Aug 21, 2015 at 2:26
  • $\begingroup$ isnt P -> Q equivalent to ~P v Q, so, the negation of that is P ^ ~Q, or am I wrong? $\endgroup$
    – dpalma
    Aug 21, 2015 at 2:45
  • $\begingroup$ I am going to accept the answer, since you gave the correct definition. Thanks for your patience :) $\endgroup$
    – dpalma
    Aug 21, 2015 at 13:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .