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 have a confusion regarding how to check whether a wff is satisfiable, unsatisfiable and valid.

As far as I understood, valid means the truth table must be a tautology, otherwise it is not a valid wff. For eg, p or (not p) is valid since it is a tautology, whereas p and (not p) is a contradiction. So it is not valid.

Unsatisfiable means the truth table is a contradiction. ie. A wff which is not valid is unsatisfiable. Eg. p and (not p)

Satisfiable can be a tautology or even if there is one True value in the truth table. Eg. p or (not p) is tautology and not(p implies q) has one True. So, they are satisfiable.

Am I correct about the terms? If not, please explain with simple examples like what I've used. Thanks in advance.

UPDATED:

Please check out [satisfiability][1] In that there is a definition about satisfiability which confuses me. It says, a formula 'A' is satisfiable if and only if 'not(A)' is not a tautology

share|improve this question
    
Yes, this seems correct. The first three paragraphs of the wikipedia article on Tautology also seems to agree. –  William Aug 17 '12 at 6:55
    
@William Please check out [docs.google.com/… In that there is a definition about satisfiability which confuses me. :( –  Gomathi Aug 17 '12 at 7:00
    
The linkn is not working for me. –  Gerry Myerson Aug 17 '12 at 7:09
    
What exactly does confuse you? Let $\phi(x_1, \ldots, x_n)$ be a wff. If $\phi$ is satisfiable, then there are some $p_1,\ldots, p_n$, s. t. $\phi(p_1,\ldots, p_n)$ is true, so $\neg\phi(p_1,\ldots, p_n)$ is false, hence $\neg\phi$ is no tautology. On the other hand, if $\neg\phi$ isn't a tautology, for some $p_1,\ldots, p_n$ $\neg\phi(p_1,\ldots, p_n)$ is false, hence $\phi(p_1,\ldots, p_n)$ holds true. Alltogether: $\phi$ is satisfiable iff $\neg\phi$ is no tautolofy. –  martini Aug 17 '12 at 7:11
add comment

1 Answer

up vote 3 down vote accepted

The following may seem rather strange, but I hope it'll help you think about these three concepts.

Let $\Bbb B$ denote the boolean set $\{ T, F \}.$ Now, think of the WFF containing $n$ propositions as a function: $\Bbb{B}^n \to \Bbb{B}.$ I will use the following WFF as my running example: $p \land \lnot q.$ That's a "function" $\mathbb{B}^2 \to \Bbb{B}.$ It's a function that takes two boolean inputs (each being true or false) and produces a boolean value $f(p, q) = p \land \lnot q.$ The truth table is just a tabulation of this "function" for all (four) possible values of $p$ and $q.$

This "function" could be true for some values of $p, q$. It could also be false for some other values of $p, q.$ Some functions are always (constant) true or always (constant) false. This is exactly the distinction between satisfiable, valid, and unsatisfiable, respectively.

Now, a WFF is valid if $f(p, q) = T$ for all values of $p, q.$ It's unsatisfiable if $f(p, q) = F$ for all values of $p, q.$ The former two cases resemble constant functions. A WFF is satisfiable if $f(p, q) = T$ for some values of $p, q.$ It could be true/false for all other values; that doesn't matter. What matter is that it's possible to find values of $p, q$ to satisfy the WFF (satisfy a WFF = making the WFF true).

share|improve this answer
    
And you're correct about your examples. –  user2468 Aug 17 '12 at 7:18
    
Thanks, then if f(p,q)=T for all values of p,q , then is it satisfiable? –  Gomathi Aug 17 '12 at 7:23
    
@Gomathi that's correct. If it's true for all $p, q$ then it's certainly true for some and hence satisfiable. Read satisfiable as "possible to satisfy", and hence valid formulas are always possible to satisfy. –  user2468 Aug 17 '12 at 7:28
    
Thank you so much. I'm very much clear now. :) –  Gomathi Aug 17 '12 at 7:31
add comment

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.