Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I tend to see these words a lot in Discrete Mathematics. I assumed these were just simple words until I bumped into a question.

Is the following proposition Satisfiable? Is it Valid?
$(P \rightarrow Q) \Leftrightarrow (Q \rightarrow R ) $

Then I searched in the net but in vain. So I'm asking here. What do you mean by Satisfiable and Valid? Please explain. Thanks in advance!

share|improve this question

3 Answers 3

up vote 4 down vote accepted

A formula is valid if it is true for all values of its terms. Satisfiability refers to the existence of a combination of values to make the expression true. So in short, a proposition is satisfiable if there is at least one true result in its truth table, valid if all values it returns in the truth table are true.

share|improve this answer
    
hey! this was the same stuff that I came across in the net. If you could explain using an example, it would be great. –  VISHNU VIVEK Dec 14 '12 at 10:36
    
The expression (p .AND. q) is satisfiable-- it returns true whenever both p and q are true. On the other hand, (p .OR. .NOT.p) is valid, it always is true regardless of the value of p. –  ashley Dec 14 '12 at 22:21
    
The expression in your Q is satisfiable but not valid. It returns true for (p, q, r)=(true, true, true) and false for (true, false, true). –  ashley Dec 14 '12 at 22:28

Satisfiability -the other way of interpretation
A propositional statement is satisfiable if and only if, its truth table is not contradiction.
Not contradiction means, it could be a tautology also.

Hence, every tautology is also Satisfiable.
However, Satisfiability doesn't imply Tautology.

Another thing to note is, if a propositional statement is Tautology, then its always valid.

Thus, Tautology implies ( Satisfiability + Validity ).

share|improve this answer

A propositional logic is said to be satisfiable if its either a tautology or contingency. Hence if a logic is a contradiction then it is said to be unsatisfiable. By contingency we mean that logic can be true or false i.e. nothing can be said for sure about the logic.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.