Algoritmalarda Ve Matematiksel İspatlarda Mantık Bağlaçları Ve Nicelikleri Ders Notu

Mantık Bağlaçları ve Nicelikleri 🚀

Matematik ve bilgisayar bilimlerinde, doğru ve yanlış ifadeleri analiz etmek, argümanları değerlendirmek ve problemleri çözmek için mantık kuralları kullanılır. Bu ders notunda, önermeler, mantık bağlaçları, niceleyiciler ve basit ispat yöntemleri ele alınacaktır.

1. Önermeler ve Doğruluk Değerleri

• Bir önerme (proposition), doğru ya da yanlış kesin bir hüküm bildiren ifadedir. Bir ifadenin aynı anda hem doğru hem de yanlış olması mümkün değildir.
• Önermelerin doğruluk değeri ‘D’ (Doğru) veya ‘1’, ‘Y’ (Yanlış) veya ‘0’ ile gösterilir.
• Örnekler:
  • "Ankara, Türkiye'nin başkentidir." (Doğruluk değeri: D veya 1)
  • "2 + 3 = 6" (Doğruluk değeri: Y veya 0)
  • "Bugün hava güzel mi?" (Önerme değildir, soru cümlesidir.)
  • "Hadi dışarı çıkalım!" (Önerme değildir, emir cümlesidir.)

2. Bileşik Önermeler ve Mantık Bağlaçları

İki veya daha fazla önermenin mantık bağlaçları ile birleştirilmesiyle elde edilen yeni önermelere bileşik önerme denir.

2.1. "Ve" Bağlacı (Tümel Evetleme) \( \land \)

• İki önermenin "ve" bağlacı ile bağlanmasıyla oluşan bileşik önerme, her iki önerme de doğru iken doğru, diğer tüm durumlarda yanlıştır.
• \( p \land q \) şeklinde gösterilir.

\( p \)	\( q \)	\( p \land q \)
1	1	1
1	0	0
0	1	0
0	0	0

2.2. "Veya" Bağlacı (Tümel Ayrılma) \( \lor \)

• İki önermenin "veya" bağlacı ile bağlanmasıyla oluşan bileşik önerme, her iki önerme de yanlış iken yanlış, diğer tüm durumlarda doğrudur.
• \( p \lor q \) şeklinde gösterilir.

\( p \)	\( q \)	\( p \lor q \)
1	1	1
1	0	1
0	1	1
0	0	0

2.3. "Değili" Bağlacı (Olumsuzlama) \( \neg \)

