9. Sınıf Matematik Mantık Bağlaçları ve Niceleyicilerin Algoritmik Problemlerde Kullanımı Konu Anlatımı

Mantık Bağlaçları ve Niceleyicilerin Algoritmik Problemlerde Kullanımı

İki kişi mesajlaşırken cihazlarının güvenli bir bağlantı kurabilmesi için ortak bir gizli anahtara ihtiyaç vardır. Ancak bu anahtarı açık bir kanaldan doğrudan göndermek tehlikelidir. Diffie-Hellman anahtar değiş tokuşu yöntemi bu sorunu matematikle çözer: Taraflar yalnızca bazı ara değerleri birbirine gönderir, gizli anahtarı ise her biri kendi cihazında hesaplar. Bu yöntemde asal sayılar, üslü ifadeler ve kalan bulma işlemleri kullanılır; algoritmanın sonunda “iki tarafın bulduğu anahtarlar eşit ise güvenli iletişim kurulur” şeklinde bir karar verilir.

Mantık bağlaçları ve niceleyiciler, matematiksel önermelerin yapı taşlarıdır. Önermeleri birleştirir, ne kadar genel olduklarını belirler ve hem matematiksel ispatları hem de algoritmaları şekillendirir. Bu konuda bir önermenin cebirsel ispatını, aynı önermeyi kontrol eden bir algoritmayla karşılaştıracak; ispat ve algoritma süreçlerinde bağlaç ve niceleyicilerin nasıl kullanıldığını göreceğiz.

Bu konunun sonunda şunları yapabiliyor olmalısın:

• bağlaç ve niceleyici içeren bir önermeyi okuyup anlamını açıklamak,
• basit önermeleri cebirsel olarak ispatlamak ve ispat adımlarını sözel olarak ifade etmek,
• ispat adımlarından bir algoritma (doğal dil, akış şeması, sözde kod) oluşturmak,
• algoritmayı test etmek ve test ile ispat arasındaki farkı açıklamak,
• bölünebilme, basamak ayırma ve kalan bulma algoritmalarını bağlaçlarla kurmak,
• Diffie-Hellman gibi bir algoritmanın adımlarını izleyip kararını belirlemek.

1. Önerme, İspat ve Algoritma

Matematikte bir önermenin doğru olduğunu göstermek için ispat yapılır. “Her” niceleyicisiyle kurulan bir önerme, sonsuz sayıda eleman hakkında bilgi verir. Bu yüzden önermenin birkaç örnek için doğru çıkması yeterli değildir; genel bir harfle (n, x, a gibi) yapılan cebirsel bir akıl yürütme gerekir.

Algoritma ise bir girdiyi alır, belirli adımları uygular ve bir çıktı üretir. Bir önermeyi kontrol eden algoritma, her girdi için “önerme bu sayı için doğru mu?” sorusunu yanıtlar. Algoritma çok sayıda girdi için çalıştırılarak test edilir. Test, önermenin bu girdiler için doğru olduğunu gösterir ama tüm sayılar için kanıt sunmaz. Öte yandan test sırasında önermeyi sağlamayan tek bir girdi bulunursa önermenin yanlış olduğu kesinleşir.

İspat ile algoritma arasındaki ilişki şöyle özetlenebilir:

• İspat adımları, algoritmanın adımlarına dönüştürülebilir.
• İspatta kullanılan “ise” bağlacı, algoritmada karar adımına (eğer … ise … değilse …) dönüşür.
• İspattaki “ve” bağlacı, algoritmada koşulların birlikte kontrol edilmesine dönüşür.
• İspattaki “her” niceleyicisi, algoritmada bir döngüyle çok sayıda girdinin denenmesine karşılık gelir; ama döngü sonlu olduğu için ispatın yerini tutmaz.

2. Her Tek Tam Sayının Karesi Tektir

Önerme: ∀x ∈ Z için x tek ⇒ x² tek.

Cebirsel ispat:

1. adım: x tek bir tam sayı olsun. O hâlde bir n ∈ Z için x = 2n + 1 yazılabilir.
2. adım: x² = (2n + 1)² = 4n² + 4n + 1.
3. adım: 4n² + 4n + 1 = 2(2n² + 2n) + 1. Burada 2n² + 2n bir tam sayıdır; buna k diyelim.
4. adım: x² = 2k + 1 biçiminde yazılabildiğinden x² tektir.

İspatın sözel ifadesi: Herhangi bir tek tam sayıyı “bir çift sayı artı 1” biçiminde yazdık, karesini açtık ve sonucun da “bir çift sayı artı 1” olduğunu gösterdik. n herhangi bir tam sayı olabildiğinden sonuç her tek tam sayı için geçerlidir.

Bu önermeyi kontrol eden algoritma:

1. adım: Başla.
2. adım: Bir tam sayı x al.
3. adım: x % 2 = 1 değilse “x tek değil” yaz ve bitir.
4. adım: y ← x * x hesapla.
5. adım: y % 2 = 1 ise “karesi tek” yaz; değilse “önerme bu sayı için yanlış” yaz.
6. adım: Bitir.

