Diyelim ki X ve Y olmak üzere iki formül var. X ↔ Y bir totoloji ise bu formüllere eşdeğerlik adı verilecektir. Eğer X ↔ Y iki formülü bir totoloji ise bunu X ⇔ Y olarak da yazabiliriz ve bu ilişkiyi X'in Y'ye eşdeğerliği şeklinde de okuyabiliriz.
Not: Formülün doğrusal denkliği yapılırken dikkat edilmesi gereken bazı noktalar vardır. Bunlar aşağıda açıklanmıştır:
- ⇔ yalnızca sembolü belirtmek için kullanılır ancak bağlayıcı değildir.
- X ↔ Y bir totoloji ise X ve Y'nin doğruluk değeri her zaman eşit olacaktır.
- Eşdeğerlik ilişkisi simetrik ve geçişli olmak üzere iki özellik içerir.
Yöntem 1: Doğruluk tablosu yöntemi:
Bu yöntemde herhangi iki ifadeli formülün doğruluk tablolarını oluşturacağız ve ardından bu ifadelerin eşdeğer olup olmadığını kontrol edeceğiz.
Örnek 1: Bu örnekte, X ∨ Y ⇔ ¬(¬X ∧ ¬Y)'yi kanıtlamamız gerekiyor.
Çözüm: X ∨ Y ⇔ ¬(¬X ∧ ¬Y)'nin doğruluk tablosu şu şekilde açıklanmaktadır:
| X | VE | X ∨ Y | ¬X | ¬Ve | ¬X ∧ ¬Y | ¬(¬X ∧ ¬Y) | X ∨ Y ⇔ ¬(¬X ∧ ¬Y) |
|---|---|---|---|---|---|---|---|
| T | T | T | F | F | F | T | T |
| T | F | T | F | T | F | T | T |
| F | T | T | T | F | F | T | T |
| F | F | F | T | T | T | F | T |
Görebildiğimiz gibi X ∨ Y ve ¬(¬X ∧ ¬Y) bir totolojidir. Dolayısıyla X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Örnek 2: Bu örnekte (X → Y) ⇔ (¬X ∨ Y)'yi kanıtlamamız gerekiyor.
Çözüm: (X → Y) ⇔ (¬X ∨ Y)'nin doğruluk tablosu şu şekilde tanımlanır:
| X | VE | X → Y | ¬X | ¬X ∨ Y | (X → Y) ⇔ (¬X ∨ Y) |
|---|---|---|---|---|---|
| T | T | T | F | T | T |
| T | F | F | F | F | T |
| F | T | T | T | T | T |
| F | F | T | T | T | T |
Görebildiğimiz gibi X → Y ve (¬X ∨ Y) bir totolojidir. Dolayısıyla (X → Y) ⇔ (¬X ∨ Y)
Denklik formülü:
Aşağıda açıklanan denklik formülünü kanıtlamak için kullanılan çeşitli yasalar vardır:
İdempotent yasa: Eğer bir ifade formülü varsa, o zaman aşağıdaki özellikleri taşıyacaktır:
X ∨ X ⇔ X X ∧ X ⇔ X
Federal hukuk: Üç ifade formülü varsa, aşağıdaki özellikleri taşıyacaktır:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Değişmeli kanun: İki ifade formülü varsa, aşağıdaki özellikleri taşıyacaktır:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Dağıtım kanunu: Üç ifade formülü varsa, aşağıdaki özellikleri taşıyacaktır:
css'de bir resim nasıl ortalanır
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Kimlik yasası: Eğer bir ifade formülü varsa, o zaman aşağıdaki özellikleri taşıyacaktır:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Tamamlayıcı yasa: Eğer bir ifade formülü varsa, o zaman aşağıdaki özellikleri taşıyacaktır:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Emilim Yasası: İki ifade formülü varsa, aşağıdaki özellikleri taşıyacaktır:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Morgan Yasasından: İki ifade formülü varsa, aşağıdaki özellikleri taşıyacaktır:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
Yöntem 2: Değiştirme Süreci
Bu yöntemde A : X → (Y → Z) formülünü varsayacağız. Y → Z formülü formülün parçası olarak bilinebilir. Formülün bu kısmını, yani Y → Z'yi, A'daki ¬Y ∨ Z denklik formülünün yardımıyla değiştirirsek, o zaman başka bir formül elde ederiz, yani B : X → (¬Y ∨ Z). Verilen A ve B formüllerinin birbirine eşdeğer olup olmadığını doğrulamak kolay bir işlemdir. Değiştirme işlemi sayesinde A'dan B'yi alabiliriz.
Örnek 1: Bu örnekte, {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z olduğunu kanıtlamamız gerekiyor.
Çözüm: Burada sol tarafı alıp sağ tarafı almaya çalışacağız.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Şimdi birleşme yasasını şu şekilde kullanacağız:
⇔ (¬X ∨ ¬Y) ∨ Z
Şimdi De Morgan yasasını şu şekilde kullanacağız:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Dolayısıyla kanıtlandı
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z Örnek 2: Bu örnekte, {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y olduğunu kanıtlamamız gerekiyor.
Çözüm: Burada sol tarafı alıp sağ tarafı almaya çalışacağız.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Dolayısıyla kanıtlandı
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
Örnek 3: Bu örnekte X → (Y → X) ⇔ ¬X → (X → Y) olduğunu kanıtlamamız gerekiyor.
Çözüm: Burada sol tarafı alıp sağ tarafı almaya çalışacağız.
X → (Y → X) ⇔ ¬X ∨ (Y → X) ⇔ ¬X ∨ (¬Y ∨ X) ⇔ (¬X ∨ X) ∨ ¬Y ⇔ T ∨ ¬Y ⇔ T and ¬X → (X → Y) ⇔ ¬(¬X) ∨ (X → Y) ⇔ X ∨ (¬X ∨ Y) ⇔ (X ∨ ¬X) ∨ Y ⇔ T ∨ Y ⇔ T
Dolayısıyla kanıtlandı
X → (Y → X) ⇔ ¬X → (X → Y)
Örnek 4: Bu örnekte, (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z olduğunu kanıtlamamız gerekiyor.
Çözüm: Burada sol tarafı alıp sağ tarafı almaya çalışacağız.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Şimdi İlişkilendirme ve Dağıtım yasalarını şu şekilde kullanacağız:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Şimdi De Morgan yasasını şu şekilde kullanacağız:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Şimdi Dağıtım yasasını şu şekilde kullanacağız:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Dolayısıyla kanıtlandı
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
Örnek 5: Bu örnekte, ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z)'nin bir totoloji olduğunu göstermemiz gerekiyor.
Çözüm: Burada küçük parçalar alıp çözeceğiz.
İlk önce De Morgan yasasını kullanacağız ve aşağıdakileri elde edeceğiz:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
Öyleyse,
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
Ayrıca
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Buradan
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Böylece
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Dolayısıyla verilen formülün bir totoloji olduğunu söyleyebiliriz.
Örnek 6: Bu örnekte (X ∧ Y) → (X ∨ Y)'nin bir totoloji olduğunu göstermemiz gerekiyor.
Çözüm: (X ∧ Y) → (X ∨ Y)
c rastgele sayı
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Şimdi De Morgan yasasını şu şekilde kullanacağız:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Şimdi birleşme yasasını ve değişme yasasını şu şekilde kullanacağız:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Şimdi Olumsuzluk yasasını şu şekilde kullanacağız:
⇔ (T ∨ T) ⇔ T
Dolayısıyla verilen formülün bir totoloji olduğunu söyleyebiliriz.
Örnek 7: Bu örnekte, aşağıda açıklanan bazı ifadelerin olumsuzunu yazmamız gerekiyor:
- Marry eğitimini tamamlayacak veya XYZ Şirketinin katılma mektubunu kabul edecek.
- Harry yarın bisiklete binecek ya da koşacak.
- İyi not alırsam kuzenim kıskanır.
Çözüm: Öncelikle ilk ifadeyi şu şekilde çözeceğiz:
1. Diyelim ki X: Marry eğitimini tamamlayacak.
Y: XYZ Şirketinin katılma mektubunu kabul edin.
Bu ifadeyi ifade etmek için aşağıdaki sembolik formu kullanabiliriz:
X ∨ Y
X ∨ Y'nin olumsuzu şu şekilde tanımlanır:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Sonuç olarak, verilen ifadenin olumsuzu şöyle olacaktır:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Diyelim ki X: Harry bir gezintiye çıkacak
Y: Harry yarın koşacak
Bu ifadeyi ifade etmek için aşağıdaki sembolik formu kullanabiliriz:
X ∨ Y
X ∨ Y'nin olumsuzu şu şekilde tanımlanır:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
Sonuç olarak, verilen ifadenin olumsuzu şöyle olacaktır:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Diyelim ki X: Eğer iyi notlar alırsam.
Y: Kuzenim kıskanacak.
Bu ifadeyi ifade etmek için aşağıdaki sembolik formu kullanabiliriz:
X → Y
X → Y'nin olumsuzu şu şekilde tanımlanır:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
Sonuç olarak, verilen ifadenin olumsuzu şöyle olacaktır:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
Örnek 8: Bu örnekte bazı ifadelerin olumsuzluğunu De Morgan yasası yardımıyla yazmamız gerekiyor. Bu ifadeler şu şekilde açıklanmaktadır:
- Bir pırlanta setine ve altın bir yüzüğe ihtiyacım var.
- İyi bir iş bulursun ya da iyi bir partner bulamazsın.
- Çok fazla iş alıyorum ve üstesinden gelemiyorum.
- Köpeğim seyahate çıkıyor ya da evde ortalığı karıştırıyor.
Çözüm: Tüm ifadelerin De Morgan yasası yardımıyla olumsuzlanması tek tek şu şekilde anlatılmaktadır:
- Bir pırlanta setine ihtiyacım yok ya da altın bir yüzüğe değmeyecek.
- İyi bir iş bulamazsınız ve iyi bir ortak bulursunuz.
- Çok fazla iş almıyorum ya da halledebilirim.
- Köpeğim geziye çıkmıyor ve evde karışıklık yaratmıyor.
Örnek 9: Bu örnekte bazı ifadelerimiz var ve bu ifadelerin olumsuzunu yazmamız gerekiyor. Açıklamalar şu şekilde anlatılıyor:
- Yağmur yağarsa plaja gitme planı iptal edilir.
- Eğer çok çalışırsam sınavda iyi notlar alırım.
- Gece yarısı bir partiye gidersem babamdan ceza alacağım.
- Benimle konuşmak istemiyorsan numaramı engellemelisin.
Çözüm: Tüm ifadelerin olumsuzluğu tek tek şöyle anlatılmaktadır:
- Plaja gitme planı iptal edilirse yağmur yağıyor demektir.
- Sınavdan iyi not alırsam çok çalışırım.
- Eğer babamdan ceza alırsam gece yarısı partisine giderim.
- Numaramı engellemek zorunda kalırsan benimle konuşmak istemezsin.
Örnek 10: Bu örnekte (X → Y) → Z ve X → (Y → Z) mantıksal olarak eşdeğer olup olmadığını kontrol etmeliyiz. Cevabımızı doğruluk tablolarının yardımıyla ve her iki ifadeyi de basitleştirmek için mantık kurallarının yardımıyla gerekçelendirmeliyiz.
Çözüm: İlk olarak, (X → Y) → Z ve X → (Y → Z)'nin mantıksal olarak eşdeğer olup olmadığını kontrol etmek için yöntem 1'i kullanacağız; bu, aşağıda açıklanmıştır:
ikili ağaç türleri
Yöntem 1: Burada aşağıdakileri varsayacağız:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
Ve
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
Yöntem 2: Şimdi ikinci yöntemi kullanacağız. Bu yöntemde doğruluk tablosunu kullanacağız.
| X | VE | İLE | X → Y | (X → Y) → Z | Y → Z | X → (Y → Z) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | T | F | T | F | F | F |
| T | F | T | F | T | T | T |
| T | F | F | F | T | T | T |
| F | T | T | T | T | T | T |
| F | T | F | T | F | F | T |
| F | F | T | T | T | T | T |
| F | F | F | T | F | T | T |
Bu doğruluk tablosunda (X → Y) → Z ve X → (Y → Z) sütunlarının aynı değerleri içermediğini görebiliriz.