Doğruluk tablosu

Doğruluk tablosu, mantıkta, özellikle Boole cebiri ve Boole fonksiyonları ile ilişkili olarak, fonksiyon değişkenlerinin bütün kombinasyonları için mantıksal ifadenin değerini hesaplamakta kullanılan bir matematiksel tablo.

Pratikte bir doğruluk tablosu, her giriş değişkeni için bir sütun (örneğin, A ve B) ve tabloda gösterilmek istenen mantıksal ifadenin, mümkün olan tüm çıkışlarını gösteren bir sütundan oluşur (örneğin, A XOR B). Doğruluk tablosunun her satırı, girdilerin muhtemel kombinasyonlarından birini (örneğin, A=doğru B=yanlış) ve fonksiyonun bu girdiler için doğruluk değerini içerir. Ludwig Wittgenstein, Tractatus Logico-Philosophicus adlı eseriyle çoğu zaman bu kavramı ortaya koyan kişi olarak anılır; bilinen ilk örnek ise Charles Sanders Peirce'ün 1893 tarihli tablosudur.

Emil Post 1921'de, doğruluk tablosu kavramının William Stanley Jevons ile John Venn'in çalışmalarında belirgin bir biçim kazandığını ve temelinin George Boole'un mantıksal fonksiyonları açma formülüne dayandığını yazdı. Irving Anellis'e göre adı bilinen bir yazara ait, bugünkü biçimdeki ilk doğruluk tablosu Charles Sanders Peirce'ün 1893'te yazdığı An Outline Sketch of Synechistic Philosophy başlıklı el yazmasında, bir önerme ve onun değili için kurduğu tablodur. Anellis, bu tablonun Post, Wittgenstein ve Łukasiewicz'in 1920-1922 arasındaki tablolarından ve Bertrand Russell'ın 1912 tarihli tablosundan önce geldiğini belirtir. Peirce, üç değerli önerme mantığını da Łukasiewicz ile Post'tan en az on yıl önce kurdu.

1997'de John Shosky, Russell'ın 1912'de verdiği bir dersin daktilo dökümündeki bir sayfanın arkasında doğruluk tablosu matrisleri buldu; değil işleminin matrisi Russell'ın, gerektirme matrisi ise Wittgenstein'ın el yazısıydı. Wittgenstein, 1921'de Almanca, 1922'de İngilizce yayımlanan Tractatus Logico-Philosophicusta önermelerin doğruluk olanaklarını doğru ve yanlış değerlerinden oluşan satırlarla gösterdi ve iki önermenin bütün doğruluk fonksiyonlarını tek bir şemada sıraladı. Stanford Felsefe Ansiklopedisi'ne göre Wittgenstein bu eserde Frege'nin mantığını, sonradan doğruluk tablosu diye anılacak biçimde sundu. Aynı yıl Post, bir fonksiyonun değişkenlerinin 2ⁿ olası doğruluk düzeninin her birine bir doğruluk değeri bağlayan ilişkiye doğruluk tablosu (truth-table) adını verdi; doğru için +, yanlış için − simgesini kullandı.

Tam bir doğruluk tablosunda ifadedeki her önerme harfi için bir sütun vardır ve n farklı harf için tablo 2ⁿ satırdır: beş harf 32, altı harf 64 satır gerektirir. Giriş sütunları düzenli bir biçimde doldurulur: en sağdaki harfin sütununda D ile Y her satırda yer değiştirir, bir soldakinde ikişer, onun solundakinde dörder satırlık öbekler hâlinde değişir; böylece bütün kombinasyonlar birer kez yazılmış olur.

Bileşik bir ifadenin değeri içten dışa doğru hesaplanır: önce en içteki alt ifadelerin sütunları doldurulur, sonra onları birleştiren bağlacın sütunu. Ara sütunlar yalnızca hesabı düzenli tutmaya yarar; ifadenin doğruluk değerini ana bağlacın altındaki sütun verir. Örneğin (p ∧ q) → r ifadesinde önce p ∧ q sütunu, ardından bu sütunla r sütunundan koşullu önerme sütunu hesaplanır.

