# FA17 Lecture 2

## Contents

# Lecture 2: Using functions to model problems

- reading: MCS [[../handouts/mcs.pdf#page=19|1.5-1.9]]
- [[../../2017sp/lectures/lec02-sudoku.html|Last semester]]
- using functions to define sudoku solution
- using quantifiers (for all and there exists)
- new notation: cartesian product ( ), for all ( ), function .
- review exercise: describe solutions to some other kind logic puzzle.

## Notation

- If
**cartesian product**of and , denoted is the set of pairs where the first part is an element of and the second part is an element of . For example, .
and are sets, then the - the upside-down A (∀) stands for
**for all**. I tend to write out the words, but occasionally the symbols are useful. It is important to be able to go back and forth. - The symbol indicates that is a function with domain and codomain .
- The symbol is used to emphasise that an equation is the definition of a variable or term.

## Sudoku

As an example, we use functions to carefully describe the solution to a sudoku puzzle. We are not describing a process to find the solution, only the properties that a solution must have.

We start by making up some notation: let

be the set of numbers. Let be the set of cells.We define a helper function

that gives us the "big box" containing the given cell. That is, gives the number in the th row and the th column of the following table:If we really wanted, we could write down a formula for the

function (something like ). But it isn't necessary: it doesn't make the function any clearer than the table. When writing definitions, optimize for clarity. Use mathematical notation when it helps clarify, but avoid it when it obscures.Now we can define a solved sudoku board. A solved sudoku board must have a single number in each cell. Therefore, we model it as a function

; given the cell , gives the number in the corresponding cell. I am using the convention that is a row number and is a column number, but nothing about the formal definition requires this (except in the definition of ).Sudoku solutions

must satisfy three properties. We list them informally and formally:- For any row, and any two different columns, the numbers in that row and those columns are different. With lots of notation: , if then
- For any column and any two different rows, the numbers in that column and those rows are different: if then .
- Two different cells in the same box must have different values: , if but , then .

A few notes about these definitions:

- Note that the formal (symbolic) defintions are much harder to read than the English description. When writing, your goal is to convey understanding to the reader. The informal description helps the reader build a mental picture, while the formal description helps the reader connect that picture to the objects you are using to model the picture. Optimize for communication.
- Although rules 1 and 2 are completely parallel, I chose to formalize them in slightly different ways (the only reason to do this is to demonstrate both styles). In general, a statement of the form "if P then Q" is equivalent to "the only way that Q is false is if P is also false" or more succinctly, "if not Q then not P". These statements ("if P then Q" and "if not Q then not P") are called
**contrapositives**. In this case, the contrapositive is sometimes easier to work with, because it's sometimes easier to reason about things being equal than things being unequal. - In rules 2 and 3, I left off the fact that and are in , and that and are in . This can be inferred from the fact that and are plugged into , and the domain of contains cells (which are pairs of numbers). It is also suggested by the fact that I'm consistently using , , and for numbers, and for cells. As with the other stylistic decisions, you should optimize for clarity.

At the end of lecture, we posited a different informal way to state the sudoku rules: instead of saying no two entries are the same, we instead might require that every number appears somewhere. We'll discuss this alternative in the next lecture.

## Some questions that were asked

**Q:** Can we model a solved sudoku problem as a set of 9 sets of numbers?

**A:** No, there is not enough data. For example, , so we can't distinguish between two boards with the first columns in a different order. Moreover, we couldn't represent a board like , because the first two columns are the same set, and so this set would only have 8 columns.

**Q:** Can we model a solved problem as a 9-tuple of 9-tuples of numbers?

**A:** Yes. However, this would make the rules harder to state (try it!); you'd need notation for extracting the th element of a tuple. You might write the th entry of the th entry of the board as , but then your definition would be exactly the same as the function definition: instead of writing you'd write . Also, it wouldn't be a good example for function notation.