---
# System prepended metadata

title: 離散 part1

---

---
title: 離散 part1
---
{%hackmd @NTNUCSIE112/DM_card %}

# Logic and proofs
Ch.1 The Foundations: Logic and Proofs

Reading assigned: 1.1, 1.3, 1.4, 1.5, 1.7, 1.8
## 1.1 Propositional Logic 命題邏輯
"Sentence": which are either True or False
### Logic operations 邏輯運算
設 $P,Q$ 為兩個敘述
+ **AND** $(\land)$ 
$(P\land Q)$ 為真，若 $P$ 和 $Q$ 皆為真
+ **OR** $(\lor)$ 
$(P\lor Q)$ 為真，若 $P$ 或 $Q$ 其中一個為真
+ **NOT** $(\neg)$
$\neg P$ 為真，若 $P$ 為假
+ **Implication** $(\implies)$
$P\implies Q$ 為真，若 $P$ 為假或 $(P\land Q)$ 為真
    + If $P$ is true, then $Q$ is true. 
    若 $P$ 則 $Q$
    + $Q$ is the necessary condition of $P$.
    $Q$ 為 $P$ 的必要條件
    + $P$ is the sufficient condition of $Q$.
    $P$ 為 $Q$ 的充分條件

### Truth table
| $P$ | $Q$ | $P\implies Q$ | $\lnot Q \implies \lnot P$ | $\lnot P \implies \lnot Q$ | $\lnot P \lor Q$ |
| --- | --- |:-------------:|:--------------------------:|:--------------------------:|:----------------:|
|  T  |  T  |  T  |  T  |  T  |  T  |
|  T  |  F  |  F  |  T  |  F  |  F  |
|  F  |  T  |  T  |  F  |  T  |  T  |
|  F  |  F  |  T  |  T  |  T  |  T  |

### 1.1.4 Truth Tables of Compound Propositions
一步步建構每個 Compound expression
### 1.1.6 Logic and Bit Operations
| $x$ | $y$ | $x\lor y$ | $x\land y$ | $x\oplus y$ |
| --- | --- | --------- | ---------- | ----------- |
| 0   | 0   | 0         | 0          | 0           |
| 0   | 1   | 1         | 0          | 1           |
| 1   | 0   | 1         | 0          | 1           |
| 1   | 1   | 1         | 1          | 0            |
## 1.3 Propositional Equivalences 等值命題
### 1.3.1 Introduction
1. *tautology* 恆真句: a compound proposition always true
2. *contradiction* 矛盾句: always false
3. *contingency* 適真句: neither tautology nor contradiction 
### **Equivalence** 等價
$P\iff Q$ 為真，若 $P\implies Q$ 和 $Q\implies P$ 皆為真
    + $P$ if and only if $Q$
    $P$ i.f.f. $Q$、$P$ 若且唯若 $Q$
    + $P$ is equivalent to $Q$
    $P$ 和 $Q$ 等價
    + $Q$ is the necessary and sufficient condition of $P$.
    $P$ 為 $Q$ 的充分必要條件
### Conditional-disjunction Equivalence
$p\to q \equiv \lnot p\lor q$ 
### De Morgan's Law
$\lnot (p\lor q) \equiv \lnot p \land \lnot q$

$\lnot (p\land q) \equiv \lnot p \lor \lnot q$
## 1.4 Predicates and Quantifiers 述詞與量詞
### Predicate Logic (First Order Logic)
+ Predicate (述語) 
a sentence that contains a variable.
    + The truth value varies depending on the variables.
+ Quantifier (量詞)
    + universal quantifier ($\forall$ $\rightarrow$ for all)
    + existential quantifier ($\exists$ $\rightarrow$ there exist some)
## 1.5 Nested Quantifiers 嵌套量詞
| 先 column 後 row | $\forall x$ | $\forall y$ | $\exists x$ | $\exists y$ |
| ---------------- | ----------- | ----------- | ----------- | ----------- |
| $\forall x$      |             |             |             |             |
| $\forall y$      |             |             |             |             |
| $\exists x$      |             |             |             |             |
| $\exists y$      |             |             |             |             |
<!--  不知道怎麼打 放棄 -->
從前往後念

## 1.7 Introduction to Proofs 證明簡介


**敘述1** Let $n$ be an integer. If $n$ is an odd number, then $n^2$ is also odd.
$proof$ 
設 $n=2k+1$，$n^2=4k^2+4k+1$
$\because 4k^2 和 4k$ 皆必為偶數，$\therefore n^2$為奇數

**敘述2** Let $n^2$ be an integer. If $n$ is an odd number, then $n$ is also odd.
$proof$
($n^2$ is odd $\implies$ $n$ is odd) $\iff$ ($n$ is even $\implies$ $n^2$ is even)
$(P\rightarrow Q)\leftrightarrow(\lnot Q\rightarrow \lnot P)$



## Proof stategies
+ Direct proof（直接證明）
+ Proof by contraposition（換句話說）
+ Proof by contradiction（反證法）

### Example. 證明 $\sqrt2$ 為無理數

rational number: $\frac{a}{b}$, $a, b \in \mathbb{Z}$, $b\neq 0$  

如果 $\sqrt 2$ 為有理數，

then $\sqrt{2} = {a\over b}$ (assume $gcd(a,b) = 1$)

$\implies 2 = {a^2\over b^2} \implies 2b^2 = a^2 \implies a^2$ $is$ $even$

$\implies a$ $is$ $even$ $\implies a = 2k , k \in Z$

$a = 2k$

$\implies a^2 = 4k^2 = 2b^2$

$\implies b^2 = 2k^2 \implies b$ $is$ $even$

## 1.8 Proof Methods and Strategy 證明的方式與策略
# Set
Ch.2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices
## 2.1 Sets
- the 1st paper is given by Cantor at 1874. ( the beginning of set theory)
- Set representation:
    - roster method(listing all elements in the set): e.g.{a, b, c, d, e}
    - set comprehension: $S = \{x|x \text{ has prperty } P\}$
        - $S$ is the set of all elements x such that x has property P.
        - e.g. $S = \{x \in N | 0<x<5 \}$
- Set serves as the primitive concept of most fields(in mathematics)
    - Gottlob Frege 1900s
    - Bertrand Russell
        - Russell's paradox: Let $S = \{X|X \text{ is a set and }X\notin X\}$ 
        - Question: Is $S \in S$ or $S\notin S$

$S = \{1,2\},1\in S,2\in S,3\notin S,\{1\}\notin S$
## 2.2 Set Operations