Mantıksal özdeşlik, bir mantıksal değer (genellikle bir önerme), doğru ise doğru, yanlış ise yanlış değerini üreten işlemdir.

Mantıksal tümleme, bir mantıksal değer, genellikle bir önerme, doğru ise yanlış, yanlış ise doğru değerini üreten bağlaçtır.

DEĞİL p işlemi ¬p, Np, Fpq ya da ~p şeklinde de gösterilebilir.

Klasik mantıkta bir önermenin tümlemesinin tümlemesi kendisine eşittir: ¬¬p, p ile eşdeğerdir. Tek değişkenli dört doğruluk fonksiyonu vardır: ikisi girişe bakmadan hep doğru ya da hep yanlış verir, biri mantıksal özdeşliktir, dördüncüsü tümlemedir. Bunlardan anlamca karşıtlık bildiren tek işlem tümlemedir.

İki değişkenin (p, q) oluşturabileceği 16 doğruluk fonksiyonunun tamamı, her satırda bir fonksiyon olacak biçimde tabloda verilmiştir; dört değer sütunu fonksiyonun dört giriş kombinasyonundaki çıkışını gösterir.

Mantık işlemleri Venn şeması kullanılarak da gösterilebilir.

Mantıksal ve, iki mantıksal değerin, genellikle iki önerme, ikisi de doğru olduğu takdirde doğru, diğer hallerde yanlış değerini üreten bağlaçtır.

p VE q işlemi p ∧ q, Kpq, p & q veya p ⋅ {\displaystyle \cdot } q şeklinde de gösterilebilir.

Tabloda görüldüğü gibi p ve q doğru iken ve işlemi p ∧ q doğru, diğer tüm ihtimallerde p∧q yanlıştır. Başka bir deyişle p doğruysa p ∧ q değeri q'ya, p yanlışsa p'ye eşittir.

VE işleminin değişme (p ∧ q ≡ q ∧ p) ve birleşme ((p ∧ q) ∧ r ≡ p ∧ (q ∧ r)) özellikleri vardır; bu yüzden ikiden çok önerme parantez gözetmeden birleştirilebilir. Bir önermenin kendisiyle VE işlemine girmesi onu değiştirmez: p ∧ p ≡ p. Bu özelliğe etkisizlik denir. Sayısal devrelerde bu işlemi VE kapısı gerçekleştirir.

Mantıksal veya iki mantıksal değerin, genellikle iki önerme, ikisinden en az biri doğru olduğu takdirde doğru, diğer hallerde yanlış değerini üreten bağlaçtır.

p VEYA q işlemi p ∨ q, Apq, p || q veya p + q şeklinde de gösterilebilir.

Mantıktaki ∨ her zaman kapsayan veyadır: iki önermeden en az biri doğruysa sonuç doğrudur, ikisinin birden doğru olduğu durum da buna girer. Gündelik dilde "veya" bazen ikisinin birlikte doğru olmasını dışlayacak biçimde kullanılır; bu okumanın mantıktaki karşılığı dışlayıcı veyadır. Stanford Felsefe Ansiklopedisi'ne göre dışlayıcı okuma sözcüğün kendi anlamından değil kullanıldığı bağlamdan doğar. ∨ simgesine benzer bir işaret ilk kez Leibniz'in 1679 tarihli bir el yazmasında görülür ve büyük olasılıkla Latincede "veya" anlamına gelen vel sözcüğünün kısaltmasıdır. VEYA da VE gibi değişme ve birleşme özelliklerine sahiptir.

Koşullu önerme, iki mantıksal değerden, ilkinin doğru, ikincisinin yanlış olduğu tek durumda yanlış değeri veren bağlaçtır.

p ise q işlemi p⇒q ya da Cpq olarak da gösterilebilir.

