Konsensüs teoremi - Consensus theorem - Wikipedia

Değişken girdilerFonksiyon değerleri
xyz
00000
00111
01000
01111
10000
10100
11011
11111

İçinde Boole cebri, konsensüs teoremi veya fikir birliği kuralı[1] kimlik:

uzlaşma veya çözücü şartların ve dır-dir . Bu, bir terimde eksiz görünen ve diğerinde olumsuzlanan harfi hariç, terimlerin tüm benzersiz değişmezlerinin birleşimidir. Eğer olumsuzlanan bir terimi içerir (veya tam tersi), fikir birliği terimi yanlış; başka bir deyişle, fikir birliği terimi yoktur.

Birleşik çift bu denklemin:

Kanıt

Uzlaşma

uzlaşma veya fikir birliği terimi Bir terim değişmezi içerdiğinde, bir ayrışmanın iki bağlaçlı terimi tanımlanır ve diğeri gerçek , bir muhalefet. Fikir birliği, iki terimin birleşimidir ve her ikisini de çıkarır. ve ve tekrarlanan değişmez değerler. Örneğin, fikir birliği ve dır-dir .[2] Birden fazla muhalefet varsa fikir birliği tanımlanmamıştır.

Kuralın birleşik ikilisi için fikir birliği türetilebilir ve içinden çözüm çıkarım kuralı. Bu, LHS'nin RHS'den türetilebileceğini gösterir (eğer BirB sonra BirAB; değiştirme Bir RHS ve B ile (yz)). RHS, LHS'den basitçe şu yolla elde edilebilir: birleşik eliminasyon çıkarım kuralı. RHS → LHS ve LHS → RHS'den beri ( önermeler hesabı ), sonra LHS = RHS (Boole cebirinde).

Başvurular

Boole cebirinde, tekrarlanan fikir birliği, hesaplamak için bir algoritmanın özüdür. Blake kanonik formu bir formülün.[2]

İçinde dijital mantık bir devrede fikir birliği terimi dahil, ortadan kaldırabilir yarış tehlikeleri.[3]

Tarih

Konsensüs kavramı, 1937'de Archie Blake tarafından tanıtıldı. Blake kanonik formu.[4] 1954'te Samson ve Mills tarafından yeniden keşfedildi.[5] ve tarafından Quine 1955'te.[6] Quine, 'konsensüs' terimini icat etti. Robinson 1965'te hükümler için kullandı "çözüm ilkesi ".[7][8]

Referanslar

  1. ^ Frank Markham Brown, Boolean Muhakeme: Boolean Denklemlerinin Mantığı, 2. baskı 2003, s. 44
  2. ^ a b Frank Markham Brown, Boolean Muhakeme: Boolean Denklemlerinin Mantığı, 2. baskı 2003, s. 81
  3. ^ M. Rafiquzzaman, Sayısal Mantık ve Mikrodenetleyicilerin Temelleri6. baskı (2014), ISBN  1118855795, s. 75
  4. ^ "Boolean cebirinde kanonik ifadeler", Tez, Matematik Bölümü, Chicago Üniversitesi, 1937, J.C.C. Sembolik Mantık Dergisi 3: 2: 93 (Haziran 1938) doi:10.2307/2267634 JSTOR  2267634
  5. ^ Edward W. Samson, Burton E. Mills, Hava Kuvvetleri Cambridge Araştırma Merkezi, Teknik Rapor 54-21, Nisan 1954
  6. ^ Willard van Orman Quine, "Doğruluk işlevlerini basitleştirme sorunu", American Mathematical Monthly 59:521-531, 1952 JSTOR  2308219
  7. ^ John Alan Robinson, "Çözünürlük İlkesine Dayalı Makine Odaklı Mantık", ACM Dergisi 12:1: 23–41.
  8. ^ Donald Ervin Knuth, Bilgisayar Programlama Sanatı 4A: Kombinatoryal AlgoritmalarBölüm 1, s. 539

daha fazla okuma

  • Roth, Charles H. Jr. ve Kinney, Larry L. (2004, 2010). "Mantık Tasarımının Temelleri", 6. Baskı, s. 66ff.