Bölüm IX Türetim III
Teoremleri Kullanmak
TEOREMLER: Sembolik mantıkta karşımıza çıkan teoremleri öncülü olmayan sonuç önermelerinden oluşan çıkarımlar olarak düşünebiliriz. Şimdi bazı teoremlerin geçerliliğinin gösterilmesine geçebiliriz.
Teorem 1: 𝑃 → 𝑃
1. Göster 𝑃 → 𝑃
2. 𝑃 (Koşullu varsayım)Teorem 2: 𝑄 → (𝑃 → 𝑄)
1. Göster 𝑄 → (𝑃 → 𝑄)
2. 𝑄
3. Göster 𝑃 → 𝑄
4. 𝑃
5. 𝑄 (2T)Burada dikkat edilmesi gereken temel husus ana eklemin belirlenmesidir. 𝑄 ve 𝑃 → 𝑄 önermeleri arasındaki → eklemi teorem 2 de ana eklemdir.
Teorem 3: 𝑃 → ((𝑃 → 𝑄) → 𝑄)
1. Göster 𝑃 → ((𝑃 → 𝑄) → 𝑄)
2. 𝑃
3. Göster (𝑃 → 𝑄) → 𝑄
4. (𝑃 → 𝑄)
5. 𝑄 (2,4 MP)Ana eklemi belirledikten sonra koşullu türetimin adımlarını bir bir uygulayarak teoremin geçerliliğini göstermiş olduk.
Teorem 4: (𝑃 → 𝑄) → ((𝑄 → 𝑅) → (𝑃 → 𝑅))Ana eklem 𝑃 → 𝑄 ve (𝑄 → 𝑅) → (𝑃 → 𝑅) arasındaki ise eklemi. Şimdi bu teoremin geçerliliğini gösterelim.
1. Göster (𝑃 → 𝑄) → ((𝑄 → 𝑅) → (𝑃 → 𝑅))
2. (𝑃 → 𝑄)
3. Göster (𝑄 → 𝑅) → (𝑃 → 𝑅)
4. 𝑄 → 𝑅
5. Göster 𝑃 → 𝑅
6. 𝑃
7. 𝑄 (2,6 MP)
8. 𝑅 (4,7 MP)Teorem 5: (𝑄 → 𝑅) → ((𝑃 → 𝑄) → (𝑃 → 𝑅))
Teorem 7: ((𝑃 → 𝑄) → (𝑃 → 𝑅)) → ((𝑃 → (𝑄 → 𝑅))
Ana eklem (𝑃 → 𝑄) → (𝑃 → 𝑅) ve (𝑃 → (𝑄 → 𝑅) arasındaki ise eklemi.
1. Göster ((𝑃 → 𝑄) → (𝑃 → 𝑅)) → ((𝑃 → (𝑄 → 𝑅))
2. (𝑃 → 𝑄) → (𝑃 → 𝑅)
3. Göster (𝑃 → (𝑄 → 𝑅)
4. 𝑃
5. Göster 𝑄 → 𝑅
6. 𝑄
7. Göster 𝑃 → 𝑄
8. 𝑃 (4T)
9. 𝑄 (6T)
10. 𝑃 → 𝑅 (2,7 MP)
11. 𝑅 (4,10 MP)Bu teoremin geçerliğinin gösterilmesinde kritik aşama yedinci satırdaki göster 𝑃 → 𝑄 adımı. Bu adımı açtık çünkü R ye ulaşmaya çalışıyoruz ve elimizde (𝑃 → 𝑄) → (𝑃 → 𝑅) gibi bir varsayım var.
Teorem 11: ¬ ¬𝑃 → 𝑃
Teorem 12: 𝑃 → ¬ ¬𝑃
Teorem 11 ve teorem 12 çifte değilleme diye başta belirttiğimiz kural. (law of double negation)
Teorem 13: (𝑃 → 𝑄) → ( ¬𝑄 → ¬𝑃)
1. Göster (𝑃 → 𝑄) → (¬𝑄 → ¬𝑃)
2. 𝑃 → 𝑄
3. Göster ¬𝑄 → ¬𝑃
4. ¬𝑄
5. ¬𝑃 (2,4 MT)Teorem 14: (𝑃 → ¬𝑄) → (𝑄 → ¬𝑃)
Teorem 15: ( ¬𝑃 → 𝑄) → ( ¬𝑄 → 𝑃)
Teorem 16: ( ¬𝑃 → ¬𝑄) → (𝑄 → 𝑃)
Teorem 17: 𝑃 → ( ¬𝑃 → 𝑄)
1. Göster 𝑃 → (¬𝑃 → 𝑄)
2. 𝑃
3. Göster ¬𝑃 → 𝑄
4. ¬𝑃*
5. 𝑃 (2T)*Bu teoremin ispatında daha önce karşılaşmadığımız bir durumla karşı karşıyayız. Şöyle ki; hiçbir satırda dolaylı varsayım yapmadığımız halde ispatı çelişki üzerinden bitirdik. Şu durumda yeni bir kuralı burada belirtebiliriz: çelişki dolaylı türetimde kullanılabileceği gibi koşullu ya da doğrudan türetimde de kullanılabilir.
Teorem 18: ¬𝑃 → (𝑃 → 𝑄)
Teorem 19: (𝑃 → ¬𝑃) → 𝑃
Teorem 20: (𝑃 → ¬𝑃) → ¬𝑃
Teorem 21: ¬(𝑃 → 𝑄) → 𝑃
1. Göster 𝑐
2. ¬(𝑃 → 𝑄)
3. Göster 𝑃
4. ¬𝑃
5. Göster 𝑃 → 𝑄*
6. 𝑃
7. ¬𝑃 (4T)
8. ¬(𝑃 → 𝑄) (2T)*Not: Bu örnekte olduğu gibi türetim esnasında kuşullu bir bileşik önermenin değiline varsayım neticesinde ulaşırsak, yapmaya çalışacağımız şey koşullu bileşik önermenin kendisine ulaşmaya çalışarak ikisi arasındaki çelişkiyi yakalamak olacaktır.
Teorem 22: ¬(𝑃 → 𝑄) → 𝑄
Teorem 23: ((𝑃 → 𝑄) → 𝑃) → 𝑃
İkinci bölüm
Ve, veya, ancak ve ancak eklemleri (and, or, if and only if)
Çıkarım kuralları (inference rules)
Sadeleştirme (S) (Simplification)
P ∧ Q ∴ P
P ∧ Q ∴ Q
Sözel bir dille ifade edecek olursak eğer elinizde 𝑃𝛬𝑄 önermesi var ise türetim aşamasında 𝑃′ yi ve 𝑄′ yu sadeleştirme yoluyla kullanabilirsiniz.
Birleştirme (Adj) (Adjunction)
P, Q ∴ P ∧ Q
Sözel bir dille ifade edecek olursak eğer elinizde 𝑃 önermesi ve 𝑄 önermesi ayrı ayrı var ise türetim aşamasında 𝑃𝛬𝑄′yu birleştirme yoluyla kullanabilirsiniz.
Ekleme (Add) (Addition)
P ∴ P ∨ Q
Sözel bir dille söyleyecek olursak elinizde 𝑃 gibi bir önerme var ise veya eklemi ile yanına herhangi bir önermeyi ekleyebilirsiniz.
Modus Tollendo Ponens (MTP)
P ∨ Q, ¬P ∴ Q P ∨ Q, ¬Q ∴ P
İkikoşulludan koşulluya (BC) (Biconditional to conditional)
P ↔︎ Q ∴ P → Q P ↔︎ Q ∴ Q → P
Koşulludan ikikoşulluya (CB) (Conditional to biconditional)
P → Q, Q → P ∴ P ↔︎ Q
Şimdi bu çıkarım kuralları ile türetim yapabiliriz.
Örnek 1: Öncülü ¬𝑃 ∧ 𝑄 sonucu ¬𝑃 olan bir çıkarımın geçerliliğini gösterin.
1. Göster ¬𝑃
2. ¬𝑃𝛬𝑄3. ¬𝑃 (2S)Örnek 2: Öncülü P ∧ (Q → R) sonucu Q → R olan bir çıkarımın geçerliliğini gösterin.
1. Göster 𝑄 → 𝑅
2. 𝑃𝛬(𝑄 → 𝑅)
3. 𝑄 → 𝑅 (2S)Bu çıkarım kurallarını kullanarak sembolik mantıkta oldukça önemli teoremlerin ispatlarını yapabiliriz, diğer bir ifadeyle geçerli olduklarını gösterebiliriz.
Teorem 24: (𝑃𝛬𝑄) ↔︎ (𝑄𝛬𝑃)
Eğer ana eklemin bu teoremde olduğu gibi ancak ve ancak olduğu bir türetim yapacaksak ancak ve ancak’ın her iki yönünü de ayrı ayrı türetmek durumundayız. Şimdi bu türetimi yapalım:
1. Göster (𝑃𝛬𝑄) ↔ (𝑄𝛬𝑃)
2. Göster (𝑃𝛬𝑄) → (𝑄𝛬𝑃)
3. 𝑃𝛬𝑄
4. 𝑃 (3S)
5. 𝑄 (3S)
6. 𝑄𝛬𝑃 (4,5 Adj)
7. Göster (𝑄𝛬𝑃) → (𝑃𝛬𝑄)
8. 𝑄𝛬𝑃
9. 𝑄 (8S)
10. 𝑃 (8S)
11. 𝑃𝛬𝑄 (9,10 Adj)
12. (𝑃𝛬𝑄) ↔ (𝑄𝛬𝑃) (2,7 CB)Teorem 25: (P ¬(Q ¬R)) ↔︎ ((P ¬Q) ¬R)
Teorem 26: ((P → Q) ¬(Q → R)) → (P → R)
1. Göster ((𝑃 → 𝑄)𝛬(𝑄 → 𝑅)) → (𝑃 → 𝑅)
2. (𝑃 → 𝑄)𝛬(𝑄 → 𝑅)
3. Göster 𝑃 → 𝑅
4. 𝑃
5. 𝑃 → 𝑄 (2S)
6. 𝑄 → 𝑅 (2S)
7. 𝑄 (4,5 MP)
8. 𝑅 (6,7 MP)Teorem 27: ((P ¬Q) → R) ↔︎ (P → (Q → R))
1. Göster ((𝑃𝛬𝑄) → 𝑅) ↔ (𝑃 → (𝑄 → 𝑅))2. Göster ((𝑃𝛬𝑄) → 𝑅) → (𝑃 → (𝑄 → 𝑅))
3. (𝑃𝛬𝑄) → 𝑅
4. Göster 𝑃 → (𝑄 → 𝑅)
5. 𝑃
6. Göster 𝑄 → 𝑅
7. 𝑄
8. 𝑃𝛬𝑄 (5,7 Adj)
9. 𝑅 (3,8 MP)
10. Göster (𝑃 → (𝑄 → 𝑅)) → ((𝑃𝛬𝑄) → 𝑅)
11. 𝑃 → (𝑄 → 𝑅)
12. Göster (𝑃𝛬𝑄) → 𝑅
13. 𝑃𝛬𝑄
14. 𝑃 (13S)
15. 𝑄 → 𝑅 (11.14 MP)
16. 𝑄 (13S)
17. 𝑅 (15,16 MP)
18. ((𝑃𝛬𝑄) → 𝑅) ↔ (𝑃 → (𝑄 → 𝑅)) (2,10 CB)Teorem 28: ((P ∧ Q) → R) ↔︎ ((P ∧ ¬R) → ¬Q)
Teorem 29: (P → (Q ∧ R)) ↔︎ ((P → Q) ∧ (P → R))
1. Göster (𝑃 → (𝑄𝛬𝑅)) ↔ ((𝑃 → 𝑄)𝛬(𝑃 → 𝑅))
2. Göster (𝑃 → (𝑄𝛬𝑅)) → ((𝑃 → 𝑄)𝛬(𝑃 → 𝑅))
3. 𝑃 → (𝑄𝛬𝑅)
4. Göster (𝑃 → 𝑄)𝛬(𝑃 → 𝑅)
5. Göster 𝑃 → 𝑄
6. 𝑃
7. 𝑄𝛬𝑅 (3,6 MP)
8. 𝑄 (7S)
9. Göster 𝑃 → 𝑅
10. 𝑃
11. 𝑄𝛬𝑅 (3,10 MP)
12. 𝑅 (11S)
13. (𝑃 → 𝑄)𝛬(𝑃 → 𝑅) (5,9 Adj)
14. Göster ((𝑃 → 𝑄)𝛬(𝑃 → 𝑅)) → (𝑃 → (𝑄𝛬𝑅))
15. (𝑃 → 𝑄)𝛬(𝑃 → 𝑅)
16. (𝑃 → 𝑄) (15S)
17. (𝑃 → 𝑅) (15S)
18. Göster (𝑃 → (𝑄𝛬𝑅)
19. 𝑃
20. 𝑄 (16,19 MP)
21. 𝑅 (17,19 MP)
22. 𝑄𝛬𝑅 (20,21 Adj)
23. (𝑃 → (𝑄𝛬𝑅)) ↔ ((𝑃 → 𝑄)𝛬(𝑃 → 𝑅)) (2,14 CB)Bu ve benzeri teoremlerin ispatlarında dikkat edilmesi gereken iki husus var. Bunlardan birincisi eğer bir satırda “göster 𝐴𝛬𝐵” gibi bir satırla karşılaşırsak 𝐴′𝑦𝚤 ve 𝐵′𝑦𝑖 ayrı ayrı türetmemiz gerekir. Dikkat etmemiz gereken ikinci husus ise kapanan kutucuktaki türettiğimiz önermeleri bir daha kullanamayacağımız.
Teorem 30: (P → Q) → ((R ∧ P) → (R ∧ Q))
1. Göster (𝑃 → 𝑄) → ((𝑅𝛬𝑃) → (𝑅𝛬𝑄))
2. 𝑃 → 𝑄
3. Göster (𝑅𝛬𝑃) → (𝑅𝛬𝑄)
4. (𝑅𝛬𝑃)
5. 𝑃 (4S)
6. 𝑄 (2,5 MP)
7. 𝑅 (4S)
8. 𝑅𝛬𝑄 (6,7Adj)Teorem 31: (P → Q) → ((P ∧ R) → (Q ∧ R))
Teorem 32: ((P → R) ∧ (Q → S)) → ((P ∧ Q) → (R ∧ S))
Teorem 33: ((P → Q) ∧ ( ¬P → Q)) → Q
Teorem 34: ((P → Q) ∧ (P → ¬Q)) → ¬P
Teorem 36: ¬(P ∧ ¬P)
1. Göster ¬(𝑃𝛬¬𝑃)
2. (𝑃𝛬¬𝑃) (Dolaylı Varsayım)
3. 𝑃 (2S)*
4. ¬𝑃(2S)*Teorem 37: (𝑃 → 𝑄) ↔︎ ¬(𝑃 ∧ ¬𝑄)
Teorem 38: (𝑃 ∧ 𝑄) ↔︎ ¬(𝑃 → ¬𝑄)
Teorem 39: ¬(𝑃 ∧ 𝑄) ↔︎ (𝑃 → ¬𝑄)
Teorem 40: ¬(𝑃 → 𝑄) ↔︎ (𝑃 ∧ ¬𝑄)
Teorem 41: 𝑃 ↔︎ (𝑃 ∧ 𝑃)
1. Göster 𝑃 ↔ (𝑃𝛬𝑃)
2. Göster 𝑃 → (𝑃𝛬𝑃)
3. 𝑃
4. 𝑃 (3S)
5. 𝑃𝛬𝑃 (3,4 Adj)
6. Göster (𝑃𝛬𝑃) → 𝑃
7. 𝑃𝛬𝑃
8. 𝑃 (7S)
9. 𝑃 ↔ (𝑃𝛬𝑃) (2,6 CB)Teorem 47: 𝑃 ↔︎ (𝑃 ∨ 𝑃)
1. Göster 𝑃 ↔ (𝑃𝑉𝑃)
2. Göster 𝑃 → (𝑃𝑉𝑃)
3. 𝑃
4. 𝑃𝑉𝑃 (3 Add)
5. Göster (𝑃𝑉𝑃) → 𝑃
6. 𝑃𝑉𝑃
7. Göster 𝑃
8. ¬𝑃 (Dolaylı Varsayım)*
9. 𝑃 (6,8 MTP)*
10. 𝑃 ↔ (𝑃𝑉𝑃) (2,5 CB)Teorem 46: (𝑃 → 𝑄) ↔︎ ( ¬𝑃 ∨ 𝑄)
1. Göster (𝑃 → 𝑄) ↔ (¬𝑃𝑉𝑄)
2. Göster (𝑃 → 𝑄) → (¬𝑃𝑉𝑄)
3. 𝑃 → 𝑄
4. Göster ¬𝑃𝑉𝑄
5. ¬(¬𝑃𝑉𝑄) (Dolaylı Varsayım)
6. Göster 𝑃
7. ¬𝑃(Dolaylı Varsayım)
8. ¬𝑃𝑉𝑄 (7 Add)*
9. ¬(¬𝑃𝑉𝑄) (5R)*
10. 𝑄 (3,6 MP))
11. ¬𝑃𝑉𝑄 (10 Add)*
12. ¬(¬𝑃𝑉𝑄) (5R)*
13. Göster (¬𝑃𝑉𝑄) → (𝑃 → 𝑄)
14. ¬𝑃𝑉𝑄
15. Göster 𝑃 → 𝑄
16. 𝑃
17. 𝑄 (14,16 MTP)
18. (𝑃 → 𝑄) ↔ (¬𝑃𝑉𝑄) (2,13 CB)Teorem 49: ((𝑃 ∨ 𝑄) ∧ (𝑃 → 𝑅) ∧ (𝑄 → 𝑅)) → 𝑅
1. Göster ((𝑃𝑉𝑄)𝛬(𝑃 → 𝑅)𝛬(𝑄 → 𝑅)) → 𝑅
2. ((𝑃𝑉𝑄)𝛬(𝑃 → 𝑅)𝛬(𝑄 → 𝑅))
3. Göster 𝑅
4. ¬𝑅
5. 𝑃 → 𝑅 (2S)
6. 𝑄 → 𝑅 (2S)
7. 𝑃𝑉𝑄 (2S)
8. ¬𝑃 (4,5 MP)
9. ¬𝑄(4,6 MP)*
10. 𝑄 (7,8MTP)*Kural: türetim yaparken özellikle “veya” eklemi içeren çıkarımlarda 𝑃 ∨ 𝑄 yerine çoğunlukla dengi olan ¬𝑃 → 𝑄 yu kullanırız. Diğer bir ifade ile 𝑃 ∨ 𝑄 ≡ ¬𝑃 → 𝑄
Teorem 48: ((𝑃 ∨ 𝑄)Λ (𝑃 → 𝑅) ∧ (𝑄 → 𝑆)) → (𝑅 ∨ 𝑆)
1. Göster ((𝑃𝑉𝑄)Λ (𝑃 → 𝑅)𝛬(𝑄 → 𝑆)) → (𝑅𝑉𝑆)
2. ((𝑃𝑉𝑄)Λ (𝑃 → 𝑅)𝛬(𝑄 → 𝑆))
3. Göster 𝑅𝑉𝑆 ≡ ¬𝑅 → 𝑆
4. ¬𝑅
5. 𝑄 → 𝑆 (2S)
6. 𝑃𝑉𝑄 ≡ ¬𝑃 → 𝑄 (2S)
7. 𝑃 → 𝑅 (2S)
8. ¬𝑃 (4,7 MT)
9. 𝑄 (6,8 MTP)
10. 𝑆 (5,9 MP)Teorem 45: (𝑃 ∨ 𝑄) ↔︎ ( ¬𝑃 → 𝑄)
Teorem 45 yukarıda andığım kuralın ispatı olarak karşımızda durmakta.
Teorem 53: (𝑃 ∨ 𝑄) ↔︎ (𝑄 ∨ 𝑃)
Teorem 54: 𝑃 ∨ (𝑄 ∨ 𝑅) ↔︎ (𝑃 ∨ 𝑄) ∨ 𝑅