puzzle sudaku

BM202 AYRIK İŞLEMSEL YAPILAR
Yrd. Doç. Dr. Mehmet ŞİMŞEK
Önermelerin Eşdeğerlikleri
Section 1.3
Totoloji, Çelişkiler, ve Tesadüf
• Bir totoloji her zaman doğru olan bir önermedir.
– Örnek: p ∨¬p
• Bir çelişki her zaman yanlış olan bir önermedir.
– Örnek : p ∧¬p
• Bir tesadüf, totoloji ya da çelişki olmayan p gibi bir
önermedir.
P
¬p
p ∨¬p
p ∧¬p
T
F
T
F
F
T
T
F
Mantıksal Eşdeğerlik
•
•
•
Eğer p↔q bir totoloji ise p ve q bileşik önermeleri mantıksal eşdeğerdir.
İki bileşik önerme ancak ve ancak doğruluk tabloları aynı ise eşdeğerdir.
¬p ∨ q doğruluk tablosu ile p → q doğruluk tablosu aynı
p
q
¬p
¬p ∨ q
p→ q
T
T
F
T
T
T
F
F
F
F
F
T
T
T
T
F
F
T
T
T
De Morgan Kuralı
Augustus De Morgan
1806-1871
De Morgan’ın ikinci yasasının doğruluk tablosu
p
q
¬p
¬q
(p∨q)
¬(p∨q)
¬p∧¬q
T
T
F
F
T
F
F
T
F
F
T
T
F
F
F
T
T
F
T
F
F
F
F
T
T
F
T
T
Temel Mantıksal Eşdeğerlikler
• Aynı
,
• Baskınlık
,
• Eşkuvvetli
,
• Çift Değil:
• Değil :
,
Temel Mantıksal Eşdeğerlikler
• Değişim:
• Birleşim :
• Dağıtım:
• Yutma:
,
Daha Fazla Mantıksal Eşdeğerlikler
Yeni Mantıksal Eşdeğerlikler Oluşturma
• İki ifadenin mantıksal olarak eşdeğer olduğunu, ard arda
eşdeğer ifadeler oluşturarak bulabiliriz.
•
olduğunu göstermek için A ile başlayan ve B ile biten
eşdeğerlikler üretiriz.
Eşdeğerlik İspatları
Örnek:
ile
‘nin
mantıksal eşdeğer olduğunu gösterin.
Çözüm:
Eşdeğerlik İspatları
Örnek:
olduğunu gösterin
Çözüm:
ifadesinin totoloji
Önermenin İnandırıcılığı (Satisfiability)
• Bir bileşik önermenin değişkenlerine atanan doğruluk
değerleri ile önerme doğru olabiliyorsa bu bileşik
önermeye inandırıcı denir. Eğer bu durumu sağlayan
hiçbir doğruluk değeri yoksa bu bileşik önermeye
inandırıcı olmayan önerme denir.
• Bir bileşik önerme ancak ve ancak bu önermenin
değili bir totoloji ise inandırıcı olmayan önermedir.
Önerme İnandırıcılığı Üzerine Sorular
Örnek : Aşağıdaki bileşik önermelerin inandırıcılıklarını
değerlendirin.
Çözüm: İnandırıcı. p, q, ver’ye T değeri ata.
Çözüm : İnandıcırı. P’ye T ve q’ya F değeri ata.
Çözüm : İnandırıcı değil. Mümkün olan bütün doğruluk
değerlerini deneyin. Hiçbirinin, ifadeyi doğru yapmadığını
göreceksiniz.
Gösterim
Sudoku
• Sudoku puzzle 99 ızgara ile gösterilir ve bu ızgara
blok olarak bilinen 33 alt ızgaralardan oluşur. 81
hücrenin herbirine 1’den 9’a kadar sayılar atanır.
• Sudokunun amacı her bir sütunu, her bir satırı ve her
bir kutuyu her bir rakam sadece bir kez kullanılacak
şekilde 1’den 9’a kadar doldurmaktır.
• Örnek
Sudokunu İnandırıcılık Problemi Olarak
İfade Etmek
• p(i,j,n) önermesi, n sayısı i. Satır j. Sütunun
gösterdiği hücreye yazıldığı zaman doğru
olsun.
• Bu şekilde 99  9 = 729 önerme var.
• Örnek puzzle’da p(5,1,6) doğrudur fakat
p(5,j,6) j = 2,3,…9 için yanlıştır.
Sudokunu İnandırıcılık Problemi Olarak
İfade Etmek
• Herbir satır bütün sayıları içerir.
• Herbir sütun bütün sayıları içerir.
• Herbir 3x3 blok bütün sayıları içerir
Sudokunu İnandırıcılık Problemi Olarak
İfade Etmek
• Hiçbir hücre birden fazla sayı barındıramaz
• n, n’, i, ve j, herbiri 1 ile 9 arasında değişir ve
İnandırıcılık Problemlerinin Çözümü
• Sudoku bulmacasını çözmek için 729 tane önermenin
doğruluk değerlerini bulmalıyız.
• Doğruluk tablosu bulmak bir inandırıcılık problemi için her
zaman bir çözümdür. Ancak, büyük problemlerin çözümünde
kullanılması pratik olmaz.
Yüklemler (Predicates) ve
Niceleyiciler (Quantifiers)
Section 1.4
Önerme Mantığı Yeterli Değil!
• Örnek:
“Bütün insanlar ölümlüdür.”
“Socrates bir insandır.”
• Yani, “Socrates ölümlüdür?”
• Önerme mantığı ile ifade edilemez.
• Nesneler, özellikleri ve ilişkileri hakkında
konuşabileceğimiz bir dil gerekli.
Yüklemler Mantığına Giriş
• Yüklemler mantığı aşağıdaki yeni özellikleri
kullanır:
– Değişkenler: x, y, z
– Yüklemler: P(x), M(x)
– Niceleyiciler
• Önerme fonksiyonları basit önermelerin
genelleştirilmiş halidir.
– Değişkenler ve Yüklemler içerirler, ör:P(x)
– Değişkenler, kendi alanlarından gerçek değerler ile
değiştirilebilir.
Önerme Fonksiyonları
• Önerme fonksiyonlarının değişkenleri, değişkenlerin alabilecekleri
gerçek değerler ile değiştirildiğinde önerme fonksiyonları basit
önermeler haline gelir. (veya değişkenler nicelendirildiklerinde)
• P(x) ifadesi, P önerme fonksiyonunun x’deki değeri anlamına gelir.
• Örneğin, P(x) önerme fonksiyonu “x > 0” olsun ve x değişkeninin
alanı tam sayılar olsun. Böylece:
P(-3) false.
P(0) false.
P(3) true.
• Genellikle alan (domain) U ile gösterilir. Bu örnekteki U tam
sayılardı.
Önerme Fonksiyonları Örnekleri
• “x + y = z”, R(x, y, z) ile gösterilsin ve U (3 değişken için de) tam sayılar
olsun. Doğruluk değerlerini bulun:
R(2,-1,5)
Çözüm:
R(3,4,7)
Çözüm :
R(x, 3, z)
Çözüm :
• Şimdi “x - y = z”, Q(x, y, z) ile gösterilsin. U tamsayılar olsun. Doğruluk
değerlerini bulun:
Q(2,-1,3)
Çözüm :
Q(3,4,7)
Çözüm :
Q(x, 3, z)
Çözüm :
Önerme Fonksiyonları Örnekleri
• “x + y = z”, R(x, y, z) ile gösterilsin ve U (3 değişken için de) tam sayılar
olsun. Doğruluk değerlerini bulun:
R(2,-1,5)
Çözüm: F
R(3,4,7)
Çözüm :
R(x, 3, z)
Çözüm :
• Şimdi “x - y = z”, Q(x, y, z) ile gösterilsin. U tamsayılar olsun. Doğruluk
değerlerini bulun:
Q(2,-1,3)
Çözüm :
Q(3,4,7)
Çözüm :
Q(x, 3, z)
Çözüm :
Önerme Fonksiyonları Örnekleri
• “x + y = z”, R(x, y, z) ile gösterilsin ve U (3 değişken için de) tam sayılar
olsun. Doğruluk değerlerini bulun:
R(2,-1,5)
Çözüm: F
R(3,4,7)
Çözüm : T
R(x, 3, z)
Çözüm :
• Şimdi “x - y = z”, Q(x, y, z) ile gösterilsin. U tamsayılar olsun. Doğruluk
değerlerini bulun:
Q(2,-1,3)
Çözüm :
Q(3,4,7)
Çözüm :
Q(x, 3, z)
Çözüm :
Önerme Fonksiyonları Örnekleri
• “x + y = z”, R(x, y, z) ile gösterilsin ve U (3 değişken için de) tam sayılar
olsun. Doğruluk değerlerini bulun:
R(2,-1,5)
Çözüm: F
R(3,4,7)
Çözüm : T
R(x, 3, z)
Çözüm : Bu bir önerme değil
• Şimdi “x - y = z”, Q(x, y, z) ile gösterilsin. U tamsayılar olsun. Doğruluk
değerlerini bulun:
Q(2,-1,3)
Çözüm :
Q(3,4,7)
Çözüm :
Q(x, 3, z)
Çözüm :
Önerme Fonksiyonları Örnekleri
• “x + y = z”, R(x, y, z) ile gösterilsin ve U (3 değişken için de) tam sayılar
olsun. Doğruluk değerlerini bulun:
R(2,-1,5)
Çözüm: F
R(3,4,7)
Çözüm : T
R(x, 3, z)
Çözüm : Bu bir önerme değil
• Şimdi “x - y = z”, Q(x, y, z) ile gösterilsin. U tamsayılar olsun. Doğruluk
değerlerini bulun:
Q(2,-1,3)
Çözüm : T
Q(3,4,7)
Çözüm :
Q(x, 3, z)
Çözüm :
Önerme Fonksiyonları Örnekleri
• “x + y = z”, R(x, y, z) ile gösterilsin ve U (3 değişken için de) tam sayılar
olsun. Doğruluk değerlerini bulun:
R(2,-1,5)
Çözüm: F
R(3,4,7)
Çözüm : T
R(x, 3, z)
Çözüm : Bu bir önerme değil
• Şimdi “x - y = z”, Q(x, y, z) ile gösterilsin. U tamsayılar olsun. Doğruluk
değerlerini bulun:
Q(2,-1,3)
Çözüm : T
Q(3,4,7)
Çözüm : F
Q(x, 3, z)
Çözüm :
Önerme Fonksiyonları Örnekleri
• “x + y = z”, R(x, y, z) ile gösterilsin ve U (3 değişken için de) tam sayılar
olsun. Doğruluk değerlerini bulun:
R(2,-1,5)
Çözüm: F
R(3,4,7)
Çözüm : T
R(x, 3, z)
Çözüm : Bu bir önerme değil
• Şimdi “x - y = z”, Q(x, y, z) ile gösterilsin. U tamsayılar olsun. Doğruluk
değerlerini bulun:
Q(2,-1,3)
Çözüm : T
Q(3,4,7)
Çözüm : F
Q(x, 3, z)
Çözüm : Bu bir önerme değil
Bileşik İfadeler
• Mantıksal önermelerdeki bağlaçlar mantıksal yüklemlerde
de kullanılır.
• P(x) “x > 0,” olsun. Doğruluk değerlerini bulun.
P(3) ∨ P(-1)
P(3) ∧ P(-1)
P(3) → P(-1)
P(3) → P(-1)
Çözüm:
Çözüm :
Çözüm :
Çözüm :
• Değişken barındıran ifadeler önerme değildir ve dolayısıyla
doğruluk değerleri de yoktur. Örnek:
P(3) ∧ P(y)
P(x) → P(y)
• Niceleyiciler (quantifiers) kullanıldığı zaman bu ifadeler
önerme haline gelir.
Bileşik İfadeler
• Mantıksal önermelerdeki bağlaçlar mantıksal yüklemlerde
de kullanılır.
• P(x) “x > 0,” olsun. Doğruluk değerlerini bulun.
P(3) ∨ P(-1)
P(3) ∧ P(-1)
P(3) → P(-1)
P(3) → P(-1)
Çözüm: T
Çözüm :
Çözüm :
Çözüm :
• Değişken barındıran ifadeler önerme değildir ve dolayısıyla
doğruluk değerleri de yoktur. Örnek:
P(3) ∧ P(y)
P(x) → P(y)
• Niceleyiciler (quantifiers) kullanıldığı zaman bu ifadeler
önerme haline gelir.
Bileşik İfadeler
• Mantıksal önermelerdeki bağlaçlar mantıksal yüklemlerde
de kullanılır.
• P(x) “x > 0,” olsun. Doğruluk değerlerini bulun.
P(3) ∨ P(-1)
P(3) ∧ P(-1)
P(3) → P(-1)
P(3) → P(-1)
Çözüm: T
Çözüm : F
Çözüm :
Çözüm :
• Değişken barındıran ifadeler önerme değildir ve dolayısıyla
doğruluk değerleri de yoktur. Örnek:
P(3) ∧ P(y)
P(x) → P(y)
• Niceleyiciler (quantifiers) kullanıldığı zaman bu ifadeler
önerme haline gelir.
Bileşik İfadeler
• Mantıksal önermelerdeki bağlaçlar mantıksal yüklemlerde
de kullanılır.
• P(x) “x > 0,” olsun. Doğruluk değerlerini bulun.
P(3) ∨ P(-1)
P(3) ∧ P(-1)
P(3) → P(-1)
P(3) → P(-1)
Çözüm: T
Çözüm : F
Çözüm : F
Çözüm :
• Değişken barındıran ifadeler önerme değildir ve dolayısıyla
doğruluk değerleri de yoktur. Örnek:
P(3) ∧ P(y)
P(x) → P(y)
• Niceleyiciler (quantifiers) kullanıldığı zaman bu ifadeler
önerme haline gelir.
Bileşik İfadeler
• Mantıksal önermelerdeki bağlaçlar mantıksal yüklemlerde
de kullanılır.
• P(x) “x > 0,” olsun. Doğruluk değerlerini bulun.
P(3) ∨ P(-1)
P(3) ∧ P(-1)
P(3) → P(-1)
P(3) → P(-1)
Çözüm: T
Çözüm : F
Çözüm : F
Çözüm : T
• Değişken barındıran ifadeler önerme değildir ve dolayısıyla
doğruluk değerleri de yoktur. Örnek:
P(3) ∧ P(y)
P(x) → P(y)
• Niceleyiciler (quantifiers) kullanıldığı zaman bu ifadeler
önerme haline gelir.
Niceleyiciler
Charles Peirce (1839-1914)
• «Hepsi» ve «Birkaçı» kelimelerinin anlamlarını ifade
edebilmek için niceleyicilere ihtiyacımız var.
– “Bütün insanlar ölür.”
– “Bazı kedilerin tüyleri yoktur.”
• En önemli iki niceleyici:
– Evrensel niceleyici, “Hepsi için,” sembol: 
– Varlık niceleyicisi, “Vardır,” sembol: 
• x P(x) ve x P(x) olarak yazılırlar.
• x P(x), P(x)’in x’in alanındaki bütün x’ler için doğru olduğunu
önerir.
• x P(x), P(x)’in x’in alanındaki bazı x’ler için doğru olduğunu
önerir.
Evrensel Niceleyici
– x P(x), “her bir x için, P(x)” şeklinde okunur.
Örnekler:
1) P(x) “x > 0” ve U tam sayılar ise x P(x) false.
2) P(x) “x > 0” ve U pozitifi tam sayılar ise x P(x) true.
3) P(x) “x çifttir” ve U tam sayılar ise  x P(x) false.
Varlık Niceleyicisi
• x P(x), “bazı x’ler için, P(x)”, veya “vardır en
az bir tane x, P(x),” şeklinde okunur
Örnekler:
1. P(x) “x > 0” ve U tam sayılar ise x P(x) true. Ayrıca
eğer U pozitif tamsayılar ise yine true.
2. P(x) “x < 0” veU pozitif tamsayılar ise x P(x) false.
3. P(x) “x çifttir” ve U tamsayılar ise x P(x) true.
Tekillik Niceleyicisi
• !x P(x), P(x)’i doğru yapan bir ve yalnız bir x
değeri vardır.
• Örnek:
P(x) “x + 1 = 0” ve U tamsayılar ise !x P(x) true.
Niceleyiciler Hakkında
• Bahsedilen alan (domain) sınırlıysa, niceleme işlemini alandaki bütün
elemanların bir döngü ile kullanılması olarak düşünebiliriz.
• x P(x) ifadesini hesaplamak için alandaki bütün x’ler döngü ile
kullanılır.
– Eğer P(x)’in bütün adımları doğru ise x P(x) doğrudur.
– Eğer P(x)’in herhangi bir adımı yanlış ise x P(x) yanlıştır ve döngü sonlandırılır.
• x P(x) ifadesini hesaplamak için alandaki bütün x’ler döngü ile
kullanılır.
– Eğer en az bir adımda P(x) doğru ise x P(x) doğrudur ve döngü sonlandırılır.
– Eğer döngü P(x)’i doğru yapan en az bir tane x bulamadan sonlanırsa x P(x)
yanlıştır.
• Bahsedilen alan sonsuz olursa yine bu şekilde düşünebilir. Ancak bazı
durumlarda döngü sonlanmayabilir.
Niceleyicilerin Özellikleri
• x P(x) ve  x P(x) ifadelerinin doğruluk
değerleri P(x) ve U’ya bağlıdır.
• Örnek:
1. U pozitif tamsayılar ve P(x) “x < 2”, ise x P(x)
true, fakat  x P(x) false olur.
Niceleyicilerin Öncelik Sıraları
•  ve  niceleyicileri diğer mantıksal operatörlere
göre önceliklidir.
• Örneğin, x P(x) ∨ Q(x) ile (x P(x))∨ Q(x) aynı
anlamdadır.
• x (P(x) ∨ Q(x)) ise başka bir şeyi ifade eder.
Türkçe’den Mantık Diline Çeviri
Örnek 1: «Bu sınıftaki her öğrenci bir java dersi almıştır.»
Çözüm:
ilk olarak U alanına karar ver.
Çözüm 1: Eğer U sınıftaki bütün öğrenciler ise, J(x)
fonksiyonunu tanımla ve anlamı “x bir java dersi almıştır”
olsun ve bunu şu şekilde tercüme etx J(x).
Çözüm 2: Eğer U bütün insanlarsa, o zaman bir S(x)
fonksiyonu tanımla ve anlamı “x bu sınıftaki bir öğrencidir”
olsun ve şu şekilde tercüme et x (S(x)→ J(x)).
Türkçe’den Mantık Diline Çeviri
Örnek 2: «Bu sınıftaki bazı öğrenciler bir java dersi almıştır.»
Çözüm :
ilk olarak U alanına karar ver.
Çözüm 1: Eğer U sınıftaki bütün öğrenciler ise şu şekilde
tercüme et x J(x)
Çözüm 2: Eğer U bütün insanlarsa, o zaman şu şekilde
çevir x (S(x) ∧ J(x))
Socrates örneğine dönelim
• Önerme fonksiyonu Man(x), “x bir insandır” ve Mortal(x), “x
bir ölümlüdür.” olsun.
• İki temel önerme (aksiyom):
• Sonuç:
• Bunun ispatını sonra yapacağız.
Yüklem Mantığında Eşdeğerlik
• Yüklemler ve niceleyiciler içeren ifadeler ancak ve
ancak doğruluk değerleri aynıysa eşdeğerdir.
• S ≡T gösterimi S ve T mantıksal denktir
demektir.
• Örnek: x ¬¬S(x) ≡ x S(x)
Niceleyicileri «ve» ve «veya» olarak
düşünmek
• Eğer alan sınırlı ise, bir evrensel niceleyici önermesi, niceleyiciler
kullanmadan yazılan ve «ve» bağlacı ile bağlanan önermelere eşdeğerdir.
• Aynı şekilde, bir varlık niceleyici önermesi, niceleyiciler kullanmadan
yazılan ve «veya» bağlacı ile bağlanan önermelere eşdeğerdir.
• U 1,2, ve 3 tam sayılarından oluşsun:
• Bahsedilen alan sonsuz olursa yine bu şekilde düşünebilir. Ancak sonsuz
sayıda ifadeyi göstermek gerekir.
Nicelik İfadelerini Olumsuz Yapmak
• x J(x) ifadesini göz önünde bulunduralım
«Bu sınıftaki her öğrenci bir java dersi almıştır.»
J(x) “x bir java dersi almıştır” ve alan (domain) sınıftaki
öğrenciler olsun.
• Orijinal ifadeyi olumsuz yapmak «Bu sınıftaki her öğrenci bir
java dersi almıştır durumu böyle değildir»
• Bu, şunu gerektirir. «sınıfta java dersi almayan bir
öğrenci vardır.»
Sembolik olarak¬x J(x) ve x ¬J(x) mantıksal
olarak denktir.
Nicelik İfadelerini Olumsuz Yapmak
•  x J(x) ifadesini göz önünde bulunduralım
«Bu sınıfta, java dersini alan en az bir öğrenci vardır» J(x) “x
bir java dersi almıştır” ve alan (domain) sınıftaki öğrenciler
olsun.
• Orijinal ifadeyi olumsuz yapmak «Bu sınıfta, java dersini
alan en az bir öğrenci vardır durumu böyle değildir»
• Bu, şunu gerektirir. «Bu sınıftaki her bir öğrenci – daha
doğru Türkçe ile hiçbir öğrenci- java dersini almamıştır»
Sembolik olarak ¬ x J(x) ve x ¬J(x) mantıksal
olarak denktir.
De Morgan’ın Niceleyiciler Üzerindeki
Yasaları
• Niceleyicileri olumsuz yapma üzerine kurallar:
• Tablodaki kanıtlar şunu gerektirir:
• Bunlar Önemli. Kullanacaksınız!
Sistem Gereksinimi Belirleme Örneği
• Yüklem mantığı, bir sistemin yapması gereken işleri (gereksinimleri)
tanımlamakta kullanılabilir.
• Örneğin, aşağıdaki cümleleri mantıksal yüklemler haline çevirin:
– “1 MB’tan büyük her e-posta mesajı sıkıştırılacaktır.”
– “Eğer bir kullanıcı aktifse, en az bir ağ bağlantısı çalışacaktır.”
• Yüklemlere ve değişkenlerin alanlarına (domain) karar verin:
–
–
–
–
L(m, y), “E-posta mesajı m, y megabyte’tan büyüktür.” olsun
C(m) , “E-posta mesajı m sıkıştırılacaktır.” olsun
A(u), “u kullanıcısı aktif.” olsun
S(n, x), “Ağ bağlantısı n’nin durumu x”. olsun
• Böylece:
Lewis Carroll’un Örneği
Charles Lutwidge Dodgson
(AKA Lewis Caroll)
(1832-1898)
• İlk ikisi önerme, üçüncüsü ise sonuç.
1.
2.
3.
•
P(x), Q(x), ve R(x) sırası ile şu mantıksal yüklemler olsun: “x bir aslandır,”
“x sinirlidir,” ve “x kahve içer,”.
1.
2.
3.
•
“Bütün aslanlar sinirlidir.”
“Bazı aslanlar kahve içmez.”
“Bazı sinirli yaratıklar kahve içmez.”
x (P(x)→ Q(x))
x (P(x) ∧ ¬R(x))
x (Q(x) ∧ ¬R(x))
İspatını sonra yapacağız.
İç İçe Niceleyiciler
Section 1.5
İç İçe Niceleyiciler
• İç içe niceleyiciler kullanmak, Türkçe cümleleri göstermek
için kullanılabileceği gibi bilgisayar bilimindeki veya
matematikteki kavramları göstermek için de kullanılabilir.
• Örnek: “Her gerçek sayının bir tersi vardır”
x y(x + y = 0)
burada x ve y için alan (domain) gerçek sayılardır.
• İç içe kullanılan mantıksal fonksiyonları şu şekilde de
düşünebiliriz:
x y(x + y = 0) ifadesi şu şekilde düşünülebilir x Q(x). burada
Q(x) y P(x, y) ifadesidir ve P(x, y) (x + y = 0) ifadesidir.
İç İçe Niceleyiciler Hakkında
• İç İçe Döngüler
– xyP (x,y) ifadesinin doğru olduğunu görmek için, x’in herbir
değeri için:
• Her bir adımda y’nin değerlerini kullanan bir döngü kur.
• Eğer bir tane x ve y değer çifti için P(x,y) yanlışsa (false), x yP(x,y) ifadesi
de yanlıştır. İçteki ve dıştaki döngüleri sonlandır.
Eğer dıştaki döngü x’in bütün değerleri için çalıştıktan sonra bittiyse
x y P(x,y) ifadesi doğrudur.
– x yP(x,y) ifadesinin doğru olduğunu görmek için x’in herbir
değeri için :
• Her bir adımda y’nin değerlerini kullanan bir döngü kur.
• P(x, y) ifadesini doğru yapan bir x ve y çifti bulduğunda içteki döngüyü
bitir (dıştaki döngünün sonraki adımına geç).
• Eğer P(x, y) ifadesini doğru yapan bir y bulunamazsa dıştaki döngüyü
sonlandır vex yP(x,y) ifadesinin yanlış olduğunu göster.
Eğer dıştaki döngü x’in bütün değerleri için çalıştıktan sonra
bittiyse x y P(x,y) ifadesi doğrudur.
• Eğer değişkenlerin alanları sınırsız ise bu işlemi gerçekleştirmek
imkansızdır.
Niceleyicilerin Sırası
Örnek:
1. P(x,y) ifadesi “x + y = y + x.” olsun.
U ‘nun gerçek sayılar olduğunu düşünelim.
Böylece x yP(x,y) ve y xP(x,y) ifadeleri
aynı doğruluk değerlerine sahip olurlar.
1. Q(x,y) ifadesi “x + y = 0.” olsun.
U ‘nun gerçek sayılar olduğunu düşünelim.
Böylecex yQ(x,y) doğru, fakat y xQ(x,y)
yanlıştır.
Niceleyicilerin Sırası İle İlgili Örnekler
Örnek 1: U ‘nun gerçek sayılar olduğunu düşünelim,
ifade: P(x,y) : x ∙ y = 0
Aşağıdakilerin doğruluk değerlerini bulunuz:
1.
xyP(x,y)
Cevap:
2.
xyP(x,y)
Cevap :
3.
xy P(x,y)
Cevap :
4.
x  y P(x,y)
Cevap :
Niceleyicilerin Sırası İle İlgili Örnekler
Örnek 1: U ‘nun gerçek sayılar olduğunu düşünelim,
ifade: P(x,y) : x ∙ y = 0
Aşağıdakilerin doğruluk değerlerini bulunuz:
1.
xyP(x,y)
Cevap: False
2.
xyP(x,y)
Cevap :
3.
xy P(x,y)
Cevap :
4.
x  y P(x,y)
Cevap :
Niceleyicilerin Sırası İle İlgili Örnekler
Örnek 1: U ‘nun gerçek sayılar olduğunu düşünelim,
ifade: P(x,y) : x ∙ y = 0
Aşağıdakilerin doğruluk değerlerini bulunuz:
1.
xyP(x,y)
Cevap: False
2.
xyP(x,y)
Cevap : True
3.
xy P(x,y)
Cevap :
4.
x  y P(x,y)
Cevap :
Niceleyicilerin Sırası İle İlgili Örnekler
Örnek 1: U ‘nun gerçek sayılar olduğunu düşünelim,
ifade: P(x,y) : x ∙ y = 0
Aşağıdakilerin doğruluk değerlerini bulunuz:
1.
xyP(x,y)
Cevap: False
2.
xyP(x,y)
Cevap : True
3.
xy P(x,y)
Cevap : True
4.
x  y P(x,y)
Cevap :
Niceleyicilerin Sırası İle İlgili Örnekler
Örnek 1: U ‘nun gerçek sayılar olduğunu düşünelim,
ifade: P(x,y) : x ∙ y = 0
Aşağıdakilerin doğruluk değerlerini bulunuz:
1.
xyP(x,y)
Cevap: False
2.
xyP(x,y)
Cevap : True
3.
xy P(x,y)
Cevap : True
4.
x  y P(x,y)
Cevap : True
Niceleyicilerin Sırası İle İlgili Örnekler
Örnek 2: U ‘nun gerçek sayılar olduğunu düşünelim,
ifade: P(x,y) : x / y = 1
Aşağıdakilerin doğruluk değerlerini bulunuz:
1. xyP(x,y)
Cevap:
2. xyP(x,y)
Cevap :
3. xy P(x,y)
Cevap :
4. x  y P(x,y)
Cevap :
Niceleyicilerin Sırası İle İlgili Örnekler
Örnek 2: U ‘nun gerçek sayılar olduğunu düşünelim,
ifade: P(x,y) : x / y = 1
Aşağıdakilerin doğruluk değerlerini bulunuz:
1. xyP(x,y)
Cevap: False
2. xyP(x,y)
Cevap :
3. xy P(x,y)
Cevap :
4. x  y P(x,y)
Cevap :
Niceleyicilerin Sırası İle İlgili Örnekler
Örnek 2: U ‘nun gerçek sayılar olduğunu düşünelim,
ifade: P(x,y) : x / y = 1
Aşağıdakilerin doğruluk değerlerini bulunuz:
1. xyP(x,y)
Cevap: False
2. xyP(x,y)
Cevap : True
3. xy P(x,y)
Cevap :
4. x  y P(x,y)
Cevap :
Niceleyicilerin Sırası İle İlgili Örnekler
Örnek 2: U ‘nun gerçek sayılar olduğunu düşünelim,
ifade: P(x,y) : x / y = 1
Aşağıdakilerin doğruluk değerlerini bulunuz:
1. xyP(x,y)
Cevap: False
2. xyP(x,y)
Cevap : True
3. xy P(x,y)
Cevap : False
4. x  y P(x,y)
Cevap :
Niceleyicilerin Sırası İle İlgili Örnekler
Örnek 2: U ‘nun gerçek sayılar olduğunu düşünelim,
ifade: P(x,y) : x / y = 1
Aşağıdakilerin doğruluk değerlerini bulunuz:
1. xyP(x,y)
Cevap: False
2. xyP(x,y)
Cevap : True
3. xy P(x,y)
Cevap : False
4. x  y P(x,y)
Cevap : True
İki Değişkenli Niceleyiciler
İfade
Ne Zaman Doğru?
Ne zaman Yanlış?
P(x,y) ifadesi bütün x,y
çiftleri için doğruysa.
P(x,y) ifadesinin yanlış
olduğu bir x,y çifti varsa.
Bütün x’ler için en az bir y
P(x,y) ifadesini doğru
yapıyorsa.
En az bir tane x için bütün
y’ler P(x,y) ifadesini yanlış
yapıyorsa.
En az bir x için bütün y’ler
P(x,y) ifadesini doğru
yapıyorsa.
Bütün x’ler için en az bir y
P(x,y) ifadesini yanlış
yapıyorsa.
P(x,y) ifadesini doğru yapan Bütün x,y çiftleri için P(x,y)
en az bir x,y çifti varsa.
ifadesi yanlışsa.
İç İçe Niceleyicileri Türkçe’ye Çevirmek
Örnek 1: İfadeyi çevirin
x (C(x )∨ y (C(y ) ∧ F(x, y)))
burada C(x) “x’in bir bilgisayarı var,” ve F(x,y) is “x ve
y arkadaşlar,” ve x ve y için alan (domain) okuldaki
bütün öğrenciler.
Çözüm:
İç İçe Niceleyicileri Türkçe’ye Çevirmek
Örnek 1: İfadeyi çevirin
x (C(x )∨ y (C(y ) ∧ F(x, y)))
burada C(x) “x’in bir bilgisayarı var,” ve F(x,y) is “x ve
y arkadaşlar,” ve x ve y için alan (domain) okuldaki
bütün öğrenciler.
Çözüm: Okuldaki bütün öğrencilerin bir bilgisayarı var
veya bilgisayarı olan bir arkadaşı var.
Matematiksel İfadeleri Mantıksal
Yüklemlere Çevirmek
Örnek: “İki pozitif tam sayının toplamı her zaman
pozitiftir” ifadesini çevirin.
Çözüm:
Matematiksel İfadeleri Mantıksal
Yüklemlere Çevirmek
Örnek: “İki pozitif tam sayının toplamı her zaman
pozitiftir” ifadesini çevirin.
Çözüm:
1. İfadeyi “gerektirme” şeklinde ve alan (domain) açıkça
ifade edilen şekilde yeniden yazın
“Her bir tamsayı çifti için, eğer bu tamsayılar pozitifse, bu tamsayıların
toplamı da pozitiftir.”
Matematiksel İfadeleri Mantıksal
Yüklemlere Çevirmek
Örnek: “İki pozitif tam sayının toplamı her zaman
pozitiftir” ifadesini çevirin.
Çözüm:
1. İfadeyi “gerektirme” şeklinde ve alan (domain) açıkça
ifade edilen şekilde yeniden yazın
“Her bir tamsayı çifti için, eğer bu tamsayılar pozitifse, bu tamsayıların
toplamı da pozitiftir.”
2. x ve y değişkenlerini tanımla, alanı belirle:
“Bütün x ve y pozitif tam sayıları için, x + y pozitiftir.”
Matematiksel İfadeleri Mantıksal
Yüklemlere Çevirmek
Örnek: “İki pozitif tam sayının toplamı her zaman
pozitiftir” ifadesini çevirin.
Çözüm:
1. İfadeyi “gerektirme” şeklinde ve alan (domain) açıkça
ifade edilen şekilde yeniden yazın
“Her bir tamsayı çifti için, eğer bu tamsayılar pozitifse, bu tamsayıların
toplamı da pozitiftir.”
2. x ve y değişkenlerini tanımla, alanı belirle:
“Bütün x ve y pozitif tam sayıları için, x + y pozitiftir.”
3. Sonuç:
x  y ((x > 0)∧ (y > 0)→ (x + y > 0))
burada her iki değişkenin alanı bütün tam sayıları kapsar.
Türkçe’den Mantıksal İfadelere
Çevirmek
Örnek: İfadeyi çevirmek için niceleyiciler kullanın.
“Dünyadaki bütün havayolu firmaları ile en az bir kez
uçmuş bir bayan vardır.”
Çözüm:
Türkçe’den Mantıksal İfadelere
Çevirmek
Örnek: İfadeyi çevirmek için niceleyiciler kullanın.
“Dünyadaki bütün havayolu firmaları ile en az bir kez
uçmuş bir bayan vardır.”
Çözüm:
1. P(w,f) “w, f yolculuğuna çıkmıştır” ve Q(f,a) “f a’daki
bir uçuştur .”
Türkçe’den Mantıksal İfadelere
Çevirmek
Örnek: İfadeyi çevirmek için niceleyiciler kullanın.
“Dünyadaki bütün havayolu firmaları ile en az bir kez
uçmuş bir bayan vardır.”
Çözüm:
1. P(w,f) “w, f yolculuğuna çıkmıştır” ve Q(f,a) “f a’daki
bir uçuştur .”
2. w’nin alanı bütün bayanlar, f’nin alanı bütün uçuşlar ve
a’nın alanı bütün havayollarıdır.
Türkçe’den Mantıksal İfadelere
Çevirmek
Örnek: İfadeyi çevirmek için niceleyiciler kullanın.
“Dünyadaki bütün havayolu firmaları ile en az bir kez
uçmuş bir bayan vardır.”
Çözüm:
1. P(w,f) “w, f yolculuğuna çıkmıştır” ve Q(f,a) “f a’daki
bir uçuştur .”
2. w’nin alanı bütün bayanlar, f’nin alanı bütün uçuşlar ve
a’nın alanı bütün havayollarıdır.
3. Böylece ifade şu şekilde gösterilebilir:
w a f (P(w,f ) ∧ Q(f,a))
Türkçe’den Çeviri Örnekleri
Doğru yüklemleri seçin ve ifadeleri oluşturun.
Örnek 1: “Herkes bazılarını sever.”
Türkçe’den Çeviri Örnekleri
Doğru yüklemleri seçin ve ifadeleri oluşturun.
Örnek 1: “Herkes bazılarını sever.”
Çözüm : x y L(x,y)
Türkçe’den Çeviri Örnekleri
Doğru yüklemleri seçin ve ifadeleri oluşturun.
Örnek 1: “Herkes bazılarını sever.”
Çözüm : x y L(x,y)
Örnek 2: “Herkes tarafından sevilen en az bir kişi
vardır.”
Türkçe’den Çeviri Örnekleri
Doğru yüklemleri seçin ve ifadeleri oluşturun.
Örnek 1: “Herkes bazılarını sever.”
Çözüm : x y L(x,y)
Örnek 2: “Herkes tarafından sevilen en az bir kişi
vardır.”
Çözüm : y x L(x,y)
Türkçe’den Çeviri Örnekleri
Doğru yüklemleri seçin ve ifadeleri oluşturun
Örnek 1: “Herkes bazılarını sever.”
Çözüm : x y L(x,y)
Örnek 2: “Herkes tarafından sevilen en az bir kişi
vardır.”
Çözüm : y x L(x,y)
Örnek 3: “Bir kişiyi seven en az bir kişi vardır.”
Türkçe’den Çeviri Örnekleri
Doğru yüklemleri seçin ve ifadeleri oluşturun
Örnek 1: “Herkes bazılarını sever.”
Çözüm : x y L(x,y)
Örnek 2: “Herkes tarafından sevilen en az bir kişi
vardır.”
Çözüm : y x L(x,y)
Örnek 3: “Bir kişiyi seven en az bir kişi vardır.”
Çözüm : x y L(x,y)
Türkçe’den Çeviri Örnekleri
Doğru yüklemleri seçin ve ifadeleri oluşturun
Örnek 1: “Herkes bazılarını sever.”
Çözüm : x y L(x,y)
Örnek 2: “Herkes tarafından sevilen en az bir kişi
vardır.”
Çözüm : y x L(x,y)
Örnek 3: “Bir kişiyi seven en az bir kişi vardır.”
Çözüm : x y L(x,y)
Örnek 4: “Herkes kendini sever”
Türkçe’den Çeviri Örnekleri
Doğru yüklemleri seçin ve ifadeleri oluşturun
Örnek 1: “Herkes bazılarını sever.”
Çözüm : x y L(x,y)
Örnek 2: “Herkes tarafından sevilen en az bir kişi
vardır.”
Çözüm : y x L(x,y)
Örnek 3: “Bir kişiyi seven en az bir kişi vardır.”
Çözüm : x y L(x,y)
Örnek 4: “Herkes kendini sever”
Çözüm : x L(x,x)
İç İçe Niceleyicileri Olumsuz Yapmak
Örnek 1: Uçuş örneğini hatırlayın:
w a f (P(w,f ) ∧ Q(f,a))
Kısım 1: İfadeyi oluşturmak için niceleyiciler kullanın “Dünyadaki bütün
havayolu firmaları ile an az bir kez uçmuş bir bayan yoktur.”
Çözüm: ¬w a f (P(w,f ) ∧ Q(f,a))
Kısım 2: Şimdi, «değil» bağlacını ifadenin içerisine mümkün olduğu kadar
ilerletmek için De Morgan kurallarını kullanın.
Çözüm:
1. ¬w a f (P(w,f ) ∧ Q(f,a))
2. w ¬ a f (P(w,f ) ∧ Q(f,a))
De Morgan kuralı  için
3. w  a ¬ f (P(w,f ) ∧ Q(f,a))
De Morgan kuralı  için
4. w  a f ¬ (P(w,f ) ∧ Q(f,a))
De Morgan kuralı  için
5. w  a f (¬ P(w,f ) ∨ ¬ Q(f,a))
De Morgan kuralı ∧ için
Kısım 3: Sonucu tekrar Türkçe’ye Çevirebilir misin?
Çözüm: ?