Mantık bilimi bilgisayar bilimlerinde oldukça geniş bir alana sahiptir. Mantık biliminde yer alan belli başlı kurallar vardır ve bu kurallar matematiksel ifadelerin net bir şekilde açıklanması için kullanılırlar. Bu kurallar, mantıksal devre tasarımı, programlama, programların doğrulanması ve simülasyon gibi birçok konuda kendine geniş bir yer bulmaktadır. Ayrık matematiğin en temel konularından biri de mantıktır. Ayrıca matematiksel ifadelerin ispatı da ayrık matematik konusu olarak değerlendirilir.
Önerme
İlk olarak mantığın temel kavramlarından ve kurallarından bahsedeceğiz. Bu kurallar zaten lisenin ilk yıllarında karşınıza çıkmış olan kurallardır. İlk olarak mantığın temel yapı taşı olan önerme kavramından başlayalım. Önerme (proposition), bir şeyin doğru veya yanlış olduğunu tanımlayan bildirimsel cümlelerdir. Örneğin aşağıdaki cümleler birer önermedir:
- Türkiye’nin başkenti Ankara’dır.
- 1 + 3 = 4
- 2 + 2 = 5
- Azerbaycan’ın başkenti Bakü değildir.
Buradaki ilk iki önerme doğru iken, son iki önerme yanlıştır. Şimdi de önerme olmayan şeylerden örnek verelim:
- Bugün nasılsın?
- Hava çok güzel.
- a + b = 3
- c + 9 = 5
Burada ilk iki cümlenin önerme olmamasının sebebi, cümlelerin bildirimsel (declarative) cümle olmamasındandır. Yani bu cümleler bir şeyin doğru olup olmadığını bildirmez. Son iki cümle ise ne doğru ne de yanlış olduğu için önerme olamaz. Önermeler ya doğru ya da yanlış olmalıdır. Biz oradaki değişkenlerin değerlerini bilmeden bu cümleler (veya denklemler) üzerinde doğruluk veya yanlışlık hakkında konuşamayız.
Önerme Değişkenleri
Bir önermenin yerini tutmak ve onunla daha kolay işlemler yapmak için x, y, z, p, q, r ve s gibi küçük harfler kullanılır. Bu harflere önerme değişkenleri (proposition variables) veya ifade değişkenleri (statement variables) adı verilir. Bir önermenin doğruluk değeri (truth value) ise o önermenin doğru (true) veya yanlış (false) olduğunun gösterimidir. Biz bu yazıda doğru olan doğruluk değerlerini T ile, yanlış olanları ise F ile göstereceğiz.
Önermelerden ve önermeler ile ilgili temel kavramlardan bahsettik. İşte bizim önermeli mantık (propositional logic) veya önermeli kalkülüs (propositional calculus) dediğimiz şey, mantık biliminin önermeler ile ilgilenen kısmıdır. Bu konuların temelleri 2300 yıl önce Yunan filozof Aristotle tarafından ortaya atılmıştır. Günümüzde kullanılan önermeli mantık ile ilgili temel kavramlar, İngiliz matematikçi George Boole tarafından 1854 yılında yazılan “The Laws of Thought (Düşüncenin Yasaları)” isimli kitaptan ortaya çıkmıştır.
Bileşik Önerme
Birçok matematiksel ifade bir ya da daha fazla önermenin bir araya gelmesiyle oluşturulur. Bileşik önerme (compound propositon) olarak adlandırılan bu önermeler varolan önermelerin mantıksal operatörler (logical operators) ile birleştirilmeleri ile oluşurlar. Mantıksal operatörler ayrıca bağlaç (connective) olarak da adlandırılırlar.
p bir önerme olmak üzere, bu önermenin olumsuzu ¬p veya p olarak gösterilir. Ben kolay yazım açısından ¬p gösterimini tercih edeceğim. Bu gösterim “p’nin değili” şeklinde okunur. p önermesinin dorğuluk değeri ne ise, ¬p önermesinin doğruluk değeri onun tersidir. Örneklerle açıklayalım:
- Mustafa’nın bilgisayarı Linux çalıştırır. (p)
- Mustafa’nın bilgisayarı Linux çalıştırmaz. (¬p)
Bir bileşik önermenin olası bütün kombinasyonlarının doğruluk değerini gösteren tabloya doğruluk tablosu (truth table) adı verilir. Örneğin ¬p ifadesinin doğruluk tablosu şu şekildedir:
| p | ¬p |
|---|---|
| T | F |
| F | T |
Burada görüldüğü gibi eğer p önermesi T olursa, ¬p önermesi F olur. Yine p önermesi F olursa, ¬p önermesi T olur. Tablonun en üst satırı ise sıradan veya bileşik önermeyi göstermektedir. Bu şekilde bir bileşik önermenin olası bütün durumları rahat bir şekilde görülebilir. Az önceki örnekteki ¬ simgesine olumsuzlama operatörü (negation operator) adı verilir ve başına koyulduğu ifadenin sonucunun tam tersi çıkmasını sağlar.
Temel Mantıksal Operatörler
p ve q birer önerme olmak üzere, p ve q önermelerinin birleşimi (conjunction) p ∧ q olarak gösterilir ve bu yeni önerme "p ve q" olarak okunur. Bu önermenin sonucu ancak p ve q önermelerinin her ikisi de doğru olduğu zaman doğru olur. Aksi takdirde diğer durumlarda yanlış olur.
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Aynı şekilde p ve q önermelerinin kesişimi (disjunction) p ∨ q olarak gösterilir ve bu yeni önerme "p veya q" olarak okunur. Bu önermenin sonucu ise p ve q önermelerinden her ikisi de yanlış olduğunda yanlış olur. Diğer durumlarda doğru olur.
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
"Çorba mı alacaksınız yoksa salata mı?" gibi bir cümleyi incelediğimizde soruyu alan kişinin ikisinden birini seçme şansı olduğunu görürsünüz. Bu durumda hiç birini seçmemesi veya ikisini birden seçmesi yanlış olacaktır. "p ∨ q" kesişiminin doğruluk tablosuna baktığımızda iki durum da doğru kabul edildiğinde de sonuç doğru çıkıyor. Bu cümledeki gibi bazı durumlarda ise sadece biri doğru olduğunda doğru, ikisi de doğru veya yanlış olduğunda ise yanlış sonuç üretiliyor.
Klasik kesişim işlemine bu durum uymamakta, bunun için farklı bir mantıksal operatör gerekmektedir. Az önceki tabloda görüldüğü gibi doğruluk değerlerine sahip olan VEYA işlemine içermeli VEYA (inclusive or) adı verilir. Bir de sadece bir önermenin doğru olduğu durumda doğru olan bir VEYA işlemi vardır. Buna ise dışlamalı VEYA (exclusive or) adı verilir. Dışlamalı VEYA p ⊕ q şeklinde gösterilir. Dışlamalı VEYA’nın doğruluk tablosu şu şekildedir:
| p | q | p ⊕ q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
Bağlaçları buradaki gibi büyük yazarak belirteceğiz. En son bu bağlaçları ve işlemleri nasıl okuyacağımıza dair bir tablo veririm. Dışlamalı VEYA işlemine ÖZEL VEYA da denmektedir. Bununla ilgili bir örnek verelim:
- Sınıftaki öğrenciler veri yapıları veya kriptografi derslerinden birini alabilir. (ÖZEL VEYA)
- Bugün günlerden Cuma veya bugün hava yağmurlu. (VEYA)
Koşullu Önermeler
Buraya kadar en temel 4 mantıksal işlemi görmüş olduk. Şimdi biraz daha fazlasına bakalım. p ve q birer önerme olmak üzere p → q işlemine koşullu önerme (conditional statement) adı verilir ve "eğer p gerçekleşirse, q olur" şeklinde okunur. Koşullu önerme yanlızca p önermesinin doğru, q önermesinin yanlış olduğu durumda yanlış olur. Diğer bütün durumlarda doğrudur.
Koşullu önermedeki p hipotez (hypothesis), temel dayanak (premise) ve öncül (antecedent) gibi isimler ile adlandırılırken; q sonuç (conclusion) ve netice (consequent) gibi isimler ile adlandırılır. Koşullu önermeler bazen çıkarım (implication) olarak da adlandırılırlar.
Buradaki temel mantık p önermesi doğru ise q önermesinin de doğru olduğu sonucuna varmaktır. Fakat p önermesi yanlış ise q önermesi anlamsız bir şekilde doğru kabul edilir. Buradaki olayı programlamadaki "if-else" yapısı ile karıştırmayın. Şimdi birkaç örnek verelim:
- Eğer final notum 90’ın üzerinde ise bu dersten AA düşer.
- Eğer köpeklerin kanatları varsa, köpekler uçabilir.
Gördüğünüz gibi ilk önerme doğru ise ikinci önermenin de mutlaka doğru olması gerekir. Fakat ilk önerme yanlış ise ikinci önermenin doğru veya yanlış olduğunun bir önemi kalmaz. Şimdi şu örnekle biraz daha pekiştirmeye çalışalım:
- Eğer seçilirsem, vergileri azaltacağım.
Yukarıdaki sözü bir politikacının seçim vaatlerinde bulunurken söylediğini düşünelim. Eğer bu politikacı seçilirse, halka vergileri azaltacağına dair bir söz verdiği için bunu gerçekleştirmesi beklenir. Eğer bunu gerçekleştirirse doğru bir şey yapmış olur. Fakat bunu gerçekleştirmezse yanlış bir şey yapmış olur ve halkın güvenini kaybeder.
Bir de politikacının seçilmediği duruma bakalım. Eğer politikacı seçilmezse, halk ondan vergileri düşürmesini beklemez. Düşürüp düşürmemek tamamen ona kalmıştır. Belki de seçilmeden de bunu yapacak gücü vardır ve vergileri düşürebilir. Belki de düşüremez. Fakat düşürse de düşürmese de halk tarafından doğru kabul edilir. İşte koşullu önermenin mantığı da buna benzemektedir.
Koşullu önermenin 3 farklı durumu olabilir ve bunların kendilerine özel isimleri vardır. Bir "p → q" önermesi için aşağıdaki önermeler tanımlanabilir:
- Karşıt (Converse) : q → p
- Ters (Inverse) : ¬p → ¬q
- Karşıt ters (Contrapositive) : ¬q → ¬p
Bir koşullu önermenin kendisi ile karşıt tersi birbirine eşittir. Bu üç özel durumun farklı kullanım alanları vardır. Bu arada iki önermenin birbirine eşit olması için doğruluk tablosundaki sonuçlarının birbirine eşit olması gerekmektedir. Yani bütün kombinasyonları birbirine eşit olmalıdır. Bir koşullu önermenin, onun tersinin, karşıtının ve karşıt tersinin doğruluk tablosunu şu şekilde gösterebiliriz:
| p | q | p → q | ¬p → ¬q | q → p | ¬q → ¬p |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | T | T | F |
| F | T | T | F | F | T |
| F | F | T | T | T | T |
Doğruluk tablsoundan göreceğiniz gibi bir koşullu ifadenin karşıtı ile tersi biribirine eşitken, aynı zamanda kendisi ile karşıt tersi de birbirine eşittir.
İki Koşullu Önermeler
Şimdi kalan son operatörümüzü inceleyelim. p ve q birer önerme olmak üzere, p ↔ q önermesi iki koşullu önerme (biconditional statement) olarak adlandırılır ve "p ancak ve ancak q ise" olarak okunur. Bazı durumlarda bir önerme doğru olduğunda diğerinin de doğru, yanlış olduğunda ise diğerinin de yanlış olmasını isteriz. İşte bu operatör tam da bu durumlarda kullanılır. İki koşullu önermelerde, her iki taraf da doğru veya yanlış olduğunda önermenin sonucu doğru çıkar. Diğer durumlarda yanlış çıkar. Şimdi örneğimize geçelim:
- p : Uçağa binebilirsin.
- q : Bilet aldın.
- p ↔ q : Ancak ve ancak bilet aldığın zaman uçağa binebilirsin.
Kendi kendini açıklayan bir örnek ile karşı karşıyayız. İki önermenin de doğru olduğu zaman sonuç da doğru olur. Yani bilet alırsan uçağa da binebilirsin. Eğer binemediysen burada bir yanlışlık vardır. Aynı şekilde uçağa binebilirsen bilet almış olman gerekir. Eğer almadan bindiysen burada yine bir yanlışlık vardır. İki koşullu önermenin doğruluk tablosunu çıkardığımızda her şey açığa çıkacaktır:
| p | q | p ↔ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
Bütün operatörleri inceledikten sonra, bileşik önermelerin doğruluk tablosunun nasıl çıkaracağımıza bakalım. "(p ∨ ¬q) → (p ∧ q)" bileşik önermesini ele alalım ve doğruluk tablosunu çıkaralım:
| p | q | ¬q | p ∨ ¬q | p ∧ q | (p ∨ ¬q) → (p ∧ q) |
|---|---|---|---|---|---|
| T | T | F | T | T | T |
| T | F | T | T | F | F |
| F | T | F | F | F | T |
| F | F | T | T | F | F |
Adım adım gittiğinizde iş oldukça kolaylaşır. Bu arada eğer elinizde 2 tip önerme varsa, doğruluk tablosunda 4 satır çıkar. Eğer n tane önermeniz varsa, doğruluk tablosunda 2n tane satır, yani kombinasyon çıkar.
Operatör Önceliği
Peki hangi işlemi hangi sıra ile yapacağımızı nasıl bileceğiz? Matematikteki cebirsel işlemlerde olduğu gibi burada da parantez, önceliği kendine kaydırmaktadır. Yine sıradan cebirsel işlemlerde, çarpma ve bölme işlemlerinin toplama ve çıkarmaya üstün olduğunu biliyoruz. Önermeli mantıkta da operatörler birbirlerine göre üstündürler. Bu üstünlükleri şu şekilde gösterelim:
| Operatör | Operatör Adı | Öncelik Seviyesi |
|---|---|---|
| ¬ | DEĞİL | 1 |
| ∧ | VE | 2 |
| ∨ | VEYA | 3 |
| → | İSE | 4 |
| ↔ | ANCAK VE ANCAK | 5 |
Gördüğünüz gibi ilk başta DEĞİL operatörü işleme alınırken en son ANCAK VE ANCAK operatörü işleme alınmaktadır. Böylelikle operatörlerin yazılarımda kullanacağım isimlerini de vermiş oldum. Tabloda verilmeyen ÖZEL VEYA operatörünün ise önceliği VEYA ile aynı kabul edilir.
Önermeli Mantığın Uygulaması
Son olarak bilgisayardaki bitler ile önermeli mantık arasındaki ilişkiye değinmek istiyorum. Ünlü istatistikçi John Tukey 1946 yılında bit kavramını terminolojiye kazandırmıştır. Bilgisayarlarda sıklıkla duyduğumuz bit, binary digit (ikilik rakam) sözcüklerinin kısaltılmış halidir. İsminin geldiği yerden anlayacağınız gibi bir bit sadece 0 veya 1 olabilir.
Önermeli mantığa göre yorumlarsak 0 değeri yanlışı (F), 1 değeri ise doğruyu (T) belirtmektedir. Değeri ya 0’a ya da 1’e eşit olabilen değişkenlere boolean değişkeni (boolean variable) adı verilir. Dolayısı ile bit de bir boolean değişkenidir.
Bilgisayardaki bit işlemleri (bit operations) önermeli mantıktaki bağlaçlarla doğrudan ilgilidir. Bit String’i (bit string) dediğimiz şey ise bir veya birden fazla bite sahip olan String’lere verilen isimdir. Örneğin "0010101" bir bit String’idir. Bir bit String’i üzerinde mantıksal operatörler ile yapılabilecek işlemler yapılabilir. Örnekler:
| Mantıksal işlem | Bir String’i |
|---|---|
| x | 100101 |
| y | 001110 |
| x ∧ y | 000100 |
| x ∨ y | 101111 |
| x ⊕ y | 101011 |
Gördüğünüz gibi sırasıyla işlemler yapılıp sonuç üretilmektedir. İlk bit ile ilk bit işleme sokulur, ikinci ile ikinci ve bu böyle devam eder. Bitsel işlemlerde en çok bu üç operatör kullanılır ve bitsel işlemlerde kullandığımız için artık onlara bitsel VE (bitwise AND), bitsel VEYA (bitwise OR) ve bitsel ÖZEL VEYA (bitwise XOR) adı verilir.
Bu yazıda temel önermeli mantık operatörlerini gördük. Bunların uygulama alanları ile ilgili ayrı bir bölüm açmayacağım. Çünkü örneğin “Sayısal Mantık Tasarımı” dersinde önermeli mantığı kullanırken zaten baştan neyin ne olduğuna değiniliyor. Yani siz önermeli mantığı bilin, kullanacağınız alana göre pekiştirme yaparsınız.
