CSE 676, Fall 2001

#### HW # 1 ANSWERS

 Last Update: 20 September 2001 Note: material is highlighted
Note:
"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.

Copyright © 2001 by William J. Rapaport (rapaport@cse.buffalo.edu)
file: 676/F01/hw1.answers.20sp01.html