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