• Bir önermenin hükmünü değiştiren bağlaçtır. Bir önerme doğru ise değili yanlış, yanlış ise değili doğrudur.
• \( \neg p \) veya \( p' \) şeklinde gösterilir.

\( p \)	\( \neg p \)
1	0
0	1

2.4. "Ya da" Bağlacı (Tekli Ayrılma) \( \underline{\lor} \)

• İki önermenin "ya da" bağlacı ile bağlanmasıyla oluşan bileşik önerme, önermelerden sadece biri doğru iken doğru, diğer durumlarda yanlıştır. (Her ikisi de doğru veya her ikisi de yanlış ise yanlıştır.)
• \( p \underline{\lor} q \) şeklinde gösterilir.

\( p \)	\( q \)	\( p \underline{\lor} q \)
1	1	0
1	0	1
0	1	1
0	0	0

2.5. "İse" Bağlacı (Koşullu Önerme) \( \implies \)

• İki önermenin "ise" bağlacı ile bağlanmasıyla oluşan bileşik önerme, ilk önerme doğru iken ikinci önerme yanlış ise yanlış, diğer tüm durumlarda doğrudur.
• \( p \implies q \) şeklinde gösterilir. "p ise q", "p gerektirir q", "p yeterlidir q için", "q gereklidir p için" şekillerinde okunabilir.

\( p \)	\( q \)	\( p \implies q \)
1	1	1
1	0	0
0	1	1
0	0	1

Unutma: \( p \implies q \) önermesi \( \neg p \lor q \) önermesine denktir. Yani \( (p \implies q) \equiv (\neg p \lor q) \).

2.6. "Ancak ve Ancak" Bağlacı (İki Yönlü Koşullu Önerme) \( \iff \)

• İki önermenin "ancak ve ancak" bağlacı ile bağlanmasıyla oluşan bileşik önerme, her iki önermenin de doğruluk değerleri aynı ise doğru, farklı ise yanlıştır.
• \( p \iff q \) şeklinde gösterilir. "p ancak ve ancak q", "p'nin q için gerek ve yeter koşulu" şeklinde okunabilir.

\( p \)	\( q \)	\( p \iff q \)
1	1	1
1	0	0
0	1	0
0	0	1

3. Denk Önermeler (Eş Değerlilik)

• Doğruluk değerleri aynı olan iki önermeye denk önermeler denir. \( p \equiv q \) şeklinde gösterilir.
• Örnek: \( p \land q \) ile \( q \land p \) önermeleri birbirine denktir. Yani \( (p \land q) \equiv (q \land p) \).

4. Totoloji ve Çelişki

• Bir bileşik önerme, bileşenlerinin tüm doğruluk değerleri için daima doğru (1) oluyorsa bu önermeye totoloji denir.
• Bir bileşik önerme, bileşenlerinin tüm doğruluk değerleri için daima yanlış (0) oluyorsa bu önermeye çelişki denir.
• Örnek: \( p \lor (\neg p) \) bir totolojidir. \( p \land (\neg p) \) bir çelişkidir.

5. De Morgan Kuralları 📚

• Bileşik önermelerin değilini alırken kullanılan önemli kurallardır:
  • \( \neg (p \land q) \equiv (\neg p \lor \neg q) \)
  • \( \neg (p \lor q) \equiv (\neg p \land \neg q) \)

6. Açık Önermeler ve Niceleyiciler

İçinde en az bir değişken bulunduran ve değişkenlere verilen değerlere göre doğru ya da yanlış olabilen ifadelere açık önerme denir.

• Örnek: "x bir doğal sayıdır ve \( x > 5 \)". Burada x'e 6 verirsek doğru, 3 verirsek yanlış olur.

6.1. Evrensel Niceleyici (Her) \( \forall \)

• "Her", "bütün", "tüm" gibi anlamlara gelir. Bir açık önermeyi tüm elemanlar için geçerli kıldığını belirtir.
• \( \forall x, P(x) \) şeklinde gösterilir ve "Her x için P(x) doğrudur" şeklinde okunur.
• Örnek: \( \forall x \in \mathbb{N}, x+1 > x \) (Her doğal sayı x için, x+1, x'ten büyüktür. Bu önerme doğrudur.)

6.2. Varlıksal Niceleyici (Bazı) \( \exists \)

• "Bazı", "en az bir", "vardır" gibi anlamlara gelir. Bir açık önermenin en az bir eleman için geçerli olduğunu belirtir.
• \( \exists x, P(x) \) şeklinde gösterilir ve "Bazı x için P(x) doğrudur" veya "En az bir x için P(x) doğrudur" şeklinde okunur.
• Örnek: \( \exists x \in \mathbb{Z}, x^2 = 4 \) (En az bir tam sayı x için, \( x^2 \) 4'e eşittir. Bu önerme doğrudur, çünkü x=2 veya x=-2 olabilir.)

6.3. Niceleyicilerin Değili

• Niceleyicilerin değilini alırken \( \forall \) ve \( \exists \) yer değiştirir ve önermenin değili alınır:
  • \( \neg (\forall x, P(x)) \equiv (\exists x, \neg P(x)) \)
  • \( \neg (\exists x, P(x)) \equiv (\forall x, \neg P(x)) \)
• Örnek: "Her öğrenci dersini sever." (\( \forall x, P(x) \)) önermesinin değili "Bazı öğrenciler dersini sevmez." (\( \exists x, \neg P(x) \)) olur.

7. Matematiksel İspat Yöntemleri

Matematiksel bir önermenin doğru olduğunu gösterme sürecine ispat denir. 9. sınıf düzeyinde temel ispat yöntemleri ele alınır.

7.1. Doğrudan İspat Yöntemi

• Bir önermenin doğru olduğunu, bilinen aksiyomlar, tanımlar ve daha önce ispatlanmış teoremleri kullanarak adım adım gösterme yöntemidir.
• Genellikle \( p \implies q \) şeklindeki koşullu önermelerin ispatında kullanılır. \( p \) doğru kabul edilerek \( q \)'nun da doğru olduğu gösterilir.
• Örnek: "Eğer x tek sayı ise, \( x+1 \) çift sayıdır." ifadesini ispatlayalım.
  • Varsayım (p): x bir tek sayıdır.
  • Tanım gereği: Bir tam sayı k olmak üzere \( x = 2k+1 \) şeklinde yazılabilir.
  • İfadeyi düzenleyelim: \( x+1 = (2k+1)+1 = 2k+2 = 2(k+1) \).
  • Sonuç (q): \( 2(k+1) \) ifadesi, 2'nin bir katı olduğu için çift sayıdır. Dolayısıyla \( x+1 \) çift sayıdır.
  • Bu durumda, x tek sayı ise \( x+1 \) çift sayıdır önermesi doğrudan ispatlanmış olur.

7.2. Çelişki ile İspat Yöntemi (Dolaylı İspat)

• İspatlanmak istenen önermenin yanlış olduğunu varsayarak başlanır. Bu varsayımın, bilinen bir gerçekle veya başka bir önermeyle çeliştiği (tutarsız olduğu) gösterilir. Bu çelişki, başlangıçtaki varsayımın yanlış olduğu ve dolayısıyla ispatlanmak istenen önermenin doğru olduğu sonucunu doğurur.
• Genellikle \( p \implies q \) şeklindeki önermelerde, \( p \) doğru ve \( q \) yanlış (yani \( p \land \neg q \)) kabul edilerek çelişki aranır.
• Örnek: "Eğer \( x^2 \) tek sayı ise, x de tek sayıdır." ifadesini çelişki ile ispatlayalım.
  • Varsayımın değili: \( x^2 \) tek sayı olsun, fakat x çift sayı olsun.
  • Tanım gereği: x çift sayı ise, bir tam sayı k olmak üzere \( x = 2k \) şeklinde yazılabilir.
  • İfadeyi düzenleyelim: \( x^2 = (2k)^2 = 4k^2 = 2(2k^2) \).
  • Sonuç: \( x^2 = 2(2k^2) \) ifadesi, 2'nin bir katı olduğu için \( x^2 \) çift sayıdır.
  • Çelişki: Biz başlangıçta \( x^2 \) tek sayı olduğunu varsaymıştık, ancak varsayımın değili (x çift) bizi \( x^2 \) çift sayı sonucuna götürdü. Bu bir çelişkidir.
  • Sonuç: Bu çelişki, başlangıçtaki "x çift sayı olsun" varsayımımızın yanlış olduğunu gösterir. Dolayısıyla, x tek sayı olmak zorundadır.

7.3. Aksine Örnek Verme Yöntemi

• Bir genel ifadenin veya önermenin yanlış olduğunu göstermek için, o ifadenin geçerli olmadığı tek bir örnek (aksine örnek) bulmak yeterlidir.
• Bu yöntem genellikle "Her zaman..." veya "Tüm..." gibi niceleyiciler içeren önermelerin yanlışlığını göstermek için kullanılır.
• Örnek: "Her asal sayı tek sayıdır." önermesinin yanlışlığını gösterelim.
  • Asal sayılar: 2, 3, 5, 7, 11, ...
  • Tek sayılar: 1, 3, 5, 7, 9, 11, ...
  • Aksine örnek: 2 bir asal sayıdır, ancak tek sayı değildir (çift sayıdır).
  • Bu tek örnek, "Her asal sayı tek sayıdır" önermesinin yanlış olduğunu ispatlar.