离散数学

Representation

Set: no order

1. set roster notation: \(\{1, 2, 3\}\)
2. set builder notation: \(\{x|P(x)\}\), P means Property

Empty set:

1. \(\phi \subset \{1,2,3\}\) is vacuously true. （空真）

---

Ordered Pairs

(a, b, c): order matters

a, b, c : can be different type of elements

Cartesian Product: 笛卡尔积

\(A × B\) ： is all ordered pairs (a, b) where a \(\in\) A, b \(\in\) B.

• \(\{a,b\} × \{0,1\}\) = { (a, 0), (a, 1), (b, 0), (b, 1) }
• A point in a two-dimensional coordinate system can be represented by \(R \times R\). 二维坐标系中的点可表示为 \(R \times R\)

---

Relations

• Def:

  ​ A relation R between A and B is a subset of \(A \times B\).

---

Function

• Def:

  ​ A function F between A and B is a relation between A and B such that:

  • for every \(x \in A\) there is a \(y \in B\) such that \((x,y) \in F\)
  • if \((x,y)\in F \ and \ (x,z) \in F\) then \(y=z\)

Ex: \(x^2 + y^2 = 1\) is not a function in Discrete Math domain definition.

---

Statement

• Def:

  ​ A sentence that is either True or False.

• Combine Form:

  1. \(\lnot p\)
  2. \(p \land q\)
  3. \(p\lor q\)

Ex 1:

​ "My shirt is gray but my shorts are not."

​ p: "my shirt is gray", q: "my shorts are gray"

​ ~q: "my shorts are not gray"

​ the result logic form: \(p \land \lnot q\)

Truth table

p	q	\(\lnot p\)	\(p \land q\)	\(p\lor q\)
T	T	F	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	F

Logically equivalent

• Def:

  ​ Two statements have the same truth table.

Ex: \(p \equiv \lnot(\lnot p)\)

Tautology

• Def:

  ​ A tautology is a statement that is always True.

Contradiction

• Def:

  ​ A contradiction is a statement that is always False.

Basic Laws

Obvious but useful

1. DeMorgan`s Law:

   \(\lnot(p \land q) \equiv (\lnot p) \lor (\lnot) q\)

   \(\lnot(p \lor q) \equiv (\lnot p) \land (\lnot) q\)

2. Identity Laws:

   \(p \lor contradiction \equiv p\)

   \(p \land tautology \equiv p\)

3. Universal Bound Laws:

   \(p \land contradiction \equiv contradiction\)

   \(p \lor tautology \equiv tautology\)

Ex: \[ \begin{align*} (\lnot(p \lor \lnot q)) \land tautology(t) & \\ (DeMorgan`s\ Law) & \equiv (\lnot p \land \lnot(\lnot q)) \land t \\ (Double\ Negative) & \equiv (\lnot p \land q) \land t \\ (Identity) & \equiv \lnot p \land q \end{align*} \]

---

Conditional statements

