Notes

Notes, etc. of Samuel Flint

CSCE 235: Discrete Mathematics

Lecture 1

Life is Beautiful (if you know where to look). Life is Beautiful because we can think. Discrete Mathematics is about mathematical thinking.

Types of thinking

Logical

Formal Logic and proogs

Relational

Sets, relations, functions graphs

Analytical

Algorithms and complexity analysis

Recursive

recurrence relations and induction

Quantitative

Combinatorics!! (Time to break out TAOCP 4.)

Teaching Method

  • High-Level

  • Starting with life, people and such.

  • Processes

  • Understanding

  • Reasoning

  • Solving the problems

  • Philosophy

  • History

  • Anecdotes

  • Poetry

  • Arts and Artists

  • Sciences and Scientists

What and Why?

What?

  • Discrete versus Continuous.

    • Continuous operates on an infinite range. (analog clocks, stringed instruments)

    • Discrete operates on a specific, finite and well-defined range. (digital clock, piano)

  • Discrete Objects are countable

    • Integers

    • Rational Numbers

    • Eggs

    • Map

  • Discrete structures are abstract mathematical structures for representing discrete objects and the relationships between them.

    • Sets

    • Relations

    • Functions

    • Graphs

    • Trees

    • Finite State Machines

  • Discrete mathematics is tthe study of discrete structures.

Discrrete Vs Continuous

  • Continuous

    • Infinitely many points between two points (Real Numbers)

  • Discrete

    • Only a finite set of numbers between to points

