###### tags: `離散數學`

:::info
[回共筆首頁](https://hackmd.io/zrsmsRtEQ-OrnGslDxT0NQ)
[回科目首頁](https://hackmd.io/OwMjUy0fRq2kEuCRiMwtkQ)
:::

# 1. The Foundations: Logic and Proofs

## Section 1.1: Propositional Logic

### Propositions
- A proposition is a declarative sentence that is **either true or fales**.有明確的真假值，才會說這個狀況是Proposition。

- Propositional Logic
- Compound Propositions
- Negation ($\neg$): NOT
- Conjunction ($\land$): AND
- Disjunction ($\lor$): OR
- Implication ($\implies$): If p, then q.
- Biconditional ($\iff$): p if and only if q. 若且唯若，兩個都成立，或是兩個都不成立

#### Implication
Example: "If you get 100% on the final, then you will get an A."
假如你得到100 => 你就會拿A => T
假如你得到100 => 你沒有拿到A => F (在說謊)
假如你沒有得到100 => ?(不重要) => T (不管結果如何，因為前提沒有成立，都還是對的)

:::danger
- if p, then q
- if p, q
- q unless (not)p
- q if p
- q whenever p
- q follows from p
- p implies q
- p only if q
- q when p
- p is sufficient for q
- q is necessary for p
- a necessary condition for p is q
- a sufficient condition for q is p
:::

### Connectives

### Truth Tables

## Section 1.2: Applications of Propositional Logic

### Consistent
- Definition: A list of propositions is **consustent** if it is possible to assign truth value to proposition varibales so that each **proposition is true**.
- 跟Satisfiable不同的地方是，Consistent是全部狀況都為True，Satisfiable是只有一個為真。

### Logic Puzzle
- 一個城裡也兩種人，knights騎士，knaves惡棍，騎士只講實話，惡棍只講謊話
- 有A跟B兩人
- A說：「B是騎士」
- B說：「我跟A相反的人」
- A跟B是哪種人？

## Section 1.3: Propositional Equivalences
- tautology => 永遠為真
- contradiction => 永遠為假，矛盾的情況
- contingency => 不是tautology，也不是contradiction，代表有真有假

### Logically Equivalent
:::danger
- **$\neg\,$p $\lor$ q** $\equiv$ **p $\implies$ q**
- **p $\implies$ q** $\equiv$ **$\neg\,$p $\lor$ q**
:::
- De Morgan's Laws
- Consistent => **多個**Compound Propositions，有一種情況可以滿足所有的Propositions都為True，則為Consistent。
- Satisfiability => **一個**Compound Proposition，有一種情況可以滿足Proposition為True，則為Satisfiable，反之為Unsatisfiable。

### 要會證明

## Section 1.4: Predicates and Quantifiers

### Predicate Logic
- Variables: x,y,z
- Predicates: P(x), M(x)
- Quantifiers:

Domain is denoted by ***U***

### Example of Propositional Functions
- Let "x+y=z" be denoted by R(x,y,z) and U(for all three varibles) be the intergers. Find these truth values:
- R(2,-1,5) **Solution: F**
- R(3,4,7) **Solution: T**
- R(x,3,z) **Solution: Not a Proposition**

### Quantifers
- To express the meaning of English words includiong all and some:
- "All men are Mortal."
- "Some cats do not have fun."

- The two most important quantifiers are:
- **Universal Quantifier**, "For all," symbol: $\forall$
- **Existential Quantifier**, "There exists," symbol: $\exists$

### Precedence of Quantifiers
- The quantifiers $\forall$ and $\exists$ have higher precedence than all the logic operators.

### Translating from English to Logic
- "every student in this class has taken a course in Java."
- $\forall$x(S(x) $\implies$ J(x))
- 如果有人不是這們課的學生，不管有沒有修過Java課，都不會影響原句的意思，因為只要S(x)成立，就看J(x)成立或不成立，才會影響
- "Some student in this class has taken a course in Java."
- $\exists$x(S(x) $\land$ J(x))
### De Morgan's Laws for Quantifiers
- ### $\neg$$\forall$xP(x) $\equiv$ $\exists$x$\neg$P(x)
- ### $\neg$$\exists$xP(x) $\equiv$ $\forall$x$\neg$P(x)

## Section 1.5: Nested Quantifiers
### Nested Quantifiers
- "Every real number has an inverse"
- $\forall x\exists y(x+y = 0)$
- Domains of x and y are the real numbers.

### Quantifications of Two Variables

### Questions on Translation from English

## Section 1.6: Rule of Inference 推論的法則
從前提推出結果
### Valid Arguments
1. Propoaitional Logic
Inference Rules
2. Predicate Logic
Inference rules for propositional logic plus additional inference rules to handle variables and quantifiers.
:::warning
- Propositional Logic 有明確的真假值的敘述
- Prodicate Logic 並沒有馬上看的出來的真假值，但是可以比較好去描述一個subjectc或variable，當帶入特定的值，就會轉變成Propositional。也要去規範Predicate的定義域(Domain)
:::

### Arguments in Propositional Logic
- 所有的proposition，除了最後一個以外，都叫做**premises**，最後一個叫做**conclusion**
- The arugument is **valid** if the premises imply the conclusion.

### Modus Ponens

### Modus Tollens

### Hypothetical Syllogism

### Disjunctive Syllogism

### Addition

### Simplification

### Conjunction

### Resolution

### Universal Instantiation (UI)

### Universal Generalization (UG)

### Exitential Instantiation (EI)

### Exitential Generalization (EG)

### Universal Modus Ponens (UI + MP)

## Section 1.7: Intruduction to Proods
### Definitions
- theorem 定理 => 說明某件事是對的
- axioms 公理
- lemma 引理
- corollary 推論
- conjecture 猜測 => 認為是對的，但還沒證明出來

### Proving Conditional Statements: p->q
- Trivial Proof
- Vacuous Proof
- Direct Proof
- Proof by Contraposition = indirect proof
- **p $\implies$ q** $\equiv$ **$\neg\,$p $\lor$ q**
- Proof by Contradiction 矛盾證法 => 假設前提不成立

## Section 1.8: Proof Methods and Strategy
### Without Loss of Generality(WLOG)
若兩種情況，令x為這種情況，y令為另外一種情況
且不失一般性(Without Loss of Generality)
x, y的假設倒過來時，結果也會成立。

### Nonconstructive Existence Proofs
- assume no c exists which makes $P(c)$ true and derive a **contradiction**
- 矛盾證法，假設不存在

### Proof Strategies for proving: p->q
- forward reasoning
- backward reasoning

### Counterexamples (反例)
利用反例證明假設不成立