Mesajlar kafes - Posts lattice - Wikipedia

Hasse diyagramı Post'un kafesi.

İçinde mantık ve evrensel cebir, Mesajın kafesi gösterir kafes hepsinden klonlar iki öğeli bir kümede {0, 1}, sıralama ölçütü dahil etme. Adı Emil Post, 1941'de kafesin tam bir açıklamasını yayınlayan.[1] Post'un kafesinin göreceli basitliği, üç öğeli (veya daha büyük) bir küme üzerindeki klonların kafesine tam bir tezat oluşturuyor. sürekliliğin temel niteliği ve karmaşık bir iç yapı. Post'un sonucunun modern bir açıklaması Lau'da (2006) bulunabilir.[2]

Temel konseptler

Bir Boole işlevi veya mantıksal bağlaç, bir n-ary operasyon f: 2n2 bazı n ≥ 1, nerede 2 iki öğeli kümeyi {0, 1} gösterir. Belirli Boole işlevleri, projeksiyonlar

ve verilen m-ary işlevi f, ve n-ary işlevler g1, ..., gmbaşka bir tane inşa edebiliriz n-ary işlevi

onları aradı kompozisyon. Kompozisyon altında kapalı olan ve tüm projeksiyonları içeren bir dizi işlev, klon.

İzin Vermek B bir dizi bağlayıcı olabilir. Bir ile tanımlanabilen fonksiyonlar formül kullanma önerme değişkenleri ve bağlantı öğeleri B bir klon oluştur [B], gerçekten de içeren en küçük klondur B. Biz ararız [B] klon oluşturulmuş tarafından Bve şunu söyle B ... temel nın-nin [B]. Örneğin, [¬, ∧] tüm Boole işlevleridir ve [0, 1, ∧, ∨] monoton işlevlerdir.

İşlemleri kullanıyoruz ¬, Np, (olumsuzluk ), ∧, Kpq, (bağlaç veya buluşmak ), ∨, Apq, (ayrılma veya katılmak ), →, Cpq, (Ima ), ↔, Epq, (iki koşullu ), +, Jpq (münhasır ayrılma veya Boole halkası ilave ), ↛, Lpq,[3] (itiraz etmeme ),?: (üçlü koşullu operatör ) ve sabit tekli fonksiyonlar 0 ve 1. Ayrıca, eşik fonksiyonlarına ihtiyacımız var

Örneğin, th1n tüm değişkenlerin büyük ayrımıdır xbenve thnn büyük kavuşumdur. Özellikle önemli olan çoğunluk işlevi

Unsurlarını belirtiriz 2n (yani, doğruluk atamaları) vektör olarak: a = (a1, ..., an). Set 2n doğal taşır ürün Boole cebri yapı. Yani sipariş verme, karşılama, birleştirme ve diğer işlemler n-ary doğruluk atamaları noktasal olarak tanımlanır:

Klonların isimlendirilmesi

Kavşak rastgele sayıdaki klonların oranı yine bir klondur. Klonların kesişimini basit bir şekilde belirtmek uygundur. yan yana koyma yani klon C1C2 ∩ ... ∩ Ck ile gösterilir C1C2...Ck. Bazı özel klonlar aşağıda tanıtılmıştır:

  • M kümesidir monoton fonksiyonlar: f(a) ≤ f(b) her biri için ab.
  • D kümesidir öz-ikili fonksiyonlar: ¬f(a) = fa).
  • Bir kümesidir afin işlevler: tatmin edici işlevler
