5 De Morgan Kuralları ve Önerme Sadeleştirme
Bir bileşik önermenin değilini almak, matematikte en sık ihtiyaç duyulan işlemlerden biridir: bir iddiayı çürütmek, olmayana ergi ile ispat yapmak veya bir tanımın “sağlanmadığı” durumu yazmak hep bu işleme dayanır.
Bu bölümde bileşik önermelerin nasıl değilleneceğini veren De Morgan kurallarını kuruyor ve ardından bu kuralları önerme sadeleştirmede kullanıyoruz.
5.1 De Morgan Kuralları
Teorem 5.1 (De Morgan Kuralları) \(p\) ve \(q\) herhangi iki önerme olmak üzere aşağıdaki özellikler gerçeklenir:
\[\textbf{i)} \;\; (p \wedge q)' \equiv p' \vee q' \qquad\qquad \textbf{ii)} \;\; (p \vee q)' \equiv p' \wedge q'\]
İspat
Her iki kuralı da doğruluk tablosu kurarak gösterelim.
i)
| \(p\) | \(q\) | \(p'\) | \(q'\) | \(p \wedge q\) | \((p \wedge q)'\) | \(p' \vee q'\) |
|---|---|---|---|---|---|---|
| \(1\) | \(1\) | \(0\) | \(0\) | \(1\) | \(0\) | \(0\) |
| \(1\) | \(0\) | \(0\) | \(1\) | \(0\) | \(1\) | \(1\) |
| \(0\) | \(1\) | \(1\) | \(0\) | \(0\) | \(1\) | \(1\) |
| \(0\) | \(0\) | \(1\) | \(1\) | \(0\) | \(1\) | \(1\) |
Son iki sütun bütün satırlarda çakıştığından \((p \wedge q)' \equiv p' \vee q'\)’dür.
ii)
| \(p\) | \(q\) | \(p'\) | \(q'\) | \(p \vee q\) | \((p \vee q)'\) | \(p' \wedge q'\) |
|---|---|---|---|---|---|---|
| \(1\) | \(1\) | \(0\) | \(0\) | \(1\) | \(0\) | \(0\) |
| \(1\) | \(0\) | \(0\) | \(1\) | \(1\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) | \(0\) | \(1\) | \(0\) | \(0\) |
| \(0\) | \(0\) | \(1\) | \(1\) | \(0\) | \(1\) | \(1\) |
Son iki sütun yine çakışmaktadır; o hâlde \((p \vee q)' \equiv p' \wedge q'\)’dür.
\(\blacksquare\)
De Morgan kuralları tek cümlede özetlenir: değil içeri girerken bağlaç yer değiştirir.
- “\(p\) ve \(q\)” doğru değilse, en az biri yanlıştır \(\to\) \(p'\) veya \(q'\).
- “\(p\) veya \(q\)” doğru değilse, ikisi de yanlıştır \(\to\) \(p'\) ve \(q'\).
Örnek 5.1 (Doğrudan Uygulama) \((a \vee b')'\) bileşik önermesini sadeleştiriniz.
Çözüm
\[(a \vee b')' \equiv a' \wedge (b')' \equiv a' \wedge b\]
\(\blacksquare\)
Örnek 5.2 (Sıfırdan Farklı Karmaşık Sayı) \(x\) ve \(y\) gerçel sayıları, \(i\) de karesi \(-1\) olan sanal sayıyı gösterdiğine göre, \(x + iy\) karmaşık sayısının sıfırdan farklı olmasını önermelerle açıklayınız.
Çözüm
\(x + iy = 0\) olması, hem gerçel hem sanal kısmın sıfır olması demektir. O hâlde:
\[ \begin{aligned} (x + iy \neq 0) &\equiv (x + iy = 0)' \\[2pt] &\equiv \big[(x = 0) \wedge (y = 0)\big]' \\[2pt] &\equiv (x \neq 0) \vee (y \neq 0) && \text{(De Morgan)} \end{aligned} \]
Yani bir karmaşık sayının sıfırdan farklı olması için gerçel kısmının veya sanal kısmının sıfırdan farklı olması yeterlidir.
\(\blacksquare\)
Örnek 5.3 (Bir Kuraldan Diğerini Elde Etmek) Her \(a, b\) önermesi için \((a \wedge b)' \equiv a' \vee b'\) olduğu bilindiğine göre, \((a \vee b)' \equiv a' \wedge b'\) olduğunu gösteriniz.
Çözüm
Verilen \((a \wedge b)' \equiv a' \vee b'\) denkliği her önerme çifti için geçerlidir. O hâlde \(a\) yerine \(a'\), \(b\) yerine \(b'\) yazabiliriz:
\[(a' \wedge b')' \equiv (a')' \vee (b')' \equiv a \vee b\]
Şimdi her iki tarafın değilini alalım:
\[\Big(\big(a' \wedge b'\big)'\Big)' \equiv (a \vee b)'\]
Soldaki ifadede değilin değili kendisine denk olduğundan
\[a' \wedge b' \equiv (a \vee b)'\]
bulunur.
\(\blacksquare\)
Yukarıdaki örnek, De Morgan kurallarından yalnızca birini ispatlamanın yeterli olduğunu gösterir: harfleri değilleriyle değiştirip sonucun değilini almak diğer kuralı verir.
Bu “değişkenleri değilleriyle değiştirme” tekniği önermeler cebirinde sık kullanılır ve ikilik (dualite) ilkesi olarak adlandırılır.
5.2 Bileşik Önermelerin Değillenmesi
Örnek 5.4 (Değilini Yazma) Aşağıdaki bileşik önermelerin denk olduğu önermeleri bulunuz.
a) \(\big[\text{"}11 \text{ sayısı asaldır"} \;\vee\; (e < \pi)\big]'\) b) \(\big[(p \wedge q)' \vee r\big]'\)
Çözüm
a) “Veya”nın değili, bileşenlerin değillerinin “ve”sidir:
\[\big[\text{"}11 \text{ asaldır"} \vee (e < \pi)\big]' \equiv \big[\text{"}11 \text{ asal değildir"} \wedge (e \geq \pi)\big]\]
b)
\[ \begin{aligned} \big[(p \wedge q)' \vee r\big]' &\equiv \big((p \wedge q)'\big)' \wedge r' && \text{(De Morgan)} \\[2pt] &\equiv (p \wedge q) \wedge r' \\[2pt] &\equiv p \wedge q \wedge r' && \text{(birleşme)} \end{aligned} \]
\(\blacksquare\)
Örnek 5.5 (Çarpımı Sıfırdan Farklı Yapan Koşul) \(m\) ve \(n\) gerçel sayıları göstermek üzere, \((m-1)(n+2) \neq 0\) önermesinin denki olan önermeyi bulunuz.
Çözüm
Bir çarpımın sıfır olması, çarpanlardan en az birinin sıfır olması demektir:
\[ \begin{aligned} \big[(m-1)(n+2) \neq 0\big] &\equiv \big[(m-1)(n+2) = 0\big]' \\[2pt] &\equiv \big[(m-1 = 0) \vee (n+2 = 0)\big]' \\[2pt] &\equiv (m-1 \neq 0) \wedge (n+2 \neq 0) && \text{(De Morgan)} \\[2pt] &\equiv (m \neq 1) \wedge (n \neq -2) \end{aligned} \]
Yani çarpımın sıfırdan farklı olması için her iki çarpanın da sıfırdan farklı olması gerekir.
\(\blacksquare\)
Yukarıdaki örnekte en sık yapılan hata, sonucu \((m \neq 1) \vee (n \neq -2)\) olarak yazmaktır. Çarpanların bulunduğu ifade “veya” ile bağlıydı; değili alınınca bağlaç “ve”ye dönmek zorundadır.
Kontrol yöntemi basittir: \(m = 1\), \(n = 5\) alın. Çarpım \(0 \cdot 7 = 0\)’dır, yani \((m-1)(n+2) \neq 0\) önermesi yanlıştır. “Veya”lı yazım ise \(n \neq -2\) sağlandığı için doğru değeri verirdi.
5.3 Sadeleştirme Uygulamaları
Örnek 5.6 (En Sade Hâle Getirme) \[\Big[\big((p \vee q) \wedge r\big)' \vee q'\Big]'\]
bileşik önermesini, doğruluk tablosu kullanmadan en sade hâle getiriniz.
Çözüm
\[ \begin{aligned} \Big[\big((p \vee q) \wedge r\big)' \vee q'\Big]' &\equiv \Big(\big((p \vee q) \wedge r\big)'\Big)' \wedge (q')' && \text{(De Morgan)} \\[2pt] &\equiv \big((p \vee q) \wedge r\big) \wedge q \\[2pt] &\equiv (p \vee q) \wedge r \wedge q && \text{(birleşme)} \\[2pt] &\equiv \big((p \vee q) \wedge q\big) \wedge r && \text{(birleşme ve değişme)} \\[2pt] &\equiv \big(q \wedge (p \vee q)\big) \wedge r && \text{(değişme)} \\[2pt] &\equiv \big(q \wedge (q \vee p)\big) \wedge r && \text{(değişme)} \\[2pt] &\equiv q \wedge r && \text{(yutma)} \end{aligned} \]
\(\blacksquare\)
Örnek 5.7 (Totoloji mi?) \(a \vee (b' \wedge a)'\) bileşik önermesinin totoloji olup olmadığını araştırınız. Sonucunuzu doğruluk tablosuyla da sağlayınız.
Çözüm
Cebirsel yol.
\[ \begin{aligned} a \vee (b' \wedge a)' &\equiv a \vee \big((b')' \vee a'\big) && \text{(De Morgan)} \\[2pt] &\equiv a \vee (b \vee a') \\[2pt] &\equiv b \vee (a \vee a') && \text{(birleşme ve değişme)} \\[2pt] &\equiv b \vee t \\[2pt] &\equiv t \end{aligned} \]
Verilen önerme bir totolojidir.
Doğruluk tablosuyla sağlama.
| \(a\) | \(b\) | \(b'\) | \(b' \wedge a\) | \((b' \wedge a)'\) | \(a \vee (b' \wedge a)'\) |
|---|---|---|---|---|---|
| \(1\) | \(1\) | \(0\) | \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) | \(1\) | \(0\) | \(1\) |
| \(0\) | \(1\) | \(0\) | \(0\) | \(1\) | \(1\) |
| \(0\) | \(0\) | \(1\) | \(0\) | \(1\) | \(1\) |
Son sütun bütün satırlarda \(1\) olduğundan sonuç doğrulanmıştır.
\(\blacksquare\)
Örnek 5.8 (De Morgan ile Totoloji İspatı) \((p \vee q) \vee (p \wedge q)'\) bileşik önermesinin bir totoloji olduğunu, doğruluk tablosu kurmadan ispat ediniz.
Çözüm
\[ \begin{aligned} (p \vee q) \vee (p \wedge q)' &\equiv (p \vee q) \vee (p' \vee q') && \text{(De Morgan)} \\[2pt] &\equiv p \vee \big(q \vee p'\big) \vee q' && \text{(birleşme)} \\[2pt] &\equiv p \vee \big(p' \vee q\big) \vee q' && \text{(değişme)} \\[2pt] &\equiv (p \vee p') \vee (q \vee q') && \text{(birleşme)} \\[2pt] &\equiv t \vee t \equiv t \end{aligned} \]
\(\blacksquare\)
Örnek 5.9 (Bir Önerme ile Değilinin Ayrımı) \(p, q, r\) ilkel önermeleri verilsin. Tablo kullanmadan
\[\big[p \vee (q \wedge r)\big] \vee \big[p \vee (q \wedge r)\big]'\]
önermesinin totoloji olduğunu gösteriniz.
Çözüm
Kısaltma olarak \(A \equiv p \vee (q \wedge r)\) diyelim. İfade \(A \vee A'\) biçimindedir ve Teorem 4.1 gereği bu bir totolojidir.
Aynı sonucu açık biçimde de görebiliriz:
\[ \begin{aligned} \big[p \vee (q \wedge r)\big] \vee \big[p \vee (q \wedge r)\big]' &\equiv \big[p \vee (q \wedge r)\big] \vee \big[p' \wedge (q \wedge r)'\big] && \text{(De Morgan)} \\[2pt] &\equiv \Big(\big[p \vee (q \wedge r)\big] \vee p'\Big) \wedge \Big(\big[p \vee (q \wedge r)\big] \vee (q \wedge r)'\Big) && \text{($\vee$'nin $\wedge$ üzerine dağılması)} \\[2pt] &\equiv \Big((p \vee p') \vee (q \wedge r)\Big) \wedge \Big(p \vee \big[(q \wedge r) \vee (q \wedge r)'\big]\Big) && \text{(birleşme ve değişme)} \\[2pt] &\equiv \big(t \vee (q \wedge r)\big) \wedge (p \vee t) \\[2pt] &\equiv t \wedge t \equiv t \end{aligned} \]
\(\blacksquare\)
Karmaşık bir önermeyi sadeleştirirken şu sıra hemen her zaman işe yarar:
- Değilleri içeri sok. De Morgan ile en dıştaki değilleri harflere kadar taşıyın; \((p')' \equiv p\) ile ikili değilleri temizleyin.
- Aynı harfleri yan yana getir. Birleşme ve değişme özellikleriyle \(p\) ile \(p'\)’yi, \(q\) ile \(q'\)’yü komşu yapın.
- Değişmezleri oluştur. \(p \vee p' \equiv t\) ve \(p \wedge p' \equiv c\) ile sabitleri açığa çıkarın.
- Sabitleri yut. \(t \vee A \equiv t\), \(c \wedge A \equiv c\), \(t \wedge A \equiv A\), \(c \vee A \equiv A\) kurallarıyla ifadeyi kısaltın.
- Yutma kuralını ara. \(p \wedge (p \vee q)\) veya \(p \vee (p \wedge q)\) kalıbı görürseniz doğrudan \(p\) yazın.
Buraya kadar üç işlemle çalıştık. Bir sonraki bölümde matematiksel teoremlerin neredeyse tamamının yazıldığı biçimi, yani “ise” işlemini tanımlıyoruz.