Mathematics for Computer Science By MIT
This is my study notes of MIT6.042J Mathematics for Computer Science offered by MIT OCW. The course covers elementary discrete mathematics for computer science and engineering. It emphasizes mathematical definitions and proofs as well as applicable methods. The notes below contain my summaries, lecture materials, and some assessments answers.
Unit 1: Proofs
1.1 Intro to proofs
有理数
：有限小数/无限循环小数无理数
：无限不循环小数proposition
: a statement that is either true or falsepredicate
(谓词，断言): a proposition whose truth depends on the value of one or more variablesaxiom
(公理): a proposition that is simply accepted as trueproof
: a sequence of logical deductions from axioms and previously proved statements that concludes with the proposition in questiontheorem
(定理): an important true propositionlemma
(引理，辅助定理): a preliminary proposition useful for proving later propositionscorollary
(推论): a proposition that follows in just a few logical steps from a theorem
Let P be a proposition, Q be another proposition.
What is a proposition of the form IF P, THEN Q called?
Implication
IF P, THEN Q is the general form of an implication and is often written as P IMPLIES Q
. Thus, given specific P and Q, P IMPLIES Q is itself a proposition
and can be either true or false.
A fundamental inference rule says:
What is this inference rule called?
Modus Ponens
(演绎推理；肯定前件论式)
What is the statement above the line called?
Antecedent
(前减，先例)
What is the statement below the line called?
consequent/conclusion
Proving a proposition’s contrapositive is as good as (and sometimes easier than) proving the proposition itself.
Which of the following is logically equivalent to the contrapositive
of P IMPLIES Q?
NOT(Q) IMPLIES NOT(P)
Draw a Venn diagram
with P inside of Q.
At the end of a proof, it is customary to write down either the delimiter ___ or the symbol ___.
A proof should begin with “Proof by ...
” and end with “QED
” or ◻
.
Logical deductions
, or inference rules
, are used to prove new propositions using previously proved ones.
A fundamental inference rule is modus ponens
.
A key requirement of an inference rule is that it must be sound
: an assignment of truth values to the letters, P , Q, . . . , that makes all the antecedents true must also make the consequent true. So if we start off with true axioms and apply sound inference rules, everything we prove will also be true.
1.2 Proof methods
Proof by contradiction
often involves clever application of proven knowledge to arrive at a contradiction. In the example proof of 2⁆’s irrationality, what is the key underlying assumption? (We will prove this later in the course!):
The product of two odd numbers is odd.
Proof by cases
might be used when a complicated proof could be broken into cases, where each case is simpler to prove and the cases together cover all possibilities.
1.3 Well Ordering Principle
1.4 Logic & Propositions
Digital Logic
1 ::= T
0 ::= F
. ::= AND
+ ::= OR
1.4.1 Propositional Operators: Video
1.4.2 Propositional Operators
1.4.3 Digital Logic: Video
1.4.4 Truth Tables: Video
A formula is satisfiable
iff it is true in some environment.
A formula is valid
iff it is true in all environments.
e.g.
satisfiable: P, NOT(P)
not satisfiable: (P AND NOT(P))
valid: (P OR NOT(P))
G and H are equivalent
exactly when (G IFF H) is valid.
Verifying Valid, Satisfiable: Truth table size doubles with each additional variable – exponential growth. Makes truth tables impossible when there are hundreds of variables. (In current digital circuits, there are millions of variables.)
1.4.5 Equivalence and Truth Table
1.4.6 Implies: Video
1.4.7 Propositional Logic: Video
Lukasiewicz’ proof system(?)
Algebraic & deduction proofs in general are no better than truth tables. No efficient method for verifying validity is known.
1.4.8 Soundness and Validity
1.4.9 Logical Connectives
1.5 Quantifiers & Predicate Logic
1.5.1 Predicate Logic 1: Quantifiers ∀,∃
Predicate: Propositions with variables.
∀x
For ALL
x; like AND
; (symbol is upside down A)
∃y
There EXISTS
some y; like OR
1.5.2 Predicate Logic 2: Validity & Satisfiability
DeMorgan’s Law
1.5.3 Satisfiability
1.5.4 Predicate Logic 3: ∀ ∃ in English
Power & Limits of Logic
Two Profound Meta Theorems about Mathematical Logic:

(Thm 1) [Gödel’s Completeness Theorem] good news: only need to know a few axioms & rules to prove all valid formulas. (in theory; in practice need lots of rules)

