İçeriğe atla

Quine-McCluskey algoritması

Asal implikants yöntemi olarak da bilinen Quine–McCluskey algoritması (QMA), 1952'de Willard V. Quine tarafından geliştirilen ve 1956'da Edward J. McCluskey tarafından genişletilen Boole işlevlerinin minimizasyonu için kullanılan bir yöntemdir.[1][2][3] Genel bir ilke olarak bu yaklaşım, mantıkçı Hugh McColl tarafından 1878'de gösterilmişti.[4][5] 1937'de Archie Blake tarafından[5][6] kanıtlandı ve yeniden keşfedildi. 1954'te Edward W. Samson ve Burton E. Mills ve 1955'te Raymond J. Nelson.[7] Yine 1955'te Paul W. Abrahams ve John G. Nordahl[8] ile Albert A. Mullin ve Wayne G. Kellner yöntemin ondalık bir varyantını önerdiler.[9][10]

Quine–McCluskey algoritması, işlevsel olarak Karno haritasıyla aynıdır, ancak tablo biçimi bilgisayar algoritmalarında kullanım için daha verimli hale getirir ve bir Boole işlevinin minimum biçimine ulaşıldığını kontrol etmek için deterministik bir yol sağlar. Bazen tablolama yöntemi olarak da adlandırılır.

Yöntem iki adımı içerir:

  1. Fonksiyonun tüm asal çarpanları bulunur.
  2. Bu asal çarpanları, fonksiyonun temel asal etkilerini ayrıca fonksiyonu kapsamak için gerekli olan diğer asal çarpanları bulmak için bir asal çarpanlar tablosu kullanılır.

Örnek

1. Adım: Asal çarpanların bulunması

İlk olarak, fonksiyonu bir tablo olarak yazıyoruz.

A B C D F
m0 0 0 0 0 0
m1 0 0 0 1 0
m2 0 0 1 0 0
m3 0 0 1 1 0
m4 0 1 0 0 1
m5 0 1 0 1 0
m6 0 1 1 0 0
m7 0 1 1 1 0
m8 1 0 0 0 1
m9 1 0 0 1 x
m10 1 0 1 0 1
m11 1 0 1 1 1
m12 1 1 0 0 1
m13 1 1 0 1 0
m14 1 1 1 0 x
m15 1 1 1 1 1

Bu tablodan çarpımların kanonik toplamını, fonksiyonun bir olarak değerlendirdiği mintermleri (önemsiz terimleri dışarıda bırakarak) toplayarak kolayca oluşturabilirsiniz:

fA,B,C,D=A'BCD' + ABC'D' + AB'CD' + ABC'D + ABC'D' + ABCD

Bu nedenle, optimize etmek için, bir olarak değerlendirilen tüm mintermler önce bir minterm tablosuna yerleştirilir. Önemsiz terimler de bu tabloya eklenir (adlar parantez içindedir), böylece mintermlerle birleştirilebilirler:

1lerin

sayısı

Minterm İkili Gösterimi
1 m4 0100
m8 1000
2 (m9) 1001
m10 1010
m12 1100
3 m11 1011
(m14) 1110
4 m15 1111

Bu noktada mintermleri diğer mintermlerle birleştirmeye başlanabilir. İki terim yalnızca tek bir basamakla farklılık gösteriyorsa, o basamak, basamağın önemli olmadığını belirten bir tire ile değiştirilebilir. Artık birleştirilemeyecek terimler bir yıldız (*) ile işaretlenmiştir. Örneğin 1000 ve 1001, 100- verecek şekilde birleştirilebilir; bu, her iki mintermin de ilk hanenin 1 ve sonraki ikisinin 0 olduğunu ima ettiğini gösterir.

1lerin

sayısı

Minterm 0-küp 2. Boyut etkileri
1 m4 0100 m(4,12) -100*
m8 1000 m(8,9) 100-
- - m(8,10) 10-0
- - m(8,12) 1-00
2 m9 1001 m(9,11) 10-1
m10 1010 m(10,11) 101-
- - m(10,14) 1-10
m12 1100 m(12,14) 11-0
3 m11 1011 m(11,15) 1-11
m14 1110 m(14,15) 111-
4 m15 1111 -

Boyut 2'den Boyut 4'e geçerken - üçüncü bir bit değeri olarak ele alın. Örneğin, -110 ve -100, -1-0'ı vermek üzere birleştirilebilir, ca -110 ve -11-'in -11- vermesi gibi, ancak -110 ve 011- olamaz çünkü -110, 1110 tarafından ima edilirken 011- değil. (Püf Noktası: İlkini eşleştirin.)

