{%hackmd @RintarouTW/About %}

# Logic

### 3.1 Propositions and Logical Operators

:::info
Proposition(主張): A proposition is a sentence to which one and only one of the terms **true** or **false** can be meaningfully applied.
:::

Example:

“Four is even,”, “4 ∈ {1, 3, 5}” and “43 > 21” are propositions

### 3.1.2 Logical Operations

Suppose $p, q$ are propositions.

#### Logical Conjunction
$p\ and\ q \iff p\land q$

| p | q | $p\land q$ |
|---|---| ---------- |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

#### Logical Disjunction
$p\ or\ q \iff p\lor q$

| p | q | $p\lor q$ |
|---|---| ---------- |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |

#### Logical Negation
$not\ p \iff \lnot p$

| p | $\lnot p$ |
|---| ---------- |
| 0 | 1 |
| 1 | 0 |

#### Conditional Statement
If $p$, then $q$, denoted "$p\rightarrow q$".

| p | q | $p\rightarrow q$ |
|---|---| ---------- |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 (this is ruled out)|
| 1 | 1 | 1 |

:::info
When we write "$p\rightarrow q$", it means "if p is true, then q must be true.", so the case that p = 1 and q = 0 is ruled out.
:::

#### Converse

The converse of $p\rightarrow q$ is $q\rightarrow q$.
But this would be a different thing.

#### Contrapositive

The contrapositive of the proposition $p\rightarrow q$ is "$\lnot q\rightarrow \lnot p$".

#### Biconditional Proposition

if and only if = iff
$p\iff q$ : if $p$ then $q$, also if $q$ then $p$, $p$ is equivalent to $q$.

| p | q | $p\iff q$ |
|---|---| ---------- |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

### Propositions Generated by a Set

:::info
Let S be any set of propositions. A proposition generated by S is any valid combination of propositions in S with conjunction, disjunction, and negation. Or, to be more precise,
(a) If p ∈ S, then p is a proposition generated by S, and
(b) If x and y are propositions generated by S, then so are (x), ¬x, x ∨ y , and x∧y.
:::

### Equivalence and Implication

$$
\cases{
\lnot (p\land q) \iff \lnot p\lor \lnot q\\
}
$$

:::info
Tautology: An expression involving logical variables that is true in all cases is a tautology. The number 1 is used to symbolize a tautology.
ex:
$$
\cases{
p\lor \lnot p\\
p\land q\rightarrow p\\
q\rightarrow p\lor q
}
$$
Contradiction: An expression involving logical variables that is false for all cases is called a contradiction. The number 0 is used to symbolize a contradiction.
ex:
$$
p\land \lnot p
$$

Equivalence: Let S be a set of propositions and let r and s be propositions generated by S. r and s are equivalent if and only if r ↔ s is a tautology. The equivalence of r and s is denoted r $\iff$ s.
ex:
$$
\cases{
(p\land q)\lor(\lnot p\land q)\iff q\\
p\rightarrow q\iff \lnot q\rightarrow \lnot p\\
p\lor q\iff q\lor p\\
p\lor\lnot p\iff 1\\
p\land\lnot p\iff 0
}
$$
:::

Implication

:::info
Implication: Let S be a set of propositions and let r and s be propositions generated by S. We say that r implies s if r → s is a tautology. We write r ⇒ s to indicate this implication.
ex: Disjuctive Addition
$$
p\implies p\lor q
$$
:::

#### A Universal Operation

The Sheffer Stroke: $p\mid q$

| p | q | $p\mid q$ | $p\land q$ | $p\lor q$ |
|---|---| ---------- |---| ---|
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |

and : 有 0 則 0 (皆 1 方 1)
or : 有 1 則 1 (皆 0 方 0)
sheffer : 有 0 則 1 (皆 1 方 0)

:::info
$p\land q \iff \lnot (p\mid q)$
$p\lor q \iff \lnot p\lor \lnot q$
$\lnot p\iff p\mid p$
$p\rightarrow q\iff \lnot p\lor q$
:::

## The Laws of Logic

:::info
duality principle
:::

Basic Logical Laws - Equivalences

|$\lor$ |$\land$ | Name of Law |
|-|-|-|
| $p\lor q\iff q\lor p$ | $p\land q \iff q\land p$| Communitive Law |
| $(p\lor q)\lor r\iff p\lor(q\lor r)$ | $(p\land q)\land r\iff p\land(q\land r)$ | Associative Law |
| $p\lor(q\land r)\iff (p\lor q)\land(p\lor r)$ | $p\land(q\lor r)\iff (p\land q)\lor(p\land r)$ | Distributive Law |
| $p\lor 0\iff p$ | $p\land 1\iff p$ | Identity Law |
| $p\lor \lnot p\iff 1$ | $p\land \lnot p\iff 0$ | Negation Law |
| $p\lor p\iff p$ | $p\land p\iff p$ | Idempotent Law |
| $p\lor 1\iff 1$ | $p\land 0\iff 0$ | Null Law |
| $p\lor (p\land q)\iff p$ | $p\land(p\lor q)\iff p$ | Absorption Law |
| $\lnot(p\lor q)\iff\lnot p\land \lnot q$ | $\lnot(p\land q)\iff\lnot p\lor\lnot q$ | DeMorgan's Law |
| $\lnot(\lnot p)\iff p$ || Involution Law |

### Basic Logical Laws - Common Implications and Equivalences
| | |
|-|-|
|Detachment|$(p\rightarrow q)\land p\implies q$|
|Contrapositive|$p\rightarrow q\iff\lnot q\rightarrow\lnot p$|
|Indirect Reasoning|$(p\rightarrow q)\land\lnot q\implies \lnot p$ ($\because p\rightarrow q\iff \lnot q\rightarrow \lnot p$)|
|Disjunctive Addition|$p\implies p\lor q$|
|Conjunctive Simplification|$p\land q\implies p$ ; $p\land q\implies q$|
|Disjunctive Simplification|$(p\lor q)\land\lnot p\implies q$ ; $(p\lor q)\land\lnot q\implies p$|
|Chain Rule|$(p\rightarrow q)\land (q\rightarrow r)\implies p\rightarrow r$|
|Conditional Equivalence|$p\rightarrow q\iff \lnot p\lor q$ (當 p 成立時，q 必需成立，否則 $\lnot p\lor q$ 就不成立。)|
|Biconditional Equivalence|$p\leftrightarrow q\iff(p\rightarrow q)\land(q\rightarrow p)\iff (p\land q)\lor(\lnot p\land \lnot q)$|

### Mathematical Systems and Proof

- A set or universe, U.
- Definitions
- Axioms
- Theorems: A true proposition derived from the axioms of a mathematical system is called a theorem.
p1 ∧ p2 ∧ · · · ∧ pn ⇒ Conclusion

:::info
Proof: A proof of a theorem is a finite sequence of logically valid steps that demonstrate that the premises of a theorem imply its conclusion.
:::

###### tags: `math` `logic`