Dowody założeniowe twierdzeń KRZ - przykłady stosowania reguł pierwotnych oraz twierdzeń w dowodzeniu. (Postarajcie się Państwo uczyć tych reguł na zasadzie np.: reguła odrywania (RO) jest to reguła, która głosi, że jeżeli w pewnym wierszu dowodowym mamy implikację o poprzedniku Φ i następniku Ψ, w innym zaś (na gruncie tego samego dowodu) wyrażenie, które jest poprzednikiem tej implikacji - czyli wyrażenie Φ, to jako nowy wiersz do dowodu można wpisać następnik tej implikacji - czyli wyrażenie Ψ ;
reguła opuszczania alternatywy (OA) głosi, że jeżeli mamy w pewnym wierszu dowodowym alternatywę, a w innym negację jej pierwszego składnika, to jako nowy wiersz do dowodu możemy dołączyć drugi składnik tej alternatywy etc.).
Sposób odczytywania reguł mieliście Państwo podany na wykładzie.
Prawo sylogizmu warunkowego
(p → q) → [(q → r) → (p → r)]
Dowód:
p → q zał.
q → r zał.
p zał.
q RO: 1, 3
r RO: 2, 4 Q.E.D.
p ∨ q → (∼q → p)
Dowód:
p ∨ q zał.
∼q zał.
∼p z.d.n.
q OA: 1, 3
sprzeczność: 2, 4 Q.E.D.
Prawo mnożenia implikacji stronami:
(p → q) ∧ (r → s) → (p ∧ r → q ∧ s)
Dowód:
(p → q) ∧ (r → s) zał.
p ∧ r zał.
p → q OK: 1
r → s OK: 1
p OK: 2
r OK: 2
q RO: 3, 5
s RO: 4, 6
q ∧ s DK: 7, 8 Q.E.D.
Przykład dowodu twierdzeń postaci:
A → (B ∧ C)
Dowód:
1. A zał.
2. A → B twierdzenie
3. A → C twierdzenie
4. B RO: 2, 1
5. C RO: 3, 1
B ∧ C DK: 4,5 Q.E.D.
(p ∨ q → r) → (p → r) ∧ (q → r)
Dowód:
(p ∨ q → r) zał.
(p ∨ q → r) → (p → r) twierdzenie
(p ∨ q → r) → (q → r) twierdzenie
p → r RO: 2,1
q → r RO: 3,1
(p → r) ∧ (q → r) DK: 4,5 Q.E.D.
Dowód twierdzenie pomocniczego (2 wiersz dowodu):
(p ∨ q → r) → (p → r)
Dowód:
1. p ∨ q → r zał.
2. p zał.
3. p ∨ q DA: 2
r RO: 1, 3 Q.E.D.
Dowód twierdzenia pomocniczego (3 wiersz dowodu):
(p ∨ q → r) → (q → r)
Dowód:
1. p ∨ q → r zał.
2. q zał.
3. p ∨ q DA: 2
r RO: 1.3 Q.E.D.
Dowody twierdzeń postaci równoważności A ≡ B:
A ≡ B
1. A → B twierdzenie
2. B → A twierdzenie
A ≡ B DE: 1, 2 Q.E.D.
Prawo transpozycji:
(p → q) ≡ (∼q → ∼p)
Dowód:
1. (p → q) → (∼q → ∼p) twierdzenie
2. (∼q → ∼p) → (p → q) twierdzenie
(p → q) ≡ (∼q → ∼p) DE: 1,2 Q.E.D.
Dowód twierdzenia pomocniczego (wiersz 1)
(p → q) → (∼q → ∼p)
Dowód:
1. p → q zał.
2. ∼q zał.
3. p z.d.n.
4. q RO: 1, 3
sprzeczność: 2, 4 Q.E.D.
Dowód twierdzenia pomocniczego (wiersz 2)
(∼q → ∼p) → (p → q)
Dowód:
∼q → ∼p zał.
2. p zał.
3. ∼q z.d.n.
4. ∼p RO: 1, 3
sprzeczność: 2, 4
Prawa De Morgana: prawo negowania alternatywy oraz prawo negowania koniunkcji
Prawo negowania alternatywy
∼(p ∨ q) ≡ (∼p ∧ ∼q)
Dowód:
1. ∼(p ∨ q) → (∼p ∧ ∼q) twierdzenie 1
2. (∼p ∧ ∼q) → ∼(p ∨ q) twierdzenie 2
∼(p ∨ q) ≡ (∼p ∧ ∼q) DE: 1, 2 Q.E.D.
Dowody twierdzeń zastosowanych w powyższym dowodzie:
Dowód twierdzenia 1
∼(p ∨ q) → (∼p ∧ ∼q)
Dowód:
∼(p ∨ q) zał.
∼(p ∨ q) → ∼p twierdzenie 3
∼(p ∨ q) → ∼q twierdzenie 4
∼p RO: 2, 1
∼q RO: 3, 1
∼p ∧ ∼q DK: 4, 5 Q.E.D.
Dowód twierdzenia 3
∼(p ∨ q) → ∼p
Dowód:
1. ∼(p ∨ q) zał.
2. ∼∼p z.d.n.
3. ∼∼p → p twierdzenie 5
4. p RO: 3, 2
5. p ∨ q DA: 4
sprzeczność: 1, 5 Q.E.D.
Dowód twierdzenia 5
∼∼p → p
Dowód:
∼∼p zał.
∼p z.d.n.
sprzeczność: 1, 2 Q.E.D.
Dowód twierdzenia 4
∼(p ∨ q) → ∼q
Dowód:
1. ∼(p ∨ q) zał.
2. ∼∼q z.d.n.
3. ∼∼q → q twierdzenie
4. q RO: 3, 2
5. p ∨ q DA: 4
sprzeczność: 1,5 Q.E.D.
Uwaga:
Dowód twierdzenia znajdującego się w wierszu 3 przebiega analogicznie jak dowód twierdzenia 5, uwzględniając następujące podstawienie: p/q.
Dowód twierdzenia 2
(∼p ∧ ∼q) → ∼(p ∨ q)
Dowód:
1. ∼p ∧ ∼q zał.
2. p ∨ q z.d.n.
3. ∼p OK: 1
4. ∼ q OK: 1
5. q OA: 2, 3
sprzeczność: 4, 5 Q.E.D.
Prawo negowania koniunkcji
∼(p ∧ q) ≡ (∼p ∨ ∼q)
Dowód:
1. ∼(p ∧ q) → (∼p ∨ ∼q) twierdzenie 6
2. (∼p ∨ ∼q) → ∼(p ∧ q) twierdzenie 7
∼(p ∧ q) ≡ (∼p ∨ ∼q) DE: 1,2 Q.E.D.
Dowód twierdzenia 6
∼(p ∧ q) → (∼p ∨ ∼q)
Dowód:
1. ∼(p ∧ q) zał.
2. ∼(∼p ∨ ∼q) z.d.n.
3. ∼(∼p ∨ ∼q) → (∼∼p ∧ ∼∼q) twierdzenie (prawo negowania alternatywy)
4. ∼∼p ∧ ∼∼q RO: 3, 2
5. ∼∼p OK: 4
6. ∼∼q OK: 4
7. ∼∼p → p twierdzenie 5
8. ∼∼q → q twierdzenie (patrz uwaga powyżej)
9. p RO: 7, 5
10. q RO: 8, 6
11. p ∧ q DK: 9, 10
sprzeczność: 1, 11 Q.E.D.
Dowód twierdzenia 7
(∼p ∨ ∼q) → ∼(p ∧ q)
Dowód:
1. ∼p ∨ ∼q zał.
2. p ∧ q z.d.n.
3. p OK: 2
4. q OK: 2
5. ∼q OA: 1,3
sprzeczność: 4, 5 Q.E.D.
Prawo dylematu destrukcyjnego złożonego
(p → q) ∧ (r → s) ∧ ∼ (q ∧ s) → ∼ (p ∧ r)
Dowód:
1. (p → q) ∧ (r → s) ∧ ∼ (q ∧ s) zał.
2. p ∧ r z.d.n.
3. p → q OK: 1
4. r → s OK: 1
5. ∼ (q ∧ s) OK: 1
6. p OK: 2
7. r OK: 2
8. q RO: 3, 6
9. s RO: 4, 7
10. q ∧ s DK: 8, 9
sprzeczność: 5, 10 Q.E.D.
Twierdzenie (postać prawa dylematu destrukcyjnego złożonego) do samodzielnego udowodnienia:
(∼r ∨ ∼s) ∧ [(p → r) ∧ (q → s)] → (∼p ∨ ∼q) (dowód nie wprost).
7