1lerin

sayısı

minterm 0-küp 2. Boyut etkileri 4. Boyut etkileri
1 m4 0100 m(4,12) -100* m(8,9,10,11) 10--*
m8 1000 m(8,9) 100- m(8,10,12,14) 1--0*
- - m(8,10) 10-0 -
- - m(8,12) 1-00 -
2 m9 1001 m(9,11) 10-1 m(10,11,14,15) 1-1-*
m10 1010 m(10,11) 101- -
- - m(10,14) 1-10 -
m12 1100 m(12,14) 11-0 -
3 m11 1011 m(11,15) 1-11 -
m14 1110 m(14,15) 111- -
4 m15 1111 - -

Not: Genel olarak bu işleme daha fazla terim birleştirilemeyecek duruma gelene kadar devam edilmelidir. Bu örnekteki terimlerin hiçbiri daha fazla birleştirilemez.

2. Adım

Terimlerin hiçbiri bundan daha fazla birleştirilemez, bu nedenle bu noktada bir asal dolaylı tablo oluşturuyoruz. Kenar boyunca, henüz oluşturulmuş olan asal çıkarımlar gider ve üst kısım boyunca daha önce belirtilen mintermler gider. Önemsiz terimler en üste yerleştirilmemiştir - gerekli girdiler olmadıkları için bu bölümden çıkarılmıştır.

4810111215⇒ABCD
Şablon:Ts | m(4,12)*✓✓⇒-100
Şablon:Ts | m(8,9,10,11)✓✓✓⇒10--
Şablon:Ts | m(8,10,12,14)✓✓✓⇒1--0
Şablon:Ts | m(10,11,14,15)*✓✓✓⇒1-1-
Temel asal çıkarımları bulmak için en üst sıra boyunca ilerliyoruz. Sadece bir "✓" içeren sütunları aramamız gerekiyor. Bir sütunda yalnızca bir "✓" varsa, bu, minterm'in yalnızca bir asal dolaylı tarafından kapsanabileceği anlamına gelir. Örneğin: ilk sütunda minterm 4 ile yalnızca bir "✓" vardır.
Bu, m(4,12)'nin gerekli olduğu anlamına gelir. Bu yüzden yanına bir yıldız koyuyoruz. Minterm 15'te de sadece bir "✓" vardır, dolayısıyla m(10,11,14,15) de esastır. Artık bir "✓" içeren tüm sütunlar kapsanmıştır.
İkinci asal implikant üçüncü ve dördüncü tarafından "kapsanabilir" ve üçüncü asal implikeant ikinci ve birinci tarafından "kapsanabilir" bu nedenle hiçbiri zorunlu değildir. Bir asal implikant gerekliyse, beklendiği gibi, onu minimize edilmiş boole denklemine dahil etmek gerekir. Bazı durumlarda, temel asal çıkarımlar tüm mintermleri kapsamaz, bu durumda çizelge indirgemesi için ek prosedürler kullanılabilir. En basit "ek prosedür" deneme yanılma yöntemidir, ancak daha sistematik bir yol Petrick'in yöntemidir. Mevcut örnekte, temel asal çıkarımlar tüm mintermleri işlemez, bu nedenle, bu durumda, temel çıkarımlar, bir denklem elde etmek için iki temel olmayanlardan biriyle birleştirilebilir:
fA,B,C,D=BC'D' + AB' + AC
veya
fA,B,C,D=BC'D' + AD' + AC
Bu son denklemlerin her ikisi de orijinal denkleme işlevsel olarak eşdeğerdir:
fA,B,C,D = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD.

