MAT2033 · 1. hafta · propositional logic, predicates and quantifiers

Önermeler mantığı, yüklemler ve niceleyiciler

Bağlaçlar, doğruluk tablosu, mantıksal denklik kanunları ve ∀/∃ ile çeviri ve olumsuzlama. Vizenin ilk sorusu neredeyse her zaman buradan gelir.

propositionconnectiveconditionalbiconditionalexclusive ortruth tabletautologycontradictioncontingencylogical equivalenceDe Morgan's lawsconverseinversecontrapositivepredicatedomain of discourseuniversal quantifierexistential quantifiercounterexample

Ayrık matematiğin dili mantıktır. Bu hafta öğrendiğin semboller dönem boyunca her ispatta, her küme sorusunda, her algoritmada karşına çıkacak. Vizede bu konudan gelen sorular mekaniktir: doğruluk tablosu kur, iki ifadenin denk olduğunu kanunlarla göster, İngilizce cümleyi sembole çevir, niceleyicili bir ifadeyi olumsuzla. Kurallar azdır ama tamamen oturmaları lazım.

Altın kurallar:

$p \to q$ sadece $p$ doğru, $q$ yanlışken yanlıştır. Diğer üç satırın hepsi doğru.
Tablo sırasını hiç değiştirme. 3 değişkende $p$ : TTTTFFFF, $q$ : TTFFTTFF, $r$ : TFTFTFTF.
Her kanun adımında tek kanun kullan ve adını yaz. Hoca isim için puan verir.
“Bütün” ok ister, “bazı” ve ister. $\forall x\,(A \to B)$ , $\exists x\,(A \land B)$ .
Olumsuzlarken niceleyici döner: $\forall \leftrightarrow \exists$ , sonra içerisi olumsuzlanır.

Önerme ve bağlaçlar

Önerme (proposition): ya doğru (T) ya yanlış (F) olan bildirme cümlesi. “7 asaldır” önermedir (doğru). " $2 + 2 = 5$ " önermedir (yanlış). “Kapıyı kapat” ya da " $x + 1 = 3$ " önerme değildir: birincisi emir, ikincisinde $x$ belli olmadan doğru/yanlış söylenemez.

Önermeleri bağlaçlarla (connectives) birleştirirsin:

Sembol	Adı	Ne zaman doğru?
$\lnot p$	negation (değil)	$p$ yanlışken
$p \land q$	conjunction (ve)	ikisi de doğruyken
$p \lor q$	disjunction (veya, kapsayan)	en az biri doğruyken
$p \oplus q$	exclusive or (ya … ya …)	tam olarak biri doğruyken
$p \to q$	conditional (ise)	$p = T, q = F$ hariç her zaman
$p \leftrightarrow q$	biconditional (ancak ve ancak)	ikisi aynı değerdeyken

$p$	$q$	$p \to q$	$p \leftrightarrow q$	$p \oplus q$
T	T	T	T	F
T	F	F	F	T
F	T	T	F	T
F	F	T	T	F

Koşullu önerme neden böyle?

$p \to q$ bir söz gibidir. Hoca “Ödevi teslim edersen 10 puan veririm” diyor. Hoca ancak tek durumda yalan söylemiş olur: ödevi teslim ettin ( $p = T$ ) ve puanı alamadın ( $q = F$ ). Teslim etmediysen ( $p = F$ ) hoca ne yaparsa yapsın sözünü bozmuş sayılmaz, önerme doğru kalır. Buna “vacuously true” (boş yere doğru) denir.

TUZAK · $p$ yanlışsa $p \to q$ doğrudur. “Yanlış hipotezden her şey çıkar.” Tabloda $p = F$ olan satırlar otomatik T. Bunu bilmek hesabı yarıya indirir.

Çeviri kalıpları

Sınavın sevdiği kalıplar; hepsi $p \to q$ ile ifade edilir:

İngilizce	Sembol
if $p$ , then $q$ / $q$ if $p$ / $q$ whenever $p$	$p \to q$
$p$ only if $q$	$p \to q$
$p$ is sufficient for $q$ / $q$ is necessary for $p$	$p \to q$
$q$ unless $p$	$\lnot p \to q$ (yani $p \lor q$ )
$p$ if and only if $q$ / $p$ iff $q$	$p \leftrightarrow q$

“Only if” en çok karıştırılan kalıp. “Sınava girersin only if kimliğin varsa” = sınava girdiysen kimliğin kesin vardır: “girdin” $\to$ “kimliğin var”. Kimliğin olması girmeyi garanti etmez.