her biri için benn, a, b2n, ve c, d2. Eşdeğer olarak, işlevler şu şekilde ifade edilebilir: f(x1, ..., xn) = a0 + a1x1 + ... + anxn bazı a0, a.
  • U kümesidir esasen tekli fonksiyonlar, yani en fazla bir girdi değişkenine bağlı olan fonksiyonlar: bir ben = 1, ..., n öyle ki f(a) = f(b) her ne zaman aben = bben.
  • Λ kümesidir birleşik fonksiyonlar: f(ab) = f(a) ∧ f(b). Klon Λ bağlaçlardan oluşur tüm alt kümeler için ben / {1, ..., n} (boş bağlaç, yani 1 sabiti dahil) ve 0 sabiti.
  • V kümesidir ayırıcı fonksiyonlar: f(ab) = f(a) ∨ f(b). Eşdeğer olarak, V ayrılıklardan oluşur tüm alt kümeler için ben / {1, ..., n} (0 boş ayrımı dahil) ve 1 sabiti.
  • Herhangi k ≥ 1, T0k işlevler kümesidir f öyle ki
Dahası, yukarıda bir değişkenle sınırlanmış işlevler kümesidir: ben = 1, ..., n öyle ki f(a) ≤ aben hepsi için a.
Özel bir durum olarak, P0 = T01 kümesidir 0 koruma fonksiyonlar: f(0) = 0. Ayrıca, ⊤ düşünülebilir T00 boş buluşma hesaba katıldığında.
  • Herhangi k ≥ 1, T1k işlevler kümesidir f öyle ki
ve aşağıda bir değişkenle sınırlanmış işlevler kümesidir: ben = 1, ..., n öyle ki f(a) ≥ aben hepsi için a.
Özel durum P1 = T11 oluşur 1-koruyucu fonksiyonlar: f(1) = 1. Ayrıca, ⊤ düşünülebilir T10 boş katılım hesaba katıldığında.
  • Tüm fonksiyonların en büyük klonu ⊤, en küçük klon (sadece çıkıntılar içeren) ⊥ ile gösterilir ve P = P0P1 klonu sürekli koruyan fonksiyonlar.

Kafesin tanımı

Tüm klonların kümesi bir kapatma sistemi, dolayısıyla bir tam kafes. Kafes sayılabilecek kadar sonsuz ve tüm üyeleri sonlu olarak oluşturulur. Tüm klonlar aşağıdaki tabloda listelenmiştir.

Hasse diyagramı Post kafesinin
Kafesin orta kısmı
klonüslerinden biri
∨, ¬
P0∨, +
P1∧, →
Px ? y : z
T0k, k ≥ 2incikk+1, ↛
T0
PT0k, k ≥ 2incikk+1, x ∧ (yz)
PT0x ∧ (yz)
T1k, k ≥ 2inci2k+1, →
T1
PT1k, k ≥ 2inci2k+1, x ∨ (y + z)
PT1x ∨ (y + z)
M∧, ∨, 0, 1
MP0∧, ∨, 0
MP1∧, ∨, 1
MP∧, ∨
MT0k, k ≥ 2incikk+1, 0
MT0x ∧ (yz), 0
MPT0k, k ≥ 2incikk+1 için k ≥ 3,
maj, x ∧ (yz) için k = 2
MPT0x ∧ (yz)
MT1k, k ≥ 2inci2k+1, 1
MT1x ∨ (yz), 1
MPT1k, k ≥ 2inci2k+1 için k ≥ 3,
maj, x ∨ (yz) için k = 2
MPT1x ∨ (yz)
Λ∧, 0, 1
ΛP0∧, 0
ΛP1∧, 1
ΛP
V∨, 0, 1
VP0∨, 0
VP1∨, 1
VP
Dmaj, ¬
DPmaj, x + y + z
DMmaj
Bir↔, 0
AD¬, x + y + z
AP0+
AP1
APx + y + z
U¬, 0
UD¬
UM0, 1
YUKARI00
YUKARI11

Sekiz sonsuz ailenin aslında aynı zamanda k = 1, ancak bunlar tabloda ayrı olarak görünür: T01 = P0, T11 = P1, PT01 = PT11 = P, MT01 = MP0, MT11 = MP1, MPT01 = MPT11 = MP.

Kafes, her klonu haritalayan doğal bir simetriye sahiptir. C ikili klonuna Cd = {fd | fC}, nerede fd(x1, ..., xn) = ¬fx1, ..., ¬xn) ... de Morgan dual Boole işlevinin f. Örneğin, Λd = V, (T0k)d = T1k, ve Md = M.

