Mantık Bağlaçları ve Niceleyiciler: Algoritmik Problemler

Konu Özeti

Algoritmalar, bir problemi adım adım çözmek için kullanılan kurallar dizisidir. Bu adımların çoğu “eğer … ise …” gibi koşullar içerir ve bu koşullar mantık önermeleriyle kurulur. Niceleyiciler ise bir kümenin tüm elemanları ya da en az bir elemanı hakkında konuşmamızı sağlar. Bu konuda bu iki aracı kullanarak algoritmaların doğruluğunu nasıl sınayacağını öğreneceksin.

Temel Kavramlar

Bir algoritma; girdi, açık ve sıralı adımlar ile çıktıdan oluşur. İyi bir algoritmanın adımları belirsiz olmaz ve algoritma sonlu sürede biter.

• Problemi anla: verilenler ve istenenler nedir?
• Çözüm adımlarını sırayla yaz (akış şeması ya da sözel olarak).
• Koşul gereken yerde “eğer … ise … değilse …” yapısını kullan.
• Tekrar gereken yerde “… olduğu sürece tekrarla” yapısını kullan.
• Algoritmayı birkaç örnek değerle deneyerek doğrula.

Algoritmalardaki koşullar birer önermedir; doğru ya da yanlış değeri alabilen cümlelerdir. Önermeler bağlaçlarla birleştirilir ve bileşik önermenin doğruluk değeri aşağıdaki tabloyla bulunur.

De Morgan: (p ∧ q)′ ≡ p′ ∨ q′ ve (p ∨ q)′ ≡ p′ ∧ q′

Bir koşulu değillerken bağlaç değişir: “ve” “veya” olur, “veya” “ve” olur. Aşağıdaki sayı doğrusu, “x > 0 ve x < 10” koşulunun çözüm aralığını gösterir.

Niceleyiciler, bir koşulun kaç elemana uyduğunu belirtir.

• Her (∀): kümenin bütün elemanları için özellik sağlanır.
• Bazı (∃): özelliği sağlayan en az bir eleman vardır.
• “Her” önermesini çürütmek için tek bir karşı örnek yeterlidir.
• “Bazı” önermesini doğrulamak için tek bir örnek yeterlidir.

Değil alma: (∀x, p(x))′ ≡ ∃x, p(x)′ ve (∃x, p(x))′ ≡ ∀x, p(x)′

Algoritmada “her” niceleyicisi, tüm elemanların tek tek kontrol edilmesi demektir; biri bile koşulu bozarsa sonuç yanlış olur. “Bazı” niceleyicisi ise bir aramadır; koşulu sağlayan ilk elemanı bulunca durulabilir.