Converse, inverse, contrapositive

$p \to q$ için üç akraba:

converse: $q \to p$
inverse: $\lnot p \to \lnot q$
contrapositive: $\lnot q \to \lnot p$

Sadece contrapositive orijinale denktir. Converse ile inverse de birbirine denktir ama orijinale değil. “Yağmur yağarsa zemin ıslanır” doğru. Converse “zemin ıslaksa yağmur yağmıştır” yanlış olabilir (biri su dökmüştür). Contrapositive “zemin kuruysa yağmur yağmamıştır” ise orijinalle aynı bilgiyi verir.

Doğruluk tablosu kurma

Şablon:

Değişken say: $n$ değişken varsa $2^n$ satır.
Sütunları standart sırayla doldur (yukarıdaki altın kural 2).
İfadeyi içten dışa parçala, her parça için ara sütun aç.
Son sütuna bak: hepsi T ise tautology, hepsi F ise contradiction, karışıksa contingency.

Örnek. $(p \land \lnot r) \to (q \lor r)$

$p$	$q$	$r$	$\lnot r$	$p \land \lnot r$	$q \lor r$	sonuç
T	T	T	F	F	T	T
T	T	F	T	T	T	T
T	F	T	F	F	T	T
T	F	F	T	T	F	F
F	T	T	F	F	T	T
F	T	F	T	F	T	T
F	F	T	F	F	T	T
F	F	F	T	F	F	T

Son sütunda bir F var, geri kalanı T: contingency. Hızlı kontrol: ok sadece “sol T, sağ F” iken F olur. Sol tarafın T olduğu satırlar ( $p=T, r=F$ ) sadece 2. ve 4. satır; bunlardan sağ tarafı F olan yalnız 4. satır.

Mantıksal denklik (logical equivalence)

$A$ ve $B$ her satırda aynı değeri alıyorsa denktir: $A \equiv B$ . Başka bir deyişle $A \leftrightarrow B$ bir tautology’dir. İki yolla gösterirsin: doğruluk tablosu ya da kanun zinciri.

Kanun	Formül
Conditional	$p \to q \equiv \lnot p \lor q$
De Morgan	$\lnot(p \land q) \equiv \lnot p \lor \lnot q$ , $\lnot(p \lor q) \equiv \lnot p \land \lnot q$
Double negation	$\lnot\lnot p \equiv p$
Distributive	$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ , $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$
Negation	$p \lor \lnot p \equiv T$ , $p \land \lnot p \equiv F$
Identity	$p \land T \equiv p$ , $p \lor F \equiv p$
Domination	$p \lor T \equiv T$ , $p \land F \equiv F$
Idempotent	$p \lor p \equiv p$ , $p \land p \equiv p$
Commutative, associative	$p \lor q \equiv q \lor p$ , $(p \lor q) \lor r \equiv p \lor (q \lor r)$
Absorption	$p \lor (p \land q) \equiv p$ , $p \land (p \lor q) \equiv p$
Biconditional	$p \leftrightarrow q \equiv (p \to q) \land (q \to p)$

Zincir stratejisi: önce okları conditional kanunuyla $\lor$ ‘a çevir, sonra parantez önündeki $\lnot$ ‘leri De Morgan ile içeri it, $\lnot\lnot$ ‘leri sil, en son dağılma ve sadeleştirme.

Örnek 1. Show that $(p \to q) \lor (p \to r) \equiv p \to (q \lor r)$ .

(p → q) ∨ (p → r)
≡ (¬p ∨ q) ∨ (¬p ∨ r)        conditional law (twice)
≡ (¬p ∨ ¬p) ∨ (q ∨ r)        commutative and associative laws
≡ ¬p ∨ (q ∨ r)               idempotent law
≡ p → (q ∨ r)                conditional law   ∎

Örnek 2. Show that $\lnot(p \lor \lnot q) \lor (\lnot p \land \lnot q) \equiv \lnot p$ .

¬(p ∨ ¬q) ∨ (¬p ∧ ¬q)
≡ (¬p ∧ ¬¬q) ∨ (¬p ∧ ¬q)     De Morgan's law
≡ (¬p ∧ q) ∨ (¬p ∧ ¬q)       double negation law
≡ ¬p ∧ (q ∨ ¬q)              distributive law (ortak ¬p dışarı)
≡ ¬p ∧ T                     negation law
≡ ¬p                         identity law   ∎

İPUCU · Denk DEĞİL demek için tablo kurma. Tek bir satır bul, iki taraf farklı çıksın. “For $p = F, q = T$ the left side is T and the right side is F” cümlesi tam puan.

