CS 2800 Lecture Notes - Lecture 3: Sudoku

20 views2 pages
Published on 3 Feb 2017
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.

Already have an account? Log in

Get OneClass Notes+

Unlimited access to class notes and textbook notes.

YearlyBest Value
75% OFF
$8 USD/m
Monthly
$30 USD/m
You will be charged $96 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.