7 Mantıksal Gerektirme ve Çıkarım Kuralları
Bir teoremin ispatı, öncüllerden sonuca giden bir çıkarım zinciridir. Bu zincirin her halkasının geçerli olması, kullanılan adımın bir mantıksal gerektirme olmasına bağlıdır. Bu bölümde gerektirme kavramını kesin biçimde tanımlıyor ve matematikte en sık kullanılan çıkarım kurallarını tek tek ispatlıyoruz.
7.1 Mantıksal Gerektirme
Tanım 7.1 (Mantıksal Gerektirme) İki tane bileşik önermenin birbirini mantıksal olarak gerektirmesi için, bu iki bileşik önermenin arasına “\(\Rightarrow\)” bağlacı konularak elde edilen yeni bileşik önermenin totoloji olması gerekir.
\(a, b, c, \dots\) önermelerine bağlı \(P\) ve \(K\) bileşik önermeleri verildiğinde
\[P \Rightarrow K \equiv t\]
ise “\(P\) önermesi \(K\) önermesini mantıksal olarak gerektirir” denir.
\(\Rightarrow\) sembolü iki ayrı işi görür ve bu ikisi karıştırılmamalıdır:
- İşlem olarak: \(p \Rightarrow q\), doğruluk değeri duruma göre \(0\) ya da \(1\) olan bir bileşik önermedir.
- Bağıntı olarak: “\(P\), \(K\)’yı gerektirir” demek, \(P \Rightarrow K\) bileşik önermesinin her durumda \(1\) olması demektir.
Yani gerektirme, koşullu önermenin totoloji hâlidir. Bir gerektirmeyi göstermek için daima “sonuç \(t\) mi?” sorusunu yanıtlarız.
Örnek 7.1 (Gerektiriyor mu?) \((p \wedge q)' \vee r\) önermesi, \((r \wedge q) \vee p'\) önermesini mantıksal olarak gerektirir mi?
Çözüm
Aradığımız şey
\[\big[(p \wedge q)' \vee r\big] \Rightarrow \big[(r \wedge q) \vee p'\big] \;\overset{?}{\equiv}\; t\]
eşitliğidir. Önce açalım:
\[ \begin{aligned} \big[(p \wedge q)' \vee r\big] \Rightarrow \big[(r \wedge q) \vee p'\big] &\equiv \big[(p \wedge q)' \vee r\big]' \vee \big[(r \wedge q) \vee p'\big] \\[2pt] &\equiv \big[(p \wedge q) \wedge r'\big] \vee (q \wedge r) \vee p' && \text{(De Morgan)} \\[2pt] &\equiv (p \wedge q \wedge r') \vee (q \wedge r) \vee p' \end{aligned} \]
Şimdi \(p'\) ile ilk terimi birleştirelim:
\[p' \vee (p \wedge q \wedge r') \equiv (p' \vee p) \wedge \big(p' \vee (q \wedge r')\big) \equiv p' \vee (q \wedge r')\]
Buradan
\[ \begin{aligned} &\equiv p' \vee (q \wedge r') \vee (q \wedge r) \\[2pt] &\equiv p' \vee \big[q \wedge (r' \vee r)\big] && \text{(dağılma, ters yönde)} \\[2pt] &\equiv p' \vee (q \wedge t) \\[2pt] &\equiv p' \vee q \end{aligned} \]
Sonuç \(p' \vee q\)’dur; bu bir totoloji değildir (\(p \equiv 1\), \(q \equiv 0\) için \(0\) olur). O hâlde \((p \wedge q)' \vee r\) önermesi \((r \wedge q) \vee p'\) önermesini mantıksal olarak gerektirmez.
Sağlama. \(p \equiv 1\), \(q \equiv 0\), \(r \equiv 0\) alalım. Birinci önerme \((1 \wedge 0)' \vee 0 \equiv 1\), ikincisi \((0 \wedge 0) \vee 0 \equiv 0\) olur; yani öncül doğruyken sonuç yanlıştır.
\(\blacksquare\)
7.2 Temel Çıkarım Kuralları
Aşağıdaki dört gerektirme, matematiksel ispatların iskeletini oluşturur.
Teorem 7.1 (Ayırma Kuralı (Modus Ponens)) \[\big[(p \Rightarrow q) \wedge p\big] \Rightarrow q\]
bir totolojidir.
İspat
Önce öncülü sadeleştirelim:
\[(p' \vee q) \wedge p \equiv (p' \wedge p) \vee (q \wedge p) \equiv c \vee (p \wedge q) \equiv p \wedge q\]
Buradan
\[\big[(p \Rightarrow q) \wedge p\big] \Rightarrow q \equiv (p \wedge q)' \vee q \equiv (p' \vee q') \vee q \equiv p' \vee (q' \vee q) \equiv p' \vee t \equiv t\]
\(\blacksquare\)
Sözle: “\(p\) ise \(q\)” doğruysa ve \(p\) de doğruysa, \(q\) doğrudur. Teoremleri uygularken yaptığımız şey tam olarak budur.
Teorem 7.2 (Karşıt Ters Kuralı (Modus Tollens)) \[\big[(p \Rightarrow q) \wedge q'\big] \Rightarrow p'\]
bir totolojidir.
İspat
Öncülü sadeleştirelim:
\[(p' \vee q) \wedge q' \equiv (p' \wedge q') \vee (q \wedge q') \equiv (p' \wedge q') \vee c \equiv p' \wedge q'\]
Buradan
\[ \begin{aligned} \big[(p \Rightarrow q) \wedge q'\big] \Rightarrow p' &\equiv (p' \wedge q')' \vee p' \\[2pt] &\equiv (p \vee q) \vee p' && \text{(De Morgan)} \\[2pt] &\equiv (p \vee p') \vee q \equiv t \vee q \equiv t \end{aligned} \]
\(\blacksquare\)
Sözle: “\(p\) ise \(q\)” doğruysa ve \(q\) yanlışsa, \(p\) de yanlıştır. Olmayana ergi ile ispatın dayandığı kural budur.
Teorem 7.3 (Zincirleme Kuralı (Hipotetik Tasım)) Her \(a, b, c\) önermesi için
\[\big[(a \Rightarrow b) \wedge (b \Rightarrow c)\big] \Rightarrow (a \Rightarrow c)\]
bir totolojidir.
İspat
\[ \begin{aligned} \big[(a \Rightarrow b) \wedge (b \Rightarrow c)\big] \Rightarrow (a \Rightarrow c) &\equiv \big[(a' \vee b) \wedge (b' \vee c)\big]' \vee (a' \vee c) \\[2pt] &\equiv \big[(a' \vee b)' \vee (b' \vee c)'\big] \vee (a' \vee c) && \text{(De Morgan)} \\[2pt] &\equiv \big[(a \wedge b') \vee (b \wedge c')\big] \vee a' \vee c && \text{(De Morgan)} \\[2pt] &\equiv \underbrace{\big[a' \vee (a \wedge b')\big]}_{\equiv\, a' \vee b'} \vee \underbrace{\big[c \vee (b \wedge c')\big]}_{\equiv\, c \vee b} \\[2pt] &\equiv (a' \vee b') \vee (b \vee c) \\[2pt] &\equiv a' \vee (b' \vee b) \vee c \equiv a' \vee t \vee c \equiv t \end{aligned} \]
Alt çizgilerdeki iki sadeleştirme, dağılma özelliğinin doğrudan sonucudur:
\[a' \vee (a \wedge b') \equiv (a' \vee a) \wedge (a' \vee b') \equiv t \wedge (a' \vee b') \equiv a' \vee b'\]
\[c \vee (b \wedge c') \equiv (c \vee b) \wedge (c \vee c') \equiv (c \vee b) \wedge t \equiv c \vee b\]
\(\blacksquare\)
Sözle: \(a\)’dan \(b\)’ye, \(b\)’den \(c\)’ye gidilebiliyorsa \(a\)’dan \(c\)’ye gidilebilir. Uzun ispatların ara adımlarını birbirine bağlayan kural budur.
Teorem 7.4 (Ayırıcı Tasım) \[\big[(p \vee q) \wedge p'\big] \Rightarrow q\]
bir totolojidir.
İspat
Öncülü sadeleştirelim:
\[(p \vee q) \wedge p' \equiv (p \wedge p') \vee (q \wedge p') \equiv c \vee (q \wedge p') \equiv q \wedge p'\]
Buradan
\[ \begin{aligned} \big[(p \vee q) \wedge p'\big] \Rightarrow q &\equiv (q \wedge p')' \vee q \\[2pt] &\equiv (q' \vee p) \vee q && \text{(De Morgan)} \\[2pt] &\equiv (q \vee q') \vee p \equiv t \vee p \equiv t \end{aligned} \]
\(\blacksquare\)
Sözle: “\(p\) veya \(q\)” doğruysa ve \(p\) yanlışsa, \(q\) doğrudur. Durum inceleme ile ispatta seçenekleri eleme adımı bu kurala dayanır.
| Kural | Öncül | Sonuç |
|---|---|---|
| Ayırma (modus ponens) | \((p \Rightarrow q) \wedge p\) | \(q\) |
| Karşıt ters (modus tollens) | \((p \Rightarrow q) \wedge q'\) | \(p'\) |
| Zincirleme (hipotetik tasım) | \((a \Rightarrow b) \wedge (b \Rightarrow c)\) | \(a \Rightarrow c\) |
| Ayırıcı tasım | \((p \vee q) \wedge p'\) | \(q\) |
Dördünün de ispatı aynı kalıptadır: öncülü sadeleştir, \(P' \vee K\) yaz, \(x \vee x' \equiv t\) çıkart.
\(\big[(p \Rightarrow q) \wedge q\big] \Rightarrow p\) bir totoloji değildir.
\(p \equiv 0\), \(q \equiv 1\) alalım: \(p \Rightarrow q\) doğru, \(q\) doğru, ama \(p\) yanlıştır. Yani sonucun doğru olması öncülün doğru olmasını gerektirmez.
7.3 Çift Gerektirme (Karşılıklı Şart)
Tanım 7.2 (Karşılıklı Şart İşlemi) Verilen \(a\) ve \(b\) önermelerinden “\((a \Rightarrow b) \wedge (b \Rightarrow a)\)” bileşik önermesini elde etme işlemine karşılıklı şart işlemi veya çift gerektirme işlemi adı verilir.
Bu önerme \(a \Leftrightarrow b\) şeklinde gösterilir ve “\(a\) ancak ve ancak \(b\)” ya da “\(a\) için gerek ve yeter koşul \(b\)’dir” şeklinde ifade edilir.
| \(a\) | \(b\) | \(a \Rightarrow b\) | \(b \Rightarrow a\) | \((a \Rightarrow b) \wedge (b \Rightarrow a)\) | \(a \Leftrightarrow b\) |
|---|---|---|---|---|---|
| \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(0\) | \(1\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) | \(0\) | \(0\) | \(0\) |
| \(0\) | \(0\) | \(1\) | \(1\) | \(1\) | \(1\) |
Tablodan görüldüğü gibi \(a \Leftrightarrow b\) önermesi, iki taraf aynı doğruluk değerini aldığında doğrudur.
Tanım 7.3 (Mantıksal Çift Gerektirme) \(a, b, c, \dots\) önermelerine bağlı \(P\) ve \(K\) bileşik önermeleri verildiğinde, \(P \Leftrightarrow K\) önermesi totoloji ise “\(P\) önermesi \(K\) önermesini mantıksal olarak çift gerektirir” denir.
\(P \Leftrightarrow K \equiv t\) olması ile \(P \equiv K\) olması aynı anlama gelir: iki önerme bütün durumlarda aynı doğruluk değerini alır.
Bu yüzden şimdiye kadar “\(\equiv\)” ile yazdığımız her denklik, aslında bir çift gerektirmedir.
Örnek 7.2 (De Morgan Kuralının Çift Gerektirmesi) \((a \vee b)'\) önermesinin \(a' \wedge b'\) önermesini mantıksal olarak çift gerektirdiğini gösteriniz.
Çözüm
\[ \begin{aligned} \big[(a \vee b)' \Leftrightarrow (a' \wedge b')\big] &\equiv \big[(a \vee b)' \Rightarrow (a' \wedge b')\big] \wedge \big[(a' \wedge b') \Rightarrow (a \vee b)'\big] \\[2pt] &\equiv \big[(a \vee b) \vee (a' \wedge b')\big] \wedge \big[(a \vee b) \vee (a' \wedge b')\big] \\[2pt] &\equiv (a \vee b) \vee (a' \wedge b') && \text{(eş güçlülük)} \end{aligned} \]
İkinci satırda her iki köşeli parantez de aynı ifadeye indirgendi; çünkü \((a' \wedge b')' \equiv a \vee b\) ve \((a \vee b)' \equiv a' \wedge b'\)’dür.
Kalan ifadeyi sadeleştirelim:
\[ \begin{aligned} (a \vee b) \vee (a' \wedge b') &\equiv \big[a \vee (a' \wedge b')\big] \vee b && \text{(birleşme)} \\[2pt] &\equiv \big[(a \vee a') \wedge (a \vee b')\big] \vee b && \text{(dağılma)} \\[2pt] &\equiv (a \vee b') \vee b \\[2pt] &\equiv a \vee (b' \vee b) \equiv a \vee t \equiv t \end{aligned} \]
O hâlde çift gerektirme sağlanır.
\(\blacksquare\)
Örnek 7.3 (Ve İşleminden Çift Gerektirmeye) Doğruluk tablosu kullanmadan, \(a \wedge b\) bileşik önermesinin \(a \Leftrightarrow b\) bileşik önermesini mantıksal gerektirdiğini ispatlayınız.
Çözüm
\(h \equiv \big[(a \wedge b) \Rightarrow (a \Leftrightarrow b)\big]\) önermesinin totoloji olduğunu göstermeliyiz.
\[ \begin{aligned} h &\equiv (a \wedge b) \Rightarrow \big[(a \Rightarrow b) \wedge (b \Rightarrow a)\big] \\[2pt] &\equiv (a \wedge b) \Rightarrow \big[(a' \vee b) \wedge (b' \vee a)\big] \\[2pt] &\equiv (a \wedge b)' \vee \big[(a' \vee b) \wedge (b' \vee a)\big] \\[2pt] &\equiv (a' \vee b') \vee \big[(a' \vee b) \wedge (b' \vee a)\big] && \text{(De Morgan)} \\[2pt] &\equiv \Big[(a' \vee b') \vee (a' \vee b)\Big] \wedge \Big[(a' \vee b') \vee (b' \vee a)\Big] && \text{(dağılma)} \end{aligned} \]
İki köşeli parantezi ayrı ayrı sadeleştirelim:
\[(a' \vee b') \vee (a' \vee b) \equiv a' \vee (b' \vee b) \equiv a' \vee t \equiv t\]
\[(a' \vee b') \vee (b' \vee a) \equiv (a' \vee a) \vee b' \equiv t \vee b' \equiv t\]
O hâlde \(h \equiv t \wedge t \equiv t\)’dir; gerektirme sağlanır.
\(\blacksquare\)
Örnek 7.4 (Çift Gerektirmenin Değili) \((p' \Leftrightarrow q)' \equiv (p \Leftrightarrow q)\) olduğunu gösteriniz.
Çözüm
\[ \begin{aligned} (p' \Leftrightarrow q)' &\equiv \big[(p' \Rightarrow q) \wedge (q \Rightarrow p')\big]' \\[2pt] &\equiv \big[(p \vee q) \wedge (q' \vee p')\big]' \\[2pt] &\equiv \Big[\big[(p \vee q) \wedge q'\big] \vee \big[(p \vee q) \wedge p'\big]\Big]' && \text{(dağılma)} \end{aligned} \]
İçerideki iki parçayı sadeleştirelim:
\[(p \vee q) \wedge q' \equiv (p \wedge q') \vee (q \wedge q') \equiv p \wedge q'\]
\[(p \vee q) \wedge p' \equiv (p \wedge p') \vee (q \wedge p') \equiv q \wedge p'\]
Buradan
\[ \begin{aligned} (p' \Leftrightarrow q)' &\equiv \big[(p \wedge q') \vee (q \wedge p')\big]' \\[2pt] &\equiv (p \wedge q')' \wedge (q \wedge p')' && \text{(De Morgan)} \\[2pt] &\equiv (p' \vee q) \wedge (q' \vee p) \\[2pt] &\equiv (p \Rightarrow q) \wedge (q \Rightarrow p) \\[2pt] &\equiv p \Leftrightarrow q \end{aligned} \]
\(\blacksquare\)
7.4 Denklik Araştırmaları
Örnek 7.5 (Denk mi, Değil mi?) \(p, q, r\) ilkel önermeler olmak üzere aşağıdaki önerme çiftlerinin denk olup olmadığını araştırınız.
a) \(q \Rightarrow (p \wedge p')\) ve \(q\) b) \(p \Rightarrow q\) ve \(q' \Rightarrow p'\)
c) \((p \vee q) \Rightarrow r\) ve \((p \Rightarrow r) \wedge (q \Rightarrow r)\) d) \((p \wedge q) \vee (p \wedge r)\) ve \(p \vee (q \wedge r)\)
Çözüm
a)
\[q \Rightarrow (p \wedge p') \equiv q' \vee (p \wedge p') \equiv q' \vee c \equiv q'\]
Sonuç \(q'\)’dür ve \(q' \not\equiv q\)’dur. O hâlde bu iki önerme denk değildir.
b)
\[p \Rightarrow q \equiv p' \vee q \equiv q \vee p' \equiv (q')' \vee p' \equiv q' \Rightarrow p'\]
Denktir; bu zaten Teorem 6.3 ile bildiğimiz karşıt ters denkliğidir.
c)
\[ \begin{aligned} (p \vee q) \Rightarrow r &\equiv (p \vee q)' \vee r \\[2pt] &\equiv (p' \wedge q') \vee r && \text{(De Morgan)} \\[2pt] &\equiv (p' \vee r) \wedge (q' \vee r) && \text{($\vee$'nin $\wedge$ üzerine dağılması)} \\[2pt] &\equiv (p \Rightarrow r) \wedge (q \Rightarrow r) \end{aligned} \]
Denktir.
d) Sol tarafı dağılma özelliğiyle sadeleştirelim:
\[(p \wedge q) \vee (p \wedge r) \equiv p \wedge (q \vee r)\]
Sağ taraf ise \(p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)\)’dir. Bu ikisi denk değildir.
Karşı örnek. \(p \equiv 1\), \(q \equiv 0\), \(r \equiv 0\) alalım:
\[p \wedge (q \vee r) \equiv 1 \wedge 0 \equiv 0, \qquad p \vee (q \wedge r) \equiv 1 \vee 0 \equiv 1\]
\(\blacksquare\)
\((d)\) şıkkındaki iki ifade birbirine çok benzer görünse de farklıdır:
\[(p \wedge q) \vee (p \wedge r) \equiv p \wedge (q \vee r), \qquad (p \vee q) \wedge (p \vee r) \equiv p \vee (q \wedge r)\]
Ortak çarpan parantezin dışına çıkarken kendi bağlacıyla çıkar: “ve” ile bağlıysa dışarıda “ve”, “veya” ile bağlıysa dışarıda “veya” kalır. Parantezin içindeki bağlaç ise diğeridir.
7.5 Çözümlü Uygulamalar
Örnek 7.6 (Dağılma Aksiyomu) Doğruluk tablosu kullanmadan
\[\big[p \Rightarrow (q \Rightarrow r)\big] \Rightarrow \big[(p \Rightarrow q) \Rightarrow (p \Rightarrow r)\big]\]
bileşik önermesinin totoloji olduğunu gösteriniz.
Çözüm
Önce iki tarafı da \(\wedge, \vee, {}'\) diline çevirelim:
\[ \begin{aligned} &\big[p \Rightarrow (q \Rightarrow r)\big] \Rightarrow \big[(p \Rightarrow q) \Rightarrow (p \Rightarrow r)\big] \\[4pt] &\equiv \big[p' \vee (q' \vee r)\big] \Rightarrow \big[(p' \vee q)' \vee (p' \vee r)\big] \\[4pt] &\equiv \big[p' \vee q' \vee r\big]' \vee \big[(p \wedge q') \vee p' \vee r\big] && \text{(De Morgan)} \\[4pt] &\equiv (p \wedge q \wedge r') \vee (p \wedge q') \vee p' \vee r && \text{(De Morgan)} \end{aligned} \]
Şimdi \(r\) ile ilk terimi birleştirelim. \(X \vee (Y \wedge X') \equiv X \vee Y\) kuralı gereği:
\[r \vee (p \wedge q \wedge r') \equiv r \vee (p \wedge q)\]
Buradan
\[ \begin{aligned} &\equiv (p \wedge q) \vee (p \wedge q') \vee p' \vee r \\[2pt] &\equiv \big[p \wedge (q \vee q')\big] \vee p' \vee r && \text{(dağılma, ters yönde)} \\[2pt] &\equiv (p \wedge t) \vee p' \vee r \\[2pt] &\equiv (p \vee p') \vee r \equiv t \vee r \equiv t \end{aligned} \]
O hâlde verilen önerme bir totolojidir.
\(\blacksquare\)
Örnek 7.7 (Totoloji Midir?) \((p \vee q) \Rightarrow \big[q \Rightarrow (p \wedge q)\big]\) önermesi totoloji midir?
Çözüm
\[ \begin{aligned} (p \vee q) \Rightarrow \big[q \Rightarrow (p \wedge q)\big] &\equiv (p \vee q)' \vee \big[q' \vee (p \wedge q)\big] \\[2pt] &\equiv (p' \wedge q') \vee q' \vee (p \wedge q) && \text{(De Morgan)} \\[2pt] &\equiv q' \vee (p \wedge q) && \text{(yutma: $q' \vee (q' \wedge p') \equiv q'$)} \\[2pt] &\equiv (q' \vee p) \wedge (q' \vee q) && \text{(dağılma)} \\[2pt] &\equiv (q' \vee p) \wedge t \\[2pt] &\equiv q' \vee p \end{aligned} \]
Sonuç \(q' \vee p\)’dir; totoloji değildir. \(p \equiv 0\), \(q \equiv 1\) için değeri \(0\) olur.
\(\blacksquare\)
Örnek 7.8 (p’ Önermesini Gerektirme) Her \(p, q\) önermesi için \((p \Rightarrow q) \wedge q'\) önermesinin \(p'\) önermesini mantıksal gerektirip gerektirmediğini araştırınız.
Çözüm
\[ \begin{aligned} \big[(p \Rightarrow q) \wedge q'\big] \Rightarrow p' &\equiv \big[(p' \vee q) \wedge q'\big]' \vee p' \\[2pt] &\equiv \big[(p' \wedge q') \vee (q \wedge q')\big]' \vee p' && \text{(dağılma)} \\[2pt] &\equiv \big[(p' \wedge q') \vee c\big]' \vee p' \\[2pt] &\equiv (p' \wedge q')' \vee p' \\[2pt] &\equiv (p \vee q) \vee p' && \text{(De Morgan)} \\[2pt] &\equiv (p \vee p') \vee q \equiv t \vee q \equiv t \end{aligned} \]
O hâlde \((p \Rightarrow q) \wedge q'\) önermesi \(p'\) önermesini mantıksal olarak gerektirir. Bu, Teorem 7.2 ile aynı sonuçtur.
\(\blacksquare\)
Buraya kadar bütün önermeler değişken içermiyordu. Bir sonraki bölümde değişken içeren ifadeleri, yani açık önermeleri ve niceleyicileri inceleyeceğiz.