Let IsOdd(X) be the statement “X is an odd number”.

Express each of these ﬁrst order formula in English.

∃XIsOdd(X)

∀XIsOdd(X)

¬(∃XIsOdd(X))

¬(∀XIsOdd(X))

∃X¬IsOdd(X)

∀X¬IsOdd(X)

¬(∃X¬IsOdd(X))

¬(∀X¬IsOdd(X))

Which of these “mean” the same thing?

Exercise 19.

Give the semantics of the following formulae

4 > 3

A + 5 ≤ B∧B = D − 7

P ≡ (A + 5 ≤ B)

Q ≡ (B = D − 7)

∀A(A + 1 > A)

A = 8∧∃B(A = 2 ∗∗B)

Exercise 20.

Let p(x,y) be the statement “x+y=x-y”. If the domain for both variablesis the set of integers, what are the truth values of the following?

p(1, 1)

p(2, 0)

∀yp(1,y)

∃xp(x, 2)

∃x∃yp(x,y)

∀x∃yp(x,y)

∃y∀xp(x,y)

∀y∃xp(x,y)

∀x∀yp(x,y)

Exercise 21.

Determine which of the following formula is satisﬁable or valid. Explainwhy.

(A + B) = (B + A)

∃AA = 0

∀AIsOdd(A)

(∃Af)⊃(∀Af)

Exercise 22.

Let p(X) be the statement “X has a pen”, let q(X) be the statement “Xhas a pencil”, and let r(X) be the statement “X has a piece of paper”.Express each of these statements in ﬁrst-order logic using these relations.Let the domain be your classmates.

A classmate has a pen, a pencil, and a piece of paper.

All your classmates have a pen, a pencil, or a piece of paper.

At least one of your classmates has a pen and a pencil, but nota piece of paper.

None of your classmates has a pen, a pencil, and a piece of paper.

For each of the three writing materials, there is a classmate ofyours that has one.

Exercise 23.

Let p(X) be the statement “X is a duck”, let q(X) be the statement “Xis one of my poultry”, let r(X) be the statement ‘X is an oﬃcer”, and s(X)be the statement “X is willing to waltz”. Express each of these statementsusing quantiﬁers, logical connectives, and the relations p(X),q(X),r(X),and s(X).

No ducks are willing to waltz.

No oﬃcers ever decline to waltz.

All my poultry are ducks.

My poultry are not oﬃcers.

Does the fourth item follow from the ﬁrst three taken together?Explain your answer.

Exercise 24.

Translate the following conversational English statementsinto ﬁrst-order logic, using the suggested predicates, or inventingappropriately-named ones if none provided. (You may also freely use =which we’ll choose to always interpret as the standard equality relation.)

“All books rare and used”. This is claimed by a local bookstore;what is the intended domain? Do you believe they mean to claim“all books rare or used”?

“Everybody who knows that UFOs have kidnapped people knowsthat Agent Mulder has been kidnapped.” (Is this true, presumingthat no UFOs have actually visited Earth ...yet?)

Exercise 25.

The puzzle game of Sudoku is played on a 9 × 9 grid, where each squareholds a number between 1 and 9. The positions of the numbers must obeyconstraints. Each row and each column has each of the 9 numbers. Eachof the 9 non-overlapping 3 × 3 square sub-grids has each of the 9numbers.

Throughout the game, some of the values have not been discovered,although they are determined. You start with some numbers revealed,enough to guarantee that the rest of the board is uniquely determined by theconstraints.

So, our domain is {1, 2, 3, 4, 5, 6, 7, 8, 9}. To model the game, we will usethe following relations:

value(r,c,v) indicates that at row r, column c is the value v.

v = w is the standard equality relation.

subgrid(g,r,c) indicates that subgrid g includes the location atrow r, column c.

Express the row, column, and subgrid constraints for Sudoku as ﬁrst orderformulae and brieﬂy explain them. In addition, you should includeconstraints on our above relations, such as that each location holds onevalue.