İç içe niceleyiciler ve çıkarım kuralları

Geçen hafta tek niceleyicili ifadeleri gördün. Gerçek matematik cümleleri ise genelde iki ya da üç niceleyici içerir: “her sayının bir tersi vardır”, “herkesten büyük bir sayı yoktur”. Bu sayfanın ilk yarısı bu ifadelerin nasıl okunacağını, doğruluk değerinin nasıl bulunacağını ve nasıl olumsuzlanacağını anlatıyor. İkinci yarısı çıkarım kurallarını (rules of inference) anlatıyor: öncüllerden sonuca adım adım, her adıma kural adı yazarak gitmek. Vizede ikisi de çıkar; niceleyici doğruluk değeri neredeyse kesin, “argüman geçerli mi” de sık gelir.

Altın kurallar:

1. Niceleyiciler soldan sağa okunur ve seçilir. Önce gelen önce seçilir; sonraki ona bakarak seçilebilir.
2. $\forall x\,\exists y$‘de $y$, $x$‘e bağlı olabilir. $\exists y\,\forall x$‘te olamaz.
3. Olumsuzlarken her niceleyici döner, sıra değişmez.
4. Geçerli argüman = öncüller doğruysa sonuç kesin doğru. Geçersizliği göstermek için öncüller T, sonuç F olan tek satır yeter.

İç içe niceleyiciler

$P(x, y)$ iki değişkenli bir yüklem olsun. $\forall x\,\exists y\, P(x,y)$ ifadesini iç içe iki döngü gibi düşün:

∀x ∃y P(x,y):   for each x:              (dış döngü, hepsi geçmeli)
                    search some y        (iç döngü, bir tane bulsan yeter)
                    with P(x,y) true
