Hey aprilrocks92.
Have you got a definition of satisfiable and/or valid? What kind of structures do these objects have?
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.
F is satisfiable if F is true in at least one interpretation. For example, 1 + 1 = 0 is satisfiable because it is true in . 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.
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.
What do you mean by "truth table" here?
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?