Kaynakça

  1. ^ Quine, W. V. (1 Ekim 1952). "The Problem of Simplifying Truth Functions". The American Mathematical Monthly. 59 (8): 521-531. doi:10.1080/00029890.1952.11988183. ISSN 0002-9890. 
  2. ^ Quine, W. V. (1 Kasım 1955). "A Way to Simplify Truth Functions". The American Mathematical Monthly. 62 (9): 627-631. doi:10.1080/00029890.1955.11988710. ISSN 0002-9890. 
  3. ^ McCluskey, E. J. (Kasım 1956). "Minimization of Boolean functions". The Bell System Technical Journal. 35 (6): 1417-1444. doi:10.1002/j.1538-7305.1956.tb03835.x. ISSN 0005-8580. 24 Haziran 2021 tarihinde kaynağından arşivlendi. Erişim tarihi: 21 Haziran 2021. 
  4. ^ McColl, Hugh (1878). "The Calculus of Equivalent Statements (Third Paper)". Proceedings of the London Mathematical Society (İngilizce). s1-10 (1): 16-28. doi:10.1112/plms/s1-10.1.16. ISSN 1460-244X. 24 Haziran 2021 tarihinde kaynağından arşivlendi. Erişim tarihi: 21 Haziran 2021. 
  5. ^ a b Brown, Frank Markham (1 Kasım 2010). "McColl and Minimization". History and Philosophy of Logic. 31 (4): 337-348. doi:10.1080/01445340.2010.517387. ISSN 0144-5340. 
  6. ^ Blake, Archie (Haziran 1938). "Corrections to Canonical expressions in Boolean algebra". The Journal of Symbolic Logic (İngilizce). 3 (2): 112-113. doi:10.2307/2267595. ISSN 0022-4812. 25 Haziran 2021 tarihinde kaynağından arşivlendi. Erişim tarihi: 21 Haziran 2021. 
  7. ^ Nelson, Raymond J. (Mart 1955). "Simplest normal truth functions". The Journal of Symbolic Logic (İngilizce). 20 (2): 105-108. doi:10.2307/2266893. ISSN 0022-4812. 25 Haziran 2021 tarihinde kaynağından arşivlendi. Erişim tarihi: 21 Haziran 2021. 
  8. ^ home, Jellison Funeral. "Obituary for John "Jack" G Nordahl". Obituary for John "Jack" G Nordahl (İngilizce). 5 Mayıs 2020 tarihinde kaynağından arşivlendi. Erişim tarihi: 21 Haziran 2021. 
  9. ^ Fielder, Daniel C. (Aralık 1966). "Classroom Reduction of Boolean Functions". IEEE Transactions on Education. 9 (4): 202-205. doi:10.1109/TE.1966.4321989. ISSN 1557-9638. 24 Haziran 2021 tarihinde kaynağından arşivlendi. Erişim tarihi: 21 Haziran 2021. 
  10. ^ Majumder, Alak; Chowdhury, Barnali; Mondai, Abir J; Jain, Kunj (Ocak 2015). "Investigation on Quine McCluskey method: A decimal manipulation based novel approach for the minimization of Boolean function". 2015 International Conference on Electronic Design, Computer Networks Automated Verification (EDCAV): 18-22. doi:10.1109/EDCAV.2015.7060531. 24 Haziran 2021 tarihinde kaynağından arşivlendi. Erişim tarihi: 21 Haziran 2021. 

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">Matematik</span> nicelik, yapı, uzay ve değişim gibi konularla ilgilenen bilim dalı

Matematik ; sayılar, felsefe, uzay ve fizik gibi konularla ilgilenir. Matematikçiler ve filozoflar arasında matematiğin kesin kapsamı ve tanımı konusunda görüş ayrılığı vardır.

<span class="mw-page-title-main">Asal sayı</span> sadece iki pozitif tam sayı böleni olan doğal sayılardır

Bir asal sayı, yalnızca 1'den büyük olup kendisinden küçük iki doğal sayının çarpımı olarak ifade edilemeyen bir doğal sayıdır. 1'den büyük ve asal olmayan doğal sayılara bileşik sayı adı verilir. Örneğin, 5 bir asal sayıdır çünkü onu bir çarpım olarak ifade etmenin mümkün olan yolları, 1 × 5 veya 5 × 1, yalnızca 5 sayısını içermektedir. Ancak, 4 bir bileşik sayıdır çünkü bu, her iki sayının da 4'ten küçük olduğu bir çarpım şeklindedir. Asal sayılar, aritmetiğin temel teoreminden ötürü sayı teorisi alanında merkezi öneme sahiptir: 1'den büyük her doğal sayı, ya bir asal sayıdır ya da asal sayıların çarpımı olarak, sıralamalarından bağımsız bir şekilde, benzersiz olarak çarpanlarına ayrılabilir.

<span class="mw-page-title-main">Epistemoloji</span> bilginin doğası, kapsamı ve kaynağı ile ilgilenen felsefe dalı

Epistemoloji ya da bilgi felsefesi, bilgiyle ilgilenen bir felsefe dalıdır. Epistemologlar, bilginin doğası, kaynağı ve kapsamı, epistemolojik gerekçelendirme, inancın rasyonelliğini ve diğer çeşitli konuları incelemektedir. Epistemoloji, felsefenin etik, mantık ve metafizikle birlikte dört ana dalından biri olarak kabul edilir.