• Def:

  ​ \(p \to q\) means "if p is True then q is True"

  p	q	\(p \to q\)	\(\lnot p \lor q\)
  T	T	T	T
  T	F	F	F
  F	T	T(vacuously true)	T
  F	F	T(vacuously true)	T

  If p is false, then I didn`t have a assumption indeed. Think it as a vacuously true statement.

Vacuously true statement

• When the hypothesis (\(p\)) is false.

  Ex: if I am a pig, then the world will be better.

  ​ equal form: Either I am not a pig, or the world will be better.

  ​ "I am not a pig.". It is vacuously true, anyway. So the whole statement is True.

Negating a conditional

• \(\lnot (p \to q) \equiv \lnot (\lnot p \lor q)\)

\[ \begin{align*} \lnot (\lnot p \lor q) & \equiv (\lnot \lnot p \land \lnot q) \\ & \equiv p \land \lnot q \end{align*} \]

Contrapositive of a statement

• Def:

  ​ \(p \to q \equiv \lnot q \to \lnot p\)

  equal form: \(\lnot p \lor q \equiv q \lor \lnot p\)

Converse of a statement

• Def:

  ​ Converse of \(p \to q\) is \(q \to p\). Not necessarily logically equivalent.

Inverse of a statement

• Def:

  ​ Inverse of \(p \to q\) is \(\lnot p \to \lnot q\).

  Cause the contrapositive is \(\lnot q \to \lnot p\) which is the converse of \(\lnot p \to \lnot q\), so:

  the inverse of \(p \to q\) is the converse of the contrapositive of \(p \to q\).

---

Biconditional

• Def:

  ​ \(p \leftrightarrow q\) means \(p \to q\) and \(q \to p\).

  Ex: I will pass the exam if and only if I study hard.

  ​ It means biconditional.

---

Logic Arguments

• Def:

  ​ A valid argument is a list of premises from which the conclusion follows.

  premises: statements.

Modus Ponens: 肯定前件推理

if \(p\), then \(q\)

\(p\)

therefore \(q\)

p	q	\(p \to q\)(premises)	p(premises)	conclusion
T	T	T	T	T
T	F	F	\(\boxtimes\)	\(\boxtimes\)
F	T	T	\(\boxtimes\)	\(\boxtimes\)
F	F	T	\(\boxtimes\)	\(\boxtimes\)

We focus on where premises is true.

Modus Tollens: 否定后件推理

if \(p\), then \(q\)

\(\lnot q\)

therefore \(\lnot p\)

We focus on where premises is true.

Generalization

\(p\) (True)

therefore, \(p \lor q\)

Specialization

\(p \land q\) (True)

therefore, \(p\)

Contradiction

\(\lnot p \to contradiction\)

therefore, \(p\)

Predicate

• Def:

  ​ A predicate(谓词) is a statement depending on variables which becomes a statement upon substituting values in the domain.

  Ex:

  ​ P(x): x is the variable that is a factor of 12 with domain \(Z^+\).

  P(x) is a predicate. When x = 6, P(6) is True. When x = 7, P(7) is False.

True set

• Def:

  ​ It is a predicate P(x) satisfies that \(\{x \in D | P(x)\ is\ True\}\)

Universal Quantifier

• \(\forall\) means "for all".

  \(\forall x \in D, P(x)\) means: For all x in domain D, \(P(x)\) is True.

  Ex:

  ​ Every dog is mammal.

  D is the dog domain, P(x) means x is a mammal.

Existential Quantifier

• \(\exists\) mean "there exists"

  \(\exists x \in D, P(x)\) means: There exists x in the domain, such that P(x) is True.

  Ex:

  ​ Some person is the oldest in the world.

  D is people in the world. P(x) means that x is the oldest.

Summary

1. P: "The earth is round." -> Statement
2. P(x): "x is round." -> Predicate
3. Q: \(\forall x \in D, P(x)\): "Every dog is a mammal." -> Statement
4. Q: \(\exists x \in D, P(x)\): "Some person is the oldest in the world." -> Statement

Negate Quantifier

For example, we have "\(\forall x \in Z^+, x > 4\)".

Negate the quantifier: \[ \lnot(\forall x \in D, P(x)) \equiv (\exists x \in D, \lnot P(x)) \] So, for the example, we have "\(\exists x \in Z^+, x \leqslant 4\)".

Ex:

​ Every integer has a larger integer.

It is \(\forall x \in Z, P(x): (\exists y \in Z, P(y): (y > x))\).

Negate it, we have \(\exists x \in Z, (\forall y \in Z, y \leqslant x)\), which can`t be True.

Ex:

​ Some number in D is the largest.

It is \(\exists x \in D, (\forall y \in D, x \geqslant y)\).

Negate it, we have \(\forall x \in D, (\exists y \in D, x < y)\)

Conditional Predicate

Universal-Conditionals

• Def:

  ​ \(P(x) \Rightarrow Q(x)\) means \(\forall x \in D, P(x) \to Q(x)\ is\ True\).

Ex:

​ If x is a dog, then x is a mammal.

D maybe all possible animals.

Sufficient Condition

• Def:

  ​ If \(A(x)\) , then \(B(x)\). We have \(A(x)\) is a sufficient condition for \(B(x)\).

Necessary Condition

• Def:

  ​ If $ A(x)$ , then $ B(x)$. We have \(A(x)\) is a necessary condition for \(B(x)\).

Use contrapositive statement to explain above definition.

Proof

• Precisely define even & odd integers

  n is even integer if \(\exists k \in Z\), such that \(n=2k\).

  n is odd integer if \(\exists k \in Z\), such that \(n=2k+1\).

