### IV.8 Exercises

#### Exercises [Slide 126]

Exercise 18.

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

Express each of these ﬁrst order formula in English.

• X IsOdd(X)
• X IsOdd(X)
• ¬(X IsOdd(X))
• ¬(X IsOdd(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 variables is the set of integers, what are the truth values of the following?

• p(1, 1)
• p(2, 0)
• y p(1,y)
• x p(x, 2)
• x y p(x,y)
• x y p(x,y)
• y x p(x,y)
• y x p(x,y)
• x y p(x,y)

Exercise 21.

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

• (A + B) = (B + A)
• A A = 0
• A IsOdd(A)
• (A f) (A f)

Exercise 22.

Let p(X) be the statement “X has a pen”, let q(X) be the statement “X has 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 not a 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 of yours that has one.

Exercise 23.

Let p(X) be the statement “X is a duck”, let q(X) be the statement “X is 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 statements using 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.

Exercise 24.

Translate the following conversational English statements into ﬁrst-order logic, using the suggested predicates, or inventing appropriately-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 knows that Agent Mulder has been kidnapped.” (Is this true, presuming that no UFOs have actually visited Earth ...yet?)

Exercise 25.

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

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 the constraints.

So, our domain is {1, 2, 3, 4, 5, 6, 7, 8, 9}. To model the game, we will use the 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 at row r, column c.

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

 2018-03-10 Contact | Home | ITL home | Course | Proofs | Algebra | FL