Boole cebiri değişkenlerin değerinin doğru ve yanlış olabildiği bir cebir altkoludur. Doğru ve yanlış değerleri genelde sırasıyla 1 ve 0 olarak ifade edilir. Değişken değerlerinin sayı, işlemlerin ise toplama ve çarpma olduğu temel cebrin aksine Boole cebrinde ∧ işareti ile ifade edilen "ve", ∨ işareti ile ifade edilen "veya", ¬ ile ifade edilen "değil" işlemleri bulunur.

<span class="mw-page-title-main">Totient</span>

Totient sayılar teorisinde, bir tam sayının o sayıdan daha küçük ve o sayı ile aralarında asal olan sayma sayı sayısını belirten fonksiyondur. Genellikle Euler Totient ya da Euler'in Totienti olarak adlandırılan Totient, İsviçreli matematikçi Leonhard Euler tarafından yaratılmıştır. Totient fonksiyonu, Yunan harflerinden ile simgelendiği için Fi fonksiyonu olarak da anılabilir.

<span class="mw-page-title-main">Willard Van Orman Quine</span> Amerikalı filozof (1908 – 2000)

Willard Van Orman Quine, analitik felsefe geleneğinden Amerikalı filozof ve mantıkçı. "Yirminci yüzyılın en etkili filozoflarından biri" sayılır. 1930'dan 70 yıl sonraki ölümüne kadar Quine sürekli olarak Harvard Üniversitesi ile öyle ya da böyle yakından ilgiliydi, önce bir öğrenci; sonra da bir profesör olarak. 1956-78 yıllarında Harvard Edgar Pierce Felsefe Kürsüsünde ders verdi.

<span class="mw-page-title-main">Leonhard Euler</span> Matematikçi ve Fizikçi

Leonhard Euler, çizge teorisi çalışmasını kuran bir İsviçreli matematikçi, fizikçi, astronom, coğrafyacı, mantıkçı ve mühendisti. Topoloji ve analitik sayı teorisi, karmaşık analiz ve sonsuz küçük hesap gibi matematiğin diğer birçok dalında öncü ve etkili keşifler yaptı. Bir matematiksel fonksiyon kavramı da dahil olmak üzere, modern matematiksel terminolojinin ve gösterim'in çoğunu tanıttı. Ayrıca mekanik, akışkan dinamiği, optik, astronomi ve müzik teorisi alanındaki çalışmalarıyla da tanınır.

Doğum kontrolü, geçici veya kalıcı olarak hamileliği engellemek ya da hamile kalma olasılığını azaltmak amacıyla çeşitli yöntemlerin, araç-gereçlerin ya da ilaçların kullanılmasıdır.

<i>Bacillus subtilis</i>

Bacillus subtilis, Gram pozitif, Katalaz-pozitif, spor oluşturan bir bakteridir. Bugüne kadar zorunlu aerob olarak bilinmesine rağmen, fakültatif anaerob olabildiği de gösterilmiştir. Üreme sıcaklığı 20-30 °C'dir. Vejetatif şekilleri yüksek ısıya dayanıksız olsa da, sporları bazen kaynama derecelerinde birkaç saat dayanabilirler. B. subtilis üzerinde en fazla çalışma yapılmış Gram-pozitif bakteri türü olarak bilinir ve bakteriyel kromozom replikasyonu ve hücre farklılaşması için bir model organizmadır. En fazla enzim üreten bakterilerden biridir ve biyoteknoloji firmaları tarafından endüstriyel ölçekte kullanılmaktadır. Panoftalmi ve iridosiklit gibi göz enfeksiyonlarına neden olur.

<span class="mw-page-title-main">Eteneliler</span> Eutheria sınıfındaki memelilerin alt sınıfı

Eteneliler, eteneli memeliler veya plasentalı memeliler, memelilerin bir infra sınıfı. Diğer alt sınıflar keseliler (Metatheria) ve hâlâ yumurtlayarak üreyen ilkel memelilerdir (Protheria). Aralarında büyük bir farkla en büyük grup etenelilerdir. Günümüzde, 6000'in üzerinde eteneli türü bulunmaktadır. Vücut yapıları ve yaşam alanlarının farklılıkları ile en çeşitli memeli grubunu oluştururlar.

<span class="mw-page-title-main">Karnaugh haritası</span>

