Hayward's 272 notes

Hayward's notes for CMPUT 272

based on the text by Bender and Williamson plus some extra stuff

formal system
sudoku
induction
collatz
beans
unit BF

formal system
sudoku
induction

simple induction example

collatz
beans
boolean functions and computer arithmetic

boolean functions
truth table
boolean operators
boolean operator precedence
number of boolean functions
0,1,2-variables
boolean algebraic rules
representing boolean functions
positional number systems

decimal
binary
base b
common
decimal to base b
base b to decimal

formal system

wikip defn

sudoku

nikoli sudoku
rules

∀ row permutation of { 1, 2, ..., 9 }

∀ column permutation of { 1, 2, ..., 9 }

∀ 3x3 block permutation of { 1, 2, ..., 9 }

sometimes puzzle makers ensure there is a unique solution
blank Jul 2006 #117©Penny Press Aug 21 2007©Pappocom
©Michael Mepham Aug 11 2007©MM Oct 1 2007©MM
web sudoku
tips: focus on cells/numbers, crosshatch, search/backtrack
Stephens how to solve sudoku puzzles
Norvig solving every sudoku puzzle

induction

history
example problem
- ∀ n ≥ 0, s(n) = 0+1+2+...+n = Σ_{j=0}^{n} j
- ∀ n ≥ 0, f(n) = n(n+1)/2
- ∀ n ≥ 0, s(n)=f(n) ?
how proof by induction works
- prove claim holds in base case
- prove if claim holds in any arbitrary case (starting with base) then claims holds in next case
- conclude claim holds for all values, starting with base case
youtube library dominoes

simple induction example

claim: ∀ integers n ≥ 0, s(n)=f(n)
base case:
let n=0. then
s(n) = s(0) = Σ_{j=0}^{0} j = 0, and
f(n) = f(0) = 0(0+1)/2 = 0, so
the claim holds in this case :)

inductive case:

inductive hypothesis:
let k be a fixed integer at least 0 (the value in the base case),
and assume that s(k)=f(k)
want to show: s(k+1)=f(k+1)

s(k+1)
	=	Σ_{j=0}^{k+1} j
	=	(Σ_{j=0}^{k} j) + (k+1)	express s(k+1) in terms of s(k)
	=	s(k) + (k+1)
	=	f(k) + (k+1)	ind. hyp.
	=	k(k+1)/2 + (k+1)	def. f(k)
	=	(k+1)(k/2 + 1)	rearrange
	=	(k+1)(k + 2)/2	rearrange
	=	f(k+1)	def. f(k+1)
			QED ... woo hoo !

collatz

def collatz(n):
    while n > 1:
        print n,
        if n % 2 == 0:
            n = n / 2
        else:
            n  = n * 3 + 1
    print "1\n"

wikidef

beans

repeat
- bn1 ← pickabean bn2 ← pickabean
- if (bn1.col = white) and (bn2.col = white) then putblack
- elseif (bn1.col = black) and (bn2.col = black) then putblack
- else putwhite
does loop terminate? under what conditions?
between each line of code: preconditions? postconditions? variants? invariants?

boolean functions

f(x) = 2x+1
function f: A → B rule, domain/input, range/output
×ⁿ{0,1} set of boolean n-tuples
boolean function f: ×ⁿ{0,1} → {0,1}

truth table

p q r   f(p,q,r)
0 0 0      0
0 0 1      1
0 1 0      0
0 1 1      1
1 0 0      0    
1 0 1      0
1 1 0      1
1 1 1      0

boolean operators

~ negation
∧ and conjunction
∨ or disjunction
⊕ xor exclusive-or p⊕q = p∧~q ∨ ~p∧q
→ implication p→q = ~p∨q
← is implied by p←q = p∨~q
↔ if and only if p↔q = ~(p⊕q)

p	q	~p	~q	p∧q	p∨q	p⊕q	p→q	p←q	p↔q
0	0	1	1	0	0	0	1	1	1
0	1	1	0	0	1	1	1	0	0
1	0	0	1	0	1	1	0	1	0
1	1	0	0	1	1	0	1	1	1

boolean operator precedence

~ ∧ ∨ → ↔
example
p ∨ r → ~ s ↔ t ∧ u = ((p ∨ r ) → (~ s)) ↔ (t ∧ u)

