IV.8 Exercises

Exercises [Slide 128]

Exercise 18.  

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

Express each of these first order formula in English.

Which of these “mean” the same thing?

Exercise 19.  

Give the formal semantics of the following formulae

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?

Exercise 21.  

Determine which of the following formula is satisfiable or valid. Explain why.

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 first-order logic using these relations. Let the domain be your classmates.

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 officer”, and s(X) be the statement “X is willing to waltz”. Express each of these statements using quantifiers, logical connectives, and the relations p(X),q(X),r(X), and s(X).

Exercise 24.  

Translate the following conversational English statements into first-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.)

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:

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

2023-09-12
Contact | Home | ITL home | Course | Proofs | Algebra | FL
© 1996-2023