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.[1]
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.[2][3]
Tarihçe
[değiştir | kaynağı değiştir]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ı.[4] 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.[3] 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.[3] Peirce, üç değerli önerme mantığını da Łukasiewicz ile Post'tan en az on yıl önce kurdu.[5]
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ı.[3] 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ı.[6][7] Stanford Felsefe Ansiklopedisi'ne göre Wittgenstein bu eserde Frege'nin mantığını, sonradan doğruluk tablosu diye anılacak biçimde sundu.[7] Aynı yıl Post, bir fonksiyonun değişkenlerinin 2n 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ı.[4]
Tablonun kurulması
[değiştir | kaynağı değiştir]| p | q | r | p ∧ q | (p ∧ q) → r |
|---|---|---|---|---|
| D | D | D | D | D |
| D | D | Y | D | Y |
| D | Y | D | Y | D |
| D | Y | Y | Y | D |
| Y | D | D | Y | D |
| Y | D | Y | Y | D |
| Y | Y | D | Y | D |
| Y | Y | Y | Y | D |
Tam bir doğruluk tablosunda ifadedeki her önerme harfi için bir sütun vardır ve n farklı harf için tablo 2n satırdır: beş harf 32, altı harf 64 satır gerektirir.[8]:81 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.[8]:81
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.[8]:381-382 Ara sütunlar yalnızca hesabı düzenli tutmaya yarar; ifadenin doğruluk değerini ana bağlacın altındaki sütun verir.[8]:79-80 Ö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.
Birli işlemler
[değiştir | kaynağı değiştir]| p | p |
|---|---|
| D | D |
| Y | Y |
| p | ¬p |
|---|---|
| D | Y |
| Y | D |
Mantıksal özdeşlik
[değiştir | kaynağı değiştir]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
[değiştir | kaynağı değiştir]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.[9][10]:402 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.[9][11]
İkili işlemler
[değiştir | kaynağı değiştir]Tüm operatörler için doğruluk tablosu
[değiştir | kaynağı değiştir]İ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.
| No. | Çıkış (p, q girişlerine göre) | Łukasiewicz gösterimi | Sayısal mantıktaki adı | Simge | Mantıktaki adı | |||
|---|---|---|---|---|---|---|---|---|
| D, D | D, Y | Y, D | Y, Y | |||||
| 0 | Y | Y | Y | Y | Opq | Boş (hep 0) | yanlış | Çelişki |
| 1 | Y | Y | Y | D | Xpq | VEYA DEĞİL (NOR) | ↓ | Mantıksal veya değil |
| 2 | Y | Y | D | Y | Mpq | Engelleme | ↚ | |
| 3 | Y | Y | D | D | Fpq | Tümleyen | ¬p | Tümleme |
| 4 | Y | D | Y | Y | Lpq | Engelleme | ↛ | |
| 5 | Y | D | Y | D | Gpq | Tümleyen | ¬q | Tümleme |
| 6 | Y | D | D | Y | Jpq | Dışlayan VEYA (XOR) | ⊕ | Dışlayıcı veya |
| 7 | Y | D | D | D | Dpq | VE DEĞİL (NAND) | ↑ | Mantıksal ve değil |
| 8 | D | Y | Y | Y | Kpq | VE (AND) | ∧ | Mantıksal ve |
| 9 | D | Y | Y | D | Epq | Eşdeğerlik (XNOR) | ↔ | İki yönlü koşullu önerme |
| 10 | D | Y | D | Y | Hpq | Aktarım | q | |
| 11 | D | Y | D | D | Cpq | İçerme | → | Koşullu önerme |
| 12 | D | D | Y | Y | Ipq | Aktarım | p | |
| 13 | D | D | Y | D | Bpq | İçerme | ← | Ters koşullu önerme |
| 14 | D | D | D | Y | Apq | VEYA (OR) | ∨ | Mantıksal veya |
| 15 | D | D | D | D | Vpq | Birim eleman (hep 1) | doğru | Totoloji |
Mantık işlemleri Venn şeması kullanılarak da gösterilebilir.
Mantıksal ve
[değiştir | kaynağı değiştir]| p | q | p ∧ q |
|---|---|---|
| D | D | D |
| D | Y | Y |
| Y | D | Y |
| Y | Y | Y |
| p | q | p ∨ q |
|---|---|---|
| D | D | D |
| D | Y | D |
| Y | D | D |
| Y | Y | Y |
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 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.[9] Bir önermenin kendisiyle VE işlemine girmesi onu değiştirmez: p ∧ p ≡ p. Bu özelliğe etkisizlik denir.[12]:59[10]:402 Sayısal devrelerde bu işlemi VE kapısı gerçekleştirir.
Mantıksal veya
[değiştir | kaynağı değiştir]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.[8]:38-39 Stanford Felsefe Ansiklopedisi'ne göre dışlayıcı okuma sözcüğün kendi anlamından değil kullanıldığı bağlamdan doğar.[13] ∨ 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.[13] VEYA da VE gibi değişme ve birleşme özelliklerine sahiptir.[9]
Koşullu önerme (İse)
[değiştir | kaynağı değiştir]| p | q | p → q |
|---|---|---|
| D | D | D |
| D | Y | Y |
| Y | D | D |
| Y | Y | D |
| p | q | p ≡ q |
|---|---|---|
| D | D | D |
| D | Y | Y |
| Y | D | Y |
| Y | Y | D |
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.[9][12]:50 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.[8]:96 p → q, ¬q → ¬p ile eşdeğerdir; ancak q → p ile genel olarak eşdeğer değildir.[12]:55
İki yönlü koşullu önerme (Ancak ve ancak)
[değiştir | kaynağı değiştir]İ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.[8]:41 İki değişkenli durumda XNOR işlemiyle aynıdır.[14] Bu yüzden sayısal devrelerde bir XNOR kapısı iki biti karşılaştıran bir eşitlik denetleyicisi olarak kullanılır.[10]:400[15]
Dışlayıcı veya
[değiştir | kaynağı değiştir]| p | q | p ⊕ q |
|---|---|---|
| D | D | Y |
| D | Y | D |
| Y | D | D |
| Y | Y | Y |
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.[16] 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).[17]
Mantıksal ve değil
[değiştir | kaynağı değiştir]| p | q | p ↑ q |
|---|---|---|
| D | D | Y |
| D | Y | D |
| Y | D | D |
| Y | Y | D |
| p | q | p∧q | ¬(p∧q) | ¬p | ¬q | (¬p)∨(¬q) |
|---|---|---|---|---|---|---|
| D | D | D | Y | Y | Y | Y |
| D | Y | Y | D | Y | D | D |
| Y | D | Y | D | D | Y | D |
| Y | Y | Y | D | D | D | D |
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.[8]:379 Sayısal tasarımda bu yüzden ikisine evrensel kapı denir.[10]:401 CMOS teknolojisinde VE DEĞİL kapıları VEYA DEĞİL kapılarından hızlıdır.[18]
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ı.[19][20] Sheffer bu işlem olarak aslında VEYA DEĞİL'i kullanmıştı; çizgiyi VE DEĞİL için kullananlar Whitehead ile Russell oldu.[21] 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ı.[8]:378
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.[9][22][10]:403-404
Mantıksal veyadeğil
[değiştir | kaynağı değiştir]| p | q | p ↓ q |
|---|---|---|
| D | D | Y |
| D | Y | Y |
| Y | D | Y |
| Y | Y | D |
| p | q | p∨q | ¬(p∨q) | ¬p | ¬q | (¬p)∧(¬q) |
|---|---|---|---|---|---|---|
| D | D | D | Y | Y | Y | Y |
| D | Y | D | Y | Y | D | Y |
| Y | D | D | Y | D | Y | Y |
| Y | Y | Y | D | D | D | D |
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.[8]:379 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.[21]
Veya işleminin değili ¬(p∨q) ya da değillerin vesi (¬p)∧(¬q) olarak da gösterilebilir.
Doğruluk tablosuyla sınama
[değiştir | kaynağı değiştir]| p | ¬p | p ∨ ¬p |
|---|---|---|
| D | Y | D |
| Y | D | D |
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.[8]:85-86 Ö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.[8]:86-87 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.[8]:98, 110 Bir ifadenin totoloji olmadığını göstermek için bütün tabloyu kurmak gerekmez, ifadenin yanlış çıktığı tek bir satır yeter.[8]:102 Bir veya bağlacının öğelerinden biri doğruysa öbürünü hesaplamaya gerek kalmaması gibi kısayollar da işi hafifletir.[8]:97
Yöntemin sınırı tablonun büyüklüğüdür: n değişkenli bir ifadenin tablosu 2n satır olduğundan, denetim için gereken emek değişken sayısıyla üstel olarak artar.[12]:58 Yirmi önerme harfli bir çıkarımı sınamak 220 = 1.048.576 satırlık bir tablo gerektirir.[8]:111-112 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.[12]:62 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.[23][24]
Sayısal mantıkta doğruluk tablosu
[değiştir | kaynağı değiştir]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.[25] Sayısal devrelerde doğruluk tablosu, doğru yerine 1, yanlış yerine 0 yazılarak kurulur.[26][10]:399 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.[10]:400
n girişli bir fonksiyonun doğruluk tablosu 2n satırdan oluşur: 2 giriş için 4, 3 giriş için 8, 4 giriş için 16 satır gerekir.[10]:400[9] Her satırın çıkışına bağımsız olarak 0 ya da 1 yazılabildiğinden n değişkenli 22n ayrı Boole fonksiyonu vardır; iki değişken için bu sayı 16'dır.[27][10]:404
| 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 |
| Girişler | Çıkışlar | ||
|---|---|---|---|
| A | B | Toplam | Elde |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
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.[10]:229[28]
| Girişler | Çıkışlar | |||
|---|---|---|---|---|
| a | b | Giren elde | Toplam | Çıkan elde |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Bir önceki basamaktan gelen eldeyi de toplayan tam toplayıcının üç girişi olduğundan doğruluk tablosu sekiz satırdır.[10]:230 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 m6'dır.[10]:405-406 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.[10]:230
Tablodan devreye
[değiştir | kaynağı değiştir]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.[10]:405 Çı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.[29][10]:405-406 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.[30][10]:407 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.[10]:412
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.[28] 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.[31]
Özet doğruluk tabloları
[değiştir | kaynağı değiştir]| Q(t) | D | Q(t+1) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
| D | Q(t+1) |
|---|---|
| 0 | 0 |
| 1 | 1 |
Çı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.[10]:429-430
İşlemci denetiminde doğruluk tablosu
[değiştir | kaynağı değiştir]| Buyruk | Kod (b2b1b0) | AMBİşlem | İşlem |
|---|---|---|---|
add | 000 | 00 | Topla |
sub | 001 | 01 | Çıkar |
ori | 010 | 10 | VEYA |
lw | 011 | 00 | Topla |
sw | 100 | 00 | Topla |
beq | 101 | 01 | Çıkar |
bne | 110 | 01 | Çıkar |
jal | 111 | XX | önemsenmeyen |
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.[10]:325 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ış, gibi iki terimli bir ifadeye iner.[10]:330
Kaynakça
[değiştir | kaynağı değiştir]- ↑ Enderton, Herbert B. (2001). A Mathematical Introduction to Logic (İngilizce) (2 bas.). San Diego: Harcourt/Academic Press. ISBN 978-0-12-238452-3.
- ↑ Georg Henrik von Wright (1955). "Ludwig Wittgenstein, A Biographical Sketch". The Philosophical Review. 64 (4). ss. 527-545 (s. 532, not 9). JSTOR 2182631.
- 1 2 3 4 Anellis, Irving H. (2012). "Peirce's Truth-functional Analysis and the Origin of the Truth Table". History and Philosophy of Logic (İngilizce). 33 (1). ss. 87-97. arXiv:1108.2429
. doi:10.1080/01445340.2011.621702. - 1 2 Post, Emil L. (1921). "Introduction to a General Theory of Elementary Propositions". American Journal of Mathematics (İngilizce). 43 (3). ss. 163-185. doi:10.2307/2370324.
- ↑ Shin, Sun-Joo (20 Mayıs 2022). "Peirce's Deductive Logic" (İngilizce). Stanford Encyclopedia of Philosophy. Erişim tarihi: 25 Eylül 2026.
- ↑ Wittgenstein, Ludwig (1922). Tractatus Logico-Philosophicus (İngilizce). C. K. Ogden tarafından çevrildi. Kegan Paul. Önerme 4.31 ve 5.101.
- 1 2 Biletzki, Anat; Matar, Anat. "Ludwig Wittgenstein" (İngilizce). Stanford Encyclopedia of Philosophy. Erişim tarihi: 25 Eylül 2026.
- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Magnus, P. D.; Button, Tim; Trueman, Robert; Zach, Richard (2025). forall x: Calgary. An Introduction to Formal Logic (PDF) (İngilizce). Open Logic Project.
- 1 2 3 4 5 6 7 Franks, Curtis (18 Mayıs 2023). "Propositional Logic" (İngilizce). Stanford Encyclopedia of Philosophy. Erişim tarihi: 25 Eylül 2026.
- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Ergin, Oğuz (2026). Bilgisayar Mimarisi: RISC-V Tabanlı Yaklaşım. 0.4.8. doi:10.5281/zenodo.18903608. ISBN 978-625-00-6081-0.
- ↑ Horn, Laurence R.; Wansing, Heinrich. "Negation" (İngilizce). Stanford Encyclopedia of Philosophy. Erişim tarihi: 26 Eylül 2026.
- 1 2 3 4 5 Lehman, Eric; Leighton, F. Thomson; Meyer, Albert R. (2018). Mathematics for Computer Science (PDF) (İngilizce). MIT.
- 1 2 Aloni, Maria. "Disjunction" (İngilizce). Stanford Encyclopedia of Philosophy. Erişim tarihi: 26 Eylül 2026.
- ↑ Weisstein, Eric W. "XNOR" (İngilizce). MathWorld. Erişim tarihi: 26 Eylül 2026.
- ↑ Benson, Greg (21 Ekim 2025). "Digital Logic Components (CS 315 Computer Architecture)" (İngilizce). University of San Francisco. Erişim tarihi: 26 Eylül 2026.
- ↑ Weisstein, Eric W. "XOR" (İngilizce). MathWorld. Erişim tarihi: 26 Eylül 2026.
- ↑ "CSE 311 Section 02" (PDF) (İngilizce). University of Washington. Erişim tarihi: 26 Eylül 2026.
- ↑ Harris, David. "Lecture 6: Logical Effort" (PDF) (İngilizce). Harvey Mudd College. Erişim tarihi: 26 Eylül 2026.
- ↑ Sheffer, Henry M. (1913). "A set of five independent postulates for Boolean algebras, with application to logical constants". Transactions of the American Mathematical Society (İngilizce). 14 (4). ss. 481-488. doi:10.1090/S0002-9947-1913-1500960-1.
- ↑ Burris, Stanley. "The Algebra of Logic Tradition" (İngilizce). Stanford Encyclopedia of Philosophy. Erişim tarihi: 26 Eylül 2026.
- 1 2 Makridis, Odysseus. "The Sheffer Stroke" (İngilizce). Internet Encyclopedia of Philosophy. Erişim tarihi: 26 Eylül 2026.
- ↑ "Augustus De Morgan" (İngilizce). MacTutor History of Mathematics, University of St Andrews. Erişim tarihi: 26 Eylül 2026.
- ↑ Dean, Walter. "Computational Complexity Theory" (İngilizce). Stanford Encyclopedia of Philosophy. Erişim tarihi: 26 Eylül 2026.
- ↑ Cook, Stephen A. (1971). The complexity of theorem-proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing (İngilizce). ACM. ss. 151-158. doi:10.1145/800157.805047.
- ↑ Shannon, Claude E. (1938). "A Symbolic Analysis of Relay and Switching Circuits". Transactions of the American Institute of Electrical Engineers (İngilizce). 57 (12). ss. 713-723. doi:10.1109/T-AIEE.1938.5057767.
- ↑ Langer, Michael (18 Ocak 2016). "COMP 273: Combinational logic 1" (PDF) (İngilizce). McGill University. Erişim tarihi: 25 Eylül 2026.
- ↑ "CS 201 lecture notes, 16 February 2018" (İngilizce). Yale University. Erişim tarihi: 25 Eylül 2026.
- 1 2 Langer, Michael (20 Ocak 2016). "COMP 273: Combinational logic 2" (PDF) (İngilizce). McGill University. Erişim tarihi: 25 Eylül 2026.
- ↑ "CSC 173 lecture notes: Propositional logic" (İngilizce). University of Rochester. Erişim tarihi: 25 Eylül 2026.
- ↑ Karnaugh, Maurice (1953). "The map method for synthesis of combinational logic circuits". Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics (İngilizce). 72 (5). ss. 593-599. doi:10.1109/TCE.1953.6371932.
- ↑ "FPGA Architecture Basics" (İngilizce). AMD. Erişim tarihi: 25 Eylül 2026.
