- 命題論理・述語論理
- 条件・性質・集合
- 命題・述語・集合
- 白馬は馬にあらず
- ２変数の命題関数
- 自由変数と束縛変数
- 演繹
- 真理値表
- ド・モルガンの法則
- 同値式
命題論理・述語論理
| 命題論理 | ⇒ ∧ ∨ ￢ |
|---|---|
| 述語論理 | ∀ ∃ |
| ∀xF(x) | すべてのxに対してF(x) |
| ∃xF(x) | F(x)というxが存在する |
| ∀x(F(x) ⇒ G(x)) | すべてのFはGである |
| ∃x(F(x) ∧ G(x)) |
或るFはGである （FであってGであるものが存在する） |
条件・性質・集合
FならばG
| 条件 |
|
|---|---|
| 性質 |
|
| 集合 |
|
白馬は馬にあらず
| ∀x( F(x) ⇒ ￢G(x) ) | Fは必ずGではない | すべてのxについて、xがFのときxはGではない。 |
| ￢∀x( F(x) ⇒ G(x) ) | Fは必ずしもGではない | 「すべてのxについて、xがFのときxはGでもある」とは言えない。 |
| ∀x( F(x) ⇔ ￢G(x) ) | FとはGでないということである | |
| ￢∀x( F(x) ⇔ G(x) ) | FとGとは違う概念である |
２変数の命題関数
| F(x, y) | …２変数x,yの命題関数 | |||
| ∀yF(x, y) | ∃yF(x, y) | …１変数xの命題関数 | ||
| ∀x∀yF(x, y) | ∃x∀yF(x, y) | ∀x∃yF(x, y) | ∃x∃yF(x, y) | …命題 |
| F(x, y) | …２変数x,yの命題関数 | |||
| ∀xF(x, y) | ∃xF(x, y) | …１変数yの命題関数 | ||
| ∀y∀xF(x, y) | ∃y∀xF(x, y) | ∀y∃xF(x, y) | ∃y∃xF(x, y) | …命題 |
∀x∃yF(x, y)
- ∃yF(n, y)
- どんなnに対しても、命題∃yF(n, y) が正しい。
- どんなnに対しても、或るyは F(n, y) である。
- どんなnに対しても、F(n, y) であるyが存在する。
∃x∀yF(x, y)
- ∀yF(n, y)
- 或るnに対し、命題∀yF(n, y) が正しい。
- 或るnに対し、すべてのyは F(n, y) である。
自由変数と束縛変数
演繹
矛盾
- 矛盾を導く命題からは任意の命題が導かれる。
(B→⋏)→(B→A) - 矛盾からは任意の命題が導かれる。
⋏→A - 矛盾とは、それから任意の命題が導かれるものである。
排中律
- A∨￢A
- 間接証明（背理法）の基礎を与えている。
背理法
- Aを証明するために、Aの否定￢Aを仮定して矛盾を導いてみせる。
- ￢A→矛盾 を証明する。
- ￢A→矛盾 というのはAの二重否定 ￢￢A のこと。
- 背理法とは「二重否定の除去の法則」ということ。￢￢A→A
真理値
→の真理値
| A | B | A→B | |
|---|---|---|---|
| ① | T | T | T |
| ② | T | F | F |
| ③ | F | T | T |
| ④ | F | F | T |
- B → (A → B)
…Bが真でありさえすれば、(A → B)は真。＜①③＞ - ￢A → (A → B)
…Aが偽でありさえすれば、(A → B)は真。＜③④＞ - A → [￢B → ￢(A → B)]
…＜②＞
ド・モルガンの法則
- ￢(A∨B) ⇔ ￢A∧￢B
- ￢(A∧B) ⇔ ￢A∨￢B
- ￢∃xF(x) ⇔ ∀x￢F(x)
- ￢∀xF(x) ⇔ ∃x￢F(x)
同値式
ベキ等律
- A∧A ⇔ A
- A∨A ⇔ A
交換律
- A∧B ⇔ B∧A
- A∨B ⇔ B∨A
結合律
- A∧(B∧C) ⇔ (A∧B)∧C
- A∨(B∨C) ⇔ (A∨B)∨C
分配律
- A∧(B∨C) ⇔ (A∧B)∨(A∧C)
- A∨(B∧C) ⇔ (A∨B)∧(A∨C)
二重否定
- ￢￢A ⇔ A
ド・モルガンの法則
- ￢(A∨B) ⇔ ￢A∧￢B
- ￢(A∧B) ⇔ ￢A∨￢B
矛盾律
- A∧￢A ⇔ 偽
排中律
- A∨￢A ⇔ 真
同一律
- (A→A) ⇔ 真
