9. Sınıf Matematik Mantık Bağlaçları ve Niceleyiciler Ders Notu

Mantık Bağlaçları ve Niceleyiciler – Ders Notu

Önerme: doğru ya da yanlış olduğu kesin söylenebilen ifade. Bağlaçlarla birleşen önermeler bileşik önerme oluşturur. Algoritmalardaki karar adımları bu önermelerle kurulur.

Bağlaçlar

• Ve (∧): hepsi doğruysa doğru. Örnek: x % 2 = 0 ∧ x % 3 = 0 ⇒ 6'ya bölünme.
• Veya (∨): en az biri doğruysa doğru. Örnek: b = 0 ∨ b = 5 ⇒ 5'e bölünme.
• Ya da (⊻): yalnız biri doğruysa doğru. Örnek: vavien devrede lamba, A ⊻ B açıkken yanar.
• İse (⇒): koşul sağlanırsa komut uygulanır (eğer … ise … değilse …).

Doğruluk özeti (p, q): D, D ⇒ ve D, veya D, ya da Y. D, Y veya Y, D ⇒ ve Y, veya D, ya da D. Y, Y ⇒ hepsi Y.

Niceleyiciler

• Her (∀): tüm ögeler için doğru; tek karşı örnek yanlışlar.
• Bazı (∃): en az bir öge için doğru; tek örnek doğrular.
• A = {2, 4, 6, 9}: “her x çift” yanlış; “bazı x tek” doğru.

Tablodan Seçim

• Ve ⇒ koşulları sağlayanların kesişimi.
• Veya ⇒ birleşimi.
• “En az 85” >= 85; “85'ten fazla” > 85.
• Bir koşul ile tersi aynı anda sağlanamaz; biri sağlanmıyorsa diğeri sağlanır.

Kadane Algoritması

Ardışık elemanların en büyük toplamı: her adımda önceki toplam negatifse bırak, değilse ekle; en büyüğü güncelle. Tüketme yaklaşımı tüm ardışık toplamları (n(n + 1)/2 tane) inceler, yavaştır.

Önerme ve Algoritma Bağlantısı

Karar adımındaki her koşul bir önermedir. Sözde kodda “eğer koşul ise … değilse …” yapısı ise bağlacını, “her eleman için” döngüsü her niceleyicisini, “koşulu sağlayan ilk elemanı bulunca dur” yapısı bazı niceleyicisini kullanır. Bazı niceleyicisi tek örnekle doğrulandığından algoritma erken durabilir; her niceleyicisini doğrulamak için tüm elemanlar kontrol edilmelidir. Vavien devre (lamba = A ⊻ B) ve Cezeri'nin fil saati (kap battı ise çan çal, sonra döngüyü yenile) bu yapıların gerçek sistemlerdeki örnekleridir.

Kısa Özet

Ve hepsini, veya en az birini, ya da yalnız birini ister; ise koşullu komut verir. Her tümü, bazı en az birini kapsar. Bu yapılar veri süzmede, akış şemalarında ve Kadane gibi verimli algoritmalarda kullanılır.