(Thm 2) [Validity is undecidable], Bad News: there is no procedure to determine whether a quantified formula is valid (in contrast to propositional formulas).
1.5.5 Name That Predicate
1.5.6 Quantifiers
1.5.7 Propositions with Quantifiers
1.5.8 Predicate Logic
1.6 Sets
1.6.1 Sets Definitions: Video
Powerset
:
pow({T, F}) = { {T}, {F}, {T, F}, ∅ }
Z ∈ pow(R)
B ∈ pow(A) iff B ⊆ A
1.6.2 Sets Operations: Video
1.6.3 Difference
1.7 Binary Relations
1.7.1 Relations & Functions
A binary relation associates elements of one set called the domain, with elements of another set called the codomain.
Binary relation
R from a set A (domain
) to a set B (codomain
) associates elements of A with elements of B.
Graph(R) ::= the arrows
range(R) ::= elements with arrows coming in = R(A)
定义域 domain f: X>Y Set X is the domain of f, set Y is the codomain of f
上域 codomain （陪域，到达域，靶target，对应域）
值域 range f(X), f(X) is a subset of codomain Y
Functions are relations.
A function
, F, from A to B is a relation which associates each element, a, of A with at most one element of B (called F(a)).
F: A > B is a function IFF F(a) <= 1
IFF a F b AND a F b' IMPLIES b = b'
1.7.2 Range of a Relation
1.7.3 Relational Mappings: Properties (Archery)
surjection
满射, onto, R is a surjection iff R (A) = B (>=1 arrow in)
injection
单射, invective function, onetoone function (<=1 arrow in)
bijection
双射, bijective function, onetoone correspondence (exactly 1 arrow out and 1 arrow in)
A bijective function f: X > Y is a onetoone (injective) and onto (surjective) mapping of a set X to a set Y
A bijection from A to B implies A = B for finite A and B
1.7.4 Total Injection
1.7.5 Finite Cardinality: Video
Mapping problem to counting problem.
“jection” relations:
A bij B ::= ∃bijection:A>B
A surj B ::= ∃surj func:A>B
A inj B ::= ∃total inj relation:A>B
Mapping Lemma:
A bij B IFF A = B
A surj B IFF A ≥ B
A inj B IFF A ≤ B
for finite A, B
1.7.6 A inj B
1.7.7 Total Relations
1.7.8 Surjective Relations
1.7.9 Inverse Relations
1.7.10 In ,Sur, and Bijections
1.7.11 Mapping Lemma: Sizes of Domains and Codomains
1.8 Induction
1.8.1 Induction: Video
1.8.2 Bogus Induction: Video
1.8.3 Same Colored Horses
1.8.4 Strong Induction: Video
1.8.5 Unstacking Game Score
1.8.6 WOP vs Induction: Video [optional]
1.8.7 Strong vs Ordinary Induction vs WOP [optional]
1.8.8 Induction by n+3
1.8.9 Induction Rules
1.8.10 Postage by Induction
1.8.11 A Bogus Induction
1.9 State Machines  Invariants
1.9.1 State Machines Invariants: Video
1.9.2 State Machine Invariants
1.9.3 Derived Variables: Video
1.9.4 Derived Variables and Termination
1.9.5 Integer Multiplication
1.9.6 Chocolate Bars
1.10 Recursive Definition
1.10.1 Recursive Data: Video
1.10.2 Matching Parentheses
1.10.3 Functions of F18
1.10.4 Structural Induction: Video
1.10.5 Structural Induction: Definition
1.10.6 Counting Cases
1.10.7 Recursive Functions: Video
1.11 Infinite Sets
1.11.1 Cardinality: Video
1.11.2 Cantor, SchroederBernstein
1.11.3 Countable Sets: Video
1.11.4 Cantor’s Theorem: Video
1.11.5 Cantor’s Diagonal Argument
1.11.6 Countable and Uncountable Sets
1.11.7 The Halting Problem: Video [Optional]
1.11.8 Halting Problem Basics [Optional]
1.11.9 Russell’s Paradox: Video
1.11.10 Russell’s Paradox [and ZFC optional]
1.11.11 Set Theory Axioms: Video [Optional]
1.11.12 Set Theory Axioms [Optional]
Unit 2. Structures
2.1 GCDs
2.1.1 GCDs & Linear Combinations: Video
2.1.2 Euclidean Algorithm: Video
2.1.3 Run Euclid Run
2.1.4 Pulverizer: Video
2.1.5 GCDs I
2.1.6 Revisiting Die Hard: Video
2.1.7 Prime Factorization: Video
2.1.8 Unique Primes
2.1.9 Divisors
2.1.10 GCDs II
2.2 Congruences
2.2.1 Congruence mod n: Video
2.2.2 Divisibility and Congruence
2.2.3 Inverses mod n: Video
2.2.4 Inverses mod n
2.2.5 Multiplicative Inverses
2.2.6 Inverses With Linear Combinations
2.3 Euler’s Theorem
2.3.1 Modular Exponentiation Euler’s Function: Video
2.3.2 Euler’s Totient Function
2.3.3 The Ring Z: Video
2.3.4 The Ring
2.3.5 Z mod n
2.3.6 Fermat’s Little Theorem
2.3.7 Euler’s Theorem
2.4 RSA Encryption
2.4.1 RSA Public Key Encryption: Video
2.4.2 RSA Encryption
2.4.3 Reducing Factoring To SAT: Video
2.4.4 Relative Primality
2.4.5 RSA computations
2.5 Digraphs: Walks & Paths
2.5.1 Digraphs: Walks & Paths: Video
2.5.2 Walks and Paths
2.5.3 Digraphs: Connected Vertices: Video
2.5.4 Longest Path
2.5.5 Adjacency Matrix
2.5.6 Counting Paths
2.6 Directed Acyclic Graphs (DAGs) & Scheduling
2.6.1 DAGs: Video
2.6.2 DAGs
2.6.3 Scheduling: Video
2.6.4 Scheduling Prerequisites
2.6.5 Time versus Processors: Video
2.6.6 Processor Time Bounds
2.6.7 The Divisibility DAG
2.7 Partial Orders and Equivalence
2.7.1 Partial Orders: Video
Transitivity
:
Theorem: R is a transitive iff R = G+ for some digraph G.
Strict partial order (SPO):
Theorem: R is a SPO iff R = D+ for some DAG D.
Linear orders: Given any two elements, one will be “bigger than” the other one.
Reflexivity: relation R on set A is reflexive iff a R a for all a ∈A, G* is reflexive. implies everything is related to itself.
Antisymmetry: binary relation R is antisymmetric iff it is asymmetric except for a R a case.
Asymmetry: aRa is never allowed; implies nothing is related to itself.
Weak partial orders (WPO):
 same as a strict partial order R, except that a R a always hold.
 transitive & antisymmetric & reflexive
 Theorem: R is a WPO iff R = D* for some DAG D