∃y ∀x P(x,y):   find ONE y such that
                    for each x: P(x,y)   (aynı y bütün x'lerle çalışmalı)

Yazılımcı gözüyle: $\forall$ bir for döngüsü içinde hepsinin true dönmesi, $\exists$ ise döngüde bir tane true bulunca break. Sıranın değişmesi döngülerin yer değiştirmesi demektir ve sonucu değiştirir.

Günlük dil örneği. Domain: takımdaki oyuncular ve antrenörler. $C(y, x)$: ”$y$, $x$‘in antrenörü”.

• $\forall x\,\exists y\, C(y, x)$: “Her oyuncunun bir antrenörü var.” Forvetin antrenörü bir kişi, defansınki başka biri olabilir.
• $\exists y\,\forall x\, C(y, x)$: “Herkesin antrenörü olan tek bir kişi var.” Çok daha güçlü bir iddia.

İkincisi doğruysa birincisi de doğrudur (o tek kişiyi herkes için seçersin). Tersi genelde doğru değil.

İki değişkenli dört temel ifade

Domain tam sayılar, $P(x, y)$: "$x < y$".

Sınavda bir ifadenin doğruluk değerini şöyle yazarsın:

• True diyorsan: $\exists$ için somut değeri ver (“take $y = x + 1$”), $\forall$ için keyfi elemanla göster (“for any integer $x$ …”).
• False diyorsan: $\forall$ için somut karşı örnek ver, $\exists$ için hiçbir elemanın sağlamadığını göster.

Çözümlü örnekler

Domain tam sayılar.

$\forall x\,\exists y\,(x = 2y)$. False. Counterexample $x = 1$: $1 = 2y$ ise $y = \tfrac12 \notin \mathbb{Z}$. (Domain reel sayılar olsaydı $y = x/2$ ile doğru olurdu.)

$\exists x\,\forall y\,(x + y = y)$. True. Take $x = 0$: $0 + y = y$ for every integer $y$.

$\forall x\,\exists y\,(xy = 1)$. False. Counterexample $x = 2$: $2y = 1$ tam sayı çözüm vermez. $x = 0$ da bozar.

TUZAK · “Sıra fark etmez” sanmak. $\forall x\,\exists y$ ile $\exists y\,\forall x$ sadece niceleyiciler aynı türdense ($\forall\forall$ ya da $\exists\exists$) yer değiştirebilir. Karışık niceleyicilerde sıra anlamı değiştirir.

Çeviri

Domain bir sınıftaki öğrenciler, $F(x, y)$: ”$x$ ve $y$ arkadaş”.

Kalıp: “every” ve “all” için $\forall$, “some”, “a”, “at least one” için $\exists$. İçteki bağlaç yine geçen haftanın kuralına uyar: $\forall$ altında koşul varsa $\to$, $\exists$ altında $\land$.

İç içe niceleyiciyi olumsuzlama

Kural geçen haftanınkiyle aynı, sadece birden fazla kez uygulanır: $\lnot$‘yi soldan sağa iterken her niceleyiciyi çevirirsin.

¬ ∀x ∃y (P(x,y) ∧ Q(x))
≡ ∃x ¬∃y (P(x,y) ∧ Q(x))
≡ ∃x ∀y ¬(P(x,y) ∧ Q(x))
≡ ∃x ∀y (¬P(x,y) ∨ ¬Q(x))        De Morgan

Kısıtlı niceleyicilerde kısıt olduğu gibi kalır: $\lnot\,\forall x > 0\; P(x) \equiv \exists x > 0\; \lnot P(x)$. “Her pozitif sayı sağlar” yanlışsa, sağlamayan bir pozitif sayı vardır.

Çıkarım kuralları (rules of inference)

Bir argüman (argument) öncüller (premises) ve bir sonuçtan (conclusion) oluşur. Argüman geçerli (valid) ise öncüllerin hepsi doğru olduğunda sonuç kesinlikle doğrudur. Yani $(p_1 \land p_2 \land \dots \land p_n) \to q$ bir tautology’dir. Geçerlilik içerikle değil, kalıpla ilgilidir.

Uzun doğruluk tablosu kurmak yerine bilinen geçerli kalıpları zincirlersin:

Niceleyicili kurallar:

İki klasik hata (fallacy)

• Affirming the conclusion: $p \to q$, $q$ $\therefore p$. Geçersiz. “Çok çalışan geçer. Ali geçti. O halde Ali çok çalıştı.” Belki şanslıydı.
• Denying the hypothesis: $p \to q$, $\lnot p$ $\therefore \lnot q$. Geçersiz. “Çok çalışan geçer. Ali çalışmadı. O halde Ali kaldı.” Belki yine de geçti.

İkisinde de bozan satır $p = F$, $q = T$: öncüller doğru, sonuç yanlış.

Çözümlü örnek: argümanı kurallarla çözmek

Premises: “If I wake up early and I am not tired, I go to the gym.” “I did not go to the gym.” “I woke up early.” Conclusion: “I was tired.”

Önce harf ver: $w$: wake up early, $h$: tired, $g$: go to the gym. Öncüller $(w \land \lnot h) \to g$, $\lnot g$, $w$. Sonuç $h$.

1. (w ∧ ¬h) → g      premise
2. ¬g                premise
3. ¬(w ∧ ¬h)         modus tollens, 1, 2
4. ¬w ∨ h            De Morgan + double negation, 3
5. w                 premise
6. h                 disjunctive syllogism, 4, 5   (¬w yanlış, kalan h)

Argüman geçerli. 4. adım bir çıkarım kuralı değil, denklik kanunu; bunu da adıyla yazman yeterli.

Çözümlü örnek: resolution

Premises $p \lor q$, $\lnot p \lor r$, $\lnot q \lor r$. Conclusion $r$.

1. p ∨ q        premise
2. ¬p ∨ r       premise
3. q ∨ r        resolution, 1, 2
4. ¬q ∨ r       premise
5. r ∨ r        resolution, 3, 4
6. r            idempotent law, 5

Gündelik okuması: “Ya otobüsle ($p$) ya trenle ($q$) gideceğim. Otobüsle gidersem geç kalırım. Trenle gidersem de geç kalırım. O halde geç kalacağım.” Bu kalıba proof by cases da denir; ispat sayfasında tekrar göreceksin.

İPUCU · Önce harfleri yaz. “Let $p$: …, $q$: …” satırı sınavda puanın bir kısmıdır. Sonra numaralı satırlarla ilerle; her satırın sağına “premise” ya da kural adı ve kullandığın satır numaraları.

Sık yapılan hatalar