Theorem 1 to proof

An even integer plus an odd integer is another odd integer.

Proof

Assumption:

​ Suppose m is even and n is odd.

Definitions:

​ \(\exists k_1 \in Z \ and \ \exists k_2 \in Z\) , so that \(m = 2*k_1\) and \(n=2*k_2+1\).

Manipulate: Then, \[ \begin{align*} m+n & = 2k_1+2k_2+1 \\ & = 2(k_1+k_2) + 1 \end{align*} \] Definitions: Thus,

​ \(\exists k_3 \in Z\) so that \(m+n=2k_3+1\).

Conclusion:

​ Thus \(m+n\) is odd.

Theorem 2 to proof

An even integer times an even integer is another even integer.

Proof:

Formally stated theorem:

​ \(\forall m,n \in Z\) if m, n are even, then \(mn\) is even.

Assumption:

​ Suppose m, n are even.

Definition:

​ \(\exists k_1, k_2 \in Z\) so that \(m = 2k_1, n=2k_2\).

Manipulation: \[ \begin{align*} mn & = 2k_1 *2k_2 \\ & = 2(2*k_1*k_2) \end{align*} \] Definition:

​ Let t = \(2k_1k_2\), \(t \in Z\).

Conclusion:

​ Thus, \(mn\) is even.

Proof by counterexample

Aim is prove \(P(x) \Rightarrow Q(x)\) is false.

To do that find one \(a \in D\) where \(P(a) \land \lnot Q(a)\) is true.

Proof by division into class

Divide the theorem into different cases.

Proof by contradiction

1. Suppose \(\lnot p\) is true;
2. Find a contradiction like 0 = 1;
3. Therefore, \(p\) is true.

\(\lnot p \to contradiction\)

therefore, \(p\)

Proof by contrapositive

\(p \to q \equiv \lnot q \to \lnot p\)

1. Goal: prove \(P(x) \Rightarrow Q(x)\).
2. Instead, prove: \(\lnot Q(x) \Rightarrow \lnot P(x)\).

Sequence

Def:

​ A sequence is a function \(f: Z^+ \to C\).

Ex:

​ \(f(k) = (-1)^k(3*k)\)

Induction

Goal: prove \(P(n), \forall n \geqslant 1\).

Step 1: prove \(P(a), P(b), ...,P(x)\) is true.

Step 2: Assume \(P(k)\) is true, Prove \(P(k+1)\) is true, \(x < k\).

Skipped things

Relations of Sets.

Permutation and combination.

Bayes` theorem.

Markov Chain.

Graph

Def:

​ A graph (V, E) has a set V called "vertices" and a set E called "edges" that consisting of two-element subsets of V.

Ex:

​ \(V = \{A,B,C,D\}\)

​ \(E = \{\{A,B\}, \{B,A\}, \{B,D\}, \{D,B\}, \{B,C\}, \{C,D\}, \{A,C\}\}\)

Complete Graph

Def:

​ A simple undirected graph in which every pair of distinct vertices is connected by a unique edge. The notation is \(K_n\). The edge number is \(\frac {n(n-1)}{2}\).

Connected Graph

Def:

​ A graph is connected if you can get from any vertex to any other via edges.

Induced Subgraph

Def:

​ \((V_1, E_1)\) is an induced subgraph of \((V_2,E_2)\) if it is a graph where \(V_1 \subseteq V_2\) and \(E_1\) contains all possible edges consisting of vertices in \(V_1\) and \(E_1 \subset E_2\).

Degree

Def:

​ The degree of a vertex is the number of edges attached.

Fact:

​ Sum of degrees of all vertices is even. Cause every edge adds 2 degrees.

Ex:

​ Among 5 people, could everyone be friends with exactly 2 people?

The degree is \(5 * 2=10\), it`s possible.

​ Among 5 people, could everyone be friends with exactly 3 people?

The degree is \(5 * 3=15\), it`s not possible.

Euler Path

Def:

​ An Euler Path walks through a graph using every edge exactly once.

​ An Euler Circuit starts and stops at the same vertex when walking through a Euler Path.

Theorem:

​ If a graph has an Euler Circuit, then every vertex has even degree.

Contrapositive Theorem:

​ If a graph has a vertex with odd degree, no Euler Circuit is possible.