# Proving satisfiability and validity

• Sep 22nd 2013, 10:30 PM
aprilrocks92
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.
• Sep 22nd 2013, 10:48 PM
chiro
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?
• Sep 23rd 2013, 08:33 AM
emakarov
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.
• Sep 23rd 2013, 11:39 AM
aprilrocks92
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)?
• Sep 23rd 2013, 01:07 PM
emakarov
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?