p→q, ¬p∨q ifadesine eşdeğerdir. Koşullu önerme yalnız öncül doğru, sonuç yanlış olduğunda yanlıştır; öncül yanlışsa sonuç ne olursa olsun önerme doğru sayılır. Yanlış öncüllü koşulluların hep doğru çıkması gündelik dildeki "ise" kullanımıyla her zaman örtüşmez ve mantıkta bir paradoks olarak tartışılır. p → q, ¬q → ¬p ile eşdeğerdir; ancak q → p ile genel olarak eşdeğer değildir.

İki yönlü koşullu önerme iki mantıksal değerin, ikisi de doğru veya ikisi de yanlış olması halinde doğru, diğer durumlarda yanlış değeri veren bağlaçtır.

p XNOR q işlemi p ↔ q, Epq, p = q ya da p ≡ q olarak da gösterilebilir.

p ↔ q'nun sonucu, p ve q aynı mantıksal değerdeyse doğru, farklı ise yanlıştır. İki yönlü koşullu önerme, koşullunun iki yönünün birlikte söylenmesidir: p ↔ q, (p → q) ∧ (q → p) ile eşdeğerdir. İki değişkenli durumda XNOR işlemiyle aynıdır. Bu yüzden sayısal devrelerde bir XNOR kapısı iki biti karşılaştıran bir eşitlik denetleyicisi olarak kullanılır.

Dışlayıcı veya iki mantıksal değerin, genellikle iki önerme, ikisinden biri doğru olduğu takdirde doğru ancak ikisi de doğru veya yanlış ise yanlış değerini üreten bağlaçtır.

p XOR q işlemi p ⊕ q, Jpq ya da p ≠ q şeklinde de gösterilebilir.

p XOR q, (p ∧ ¬q) ∨ (¬p ∧ q) olarak da yazılabilir. Bilgisayar biliminde dışlayıcı veya çoğu zaman 2'ye göre toplama (modüler aritmetik) olarak ele alınır. Değişme ve birleşme özellikleri vardır; ikiden çok girişte sonuç, doğru olan girişlerin sayısı tekse doğrudur. Bu özellik toplayıcılarda ve eşlik bitinin üretilip denetlenmesinde kullanılır. Bir önermenin kendisiyle dışlayıcı veyası hep yanlıştır (p ⊕ p ≡ Y), yanlışla dışlayıcı veyası ise kendisine eşittir (p ⊕ Y ≡ p).

Mantıksal vedeğil iki mantıksal değerin, genellikle iki önerme, ikisi de doğru ise yanlış değerini üreten bağlaçtır. Başka bir deyişle değerlerden en az biri yanlış ise doğru üretir.

p NAND q işlemi p ↑ q, Dpq veya p | q şeklinde de gösterilebilir.

VE DEĞİL (NAND) işlemi, VE ile DEĞİL işlemlerinin birleşiminden oluşur. VE DEĞİL tek başına bütün doğruluk fonksiyonlarını kurmaya yeter: VE, VEYA ve DEĞİL işlemlerinin hepsi yalnızca VE DEĞİL ile yazılabilir. İki değişkenli bağlaçlar arasında bu özelliği taşıyan yalnızca VE DEĞİL ile VEYA DEĞİL'dir. Sayısal tasarımda bu yüzden ikisine evrensel kapı denir. CMOS teknolojisinde VE DEĞİL kapıları VEYA DEĞİL kapılarından hızlıdır.

Dik çizgi simgesi Henry M. Sheffer'in adıyla Sheffer çizgisi diye anılır. Sheffer 1913'te Boole cebrini tek bir işlemle beş eşitlik üzerine kurdu ve "Boole cebri" adını da bu makalede kullandı. Sheffer bu işlem olarak aslında VEYA DEĞİL'i kullanmıştı; çizgiyi VE DEĞİL için kullananlar Whitehead ile Russell oldu. Charles Sanders Peirce aynı sonuca yaklaşık otuz yıl önce ulaşmış ama yayımlamamıştı; Edward Stamm da sonucu Sheffer'den iki yıl önce yayımlamıştı.