Why?

  • Great intellects are skeptical – Friedrich Nietzche

  • The Answer:

    • Given a right triangle, a = 3, b = 4, find c.

    • c = 5.

    • $a^2 + b^2 = c^2$

    • But Why?

      • It must be proven all cases to be considered useful in general.

        • This is done using a formal approach.

        • Discrete mathematics is the foundation for this formal approach.

  • What is Truth? This includes persuasion, the purpose of proofs.

  • How not to be wrong! (Jordan Ellenberg's book)

  • Everyday Life

    • Social Networks

      • Who is most popular?

      • Who is posting most on your timeline?

      • Who is the most introverted?

      • This can be done using graph algorithms.

Our Goal

Learn a set of mathematical facts and how to apply them.

  • Understanding mathemitcal reasoning

  • Combinatorics, counting problems and algorithmic analysis

  • Discrete structures

  • Algorithmic thinking

  • Applications and Modeling

In CS

  • Networking

    • Number of routse

    • Shortest-path Problems

    • Longest Path

    • Koningsberg

    • Traveling Salesmen

    • Dining Generals

  • Sorting

  • Social Networking

  • Web Searching

  • Analyzing algorithms

  • Cryptographic protocols.

Adminsistrative stuff

  • Check Blackboard, especially the schedule.

  • Book of proof http://www.people.vcu.edu/~rhammack/BookOfProof/ (consider buying)

  • Look at secture slides

  • Recitation classes

  • Pop quizes in both recitation and lecture

  • No makeup quizes

  • 7-8 homework assignments

    • Make sure to be legible.

    • Don't uses tear out pages

    • Use A4/Letter

    • Use LaTeX for bonus points.

  • One late pass, not including last assignment.

  • Strict in-class due date.

Email

  • Don't use Blackboard!

  • Use UNL email address.

  • Be courteous.

  • State course code and state the subject.

  • Include name and NUID.

Lecture 2

Mathematical Thinking

  • 5 types of thinking

  • Logical

  • Relational

  • Analytical

  • Recursive

  • Quantitative

Automated Reasoning

  • Relies on the ability to state things precisely.

  • Every word is taken seriously, and everything is important.

  • There is a clear, unambiguous message.

Why is this important?

  • We deal in ambiguity, but a computer is exacting.

  • Precision is paramount.

  • The ability to reduce a statement in human language to a symbolic language or technical notation is at the core of what we do.

  • This is a form of mathematics, discrete mathematics, which provide symbolic manipulations.

  • This is the formal approach to logic. Using this helps us to avoid errors in logic.

Logic!

  • Specifying precise meanings of statements.

  • Logic is the set of rules used to distinguish between validity and invalidity.

  • Allows us to construct correct mathematical argument(s).

  • Allows us to deduce new information.

  • Used to build circuits

  • Define algorithms

  • Model Problems

  • Manipulate Statements

  • Find truth and convince others.

  • Used to verify algorithms and security. This will include AI.

Questions

  • Tools?

  • Proving methods?

  • Strategies?

The Start

  • Take natural language requirements and produce precise, unambiguous specifications in the case of a specification. This should be consistent.

  • Translation from english to logic.

    • Write simple statements

    • Combine simple statements into compound statements.

  • Statements are either true or false, delarative. They are represented by a lowercase latin letter. There must be no free variables. They should not be self-referential.

  • Fermat's Last Theorem states: For all natural numbers $a$, $b$, $c$, $n$ where $n > 2$, it is the case that $a^n + b^n \neq c^n$. This was proved in 1993.

  • Goldbach Conjecture states: Every integer greater than 2 is the sum of two prime numbers. This has yet to be proven.

  • An Exercise:

    • If Aaron is late, the Bill is late, and if both Aaron and Bill are late, then class is boring. Suppose that class is not boring. What can you conclude about Aaron?

    • p: Aaron is late.

    • q: Bill is late

    • r: Class is boring.

  • This is the Propositional Calculus, which is the study of the logical relationship between propositions and forms the basis of all mathematical reasoning.

    • sentential logic

    • statement logic

    • developed by Aristotle

    • This allows us to make deductions formally

    • Allows us to manipulate formulae symbolically

    • We start with obvious and previous statements to deduce more complex statements.

  • Simplest propositions are considered individual units.

  • These simple propositions are used to produce more complex propositions.

  • We use the following operators

    Operator Symbol Gates
    Negation $\neg$ overline
    And (conjunction) $\wedge$ $\cdot$
    Or (disjunction) $\vee$ $+$
    Exclusive Or (connection) $\oplus$
    Implication $\to$
    If and Only If $\leftrightarrow$
    Operators Table

Lecture 3

Announcements

Homework has been posted and is due September 7th. 5 points bonus for using \LaTeX.

Implications

  • These are conditional statements..

  • A Conditional is a promise. If $p$ is true, then $q$ will be true, otherwise I make no claim.

  • They default to true.

  • If the hypothesis is true, and the conclusion is false, then the answer is false.

  • When the hypothesis is false, the entire proposition is true.

  • if then, implies, only-if q if p, q follows from p, p is a sufficient condition for q, q is a necessary ccondition for p.

  • p is not necessary, put q is necessary.

  • Necessary condition: To get an A in this clas, you must get more than 93 on the final.

  • Sufficient condition: Getting an A on every piece of graded work.

  • You miss an A, but your average is an A. You get an A.

  • If you pass the final exam, then you will pass the course.

    • passing the exam is the sufficient condition

    • passing the course is the necessary condition

  • Given

    p

    grizzly bears have been seen in the area

    q

    Hiking is safe on the trail

    r

    berries are ripe along the trail.

    ?

    $q \to \neg r$ (it is necessary for berries to not be ripe to be safe to hike)

    ?

    $\neg r \to q$ (it is sufficient that berries not be ripe to be safe)

    ?

    $\neg\left[\neg r \to q\right]$ (it is not sufficient for berries to be ripe to be safe)

    ?

    $q \to \neg \left[p \wedge r\right]$ (necessary but not sufficient that berries not be ripe and grizzly bears not be seen to be safe)

  • Biconditionals

    • p and q must both have the same truth value.

    • p : a is divisible by two. q: a is even. $p \to q$, $q \to p$ $\therefore$ $p \leftrightarrow q$

    • Only look at the truth value.

    • p if and only if q

    • p is necessary and sufficient for q

    • if p then q and conversely

    • p iff q

  • Converse, contrapositive and inverse

    • given $p \to q$

    • $q \to p$ is the converse

    • $\neg q \to \neg p$ is the contrapositive

    • $\neg p \to \neg q$ is the inverse

Showing relations between individual and compound propositions (truth tables)

p q p and q p or q p xor q
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0
  • Ordering is important

    1. negation

    2. conjunction

    3. disjunction

    4. implication

    5. biconjunction

  • use parenthesis for clarity

  • these can be used on bit strings

  • specifications can be written in the propositional calculus

  • if the file system is full, the automated reply cannot be sent.

    p

    the automated reply can be sent

    q

    the file system is full

    $\neg p$

    the automated reply cannot be sent

    $q \to \neg p$

    if the filesystem is full, the automated reply cannot be sent.

  • Given:

    • p the diagnostic message is stored in the buffer

    • q the diagnostic message is retransmited

    • The diagnostic message is stored in the buffer or it is retransmitted. ($p \vee q$)

    • The diagnostic message is not stored in the buffer. ($\neg p$)

    • If the diagnostic message is stored in the buffer, then it is retransmitted. ($p \to q$)

    • This is true if p is false and q is true, thus, the specification is consistent.

Lecture 4: Logical Equivalence

  • Compound propositions are extremely powerful

  • remember to be careful about how a logical test is written

  • remember that equivalence can be used for better readability.

  • equavalence $p \equiv q$ sometimes $p \Leftrightarrow q$

  • are $p \to q$ and $\neg p \lor q$ equivalent?

    • yes, $p \to q \equiv \neg p \lor q$

    • use a truth table to show this.

  • Laws:

    Implication

    $p \to \equiv \neg p \lor q$

    Equivalence A

    $p \leftrightarrow q \equiv (p \to q) \land (q \to q)$

    Equivalence B

    $p \oplus q \equiv (\neg p \land q) \lor (p \land \neg q)$

    De Morgan's Law

    $\neg\left(p \lor q\right) \equiv \left(\neg p \lor \neg q\right)$, and the same holds for $\land$

  • Tautologies

    Tautology

    $p \land \neg p$

    Contradiction

    $p \lor \neg p$

    Contigency

    $p \lor q$

  • Equivalence:

    • Show $p \lor (q \land r)$ and $(p \lor q) \land (p \lor r)$

    • This can be done using logical equivalences instead of truth tables.

    • These form a rewrite system.

    • $(p \land q) \to q \equiv \mathrm{True}$

    • $(p \to q) \equiv \neg p \land q$; $\equiv \neg (p \land q) \lor q$ (implication)

    • $\equiv \neg p \lor (\neg q \lor q)$ (demorgans)

    • $\equiv \neg p \lor \mathrm{True}$ (tautology)

    • $\equiv \mathrm{True}\hfill\blacksquare$

  • Try: $\neg \left(q \to p\right) \lor \left(p \and q\right) \equiv q$

    • $\neg\left(\neg q \lor p\right) \lor \left(p \land q\right)$ (implication)

    • $\left[\neg \left(\neg q\right) \land \neg p\right] \lor \left(p \land q\right)$ (demorgans)

    • $\left(q \land \neg p\right) \lor \left(q \lor p\right)$

    • $q \land \left(\neg p \lor p\right)$

    • $q \land \mathrm{True}$ (tautology)

    • $q \hfill\blacksquare$

  • Given $(p \lor \neg q) \land (\neg p \lor q) \land (\neg p \lor \neg q)$

    • Is the problem satisfiable

    • This can be done with truth tables and rewriting.

    • This can also be done using logical reasoning (formal technique).

    • $p$ and $q$ must both be false for this propsition to be true.

    • Satisfiability is useful for a variety of applications:

      • robotics

      • testing

      • CAD

      • machine vision

      • IC design

      • networking

      • genetics

      • logic puzzles.

Recitation 2

  • The TA hates prolog. Shame on him.

  • Mind the difference between inclusive and exclusive or.

  • Don't forget bitwise ops.

  • Make sure to be careful when trying to convert from the propositional calculus to english.

Lecture 5

Goal of the course

  • build formal systems to solve logic problems

  • Buliding a tool box

    • not

    • and

    • or

    • exclusive or

    • implication/conditionals

    • biconditionals (iff)

Extending the toolbox

  • compound propositions

  • determining relationships between two compound propositions

  • now we learn to desconstruct relationships

  • limitations:

    • knowing whether something is true or false if it's a variable.

    • unable to form propositions from things like "x is greater than 1"

    • unable to express certain types of equivalence, especially when quantifiers are involved.

    • not powerful enough to represent all types of assertions that are used in computer science and mathematics.

    • We need something more powerful, enter the Predicate Calculus

The Predicate Calculus

predicates

a statement that depends onn one or more variables. describes a property.

  • able to make propositions from predicate logic. This is done systematically.

  • x > 3; x =

  • P(x) = x > 3; upon assigning a variable to x, P(x) becomes a proposition

  • a propositional function is a function that takes one or more arguments and expresses a proposition when vvalues are given to the arguments.

  • P is the predicate, x is the variable

  • let Q(x,y,z) denote the statement $x^2 + y^2 = z^2$

    • this only holds when the values end up correct (3,4,5) but not (2,2,3)

  • The universe of discourse is the set of all things that we wish to talk about, all object that we can sensibly assign a variable.

quantifiers

Specify a grouping of values

$\forall$ – the Universal quantifier

Everything, ever.

  • $\forall xP(x)$ – $\forall xP(x) \iff P(n_1) \land P(n_2)\land\cdots\land P(n_k)$

  • for all

  • for every

  • all of

  • for each

  • given any

  • for arbitrary

  • for any

  • Example

    • $P(x)$ – "x is a CS student"

    • $Q(x)$ – "x must take a discrete math course"

    • Where $x$ is a UNL student.

    • $\forall x(P(x) \to Q(x))$

  • Example

    • $P(x)$ – "$x$ is a computer science student"

    • $Q(x)$ – "$x$ must take a discrete math course"

  • Example:

    • For every x and every y, x+y > 10

    • $P(x,y) = x + y > 10$

    • where $x\in \mathbb{Z}$ and $y\in \mathbb{Z}$

    • $\forall x \forall y P(x,y)$ or $\forall x,yP(x,y)$

$\exists$ – the Existential quantifier

there exists$\ldots$, such that$\ldots$

  • Points to very few objects within a domain.

  • $\exists xP(x)$ – $\exists x P(x) \iff P(n_1) \lor P(n_2) \lor\cdots\lor P(n_k)$

  • There exists

  • for some

  • there is at least one

  • there is

  • there is exactly one

Lecture 6

Equivalence

  • p and T == p

  • p or F == p

  • p or T == T

  • p and F == F

  • p or p == p

  • p and p == p

  • not (not p) == p

  • p or q == q or p

  • p and q == q and p

  • (p or q) or r == p or (q or r)

  • (p and q) and r == p and (q and r)

  • p or (q and r) == (p or q) and (p or r)

  • demorgan's copies not over all within the or or and

  • p or (p and q) == p

  • p and (p or q) == p

  • p or not p == T

  • p and not p == F

Quantifiers and the predicate calculus

  • EX:

    • Every student in the class is sleeping

    • There is no student in the class

    • True.

  • If the domain is empty:

    • $\exists xP(x)$ is always false

    • $\forall xP(x)$ is always true

      • this is vacuously true

  • Quantifiers can be mixed:

    • $\exists x\forall yP(x,y) \not\equiv \forall y\exists xP(x,y)$

    • P(x) = x+y = 0

    • $\forall x\exists yP(x,y)$ is correct

    • $\exists y \forall x P(x,Y)$ is not

  • Ex:

    • There exists an x not being 0, and a Y such that xy=1

    • $P(x,y) \gets xy = 1$

    • $\forall x(x\neq0\to\exists yP(x,y))$

  • Ex:

    • Every student has at least one partner

    • S(x,y) student x has partner y

    • $\forall x\exists y (S(x,y))$

  • Ex:

    • Every student has at least one partner

    • S(x,y) student x has partner y

    • $\forall x\exists y\left[S(x,y)\land\forall z(z\neq y)\to\neg S(x,z)\right]$

  • Negation can be done on quantified expressions:

    • let P(x) be a predicate, then the following hold

      • $\neg \forall x P(x) \equiv \exists x \not P(x)$

      • $\neg \exists x P(x) \equiv \forall x \neg P(x)$

      • This is deMorgan's Lemma

  • Ex:

    • There exists a number x such that when added to any number, the result is that number and if it is multiplied by any number, the result is x.

    • $P(x,y) \gets x + y = y$

    • $Q(x,y) \gets xy = x$

    • then: $\exists x\forall y(P(x,y)\land Q(x,y))$

    • This holds over all but the following sets of numbers:

      • Counting

      • irrational numbers

      • positive integers alone

  • Ex:

  • There are at least two paths connecting every two distinct end points.

    • $P(p, x,y) \gets $ p is a path that connects x and y

    • $\forall x \forall y \left[(x\neq y)\to \exists p \exists q((p\neq q) \land P(p,x,y) \land P(q,x,y))$

Lecture 7: Proof techniques

  • the search for absolute knowledge can bring peace (not really)

  • how do we acquire absolute knowledge?

  • mathematical proofs are the only truly absolute knowledge

  • this provides a guarentee

  • proofs are like diamonds, hard and clear, and will be touched with nothing but strict reasoning. – locke

  • proving the most obvious things in the least obvious way – polya

  • though this be madness, yet ther is a method in it – hamlet

in CS

  • to prove an algorithm is correct

  • to prove efficient

  • to prove better than previous things

What is a mathematical proof

  • valid arguments that establish the trut of mathematical statements

  • an argument is a sequence of statements that end with a conclusion

  • a valid argument is a n argument that follows from the truth of the preceding statements or the premises of the argument

  • fallacies or incorrect reasoning lead to invalid arguments

  • determining argument validity:

    • a valid argument is always true (tautological)

    • ex

      • p: it snows today

      • q: the class is cancelled

      • $p\to q$

      • $p$

      • $\therefore q$

      • valid argument because when any premise is true, the conclusion must also be true.

  • Truth tables can be used (this can be very inefficient)

  • Rules of inference can be used as building blocks. (see table 1 in chapter 1.6/7)

    modus ponens (mode that affirms)

    if $p\to q$ and p are true, q must be true

    modus tollens

    $p\to q$ and $\lnot q$ are true, then $\lnot p$ must be true

    • $p\to q$ and $\lnot p$ are true, q does not necessarily follow (invalid argument)

    contrapositive

    if $p\to q$ is true, the $\lnot q\to\lnot p$ is also true

    conjunction

    if p is true and q is true, then $p\land q$ will be true

    addition

    if p is true the $p\lor q$ must be true

    simplification

    if $p\land q$ is true, then p must be true

    syllogism

    a deductive inference of two premises and a conclusion.

    hypothetical syllogism

    $((p\to q)\lor(q\to r))\to (p\to r)$ transitive

    disjunctive syllogism

    $((p\lor q)\and \lnot p)\to q$ (be careful with this one)

    resolution

    $((p\lor q)\land(\lnot p\lor r))\to(q\lor r)$

  • Example:

    • assume

      • $p\to q$

      • $r\to s$

      • $r\lor p$

      • $q\equiv false$

    • Show that s is true

      • $p\to q$ , $\lnot q$ ; $\therefore\lnot p$ (modus tollens)

      • $r\lor p$ , $\lnot p$ ; $\therefore r$ (disjunctive syllogism)

      • $r\to s$ , $r$ ; $\therefore s\quad\blacksquare$ (modus ponens)

  • Fallacies

    • fallacy of affirming the conclusion

      • p it snows today

      • q class is cancelled

      • $p\to q$ if it snows, class is cancelled

      • is it thus that p will always be true if $p\to q$ is true?

      • no, can be shown by a truth table.

      • reversed version of modus tollens

    • fallacy of denying the hypothesis

      • p it snows today

      • q the class is cancelled

      • $p\to q$

      • given $\lnot p$ and $p\to q$ as both true, is $\lnot q$ true?

      • no

    • circular reasoning

      • use the conclusion as an assumption or a premise avoiding an actual proof

    • see Plato's The Republic

    • "Justice is what is good for the stronger." – Thrasymachus

    • "Sophistry is only fit to make men more conceited in their ignorance." – John Locke

    • sometimes it's a bad operation rather than bad logic

  • Proofs with quantifiers:

    • rules can be extended to quantified statements

    • quantified statements must be transformed so that the first talk about an object from the domain.

    • universal instantiation

      • all students of 235 are genius

      • Turing is a student of 235

      • therefore Turing is a genius.

    • universal generalization

      • let Turing be from 235

      • Turing is a genius

      • therefore all students of CSCE is a genius

    • existential instantiation

      • there exists in 235 an extraordinary genius

      • that student is Turing

      • Turing is an extra-ordinary genius

    • existential generalization

      • Turing is an extra-ordinary genius of 235

      • therefore there exists a student in 235 that is an extra-ordinary genius

Lecture 8

  • the rules of inference:

    • work through them

    • learn them

    • become one with them

    • provides templates for constructing valid arguments

  • Example:

    • show that the premise a care in this garage has an engine problem andd every care in this garage has been sold imply the conclusion a car wchich has been sold has an engine problem.

    • $G(x)$ x is in this garage

    • E(x) x has an engine problem

    • S(x) x has been sold

    • $\exists x(G(x)\land E(x))$

    • $\forall x(G(x)\to S(x))$

    • $\forall x(S(x)\land E(x))$

    • Existential Instantiation: $G(c)\land E(c)$ : G(C) and E(c) are thus true by simplification

    • Universal Instantiation: $G(c)\to S(c)$ : by modus ponens, this is show no be true. and $S(c)$ is true

    • By E(c) and S(c) being true, by the rule of conjunction, $S(c)\land E(c)$ are true.

    • Therefore, by Existential Generalization: $\exists x\left[S(x)\land E(x)\right]\quad\blacksquare$

  • Remember to work carefully and consistently.

  • Example:

    • Every Resident has a birth certificate

    • Turing does not have a birth certificate

    • Feinman has a birth certificate

    • R(x) x is a resident

    • B(x) x has a birth certificate

    • $\forall x\left[R(x)\to B(x)\right]$

    • $\lnot B(t)$ Turing does not have a birth certificate.

    • Use Universal instantiation

    • $R(t)\to B(t)$

    • $\lnot B(t)$

    • $\lnot R(t)$ by modus tollens

    • $R(f) \to B(f)$

    • $B(f)$

    • No conclusion can be drawn.

  • A theorem is a statement that can be shown to be true using a proof

  • a proof is a sequence of statements that form a valid argument

  • axiom is true on self-evidence

  • lemma and corollaries are types of theromes

  • a proposition is a fact for which there is no proof

  • a conjecture is a statement whose truth value is unknown.

  • A proof should be absolutely convincing.

  • use definitions to avoid ambiguity

  • defs must be exact and unambiguous. They must be agreed apon by all

  • defs

    even integer

    n = 2a

    odd integer

    n = 2a + 1

    rational number

    r = $\frac{p}{q}$ where $q\neq 0$

    irrational number

    a real number that is not rational

  • Therome conditional form:

    • biconditionals

    • theorems about specific things

  • Proofs often involve many intermediate steps

  • each step must be justified

  • types:

    • direct

      • Simple way of proving theromes that are in the form of conditionas.

      • assume p, and then show that p forces q.

      • EX: prove that if x is odd then x^2 is also odd.

        • Assume that X is an odd integer

        • For any integer a, x = 2 a + 1

        • Then x^2 = (2a + 1)^2

        • = 4a^2 + 4a + 1

        • = 2(2a^2 + 2a) + 1

        • 2a^2 + 2a = integer

        • 2(integer) + 1

        • thus odd.

      • EX: if x and Y are positive real numbers, then $2\sqrt{xy} \leq x + y$

        • work backwards and get $0 \le (x-y)^2$

        • then follow from there.

      • this can be limited.

        • prove that if n is int and 3n+2 is odd, then n is odd

        • sometimes you have to reformulate your problem statement

    • trivial

      • often form the base case of a proof

      • not necesarrily easy, but given when the conclusion is shown to always be true without using the hypothesis.

      • these hold without the hypothesis

    • vacuous

      • if the premise is false (p) then the implication ($p\to q$) is trivially true.

      • this will be used in set theory

    • by contrapositivve

    • contradiction

    • cases

    • equivalence proofs

    • existence proofs

    • uniqueness proofs

Lecture 9

  • Homework:

    • I(x): X is an insect

    • L(x): X has six legs

    • $\forall x\left[I(x)\to L(x)\right]$

    • I(Dragonfly)

    • Use universal instantiation: $I(Dragonfly)\to L(Dragonfly)$

    • L(Dragonfly) (by modus ponens)

    • Make sure to use the rules of inference, and be careful about their use.

More methods of proving: Beyond the direct proof

  • Direct Proof can often get stuck on definitions of things.

  • This can include very simple problems.

  • Instead, prove the contrapositive: if n is not odd, then 3n + 2 is not odd.

    • then n = 2k, for some integer k

    • 3n + 2 = 3(2k) + 2 = 6 k + 2 = 2(3k + 1)

    • 3n + 2 is even

    • therefore if n is even, then 3n + 2 is even.

  • Indirect

    • $p\to q \equiv \lnot q \to \lnot p$

    • This is the contrapositive

    • Prove that if $x^2$ is even then $x$ is even.

      • By indirect proof:

      • Suppose $x$ is not even.

      • $x$ thereforre is odd, and is of the form $x = 2k + 1$ where $k$ is an integer.

      • $x^2 = (2k + 1)^2$

      • $x^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$

      • Consequently $x^2$ is not even.

      • Therefore $x^2$ is odd.

    • Prove that if $x^3$ is irrational, the $x$ is irrational.

      • Using the indirect proof:

        • If $x$ is not irrational, then $x^3$ is not irrational.

        • $x$ is, therefore rational.

        • $x = \frac{p}{q}$ where $(p,q)\in \mathbb{Z}$ and $q\neq 0$.

        • $x^3 = \frac{p^3}{q^3} = \frac{m}{n}$ where $m = p^3$, $n = q^3$, $(m,n)\in\mathbb{Z}$ and $n \neq 0$

        • $x^3$ is rational.

        • $x^3$ is thusly not irrational.

Proving statements that are not conditional

  • Statements that assert facts.

  • Proof by contradiction can be used to prove conditional statements as well as any other kind of statement.

    • Assume the sttatement we want to prove is false.

    • then show that this assumption leads to nonsense (a contradiction).

  • Contradiction: A compound statement that is always false.

    • $p\land\lnot p$ is a contradiction

    • $p\lor\lnot p$ is a tautology

  • Prove P is true, we assume that it is false.

  • Show that $C\land\lnot C$ is true.

  • By virtue of this being contradictory, P is true.

  • $\lnot P\to (C\land\lnot C) \equiv P\lor(C\land\lnot C)$, thus $P$ is true.

  • Proof by Contradiction was used by Hippasus of Metapontum

  • Show that $\sqrt{2}$ is Irrational:

    • By Contradiction:

    • Assume that $\sqrt{2}$ is irrational.

    • $\sqrt{2} = \frac{p}{q}$ where $p$ and $q$ are integers and $q\neq0$. And $\frac{p}{q}$ is in lowest form.

    • $2 = \frac{p^2}{q^2}$, $p^2 = 2q^2$

    • $p^2$ is even, therefore $p$ is even. $p = 2k$

    • $4k^2 = 2 q^2$

    • $q^2 = 2k^2$

    • $q^2$ is even, and thus $q$ is even.

    • If both $p$ and $q$ are both even, then they can be further reduced.

    • Therefore $\sqrt{2}$ is irrational.

  • Show that $\sqrt{3}$ is irrational.

    • We are unsure of what the statement C will be.

  • Remember that proof by contradiction can be used to prove conditional sttatements as well as any kind of statement.

  • Show that $p\to q$:

    • Assume that $p\to q$ is false. (This is only possible if $p$ is true and $q$ is false.)

    • Suppose $p$ and $\lnot q$

  • Prove by contradiction that $a$ is even if $a^2$ is even $a$ being an integer.

    • Assume $a^2$ is even and $a$ is not even (odd).

    • $a = 2k + 1$ where $k$ is an integer.

    • $a^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1 = 2(int) + 1$

    • $a^2$ is odd.

Recitation 3

  • mail box thing:

    • Every user has access to one and only one mailbox.

    • $\forall u\exists m\left(A(u,m) \land \forall n(n\neq m\to\lnot A(u,n)))$

  • All users can access all websites that are in the ".edu." TLD.: $\forall u\forall w\left(T(w,".edu")\to A(u,w)\right)$

  • Rewrite: $\lnot \exists y\exists x P(x,y)$: $\forall y \forall x \lnot P(x,y)$

  • Rewrite: $\lnot \exists y\left(\exists x R(x,y) \lor \forall x S(x,y)\right)$: $\forall y \left(\forall x \lnot R(x,y)\land \exists x\lnot S(x,y)\right)$

  • Ex:

    • I am clever or I am Lucky. I am not lucky. If I am lucky, I will win the lottery

    • c: I am clever.

    • l: I am lucky.

    • w: I win the lottery

    • $c\lor l$

    • $\lnot l$

    • $l\to w$

    • $c$ by the disjunctive syllogism

  • Ex: 1.6.35

    • If Superman were able and willing to prevent evil, he would do so.

    • If Superman were unable to prevent evil, he would be impotent.

    • If Superman were unwilling to prevent evil, he would be malevolent.

    • If Superman exists, he is neither impontent nor malevolant.

    • Superman does not prevent evil.

    • Given these, Superman does not exist.

    • A(x): x is able to prevent evil

    • W(x): x is willing to prevent evil.

    • P(x): x prevents evil.

    • I(x): x is impontent.

    • M(x): x is malevolent.

    • E(x): x exists.

    • $\lnot A(s)\to I(s)$

    • $\lnot W(s)\to M(s)$

    • $\lnot P(s)$

    • $A(s) \land W(s) \to \lnot E(e)$

    • $E(e)$

    • $E(s)\to\left(\lnot M(s)\land\lnot I(s)\right)$

    • $\lnot E(s)$

    • Proof:

      • Assume E(s).

      • Therefore, $\lnot M(s)$ and $\lnot I(s)$

      • Thus, $\lnot\lnot A(s)$ and $\lnot\lnot W(s)$, or $A(s)$ and $W(s)$

      • By $A(s)\land W(s)\to\lnot E(e)$ and $E(e)$, Evil exists.

      • Therefore Superman does not exist.

    • Proof (direct):

      • If n is a perfect square, then $n + 2$ is not a perfect square.

      • $n = m^2$ where $m\in\mathbb{Z}^+$

      • $m=0$, $n = 0$

      • $n + 2 = 0$ which is not a perfect square.

      • $m \ge 1$

      • $(m+1)^2 = m^2 + 2m + 1 = n + 2m + 1 \ge m + 2\cdot 1 + 1$

      • $\blacksquare$

    • Prove (by contradiction): The sum of a rational and an irrational is an irrational number.

      • $r + i = s$ where $r$ is rational and $i$ is irrational

      • Show that $s$ is irrational.

      • Assume $s$ is rational.

      • $s - r = i$.

      • $i$ is rational which contradicts.

      • Therefore $s$ must be irrational.

Lecture 10: Proof techniques, continued

Proving conditionals with proof by contradiction

  • we want to show that $p\to q$

  • Assume $p\to q$ is false.

  • Show that p and $\lnot q$.

  • EX:

    • let a be a non-zero ratianl number $a\in q \left{0\right}$ and let $b$ be an irrational number. Prove that $ab$ is an irrational number.

    • Premise: $a$ is rational, and $b$ is an irrational. $a = \frac{m}{n}$ where $m$ and $n$ are integers and $n \neq 0$. and $b$ is an irrational.

    • Conclusion: $ab$ is an irrational number. $ab = \frac{p}{q}$ where $p$ and $q$ are integers and $q \neq 0$.

    • Let us assume that $ab$ is not an irrational number.

    • $ab = a\times b$

    • $\frac{p}{q} = \frac{m}{n} \times b$

    • $b = \frac{pn}{qm} = \frac{x}{y}$ where $x = pn$ and $y = qm$ are integers (because $m, n, p, q$ are integers) and $y\neq 0$.

    • Therefore $b$ is rational.

    • Given this, the orriginal statement is true.

  • Use it only when the direct and contrapositive approaches don't seem to work.

    • often times, a proof by contradiction has hidden within it a simple proof by contrapositive.

  • Always go direct, contrapositive, and finally contradiction, unless there is a statement of fact (ex: prove that $\sqrt{3}$ is irrational)

Prooving equivalency of a group of statements

  • any chain of propositions can be shown to be valid

  • $p_1\to p_2$, then $p_2 \to p_3$ and finally $p_3 \to p_1$

  • EX:

    • $p_1$: n is even

    • $p_2$: n - 1 is odd

    • $p_3$: $n^2$ is even

    • $n = 2k$ where $k$ is any integer

    • $n-1 = 2k - 1 = 2(k-1) + 1$, $n-1$ is odd

    • $p_1 \to p_2$

    • $n-1 = 2k + 1$ where $k$ is any integer

    • $n = 2k + 2$

    • $n^2 = (2k + 2)^2 = 4k^2 + 8k + 4 = 2(2k^2 + 4k + 2)$

    • thus $p_2 \to p_3$

    • Using the contrapositive:

      • show $\lnot p_1 \to \lnot p_3$

      • $n$ is not even, $n = 2k + 1$ where k is any integer.

      • $n^2 = 2(int) + 1$

      • Therefore, $p_3 \to p_1$

Proof by cases

  • sometimes we cannot prove a theorem using a single argument that holds for all posible cases.

  • Ex: "Suppose $x$ is an integer, prove\ldots"

  • Ex:

    • prove that if $n$ is a natural number, then $1 + (-1)^2(2n-1)$ is a multiple of 4

    • Step 1, examine using various values of n.

      • The expression behaves differenttly when $n$ is odd than it does when $n$ is even.

      • The proof must examine these two possibilities separately.

    • Prove that if $n$ is an even natural number, then $1+(-1)^2(2n-1)$ is a multiple of 4.

      • $n = 2k$ where $k$ is a positive integer.

      • $1 + (-1)^n(2n-1) = 1 + (-1)^{2k}(2(2k) - 1) = \cdots = 4k$

    • Prove that if $n$ is an odd natural number, then $1+(-1)^2(2n-1)$ is a multiple of 4.

      • $n = 2k + 1$ where $k$ is a positive integer.

      • $1 + (-1)^{2k + 1}(2(2k + 1) - 1) = 1 - (4k + 1) = -4k$

  • Choosing that something must be proven using mulitple cases can be done by:

    • look carefully at the problem

    • notice that things are differentfor different cases of $n$

  • Ex:

    • Let $n \in \mathbb{Z}$. Prove that $9n^2 + 3n - 2$

    • $n$ can equal zero in this case.

    • 0 can be considered positive.

    • Assume $n$ is even.

    • Assume $n$ to be odd.

    • Or, use factoring, and then work from there.

Proof by exhaustion

  • This should only be done for a small number of cases.

  • Ex:

    • Prove that only consecutive positive integers not exceeding 100 that are perfect powers are 8 and 9.

    • This can be done using a program.

    • This can be done by listing all perfect powers under 100 and then finding the consecutive perfect powers.

  • This is not useful for large cases.

Lecture 11: Proof techniques, continued

Proving biconditionals statements

  • prove $p\to q$ and then $q\to p$ to prove $p\iff q$

  • Ex:

    • prove $n$ is odd iff $n^2$ is odd.

    • first show that if $n$ is odd, $n^2$ is odd. (direct technique)

    • then prove than if $n^2$ is odd, $n$ is odd. (contrapositive)

Existence Proofs

  • conditional statements are universally quantified statements: $P(x)\to Q(x)$& is also $\forall x\left[P(x)\to Q(x)\right]$

  • some howevere are not, these are existence statementts, and have the form of an existence statement.

  • $\exists xR(x)$, we must find an x that satisfies $R(x)$

    • this can be done simply by showing an example

  • Ex: Prove that there exists an integer that can be expressed as the sum of two perfect cubes in two different ways.

    • A computer is often useful for this.

    • $1729 = 1^3 + 12^3 = 9^3 + 10^3$ – Ramanujan's number

  • Constructive proofs

    • show the example. This doesn't matter how you find the number that provides the example.

    • Ex: prove that there exist irrational numbers $x, y$ for which $x^y$ is rational:

      • $x = \sqrt{2}$ (prove) (proof by contradiction)

      • $y = \log_2 9$ (prove) (proof by contradiction)

        • Assume $\log_2 9$ is rational

        • $\log_2 9 = \frac{p}{q}$ where $p, q$ are integers and $q\neq 0$

        • $2^{\frac{p}{q}} = 9$

        • $(2^{\frac{p}{q}})^q = 9^q$

        • $2^p = 9^q$

        • Contradiction.

      • $x^y = \sqrt{2}^{\log_2 3^2} = \sqrt{2}^{2\log_2 3} = 2^{\log_2 3} = 3$

  • non-constructive proofs

    • Prove that an example exists without actually giving it.

    • Ex: Prove that there exists $x, y$ which are irrational, but $x^y$ is rational.

      • Assume $x = y = \sqrt{2}$

      • $x^y = \sqrt{2}^{\sqrt{2}}$

      • Let us assume that it is irrational,

      • $x= \sqrt{2}^{\sqrt{2}}$, $y = \sqrt{2}$

      • ${\sqrt{2}^{\sqrt{2})}^{\sqrt{2}}$

  • Uniqueness Proof:

    • There exists one and only one $x$ that makes $P(x)$ true.

    • $\exists x(P(x)\land\forall y (y \neq x \to \lnot P(x)))$

    • Ex: Show that if $a, b$ are real, and $a\neq 0$ then there ixists a unique real number $r$ such that $ar + b = 0$

      • $r = a\frac{-b}{a} + b = -b + b = 0$

      • Assume that there exists a real number $s$ such that $as + b = 0$.

      • $ar + b = as + b$

      • $r = s$

      • If $s\neq r$ then $as + b \neq 0$

Counter examples

  • Disproving a statement.

  • Often done by counter example.

  • Ex: Prove or disprove that $n^2 + n + 1$ is a prime number fo all $n \ge 1$

    • we see when $n = 4$ the given equation is not prime

  • Ex: if $a, b$ are rational numbers, that $a^b$ is also rational.

    • $4^2 = 16$

    • $3^2 = 9$

    • $a = 2$, $b = \frac{1}{2}$, $a^b = 2^{\frac{1}{2}} = \sqrt{2}$

  • Examples can only be used for disproving things, unless using proof by exhaustion, or the universe of discourse is finite.

Lecture 12: Types of proofs

Not all things are provable

  • entdiestungsproblem

  • Hilbert's 23 questions, and 3 remain to be solved.

    • Is mathematics Complete? (Is there a proof for every true statement?)

    • Is mathematics consistent? (can we only prove things that are true, or can we prove false statements?)

    • Mathematics is either complete or consistent. This is G\"odel's Incompleteness Theorem

    • This is not provable. (If this were to be proven true, mathematics would be inconsistent. If you can not prove it, mathematics is incomplete.)

  • An eternal yet Asymmetcric Friendship.

  • Logic has its limits.

  • See Escher prints

  • Try to prove assertions before you take them as fact.

  • Don't peek at proofs, try to prove it yourself.

  • Practice and do a lot of scratch work.

  • Look at the proof tips slide!

Future Land

  • CSCE 310 – Data structures and Algorithms

    • satisfiability

    • algorithmic analysis

    • NP completeness

  • CSCE 476/876 – AI

  • CSCE 421/821 – Foundations of Constraint Processing

    • First-order logic and inference

    • knowledge-based agent

Lecture 12: Mathematical Thinking: Relational Thinking

  • Sets, relations, functions and graphs

  • discrete mathematics is the study of discrete structures.

  • discrete structures are abstract mathematical structures for represteting discrete objects and relationships between these objjects

  • how then do we build discrete structures: Sets

  • Sets are a collection of objects, containing only one of each given element.

    • $\mathbb{R}\times\mathbb{R}$

    • $\mathbb{R}\times\mathbb{N}$

    • $\mathbb{N}\times\mathbb{N}$

  • How many different committees of 3 studentts can be formed from a group of four studentts. (combinations)

    • 4 combinations, a set of 4 combinations.

  • How do we describe a 2-dimensional plane? (functions)

    • Lines?

    • Points?

    • The Cartesian product of $x$ ($\mathbb{R}$) and $y$ ($\mathbb{R}$).

  • A line is another cartesian product (Relations (a set of ordered pairs)).

  • Social Networks: (Graph theory)

    • Graphs and graph algorithms.

    • graphs are a set of vertices and a set of edges.

  • To build discrete structures, we need sets.

  • To quote Hofstadter: "All of mathematics can be described using sets."

Sets

  • Sets are a collection of "objects". – Georg Cantor, 1895

  • This is a loose definition.

  • This is the fundamental discrete structures.

  • the objects in a set often have similar properties.

  • this is the study of coollections in an organized fashion.

  • Unique set: $\left{a,b\right}$

  • Multiset: $\left{a,a,b,b\right}$

  • If an element is in a set, the set contains that element: $x\in A$, not being in A $x \not\in A$

  • Roster Method: All members of set listed in braces.

  • We need something more powerful: Set Builder Notation

    • $O = \left\{x | (x\in \mathbb{Z}) \land (x = 2k\ \mathrm{for\ some}\ k \in Z)\right\}$

  • Sets in Computer Science:

    • types and datatypes are based on the concept of a set. A datatype is the name of a set and the set of operations that are available.

  • When are two sets equal?

    • Order doesn't matter.

    • When the number of elements is equal and the elements themselves are equal, however, a bag is allowed as long as there are no differing elements

  • Sets can contain other sets.

  • Sets can also be described using Venn Diagrams.

    • Make sure that there is a universal set $U$ which is represented by the outer-most rectangle.

  • Empty Set / Null Set $\emptyset$ or $\{\}$

  • Singleton: $\{a\}$

  • Remember: $\emptyset \neq \{\emptyset\}$

  • $A$ is a subset of $B$ iff every element of $A$ is an element of $B$: $A\subset B$

    • $A\subseteq B \iff \forall x(x\inA \to x\in B)$

    • if $B$ has $n$ elements, $B$ will have $2^n$ subsets.

Recitation 4

  • Remember that predicate logic provides rules for things, not facts.

  • Propositional logic provides concrete facts, not rules.

  • Use predicate logic for groups of things and their related rules.

  • Universal and existential instantiation applies rules to objects.

  • Remember that $T\to T$ and $F\to T$ are both $T$.

  • Prove or disprove that the product of two irrational numbers is irrational.

    • Disproved by counterexample: $\sqrt{2}\cdot\sqrt{2} = \sqrt{2}^2 = 2$

  • Prove that there are 100 consecutive numbers which are not perfect squares:

    • $(n + 1)^2 - n^2 = 100$

  • Prove that there exists a rational $x$ and an irrational $y$ such that $x^y$ is irrational. (non-constructive by law of excluded middle)

    • $x = 2$; $y = \sqrt{2}$.

    • $x^y = 2^\sqrt{2}$

      • Irrational

      • Rational:

        • $\left(2^\sqrt{2}\right)^\frac{\sqrt{2}}{4} = 2^\frac{2}{4} = 2^\frac{1}{2} = \sqrt{2}$

  • Set builder notation

  • Cardinality of a set is the number of elements in a set.

Lecture 13: Set Theory, Continued

  • Recall the definition of subset: $a\subseteq b \iff \forall x(x\in A \to x\in B)$

  • creation of all subsets of $B = \{a,b,c\}$, there are $2^n$ subsets for a set with $n$ elements.

    • this can be proven using induction.

  • remember that $\emptyset \subseteq S$ and $S\subseteq S$

    • Proof (vacuous proof)

    • Assume that $S$ is a non-empty set.

    • If $\emptyset \subseteq S \iff \forall x \left[x\in\emptyset\to x\in S\right]$

    • $\emptyset = \{\}$

    • $x \in \emptyset$

    • Therefore, $\emptyset \subseteq S$.

  • show that $A\subseteq B \land A \neq B$. This is shown as $A\subset B$ or $A\subsetneq B$.

  • Ex:

    • $A = \{x | x \in \mathbb{Z} \land x \pmod{2} \equiv 0\}$

    • Is $A \subseteq \mathbb{Z}$? Yes, A is a subset of Z.

    • Is $A\subset\mathbb{Z}$? Yes, it's also a proper subset.

    • Is $\mathbb{Z}\subseteq A$? No.

    • Is $10 \in A$? Yes.

  • Ex:

    • $B = \{2,3,5,10\}$; $C = \{2,3,5,\{10\}\}$

    • $B = C$ – No.

    • $B \subseteq C$ – No.

    • $C \subseteq B$ – No.

    • $\{10\} \in C$ – Yes.

    • $\{\{10\}\} \subseteq C$ – Yes.

  • Cardinality is the number of distinct elements in a finite set $S$. Cardinality is represented as $|S| = n$

  • Recall $B = \{x | (x\leq 100) \land (x is prime)\}$

    • $|B| = 25$

  • $|\emptyset| = 0$

  • $S = \{\mathbb{N}, \mathbb{Z}\}$, $|S| = 2$

  • Infinite sets do not all have the same cardinality.

    • $\mathbb{N, Z, Q}$ are countably infinite. This means that the elements can be ordered and enumerated.

    • $\mathbb{R}$ is not countably infinite. The elements cannot be enumerated.

    • There are different types of infinity.

  • Hilbert's Hotel

  • Georg Cantor discovered different magnitudes of infinity.

  • There are more real numbers than there are integers, yet there are just as many integers as there are rationals.

  • Bijective functions.

  • dangerous knowledeg of georg cantor

Lecture 14: Proving Equivalence

  • Show that a set is:

    • a subset

      • $A\subseteq B \iff \forall x (x\in A \to x\in B)$

      • it is enough to show this for an arbitrary element

    • a proper subset

      • $A\subset B \iff (A\subset B \land \exists x ((x\in B) \land (x\not\in A)))$

    • equal to another set

      • show that $A\subseteq B$ and $B\subseteq A$

  • The Power set

    • A set that contains all subsets of $S$ as its elements

    • every possible subset of $S$

    • $A = \{a,b,c\}$

    • $P(A) = \{\emptyset,\{a\},\{b\},\{c\},\ldots,\{a,b,c\}\}$

    • What is the powerset of $\emptyset$? $P(\emptyset) = \{\emptyset\}$

    • What is the powerset of $\{\emptyset\}$? $P(\{\emptyset\}) = \{\emptyset,\{\emptyset\}\}$

    • $P(P(\{\emptyset\})) = \{\emptyset, \{\emptyset\},\{\{\emptyset\}\},\{\emptyset,\{\emptyset\}\}\}$

  • Cardinality of a power set:

    • let $S$ be a set such that $|S| = n$

    • then $|P(S)| = 2^n$

  • What is $x$ where $P(x) = \{\emptyset,\{k\}\}$? $x = \{k\}$

  • What is $P(\mathbb{R}^2)$?

    • $\mathbb{R}^2 = \{(x,y) | (x,y) \in \mathbb{R}\}$

    • This is every, and all possible bitmaps.

    • an incomprehensibly large set.

  • Remember that sets are unordered, but we often must deal with ordered collections.

    • points on a plane or in space $(x,y)$ and $(x,y,z)$ respectively.

    • This is the ordered n-tuple $(a_1,a_2,\ldots,a_{n-1},a_n)$

    • $n = 2$ is an ordered pair, $(a,b)$ and $(c,d)$ Equal only when $a=c \land b=d$

    • We use a Cartesian product to produce ordered pairs. $A\times B$

    • $A\times B = \{(a,b) | (a\in A) \land (b\in B)\}$

    • Ex:

      • $A = \{x,y,z\}$

      • $B = \{1,2,3\}$

    • Named after Rene Descartes

Lecture 15: Cartesian Product, n-tuples and more

  • Let all students be $A$ and all courses be $B$.

    • What is $A\times B$?

    • What can it be used for?

      • it represents every possible enrollment.

  • Used to describe a plane.

  • a relation is a subset of a cartesian product.

    • $R\subseteq A\times B$ is a relation from set $A$ to set $B$.

  • Create a set of either math or CS majors

    • $A \cup B \equiv \{x | (x \in A) \lor (x \in B)\}$

  • Create a set of both math and CS majors

    • $A \cap B \equiv \{x | (x\in A) \land (x \in B)\}$

  • Create a set of non-math majors (represented with a bar above) $\{x | x\not\in A\}$

  • Difference: $A - B \equiv \{x | x \in A \land x \not\in B\}$

  • Demorgan's Law: $\bar{A\cap B} \equiv \bar{A} \cup \bar{B}$

  • Universal set is anything union with it's complement

Recitation 5

  • Set Operations

Lecture 16: Set Theory, continued

  • $\overline{A}$ means the set of elements which are not in $A$

  • Show that $(A\cap B) \cup (A\cap \overline{B}) = A$

  • Membership tables

    • to indicate an element is part of a set, use 1

    • to indicate not being a set, use 0

    • Ex:

      • $\overline{A\cap B\cap C} = \overline{A}\cup\overline{B}\cup\overline{C}$

      • Provides for a truth table-like element.

  • $\overline{A\cap B} = \overline{A}\cup\overline{B}$ is the equivalent of DeMorgan's law.

  • Union works on any finite number of sets, as does intersection

  • Can you represent a set in a computer?

    • Not for infinite sets, unless there is a finite representation.

    • If we can assume that the Universal set is finite, we can easily and efficiently represent sets by bit vectors.

    • A is the set of all even integers, then for this, the universal set is all integers.

    • The universal set is all objects that we are interested in.

    • We must then force an ordering on the objects.

    • Let $A = \{0,1,6,7\}$. $U = \{0,1,2,3,4,5,6,7\}$

      • Order these, and produce a bitvector: $A = 11000011$

    • By representation as a bitvector, set operations become trivial.

  • Cardinality of a union of two sets $|A \cup B|$.

    • Can we use $|A| + |B|$? No.

    • However, $|A| + |B| - |A \cap B|$ will work.

    • This is the principle of inclusion-exclusion.

  • Interesting farct about set theory:

    • There is a flaw.

    • Vally Guttman and her Melancholic Husband (Georg Cantor)

    • Cantor's set theory is na\:ive.

      • a set is an onordered collection of objects

      • there was no formal definition of objects, rather, he used an intuitive definition

    • The Barber Paradox

      • A group of barbers who shave only those men who do not shave themselves.

      • Suppose there is a barber who does not shave himself.

      • thus, he must shave himself.

      • He cannot exists in the collection. No barber in the collection can shave himself.

    • Cantor said that any definable collection is a set.

    • $S = \{x | x \not\in x\}$

      • This cannot contain the null set.

      • Does $S$ contain itself?

        • Case 1: Yes

          • $S$ thus contains itself.

          • This is not possible by definition.

        • Case 2: No

          • $S$ thus contains itself.

          • This is not possible by the definition.

        • This is a paradox.

    • Remember there is a limit of computation.

    • Russell's Paradox:

      • An inconsitency.

      • $R = {x | x \in x}$

      • $R \in R \iff R \not\in R$

      • This lead to axiomatic set theory, not useful now, but quite useful later.

Lecture 17: Functions

  • remember the definitionof a function from algebra.

  • functions form a relationship between two sets

    • domain

    • range

  • functions are more than just a description of a relationship between two numbers.

  • Ex: how do we know that the cardinality of $\mathbb{N}$ and $\mathbb{Z}$b are equal?

    • we cannot count the number of elements in these two sets.

    • we can however, use functions to calculate the cardinality.

  • Remember that functions are discrete, not continuous

  • functions are not rules, rather, there is a set-theoretic definition.

  • a function creates a relation between two sets.

    • sending elements from one set to another

    • for every given input, there is one, and only one value for the given function.

    • $f: A\to B$ is a relation $f \subset A\times B$ from $A$ to $B$

    • $f$ maps items from $A$ to $B$

      • Remember that $A$ can only point to one $B$, but there can be more than one $A$ that points to $B$, or none at all

    • $(a,b) \in f$ is abbreviated as $f(a) = b

  • let $f: A\to B$ and let $f(a) = b$

    • $A$ is the domain

    • $B$ is the codomain

    • $b$ is the image

    • $a$ is the preimage

    • The set of all images is the range of the function

  • Types of functions

    • strictly increasing: $f(x) < f(y)$ where $x < y$

    • strictly decreasing: $f(x) > f(y)$ where $x < y$

    • injective (one-to-one): $f(x) = f(y) \to x = y$; $f: A\to B$, $x,y \in A$, $x \neq y$, $f(x) \neq f(y)$

    • surjective (onto): for every $b \in B$ there exists an element $a \in A$ such that $f(a) = b$; every element of the codomain is mapped; surjective if and only if the range and domain are equal.

    • bijective (one-to-one corespondence): the function must be both one-to-one and onto

  • Mappings to remember:

    • one-to-one – injective

    • onto – surjective

    • one-to-one correspondence – bijective

Lecture 18: Still more Functions

  • Given a mapping: $f: A\to B$:

    • How do we tell if $f$ is a function?

      • Is there an element $a \in A$ such that $f(a) \not\in B$? If so, no.

      • is there an element $a\in A$ that maps to two elemennts in $B$? If so, no.

    • Is $f$ injective?

      • suppose $x,y \in A$ and $x\neq y$, if $f(x) \neq f(y)$, this is injective.

      • or $x,y\in A$ and $x = y$ if $f(x) = f(y)$, this is injective. (contrapositive approach)

      • Or use contradiction.

    • Is $f$ not injective?

      • Show a counter example, $x,y \in A$ and $x\neq y$, show $f(x) = f(y)$.

      • use contrapositive.

    • Is $f$ surjective?

      • is the range equal to the codomain? If so, the function is surjective

      • is the range bounded? If so, then the function is not surjective

      • Suppose $b \in B$. Show that there exists an $a \in A$ such that $f(a) = b$. This is simplified when a function is algebraic.

      • This is an issue of domain and codomain, not the function itself.

  • remember to use counter examples, the contrapositive and a few other such techniques.

  • be careful of mapping sets.

Recitation 6

  • remember the form of proof by contradiction

  • $f: A \to B$

  • Remember, there exists only one thing in $B$ that an element in $A$ maps to.

  • remember to be careful with your arithmetic

  • remember that if the leading power is even, the function is not onto, but this is not a sufficient proof

Lecture 19

  • Remember to try the contrapositive for showing one-to-one first, then on to the proof by contradiction.

  • be careful with your algebra

  • if in integer space, and you see non-integer, contradiction is the best for showing one-to-one

  • onto can be disproven by finding global extrema, or by showing that you require something in a different domain.

  • Ex: $f:\mathbb{Z} \to \mathbb{Z}$ by $f(x) = 3x^3 - 3$ (exercise to the reader)

  • horizontal line test does not always work depending on the given domain and codomain

  • recall the definitions for strictly increasing and decreasing functions

    • $\forall x \forall y (x < y \to f(x) \le f(y))$

    • $\forall x \forall y (x < y \to f(x) < f(y))$

    • $\forall x \forall y (x < y \to f(x) \ge f(y))$

    • $\forall x \forall y (x < y \to f(x) > f(y))$

  • Remember that if a function is strictly increasing or strictly decreasing, it must be one-to-one, but this can not be used used in a proof.

  • What is the significance of a bijective function?

    • if a function is bijective, then it has an inverse.

    • an inverse "undoes" the effect of a function.

  • let $A = \{a,b,c\}$, $B = \{1,2,3\}$, $f = \{(a,2),(b,3),(c,1)\}$ from $A\to B$

    • then $f^{-1} = \{(2,a),(3,b),(1,C)\}$

  • functions must be bijective to have an inverse. (both onto and one-to-one)

  • when finding an inverse, make sure that the function is bijective.

  • be careful with function composition

  • remember that the range of g must be in the domain of f for a composition to be valid.

  • remember floor and ceiling functions

    • floor takes a real number, and finds the closest integer that is either equal to the real or smaller than it.

    • cieling takes a real number and finds the closest integer that is either equal to or greater than it.

    • These are useful for counting problems, such as data storage and data transmission.

Lecture 20

  • the pigeonhole principle for determining injective or surjective.

    • one pigeon in one hole.

    • if you have more pigeons that holes, the function is not injective

    • if you have more holes than pigeons, the function is surjective

  • When do two sets have the same cardinality?

    • two sets have the same cardinality if and only if there eixsts a bijective function that maps from one to the other.

    • remember that $\mathbb{N} \subseteq \mathbb{Z}$ and $|\mathbb{N}| = |\mathbb{Z}|$

  • A set is countable if its cardinality is equal to the cardinality of the natural numbers.

    • positive integers

    • negative integers

    • all integers

  • When an infinite set is countable, it's cardinality is denoted by $\aleph_{0}$, $|S| = \aleph_{0}$

  • The diagonalization argument shows that the set of real numbers is uncountable.

  • There is a hierarchy of infinities.

Rules for exam success

  • Solve all problems discussed in the lecture.

  • Solve all the recitation problems (see Piazza).

  • Solve all the homework problems.

  • Solve all the quiz problems.

  • Look at last semester's midterm on Blackboard.

More Relational Thinking

  • graph theory

    • set of paths

      • can have direction, but do not have to.

    • Given a set of paths $S = \{(a, b), (b, c), (c, a)\}$, find all sets of paths between pairs of points.

    • How can we find a direct or indirect path between two nodes?

      • sets of nodes

      • sets of relations (this is a function)

      • To do this, we need sets, relations and functions.

      • relationships are shown using a variety of notations.

Lecture 21

  • A relation is a subset of the cartesian product of two sets.

  • Determining the number of relations on a finite set:

    • The cardinality of the power set of the cartesian product of the set by the set, $|P(A \times A)|$

    • Or $2^{n^2}$

  • Some relations have properties that others don't.

    • the relation $\le$ on $\mathbb{Z}$ satisfies $x \le x$ for every $x$ in $\mathbb{Z}$

    • but $<$ is never true where $x < x$ on $\mathbb{Z}$

    • The Properties

      reflexive

      if the orderd pair $(a, a)$ exists such that $a \in A$. There must be $n$ reflexive pairs where $n = |A|$

      • On Integers: $\le$, $=$ and $/$, but not $>$, $<$, or $\neq$

      symmetric

      if you have $(b, a)$ there must be $(a, b)$, $(b, a) \in R \iff (a, b) \in R$

      • On Integers, $\neq$, $=$, but not $\leq$, $\geq$

      antisymmetric

      $\forall a, b [((a, b) \in R \land (b, a) \in R) \to a = b]$ (When the two elements are equal are the only symmetric pairs)

Midterm Review

Logic

  • do you understand the purpose of logic?

  • What is tthe goal?

    • automate human decision making

  • the use of statements and operators

  • use inference rules to make decisions

  • computers are logic machines, we use symbols to define logic.

  • we define the propositional and predicate calculi to deal with logic.

  • propositional calculus

    • declarative sentences that is either true or false.

  • predicate calculus

    • declarative sentences that include variables and are either true or false.

    • allow for quantifiers.

  • The rules of inference

    • are used to make conclusions from predicates and propositions

    • can be derived using truth tables and proving techniques.

Functions and Relations

  • Determine onto and one-to-one

  • disprove onto using counterexample

  • remember which techniques you use and mention which technique.

  • to show that a function is not invertible show that it is not bijective.

  • don't use short hand, and be explicit.

Recitation

  • remember the difference between necessary and sufficient

Lecture 22: Relations, continued

  • Be careful in proving relational statements, they can be a bit tricky.

  • For disproof oonly show a counter example.

  • Transitivity is such that $\forall a, b, c \in A((aRb \land bRc) \to aRc)$

  • be careful with transivity. it's a propogation of relationships

  • Review table from notes

  • Asymmetric and irreflexive relations

    • asymmetric has absolutely no symmetric pairs.

    • irreflexive has no reflexive pairs.

    • a relation can be asymetric iff it is both irreflexive and antisymmetric

  • Calculating the number of relations:

    • The cardinality of the power set of the $A \times B$

    • $n^2$ ordered pairs, $n$ reflexive pairs for $A \times A$ and $n = |A|$ Total Reflexive relations = $2^{n^2 - n}$

Lecture 23: Combining Relations

  • relations can be combined using set operators.

  • by combining relations, we can have new relations with new properties

  • Relation composition works like function composition

  • using composition allows recursive relations on R, or powers of the relation R

    • this is done in part to develop transitive relations

    • And, at some point, $R^n = R^h$, where h is the highest power. The highest power is if $R^n = \{\emptyset\}$, then $h = n - 1$, or that any higher powers are equal to $R^h$

    • A relation R is transitive iff $R^n \subseteq R$ for $n = 1, 2, 3, \ldots$

  • To make a transitive relation, find all higher powers and take the union.

  • Efficiently computing higher powers of a relation:

    • use 0-1 matrix representation

      • 0-1 matrices let r be relation from set A to B.

        • Where there exists a pair $(a, b)$, there exists a 1, in all other cases, 0. This requires an ordering to be imposed on A and B

        • iff all elements on the diagonal are 1, then it is reflexive

        • look across the diagonal for symmetric and antisymetric

      • union is entry-wise $\lor$ and intersection is entrywise $\land$

      • composition is done by the boolean product of the two. See 2.6 from text book.

      • $R^n = M_R^n$

      • By recursive composition, we can find a transitive relation

    • The directed graph form

      • a graph can be used to show where an element is connected to another element.

      • this can show properties of a relation in a very visual way.

      • a relation is reflexive if all nodes have a self-loop

      • a relation is symmetric if there's a path from x to y and the other direction

      • a relation is antisymmetric if there's a path from x to y and no other path back

      • a relation is transitive if there exists x to y and y to z and x to z

  • Closures

    • adding some kind of property

    • the transitive closure would add the required paths to make a relation transitive

    • transitive relations are much, much more difficult.

Lecture 24: Construction of transitive closures

  • Be able to find the highest power.

  • Adding a relation of R with all of its higher powers is called a connectivity relation, denoted by $R^* = \cup_{i=1}^n R^n$.

  • computing higher powers of a sets with 0-1 matrices, and take the union of hall higher powers

  • To solve manually, find the missing pairs and then add them to R. This is not transitive however. This may have to be done multiple times.

  • Create a zero 1 matrix and find all higher powers of a matrix.

  • union of two matrices is denoted with $\lor$

  • time and space increases with the size of the matrix.

  • You can use Warshall's algorithm to do this quickly.

    • take a zero-one matrix and call it $M_{k- 1}$

    • transfer all the ones to $M_k$

    • on $M_{k-1}$ refer to colums as z, rows as y.

    • call rows y_n where there is a 1, doing the same for Z.

  • Digraphs, adjacency matrices and the transitive closure can all be found with Warshall's algorithm. Never could work sitting at his desk.

Lecture 25: More relations

  • Let $A$ be the set of all people.

  • Let $R = \{(a, b) \mid H(a) = H(b)\}$

  • An equivalence relation is reflexive, transitive and symmetric

  • The $=$ relation on $\mathbb{Z}$ is an equivalence relation

  • the equals method in many probgramming languages defines an equivalence relation

  • Imagine there is a relation on the set of strings of inglesh letters, such that $aRb$ iff $l(a) = b(a)$

    • this is reflexive

    • symmetric

    • transitive.

  • Is the devides relation on the set of positive intteger an equivalence relation?

    • reflexive

    • not symmetric

    • not entirely transitive.

  • Let m be an integer such that $m > 1$. Is $R = \{(a, b) \mid a \equiv b \pmod{m}\}$.

    • congruence can be checked by $\frac{a - b}{m}$ is an integer.

    • reflexive

    • symmetric

    • transitive

  • Equivalence classes are things like "x has the same parity as y"

  • Each relation has a different number of equivalence classes.

  • Partitions: $R$ = a lives in the same state as b.

    • there are 50 equivalence classes, this provides 50 partitions

Recitation 8

reflexive

$\forall a (a, a) \in R$

symmetric

$\forall a, b (a, b) \in R \to (b, a) \in R$

antisymmetric

$\forall a, b \[(a, b) \in R \land (b, a) \in R\] \to b = a$

transitive

$\forall a, b, c \[(a, b) \in R \land (b, c) \in R \] \to (a, c) \in R$

?

relations on a set n that are:

reflexive

$2^{n^2 - n}$

symmetric

$2^{\frac{n^2 + n}{2}}$

Lecture 26: Equivalence relations, continued

  • an equivalence class is a set partitioning an equivalence relation.

  • $[2] = \{ x \in A : xR2}$; $[2] = \{2, 4\}$

  • EX: $A = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$

    • how many equivalence classes can be formed in which the elements are $a \equiv b \pmod{2}$ (this gives 2, as there are two sets)

    • How many are there $a \equiv b \pmod{3}$? 3

  • Equivalences classes are either identical or disjoint.

  • See theorem 1

  • Subsets must be non-empty and pairwise disjoint to be valid partitions.

  • EX: $(a, b) \in R$ such that $a$ and $b$ live in the same state.

    • There are thus 50 equivalence classes

  • Developing equivalence classes with a 0-1 matrix or a Digraph.

    • matrices

      • if there are squares of 1s, with 0s elsewhere, then those are partitions

    • digraphs

      • there must be multiple disjoint, complete graphs (complete graphs are such that each vertex is connected to every other vertex via a pair of unique edges).

Lecture 27: Ordering problems

  • motivating applications:

    • going from concurrent to sequential tasks

  • not allowing to differentt processes to run simultaneously

  • two processes should not be symmetric

  • processes should be transitive

  • EX: The ordering of schools.

  • this is a relation of sorts.

  • total order is a complete order from start to finish.

  • many processes, total order is natural order.

  • there are processes which total ordering cannot be done.

    • there are pairs that are not related, which means there is no natural order between to tasks

    • partial order is allowed in the absence of natural order. we must impose a binary relation between pairs.

  • $T_1RT_2$ if $T_1$ is $T_2$ or $T_1$ precedes $T_2$

  • once we have this, we can find the properties.

  • It must be reflexive

  • it cannot be symmetric

  • it should be transitive.

  • for a given set of tasks we define a relation to impose partial orderings among tasks.

  • $S$ is the set of all tasks, $R$ is the relation to impose ordering.

    • $(a, b) \in R$ iff $a = b$ or $a$ before $b$

    • the relation is symmetric if it is reflexive, antisymmetric and transitive, this is a poset, denoted $(S, R)$

  • posets are used for sets without a natural order

    • this means that not all pairs are related

  • There are several types of orderings

  • An example of a poset is the people with the relation a = b or a is an ancestor of b

  • Or a is not taller than b

  • $\{(X,Y) \mid X \subseteq Y\}$ on the $P(\{a, b, c\})$

    • reflexive

    • antisymmetric

    • transitive

    • thus a poset

  • Notation for partial orderings

    • $\preceq$ is before

    • $\prec$ is strictly before

  • If $(S, \preceq)$ is a poset and every two elements of $S$ are comparable, $S$ is a totally ordered set. the relation $\preceq$ is thus a total order.

    • this is the case for $\leq$ on $\mathbb{Z}$

  • A well-ordered set is if it is a poset such that $\preceq$ is a total order and that every non-empty subset of $S$ has a least element

    • this is true for $\leq$ on $\mathbb{N}$

Lecture 28: More Ordering Problems: Total Order

  • every pair is related

  • Well ordered means that $\preceq$ is a total order and that every non-empty subset has a least element.

  • Lexicographic orderings are those based on the alphabet or something similar.

    • based on a form of partial orderings

    • This works on ordered tuples

  • As with relations and functions, there are convenient graphicl representations for posets. These are called Hasse diagrams.

    • these are digraphs that are reflexive, antisymmetric and transitive.

      • Remove the self loops first

      • then remove the transitive loops

      • then convert to a graph, removing direction.

  • To produce a total order from a poset, the extremal elements

    • the extremal elements are the numbers that are terminal on a hasse diagram

    • maximal elements are the elements that do not precede others

    • minimal are elements that have no preceding elements

    • upper bounds (maximum) find all elements that a group of elements precedes

    • lower bounds (minimum) find all elements that precede a group of elements

Recitation 9

  • antisymmetric $\forall a, b \in S \left[ (a, b) \in R \land (b, a) \in R\right] \to a = b$

  • A lattice is such that every pair of elements has both a least upper bound and a greatest lower bound. See example 21, p. 626.

Lecture 29: More Posets

  • for a poset to be a lattice, all elements bust be comparable

  • total or linear orders will always be a lattice

  • $(\mathbb{Z}^+, |)$ is a lattice as the greatest lower bound is the GCD and the least upper bound is the LCM

  • Topological sorting:

    • this is the creation of a total order that is compatible with the partial order.

    • For this, we know that every finite, non empty set with the relationn $(S, \preceq)$, there exists a minimal element.

    • To do this, we remove each and every given minimal element, in turn and then from there, we continue, keeping track of the order one-by-one.

Lecture 30: Algorithms

  • this is the essence of computer science

  • these are a set of many high-level steps instructing a computer to accomplish shomething

  • we then determine the feasability of the algorithm

  • The word Algorithm comes from Muhammad ibn Musa al-Khwarizmi

    • also gave us the name algebra

  • Three steps:

    • what are the classes of problems

      • search or sort

    • what are the paradigms

      • brute force

        • tends not to be optimized

        • very straight forward

      • divide and conquer

        • Also known as bisection

      • greedy techniques

      • dynamic programmyng

      • backtracking

      • probabalistic techniques

    • how do we analyze

  • Actually apply

    1. Translate to a mathematical context

    2. Write an unmbiguous specification

      • This must be correct

      • it must execute in a finite amount of time

      • This should be described using psuedo code. See 156 Notes, Lecture 28: Computation.

    3. Analyze this

Lecture 31: More algorithms

  • remember that divide-and-conquer algorithms are quite useful and elegant

    • these tend to be very fast

  • when writing algorithms, be very careful and precise

  • Sort:

    • brute force:

      • bubble sort

        • very ugly

        • very slow

      • insertion sort

        • takes time

        • is very contrived

    • bisection

  • optimization problems

    • finding fastest route, best fit, and the like

    • A simple technique is the greedy technique

      • most immediate solution, however this is only local

      • not guaranteed to be the best global solution

Recitation 10

  • writing psuedocode

  • think a strange blend of python and algol

  • yuck, algol

Lecture 32: Efficiency analysis

  • Determining algorithm performance

    • compare resource efficiency

      • time

      • memory

      • i/o

      • circuits, power

    • we will only study time efficiency

      • while this is hardware-dependent, we don't need to worry about implementation details

      • time depends on input size

  • Don't ever compare when input size is small, this can fool you

  • we compare growth rate, not actual running time.

  • we thus study the asymptotic behavior as $n\to \infty$

  • we look at the most dominant term of a function to determine the type of run-time, and the constants are not particularly important, as they are especially implementation dependent

  • Big O provides a crude measure of the running time of an algorithm, as the growth rate of the algorithm

  • This is a part of Bachmann-Landau notation

  • remember to use the simplest term inside of big-o

  • use the upper bound to find big O

  • big $\Omega$ is the lower bound

  • for both, the tight bound, we use Big $\Theta$

  • For $f(x) = x^2 + 2x$

    • Function is quadratic

    • however, to find upper bound, find a constant $c$ such that $x^2 + 2x \leq cx^2$

    • $3x^2$ is greater, thus $c = 3$

    • thus $f(x) = O(x^2)$

  • remember that the dominant term is often all you need to look at, but remember to find a threshold and a multiplier.[]

Lecture 33: Continued Big O Analysis

  • remember to use constant multipliers instead of $\pm c$

  • remember to use the closest upper bound of a function

  • can be either $f(n) = O(g(n))$ or $f(n) \in O(g(n))$

  • $f(n)$ asymptotically less than or equal to $g(n)$

  • limits can be used to find upper bound

  • find the threshold and multiplicative constants

Lecture 34: More Big O

  • Show that $x \log_2 x$ is $O(x^2)$

    • when $x > 0$, $x \log_2 x \leq xx = x^2$

    • Assume that when $x^2 = x\log x$

      • $x^2 \leq C(x\log x)$

      • $\frac{x}{\log x} \leq C$

      • Or $C \geq \frac{x}{\log x}$

  • Big O analysis for the sum of the first n positive numbers. The max is shown to be $O(n^2)$

  • Big O for factorials is $O(n^n)$

  • $2x^2 + x^3\log x$ is $O(n^4)$, $C = 3, k = 1$

  • $3x^5 + (\log x)^4$ is $O(n^5)$, $C = 4, k = 0$

  • $\frac{x^4 + x^2 + 1}{x^4 + 1}$ is $O(1)$.

Recitation 11

  • Big-O can be defined as such ($f(n) \in O(g(n))$):

    • $\forall x > x_0 f(x) \leq c \cdot g(x)$

  • complexity class a times complexity class b is class ab

  • as $\lim_{x \to \infty} \frac{f(x)}{g(x)}$

    • if it goes to inifinity: $f(x) \in \Omega(g(x))$

    • if it goes to 0: $f(x) \in O(g(x))$

  • L'Hopital's rule:

    • Applies To:

      • $\frac{\infty}{\infty}$

      • $\frac{0}{0}$

    • take the derivatives of the two, separately. Re-apply if necessary.

Lecture 35: Beyond Big-O analysis

  • Big-O does not deal with the lower bound (best-case)

  • For this, we use Big-$\Omega$

  • Uses otherwise the same techniques and notation, save $\Omega$

  • Big-$\Theta$ provides both an upper and a lower bound, such that there exists $C_1, C_2, k$ that multiply $g(x)$ and provide both an upper bound and a lower bound for the function.

    • this means that f(x) and g(x) are asymptotically equal.

  • The use of the limit method:

    • f(n) is the running time function.

    • find a function g(n) that is the upper bound, lower bound and tight bound (O, $\Omega$, $\Theta$).

    • $\lim_{n\to \infty} \frac{f(n)}{g(n)}$ $$ \lim_{n\to \infty} \frac{f(x)}{g(x)} = \left\{\begin{array}{ll} 0 & f(x) = O(g(x))\\ C > 0 & f(x) = \Theta(g(x)) \\ \infty & f(x) = \Omega(g(x)) \end{array} \right. $$

      • as it goes to 0, $g(n)$ is the upper bound (O).

      • as it goes to $\infty$, $g(n)$ is the lower bound ($\Omega$).

      • if it goes to an arbitrary, non-zero constant $C > 0$, you have the tight bound ($\Theta$).

  • simplify the functions first

  • no need for witnesses

  • use L'Hôpital's rule, if applicable

  • $$ \lim_{n \to \infty} a^n = \left\{ \begin{array}{ll} 0 & a < 1 \\ 1 & a = 1 \\ \infty & a > 1 \end{array} \right. $$

  • remember that bases of logs must be equal. Use the change of base formula: $\log_3 n = \frac{\log n}{\log 3}$

Lecture 36: Analysis continued, analyzing your own algorithms

  • we deal with time only, not memory

  • this is done by finding the number of elementary operations

    • look especially at the number of repeated operations

  • remember, we want the worst-case running time

  • many algoirthms perform very differently on different input sizes

  • understand the Master theorem

  • be familiar with Big-$\Sigma$ notation

  • no the different complexity families

  • remember that most problems are categorized by worst-case complexity

  • there are solvable and unsolvable problems

    • solvables

      • tractable (polynomial time) P problems

      • intractable (no polynomial time solution) NP

    • unsolvable problems:

      • The HALTING Problem

  • If a solution can be verified in polynomial time, but cannot be solved in polynomial time is NP.

  • There exist NP complete problems, such that they have any polynomial worst-case solution

  • P = NP?

  • Scott Aaronson: If P = NP, the world would be a completely different place than we assume it to be.

Lecture 37: Confirming truth, proving the ranking of the families of big-O, the proof by induction

  • the sum of the first n odd natural numbers equals n^2

  • When do we use induction?

    • when we have a set of statements $S_1, S_2, S_3, \ldots, S_n$ and we need to prove that they are all true.

    • imagine that each statement is a domino

    • prove that if you push the first domino

    • show that if you cause a domino to fall, the next domino will also fall

  • Proving that the first statement is true is called the base step

  • the second step is called the inductive step. this is often done using direct proof

  • then, by the inductive hypothesis, you prove the inductive conclusion

  • EX:

    • $n = 1$

    • $1 = 1^2$

    • For $k > 1$: $1 + 3 + 5 + 7 + \cdots + (2k - 1) = k^2$ $S_k \to S_{k + 1}$

      • $k^2 + (2(k + 1) - 1) = (k + 1)^2$

      • $k^2 + 2k + 2 - 1 = (k + 1)^2$

      • $k^2 + 2k + 1 = (k + 1)^2$

  • Try for $n \geq 0$, $5 \mid (n^5 - n)$

Recitation 12

  • Ex:

    • $\sum_{i = 0}^{n} = 2^{n + 1} - 1, n \geq 0$

    • $1 = 2^{0 + 1} - 1 = 1$

    • $\sum_{i = 0}^{k} 2^k \to \sum_{i = 0}^{k + 1} 2^k$

    • $2^{k + 1} - 1 \to 2^{k + 1 + 1} - 1$

    • $2\cdot2^{k + 1} - 1 = 2^{k + 2} - 1$

  • Ex:

    • $\sum_{i = 0}^{n} ar^i = \frac{ar^{n + 1} - a}{r - 1}, r \neq 1, n \geq 0$

    • $ar^0 = a = \frac{ar^1 - a}{r - 1} = \frac{a(r - 1)}{r - 1} = a$

    • if $\sum_{i = 0}^{k} ar^k = \frac{ar^{k + 1} - a}{r - 1}$ then $\sum_{i = 0}^{k + 1} ar^k = \frac{ar^{(k + 1) + 1} - a}{r - 1}$

    • $\left(\sum_{i = 0}^{k+1} ar^k = \frac{ar^{(k + 1) + 1} - a}{r - 1}\right) - \left(\sum_{i = 0}^{k} ar^k = \frac{ar^{k + 1} - a}{r - 1}\right) = ar^{k+1}$

  • Ex: Prove that $57 \mid (7^{n + 2} + 8^{2n + 1}), n \geq 0$

    • $n = 0, 7^2 + 8 = 57$

    • $(57 \mid 7^{k + 2} + 8^{2k + 1}) \to (57 \mid 7^{k + 3} + 8^{2k + 3})$

    • $7\cdot7^{k + 2} + 64\cdot8^{2k + 1}$

    • $7(7^{k + 0} + 8^{2k + 1}) + 57\cdot8^{2k + 1}$

  • Ex: Problem 3.

    • Not Writing This Down

Lecture 38: More Induction

  • Two steps

    • Prove the base case

    • prove the inductive hypothesis

      • define the inductive hypothesis

      • prove the hypothesis

  • Remember to do scratch work.

  • Show that you can create postage using only 4 and 7 cent stamps whene n ≥q 18:

    • 18 = 4 + 7 + 7

    • Show that $P(n) \to P(n + 1)$

    • Show that $(P(1) \land P(2) \cdots \land P(n)) \to P(n + 1)$

    • Show that a specific previous one is true, you can then show that the given is true.

  • This must be proven using strong induction:

    • use this when $S_k \to S_{k + 1}$ is dificult to show.

    • instead of assuming $S_k$ is true and forces $S_{k + 1}$ to be true, we assume that all previous statements are true and together force $S_{k + 1}$ to be true.

    • This can be shown for specific numbers, which allows it to be a bit easier

  • Strong induction can be used to prove the fundamental theorem of arithmetic

Recitation 31

  • Remember to use a proper base case. Also, remember that if a base-case fails, the proof fails.

  • Remember to correctly write your inductive hypothesis and inductive conclusion

  • be very careful with the algebra

  • $IH \to IC$

  • Remember not to cancel things explicitly

  • $n \mid x$ is read as n divides x

  • be very careful with definitions

  • redefinitions are legal, however, always preserve range

Lecture 39: Recursion and Recurrence Relations

  • use forward substitution to solve recurrence relations

    • start with the initial condition $a_1$ and work upward until we reach $a_n$

  • use backward substitution

    • goes backward

    • starts at $a_n$

  • Use induction to prove formulas are the equivalent of a recurrence relation

Lecture 40: More Recursion/Recursive analysis

  • Writing relations for analysis

  • a is times done, b is times split, polynomial is the remainder of the time function

  • Recursion trees

    • number of nodes times cost of each function

    • When we reach the base case, we stop

    • we sum all per-level costs

Lecture 41: Combinatorics

  • The mathemaics of counting

  • counting is the process of giving each object a number to get a total

  • are there any mathematical techniques that bypasses the actual process of counting the objects? — This is combinatorics, sophisticated counting.

  • the study of collections of objects, arrangerment, derangement and he like.

  • we also discuss algorithmic analysis and discrete probabilities.

  • this is often used for gambling

  • collection types:

    • list – ordered collection of objects

    • set – unordered collection of objects

  • two counting problems

    • counting lists

    • counting sets

  • a list is an ordered sequence of objects

  • a different order, but the same elementts is a different list

  • lists can have repeated items

  • a set has no order

  • counting lists:

    • the number of possible lists that satisfy some condition or property

    • number of bitstrings of length seven

    • the product rule

      • length n

      • $a_i$ possibilities at each $i$

      • $a_1 \cdot a_2 \cdot a_3 \cdot\cdots\cdot a_n$ is the value

    • Counting lists with repetition

      • if you allow repetition, it's always $c^n$, where $c$ is the number of choices and $n$ is the length

    • Counting lists without repetition is often of the form $\frac{c!}{(c - n)!}$ where $c$ is the number of choices, and $n$ is the length wanted. In the case $c = n$, the repetition is of the form $n!$

    • factorials allow us to compute the number of total permutations

    • r-permutations are a list of $r$ objects from $n$ options.

Lecture 42: Combinatorics

  • how many reflexive relaions are there on a set with $n$ elements? $2^{n^2 - n}$

  • how many irreflexive relations are there on a set with $n$ elements? $2^{n^2 - n}$

  • counting subsets

    • not the same as counting subsets

    • this is $C(n, r)$, or $\binom{n}{k}$, read as $n$ choose $r$

    • This is represented as $\binom{n}{k} = \frac{n!}{r!(n - r)!}$

  • combinations with repetition is shown as: $$\left(\!\!\binom{n}{k}\!\!\left) = \binom{n + k - 1}{k} = \frac{(n + k - 1)!}{k!(n - 1)!}$$

  • permutations with repetition is shown as: $n^r$