Önermeler mantığı ve ispatlar: adım adım çözümlü alıştırma soruları
Şekiller, ipuçları ve ayrıntılı çözümlerle ücretsiz Önermeler mantığı ve ispatlar alıştırma soruları. Her seferinde yeni değerler, üç seviyede: doğruluk tabloları, denklikler ve ispat yöntemleri, niceleyiciler ve argümanlar.
Önermeler mantığı ve ispatlar konusunu sıfırdan öğrenin
1Önermeler ve bağlaçlar
Önerme, “7 asaldır” gibi ya doğru ya yanlış olan bir ifadedir. Bir harfle, p ya da q ile yazarız; doğruluk değerini ise 1 (doğru) veya 0 (yanlış) ile gösteririz.
Bağlaçlar küçük formüllerden daha büyük formüller kurar:
¬p (p değil) değeri tersine çevirir.
p ∧ q (ve) yalnızca ikisi de 1 olduğunda 1’dir.
p ∨ q (veya) yalnızca ikisi de 0 olduğunda 0’dır. Kapsayıcı veya’dır: ikisi de doğru olabilir.
p → q (p ise q) yalnızca p = 1 ve q = 0 olduğunda 0’dır.
p ↔ q (ancak ve ancak) p ile q aynı değere sahip olduğunda 1’dir.
Gerektirme birçok öğrenciyi şaşırtır: p yanlışken q ne olursa olsun p → q doğrudur. “Yağmur yağarsa şemsiye alırım” sözü yalnızca şemsiyesiz bir yağmurlu günde bozulur.
Kendini sına p = 0 ve q = 1. p → q’nun değeri nedir?
0
1
Bağlama bağlıdır
Tanımsızdır
Cevap: 1. Bir gerektirme yalnızca koşul sağlanıp sonuç sağlanmadığında (p = 1, q = 0) yanlıştır. p = 0 iken q ne olursa olsun doğrudur.
2Doğruluk tabloları
Bir doğruluk tablosu değişkenlerin doğruluk değerlerinin her birleşimini listeler. n farklı değişkenle 2ⁿ satır vardır: iki değişken için 4, üç için 8, dört için 16. İki kez geçen bir değişken yine de bir kez sayılır.
İçten dışa doğru çalışın. Her alt formüle kendi sütununu verin; böylece her yeni sütun için, elinizdeki sütunlara yalnızca bir bağlaç uygulamanız gerekir.
Değişkenleri listeleyin ve 2ⁿ birleşimin hepsini yazın; hepsinin 1 olduğu satırla başlayın.
Her alt formül için bir sütun ekleyin, en içtekinden başlayarak.
Her sütunu ana bağlacının kuralına göre doldurun.
Cevabı son sütundan okuyun: 1’leri sayın ya da istenen satırı bulun.
Kendini sına (p ∧ q) → (r ∨ p) formülünün doğruluk tablosu kaç satırdan oluşur?
16
4
6
8
Cevap: 8. Formülde üç farklı değişken vardır: p, q ve r; dolayısıyla 2³ = 8 satır. p iki kez geçer ama tek bir değişkendir; 16, dört geçiş için 2⁴ olurdu.
3Çözümlü bir örnek
Her adımı izleyin. Açmadan önce bir sonrakini tahmin etmeye çalışın.
İki değişken, p ve q, dolayısıyla 4 satır: (1, 1), (1, 0), (0, 1), (0, 0).
2
p → q sütunu
Yalnızca p = 1, q = 0 satırında 0’dır:
p → q: 1, 0, 1, 1
3
¬q sütunu
¬q: 0, 1, 0, 1
4
Ve bağlacı (konjonksiyon)
İki sütun da 1 olmalıdır. Bu yalnızca son satırda, p = 0 ve q = 0 iken olur.
(p → q) ∧ ¬q: 0, 0, 0, 1
Cevap
Formül 1 satırda doğrudur: p = 0, q = 0 satırı. p → q ile ¬q birlikte ¬p’yi verir (modus tollens); sebep budur.
4Denklikler ve ispat yöntemleri
İki formülün doğruluk tablosu sütunları özdeşse bunlar denktir (≡). Totoloji her satırda 1’dir, çelişki her satırda 0’dır, olumsallık ise ikisi de değildir.
En çok kullandığınız kurallar:
¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p ¬(p → q) ≡ p ∧ ¬q
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Bu kurallar ispat yöntemlerinin temelidir. p → q’nun karşıt değil yoluyla ispatı, bunun yerine denk olan ¬q → ¬p’yi ispatlar. Olmayana ergi yoluyla ispat, gerektirmenin yanlış olabileceği tek durumu, p ∧ ¬q’yu varsayar ve imkânsız bir sonuca ulaşır.
Dikkat: karşıtı q → p ve tersi ¬p → ¬q, p → q’ya denk değildir.
Kendini sına Hangi formül ¬(p ∧ q)’ya denktir?
p ∨ q
¬p ∧ q
¬p ∧ ¬q
¬p ∨ ¬q
Cevap: ¬p ∨ ¬q. De Morgan’a göre ∧ , ∨ olur ve her iki parçanın değili alınır. ¬p ∧ ¬q, p ∨ q’nun değilidir, farklı bir önermedir: p ile q’dan tam biri doğruyken yanlıştır, oysa ¬(p ∧ q) doğrudur.
5Niceleyiciler ve geçerli argümanlar
Bir küme üzerinde değişkenlerle, ∀x P(x) “P her x için geçerlidir”, ∃x P(x) ise “P en az bir x için geçerlidir” der. Bir değil işlemi niceleyiciyi değiştirir:
¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)
Değili içeri doğru, her seferinde bir adım taşıyın; içeride önermeler mantığının kurallarını kullanın. Örneğin ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x)): “her P bir Q değildir” demek “bazı P’ler Q değildir” demektir.
Bir argüman, tüm öncüllerin 1 olduğu her satırda sonuç da 1 ise geçerlidir. Klasik geçerli biçimler modus ponens (p → q, p, öyleyse q), modus tollens (p → q, ¬q, öyleyse ¬p) ve varsayımsal kıyastır (p → q, q → r, öyleyse p → r).
Tüm öncüllerin 1, sonucun 0 olduğu bir satır bir karşı örnektir. Sonucu onaylamak (p → q, q, öyleyse p) geçersizdir: p = 0, q = 1 satırı bir karşı örnektir.
Kendini sına “Her öğrenci geçti”, ∀x P(x), önermesinin değili nedir?
Sabit bir öğrenci x için ¬P(x)
∀x ¬P(x): hiçbir öğrenci geçmedi
∃x P(x): bazı öğrenciler geçti
∃x ¬P(x): bazı öğrenciler geçmedi
Cevap: ∃x ¬P(x): bazı öğrenciler geçmedi. Kalan tek bir öğrenci “her öğrenci geçti” önermesini yanlış yapmaya yeter. “Hiçbir öğrenci geçmedi” değilinden çok daha güçlüdür.
6Sık yapılan hatalar
p yanlışken p → q’yu yanlış saymak. Yalnızca p = 1 ve q = 0 iken yanlıştır.
Satır sayısını bulurken tekrar eden bir değişkeni iki kez saymak.
Karşıt değili ¬q → ¬p ile karşıtı q → p ya da tersi ¬p → ¬q birbirine karıştırmak.
∀x P(x) önermesinin değilini ∀x ¬P(x) olarak yazmak: niceleyicinin ∃’ye dönmesi gerekir.
¬(p ∧ q)’yu ¬p ∧ ¬q olarak yazmak: De Morgan bağlacı da değiştirir.
Kendini sına Hangi önerme “n² çiftse n çifttir” önermesinin karşıt değilidir?
n tekse n² tektir
n çiftse n² çifttir
n² tekse n tektir
n² çifttir ve n tektir
Cevap: n tekse n² tektir. İki parçayı yer değiştirin ve ikisinin de değilini alın: (n çift değil) → (n² çift değil). “n çiftse n² çifttir” karşıtıdır; son seçenek ise olmayana ergi ile ispatın varsaydığı şeydir.
7Sınav soruları nasıl görünür
Kolay: doğruluk tabloları. Satır sayısını bulur, bir formülün doğru olduğu satırları sayar ya da bir formülü doğru ya da yanlış yapan tek satıra tıklarsınız.
Orta: denklikler ve ispat yöntemleri. Bir formülün totoloji, çelişki ya da olumsallık olduğuna karar verir, denk formülü ya da karşıt değil veya olmayana ergi ile ispatta kanıtlanacak önermeyi seçersiniz.
Zor: niceleyiciler ve argümanlar. Niceleyicili önermelerin değilini alır, öncüllerden çıkan sonucu seçer, geçersiz bir argümanın karşı örnek satırına tıklar ya da dört değişkenli bir tabloda doğru satırları sayarsınız.
Doğruluk tablosunun tam bir satırı ¬(p ∨ q) → q formülünü yanlış yapar. O satıra tıklayın.
¬(p ∨ q) → q
1p = 1, q = 1
2p = 1, q = 0
3p = 0, q = 1
4p = 0, q = 0
İpuçlarını göster
a → b yalnızca a = 1 ve b = 0 olduğunda 0’dır. ¬a değeri tersine çevirir. a ∨ b yalnızca ikisi de 0 olduğunda 0’dır.
Önce ana bağlacı çözün: tüm formülün 0 olması için iki tarafı ne olmalıdır?
Her parçaya kendi sütununu verin: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Cevabı ve açıklamayı göster
Doğruluk tabloları: n farklı değişkenli bir formülün 2ⁿ satırı vardır; her satır doğruluk değerlerinin bir birleşimidir (1 = doğru, 0 = yanlış). İçten dışa doğru çalışın ve her alt formüle kendi sütununu verin. ¬a değeri tersine çevirir; a ∧ b yalnızca ikisi de 1 olduğunda 1’dir; a ∨ b yalnızca ikisi de 0 olduğunda 0’dır; a → b yalnızca a = 1 ve b = 0 olduğunda 0’dır; a ↔ b iki taraf eşit olduğunda 1’dir.
Hangi formül (b ∧ c) → a formülüne mantıksal olarak denktir? Üzerine tıklayın.
(b ∧ c) → a
1(b → a) ∧ (c → a)
2b → (c → a)
3b ∧ (c → a)
4(b → c) → a
İpuçlarını göster
Denk formüller doğruluk tablosunun her satırında aynı değeri alır. Farklı oldukları tek bir satır bir seçeneği eler.
(b ∧ c) → a formülünü 0 yapan bir satır deneyin ve hangi seçeneklerin orada da 0 olduğuna bakın.
Dışa aktarma: (a ∧ b) → c ≡ a → (b → c). İkisi de yalnızca a = 1, b = 1 ve c = 0 iken 0’dır.
Cevabı ve açıklamayı göster
Mantıksal denklik: doğruluk tablosunun her satırında aynı değere sahip iki formül denktir (≡). Totoloji her satırda 1, çelişki her satırda 0’dır; olumsallık ikisi de değildir. Yararlı kurallar: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b ve ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (karşıt değil); ¬(a → b) ≡ a ∧ ¬b; ve dağılma kuralları, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Kural
Dışa aktarma: (a ∧ b) → c ≡ a → (b → c). İkisi de yalnızca a = 1, b = 1 ve c = 0 iken 0’dır.
(b ∧ c) → a ≡ b → (c → a)
Doğruluk tablosuyla denetleyin
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 0 1
a = 1, b = 0, c = 0: 1 | 1 1 0 1
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0
Cevap
b → (c → a)
Çubuktan sonraki sütunlar, gösterilen sırayla seçeneklerdir.
Örnek 3Zor
(q ∧ p) → r; q; ¬r öncülleri verilmiştir. Bunlardan hangi sonuç çıkar? Üzerine tıklayın.
(q ∧ p) → rq¬r
1p
2p ∧ ¬r
3¬p
4r
İpuçlarını göster
Tüm öncüllerin 1 olduğu her satırda bir sonuç da 1 ise, bu sonuç öncüllerden çıkar.
Tüm öncülleri 1 yapan satırları bulun, sonra her seçeneği bu satırlarda sınayın.
Bu standart bir kuraldır: bir konjonksiyonla modus tollens.
Cevabı ve açıklamayı göster
Niceleyiciler ve argümanlar: ¬∀x P(x) ≡ ∃x ¬P(x) ve ¬∃x P(x) ≡ ∀x ¬P(x). Değili içeri taşıyın, geçtiği her niceleyiciyi değiştirin ve iç formülün değilini ¬(a → b) ≡ a ∧ ¬b gibi önermeler mantığı kurallarıyla alın. Tüm öncüllerin 1 olduğu her satırda sonuç da 1 ise bir argüman geçerlidir. Öncüllerin doğru, sonucun yanlış olduğu tek bir satır bir karşı örnektir ve argümanın geçersiz olduğunu gösterir.
Tüm öncüllerin doğru olduğu satırlar
p = 0, q = 1, r = 0: p = 0, p ∧ ¬r = 0, ¬p = 1, r = 0
Sonuç
¬p (bir konjonksiyonla modus tollens)
Cevap
¬p
Sorular ve cevaplar
Önermeler mantığı ve ispatlar nedir?
Bağlaçlar küçük formüllerden daha büyük formüller kurar:
Gerektirme birçok öğrenciyi şaşırtır: p yanlışken q ne olursa olsun p → q doğrudur. “Yağmur yağarsa şemsiye alırım” sözü yalnızca şemsiyesiz bir yağmurlu günde bozulur.
Önermeler mantığı ve ispatlar soruları adım adım nasıl çözülür?
Farklı değişkenleri sayın: doğruluk tablosu 2ⁿ satırdan oluşur ve hepsinin 1 olduğu satırla başlar.
Her alt formüle kendi sütununu verin ve sütunları içten dışa doğru doldurun.
Her bağlacın kuralını uygulayın: → yalnızca 1 → 0 için 0’dır, ↔ iki taraf aynı olduğunda 1’dir.
Denkliklerde son sütunları satır satır karşılaştırın; bir argümanda ise yalnızca bütün öncüllerin 1 olduğu satırlara bakın.
Niceleyicili bir önermenin değilini almak için ¬’yi içeri taşıyın, ∀ ile ∃’yi değiştirin ve iç formülün değilini alın.
Önermeler mantığı ve ispatlar konusunda en sık yapılan hatalar nelerdir?
p yanlışken p → q’yu yanlış saymak.
Satır sayısını bulurken tekrar eden bir değişkeni iki kez saymak.
Karşıt değili ¬q → ¬p ile karşıtı q → p birbirine karıştırmak.
∀x P(x) önermesinin değilini ∃x ¬P(x) yerine ∀x ¬P(x) olarak yazmak.
De Morgan’ı ∧ ile ∨’yi değiştirmeden uygulamak.
Önermeler mantığı ve ispatlar alıştırmaları neleri kapsar?
Kolay: doğruluk tabloları
Orta: denklikler ve ispat yöntemleri
Zor: niceleyiciler ve argümanlar
Her soruda yeni değerler olur; böylece bir cevabı değil, yöntemi öğrenirsiniz. Takıldınız mı? Önce küçük bir ipucu açın, tam açıklamayı ise yalnızca gerektiğinde.
Çalışma nasıl işler
Her soruda yeni değerler olur; böylece bir cevabı değil, yöntemi öğrenirsiniz.
Takıldınız mı? Önce küçük bir ipucu açın, tam açıklamayı ise yalnızca gerektiğinde.
İlerlemeniz, hatalarınız ve kaydettiğiniz sorular saklanır; böylece sınavdan önce gözden geçirebilirsiniz.