Yüklemler ve niceleyiciler

" $x > 3$ " bir önerme değil, çünkü $x$ belli değil. Buna yüklem (predicate) denir: $P(x)$ . $x$ ‘e değer verince önerme olur: $P(5)$ doğru, $P(1)$ yanlış. $x$ ‘in alabileceği değerler kümesine domain (domain of discourse) denir. Domain verilmeden niceleyicili bir ifadenin doğruluğu belirlenemez.

İfade	Anlamı	Ne zaman doğru?	Ne zaman yanlış?
$\forall x\, P(x)$	her $x$ için $P(x)$	domain’deki her eleman sağlıyorsa	tek bir karşı örnek (counterexample) varsa
$\exists x\, P(x)$	en az bir $x$ için $P(x)$	tek bir örnek varsa	hiçbir eleman sağlamıyorsa

Sonlu domain’de niceleyiciler büyük birer “ve”/“veya”dır. Domain $\{1, 2, 3\}$ ise $\forall x\,P(x) \equiv P(1) \land P(2) \land P(3)$ ve $\exists x\,P(x) \equiv P(1) \lor P(2) \lor P(3)$ . Bu yüzden niceleyicinin olumsuzlanması De Morgan’ın ta kendisidir:

$\lnot \forall x\, P(x) \equiv \exists x\, \lnot P(x) \qquad \lnot \exists x\, P(x) \equiv \forall x\, \lnot P(x)$

“Herkes geçti” yanlışsa, “geçemeyen biri var” demektir. “Hiç kimse geçmedi” demek değildir.

Domain etkisi: $\exists x\,(2x = 1)$ reel sayılarda doğru ( $x = \tfrac12$ ), tam sayılarda yanlış. Niceleyiciler $\lnot$ dışında bütün bağlaçlardan önce bağlanır: $\forall x\, P(x) \land Q(x)$ , $(\forall x\, P(x)) \land Q(x)$ demektir.

Çeviri: ok mu, ve mi?

Domain bütün insanlar, $A(x)$ : ” $x$ bir sporcu”, $S(x)$ : ” $x$ öğrenci”.

Cümle	Doğru	Yanlış (neden)
All athletes are students.	$\forall x\,(A(x) \to S(x))$	$\forall x\,(A(x) \land S(x))$ : “herkes sporcu ve öğrenci” der
Some athletes are students.	$\exists x\,(A(x) \land S(x))$	$\exists x\,(A(x) \to S(x))$ : sporcu olmayan biri yüzünden otomatik doğru olur
No athlete is a student.	$\forall x\,(A(x) \to \lnot S(x))$
Not all athletes are students.	$\exists x\,(A(x) \land \lnot S(x))$

İkinci satırdaki tuzağın sebebi koşullu önermenin boş doğruluğu: domain’de sporcu olmayan tek bir kişi $A(x) \to S(x)$ ‘i doğru yapar, cümle hiçbir şey söylememiş olur.

Çözümlü örnek: olumsuzlama

“Every student who studies passes.” $S(x)$ : studies, $P(x)$ : passes.

∀x (S(x) → P(x))                    orijinal
¬∀x (S(x) → P(x))                   olumsuzla
≡ ∃x ¬(S(x) → P(x))                 niceleyici döner
≡ ∃x (S(x) ∧ ¬P(x))                 ¬(a → b) ≡ a ∧ ¬b

İngilizcesi: “There is a student who studies but does not pass.” Olumsuzlamayı “Not every student who studies passes” diye bırakma; soru genelde “no negation in front of a quantifier” ister.

Sık yapılan hatalar

Yanlış düşünce	Doğrusu
$p$ yanlışsa $p \to q$ yanlıştır	Doğrudur. Ok sadece $T \to F$ iken yanlış
” $p$ only if $q$ ” = $q \to p$	$p \to q$
” $q$ unless $p$ ” = $p \to q$	$\lnot p \to q$
Converse orijinale denktir	Sadece contrapositive denktir
$\lnot(p \land q) \equiv \lnot p \land \lnot q$	$\lnot p \lor \lnot q$ ; $\land$ ile $\lor$ yer değiştirir
$\lnot \forall x\,P(x) \equiv \forall x\,\lnot P(x)$	$\exists x\,\lnot P(x)$ ; niceleyici de döner
“Some A are B” = $\exists x\,(A \to B)$	$\exists x\,(A \land B)$
“All A are B” = $\forall x\,(A \land B)$	$\forall x\,(A \to B)$
Birkaç örnek denedim, $\forall$ doğru	$\forall$ örnekle ispatlanmaz; ama tek karşı örnek onu yıkar
Domain’e bakmadan cevap vermek	Aynı ifade $\mathbb{R}$ ‘de doğru, $\mathbb{Z}$ ‘de yanlış olabilir

