1. Elementy logiki
Dowody metodą tabeli zero-jedynkowej.
Dowody prawdziwości praw logicznych przeprowadzamy często stosując tabele zero-jedynkowe.
Dla przykładu udowodnimy jedno z praw de Morgana, prawo rozdzielności alternatywy względem koniunkcji i prawo kontrapozycji.
Przykłady.
a) Prawo de Morgana dla alternatywy
Pełna tabela wygląda następująco:
w(p) |
w(q) |
w(p∨q) |
w[¬(p∨q)] |
w(¬p) |
w(¬q) |
w(¬p∧¬q) |
w[¬(p∨q)⇔(¬p∧¬q)] |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
Często stosuje się tablicę skróconą:
w(p) |
w(q) |
w[¬ (p ∨ q) ⇔ (¬ p ∧ ¬ q)] |
0 |
0 |
1 0 1 1 1 1 |
0 |
1 |
0 1 1 1 0 0 |
1 |
0 |
0 1 1 0 0 1 |
1 |
1 |
0 1 1 0 0 0 |
W tabeli tej wypełniamy wpierw kolumnę pierwszą i drugą, a następnie w kolejności: czwarta, trzecia, szósta, ósma, siódma, piąta.
b) Prawo rozdzielności alternatywy względem koniunkcji.
Zastosujemy tu tabelę skróconą.
w(p) |
w(q) |
w(r) |
w[p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r)] |
0 |
0 |
0 |
0 0 1 0 0 0 |
0 |
0 |
1 |
0 0 1 0 0 1 |
0 |
1 |
0 |
0 0 1 1 0 0 |
0 |
1 |
1 |
1 1 1 1 1 1 |
1 |
0 |
0 |
1 0 1 1 1 1 |
1 |
0 |
1 |
1 0 1 1 1 1 |
1 |
1 |
0 |
1 0 1 1 1 1 |
1 |
1 |
1 |
1 1 1 1 1 1 |
Kolumny uzupełniamy w kolejności: 1, 2, 3, a następnie 5, 4, 7, 9, 8, 6.
c) Prawo kontrapozycji
w(p) |
w(q) |
w[(p ⇒ q) ⇔ (¬ q ⇒ ¬ p)] |
0 |
0 |
1 1 1 1 1 |
0 |
1 |
1 1 0 1 1 |
1 |
0 |
0 1 1 0 0 |
1 |
1 |
1 1 0 1 0 |
Tabelę uzupełniamy kolejności: kolumny 1, 2, a następnie 3, 5, 7, 6, 4.