# Thread: Proving satisfiability and validity

1. ## Proving satisfiability and validity

Hi,

I am struggling to prove whether the following statements are true or false, and consequently to prove why that is.
Mainly because I don't understand the difference between satisfiable and valid, so if someone could explain that, I'd highly appreciate it!

(i) For all F, F is satisfiable or ~F is satisfiable.

(ii) For all F, F is valid or ~F is valid.

2. ## Re: Proving satisfiability and validity

Hey aprilrocks92.

Have you got a definition of satisfiable and/or valid? What kind of structures do these objects have?

3. ## Re: Proving satisfiability and validity

F is satisfiable if F is true in at least one interpretation. For example, 1 + 1 = 0 is satisfiable because it is true in $\mathbb{Z}_2$. F is valid if it is true in all interpetations. For example, 1 + 1 = 0 and 1 + 1 = 2 are not valid, but 1 = 1 is. Obviously, if a formula is valid, it is satisfiable. (This assumes that there is at least one interpretation.)

Concerning the first claim, a stronger one is true: F is satisfiable or ~F is valid for all F.

4. ## Re: Proving satisfiability and validity

So far, I have the following:
Statement (i) is true, as for all F, F will either be satisfiable, or ~F will be satisfiable (truth table). However, how do I go about solving for statement (ii)?

5. ## Re: Proving satisfiability and validity

First, I have to ask. Have you learned the definitions of formulas, interpretations and when a formula is true in an interpretation? Without it, it's meaningless to go forward.

Originally Posted by aprilrocks92
Statement (i) is true, as for all F, F will either be satisfiable, or ~F will be satisfiable (truth table).
What do you mean by "truth table" here?

Originally Posted by aprilrocks92
However, how do I go about solving for statement (ii)?
Let's take this in steps. Let P(i) say "i is prime" where i is a natural number. Does the following disjunction hold:

(for all i, P(i) holds) or (for all i, P(i) does not hold)?

Now, let i range over interpretations instead of numbers and let P(i) say that the given formula F is true in an interpretation i.

(1) F is valid ⇔ F is true in all interpretations i ⇔ for all i, P(i) holds .

Similarly,

(2) ~F is valid ⇔ ~F is true in all interpretations i ⇔ F is false in all i ⇔ for all i, P(i) does not hold.

Does it have to be that (1) or (2) holds?