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

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?

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 $\displaystyle \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.

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

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.

Quote:

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?

Quote:

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?