MATH 374 Discrete Structures Notes

Jan 13 2016

Section 1.1

Compound propositions

The sun shines, and if gold price goes up, then Euro price goes down. S \land ( G \to E)

S \land (G \to E)

Well-formed formula (WFF)

Not WFF:

• p \lor \land q
• p)) q \lor ((

Binding Strength

1. () parentheses
2. ‘ negation
3. \lor or, \land and
4. \to implication
5. \leftrightarrow biconditional

Defs

Tautology

proposition true with all possible values of variables (denoted 1)

Contradiction

proposition false with all possible values of variables (denoted 0)

Contingency

proposition neither Tautology nor Contradiction

DeMorgan’s Laws

(p \lor q)’ \iff p’ \land q’

(p \land q)’ \iff p’ \lor q’

Sheffor Stroke (NAND)

A B A|B

T T F T F T F T T F F T

A’ \iff A|A

(A \land B)’ \iff A|B

A \land B \iff (A|B)|(A|B)

Jan 22 2016

What does P(x,y) mean?

• Particular predicate

  • x > y \forall x,y \in Reals
  • Person x owns car y

• Any or all predicates

\exists ! x~P(x) There exists one and only one x with property P.

\exists ! x~(\forall y \in~Reals~ x+y=y) true

The following two mean the same:

• (\exists x~P(x)) \land (\forall u~\forall v~ P(u) \land P(v) \to u=v)
• \exists x~[P(x) \land (\forall y~P(y) \to x=y)]

Predicate WFF

x \lor y \exists is not WFF

\forall, \exists bind least

SCOPE OF QUANTIFIER

E.g. All parrots are ugly.

P(x) :~x is parrot
U(x) :~x is ugly

domain: parrots

\forall x~U(x)

domain: animals

\forall x~[P(x) \to U(x)]

There is an ugly lion.

L(x) :~x is lion

domain: lions

\exists x~U(x)

domain: animals

\exists x~[L(x) \land U(x)]

(\forall x~[P(x) \to Q(x)])’
\Leftrightarrow \exists x~[P(x) \to Q(x)]’
\Leftrightarrow \exists x~[P(x) \land Q’(x)]

Predicate WFF is VALID

if for (all domains, all interpretations of predicate as properties on domain) is always true

E.g.
(\forall x~[P(x) \land Q(x)]) \leftrightarrow (\forall x~P(x)) \land (\forall x~Q(x))

domain: integers

P(x) :~x is odd
Q(x) :~x is even

F \leftrightarrow (F \land F)

^ SINGLE INTERPRETATION

IGNORE THIS:

For all not integers, both are false, and (false and false) is false, so the WFF is VALID. (???)

E.g.
(\forall x~[P(x) \lor Q(x)]) \leftrightarrow (\forall x~P(x)) \lor (\forall x~Q(x))

domain: integers

P(x) :~x is odd
Q(x) :~x is even

T \leftrightarrow (F \lor F)

NOT VALID

\text{\S} 1.4 Predicate logic

[Propositional Logic + 4 new laws] :

• universal instantiation

  \forall x~P(x) infers P(c) where c is variable or a constant.

• existential instantiation

  \exists x~P(x) infers P(c) where c is a constant not used before.

• existential generalization

  P(c) infers \exists x~P(x)

• universal generalization

  P(x) infers \forall x~P(x) [WARNING: Does not always apply.]

Jan 25 2016

\text{\S} 1.5 Logic Programming

Many popular prog. languages are procedural (C++, Java).

Another language paradigm is descriptive/declarative/logical — You write WFFs and the computer makes inferences from them.

Prolog (LOGical PROgramming) is a typical logical programming language.

Prolog operates on a database of facts and rules. These things are essentially predicate WFFs. Behind this database is running program inference rules, which does the work of making the inferences.

Example

Objects

• bear
• fox
• pine tree
• grass
• fish
• …

Facts

• eat(deer, grass) [means deer eat grass]
• eat(bear, fish)
• eat(bear, fox)
• …

E.g. unary predicates

• animal(bear) \Rightarrow T
• animal(grass) \Rightarrow F
• plant(grass) \Rightarrow T
• plant(bear) \Rightarrow F

Queries (can use \land, \lor, ‘)

• IS (animal(bear)) \Rightarrow T
• WHICH (x : eat(x, grass)) \Rightarrow deer
• WHICH (x : eat(x, grass) \land animal(x)) \Rightarrow deer
• WHICH (x : eat(bear, x) \land mammal(x)) \Rightarrow fox

Inference Rule (RESOLUTION)

p \lor q and r \lor q’ infer p \lor r
i.e. (p \lor q) \land (r \lor q’) \to p \lor r

SPECIAL CASE

(0 \lor q)~and~(r \lor q’)~infer~0 \lor r
q~and~(r \lor q’)~infer~r
q~and~(q \to r)~infer~r

Another Example

p \lor q \lor t ~and~ r \lor q’ \lor s ~infer~ (p \lor t) \lor (r \lor s) (p \lor t) \lor q ~and~ (r \lor s) \lor q’

HORN CLAUSE

• many statements \lor‘d together
• at most one is NON-NEGATED

p YES p’ YES p \lor q NO p’ \lor q’ \lor r’ \lor t YES p’ \lor q’ YES p \to q \Leftrightarrow p’ \lor q YES

(p \to q) \land (q \to r) \to (p \to r) p’ \lor q ~and~ q’ \lor r ~infer~ p’ \lor r

PROLOG RULES

• eat(y,x) \land animal(x) \to prey(x) [Def. of prey added to database]

ACCORDING TO GERSTING: \forall y~\forall x~[eat(y,x) \land animal(x) \to prey(x)]
NOT GOOD: gives all as prey

CORRECT WAY: call the fewest # of animals “prey” so that still holds.

If 2 horn clauses allow resolution, the outcome is also horn clause.

p \lor q’ ~and~ z’ \lor r [Resolution does not apply.]

p \lor q’ \lor r’ ~and~ s’ \lor q \lor t’ [Resolution does apply.]
~infer~ p \lor r’ \lor s’ \lor t’

Output must be horn clause because all is \lor‘d and the one non-negated in the second WFF is removed by resolution.

eat(y,x) \land animal(x) \to prey(x)
into Horn clause:
[eat(y,x)]’ \lor [animal(x)]’ \lor prey(x)

E.g. y=bear, x=fish :

facts: eat(bear,fish); animal(fish)

How to match? Universal instantiation.

eat(bear,fish) \Rightarrow T

animal(fish) \to prey(fish)

Jan 27 2016

PROLOG RULE

animal(x) \land eat(y,x) \to prey(x) [Def-of prey — database works out preys.]

RECURSIVE RULES

y is in food-chain of x ~ IFCO(y,x)

if eat(x,y) then IFCO(y,x)
if IFCO(z,x) \land eat(z,y) then IFCO(y,x)

if eat(x,y) then IFCO(y,x)
if eat(x,z) \land IFCO(y,z) then IFCO(y,x)

if eat(x,y) then IFCO(y,x)
if IFCO(z,x) \land IFCO(y,z) then IFCO(y,x)

masculine(John)
feminine(Kathy)

P(x,y) x is parent of y

if masculine(a) \land P(a,x) \land P(x,b) then a is grandfather of b

A(x,y) x is ancestor of y

if P(x,y) then A(x,y)
if A(x,z) \land A(z,y) then A(x,y)

\text{\S} 1.6 PROOF OF PROGRAM CORRECTNESS

x input \to P program \to P[x] output

P program:

• s_1
• s_2
• s_3
• \vdots
• s_k

{Q} precondition \to s_i \to {R} postcondition

\langle {Q},s_i,{R} \rangle HOARE triple

• {Q}
• s_1
• {Q_1}
• s_2
• {Q_2}
• \vdots
• {Q_{k-1}}
• s_k
• {R}

proof correctness:

\forall x~[Q(x) \to R[x,P(x)]]

e.g. compute \sqrt{~}

Q(x):~x>0
P(x):~\sqrt{x}

\forall x~(x>0 \to (P(x))^2 =x)

Program correctness follows from:

• \langle {Q},s_1,{Q_1} \rangle
• \langle {Q_1},s_2,{Q_2} \rangle
• \vdots
• \langle {Q_{k-1}},s_k,{R} \rangle

Gersting says do these steps backward!

= Relation between 2 numbers (commutative, associative)

    x = y if and only if y = x

= Assignment of value

    x = y (set x to current value of y)

    y = x (set y to current value of x)
    

• {x > 2}
• x = x + 1
• {x > 3}

• {x = \pi}
• x = x + 1
• {x = \pi + 1}

\langle {Q_i},x=e,{Q_{i+1}} \rangle

valid if Q_i is Q_{i+1} with e substituded for x everywhere. (???)

Jan 29 2016

\text{\S} 1.6 Proof Correctness

• {Q_i} precondition
• x=e (assignment command)
• {Q_{i+1}} postcontition

\langle {Q_i}, x=e, {Q_{i+1}} \rangle

valid if substituting e to place of x in Q_{i+1} gives Q_i.

Code to interchange values of program variables x and y:

Goal

{x=a, y=b}

temp = x
x = y
y = temp
    

{x=b, y=a}

Checking

Go backwards

{x=b, y=a}

y = temp
    

{x=b, temp=a}

x = y
    

{y=b, temp=a}

temp = x
    

{y=b, x=a} \equiv {x=a, y=b}

VALID

Problems with the method

{x>0, y>0} \to {x+y>0}

z = x + y
    

{z>0}

Conditional rule

s_i:

If B

then P_1

else P_2

End If

\langle {Q}, s_i, {R} \rangle

VALID IF:

\langle {Q \land B}, P_1, {R} \rangle

AND

\langle {Q \land B’}, P_2, {R} \rangle

Example

{n=5}

if (n >= 0)
    then { y = 100 }
    else { y = n + 1 }
endif
    

{y=6}

\langle {n=5 \land n \ge 10}, y=100, {y=6} \rangle

{100=6} FALSE

This wouldn’t be executed anyway.

\langle {n=5 \land n<10}, y=n+1, {y=6} \rangle

{n+1=6} \equiv {n=5}

VALID

\text{\S} 2.1 Mathematical Proofs

mathematical objects

integers, reals, points, lines, etc.

Definitions, Axioms, Theorems

Definitions are about new words; Axioms are things that are supposed to be true; Theorems are things that follow from the definitions and the axioms (possibly through other theorems).

Theorem

Sum of rational and irrational numbers is irrational.

\forall x~\forall y~(x~rat. \land y~irr. \to x+y~irr.)

Proof by contradiction

P \to Q

(P \land Q’ \to 0) \to (P \to Q)

Assume that x is rat. and y is irr. and x+y is rat.

x = a / b,~a, b \ne 0~\in integers

x+y = c / d,~c, d \ne 0~\in integers

a/b + y = c/d

y = c/d - a/b = (b c - d a) / (b d)

(b c - d a) and (b d) are integers, and (b d) is nonzero, thus y must be rational. This is a contradiction. This proves

\forall x~\forall y~(x~rat. \land y~irr. \to x+y~irr.)

Definitions

Absolute value

x real

|x| = \{~ x if x \ge 0 ;~ -x if x < 0

Prime

n > 1 integer is prime if

\forall a,b~integers~(ab=n \to a=1 or a=n)

Composite

n > 1 integer that is not prime

Perfect Square

n is a perfect square if exists integer k such that n = k^2

Counterexample

E.g. All primes are odd. Counterexample: 2

E.g. All positive integers are are the sum of 3 perfect squares.

0 = 0^2 + 0^2 + 0^2

1 = 0^2 + 0^2 + 1^2

2 = 0^2 + 1^2 + 1^2

3 = 1^2 + 1^2 + 1^2

4 = 0^2 + 0^2 + 2^2

7 is a counterexample.

Conjecture

Statement not proved yet, nor counterexample is known.

E.g. Goldbach’s Conjecture:

Every even number at least 6 us a sum of 2 primes.

6 = 3 + 3

8 = 3 + 5

10 = 5 + 5

Exhaustive Proof

\forall x~P(x) Finite domain has elements x_1, x_2, …, x_n

check P(x_1) \land P(x_2) \land … \land P(x_n)

E.g. All odd integers between 4 and 8 are prime.

domain: 5,7

(5 is prime) \land (7 is prime)

\exists x~P(x) Finite domain has elements x_1, x_2, …, x_n

check P(x_1) \lor P(x_2) \lor … \lor P(x_n)

E.g. Between 15 and 24, there is a perfect square.

domain: 15,16,…,24

(15 is perf. sq.) \lor (16 is perf. sq.) \lor … \lor (24 is perf. sq.)

Proof by Cases

(P_1 \lor P_2 \lor … \lor P_n) \Leftrightarrow (P_1 \to q) \land (P_2 \to q) \land … \land (P_n \to q)

E.g. For pos. integer k, in decimal representation, the last digit k^2 is 0 or 1 or 4 or 5 or 6.

q: The last digit k^2 is 0 or 1 or 4 or 5 or 6. I am super sorry. I was not in class this day. I will, however, add some notes here on the topics covered.

Feb 08 2016

Theorem

\forall n \ge 0~\in integer~[3|2^{2n}-1]

Proof by induction on n.

n = 0 P(0) means 3|0, which is true.

Inductive step: need to show\forall n \ge 0~(3|2^{2n}-1 \to 3|2^{2(n+1)}-1)

2^{2(n+1)}-1 = 2^{2n+2}-1 = 2^{2n} \times 2^2 -1 = 4 \times 2^{2n} -1 = 4 \times 2^{2n} -4 +3

2^{2(n+1)}-1 = 4 \times 2^{2n}-1 = 4 \times 2^{2n} -4 +3

I am lost. I will finish this out when I understand it.

Consider an m \times m chessboard.

A domino can cover two squares. We want to cover the chessboard with dominos, i.e. cover all squares in one layer with no dominos “sticking out” of the chessboard.

Can we cover an m=7 chessboard? No; odd # of squares.

Can we cover an m=8 chessboard with two opposite corners removed? No —

Each domino must cover exactly one dark tile and exactly one light tile. By removing the two corners, we remove tow of the same color. Therefore, there is not a corresponding tile of the opposite color for each tile, and the board cannot be covered.

Theorem

\forall n \ge 1~ 2^n \times 2^n chessboard minus a field has a domino cover — call this P(n).

Isn’t this false? I guess let’s just go with it…

Proof by induction

Inductive step: \forall n \ge 1~ P(n) \to P(n+1)

Consider a 2^{n+1} \times 2^{n+1} chessboard with a field removed.

We somehow have a three-space domino… This makes no damn sense… But sure.

Somehow proof! Bad example, I say!

I’ll add better examples at some point.

P(1) \land [\forall n \ge 1~ P(n) \to P(n+1)]~\to~(\forall n \ge 1~ P(n))

P(1) \land [\forall n \ge 1~ P(1) \land P(2) \land … \land P(n) \to P(n+1)]~\to~(\forall n \ge 1~ P(n))

Theorem

Only \$3 and \$4 coins.

\forall n \ge 6 \$n can be paid exactly — P(n)

Base case: P(6): 6 = 3 + 3

Inductive step: ??? — this is what it is:

P(7): 7 = 3 + 4
P(8): 8 = 4 + 4
P(n): n = (n-2) + 3

Finally, one that makes sense!

Apparently we can also do this with the first form… Practical!

Actually, I bet this will be making a flat algorithm, which is actually kinda cool. I hope that’s what this is.

Base case: P(6)

Inductive step: —

n = 3 + 3 + … + 4 + 4
n+1 = 3 + … + 4 + 4 + 4

n = 4 + 4 + … + 4 + 4 n+1 = 3 + 3 + 3 + … 4 + 4

Ah. Just a different kind of branching.

Feb 10 2016

Theorem

\forall n \ge 2~ \text{integer} n \text{can be written as a product of primes}

Proof by 2nd principle of induction:

Base case: P(2): 2 is prime

Inductive step: to show that \forall n \ge 2~ P(2) \land P(3) \land … \land P(n) \to P(n+1)

Consider n+1. Cases:

• n+1 is prime

• not: n+1 = a \times b

1 < a,b < n+1 \text{infers} 2 \le a,b \le n

P(a) and P(b) are part of hypothesis.

a = p_1 \times p_2 \times … \times p_i

b = q_1 \times q_2 \times … \times p_i

n+1 = a \times b = p_1 \times p_2 \times … \times p_k \times q_1 \times q_2 \times … \times q_l

Pitfalls

Bad base cases can propogate errors.

Harmonic numbers

H_n = {1 \over 1} + {1 \over 2} + {1 \over 3} + … + {1 \over n}

Theorem

\forall n \ge 1~ H_{2^n} \ge 1 + {n \over 2}

We’re goin’ to Alaska!

Proof

P(1):~ H_2 \ge 1 + {1 \over 2}

\forall n \ge 1~ P(n) \to P(n+1)

P(n+1):~ H_{2^{n+1}} \ge 1 + {n+1 \over 2}

H_{2^{n+1}} = (1 + 1/2 + 1/3 + … + 1/(2^n))+(1/(2^n +1) + … + 1/(2^{n+1}))

Alaska!

Recall de Morgan

Let’s generalize!

It is a math class, after all.

\forall n \ge 2~ (P_1 \lor P_2 \lor … \lor P_n)’ \Leftrightarrow {P_1}’ \land {P_2}’ \land … \land {P_n}’

Q(2):~ (P_1 \lor P_2)’ \Leftrightarrow {P_1}’ \land {P_2}’

P(n+1):~ (P_1 \lor P_2 \lor … \lor P_n \lor P_{n+1})’ \Leftrightarrow ((P_1 \lor P_2 \lor … \lor P_n) \lor P_{n+1})’ \Leftrightarrow (P_1 \lor P_2 \lor … \lor P_n)’ \land P_{n+1}’ \Leftrightarrow Q(n) \land {P_{n+1}}’ \Leftrightarrow {P_1}’ \land {P_2}’ \land … \land {P_n}’ \land {P_{n+1}}’

Description by characters

H = those positive integers that can be defined in English with at most 200 characters

We can define the smallest positive integer not in H as “the smallest positive integer that cannot be defined in English with at most 200 characters.” But wait! We just defined it in less than 200 characters!

Feb 15 2016

Test goes up to induction (\text{\S} 2.2).

Domination

A \lor 1 \Leftrightarrow 1
A \land 0 \Leftrightarrow 0

Backus-Naur Normal Form

BNNF is actually really cool. You can check out more about its extended form EBNF on Wikipedia

Example:

<letter>    ::= A|B|C|...|Z
<digit>     ::= 0|1|2|3|4|5|6|7|8|9
<identifier>::= <letter>|<identifier><letter>|<identifier><digit>
    

Palindromes

<letter>    ::= A|B|C|...|Z
<palindrome>::= <letter>|λ|<A><palindrome><A>|<B><palindrome><B>
              |...|<Z><palindrome><Z>
    

λ is the empty string.

Words with no consecutive vowels

<letter>    ::= A|B|C|...|Z
<vowel>     ::= A|E|I|O|U
<consonant> ::= B|C|D|...|Z
<word>      ::= <letter>|λ|<word><consonant>
              |<word><consonant><vowel>
    

Show:

• Word does not have 2 consecutive vowels.

  • <letter> \checkmark
  • λ \checkmark
  • <word><cons> \checkmark
  • <word><cons><vowel> \checkmark

• If word without 2 cons. vowels, is valid <word>.

  • Last Letter

    • Empty String \checkmark

    • Consonant

      • Length 1 word \checkmark
      • More length \checkmark

    • Vowel

      • Length 1 word \checkmark
      • A consonant before \checkmark

A_1 \lor A_2 \lor … \lor A_n does not depend on parenthesation.

Recursive definition

A_1 \lor A_2 by truth table.

n \ge 2~ A_1 \lor A_2 \lor … \lor A_{n+1} def (A_1 \lor A_2 \lor … \lor A_n) \lor A_{n+1}

Theorem: definition is the same for all parenthesation for n items

By hypothesis (…) \lor A_{n+1} = \text{same}.

(A_1 \lor … \lor A_k) \lor (A_{k+1} \lor … \lor A_{n+1})

(A_1 \lor … \lor A_k) \lor (A_{k+1} \lor (A_{k+2}\lor …\lor A_{n+1}))

P \lor (Q \lor R) \Leftrightarrow (P \lor Q) \lor R

((A_1 \lor … \lor A_k) \lor A_{k+1}) \lor (A_{k+2}\lor …\lor A_{n+1})

This means we can move any parenthesation.

61

n straight lines, no 2 parallel, no 3 through a point

cut the plane into (n^2 + n +2)/2 pieces

P(1): (1^2 + 1 + 2)/2 = 2

Assume n+1 lines, n black, 1 red.

Black lines make (n^2 + n +2)/2 pieces.

Does adding in the red line make there be ((n+1)^2 + n+1 +2)/2?

Adding red line adds n intersection points (no parallel).

This adds n+1 pieces.

(n^2 + n +2)/2 + n+1 = ((n+1)^2 + n+1 +2)/2

I spent my time getting this working, so I can’t cover #74… Sorry. My laptop is dead. It has to do with arithmetic progression:

\Sigma = a + (a+b) + … + (a+(n-1)b)

\Sigma = (a+(n-1)b) + (a+(n-2)b) + … + a

2\Sigma = n(2a+nb)

\Sigma = n(2a+nb)/2

\text{\S} 2.4: Recursive algorithms

L list of numbers

Find the biggest item.

There is a simple non-recursive algorithm.

def find_max(L):
    u = float('-Infinity')
    i = 0
    while i < n:
        u = max(u, L[i])
        i = i + 1
    return u
    

Recursive algorithm:

def find_max(L):
    if len(L) == 1:
        return L[0]
    else:
        Lp = L[1:]
        return max(L[0], find_max(Lp))
    

Sorting

Bubble sort

Iterative:

def bubble_sort(L):
    for i in range(len(L)-1):
        if L[i] > L[i+1]:
            tmp = L[i]
            L[i] = L[i+1]
            L[i+1] = tmp
    

Merge sort

Recursive:

def merge_sort(L):
    if len(L):
        I will fill this out later
    

Binary search

The example is in the book. I cannot type this fastvon my phone

\text{\S} 2.3 Correction of Loops

[Q]

while B holds
    P
end
    

[R]

i counts the loops

[Q_0]: i=0

P

[Q_1]

P

[Q_2]

\vdots

Q_r \land B Sorry about that. I hadn’t eaten yet today.

Pre-Test Review

6

\exists x~ P(x) \to \forall x~ P(x)

Show that this is not valid.

We need a domain and a meaning for P(x).

Domain: integers

P(x):~ x \ge 0

\exists x~ P(x): true (example: x=5)

\forall x~ P(x): false (counterexample: x=-1)

8. Going backwards.

   {A1=c,A2=a,A3=b}

   A2=temp
       

   {A1=c,temp=a,A3=b}

   A3=A2
       

   {A1=c,temp=a,A2=b}

   A1=A3
       

   {A3=c,temp=a,A2=b}

   temp=A1
       

   {A3=c,A1=a,A2=b} \equiv {A1=a,A2=b,A3=c}

9. \forall n\in\mathbb{N}^\ast~[2+7+12+…+(5n+2)=2+2n^2+4n+{n^2+n \over 2}]

   P(n):~2+7+12+…+(5n+2)=2+2n^2+4n+{n^2+n \over 2}

   P(1):~2+7=2+2(1)^2+4(1)+{1^2+1 \over 2}=2+2+4+1=2+7

   P(n+1):~2+7+…+(5n+2)+(5(n+1)+2)=2+2(n+1)^2+4(n+1)+{(n+1)^2+n+1 \over 2}