Ve işleminin değili: ¬(p∧q) ya da değillerin veyası: (¬p)∨(¬q) olarak da gösterilebilir. Bu eşdeğerlik ve VEYA için karşılığı, adını Augustus De Morgan'dan alan De Morgan kuramlarıdır.

Mantıksal veyadeğil iki mantıksal değerin, genellikle iki önerme, ikisi de yanlış ise doğru değerini üreten bağlaçtır. Başka bir deyişle değerlerden en az biri doğru ise yanlış üretir.

p NOR q işlemi p ↓ q, Xpq veya p ⊥ q şeklinde de gösterilebilir. VEYA DEĞİL de tek başına bütün doğruluk fonksiyonlarını kurmaya yeter. Bu işlem, 1880 tarihli bir el yazmasında onu kullanan Peirce'ün adıyla Peirce oku, simgesi nedeniyle de Quine hançeri diye anılır.

Veya işleminin değili ¬(p∨q) ya da değillerin vesi (¬p)∧(¬q) olarak da gösterilebilir.

Doğruluk tablosu, bir ifadenin ya da bir çıkarımın mantıksal özelliklerini denetlemenin doğrudan bir yoludur. Tam tablosunun her satırında doğru çıkan ifade bir totoloji, her satırında yanlış çıkan ifade bir çelişkidir. Örneğin p ∨ ¬p iki satırın ikisinde de doğrudur. İki ifade, her satırda aynı doğruluk değerini alıyorsa eşdeğerdir. Bir çıkarım, bütün öncüllerin doğru, sonucun yanlış olduğu bir durum yoksa geçerlidir; tabloda bu, öncüllerin hepsinin doğru, sonucun yanlış olduğu bir "kötü satır" aramak demektir. Bir ifadenin totoloji olmadığını göstermek için bütün tabloyu kurmak gerekmez, ifadenin yanlış çıktığı tek bir satır yeter. Bir veya bağlacının öğelerinden biri doğruysa öbürünü hesaplamaya gerek kalmaması gibi kısayollar da işi hafifletir.

Yöntemin sınırı tablonun büyüklüğüdür: n değişkenli bir ifadenin tablosu 2ⁿ satır olduğundan, denetim için gereken emek değişken sayısıyla üstel olarak artar. Yirmi önerme harfli bir çıkarımı sınamak 2²⁰ = 1.048.576 satırlık bir tablo gerektirir. Bir ifadeyi doğru yapan bir değer ataması bulunup bulunmadığını soran sağlanabilirlik sorunu (SAT) için de tablo yöntemi, değişken sayısı arttıkça hızla ağırlaşır. Stephen Cook 1971'de, Leonid Levin de 1973'te birbirinden bağımsız olarak bu sorunun NP-tam olduğunu gösterdi; bir ifadenin totoloji olup olmadığına karar vermek ise coNP-tamdır.

Claude Shannon, 1938'de röle ve anahtarlama devreleri için geliştirdiği hesabın, mantıkta kullanılan önermeler hesabının tam bir karşılığı olduğunu gösterdi. Sayısal devrelerde doğruluk tablosu, doğru yerine 1, yanlış yerine 0 yazılarak kurulur. Bir mantık kapısının davranışı doğruluk tablosuyla tanımlanır: tablonun her satırı olası bir giriş kombinasyonunu, karşısındaki sütun ise o kombinasyon için üretilen çıkış değerini gösterir.

n girişli bir fonksiyonun doğruluk tablosu 2ⁿ satırdan oluşur: 2 giriş için 4, 3 giriş için 8, 4 giriş için 16 satır gerekir. Her satırın çıkışına bağımsız olarak 0 ya da 1 yazılabildiğinden n değişkenli 2²ⁿ ayrı Boole fonksiyonu vardır; iki değişken için bu sayı 16'dır.

Değişken sayısı (n)	Satır sayısı (2n)	Ayrı Boole fonksiyonu (22n)
1	2	4
2	4	16
3	8	256
4	16	65.536

