Computer Science
Mantıksal Çıkarımları Kanıtlamak: Düz Yol mu, Arka Kapı mı?
November 19, 2025
Bilgisayar bilimciler ve matematikçiler olarak hayatımız “Eğer … ise …” cümleleri üzerine kuruludur. Bir algoritmanın karmaşıklığını analiz ederken veya bir veri yapısının tutarlılığını kontrol ederken sürekli şu kalıbı kullanırız: “Eğer bu koşul sağlanıyorsa, şu sonuç gerçekleşmelidir.” Matematiksel dilde buna gerektirme ($P \implies Q$) diyoruz.
Peki, bu iddialı cümlelerin arkasını nasıl doldururuz? Her zaman tek bir yol mu vardır? Aşağıda matematikte ve bilgisayar biliminde sıkça kullanılan iki farklı yaklaşımı, örneklerle inceleyelim.
1. Yöntem: Doğrudan Kanıt (Direct Proof)
En sezgisel yöntemdir. Bir tartışmada karşınızdakine “Peki, dediğin gibi olsun…” diyerek başlamaya benzer.
Strateji:
- İddianın ilk kısmını ($P$) doğru kabul et.
- Matematiksel kuralları kullanarak ikinci kısmın ($Q$) doğru olduğunu göster.
Örnek: Tek Sayıların Karesi
Kanıtlamak istediğimiz ifade:
Teorem: Eğer $n$ bir tek sayı ise, $n^2$ de bir tek sayıdır.
Bu ifadeyi test etmek kolaydır (3 → 9, 5 → 25…), ama kanıt için genel bir dil gerekir.
Kanıt:
$n$ tek bir sayı olsun. O halde bir tam sayı $k$ için:
\[n = 2k + 1\]Şimdi $n^2$’ye bakalım:
\[n^2 = (2k + 1)^2 = 4k^2 + 4k + 1\]İlk iki terimi 2 parantezine alırsak:
\[n^2 = 2(2k^2 + 2k) + 1\]Parantez içi bir tam sayıdır; buna $m$ diyelim:
\[n^2 = 2m + 1\]Bu form, $n^2$’nin tek sayı tanımına uyar. Böylece sonuç tamamlanır. $\square$
2. Yöntem: Karşıt Ters (Proof by Contrapositive)
Bazen doğrudan gitmek zordur. Böyle durumlarda gerektirmenin mantıksal eşdeğeri olan karşıt ters devreye girer.
Bir gerektirme ($P \implies Q$), karşıt tersine eşdeğerdir:
“Eğer $Q$ yanlışsa, $P$ de yanlıştır.”
($\neg Q \implies \neg P$)
Örnek: Zor Bir Denklem
Teorem: Eğer $3n + 2$ ifadesi tek bir sayı ise, o zaman $n$ tek sayıdır.
Bunu doğrudan kanıtlamak zahmetlidir, çünkü:
\[3n + 2 = 2k + 1 \implies n = \frac{2k - 1}{3}\]Bu ifade tam sayı olup olmadığını garanti etmez. Bunun yerine karşıt tersi kanıtlanır:
“Eğer $n$ tek değilse (yani çiftse), $3n + 2$ de tek değildir (yani çifttir).”
Kanıt (Karşıt Ters Yöntemiyle):
$n$ çift bir sayı olsun. Bir tam sayı $k$ için:
\[n = 2k\]Bu değeri $3n + 2$ içinde kullanalım:
\[3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)\]Sonuç $2 \times (\text{tam sayı})$ biçimindedir; yani çifttir.
Dolayısıyla karşıt ters doğru olduğundan, orijinal ifade de doğrudur. $\blacksquare$
Özet
Kanıt yöntemleri bir marangozun alet çantası gibidir. Bazen çekiç gerekir (Doğrudan Kanıt), bazen tornavida (Karşıt Ters).
- Verilen bilgi ($P$) işlenebilir ve basitse, Doğrudan Kanıt uygundur.
- Sonuç ($Q$) hakkında bilgi sahibi olmak başlangıçtan daha kolaysa veya olumsuzluk içeriyorsa, Karşıt Ters fazlasıyla etkilidir.
Referanslar
- Lehman, E., Leighton, F. T., & Meyer, A. R. (2010). Mathematics for Computer Science. MIT.
- Velleman, D. J. (2006). How to Prove It: A Structured Approach. Cambridge University Press.
Yorumlar