# Finding Satisfiability, Unsatisfiability and Valid well formed formula

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 satisﬁable if and only if 'not(A)' is not a tautology

-
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

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).

-
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