Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
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. Genel bir ilke olarak bu yaklaşım, mantıkçı Hugh McColl tarafından 1878'de gösterilmişti. 1937'de Archie Blake tarafından kanıtlandı ve yeniden keşfedildi. 1954'te Edward W. Samson ve Burton E. Mills ve 1955'te Raymond J. Nelson. Yine 1955'te Paul W. Abrahams ve John G. Nordahl ile Albert A. Mullin ve Wayne G. Kellner yöntemin ondalık bir varyantını önerdiler.
Quine–McCluskey algoritması, işlevsel olarak 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:
- Fonksiyonun tüm asal çarpanları bulunur.
- 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.
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.4 8 10 11 12 15 ⇒ A B C D | m(4,12)* ⇒ - 1 0 0 | m(8,9,10,11) ⇒ 1 0 - - | m(8,10,12,14) ⇒ 1 - - 0 | m(10,11,14,15)* ⇒ 1 - 1 -
- 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 . 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
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Asal implikants yontemi olarak da bilinen Quine McCluskey algoritmasi QMA 1952 de Willard V Quine tarafindan gelistirilen ve 1956 da Edward J McCluskey tarafindan genisletilen Boole islevlerinin minimizasyonu icin kullanilan bir yontemdir Genel bir ilke olarak bu yaklasim mantikci Hugh McColl tarafindan 1878 de gosterilmisti 1937 de Archie Blake tarafindan kanitlandi ve yeniden kesfedildi 1954 te Edward W Samson ve Burton E Mills ve 1955 te Raymond J Nelson Yine 1955 te Paul W Abrahams ve John G Nordahl ile Albert A Mullin ve Wayne G Kellner yontemin ondalik bir varyantini onerdiler Quine McCluskey algoritmasi islevsel olarak aynidir ancak tablo bicimi bilgisayar algoritmalarinda kullanim icin daha verimli hale getirir ve bir Boole islevinin minimum bicimine ulasildigini kontrol etmek icin deterministik bir yol saglar Bazen tablolama yontemi olarak da adlandirilir Yontem iki adimi icerir Fonksiyonun tum asal carpanlari bulunur Bu asal carpanlari fonksiyonun temel asal etkilerini ayrica fonksiyonu kapsamak icin gerekli olan diger asal carpanlari bulmak icin bir asal carpanlar tablosu kullanilir Ornek1 Adim Asal carpanlarin bulunmasi Ilk olarak fonksiyonu bir tablo olarak yaziyoruz A B C D Fm0 0 0 0 0 0m1 0 0 0 1 0m2 0 0 1 0 0m3 0 0 1 1 0m4 0 1 0 0 1m5 0 1 0 1 0m6 0 1 1 0 0m7 0 1 1 1 0m8 1 0 0 0 1m9 1 0 0 1 xm10 1 0 1 0 1m11 1 0 1 1 1m12 1 1 0 0 1m13 1 1 0 1 0m14 1 1 1 0 xm15 1 1 1 1 1 Bu tablodan carpimlarin kanonik toplamini fonksiyonun bir olarak degerlendirdigi mintermleri onemsiz terimleri disarida birakarak toplayarak kolayca olusturabilirsiniz fA B C D A BCD ABC D AB CD ABC D ABC D ABCD Bu nedenle optimize etmek icin bir olarak degerlendirilen tum mintermler once bir minterm tablosuna yerlestirilir Onemsiz terimler de bu tabloya eklenir adlar parantez icindedir boylece mintermlerle birlestirilebilirler 1lerin sayisi Minterm Ikili Gosterimi1 m4 0100m8 10002 m9 1001m10 1010m12 11003 m11 1011 m14 11104 m15 1111 Bu noktada mintermleri diger mintermlerle birlestirmeye baslanabilir Iki terim yalnizca tek bir basamakla farklilik gosteriyorsa o basamak basamagin onemli olmadigini belirten bir tire ile degistirilebilir Artik birlestirilemeyecek terimler bir yildiz ile isaretlenmistir Ornegin 1000 ve 1001 100 verecek sekilde birlestirilebilir bu her iki mintermin de ilk hanenin 1 ve sonraki ikisinin 0 oldugunu ima ettigini gosterir 1lerin sayisi Minterm 0 kup 2 Boyut etkileri1 m4 0100 m 4 12 100 m8 1000 m 8 9 100 m 8 10 10 0 m 8 12 1 002 m9 1001 m 9 11 10 1m10 1010 m 10 11 101 m 10 14 1 10m12 1100 m 12 14 11 03 m11 1011 m 11 15 1 11m14 1110 m 14 15 111 4 m15 1111 Boyut 2 den Boyut 4 e gecerken ucuncu bir bit degeri olarak ele alin Ornegin 110 ve 100 1 0 i vermek uzere birlestirilebilir ca 110 ve 11 in 11 vermesi gibi ancak 110 ve 011 olamaz cunku 110 1110 tarafindan ima edilirken 011 degil Puf Noktasi Ilkini eslestirin 1lerin sayisi minterm 0 kup 2 Boyut etkileri 4 Boyut etkileri1 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 isleme daha fazla terim birlestirilemeyecek duruma gelene kadar devam edilmelidir Bu ornekteki terimlerin hicbiri daha fazla birlestirilemez 2 Adim Terimlerin hicbiri bundan daha fazla birlestirilemez bu nedenle bu noktada bir asal dolayli tablo olusturuyoruz Kenar boyunca henuz olusturulmus olan asal cikarimlar gider ve ust kisim boyunca daha once belirtilen mintermler gider Onemsiz terimler en uste yerlestirilmemistir gerekli girdiler olmadiklari icin bu bolumden cikarilmistir 4 8 10 11 12 15 A B C D m 4 12 1 0 0 m 8 9 10 11 1 0 m 8 10 12 14 1 0 m 10 11 14 15 1 1 Temel asal cikarimlari bulmak icin en ust sira boyunca ilerliyoruz Sadece bir iceren sutunlari aramamiz gerekiyor Bir sutunda yalnizca bir varsa bu minterm in yalnizca bir asal dolayli tarafindan kapsanabilecegi anlamina gelir Ornegin ilk sutunda minterm 4 ile yalnizca bir vardir Bu m 4 12 nin gerekli oldugu anlamina gelir Bu yuzden yanina bir yildiz koyuyoruz Minterm 15 te de sadece bir vardir dolayisiyla m 10 11 14 15 de esastir Artik bir iceren tum sutunlar kapsanmistir Ikinci asal implikant ucuncu ve dorduncu tarafindan kapsanabilir ve ucuncu asal implikeant ikinci ve birinci tarafindan kapsanabilir bu nedenle hicbiri zorunlu degildir Bir asal implikant gerekliyse beklendigi gibi onu minimize edilmis boole denklemine dahil etmek gerekir Bazi durumlarda temel asal cikarimlar tum mintermleri kapsamaz bu durumda cizelge indirgemesi icin ek prosedurler kullanilabilir En basit ek prosedur deneme yanilma yontemidir ancak daha sistematik bir yol Mevcut ornekte temel asal cikarimlar tum mintermleri islemez bu nedenle bu durumda temel cikarimlar bir denklem elde etmek icin iki temel olmayanlardan biriyle birlestirilebilir 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 islevsel olarak esdegerdir fA B C D A BC D AB C D AB C D AB CD AB CD ABC D ABCD ABCD Kaynakca 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 Quine W V 1 Kasim 1955 A Way to Simplify Truth Functions The American Mathematical Monthly 62 9 627 631 doi 10 1080 00029890 1955 11988710 ISSN 0002 9890 McCluskey E J Kasim 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 kaynagindan arsivlendi Erisim tarihi 21 Haziran 2021 McColl Hugh 1878 The Calculus of Equivalent Statements Third Paper Proceedings of the London Mathematical Society Ingilizce s1 10 1 16 28 doi 10 1112 plms s1 10 1 16 ISSN 1460 244X 24 Haziran 2021 tarihinde kaynagindan arsivlendi Erisim tarihi 21 Haziran 2021 a b Brown Frank Markham 1 Kasim 2010 McColl and Minimization History and Philosophy of Logic 31 4 337 348 doi 10 1080 01445340 2010 517387 ISSN 0144 5340 Blake Archie Haziran 1938 Corrections to Canonical expressions in Boolean algebra The Journal of Symbolic Logic Ingilizce 3 2 112 113 doi 10 2307 2267595 ISSN 0022 4812 25 Haziran 2021 tarihinde kaynagindan arsivlendi Erisim tarihi 21 Haziran 2021 Nelson Raymond J Mart 1955 Simplest normal truth functions The Journal of Symbolic Logic Ingilizce 20 2 105 108 doi 10 2307 2266893 ISSN 0022 4812 25 Haziran 2021 tarihinde kaynagindan arsivlendi Erisim tarihi 21 Haziran 2021 home Jellison Funeral Obituary for John Jack G Nordahl Obituary for John Jack G Nordahl Ingilizce 5 Mayis 2020 tarihinde kaynagindan arsivlendi Erisim tarihi 21 Haziran 2021 Fielder Daniel C Aralik 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 kaynagindan arsivlendi Erisim tarihi 21 Haziran 2021 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 kaynagindan arsivlendi Erisim tarihi 21 Haziran 2021