Doğruluk tablosu bir devrenin tasarımında da başlangıç noktasıdır. İki tek bitlik sayıyı toplayan yarım toplayıcının tablosunda toplam sütunu dışlayan VEYA (XOR), elde sütunu ise VE işleminin doğruluk tablosuyla aynıdır; bu yüzden yarım toplayıcı bir dışlayan VEYA ile bir VE kapısından kurulur.

Bir önceki basamaktan gelen eldeyi de toplayan tam toplayıcının üç girişi olduğundan doğruluk tablosu sekiz satırdır. Satırlar girişlerin oluşturduğu ikili sayının sırasıyla dizilir ve mini terimler de bu sıra numarasıyla anılır; örneğin x = 1, y = 1, z = 0 satırının mini terimi m₆'dır. Tam toplayıcının çıkış sütunlarından hiçbiri tek bir kapının doğruluk tablosuyla örtüşmez; bu yüzden fonksiyonlar Karno haritasıyla yalınlaştırılır. İki yarım toplayıcı ile bir VEYA kapısı birleştirilerek de tam toplayıcı elde edilir.

Bir doğruluk tablosundan doğrudan bir Boole ifadesi yazmanın yolu mini terimlerdir. Mini terim, fonksiyonun bütün değişkenlerinin VE işlemiyle birleştirilmesiyle oluşur ve doğruluk tablosunun tam olarak bir satırında 1 üretir. Çıkışın 1 olduğu her satır için bir mini terim yazılıp bunlar VEYA işlemiyle birleştirilince fonksiyonun standart çarpımlar toplamı (SÇT) biçimi elde edilir; çıkışın 0 olduğu satırlardan da aynı yolla maksi terimler çarpımı yazılabilir. Bu ifadeleri yalınlaştırmak için Maurice Karnaugh'nun 1953'te geliştirdiği Karno haritası kullanılır: doğruluk tablosu özel bir düzende haritaya yerleştirilir, komşu 1'ler gruplanarak değişkenler elenir. Bazı giriş kombinasyonları hiç oluşmuyorsa ya da çıkış bu kombinasyonlarda önem taşımıyorsa, bu satırlar doğruluk tablosunda X ile gösterilir ve önemsenmeyen durum (don't care) olarak adlandırılır.

Birleşik mantık devresi bir salt okunur bellek gibi de düşünülebilir: girişler bir adresi, çıkışlar o adreste saklanan değeri kodlar. FPGA'lardaki bakış tabloları (LUT) bu fikre dayanır: küçük bir bellek, yapılandırılabilen bir doğruluk tablosunun çıkış sütununu tutar ve girişler bir çoklayıcı üzerinden bu bellekten bir biti seçer.

Çıkış bazı girişlere bağlı değilse o girişler tablodan düşürülerek daha kısa bir özet tablo yazılabilir. D flip-flopunun yalnızca bir veri girişi vardır ve saatin her yükselen kenarında çıkışı D girişinin değerini alır; bir sonraki durum Q(t+1) şimdiki durum Q(t)'den bağımsız olduğu için dört satırlık tam tablo iki satıra iner.

Bir işlemcinin denetim birimi işlevsel olarak bir birleşik mantık bloğudur: girişleri buyruğun işlem kodu ve ilgili alanları, çıkışları ise denetim sinyalleridir. Denetim sinyalleri de doğruluk tablosundan Karno haritasına, oradan kapı devresine giden yolla tasarlanır. Sekiz buyruğa üç bitlik birer kod atanan basitleştirilmiş bir örnekte, aritmetik mantık biriminin (AMB) yapacağı işlemi seçen iki bitlik AMBİşlem sinyalinin tablosunda jal buyruğunun satırı önemsenmeyen durumdur, çünkü bu buyruk AMB'yi kullanmaz. Bu serbestlik Karno haritasında yalınlaştırmaya yardımcı olur: AMBİşlem[0] haritasında önemsenmeyen hücre komşu grupla birlikte alınınca çıkış, b 1 ¯ b 0 + b 2 b 1 {\displaystyle {\overline {b_{1}}}\,b_{0}+b_{2}\,b_{1}} gibi iki terimli bir ifadeye iner.