Başvurular

Post tarafından verilen Boolean klonlarının tam sınıflandırması, Boole işlevlerinin sınıfları hakkında çeşitli soruların çözülmesine yardımcı olur. Örneğin:

  • Kafesin incelenmesi, maksimal klonların ⊤'den farklı olduğunu gösterir (genellikle Gönderinin sınıfları) M, D, A, P0, P1ve ⊤'nin her uygun alt klonu bunlardan birinde bulunur. Bir set olarak B bağlantı sayısı işlevsel olarak tamamlandı ancak ve ancak ⊤ üretirse, aşağıdaki karakterizasyonu elde ederiz: B beş Gönderi sınıfından birine dahil değilse işlevsel olarak tamamlanmıştır.
  • tatmin edilebilirlik sorunu Boole formülleri için NP tamamlandı tarafından Cook teoremi. Sorunun sınırlı bir versiyonunu düşünün: sabit bir sonlu küme için B bağlantıların B-SAT, verili olup olmadığını kontrol etmenin algoritmik problemi olabilir. B-formül tatmin edici. Lewis[4] bunu göstermek için Post'un kafesinin açıklamasını kullandı B-SAT NP-tamamlandı, eğer ↛ işlevi B (yani [B] ⊇ T0) ve diğer tüm durumlarda B-SAT polinom-zaman karar verilebilir.

Varyantlar

Post, başlangıçta modern klon tanımıyla değil, sözde yinelemeli sistemlerikame altında kapatılan işlemler dizisidir

değişkenlerin permütasyonu ve tanımlanması gibi. Temel fark, yinelemeli sistemlerin tüm projeksiyonları içermesi gerekmemesidir. Her klon yinelemeli bir sistemdir ve klon olmayan 20 boş olmayan yinelemeli sistem vardır. (Post ayrıca boş yinelemeli sistemi sınıflandırmanın dışında tuttu, bu nedenle diyagramının en küçük öğesi yok ve kafes olamıyor.) Başka bir alternatif olarak, bazı yazarlar bir kavramla çalışır. kapalı sınıf, kukla değişkenlerin tanıtımı altında kapalı yinelemeli bir sistem olan. Klon olmayan dört kapalı sınıf vardır: boş küme, sabit 0 işlevler kümesi, sabit 1 işlevler kümesi ve tüm sabit işlevler kümesi.

Bileşim tek başına karşılık gelen tekli sabit fonksiyondan sıfır fonksiyon üretmeye izin vermez, bu, Post'un sınıflandırmasında boş fonksiyonların klonlardan çıkarılmasının teknik nedenidir. Kısıtlamayı kaldırırsak, daha fazla klon elde ederiz. Yani her klon C En az bir sabit fonksiyon içeren Post'un kafesinde, daha az kısıtlayıcı tanım altında iki klona karşılık gelir: C, ve C tekli sürümleri olan tüm sıfır işlevlerle birlikte C.

Referanslar

  1. ^ E. L. Post, Matematiksel mantığın iki değerli yinelemeli sistemleri, Annals of Mathematics Studies, no. 5, Princeton University Press, Princeton 1941, 122 s.
  2. ^ D. Lau, Sonlu kümelerde fonksiyon cebirleri: Çok değerli mantık ve klon teorisi üzerine temel ders, Springer, New York, 2006, 668 s. ISBN  978-3-540-36022-3
  3. ^ Jozef Maria Bochenski (1959), rev., Albert Menne, ed. ve çev., Otto Bird, Kesin Matematiksel Mantık, New York: Gordon ve İhlal, Bölüm II, "Cümlelerin Mantığı", Böl. 3,23, "'Np, "Bölüm 3.32," 16 ikili doğruluk işlevcisi ", s. 10-11.
  4. ^ H. R. Lewis, Önerme taşları için karşılanabilirlik sorunları, Mathematical Systems Theory 13 (1979), s. 45–53.