Published on 3 Feb 2017

School

Department

Course

Professor

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: