あまり詳しくないので命題論理に限って真理値表を使って簡潔にまとめます。
トートロジーとは
論理式で、それを構成する命題(atomic units)の任意の組み合わせに対して、1となる論理式のことを指します。例えば¬A∨A とか(A∧B)→Aのことです。例として、真理値表を使って(A∧B)→AがA,Bの値によらずに常に１となることを示します。
| A | B | A∧B |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
| A | B | A→B |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
| A | B | (A∧B) | (A∧B)→A |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 |
同値とは
理論や用語の定義によって異なりますが・命題Aと命題Bが同値であるとは(A→B)∧(B→A)がトートロジーであることを指します。
一番下の表のように一般に(A→B)∧(B→A)がトートロジーである、つまり常に1となるとは限りません。
| A | B | A→B |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
| A | B | B→A |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
| A | B | A∧B |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
| A | B | (A→B)∧(B→A) |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |