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 false
• predicate(谓词，断言): a proposition whose truth depends on the value of one or more variables
• axiom(公理): a proposition that is simply accepted as true
• proof: a sequence of logical deductions from axioms and previously proved statements that concludes with the proposition in question
• theorem(定理): an important true proposition
• lemma(引理，辅助定理): a preliminary proposition useful for proving later propositions
• corollary(推论): 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.4 Logic & Propositions

### Digital Logic

1 ::= T
0 ::= F
. ::= AND
+ ::= OR


### 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.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.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

DeMorgan’s Law

### 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.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.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



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.3 Relational Mappings: Properties (Archery)

surjection 满射, onto, R is a surjection iff R (A) = B (>=1 arrow in)

injection 单射, invective function, one-to-one function (<=1 arrow in)

bijection 双射, bijective function, one-to-one correspondence (exactly 1 arrow out and 1 arrow in)

A bijective function f: X -> Y is a one-to-one (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.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


# Unit 2. Structures

## 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