number of n-variable boolean functions?

number of n-variable truth tables?
domain size 2ⁿ, so each TT has 2ⁿ rows
each different output column gives diff't TT
number of diff't binary columns with 2ⁿ entries?
2^(2ⁿ) ... woo hoo !

0,1,2-variable boolean functions

0 variable ? f( ) = ...

1-variable ? f(x) = ...

0 1 x ~x

2-variable ? f(x,y) = ...

0
x y
x∧y x∨y x⊕y ~x∨y (same as x→y) x∨~y (same as y→x)
negations

boolean algebraic rules

~~p = p	double negation
p∧~p = 0 p∨~p = 1	negation
p∧0 = 0 p∧1 = p p∨0 = p p∨1 = 1	bound
p ◊ (p ∗ q) = p	absorption
p ◊ p = p	idempotent
p ◊ q = q ◊ p	commutative
(p ◊ q) ◊ r = p ◊ (q ◊ r)	associative
p ◊ (q ∗ r) = (p ◊ q) ∗ (p ◊ r)	distributive
~(p ◊ q) = ~p ∗ ~q	DeMorgan

◊ = ∧/∨ ∗ = ∨/∧

bool. fn. repn. thm.

any boolean function can be expressed

using variables, ~, ∨
using variables, ~, ∧

proof (sketch)

f( ) = 0?
f( ) = p∧~p = ~~(p∧~p) = ~(~p∨~~p) = ~(~p∨p)
f( ) ≠ 0?
f( ) = x₁ ∨ x₂ ∨ ... ∨ x_k x_j ↔ input with output 1
eliminate either ∨/∧ using ~~ and deMorgan

bool. fn. truth table

p q r  f(p,q,r)
0 0 0     0
0 0 1     1
0 1 0     0
0 1 1     1
1 0 0     0
1 0 1     0
1 1 0     1
1 1 1     0

with variables, ( ), ~ ∨ ∧

let
	a = (~p ∧ ~q ∧ r)
	b = (~p ∧ q ∧ r)
	c = (p ∧ q ∧ ~r)
then f(p,q,r)
=	a ∨ b ∨ c
=	(~p ∧ ~q ∧ r) ∨ (~p ∧ q ∧ r) ∨ (p ∧ q ∧ ~r)

without ∨

f(p,q,r)
=	a ∨ b ∨ c
=	~~(a ∨ b ∨ c)
=	~(~a ∧ ~b ∧ ~c)
=	~ ( ~(~p ∧ ~q ∧ r) ∧ ~(~p ∧ q ∧ r) ∧ ~(p ∧ q ∧ ~r) )

without ∧

f(p,q,r)
=	a ∨ b ∨ c
=	~~a ∨ ~~b ∨ ~~c
=	~(~a) ∨ ~(~b) ∨ ~(~c)
=	~(p ∨ q ∨ ~r) ∨ ~(p ∨ ~q ∨ ~r) ∨ ~(~p ∨ ~q ∨ r)

dnf and cnf

disjunctive normal form
a₁ ∨ a₂ ∨ ... ∨ a_t
where each a_j is ∧ of one or more (negated) variables
conjunctive normal form
a₁ ∧ a₂ ∧ ... ∧ a_t
where each a_j is ∨ of one or more (negated) variables
representation theorem converts function into dnf

from tabular to cnf

tabular ~f to dnf
deMorgan and ~~f = f

p q r  f(p,q,r)
0 0 0     0
0 0 1     1
0 1 0     0
0 1 1     1
1 0 0     0
1 0 1     0
1 1 0     1
1 1 1     0

~f(p,q,r)	=	v ∨ w ∨ x ∨ y ∨ z
where v	=	(~p ∧ ~q ∧ ~r)
w	=	(~p ∧ q ∧ ~r)
x	=	(p ∧ ~q ∧ ~r)
y	=	(p ∧ ~q ∧ r)
z	=	(p ∧ q ∧ r) so
~~f(p,q,r)	=	~(v ∨ w ∨ x ∨ y ∨ z)
	=	~v ∧ ~w ∧ ~x ∧ ~y ∧ ~z
	=	(p ∨ q ∨ r) ∧
		(p ∨ ~q ∨ r) ∧
		(~p ∨ q ∨ r) ∧
		(~p ∨ q ∨ ~r) ∧
		(~p ∨ ~q ∨ ~r)

