A sentence is satisfiable if and only if there is an interpretation of it in whi

Question

A sentence is satisfiable if and only if there is an interpretation of it in which it is true, a sentence A implies a sentence B if and only if there is no interpretation of A and B in which A is true and B is false, and a sentence is valid if and only if it is true in all of its interpretations. Show that the decision problem for satisfiability is solvable if and only if the decision problem for implication is solvable, and the decision problem for implication is solvable if and only if the decision problem for validity is solvable.

Explanation / Answer

Let A, B be two sentences

from the above statement, A or B should be true on some interpretation to be satisfiable,

it means that if A=> B then B is never false if A is true,

A or B should be true on all interpretation to be valid.

Proof: Let us use indirect method

Suppose, a decision problem, say d(A,B) be valid

the d(A,B) is true on all interpretations.

Since d(A,B) contains A and B both must be true on all interpretations, according to the definition of validity.

Since for d(A,B) to be implication the must be no condition where A is true and B is false.

d(A,B) being a valid sentence, there is no interpretation for which B is false.

Thus d(A,B) is also implication.

Similarly for the sentence d(A,B) be satisfiable if and only if there is an interpretation which is true and since d(A,B) is both implication and valid, thus it is also satisfiable as for the sentence to be implication or valid there is atleast one interpretation which is true. Thus the above statement is proved through indirect method.

Example:

let A= its is monday

B= it is raining.

suppose A is false then even if it is not monday, it can rain. Thus the statement is satifiable. But the statement " if A the B " (implication) is not always true.

Let

let A= its is cloudy

B= it is raining.

Now these statements are satisfiable and also valid but may not be always valid because not all cloudy days rain.

Let

let A= its is raining

B= it is wet outside.

Now these statements are satisfiable, implication and valid because if it rains, then it will be wet on all interpretations.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.