Kendini test et

Sınavdaki gibi İngilizce sorular. Önce kâğıt kalemle çöz, sonra cevabı aç.

Soru 1kolay

Let $p$ be true, $q$ be false and $r$ be true. Find the truth value of $(p \lor q) \to (\lnot r \land q)$ .

Cevabı göster

False

Sol taraf: $p \lor q = T \lor F = T$ . Sağ taraf: $\lnot r \land q = F \land F = F$ . Ok sadece $T \to F$ iken yanlış: $T \to F = F$ .

Soru 2kolay

Let $g$ : "you can use the gym", $s$ : "you are a student", $t$ : "you are staff". Write in symbols: "You can use the gym only if you are a student or staff."

Cevabı göster

g \to (s \lor t)

"p only if q" kalıbı $p \to q$ demektir: spor salonunu kullanıyorsan kesin öğrenci ya da personelsin. Sonuç kısmı $s \lor t$ . Ters yön ( $(s \lor t) \to g$ ) yazmak klasik hata.

Soru 3kolay

Write the converse and the contrapositive of: "If $n$ is divisible by 6, then $n$ is even." Which of the two is always equivalent to the original?

Cevabı göster

Converse: if n is even, then n is divisible by 6. Contrapositive: if n is not even, then n is not divisible by 6. The contrapositive.

$p$ : "6 divides n", $q$ : "n is even". Converse $q \to p$ (yön değişir), contrapositive $\lnot q \to \lnot p$ (yön değişir ve ikisi de olumsuzlanır). Sadece contrapositive orijinale denktir. Converse burada yanlış bile: $n = 4$ çift ama 6'ya bölünmez.

Soru 4orta

Construct the truth table of $(p \to q) \to (q \to p)$ . Is it a tautology, a contradiction or a contingency?

Cevabı göster

Contingency (false only when p = F, q = T)

Satırlar TT, TF, FT, FF. $p \to q$ : T, F, T, T. $q \to p$ : T, T, F, T. Dış ok: $T\to T = T$ , $F \to T = T$ , $T \to F = F$ , $T \to T = T$ . Son sütun TTFT: hem T hem F var, yani contingency.

Soru 5orta

In how many rows of its truth table is $(p \oplus q) \land (q \lor r)$ true?

Cevabı göster

8 satır. $p \oplus q$ sadece $p$ ile $q$ farklıyken T: TF* ve FT* satırları (4 satır). Bunlardan $q \lor r$ de T olanlar: TFT ( $r=T$ ), FTT, FTF ( $q=T$ ). TFF satırında $q \lor r = F$ . Toplam 3 satır.

Soru 6orta

Using the laws of logic (name each law), show that $\lnot(p \to q) \to p$ is a tautology.

Cevabı göster

It is equivalent to T, so it is a tautology.

$\lnot(p\to q) \to p \equiv \lnot\lnot(p \to q) \lor p$ (conditional law) $\equiv (p \to q) \lor p$ (double negation) $\equiv (\lnot p \lor q) \lor p$ (conditional law) $\equiv (p \lor \lnot p) \lor q$ (commutative + associative) $\equiv T \lor q$ (negation law) $\equiv T$ (domination law). Her adımda tek kanun, adıyla.

Soru 7zor

Are $p \to (q \to r)$ and $(p \to q) \to r$ logically equivalent? Justify.

Cevabı göster

No. For p = F, q = F, r = F the first is T and the second is F.

Denk değil demek için tek satır yeter. $p = F$ alınca $p \to (q \to r)$ otomatik T. Öbür tarafta $p \to q = T$ olur; $r = F$ seçersek $(p\to q) \to r = T \to F = F$ . Farklı değer, denk değiller. (Doğrulama: farklı çıkan satırlar FTF ve FFF.)

Soru 8kolay

Let $Q(x)$ be " $x^2 - 5x + 6 = 0$ ", the domain being all integers. Find the truth values of $\exists x\, Q(x)$ and $\forall x\, Q(x)$ .

Cevabı göster

∃x Q(x) is true, ∀x Q(x) is false