Algoritma −9'dan 9'a kadar olan tek tam sayılar için çalıştırıldığında her seferinde “karesi tek” çıktısı verir (örneğin (−7)² = 49, 9² = 81). Ancak bu test sonlu sayıda sayıyı kapsar; önermenin her tek tam sayı için doğru olduğunu gösteren cebirsel ispattır.

Not: Bazı programlama dillerinde negatif sayıların kalanı farklı hesaplanabilir; bu yüzden tek sayı kontrolü x % 2 != 0 biçiminde de yazılabilir.

3. Bölünebilme Önermeleri ve Basamak Ayırma

Basamakları Ayırmak

Üç basamaklı abc sayısının basamakları algoritmada şu işlemlerle elde edilir:

• a ← abc / 100 (bölümün tam kısmı alınır),
• b ← (abc / 10) % 10 (önce bölümün tam kısmı alınır, sonra 10 ile bölümünden kalan bulunur),
• c ← abc % 10.

Örneğin 738 için: a = 738 / 100 → 7; b = (738 / 10) % 10 = 73 % 10 = 3; c = 738 % 10 = 8.

6'ya Bölünebilme

Önerme: abc üç basamaklı bir doğal sayı; k ∈ Z ve m, n ∈ Z⁺ olmak üzere (a + b + c = 3m ∧ c = 2k) ⇒ abc = 6n.

Bu önermede “ve” bağlacı iki koşulun birlikte sağlanması gerektiğini, “ise” bağlacı bu koşullar sağlandığında sonucun geleceğini anlatır.

İspat:

abc = 100a + 10b + c = (99a + 9b) + (a + b + c) yazılır. 99a + 9b = 3(33a + 3b) olduğundan 3'ün katıdır. a + b + c = 3m verildiğinden abc, 3'ün iki katının toplamıdır; yani 3'ün katıdır.

c = 2k ise birler basamağı çifttir; 100a + 10b çift olduğundan abc çifttir, yani 2'nin katıdır.

abc hem 2'nin hem de 3'ün katı olduğundan 6'nın katıdır: abc = 6n.

Bu ispattan elde edilen sözde kod:

Girdi: abc Çıktı: abc'nin 6'ya tam bölünüp bölünmediği Başla a ← abc / 100 (tam kısım) b ← (abc / 10) % 10 c ← abc % 10 eğer (a + b + c) % 3 = 0 ve c % 2 = 0 ise yazdır “abc, 6'ya tam bölünür.” değilse yazdır “abc, 6'ya tam bölünmez.” Bitir

Burada “ve” bağlacı iki eşitliğin aynı anda sağlanmasını kontrol eder; “ise” bağlacı da bu kontrolün sonucuna göre farklı çıktılar üretilmesini sağlar.

9'a Bölünebilme

Benzer şekilde (a + b + c = 9m) ⇒ abc = 9n önermesi doğrudur: abc = 9(11a + b) + (a + b + c) olduğundan rakamlar toplamı 9'un katıysa sayı da 9'un katıdır. Algoritmada koşul (a + b + c) % 9 = 0 biçiminde yazılır.

8'e Bölünebilme

Üç basamaklı bir sayı için 100a + 10b + c = (96a + 8b) + (4a + 2b + c) yazılabilir. 96a + 8b = 8(12a + b) olduğundan 8'in katıdır. Bu yüzden:

Önerme: (4a + 2b + c = 8m) ⇒ abc = 8n.

Algoritmada koşul (4 * a + 2 * b + c) % 8 = 0 biçiminde kontrol edilir.

4. Doğrusal Fonksiyonun Artanlığı

Bir fonksiyonun artan olması tanımı niceleyici ve bağlaçlarla yazılır: ∀x₁, x₂ ∈ R için x₁ < x₂ ⇒ f(x₁) < f(x₂).

Önerme: ∀a > 0 için f: R → R, f(x) = ax + b doğrusal fonksiyonu artandır.

İspat:

1. adım: a > 0 olsun ve x₁ < x₂ olacak şekilde herhangi iki gerçek sayı seçelim.
2. adım: f(x₂) − f(x₁) = (ax₂ + b) − (ax₁ + b) = a(x₂ − x₁).
3. adım: x₂ − x₁ > 0 ve a > 0 olduğundan a(x₂ − x₁) > 0'dır.
4. adım: O hâlde f(x₁) < f(x₂) olur. x₁ ve x₂ keyfî seçildiğinden fonksiyon artandır.

İspatın algoritmik ifadesi: a, b, x₁, x₂ girdilerini al; x₁ < x₂ ve a > 0 koşullarını kontrol et; fark ← a * (x₂ − x₁) hesapla; fark > 0 ise “f(x₁) < f(x₂)” yazdır. Buradaki “ve” bağlacı iki varsayımın birlikte kullanılmasını, “her” niceleyicisi ise sonucun tüm x₁ < x₂ çiftleri için geçerli olduğunu anlatır.

5. Çarpımı Sıfır Olan Sayılar

Önerme: ∀a, b ∈ R için a · b = 0 ⇒ (a = 0 ∨ b = 0).

