HW # 1 ANSWERS

"A" represents the universal quantifier;
"E" represents the existential quantifier;
"~" represents negation.

8.

a) Ax[P(x) -> Q(x)]

b) Ex[Q(x) ^ P(x)]

c) ~Ax[Q(x) -> P(x)]
   or: Ex~(Q(x) -> P(x))
   or: Ex[Q(x) ^ ~P(x))

9.

a) Something (or: someone) is a politician.
   or: There is a politician.

b) Something (or: someone) is honest.

c) All politicians are not honest (or: are dishonest).

d) There is an honest politician.

e) There is something (or: someone) who, if she/he/it is a politician, is honest.
   [Note: my pen satisfies this!]

10. Note: I(P) = is almost like "less than or equals", except that ~P(2,2); for convenience, I will use "<=" below to represent this relation. Note that "P" is the predicate symbol in the syntax of our representation language that names or refers to this relation, whereas "<=" is the relation in the model or conceptualization (i.e., in the semantic domain).

a) |=_I P(a,f(a)) ^ P(b,f(b)) iff

   I(P)[I(a), I(f)[I(a)]]
   & I(P)[I(b), I(f)[I(b)]]

   iff

   I(a) <= I(f)[I(a)]
   & I(b) <= I(f)[I(b)]

   iff

   1 <= I(f)[1]
   & 2 <= I(f)[2]

   iff 1 <= 2 & 2 <= 1

   But 2 is not <= 1
   So, P(a,f(a)) ^ P(b,f(b)) is not satisfied by I.

b) |=_I P(a,a) iff 1 <= 1
   satisfied

c) |=_I AxEyP(x,y) iff for each x, there is a y such that x <= y
   iff there is a y such that 1 <= y
      & there is maybe another y such that 2 <= y

   But there is no y such that 2 <= y
   So, not satisfied.

d) |=_I AxAy[P(x,y) -> P(f(x),f(y))] iff:
   if 1 <= 1, then 2 <= 2
   & if 1 <= 2, then 2 <= 1
   & if 2 <= 1, then 1 <= 2
   & if 2 <= 2, then 1 <= 1

   But, in the first conjunct, the antecedent can be true while the consequent can be false
   So, the first conjunct is false
   So, not satisfied

11.

a) Ax: x is an American citizen;
   Fx: x belongs to the FBI

   Ax[Fx -> Ax]

b) Fx: x is a farmer;
   Dx: x is a donkey;
   Oxy: x owns y;
   Bxy: x beats y

   Ax[Fx ^ Ey[Dy ^ Oxy] -> Bxy]

Note that "Bxy" contains a free occurrence of "y"; hence, this formula is ill-formed, even though it fairly closely captures the English expression.

For discussion, see:

• McCawley, James D. (1981), Everything that Linguists Have Always Wanted to Know about Logic but Were Ashamed to Ask (Chicago: University of Chicago Press).

• Donkey Sentence Discussion
  • May need to be viewed on a non-Unix browser

c) Rx: x is a relation;
   Ref(x): x is reflexive;
   Sat(x,y,z): x and y satisfy z

   Az[Rz ^ Ref(z) -> AxAy[Sat(x,y,z) -> Sat(y,x,z)]]

   or: Az[Ref(z) -> AxAy[z(x,y) -> z(y,x)]],
   which is a second-order sentence!

12.

a) i: me!
   Saw(x,y): x saw y;
   Ax: x is an animal;
   Cx: x is a cat;
   Dx: x is a dog;
   Kxy: x knows that [or: can tell whether] y

   Ex[Ax ^ Saw(i,x) ^ ~K(i, (Cx v Dx))]
   which is not first-order!

b) Px: x is persistent;
   Person(x): x is a person;
   Lxy: x may [= can? it is possible that?] learn y;
   l: logic

   Ax[Px ^ Person(x) -> L(x,l)]

c) Px: x is a politician;
   Hx: x is honest

   ~Ex[Px ^ Hx]
   or: Ax[Px -> ~Hx]

d) Bx: x is a bird;
   Fx: x flies

   ~Ax[Bx -> Fx]

e) Axy: x is able to do y;
   a: Anna

   EyEx[Axy -> Aay]

f) j: John;
   Hxy: x hates y

   Ax[~Hxx -> Hjx]

For discussion, see: Shapiro, Stuart C. (1986), "Symmetric Relations, Intensional Individuals, and Variable Binding", Proceedings of the IEEE 74(10): 1354-1363.