1

I found this problem in an old logic textbook in the library but it unfortunately did not have any answers is my understanding/attempt correct? Can it be improved?

Consider the set Φ consisting of the following five predicate logic formulas.

$∀x (old(x) → wise(x))$

$∀x (old(x) ∨ wise(x) → knight(x))$

$∃x old(x)$

$∃x ¬wise(x)$

$∃x ¬knight(x)$

Please describe the following interpretations, by stating the domain of discourse and the interpretation of the three predicate symbols mentioned in the formula.

a) Describe a model for Φ with a finite domain of discourse.

b) Describe a model for Φ with an infinite domain of discourse.

c) Describe an interpretation that is not a model for Φ.

d) Based on the above, would you say that Φ is valid, satisfiable but not valid, or unsatisfiable?

My attempt:

a)

Domain of discourse: $D = \{a, b, c\}$

Interpretation of Predicate symbols: $old^I$, $wise^I$, and $knight^I$ (as given by the table)

Assignment of Variable symbols: $x^I$ = a, b or c? (Not sure how to do this)

$$ \begin{array} {|r|r|} \hline & old^I & wise^I & knight^I \\ \hline a & T & T & T\\ \hline b & F & T & T\\ \hline c & F & F & F\\ \hline \end{array} $$

b)

Domain of discourse: D = $\mathbb{N}_0$ = $\{0,1,2,…\}$

Interpretation of Predicate symbols:

$$old(n) = \left\{ \begin{array}{lcc} T & n \% 5 == 0\\ \\ F, & for \space anything \space else \\ \\ \end{array} \right.$$

$$wise(n) = \left\{ \begin{array}{lcc} T & n \space \% \space 5 == 0\\ \\ T, & n \space \% \space 10 == 0 \\ \\ F, & for \space anything \space else \\ \\ \end{array} \right.$$

$$knight(n) = \left\{ \begin{array}{lcc} T & n \space \% \space 5 == 0\\ \\ T, & n \space \% \space 10 == 0 \\ \\ F, & for \space anything \space else \\ \\ \end{array} \right.$$

Assignment of Variable symbols: $x^I$ = ... (Not sure how to do this)

c)

Domain of discourse: $D = \{a\}$

Interpretation of Predicate symbols: $old^I$, $wise^I$, and $knight^I$ (as given by the table)

Assignment of Variable symbols: $x^I$ = a

$$ \begin{array} {|r|r|} \hline & old^I & wise^I & knight^I \\ \hline a & T & T & F\\ \hline \end{array} $$

This interpretation is not a model because $∀x (old(x) ∨ wise(x) → knight(x))$ is not possible in this case.

d)

Φ is satisfiable but not valid because it holds under some interpretation e.g. the interpretations for a) and b) but it is not valid because it does not holds under every interpretation i.e the interpretation for c)

Jerry Springer
  • 13

1 Answers1

1

You don't assign values to the variables in an interpretation: just provide a domain and interpret the predicate symbols!

a) For your finite domain: Your interpretation works, though note:

You need someone who is old, and anyone who is old is wise, and yet there is someone who is not wise ... So you need at least two different objects: one who is old and wise, and one who is not wise, and thus not old. Also, anyone old or wise is a knight, and yet there is someone not a knight. Well, the first person is a knight, but the second person does not need to be. So, you can have a counterexample with just two objects: someone who is old, wise, and a knight, and someone who is none of those.

b) For your infinite model, you can of course simply pick 1 object who is old, wise, and a knight, and infinitely many other objects who are all not old, not wise, and not knights. Or vice versa.

c) Your non-model works: as we already established, you need at least two objects in any model, so any interpretation with 1 object will not be a model, no matter what.

d) exactly right!

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • @JerrySpringer It depends how formal the answer needs to be. Many people would be just fine with that one sentence .. But some may insist on a mathematical description. So, how about: domain is $\mathbb{N}_0$, and $I(old)=I(wise)=I(Knight)={ 0 }$ – Bram28 Mar 12 '17 at 02:51
  • So I just list the elements on the domain that have the property 'old', ,wise' , etc. as the interpretation, which is how interpretations of 1-place predicates are mathematically defined: subsets of the domain. If you want something more 'meaningful', you could interpret all three predicates as 'equals zero' or 'is the smallest number'. – Bram28 Mar 12 '17 at 02:57
  • Thanks so much you cleared so many of misconceptions. – Jerry Springer Mar 12 '17 at 02:58
  • @JerrySpringer You're welcome. And again: that was an amazing first post with all the type-setting! That's why I didn't realize it was your first post on Math.SE! – Bram28 Mar 12 '17 at 03:01