$x^2 - 5x + 6 = (x-2)(x-3)$ . $x = 2$ sağlar, o yüzden $\exists x\,Q(x)$ doğru (tek örnek yeter). $\forall$ için tek karşı örnek yeter: $x = 0$ için $6 \ne 0$ , yanlış.

Soru 9orta

The domain is $\{1, 2, 3, 4\}$ . Determine the truth values of (a) $\forall x\,(x \text{ is odd} \to x^2 < 10)$ and (b) $\exists x\,(x \text{ is even} \land x^2 > 15)$ .

Cevabı göster

(a) true, (b) true

(a) Tek olanlara bakmak yeter (çift olanlarda ok otomatik T): $1^2 = 1 < 10$ , $3^2 = 9 < 10$ . Hepsi tutuyor, doğru.
(b) Çift olan ve karesi 15'ten büyük biri lazım: $x = 4$ , $16 > 15$ . Doğru.

Soru 10orta

Let $M(x)$ : " $x$ misses practice" and $B(x)$ : " $x$ is benched", the domain being the players of a team. Express "Every player who misses practice is benched" in logic, then write its negation with no negation sign in front of a quantifier, and say it in English.

Cevabı göster

∀x (M(x) → B(x)); negation: ∃x (M(x) ∧ ¬B(x)), "Some player misses practice but is not benched."

"Every ... who ..." kalıbı $\forall$ ve ok ister: $\forall x\,(M(x) \to B(x))$ . Olumsuzlama: $\lnot\forall x\,(\dots) \equiv \exists x\,\lnot(M(x)\to B(x))$ , sonra $\lnot(a \to b) \equiv a \land \lnot b$ . Sonuç $\exists x\,(M(x) \land \lnot B(x))$ .

Soru 11zor

Let $S(x)$ : " $x$ is a student" and $L(x)$ : " $x$ is lazy", the domain being all people. Express "No student is lazy" in two equivalent ways, one using $\forall$ and one using $\exists$ .

Cevabı göster

∀x (S(x) → ¬L(x)) and ¬∃x (S(x) ∧ L(x))

"Hiçbir öğrenci tembel değil" = "tembel bir öğrenci yok": $\lnot\exists x\,(S(x) \land L(x))$ . Olumsuzlamayı içeri itince $\forall x\,\lnot(S(x)\land L(x)) \equiv \forall x\,(\lnot S(x) \lor \lnot L(x)) \equiv \forall x\,(S(x) \to \lnot L(x))$ . İkisi aynı şeyi söyler.

Soru 12zor

Determine the truth value of $\forall x\,(x^2 \ge x)$ when the domain is (a) all real numbers, (b) all integers.

Cevabı göster

(a) false, (b) true

(a) Karşı örnek $x = \tfrac12$ : $\tfrac14 \ge \tfrac12$ yanlış. Tek örnek $\forall$ 'ı yıkar.
(b) $x^2 - x = x(x-1)$ . Tam sayılarda $x \le 0$ ise iki çarpan da $\le 0$ , $x \ge 1$ ise ikisi de $\ge 0$ ; çarpım hep $\ge 0$ . Doğru. Aynı cümle, farklı domain, farklı cevap.

Doğrulama: Bütün doğruluk tabloları, denklikler ve niceleyici doğruluk değerleri node ile kaba kuvvetle (bütün satırlar / sonlu tanım kümesi ve -1000..1000 taraması) kontrol edildi (verify/MAT2033/01.mjs).

Deftere not kartı

p→q sadece T→F iken F. p↔q aynıysa T. p⊕q farklıysa T. p→q ≡ ¬p∨q ¬(p→q) ≡ p∧¬q p↔q ≡ (p→q)∧(q→p) De Morgan: ¬(p∧q) ≡ ¬p∨¬q ¬(p∨q) ≡ ¬p∧¬q "p only if q" = p→q "q if p" = p→q "q unless p" = ¬p→q "p sufficient for q" = p→q "q necessary for p" = p→q converse q→p, inverse ¬p→¬q, contrapositive ¬q→¬p (sadece bu denk) n değişken → 2^n satır; p: TTTTFFFF, q: TTFFTTFF, r: TFTFTFTF hepsi T tautology, hepsi F contradiction, karışık contingency Denk değil göstermek: farklı çıkan TEK satır yeter ∀: bir karşı örnek yanlış yapar. ∃: bir örnek doğru yapar. ¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x) "All A are B" = ∀x (A(x)→B(x)) "Some A are B" = ∃x (A(x)∧B(x)) Domain değişirse cevap değişir: ∃x(2x=1) R'de T, Z'de F