İspat: a · b = 0 olsun. a = 0 ise önerme sağlanır. a ≠ 0 ise eşitliğin iki tarafı 1/a ile çarpılır: (1/a) · a · b = 0 ⇒ b = 0. Her iki durumda da a = 0 veya b = 0 olur.

Bu ispatta “veya” bağlacı, iki durumdan en az birinin gerçekleştiğini anlatır. İspat, “a = 0 mı?” sorusuyla iki duruma ayrılır; algoritmada bu, bir karar adımıyla gösterilir:

Girdi: a, b Başla eğer a * b = 0 ise eğer a = 0 ise yazdır “a sıfırdır.” değilse yazdır “b sıfırdır.” Bitir

Not: İki sayı da sıfır olabilir; “veya” bağlacı bu durumu da kapsar.

6. Diffie-Hellman Anahtar Değiş Tokuşu

Bu algoritmada bir asal sayı p ve bir taban g herkese açıktır. Uğur'un cihazının gizli sayısı a, Elif'in cihazının gizli sayısı b'dir.

1. Uğur'un cihazı A = g^a % p, Elif'in cihazı B = g^b % p değerini hesaplar.
2. Cihazlar A ve B değerlerini birbirine gönderir. (Bu değerler açık kanaldan gidebilir.)
3. Uğur'un cihazı u = B^a % p, Elif'in cihazı e = A^b % p değerini hesaplar.
4. u = e ise güvenli iletişim kurulur; değilse kurulmaz.

Matematiksel olarak u = (g^b)^a % p = g^(a·b) % p ve e = (g^a)^b % p = g^(a·b) % p olduğundan iki değer her zaman eşit çıkar. Gizli sayılar a ve b hiç gönderilmez; yalnızca A ve B'yi bilen biri için g^(a·b) % p değerini bulmak, sayılar büyük seçildiğinde çok zordur. Bu yüzden asal sayının ve tabanın uygun seçilmesi güvenlik açısından önemlidir.

Sınavlarda Sık Görülen Soru Kalıpları

Kalıp 1: Sözde Kodu Çalıştırma

Basamak ayıran ve bölünebilme kontrol eden bir sözde kod verilir; bir girdi için çıktı sorulur.

Kalıp 2: İspat Adımı

Bir ispatın eksik adımı sorulur.

Kalıp 3: Test ve İspat

Bir algoritmanın test sonuçlarından ne çıkarılabileceği sorulur.

Kalıp 4: Mod ve Anahtar

Diffie-Hellman değerleri istenir.

Sık Karıştırılan Noktalar

• Bir algoritmanın sonlu sayıda örnekle test edilmesi “her” önermesini ispatlamaz.
• Tek bir karşı örnek “her” ile kurulan önermeyi çürütmeye yeter.
• abc / 100 işleminde bölümün tam kısmı alınır; (abc / 10) % 10 onlar basamağını verir.
• 6'ya bölünmede iki koşul “ve” ile bağlanır; yalnız birinin sağlanması yetmez.
• 8'e bölünme için üç basamaklı sayıda 4a + 2b + c, 9'a bölünme için a + b + c kontrol edilir.
• a · b = 0 ⇒ (a = 0 ∨ b = 0) önermesinde “veya” iki sayının birden sıfır olmasını da kapsar.
• Diffie-Hellman'da gizli sayılar (a ve b) gönderilmez; yalnız A ve B gönderilir.

Soru Çözerken Kullanılabilecek Yaklaşım

• Önermeyi okurken niceleyiciyi, varsayımı ve sonucu ayrı ayrı belirle.
• İspatta genel bir harf kullan (tek sayı 2n + 1, çift sayı 2n gibi).
• İspat adımlarını tek tek sözel olarak ifade et; her adımın gerekçesini yaz.
• Algoritmada varsayımları karar adımına, sonuçları çıktılara dönüştür.
• Sözde kodu verilen girdiyle satır satır çalıştır; ara değerleri tabloya yaz.
• Mod işlemlerinde büyük sayıları adım adım küçült; bölüm ve kalanı kontrol et.

Konu Özeti

Mantık bağlaçları ve niceleyiciler, matematiksel ispatlarda ve algoritmalarda dört temel işlev görür: koşullara göre karar vermek, adımları birleştirmek, genellemek veya özelleştirmek ve sembolik ifadeleri netleştirmek. “Her tek tam sayının karesi tektir”, “rakamlar toplamı 3'ün katı ve birler basamağı çift olan sayı 6'nın katıdır”, “a > 0 ise ax + b artandır” ve “çarpımı sıfır olan iki sayıdan en az biri sıfırdır” gibi önermeler cebirsel olarak ispatlanır; ispat adımları da algoritmalara dönüştürülür. Algoritmada “ve” koşulların birlikte kontrolünü, “veya” durumlardan en az birini, “ise” karar adımını sağlar. Algoritma testleri önermeyi destekler ama ispat yerine geçmez; tek bir karşı örnek ise önermeyi çürütür. Diffie-Hellman yöntemi, üslü ifadeler ve kalan bulma ile iki cihazın ortak gizli anahtar oluşturmasını sağlar ve “u = e ise güvenli iletişim” kararıyla sonuçlanır.