# CS 2800 Lecture Notes - Lecture 3: Sudoku

20 views2 pages
Published on 3 Feb 2017
School
Course
Lecture 3
(Mon, January 30)
Today:
Proofs & quantifiers, function properties
Definition: A sudoku solution is a function s: C → N with the following 3 properties
1. For all i, for all n, there exists a j, such that s(i,j) = n
2. For all j, for all n, there exists an i, such that s(i,j) = n
3. For all c1≠c2, if box(c1) = box(c2) then s(c1)≠s(c2)
In English, these three properties are:
1. Each number appears in every row
2. Each number appears in every column
3. No number appears twice in the same box
X≥7 is a predicate
Predicate: something that is true or false based on a variable
There exists an x in N (natural numbers) such that x≥7
→ this is a proposition (and is true)
To prove a statement with “there exists” → we need to give an example
To disprove a statement with “there exists” → we need to disprove for all possible cases
For all x in N (natural numbers), x≥0
→ this is another proposition, and is also true
To prove a statement with “for all” → we need to prove it for all possible cases
To disprove a statement with “for all” → we need to find one counterexample
Note: the order of quantifiers is important
Let’s write property 1 in other styles
For all i, for all j1, j2 if j1≠j2, s(i,j1) ≠ s(i,j2) [this is 1’]
For all i, for all j1, ,j2 if s(i,j1) = s(i,j2) then j1=j2 [this is 1’’]
Proof: what is a proof? A logical series of statement.
Proof example:
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.