1
$\begingroup$

I'm struggling with a proof in the text for my logic course, and I'm wondering if someone could offer a hint or some help. The question is basically as follows. Show that if the decision problem for satisfiability is solvable iff the decision problem for implication is solvable. Then, show that the decision problem of implication is solvable iff the decision problem of validity is solvable.

My attempt so far is as follows. Suppose we can decide whether or not a given sentence is satisfiable. If not, implication problem for the sentence A is true. If it is satisfiable, we must ensure that all interpretations in which A is satisfiable, B is also true.

I'm assuming the second part proceeds similarly, but I'm not exactly sure, and would appreciate any guidance.

Thanks

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Can you be more explicit about exactly what your question is? I suspect you're already aware that "please do the second part of my homework question for me" is not a good fit for this site. So, we prefer that you articulate a more specific question about what you're confused or uncertain about. What approaches have you considered, for the second part? How far have you gotten? Is there anything in particular that you are unsure about? Right now you haven't given us much to work with, in terms of understanding what your specific issue might be. $\endgroup$ – D.W.♦ Oct 30 '15 at 21:59
  • $\begingroup$ I'm not actually very sure I've got the first part right either. I'd just like kind of a general procedure for showing these implications. Not a full proof, but just sort of an outline. Also, this actually isn't a homework question per se. It's just a question from a logic text that I thought I'd clarify. $\endgroup$ – user979616 Oct 31 '15 at 6:51

Your Answer

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

Browse other questions tagged or ask your own question.