20 Uygulamalı Özet
Bu sayfa kitabın kurallarını ispatsız, soru çözmeye dönük bir kopya kâğıdı olarak toplar. Uygulamada en sık karşılaşılan sorular şunlardır: bir bileşik önermeyi sadeleştirip totoloji olup olmadığına karar vermek, bir önermenin değilini ya da karşıt tersini yazmak, niceleyici içeren bir önermenin doğruluk değerini bulmak, \(p \Rightarrow q\) biçimindeki bir iddiayı uygun yöntemle ispatlamak ve bir küme özdeşliğini ispatlamak ya da aksine örnekle çürütmek. Sayfa her soru tipi için adım adım bir yol, gerekli kural tablolarını, kısa yolları, sık yapılan hataları ve kısa ama tam çözümlü örnekleri verir. Her kural, gerekçesinin bulunduğu tanıma ya da teoreme bağlanır.
20.1 Soru Tipine Göre Yöntem
Bir soruyu okuyunca ilk iş, sorunun hangi kalıba girdiğini ve hangi aracın en kısa yol olduğunu belirlemektir. Aşağıdaki tablo soru kalıplarını yöntemlerle eşleştirir.
| Soruda istenen | Yöntem | Bu sayfada |
|---|---|---|
| Bileşik önermenin doğruluk değeri ya da doğruluk tablosu | Bağlaç tablosu, içten dışa doldurma | Bölüm 20.2 |
| Önermenin doğru ya da yanlış olduğu verilmiş; bileşenlerin değerleri | Tek \(0\) ya da tek \(1\) satırından geriye çözme | Bölüm 20.2 |
| Tablosu verilen bir önerme yazmak | Tek sıfırlı satır \(\to\) “veya”, tek birli satır \(\to\) “ve” | Bölüm 20.2 |
| Sadeleştirme; totoloji mi, çelişki mi, hiçbiri mi | İse açılımı, De Morgan, \(t\) ve \(c\) kuralları | Bölüm 20.3 |
| Değili, tersi, karşıtı, karşıt tersi | Koşullu önerme tablosu | Bölüm 20.4 |
| \(P\), \(K\)’yı gerektirir mi; iki önerme denk mi | \(P' \vee K \equiv t\) mi; karşı satır | Bölüm 20.5 |
| Niceleyicili önermenin doğruluğu ve değili | Örnek ya da karşı örnek; \(\forall \leftrightarrow \exists\) | Bölüm 20.6 |
| \(p \Rightarrow q\) biçimindeki bir teoremin ispatı | İspat yöntemi seçimi tablosu | Bölüm 20.7 |
| Küme ifadesi, özdeşlik ispatı ya da çürütülmesi | \(A \setminus B = A \cap B^{c}\), cebir, çift kapsama | Bölüm 20.8 |
| Sonlu kümelerde eleman sayısı | İçerme–dışarma | Bölüm 20.9 |
| \(\in\) mi, \(\subseteq\) mi; kuvvet kümesi | Öğe listesi, \(2^n\) | Bölüm 20.10 |
| Kartezyen çarpım | Sıralı ikili, dağılma | Bölüm 20.11 |
| Bağıntı, ters bağıntı, yansıma, simetri | \(I_A \subseteq \beta\), \(\beta = \beta^{-1}\) | Bölüm 20.12 |
20.2 Doğruluk Tabloları ve Doğruluk Değeri
Bütün hesapların temeli beş bağlacın doğruluk tablosudur; bunlar ezbere bilinmelidir (Tanım 3.1, Tanım 6.1, Tanım 7.2).
| \(p\) | \(q\) | \(p'\) | \(p \wedge q\) | \(p \vee q\) | \(p \Rightarrow q\) | \(p \Leftrightarrow q\) |
|---|---|---|---|---|---|---|
| \(1\) | \(1\) | \(0\) | \(1\) | \(1\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(0\) | \(0\) | \(1\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) | \(0\) | \(1\) | \(1\) | \(0\) |
| \(0\) | \(0\) | \(1\) | \(0\) | \(0\) | \(1\) | \(1\) |
Tabloyu tek satırda hatırlamak: “ve” için tek bir \(0\), “veya” için tek bir \(1\) sonucu belirler; \(p \Rightarrow q\) yalnız \(1 \Rightarrow 0\) durumunda yanlıştır; \(p \Leftrightarrow q\) iki taraf aynı değerdeyse doğrudur.
- Satır sayısı. \(n\) farklı önerme için \(2^n\) satır vardır (Teorem 2.1). İlk sütuna \(2^{n-1}\) tane \(1\) ve ardından \(2^{n-1}\) tane \(0\) yaz; her sonraki sütunda blok boyunu yarıya indir. Son sütun \(1, 0, 1, 0, \dots\) diye gider.
- Ara sütunlar. Önce değilleri, sonra en içteki paranteze karşılık gelen sütunu aç; dışa doğru ilerle.
- Doldur. Her sütunu yukarıdaki bağlaç tablosuna göre satır satır doldur.
- Oku. Son sütun hep \(1\) ise totoloji, hep \(0\) ise çelişkidir (Tanım 4.1, Tanım 4.2). İki önermenin son sütunları her satırda aynıysa denktirler (Tanım 2.6); denk olmadıklarını göstermek için tek bir farklı satır yeter.
Kısa yollar.
- Değeri tek türlü belirleyen üç durum vardır: yanlış bir \(p \Rightarrow q\) için \(p \equiv 1\), \(q \equiv 0\); doğru bir “ve” için bütün bileşenler \(1\); yanlış bir “veya” için bütün bileşenler \(0\). Bileşen bulma sorularında bu satırlardan başla.
- Tablodan önerme. Sonuç sütununda yalnız bir \(0\) varsa, o satırda \(0\) olan harfleri (o satırda \(1\) olan harfin yerine değilini) “veya” ile bağla. Yalnız bir \(1\) varsa, o satırı \(1\) yapan harfleri “ve” ile bağla. Örneğin yalnız \(p = 1\), \(q = 0\) satırında \(1\) olan önerme \(p \wedge q'\)’dür.
- “İki taraf farklıysa \(1\)” davranışını \((p \vee q) \wedge (p' \vee q')\) verir (Örnek 3.6).
Örnek 20.1 (Bileşenlerin Değerlerini Bulma) \((p \wedge q) \Rightarrow r'\) önermesi yanlış ve \(r \Leftrightarrow s'\) önermesi doğru olduğuna göre \(p, q, r, s\) önermelerinin doğruluk değerlerini bulunuz.
Çözüm
Bir koşullu önerme yalnız öncül doğru, sonuç yanlış iken yanlıştır: \[p \wedge q \equiv 1, \qquad r' \equiv 0.\] Doğru bir “ve” önermesinin bütün bileşenleri doğrudur, dolayısıyla \(p \equiv q \equiv 1\); ayrıca \(r' \equiv 0\) olduğundan \(r \equiv 1\)’dir.
\(r \Leftrightarrow s'\) doğru olduğundan iki taraf aynı değerdedir: \(s' \equiv r \equiv 1\), yani \(s \equiv 0\).
Sonuç: \(p \equiv q \equiv r \equiv 1\) ve \(s \equiv 0\).
\(\blacksquare\)
Örnek 20.2 (Üç Önermeli Tablodan Önerme Yazma) \(p, q, r\) önermelerinin sekiz satırlık doğruluk tablosunda sonuç sütunu yalnız ikinci satırda (\(p = 1\), \(q = 1\), \(r = 0\)) \(0\), diğer yedi satırda \(1\) olan bir önermeyi \(\wedge\), \(\vee\) ve \('\) kullanarak yazınız.
Çözüm
Sonuç yalnız \(p = 1\), \(q = 1\), \(r = 0\) satırında \(0\)’dır. Bir “veya” önermesi ancak bütün bileşenleri \(0\) olduğunda \(0\) olur. Bu satırda \(0\) olan harfler \(p'\), \(q'\) ve \(r\)’dir: \[? \equiv p' \vee q' \vee r.\]
Sağlama. \(p' \vee q' \vee r\) ifadesi yalnız \(p' \equiv q' \equiv r \equiv 0\), yani \(p \equiv q \equiv 1\), \(r \equiv 0\) iken \(0\)’dır; diğer yedi satırda \(1\)’dir. Ayrıca De Morgan ve ise açılımıyla \[p' \vee q' \vee r \equiv (p \wedge q)' \vee r \equiv (p \wedge q) \Rightarrow r\] olduğu da görülür.
\(\blacksquare\)
20.3 Sadeleştirme: Totoloji, Çelişki ya da Hiçbiri
Uzun bir önerme doğruluk tablosu kurmadan, aşağıdaki kurallarla sadeleştirilir. Kuralların “ve” ve “veya” biçimleri birbirinin aynası olduğundan biri öğrenilince diğeri de öğrenilmiş olur.
| Kural | “Ve” biçimi | “Veya” biçimi | Kitapta |
|---|---|---|---|
| Eş güçlülük | \(p \wedge p \equiv p\) | \(p \vee p \equiv p\) | Teorem 3.1, Teorem 3.2 |
| Değişme | \(p \wedge q \equiv q \wedge p\) | \(p \vee q \equiv q \vee p\) | Teorem 3.1, Teorem 3.2 |
| Dağılma | \(p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)\) | \(p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)\) | Teorem 3.3 |
| De Morgan | \((p \wedge q)' \equiv p' \vee q'\) | \((p \vee q)' \equiv p' \wedge q'\) | Teorem 5.1 |
| Önerme ve değili | \(p \wedge p' \equiv c\) | \(p \vee p' \equiv t\) | Teorem 4.1 |
| Etkisiz eleman | \(p \wedge t \equiv p\) | \(p \vee c \equiv p\) | Teorem 4.2 |
| Yutan eleman | \(p \wedge c \equiv c\) | \(p \vee t \equiv t\) | Teorem 4.2 |
| Yutma | \(p \wedge (p \vee q) \equiv p\) | \(p \vee (p \wedge q) \equiv p\) | Teorem 3.5 |
| Değilin değili | \((p')' \equiv p\) | Teorem 3.4 | |
| İse açılımı | \(p \Rightarrow q \equiv p' \vee q\) | Teorem 6.1 | |
| Çift gerektirme | \(p \Leftrightarrow q \equiv (p' \vee q) \wedge (q' \vee p)\) | Tanım 7.2 |
- Okları aç. Her \(\Rightarrow\) ve \(\Leftrightarrow\)’yu yukarıdaki son iki satırla \(\wedge\), \(\vee\), \('\) diline çevir.
- Değilleri içeri sok. De Morgan ile değilleri harflere kadar taşı, \((p')' \equiv p\) ile çift değilleri sil.
- Aynı harfleri yan yana getir. Değişme ve birleşme ile \(p\) ile \(p'\)’yü komşu yap.
- Sabitleri üret ve yut. \(p \vee p' \equiv t\), \(p \wedge p' \equiv c\) yaz; sonra \(t\) ve \(c\)’yi etkisiz ya da yutan eleman olarak kullan.
- Yutma kalıbını ara. \(p \wedge (p \vee q)\) ya da \(p \vee (p \wedge q)\) görürsen doğrudan \(p\) yaz.
Sonuç \(t\) ise önerme totoloji, \(c\) ise çelişkidir; harf kalırsa ikisi de değildir ve bunu göstermek için ifadeyi \(0\) (ya da \(1\)) yapan tek bir satır vermek yeter. Örneğin \((p \Rightarrow q) \Rightarrow p \equiv (p \wedge q') \vee p \equiv p\) olur (yutma); bu önerme \(p \equiv 0\) satırında \(0\) olduğundan totoloji değildir.
Kısa yollar.
- \(X \vee (X' \wedge Y) \equiv X \vee Y\) ve \(X \wedge (X' \vee Y) \equiv X \wedge Y\). İkisi de dağılma ve \(X \vee X' \equiv t\) (ya da \(X \wedge X' \equiv c\)) ile iki adımda çıkar (Örnek 7.6).
- Hızlı totoloji sınaması. İfadeyi \(0\) yapmaya çalış: koşullu önermede öncüle \(1\), sonuca \(0\) ata ve harflerin değerlerini zorla. Bir harf hem \(1\) hem \(0\) çıkıyorsa ifade hiçbir satırda \(0\) olamaz, yani totolojidir; tutarlı bir atama bulunursa o atama karşı satırdır.
- Tekrar eden uzun bir parantezi \(A\) ile kısalt: \(A \vee A'\) biçimi görünüyorsa sonuç hemen \(t\)’dir (Örnek 5.9).
- \(p \wedge (q \vee r) \not\equiv (p \wedge q) \vee r\); dağıtırken \(p\) her iki terime de gider.
- De Morgan’da bağlacı çevirmeyi unutmak: \((p \wedge q)'\), \(p' \wedge q'\) değil \(p' \vee q'\)’dür.
- \((p \Rightarrow q)'\) ifadesini \(p' \Rightarrow q'\) yazmak; doğrusu \(p \wedge q'\)’dür.
- \(x < 3\)’ün değilini \(x > 3\) yazmak; doğrusu \(x \geq 3\)’tür.
Örnek 20.3 (İki Koşulun Ortak Sonucu) \((p \Rightarrow q) \wedge (p \vee q)\) önermesini en sade hâlde yazınız.
Çözüm
\[ \begin{aligned} (p \Rightarrow q) \wedge (p \vee q) &\equiv (p' \vee q) \wedge (p \vee q) && \text{(ise açılımı)} \\[1mm] &\equiv (q \vee p') \wedge (q \vee p) && \text{(değişme)} \\[1mm] &\equiv q \vee (p' \wedge p) && \text{(dağılma, ters yönde)} \\[1mm] &\equiv q \vee c \equiv q \end{aligned} \] Önerme \(q\)’ya denktir; ne totoloji ne çelişkidir.
\(\blacksquare\)
Örnek 20.4 (Kesişimden Birleşime Gerektirme) \((p \wedge q) \Rightarrow (p \vee r)\) önermesinin bir totoloji olduğunu gösteriniz.
Çözüm
\[ \begin{aligned} (p \wedge q) \Rightarrow (p \vee r) &\equiv (p \wedge q)' \vee (p \vee r) && \text{(ise açılımı)} \\[1mm] &\equiv p' \vee q' \vee p \vee r && \text{(De Morgan)} \\[1mm] &\equiv (p \vee p') \vee q' \vee r && \text{(değişme, birleşme)} \\[1mm] &\equiv t \vee q' \vee r \equiv t \end{aligned} \]
Hızlı sınama. İfadenin \(0\) olması için \(p \wedge q \equiv 1\) ve \(p \vee r \equiv 0\) gerekirdi. Birincisi \(p \equiv 1\), ikincisi \(p \equiv 0\) ister; bu olanaksız olduğundan ifade hiçbir satırda \(0\) olmaz.
\(\blacksquare\)
20.4 Koşullu Önerme: Değil, Ters, Karşıt, Karşıt Ters
Bir \(p \Rightarrow q\) önermesinde \(p\) öncül (yeter şart), \(q\) sonuçtur (gerek şart). Bir koşullu önermeden türetilen dört önerme ve bunların asıl önermeyle ilişkisi aşağıdadır (Tanım 6.2).
| Ad | Biçim | \(p \Rightarrow q\)’ya denk mi? | Kitapta |
|---|---|---|---|
| Tersi | \(p' \Rightarrow q'\) | Hayır | Tanım 6.2 |
| Karşıtı | \(q \Rightarrow p\) | Hayır | Tanım 6.2 |
| Karşıt tersi | \(q' \Rightarrow p'\) | Evet | Teorem 6.3 |
| Değili | \(p \wedge q'\) | Her satırda zıt değerli | Teorem 6.2 |
Kısa yollar.
- Tersi ile karşıtı birbirinin karşıt tersidir, dolayısıyla birbirine denktir: \(p' \Rightarrow q' \equiv q \Rightarrow p\). Biri doğruysa öteki de doğrudur.
- Uzun bir koşullunun değilinde öncül ve sonucu birer harf gibi düşün: \((A \Rightarrow B)' \equiv A \wedge B'\), sonra yalnız \(B'\)’yi De Morgan ile aç. Örneğin \[\big[(p \vee q) \Rightarrow (r \wedge s')\big]' \equiv (p \vee q) \wedge (r' \vee s).\]
Uzun koşullu önermelerde işe yarayan denklikler:
| Önerme | Denki | Kitapta |
|---|---|---|
| \(a \Rightarrow (b \wedge c)\) | \((a \Rightarrow b) \wedge (a \Rightarrow c)\) | Teorem 6.4 |
| \((b \vee c) \Rightarrow a\) | \((b \Rightarrow a) \wedge (c \Rightarrow a)\) | Örnek 6.2 |
| \(a \Rightarrow (b \vee c)\) | \((a \wedge b') \Rightarrow c\) | Örnek 6.3 |
| \(p \Rightarrow (q \Rightarrow r)\) | \((p \wedge q) \Rightarrow r\) | Teorem 6.1 ile iki satırda |
| \((p \Leftrightarrow q)'\) | \(p' \Leftrightarrow q\) | Örnek 7.4 |
- Öncüldeki “ve” dağılmaz: \((b \wedge c) \Rightarrow a\), \((b \Rightarrow a) \wedge (c \Rightarrow a)\)’ya denk değildir.
- Karşıtın ya da tersin doğru olduğunu göstermek asıl önermeyi ispatlamaz; yalnız karşıt ters ispatlar.
- Öncülü yanlış olan koşullu önerme doğrudur; “anlamsız” sayılıp atlanmaz.
Örnek 20.5 (Altı ile Bölünen Sayılar) “Bir tam sayı \(6\) ile bölünüyorsa \(3\) ile bölünür.” önermesinin tersi, karşıtı ve karşıt tersinden hangileri doğrudur?
Çözüm
\(p\): “\(n\), \(6\) ile bölünür”, \(q\): “\(n\), \(3\) ile bölünür” olsun. \(6 \mid n\) ise \(n = 6k = 3(2k)\) olduğundan asıl önerme doğrudur.
- Karşıt tersi \(q' \Rightarrow p'\): “\(3\) ile bölünmeyen bir tam sayı \(6\) ile bölünmez.” Asıl önermeye denk olduğundan doğrudur.
- Karşıtı \(q \Rightarrow p\): “\(3\) ile bölünen bir tam sayı \(6\) ile bölünür.” \(n = 3\) için öncül doğru, sonuç yanlıştır; yanlıştır.
- Tersi \(p' \Rightarrow q'\): “\(6\) ile bölünmeyen bir tam sayı \(3\) ile bölünmez.” Karşıta denk olduğundan o da yanlıştır; yine \(n = 3\) aksine örnektir.
Yalnız karşıt ters doğrudur.
\(\blacksquare\)
20.5 Gerektirme, Denklik ve Çıkarım Kuralları
“\(P\), \(K\)’yı mantıksal olarak gerektirir” demek \(P \Rightarrow K\) önermesinin totoloji olması demektir (Tanım 7.1); “\(P\) ile \(K\) denktir” demek ise \(P \Leftrightarrow K\)’nın totoloji olmasıdır (Tanım 7.3).
- Kur. \(P \Rightarrow K \equiv P' \vee K\) yaz.
- Sadeleştir. Bölüm 20.3 adımlarıyla \(P' \vee K\)’yı indir. Öncül uzunsa önce \(P\)’yi ayrıca sadeleştirmek işi kısaltır.
- Karar ver. \(t\) çıkarsa gerektirir. Harf kalırsa gerektirmez; \(P \equiv 1\), \(K \equiv 0\) yapan bir satırı sağlama olarak yaz.
Denklik sorularında iki taraf ayrı ayrı aynı sade biçime indirilir. Örneğin \(p \Rightarrow (q \Rightarrow r)\) ve \((p \wedge q) \Rightarrow r\) önermelerinin ikisi de \(p' \vee q' \vee r\)’ye indiğinden denktir. Denk olmadıklarını göstermek için iki tarafa farklı değer veren tek bir satır yeter.
| Kural | Öncüller | Sonuç | Geçerli mi? |
|---|---|---|---|
| Ayırma (modus ponens) | \(p \Rightarrow q\), \(p\) | \(q\) | Evet (Teorem 7.1) |
| Karşıt ters (modus tollens) | \(p \Rightarrow q\), \(q'\) | \(p'\) | Evet (Teorem 7.2) |
| Zincirleme | \(a \Rightarrow b\), \(b \Rightarrow c\) | \(a \Rightarrow c\) | Evet (Teorem 7.3) |
| Ayırıcı tasım | \(p \vee q\), \(p'\) | \(q\) | Evet (Teorem 7.4) |
| Sonuçtan öncüle dönmek | \(p \Rightarrow q\), \(q\) | \(p\) | Hayır: \(p \equiv 0\), \(q \equiv 1\) |
| Öncülün değilinden sonucun değiline | \(p \Rightarrow q\), \(p'\) | \(q'\) | Hayır: \(p \equiv 0\), \(q \equiv 1\) |
Örnek 20.6 (Öncülün Değilinden Çıkarım) \((p \Rightarrow q) \wedge p'\) önermesi \(q'\) önermesini mantıksal olarak gerektirir mi?
Çözüm
Önce öncülü sadeleştirelim. \(X \equiv p'\) dersek \((p' \vee q) \wedge p' \equiv X \wedge (X \vee q) \equiv X\) olur (yutma); yani öncül \(p'\)’ye denktir. Buradan \[ \begin{aligned} \big[(p \Rightarrow q) \wedge p'\big] \Rightarrow q' &\equiv p' \Rightarrow q' \\[1mm] &\equiv (p')' \vee q' \equiv p \vee q'. \end{aligned} \] Sonuç \(p \vee q'\)’dür; totoloji değildir. Dolayısıyla gerektirme yoktur.
Sağlama. \(p \equiv 0\), \(q \equiv 1\) alalım. Öncül \((0 \Rightarrow 1) \wedge 1 \equiv 1\), sonuç \(q' \equiv 0\) olur; öncül doğruyken sonuç yanlıştır.
\(\blacksquare\)
20.6 Niceleyiciler: Doğruluk ve Değilleme
\(\forall\) uzun bir “ve” zinciri, \(\exists\) uzun bir “veya” zinciridir; doğruluk ve değilleme kurallarının hepsi bundan çıkar (Tanım 8.2, Tanım 8.3, Teorem 8.1).
| Önerme | Doğru olduğunu göstermek | Yanlış olduğunu göstermek | Değili |
|---|---|---|---|
| \(\forall x, \; p(x)\) | Bütün \(x\)’leri kapsayan bir akıl yürütme | Tek bir karşı örnek | \(\exists x, \; p'(x)\) |
| \(\exists x, \; p(x)\) | Tek bir örnek | Her \(x\) için \(p'(x)\) olduğunu göstermek | \(\forall x, \; p'(x)\) |
| Önerme | Değili |
|---|---|
| \(\forall x, \; p(x) \Rightarrow q(x)\) | \(\exists x, \; p(x) \wedge q'(x)\) |
| \(\exists x, \; p(x) \wedge q(x)\) | \(\forall x, \; p'(x) \vee q'(x)\) |
| \(\exists x, \; p(x) \vee q(x)\) | \(\forall x, \; p'(x) \wedge q'(x)\) |
| \(x < a\) | \(x \geq a\) |
| \((x = 0) \wedge (y = 0)\) | \((x \neq 0) \vee (y \neq 0)\) |
| \(ab = 0\), yani \((a = 0) \vee (b = 0)\) | \((a \neq 0) \wedge (b \neq 0)\) |
Kısa yol. Uzun bir nicelenmiş önermenin değilini soldan sağa yürüyerek yaz: her \(\forall\)’i \(\exists\), her \(\exists\)’i \(\forall\) yap; en içe varınca koşulluyu \(p \wedge q'\)’ye çevir, \(\wedge\) ile \(\vee\)’yi takas et ve her bileşeni değille.
- Evrensel önermeyi bir ya da birkaç değer deneyerek “ispatlamak”. Tek değer yalnız çürütmeye yeter.
- \(\forall x, \; \big(s(x) \Rightarrow p(x)\big)\) ile \(\forall x, \; \big(s(x) \wedge p(x)\big)\)’yi karıştırmak; birincisi yalnız \(s\)’yi sağlayanlardan söz eder.
- \(\exists x, \; \big(p(x) \Rightarrow r(x)\big)\) önermesi, öncülü yanlış yapan tek bir \(x\) varsa bile doğrudur.
- Evreni unutmak: \(\forall x, \; x^2 \geq x\) önermesi \(\mathbb{Z}\)’de doğru, \(\mathbb{R}\)’de yanlıştır (\(x = \tfrac12\) için \(\tfrac14 < \tfrac12\)).
Örnek 20.7 (Kökleri Üzerinden Evrensel Koşul) Tam sayılar üzerinde \(p(x) := x^2 - 5x + 6 = 0\) ve \(r(x) := x > 2\) açık önermeleri verilsin. \(\forall x, \; p(x) \Rightarrow r(x)\) önermesinin doğruluk değerini belirleyiniz.
Çözüm
\(x^2 - 5x + 6 = (x - 2)(x - 3)\) olduğundan \(p(x)\) yalnız \(x = 2\) ve \(x = 3\) için doğrudur. Öncülü yanlış olan bütün \(x\)’lerde koşullu önerme doğrudur; bakılması gereken yalnız bu iki değerdir.
- \(x = 3\): \(p(3) \equiv 1\), \(r(3) \equiv 1\); \(1 \Rightarrow 1 \equiv 1\).
- \(x = 2\): \(p(2) \equiv 1\), fakat \(2 > 2\) yanlış olduğundan \(r(2) \equiv 0\); \(1 \Rightarrow 0 \equiv 0\).
\(x = 2\) bir aksine örnektir; önerme yanlıştır. (Buna karşılık \(\exists x, \; p(x) \Rightarrow r(x)\) önermesi \(x = 3\) ile doğrudur.)
\(\blacksquare\)
Örnek 20.8 (Kareyle Kıyaslamanın Değili) \(\forall x \in \mathbb{Z}, \; x^2 \geq x\) önermesinin değilini yazınız ve değilin doğruluk değerini belirleyiniz.
Çözüm
Niceleyici çevrilir, \(\geq\)’nin değili \(<\) olur: \[\big[\forall x \in \mathbb{Z}, \; x^2 \geq x\big]' \equiv \exists x \in \mathbb{Z} \ni x^2 < x.\]
\(x^2 < x\) eşitsizliği \(x(x - 1) < 0\) demektir. İki çarpanın çarpımı ancak işaretleri zıtsa negatiftir; bu da \(x > 0\) ve \(x - 1 < 0\), yani \(0 < x < 1\) demektir. Bu aralıkta hiç tam sayı yoktur.
O hâlde değil yanlıştır; dolayısıyla asıl önerme doğrudur.
\(\blacksquare\)
20.7 İspat Yöntemi Seçimi
Bir \(p \Rightarrow q\) iddiasında yöntemi, öncülün ve sonucun biçimi belirler. Çözümün ilk cümlesinde kullanılan yöntem açıkça söylenir.
| İpucu | Yöntem | İlk cümle | Kitapta |
|---|---|---|---|
| Öncül olumlu ve bir denkleme çevrilebiliyor | Doğrudan | “\(n\) çift olsun; \(n = 2k\).” | Tanım 9.1 |
| Öncül ya da sonuç olumsuz (\(\nmid\), “tek değil”, \(\neq\)) | Karşıt ters | “\(q'\) doğru olsun; \(p'\) gösterilecek.” | Tanım 10.1 |
| Sonuç “irrasyoneldir”, “sonsuzdur”, “yoktur” | Çelişki | “\(p\) doğru ve \(q\) yanlış olsun.” | Tanım 11.2 |
| “Her \(n \in \mathbb{Z}\) için”, tek–çift ya da kalan ayrımı | Durum inceleme | “\(n = 3k\), \(3k + 1\) ya da \(3k + 2\)’dir.” | Tanım 12.1 |
| \(\forall\) önermesinin yanlış olduğu düşünülüyor | Aksine örnek | “\(x = \dots\) için \(p\) doğru, \(q\) yanlış.” | Tanım 11.1 |
| “Ancak ve ancak” | İki yön ayrı ayrı | “(\(\Rightarrow\)) … (\(\Leftarrow\)) …” | Tanım 7.2 |
| İki kümenin eşitliği | Çift kapsama | “Keyfi bir \(x \in A\) alalım.” | Teorem 14.2 |
Hesaba başlamak için sözel hipotez önce bir denkleme çevrilir:
| İfade | Denklem (\(k \in \mathbb{Z}\)) | Kitapta |
|---|---|---|
| \(n\) çift / tek | \(n = 2k\) / \(n = 2k + 1\) | Örnek 9.1 |
| \(a \mid b\) | \(b = a k\) | Tanım 9.2 |
| \(a \equiv b \pmod n\) | \(a - b = n k\) | Tanım 9.3 |
| \(x \in \mathbb{Q}\) | \(x = \frac{a}{b}\), \(a, b \in \mathbb{Z}\), \(b \neq 0\) | Örnek 11.4 |
| \(n\)’nin \(3\) ile bölümünden kalan \(r\) | \(n = 3k + r\), \(r \in \{0, 1, 2\}\) | Örnek 12.2 |
Hazır sonuçlar. İspatlarda yeniden kanıtlanmadan kullanılabilenler: \(a^2\) çift ise \(a\) çifttir (Örnek 11.2); \(a \mid b\) ve \(b \mid c\) ise \(a \mid c\) (Örnek 9.6); \(\sqrt{2}\) irrasyoneldir (Örnek 11.3); rasyonel ile irrasyonelin toplamı irrasyoneldir (Örnek 11.4). Eşitsizliklerde çıkış noktası \((ax - by)^2 \geq 0\) biçiminde bir karedir; \(a\) ve \(b\), açılımdaki \(-2ab\,xy\) terimi istenen katsayıyı verecek şekilde seçilir (Örnek 9.5).
- Karşıtı ispatlayıp asıl önermeyi ispatlamış saymak.
- Durum incelemede bir durumu atlamak; durumlar bütün değerleri kapsamalıdır.
- Eşitsizliği işaretini bilmediğin bir ifadeyle çarpmak ya da bölmek.
- Sonuç “ve” ile kuruluysa karşıt terste değilini alırken De Morgan’ı unutmak: \((5 \nmid x \wedge 5 \nmid y)' \equiv 5 \mid x \vee 5 \mid y\).
Örnek 20.9 (Karşıt Ters ile Teklik) \(n\) bir tam sayı olmak üzere, \(n^2 + 4n\) tek ise \(n\)’nin tek olduğunu gösteriniz.
Çözüm
Karşıt ters ile ispat yöntemini kullanalım. İspatlanacak önerme “\(n\) çift ise \(n^2 + 4n\) çifttir” önermesidir.
\(n\) çift olsun; \(n = 2k\) olacak şekilde bir \(k \in \mathbb{Z}\) vardır. Buna göre \[n^2 + 4n = 4k^2 + 8k = 2\underbrace{(2k^2 + 4k)}_{\in\, \mathbb{Z}}\] olur; yani \(n^2 + 4n\) çifttir. Karşıt ters önerme doğru olduğundan asıl önerme de doğrudur.
\(\blacksquare\)
Örnek 20.10 (Üç Durumla Bölünmezlik) Her \(n\) tam sayısı için \(n^2 - 2\) sayısının \(3\) ile bölünmediğini gösteriniz.
Çözüm
Durum incelemeli ispat yöntemini kullanalım. \(n\)’nin \(3\) ile bölümünden kalan \(0\), \(1\) ya da \(2\)’dir; her durumda \(n^2 - 2\)’nin \(3\) ile bölümünden kalanı bulalım. Her durumda \(k \in \mathbb{Z}\)’dir.
1. durum: \(n = 3k\). \[n^2 - 2 = 9k^2 - 2 = 3(3k^2 - 1) + 1.\]
2. durum: \(n = 3k + 1\). \[n^2 - 2 = 9k^2 + 6k - 1 = 3(3k^2 + 2k - 1) + 2.\]
3. durum: \(n = 3k + 2\). \[n^2 - 2 = 9k^2 + 12k + 2 = 3(3k^2 + 4k) + 2.\]
Parantez içleri tam sayıdır ve kalanlar \(1\), \(2\), \(2\) olup hiçbiri \(0\) değildir. Dolayısıyla her \(n \in \mathbb{Z}\) için \(3 \nmid n^2 - 2\)’dir.
\(\blacksquare\)
Örnek 20.11 (Çelişkiyle Bir Eşitsizlik) \(a\) ve \(b\) tam sayılar olmak üzere \(a^2 - 4b \neq 2\) olduğunu gösteriniz.
Çözüm
Çelişki ile ispat yöntemini kullanalım. Kabul edelim ki \(a^2 - 4b = 2\) olacak şekilde \(a, b \in \mathbb{Z}\) bulunsun. Buradan \[a^2 = 4b + 2 = 2(2b + 1)\] olur; \(a^2\) çifttir. Örnek 11.2 gereği \(a\) da çifttir; \(a = 2c\) olacak şekilde bir \(c \in \mathbb{Z}\) vardır. Yerine yazalım: \[4c^2 = 4b + 2 \;\Longrightarrow\; c^2 - b = \frac{1}{2}.\] Sol taraf iki tam sayının farkı olduğundan bir tam sayıdır, sağ taraf ise tam sayı değildir. Bu bir çelişkidir. Çelişkiye kabulümüz yol açtığına göre kabulümüz yanlıştır; her \(a, b \in \mathbb{Z}\) için \(a^2 - 4b \neq 2\)’dir.
\(\blacksquare\)
20.8 Küme İşlemleri ve Özdeşlikler
Küme işlemleri mantık bağlaçlarının birebir karşılığıdır. Bu yüzden küme sorularının hepsi ya doğrudan küme cebiriyle ya da öğe koşulunu önermeye çevirerek çözülür.
| Küme dili | Mantık dili | Kitapta |
|---|---|---|
| \(x \in A \cup B\) | \((x \in A) \vee (x \in B)\) | Tanım 16.1 |
| \(x \in A \cap B\) | \((x \in A) \wedge (x \in B)\) | Tanım 16.2 |
| \(x \in A^{c}\) | \((x \in \mathcal{E}) \wedge (x \notin A)\) | Tanım 17.1 |
| \(x \in A \setminus B\) | \((x \in A) \wedge (x \notin B)\) | Tanım 17.3 |
| \(x \in A \triangle B\) | \(x\), kümelerden tam olarak birinde | Tanım 17.4 |
| \(A \subseteq B\) | \(\forall x, \; x \in A \Rightarrow x \in B\) | Tanım 14.1 |
| \(A = B\) | \(\forall x, \; x \in A \Leftrightarrow x \in B\) | Tanım 14.4 |
| \(\varnothing\), \(\mathcal{E}\) | \(c\), \(t\) | Teorem 16.3 |
| Özdeşlik | Kitapta |
|---|---|
| \(A \setminus B = A \cap B^{c}\) | Teorem 17.4 |
| \((A \cup B)^{c} = A^{c} \cap B^{c}\), \(\;(A \cap B)^{c} = A^{c} \cup B^{c}\) | Teorem 17.1 |
| \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\) | Teorem 16.5 |
| \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\) | Teorem 16.5 |
| \(A \cup A^{c} = \mathcal{E}\), \(\;A \cap A^{c} = \varnothing\), \(\;(A^{c})^{c} = A\) | Teorem 17.2 |
| \(A \cup \varnothing = A\), \(\;A \cup \mathcal{E} = \mathcal{E}\) | Teorem 16.3 |
| \(A \cap \varnothing = \varnothing\), \(\;A \cap \mathcal{E} = A\) | Teorem 16.4 |
| \(B \subseteq A \Leftrightarrow A \cup B = A \Leftrightarrow A \cap B = B\) | Teorem 16.3, Teorem 16.4 |
| \(A \subseteq B \Rightarrow B^{c} \subseteq A^{c}\) | Teorem 17.2 |
| \(A \cap B = \varnothing \Leftrightarrow A \subseteq B^{c}\) | Teorem 17.3 |
| \(A \cup (B \setminus A) = A \cup B\) | Örnek 17.4 |
| \(A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)\) | Örnek 17.4 |
| \(A = (A \setminus B) \cup (A \cap B)\), iki parça ayrık | Örnek 17.5 |
| \((A \triangle B)^{c} = (A \cap B) \cup (A \cup B)^{c}\) | Örnek 17.7 |
- Cebirsel yol. Her farkı \(A \cap B^{c}\), her simetrik farkı \((A \cap B^{c}) \cup (B \cap A^{c})\) biçiminde yaz; De Morgan ve dağılmayla aç; \(A \cap A^{c} = \varnothing\) ve \(A \cup A^{c} = \mathcal{E}\) ile temizle.
- Öğe yolu. \(x \in\) (sol taraf) koşulunu önermeye çevir, önermeler cebiriyle dönüştür ve \(x \in\) (sağ taraf) koşuluna ulaş. Adımlar tek yönlüyse iki kapsamayı ayrı ayrı göster (Teorem 14.2).
- Çürütme. Eşitlik şüpheliyse \(A = \{1, 2\}\), \(B = \{2, 3\}\) gibi küçük kümeler dene; iki tarafı ayıran tek bir öğe aksine örnektir.
Kısa yol: üç kümelik sağlama. \(x \in A\), \(x \in B\), \(x \in C\) koşullarını \(1\) ya da \(0\) alarak sekiz satırlık bir tablo kur; bu, Venn diyagramının sekiz bölgesidir. İki tarafın sütunları her satırda aynıysa eşitlik doğrudur; farklı çıkan bir satır, o bölgeden bir öğe seçilerek doğrudan aksine örneğe dönüşür.
- \(A \setminus B = B \setminus A\) sanmak; fark değişmeli değildir, simetrik fark değişmelidir.
- \((A \cup B) \setminus B = A\) yazmak; doğrusu \(A \setminus B\)’dir (Örnek 20.13).
- Tümleyen alınca kapsamanın yön değiştirdiğini unutmak: \(A \subseteq B\) ise \(A^{c} \subseteq B^{c}\) değil, \(B^{c} \subseteq A^{c}\)’dir.
- \(A \cup (B \cap C)\) ile \((A \cup B) \cap C\)’yi karıştırmak; dağıtılan küme her terime gider.
Örnek 20.12 (Kesişimden Çıkarmak) Her \(A, B, C\) kümesi için \(A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)\) olduğunu gösteriniz.
Çözüm
Farkı kesişim ve tümleyen cinsinden yazalım: \[ \begin{aligned} A \setminus (B \cap C) &= A \cap (B \cap C)^{c} && \text{(fark = kesişim)} \\[1mm] &= A \cap \big(B^{c} \cup C^{c}\big) && \text{(De Morgan)} \\[1mm] &= \big(A \cap B^{c}\big) \cup \big(A \cap C^{c}\big) && \text{(dağılma)} \\[1mm] &= (A \setminus B) \cup (A \setminus C) \end{aligned} \]
\(\blacksquare\)
Örnek 20.13 (Birleştirip Geri Çıkarmak) \((A \cup B) \setminus B = A\) eşitliği her \(A, B\) kümesi için doğru mudur?
Çözüm
Doğru değildir. \(A = \{1, 2\}\) ve \(B = \{2\}\) alalım: \[(A \cup B) \setminus B = \{1, 2\} \setminus \{2\} = \{1\} \neq A.\]
Sol tarafın gerçekte neye eşit olduğu cebirsel yoldan görülür: \[ \begin{aligned} (A \cup B) \setminus B &= (A \cup B) \cap B^{c} \\[1mm] &= \big(A \cap B^{c}\big) \cup \big(B \cap B^{c}\big) \\[1mm] &= \big(A \cap B^{c}\big) \cup \varnothing = A \setminus B \end{aligned} \] Dolayısıyla eşitlik ancak \(A \setminus B = A\) olduğunda, yani \(A\) ile \(B\) ayrık olduğunda sağlanır. Örnekteki \(A\) ile \(B\) ortak \(2\) öğesini içerdiği için eşitlik bozulmuştur.
\(\blacksquare\)
20.9 Eleman Sayısı
Sonlu kümelerde eleman sayısı soruları birkaç formülle çözülür. Aşağıda \(s(A)\), \(A\)’nın eleman sayısıdır; kitapta nicelik sayısı \(\lvert A \rvert\) ile de gösterilir (Tanım 15.3).
| Durum | Formül | Kitapta |
|---|---|---|
| İki küme | \(s(A \cup B) = s(A) + s(B) - s(A \cap B)\) | Örnek 17.9 |
| Üç küme | Tekliler \(+\), ikili kesişimler \(-\), üçlü kesişim \(+\) | Örnek 17.9 |
| Parçalanma | \(s(A) = s(A \cap B) + s(A \setminus B)\) | Örnek 17.5 |
| Tümleyen | \(s(A^{c}) = s(\mathcal{E}) - s(A)\) | Tanım 17.1 |
| Simetrik fark | \(s(A \triangle B) = s(A) + s(B) - 2\,s(A \cap B)\) | Tanım 17.4 |
| Kartezyen çarpım | \(s(A \times B) = s(A) \cdot s(B)\) | Tanım 18.3 |
| Kuvvet kümesi | \(s(A) = n \Rightarrow s\big(P(A)\big) = 2^n\) | Teorem 15.2 |
Kısa yol. “Hiçbirinde olmayan” soruluyorsa önce birleşimi içerme–dışarma ile bul, sonra evrenden çıkar: \[s\big((A \cup B \cup C)^{c}\big) = s(\mathcal{E}) - s(A \cup B \cup C).\] Bölünebilme sorularında \(1, \dots, N\) arasında \(m\)’ye bölünenlerin sayısı \(N\)’nin \(m\)’ye bölümündeki bölümdür; aralarında asal iki sayıya birlikte bölünenler, çarpımlarına bölünenlerdir.
Örnek 20.14 (Hiçbiriyle Bölünmeyen Sayılar) \(1\)’den \(100\)’e kadar olan tam sayılardan kaç tanesi \(2\), \(3\) ve \(5\) sayılarının hiçbiriyle bölünmez?
Çözüm
\(\mathcal{E} = \{1, 2, \dots, 100\}\) ve \(A\), \(B\), \(C\) sırasıyla \(2\)’ye, \(3\)’e ve \(5\)’e bölünenlerin kümeleri olsun. \(2\), \(3\), \(5\) ikişer ikişer aralarında asal olduğundan \(A \cap B\) kümesi \(6\)’ya, \(A \cap C\) kümesi \(10\)’a, \(B \cap C\) kümesi \(15\)’e, \(A \cap B \cap C\) kümesi \(30\)’a bölünenlerden oluşur. Sayarsak:
| Küme | \(A\) | \(B\) | \(C\) | \(A \cap B\) | \(A \cap C\) | \(B \cap C\) | \(A \cap B \cap C\) |
|---|---|---|---|---|---|---|---|
| Eleman sayısı | \(50\) | \(33\) | \(20\) | \(16\) | \(10\) | \(6\) | \(3\) |
İçerme–dışarma ile \[s(A \cup B \cup C) = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74.\] Hiçbiriyle bölünmeyenler birleşimin tümleyenidir: \[s\big((A \cup B \cup C)^{c}\big) = 100 - 74 = 26.\]
\(\blacksquare\)
20.10 Öğe, Alt Küme ve Kuvvet Kümesi
Öğe (\(\in\)) ile alt küme (\(\subseteq\)) sorularındaki hataların neredeyse hepsi, kümenin öğelerini doğru listelememekten gelir. Bu yüzden her soru aynı sırayla çözülür.
- Listele. Kümenin en dış ayraçlarının içindeki öğeleri virgüllerle tek tek ayır ve say. \(\{1, 2\}\) gibi iç ayraçlı bir şey tek öğedir.
- \(x \in B\) sorusu. \(x\)’in kendisini bu listede ara.
- \(X \subseteq B\) sorusu. \(X\)’in her öğesini listede ara. \(X \subset B\) için ayrıca \(B\)’de olup \(X\)’te olmayan bir öğe göster. Gerekirse \(X \subseteq B \Leftrightarrow X \in P(B)\) denkliğini kullan.
| Gerçek | Kitapta |
|---|---|
| Her \(A\) için \(\varnothing \subseteq A\); \(A \neq \varnothing\) ise \(\varnothing \subset A\) | Teorem 15.1 |
| \(\varnothing \in A\) ancak \(\varnothing\), \(A\)’nın listesinde yazılıysa doğrudur | Örnek 15.7 |
| \(\varnothing \neq \{\varnothing\}\); \(\lvert \varnothing \rvert = 0\), \(\lvert \{\varnothing\} \rvert = 1\) | Tanım 15.1 |
| \(A \nsubseteq B \Leftrightarrow \exists x, \; (x \in A) \wedge (x \notin B)\) | Teorem 14.1 |
| \(\subseteq\) geçişmelidir; \(\in\) geçişmeli değildir | Teorem 14.4, Örnek 14.4 |
| \(\lvert A \rvert = n\) ise \(\lvert P(A) \rvert = 2^n\); öz alt küme sayısı \(2^n - 1\) | Teorem 15.2 |
| Belirli \(k\) öğeyi içeren (ya da içermeyen) alt küme sayısı \(2^{n-k}\) | Teorem 15.2 |
Son satırın gerekçesi, kuvvet kümesi teoreminin “her öğe için alırım ya da almam” sayımıdır: durumu belirlenmiş \(k\) öğe için seçim yoktur, kalan \(n - k\) öğenin her biri için iki seçim vardır. Örneğin \(\{1, 2, 3, 4, 5, 6\}\) kümesinin \(1\)’i içeren fakat \(2\)’yi içermeyen alt kümeleri, \(\{3, 4, 5, 6\}\)’nın her alt kümesine \(1\) eklenerek elde edilir; bunlardan \(2^4 = 16\) tane vardır. Aynı küme farklı formüllerle verilmişse her formülü \(2k + r\) biçimine indirip karşılaştırmak en güvenli yoldur (Örnek 14.6).
Örnek 20.15 (Dört Öğeli Bir Küme) \(A = \big\{\varnothing, \, 1, \, \{1\}, \, \{1, 2\}\big\}\) olsun. \(\varnothing \in A\), \(\;\varnothing \subset A\), \(\;\{1\} \in A\), \(\;\{1\} \subseteq A\), \(\;\{2\} \subseteq A\), \(\;\{1, 2\} \subseteq A\), \(\;\big\{\{1, 2\}\big\} \subseteq A\) ve \(\big\{\varnothing, \{1\}\big\} \in P(A)\) önermelerinden hangileri doğrudur?
Çözüm
\(A\)’nın dört öğesi vardır: \(\varnothing\), \(1\), \(\{1\}\) ve \(\{1, 2\}\). Dikkat: \(2\) sayısı \(A\)’nın öğesi değildir.
| Önerme | Gerekçe | Değer |
|---|---|---|
| \(\varnothing \in A\) | \(\varnothing\) listede yazılı | Doğru |
| \(\varnothing \subset A\) | boş küme her kümenin alt kümesi, \(A \neq \varnothing\) | Doğru |
| \(\{1\} \in A\) | \(\{1\}\) listede yazılı | Doğru |
| \(\{1\} \subseteq A\) | tek öğesi \(1\), listede | Doğru |
| \(\{2\} \subseteq A\) | \(2 \notin A\) | Yanlış |
| \(\{1, 2\} \subseteq A\) | \(2 \notin A\) (\(\{1,2\} \in A\) olsa da) | Yanlış |
| \(\big\{\{1, 2\}\big\} \subseteq A\) | tek öğesi \(\{1, 2\}\), listede | Doğru |
| \(\big\{\varnothing, \{1\}\big\} \in P(A)\) | \(\varnothing \in A\) ve \(\{1\} \in A\) olduğundan alt küme | Doğru |
Altı önerme doğru, iki önerme yanlıştır.
\(\blacksquare\)
20.11 Kartezyen Çarpım
Kartezyen çarpımın öğeleri sıralı ikililerdir; sıra önemlidir ve \((a, b) = (c, d)\) ancak \(a = c\) ve \(b = d\) iken doğrudur (Tanım 18.2). Özellikler aşağıdadır.
| Özellik | Doğru mu? | Kitapta |
|---|---|---|
| \(A \times B = B \times A\) | Genel olarak hayır | Teorem 18.1 |
| \((A \times B) \times C = A \times (B \times C)\) | Evet | Teorem 18.1 |
| \(A \times (B \cup C) = (A \times B) \cup (A \times C)\), sağdan da | Evet | Teorem 18.2 |
| \(A \times (B \cap C) = (A \times B) \cap (A \times C)\), sağdan da | Evet | Teorem 18.2, Örnek 18.2 |
| \(A \times (B \setminus C) = (A \times B) \setminus (A \times C)\) | Evet | Örnek 18.3 |
| \(A \subseteq B\) ve \(C \subseteq D\) ise \(A \times C \subseteq B \times D\) | Evet | Teorem 18.3 |
| \((A \cup B) \times (C \cup D) = (A \times C) \cup (B \times D)\) | Hayır | aşağıdaki hata listesi |
- \((a, b)\) ile \(\{a, b\}\)’yi karıştırmak: kümede sıra yoktur, ikilide vardır; \((a, a)\) geçerli bir ikilidir.
- İki birleşimin çarpımını “çapraz terimler” olmadan açmak. \(A = \{1\}\), \(B = \{2\}\), \(C = \{a\}\), \(D = \{b\}\) için \((1, b) \in (A \cup B) \times (C \cup D)\) fakat \((1, b) \notin (A \times C) \cup (B \times D)\)’dir.
- Eleman sayısını toplamak: \(s(A \times B)\), \(s(A) + s(B)\) değil \(s(A) \cdot s(B)\)’dir.
Örnek 20.16 (Birleşim ile Kesişimin Çarpımı) \(A = \{1, 2\}\), \(B = \{2, 3\}\) ve \(C = \{3, 4\}\) olsun. \((A \cup B) \times (B \cap C)\) kümesini listeleyiniz.
Çözüm
Önce parantez içlerini bulalım: \[A \cup B = \{1, 2, 3\}, \qquad B \cap C = \{3\}.\] Birinci bileşen \(\{1, 2, 3\}\)’ten, ikinci bileşen \(\{3\}\)’ten seçilir: \[(A \cup B) \times (B \cap C) = \big\{(1, 3), \, (2, 3), \, (3, 3)\big\}.\] Eleman sayısı \(3 \cdot 1 = 3\)’tür.
\(\blacksquare\)
20.12 Bağıntılar
\(A\)’dan \(B\)’ye bir bağıntı, \(A \times B\)’nin herhangi bir alt kümesidir (Tanım 19.1). Yansıma ve simetri yalnız bir \(A\) kümesinde, yani \(\beta \subseteq A \times A\) için tanımlıdır.
- Bağıntı mı? Her ikilinin birinci bileşeni \(A\)’da, ikinci bileşeni \(B\)’de olmalıdır; bu kurala uymayan tek bir ikili, kümenin bağıntı olmadığını göstermeye yeter.
- İkilileri yaz. Kural verilmişse \(A\)’nın her \(x\) öğesi için kuralı sağlayan bütün \(y\)’leri tek tek bul.
- Ters bağıntı. Her ikilinin bileşenlerini yer değiştir: \((x, y) \in \beta \Leftrightarrow (y, x) \in \beta^{-1}\) (Tanım 19.2, Teorem 19.1).
- Özellikler. Yansıma için \(I_A \subseteq \beta\), simetri için \(\beta = \beta^{-1}\) olup olmadığına bak.
| Özellik | Sınama | Bozulduğunu göstermek | Kitapta |
|---|---|---|---|
| Yansıma | Her \(x \in A\) için \((x, x) \in \beta\), yani \(I_A \subseteq \beta\) | \((x, x) \notin \beta\) olan tek bir \(x\) | Tanım 19.4, Tanım 19.3 |
| Simetri | Her \((x, y) \in \beta\) için \((y, x) \in \beta\), yani \(\beta = \beta^{-1}\) | \((x, y) \in \beta\), \((y, x) \notin \beta\) olan tek bir ikili | Tanım 19.5 |
Kısa yollar: sayma. \(\lvert A \rvert = m\), \(\lvert B \rvert = n\) ise \(A \times B\)’nin \(mn\) öğesi vardır ve \(A\)’dan \(B\)’ye \(2^{mn}\) bağıntı tanımlanır (Teorem 15.2). \(n\) öğeli bir kümede yansıyan bağıntı sayısı \(2^{n^2 - n}\)’dir: \(n\) köşegen ikili zorunludur, kalan \(n^2 - n\) ikilinin her biri için iki seçim vardır. Simetrik bağıntı sayısı \(2^{n(n+1)/2}\)’dir: \((x, y)\) ile \((y, x)\) birlikte alınıp birlikte bırakılır, böylece \(n\) köşegen ikili ile \(\frac{n(n-1)}{2}\) çift serbestçe seçilir.
- Simetri koşulunu \(A \times A\)’nın bütün ikililerine uygulamak; koşul yalnız \(\beta\)’daki ikililer içindir. Örneğin \(\varnothing\) bağıntısı simetriktir ama \(A \neq \varnothing\) ise yansıyan değildir.
- Yansıma ile simetriyi birbirine bağlamak; ikisi bağımsızdır. Doğrular arasındaki diklik simetriktir ama yansıyan değildir; alt küme bağıntısı yansıyandır ama simetrik değildir (Örnek 19.5).
- \(y = \beta(x)\) gösteriminde \(x\)’e tek bir \(y\) karşılık geldiğini sanmak; bağıntıda birden çok \(y\) olabilir, hiç olmayabilir.
Örnek 20.17 (Bölme Bağıntısının Tersi) \(A = \{1, 2, 3, 6\}\) kümesinde \(\beta = \{(x, y) : x \in A, \; y \in A, \; x \mid y\}\) bağıntısı tanımlansın. \(\beta^{-1}\) ters bağıntısını yazınız.
Çözüm
Önce \(\beta\)’yı belirleyelim; \(A\)’nın her \(x\) öğesi için \(A\)’da böldüğü sayıları arayalım:
- \(x = 1\): \(1\) her sayıyı böler \(\to\) \((1,1), (1,2), (1,3), (1,6)\)
- \(x = 2\): \(2 \mid 2\), \(2 \mid 6\) \(\to\) \((2,2), (2,6)\)
- \(x = 3\): \(3 \mid 3\), \(3 \mid 6\) \(\to\) \((3,3), (3,6)\)
- \(x = 6\): \(6 \mid 6\) \(\to\) \((6,6)\)
\(\beta\) dokuz ikiliden oluşur. Her ikilinin bileşenlerini yer değiştirelim: \[ \begin{aligned} \beta^{-1} = \big\{&(1,1), \, (2,1), \, (3,1), \, (6,1), \, (2,2), \\ &(6,2), \, (3,3), \, (6,3), \, (6,6)\big\}. \end{aligned} \] Yani \(\beta^{-1}\), “\(y \mid x\)” kuralıyla tanımlı bağıntıdır.
\(\blacksquare\)
Örnek 20.18 (Bölme Bağıntısının Özellikleri) \(A = \{1, 2, 3, 6\}\) kümesinde \(\beta = \{(x, y) : x \in A, \; y \in A, \; x \mid y\}\) bağıntısı yansıma ve simetri özelliklerinden hangilerine sahiptir?
Çözüm
Yansıma. Her \(x \in A\) için \(x = x \cdot 1\) olduğundan \(x \mid x\)’tir; yani \((1,1), (2,2), (3,3), (6,6) \in \beta\) ve \(I_A \subseteq \beta\)’dır. \(\beta\) yansıyandır.
Simetri. \(1 \mid 2\) olduğundan \((1, 2) \in \beta\)’dır; fakat \(2 \nmid 1\) olduğundan \((2, 1) \notin \beta\)’dır. Bu tek ikili simetriyi bozar; \(\beta\) simetrik değildir. Aynı sonuç \(\beta \neq \beta^{-1}\) olmasından da görülür: \((2, 1)\) ikilisi \(\beta^{-1}\)’dedir (Örnek 20.17) ama \(\beta\)’da değildir.
\(\blacksquare\)