Karnaugh haritası (İngilizce) Boolean cebri'ndeki ifadeleri sadeleştirmek için kullanılan bir yöntemdir. Maurice Karnaugh 1953'te Edward Veitch'in 1952'te keşfettiği Veitch tablosunun geliştirilmiş ve elektrik devrelerine odaklanmış versiyonu olarak tanıtıldı. Veitch tablosu ve Karnaugh haritası bu yüzden Marquand-Veitch diyagramı ve Karnaugh Veitch haritası olarak da bilinir.Karnaugh haritası insanların örüntü tanıyabilme kabiliyetini kullanarak karışık hesaplamaları sadeleştirir. Aynı zamanda potansiyel hata durumlarının hızlıca fark edilmesini ve ortadan kaldırılmasını kolaylaştırır.

Optogenetik, ışık sayesinde ve genetik yardımla beyin hücrelerini araştıran yeni gelişmekte olan bir bilim dalı.

<span class="mw-page-title-main">Anabolik steroid</span>

Anabolik steroidler ya da teknik adıyla anabolik-androjenik steroidler veya halk diliyle steroidler, vücutta testosteron veya daha etkin formu olan dihidrotestosteron etkilerini taklit eden ilaçlardır. Bu ilaçlar hücrelerde protein sentezini arttırarak dokuların gelişimini uyarırlar. Etkileri özellikle kas dokusunda belirgindir. Anabolik steroidler ayrıca seste kalınlaşma, vücut kıllarında artış, testislerde büyüme gibi erkeksi özellikleri geliştiren androjenik ve virilizan özelliklere sahiptirler.

Sayı teorisinde, asal çarpanlara ayırma bir bileşik sayının, çarpıldıklarında yine aynı sayıyı verecek şekilde, bir ve kendisi dışındaki bölenlerine ayrılmasıdır.

Matematik konularının listesi, matematik ile ilgili çeşitli konuları kapsar. Bu listelerden bazıları yüzlerce makaleye bağlantı içerir; bazıları sadece birkaç tane ile bağlantılıdır. Bu makale, aynı içeriği, göz atmaya daha uygun bir şekilde organize halde bir araya getirmektedir. Listeler, temel ve ileri matematik, metodoloji, matematiksel ifadeler, integraller, genel kavramlar, matematiksel nesneler ve referans tablolarının özelliklerini kapsar. Ayrıca insanların adını taşıyan denklemleri, matematiksel toplulukları, matematikçileri, matematik dergilerini ve meta listeleri de kapsar.

<span class="mw-page-title-main">Sergey Bernstein</span> Sovyet matematikçi

Sergey Natanoviç Bernstein kısmi diferansiyel denklemlere, diferansiyel geometriye, olasılık teorisine ve yaklaşım teorisine katkılarıyla tanınan Yahudi kökenli bir Rus ve Sovyet matematikçi.

Espresso mantık sadeleştiricisi, dijital mantık kapısı devrelerinin karmaşıklığını etkili bir şekilde azaltmak için sezgisel ve özel algoritmalar kullanan bir bilgisayar programıdır. Espresso, IBM'den Robert K. Brayton tarafından geliştirilmiştir. Richard L. Rudell daha sonra 1986'da "PLA Sentezi için Çok Değerlikli Mantık Minimizasyonu" başlığı altında Espresso-MV varyantını yayınladı. Espresso birçok türevine ilham vermiştir.

<span class="mw-page-title-main">Bağımsız süspansiyon</span>

Bu tip süspansiyon, karşı tekerleğin hareketini etkilemeden tekerleğin hareket etmesini sağlamaktadır.

Bastırılmış hafıza, özellikle bireyleri haksız ve yanlış bir şekilde suçlamak için kullanıldığı ve önemli zararlara yol açtığı yasal bağlamlarda tartışmalı bir kavramdır. Amerikan Psikoloji Derneği çalışma grubu, "çocukken cinsel istismara uğrayan çoğu insan, başlarına gelenlerin tamamını veya bir kısmını hatırlarken, uzun süredir geçmiş istismar anılarının unutulmasının mümkün olduğunu belirtmiştir. Sigmund Freud, daha sonra teorisini revize etse de, başlangıçta çocukluk cinsel travması anılarının sıklıkla bastırıldığını ancak bu travmaların bilinçsizce davranışları ve duygusal tepkileri etkilediğini savunmuştur.

Bu bir sayılar teorisi zaman çizelgesidir.


Bu sayfa, bu Vikipedi makalesine dayanmaktadır.
Metin, CC BY-SA 4.0 lisansı altında mevcuttur; ek koşullar uygulanabilir.
Görseller, videolar ve sesler kendi lisansları altında mevcuttur.