from dnf to cnf

dnf → truth table → cnf (exercise)
distributive rule
(x1 ∧ x2) ∨ (y1 ∧ y2) =
(x1 ∨ (y1 ∧ y2)) ∧ (x2 ∨ (y1 ∧ y2)) =
(x1 ∨ y1) ∧ (x1 ∨ y2) ∧ (x2 ∨ y1) ∧ (x2 ∨ y2)
if f has n variables, how many literals in final cnf?

positional number systems: decimal

decimal (base 10) system out of India/Arabia, eg. Abu'l-Hasan al-Uqlidisi
12301 =
12301₁₀ =
1 × 10⁴ + 2 × 10³ + 3 × 10² + 0 × 10¹ + 1 × 10⁰

positional number systems: binary

binary (base 2)
11011001₂ =
1 × 2⁷ + 1 × 2⁶ + 0 × 2⁵ + 1 × 2⁴ + 1 × 2³ + 0 × 2² + 0 × 2¹ + 1 × 2⁰

positional number systems: base b

625301₇ =
6 × 7⁵ + 2 × 7⁴ + 5 × 7³ + 3 × 7² + 0 × 7¹ + 1 × 7⁰

arbitrary d-digit base b number, say
(x_d-1 x_d-2 ... x₂ x₁ x₀)_b =
Σ_k=0^d-1 (b^k × x_k) =
x_d-1 × b^d-1 + x_d-2 × b^d-2 + ... + x₂ × b² + x₁ × b¹ + x₀ × b⁰

common number systems

base 2: binary
base 3: ternary
base 8: octal
base 10: decimal
base 16: hexadecimal ( use digits 0 1 2 ... 9 A B C D E F )

convert decimal-to-(base b)

repeat: divide by b, take remainder

217 = 2 × 108 + 1

108 = 2 × 54 + 0

54 = 2 × 27 + 0

27 = 2 × 13 + 1

13 = 2 × 6 + 1

6 = 2 × 3 + 0

3 = 2 × 1 + 1

1 = 2 × 0 + 1

11011001₂
= 1 × 2⁷ + 1 × 2⁶ + 0 × 2⁵ + 1 × 2⁴ + 1 × 2³ + 0 × 2² + 0 × 2¹ + 1 × 2⁰
= 1 × 128 + 1 × 64 + 0 × 32 + 1 × 16 + 1 × 8 + 0 × 4 + 0 × 2 + 1 × 1
= 217₁₀

check work with calculator

convert (base b)-to-decimal

repeat: add digit, multiply by base

625301₇ = ?₁₀

1₇ = 1

01₇ = 1 + 7*(0)

301₇ = 1 + 7*(0 + 7*(3) )

5301₇ = 1 + 7*(0 + 7*(3 + 7*(5) ) )

...

625301₇ = 1 + 7*(0 + 7*(3 + 7*(5 + 7*(2 + 7*(6) ) ) ) ) = 107507₁₀

convert binary to hexadecimal

16 = 2⁴, so group bits in 4s

110101110100110001010100₂ =

1101 0111 0100 1100 0101 0100₂ =

D 7 4 C 5 4₁₆ =

∀ row	permutation of { 1, 2, ..., 9 }
∀ column	permutation of { 1, 2, ..., 9 }
∀ 3x3 block	permutation of { 1, 2, ..., 9 }
sometimes	puzzle makers ensure there is a unique solution

217	=	2	×	108	+	1
108	=	2	×	54	+	0
54	=	2	×	27	+	0
27	=	2	×	13	+	1
13	=	2	×	6	+	1
6	=	2	×	3	+	0
3	=	2	×	1	+	1
1	=	2	×	0	+	1

217	=	2	×	108	+	1
108	=	2	×	54	+	0
54	=	2	×	27	+	0
27	=	2	×	13	+	1
13	=	2	×	6	+	1
6	=	2	×	3	+	0
3	=	2	×	1	+	1
1	=	2	×	0	+	1

217	=	2	×	108	+	1
108	=	2	×	54	+	0
54	=	2	×	27	+	0
27	=	2	×	13	+	1
13	=	2	×	6	+	1
6	=	2	×	3	+	0
3	=	2	×	1	+	1
1	=	2	×	0	+	1