Mantıksal bir fonksiyonun bağlaçlı normal formu. Mantıksal fonksiyonların normal biçimleri

Bağlaçlı normal form, teoremlerin otomatik olarak kanıtlanması için uygundur. Herhangi bir Boolean formülü CNF'ye indirgenebilir. Bunun için şunları kullanabilirsiniz: çift olumsuzlama kanunu, de Morgan kanunu, dağılım.

Ansiklopedik YouTube

• 1 / 5

  Formüller KNF'de:

  ¬ Bir ∧ (B ∨ C), (\displaystyle \neg A\kama (B\vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E) , (\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge ( D\vee\neg E),) A∧B. (\displaystyle A\kama B.)

  Formüller KNF'de değil:

  ¬ (B ∨ C) , (\displaystyle \neg (B\vee C),) (A ∧ B) ∨ C , (\displaystyle (A\kama B)\vee C,) bir ∧ (B ∨ (D ∧ E)) . (\displaystyle A\kama (B\vee (D\kama E))).)

  Ancak CNF'de olmayan bu 3 formül, CNF'deki aşağıdaki formüllere eşdeğerdir:

  ¬ B ∧ ¬ C , (\displaystyle \neg B\kama \neg C,) (A ∨ C) ∧ (B ∨ C) , (\displaystyle (A\vee C)\kama (B\vee C),) Bir ∧ (B ∨ D) ∧ (B ∨ E) . (\displaystyle A\kama (B\vee D)\kama (B\vee E).)

  CNF'nin inşaatı

  CNF oluşturmak için algoritma

  1) Formülde yer alan tüm mantıksal işlemlerden kurtulun ve bunları temel işlemlerle değiştirin: bağlaç, ayırma, olumsuzlama. Bu, eşdeğer formüller kullanılarak yapılabilir:

  A → B = ¬ A ∨ B , (\displaystyle A\rightarrow B=\neg A\vee B,) Bir ↔ B = (¬ Bir ∨ B) ∧ (A ∨ ¬ B) . (\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \neg B).)

  2) İfadenin tamamıyla ilgili olumsuzluk işaretini, aşağıdaki formüllere dayalı olarak bireysel değişken ifadeleriyle ilgili olumsuzluk işaretleriyle değiştirin:

  ¬ (A ∨ B) = ¬ A ∧ ¬ B , (\displaystyle \neg (A\vee B)=\neg A\wedge \neg B,) ¬ (A ∧ B) = ¬ Bir ∨ ¬ B . (\displaystyle \neg (A\kama B)=\neg A\vee \neg B.)

  3) Çift olumsuzluklardan kurtulun.

  4) Gerekirse dağılım ve soğurma formüllerinin özelliklerini birleşme ve ayrılma işlemlerine uygular.

  CNF yapımı örneği

  Formülü CNF’ye getirelim

  F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) . (\displaystyle F=(X\rightarrow Y)\wedge ((\neg Y\rightarrow Z)\rightarrow \neg X).)

  Formülü dönüştürelim F (\displaystyle F) içermeyen bir formüle → (\displaystyle \rightarrow ):

  F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ Y ∨ Z) ​​​​∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\kama (\neg (\neg Y\rightarrow Z)\vee \neg X)=(\neg X\vee Y)\kama (\neg (\neg \ neg Y\vee Z)\vee \neg X).)

  Ortaya çıkan formülde olumsuzlamayı değişkenlere aktarıyoruz ve çift negatifleri azaltıyoruz:

  F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\kama ((\neg Y\kama \neg Z)\vee \neg X).)

  Örneğin aşağıdaki formül 2-CNF'de yazılmıştır:

  (A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . (\ displaystyle (A\lor B)\land (\neg B\lor C)\land (B\lor \neg C).)

  Önermesel cebirin ayırıcı ve bağlayıcı normal formları. Her önermesel mantık fonksiyonu için bir doğruluk tablosu oluşturulabilir. Ters problem de her zaman çözülebilir. Birkaç tanım sunalım.

  Temel bağlaçlar (bağlaçlar) her değişkenin en fazla meydana geldiği değişkenlerin bağlaçları veya bunların olumsuzlamaları denir

  bir kere.

  Ayırıcı normal form(DNF), temel bağlaçların ayrılması biçiminde olan bir formüldür.

  Temel ayrımlar (ayrılmalar) olumsuzlamalı veya olumsuzlamasız değişkenlerin ayrımları denir.

  Bağlaç normal formu(CNF), temel ayrımların birleşimi biçiminde olan bir formüldür.

  Her önermeli cebir fonksiyonu için bir dizi ayırıcı ve birleştirici normal form bulunabilir.

  DNF oluşturmak için algoritma:

  1. Eşdeğer dönüşüm formüllerini kullanarak Boolean işlemlerine gidin.

  2. Yakın olumsuzluklara sahip formüllere gidin, yani olumsuzlukların değişkenlerin üstünde yer almadığı bir formüle gidin - De Morgan yasalarını uygulayın.

  3. Parantezleri açın - dağıtım yasalarını uygulayın.

  4. Tekrarlanan terimleri birer birer alın - eşitsizlik yasası.

  5. Absorbsiyon ve yarı absorbsiyon yasalarını uygulayabilecektir.

  Örnek 6. DNF formüllerini bulun: .

  Boole cebirinde bu doğrudur dualite ilkesi. Aşağıdaki gibidir.

  Fonksiyon çağrılır çift eğer işlevine. Onlar. Belirli bir fonksiyona ikili bir fonksiyon bulmak için, argümanların olumsuzlamalarından fonksiyonun olumsuzluğunu oluşturmak gerekir.

  Örnek 7. ile ikili fonksiyonunu bulun.

  Mantık cebirinin temel fonksiyonları arasında 1'in 0'a ikili olması ve bunun tersi, x'in ikili olması, x'in ikili olması, ikili olması ve tam tersidir.

  Fonksiyonu temsil eden F 1 formülünde tüm bağlaçları değiştirirsek

  ayrıklık üzerinde, bağlaç üzerinde ayrıklık, 0 üzerinde 1, 1 üzerinde 0, sonra * ikili fonksiyonunu temsil eden F* formülünü elde ederiz.

  Birleşik normal form (CNF), DNF için ikili bir kavramdır, dolayısıyla aşağıdaki şemaya göre kolayca oluşturulabilir:

  Örnek 8. CNF formülünü bulun: .

  Örnek 6'nın sonucunu kullanarak,

  Mükemmel ayırıcı ve mükemmel birleştirici normal formlar. Normal form türlerinin her birinde (ayırıcı ve bağlaçlı), mükemmel formlar SDNF ve SCNF sınıfını ayırt etmek mümkündür.

  Mükemmel bir temel bağlaç, olumsuzlamalı veya olumsuzlamasız tüm değişkenlerin mantıksal ürünüdür ve her değişken, çarpımda yalnızca bir kez görünür.

  Herhangi bir DNF, tüm değişkenleri içermeyen bağlaçların bölünmesiyle bir SDNF'ye indirgenebilir; eksik değişken için x i eklenerek dağıtım yasası kullanılarak çarpılır

  Örnek 9.Örnek 6'nın DNF'si için SDNF'yi bulun

  Mükemmel temel ayrım olumsuzlamalı veya olumsuzlamasız tüm değişkenlerin mantıksal toplamıdır ve her değişken toplama yalnızca bir kez dahil edilir.

  Herhangi bir CNF, bağlaç yoluyla herhangi bir Xi değişkeni içermeyen bir bağlaç terimi eklenerek ve dağıtım yasası uygulanarak SCNF'ye indirgenebilir.

  Örnek 10. KNF'yi SKNF'ye getirin:

  SCNF'yi oluşturmak için diyagramı kullanabilirsiniz.

  Örnek 11.Örnek 6'daki formül için SCNF'yi bulun.

  Her işlevin bir SDNF'si ve dahası benzersiz bir SDNF'si vardır. Her fonksiyonun bir SCNF'si ve dahası benzersiz bir SCNF'si vardır.

  Çünkü SDNF ve SKNF formüllerle benzersiz bir şekilde tanımlanır; formülün doğruluk tablosu kullanılarak oluşturulabilirler.

  Bir SDNF oluşturmak için F'nin 1 değerini aldığı satırları seçmek ve bunlar için mükemmel temel bağlaçları yazmak gerekir. Doğruluk tablosunun istenen satırındaki bir değişkenin değeri bire eşitse, mükemmel bir birliktelikte olumsuzlama olmadan, sıfırsa olumsuzlukla alınır. Daha sonra mükemmel bağlaçlar (sayıları tablodaki birim sayısına eşittir) ayırma işaretleriyle bağlanır.

  Doğruluk tablosu kullanarak bir SCNF oluşturmak için, içindeki F = 0 olan satırları seçmek, mükemmel temel ayrımları yazmak ve ardından bunları bağlaç işaretleriyle birleştirmek gerekir. Doğruluk tablosunun istenen satırında (F=0) değişkenin değeri sıfıra karşılık geliyorsa, mükemmel cümlede olumsuzlama olmadan, bir ise olumsuzlamayla alınır.

  Örnek 12.Örnek 6'daki formül için doğruluk tablosunu kullanarak SDNF ve SCNF'yi bulun.

  Tablo 14 yalnızca F=10101101 nihai değerini göstermektedir. Ayrıntılı bir doğruluk tablosu oluşturarak bu ifadenin geçerliliğini kendiniz doğrulamalısınız.

  Tablo 14

  X	sen	z

  Tanım 1.Konjonktif tek terimli (temel bağlaç) Değişkenlerin sayısı, bu değişkenlerin birleşimi veya olumsuzluklarıdır.

  Örneğin, temel bir bağlaçtır.

  Tanım 2.Ayırıcı tek terimli (temel ayrım) değişkenlerden ayrılması, bu değişkenlerin ayrılması veya olumsuzlanmasıdır.

  Örneğin, temel bir ayrımdır.

  Tanım 3. Belirli bir önermeli cebir formülüne eşdeğer olan ve temel birleşik monomların ayrıklığı olan bir formüle denir. ayırıcı normal form(DNF) bu formülün.

  Örneğin,– DNF.

  Tanım 4. Belirli bir önermeli cebir formülüne eşdeğer olan ve temel ayırıcı monomların birleşimi olan bir formüle denir. birleşik normal form(CNF) bu formülün.

  Örneğin, –KNF.

  Her önermeli cebir formülü için bir dizi ayırıcı ve birleştirici normal form bulunabilir.

  Normal formlar oluşturmak için algoritma

  Mantıksal cebirin eşdeğerliklerini kullanarak formüldeki tüm temel işlemleri değiştirin: bağlaç, ayırma, olumsuzlama:

  Çift olumsuzluklardan kurtulun.

  Gerekirse, dağılma ve soğurma formüllerinin özelliklerini birleşme ve ayrılma işlemlerine uygulayın.

  2.6. Mükemmel ayırıcı ve mükemmel birleştirici normal formlar

  Herhangi bir Boolean işlevi, DNF ve CNF biçiminde birçok temsile sahip olabilir. Bu temsiller arasında özel bir yer mükemmel DNF (SDNF) ve mükemmel CNF (SCNF) tarafından işgal edilmektedir.

  Tanım 1. Mükemmel ayırıcı normal form(SDNF), her birleştirici tek terimli kümedeki her değişkenin kendisini veya olumsuzunu tam olarak bir kez içerdiği bir DNF'dir.

  Yapısal olarak, bir DNF'ye indirgenmiş her önermeli cebir formülü için SDNF, aşağıdaki gibi tanımlanabilir:

  Tanım 2. Mükemmel ayırıcı normal form Bir önermeli cebir formülünün (SDNF), aşağıdaki özelliklere sahip olan DNF'si olarak adlandırılır:

  Tanım 3. Mükemmel birleştirici normal form(SCNF), her ayırıcı tek terimlinin kümedeki her değişkeni tam olarak bir kez içerdiği ve kendisinin ya da olumsuzlamasının göründüğü bir CNF'dir.

  Yapısal olarak, CNF'ye indirgenmiş her önermeli cebir formülü için SCNF aşağıdaki gibi tanımlanabilir.

  Tanım 4. Mükemmel birleştirici normal form Belirli bir önermeli cebir formülünün (SCNF) aşağıdaki özellikleri karşılayan bir CNF'si olarak adlandırılır.

  Teorem 1. Aynı şekilde yanlış olmayan değişkenlerin her Boolean işlevi, SDNF'de benzersiz bir şekilde temsil edilebilir.

  SDNF bulma yöntemleri

  1. yöntem

  2. yöntem

  formülün 1 değerini aldığı satırları seçin;

  Bağlaçların ayrıklığını, bir değişkenin 1 değeriyle bağlaca dahil edilmesi durumunda bu değişkenin yazılması, 0 değeriyle birlikte olumsuzlanması koşuluyla oluştururuz. SDNF'yi alıyoruz.

  Teorem 2. Aynı şekilde doğru olmayan değişkenlerin her Boolean fonksiyonu, SCNF'de ve benzersiz bir şekilde temsil edilebilir.

  SCNF'yi bulma yöntemleri

  1. yöntem– eşdeğer dönüşümleri kullanarak:

  2. yöntem– doğruluk tablolarını kullanma:

  formülün 0 değerini aldığı satırları seçin;

  ayrıklığa 0 değerinde bir değişken dahil edilirse bu değişkeni yazmamız, 1 değeri varsa bunun olumsuzlanması koşuluyla bir ayırma bağlacı oluştururuz. SKNF'yi alıyoruz.

  Örnek 1. CNF işlevlerini oluşturun.

  Çözüm

  Değişkenlerin dönüşüm yasalarını kullanarak "" bağlacını ortadan kaldıralım:

  = /de Morgan yasaları ve çift olumsuzlama/ =

  /dağıtım yasaları/ =

  Örnek 2. Formülü DNF'ye verin.

  Çözüm

  Mantıksal işlemleri ve kullanarak ifade edelim:

  = /olumsuzlamayı değişken olarak sınıflandıralım ve çift olumsuzları azaltalım/ =

  = /dağılım yasası/ .

  Örnek 3. Formülü DNF ve SDNF'ye yazın.

  Çözüm

  Mantık yasalarını kullanarak bu formülü yalnızca temel bağlaçların ayrımlarını içeren bir biçime indirgeyebiliriz. Ortaya çıkan formül istenen DNF olacaktır:

  SDNF'yi oluşturmak için bu formül için bir doğruluk tablosu oluşturalım:

  Formülün (son sütun) 1 değerini aldığı tablonun satırlarını işaretliyoruz. Bu tür her satır için, bu satırın değişkenleri kümesinde doğru olan bir formül yazıyoruz:

  satır 1: ;

  satır 3: ;

  satır 5: .

  Bu üç formülün ayrılması yalnızca 1, 3, 5. satırlardaki değişken kümelerinde 1 değerini alacaktır ve bu nedenle istenen mükemmel ayırıcı normal form (PDNF) olacaktır:

  Örnek 4. Formülü SKNF'ye iki şekilde getirin:

  a) eşdeğer dönüşümlerin kullanılması;

  b) doğruluk tablosunun kullanılması.

  Çözüm:

  İkinci temel ayrıklığı dönüştürelim:

  Formül şuna benziyor:

  b) Bu formül için bir doğruluk tablosu hazırlayın:

  Formülün (son sütun) 0 değerini aldığı tablonun satırlarını işaretliyoruz. Bu tür her satır için, bu satırın değişkenleri kümesinde doğru olan bir formül yazıyoruz:

  hat 2: ;

  satır 6: .

  Bu iki formülün birleşimi yalnızca 2. ve 6. satırlardaki değişken kümelerinde 0 değerini alacaktır ve bu nedenle istenen mükemmel birleşik normal form (PCNF) olacaktır:

  Bağımsız çözüm için sorular ve görevler

  1. Eşdeğer dönüşümleri kullanarak formülleri DNF'ye düşürün:

  2. Eşdeğer dönüşümleri kullanarak formülleri CNF'ye getirin:

  3. İkinci dağıtım yasasını kullanarak DNF'yi CNF'ye dönüştürün:

  A) ;

  4. Verilen DNF'leri SDNF'lere dönüştürün:

  5. Verilen CNF'yi SCNF'ye dönüştürün:

  6. Verilen mantıksal formüller için SDNF ve SCNF'yi iki şekilde oluşturun: eşdeğer dönüşümler kullanarak ve doğruluk tablosu kullanarak.

  B) ;

  Basit bağlaç isminde bağlaç bir veya birçok değişkenler, en Bu her biri değişken buluşuyor Olumsuz Daha bir zamanlar (veya kendini, veya o olumsuzlama).

  Örneğin basit bir bağlaçtır,

  ayırıcı normal şekil(DNF) isminde ayrılık basit bağlaçlar.

  Örneğin ifade DNF'dir.

  Mükemmel ayırıcı normal şekil(SDNF) isminde bunun gibi ayırıcı normal biçim, en Hangi V Her bağlaç dahil Tüm değişkenler verildi liste (veya kendileri, veya onların inkar), Ve V bir Ve hacim veyaTamam.

  Örneğin ifade DNF'dir ancak SDNF değildir. İfade SDNF'dir.

  Benzer tanımlar (bağlaç yerine ayrım ve tam tersi) CNF ve SKNF için de geçerlidir. Tam ifadesini verelim.

  Basit ayrılık isminde ayrılık bir veya birçok değişkenler, en Bu her biri değişken dahil Olumsuz Daha bir zamanlar (veya kendini, veya o olumsuzlama).Örneğin, ifade basit bir ayrımdır,

  Bağlaç normal şekil(KNF) isminde bağlaç basit ayrılıklar(örneğin ifade CNF'dir).

  Mükemmel bir birleşik normal form (PCNF), her basit ayrışımın belirli bir listedeki tüm değişkenleri (kendileri veya olumsuzları) ve aynı sırada içerdiği bir CNF'dir.

  Örneğin, ifade SKNF'dir.

  Bir formdan diğerine geçiş için algoritmalar sunalım. Doğal olarak, belirli durumlarda (belirli bir yaratıcı yaklaşımla), algoritmaların kullanımı, belirli bir formun belirli bir türünü kullanan basit dönüşümlerden daha fazla emek yoğun olabilir:

  a) DNF'den CNF'ye geçiş

  Bu geçişin algoritması şu şekildedir: DNF'nin üstüne iki olumsuzlama koyarız ve De Morgan'ın kurallarını kullanarak (üstteki olumsuzlamaya dokunmadan), DNF'nin olumsuzluğunu tekrar DNF'ye indiririz. Bu durumda parantezleri emilim kuralını (veya Blake kuralını) kullanarak açmanız gerekir. Ortaya çıkan DNF'nin olumsuzluğu (üst) (yine de Morgan kuralına göre) bize hemen CNF'yi verir:

  Çıkarırsak CNF'nin orijinal ifadeden de elde edilebileceğini unutmayın. en parantezlerin ötesinde;

  b) CNF'den DNF'ye geçiş

  Bu geçiş basitçe parantezlerin açılmasıyla gerçekleştirilir (yine soğurma kuralı kullanılır)

  Böylece DNF'yi aldık.

  Ters geçiş (SDNF'den DNF'ye) DNF'nin en aza indirilmesi sorunuyla ilişkilidir. Bu konu bölümde daha ayrıntılı olarak ele alınacaktır. Şekil 5'te, burada DNF'nin (veya SDNF'nin) Blake kuralına göre nasıl basitleştirileceğini göstereceğiz. Bu tür DNF denir kısaltılmış DNF;

  c) DNF (veya SDNF) kısaltması: kural Blake'in

  Bu kuralın uygulanması iki bölümden oluşur:

  DNF'deki ayrık terimler arasında terimler varsa , sonra tüm ayrıklığa terimi ekliyoruz İLE 1 İLE 2. Bu işlemi tüm olası terim çiftleri için birkaç kez (muhtemelen sırayla veya aynı anda) gerçekleştiriyoruz ve ardından normal soğurma uyguluyoruz;

  Eklenen terim zaten DNF'de yer alıyorsa, tamamen atılabilir, örneğin:

  veya

  Tabii ki, kısaltılmış DNF benzersiz bir şekilde tanımlanmamıştır, ancak hepsi aynı sayıda harf içermektedir (örneğin, DNF vardır) Blake kuralı uygulandıktan sonra buna eşdeğer bir DNF elde edilebilir):

  c) DNF'den SDNF'ye geçiş

  Örneğin, bazı basit bağlaçlarda bir değişken eksikse, z, içine ifadeyi ekleyin ve ardından parantezleri açın (yinelenen ayrık terimler yazmıyoruz). Örneğin:

  d) KNF'den SKNF'ye geçiş

  Bu geçiş öncekine benzer bir şekilde gerçekleştirilir: eğer basit bir ayırmada bazı değişkenler eksikse (örneğin, z, sonra ona bir ifade ekliyoruz (bu, ayrılığın kendisini değiştirmez), ardından dağıtım yasasını kullanarak parantezleri açıyoruz:

  Böylece SKNF, CNF'den elde edildi.

  Minimum veya azaltılmış CNF'nin genellikle karşılık gelen DNF'den elde edildiğine dikkat edin.

  Standart temel. Temel formüller değişmez değerlerdir. Temel bağlaç (ayrılma). Ayırıcı (bağlaçlı) normal form ve mükemmel form. Teorem: 0'dan (1'den) farklı herhangi bir Boole fonksiyonu SDNF (SCNF) biçiminde temsil edilebilir. Standart temelin eksiksizliği. Tam baz örnekleri: Zhegalkin temeli, Schaeffer vuruşu, Peirce oku.

  Standart temel Boole cebirinin üç temel işleminden oluşan bir kümedir: toplama (birleştirme), çarpma (kesişme) ve olumsuzlama.

  İşte arayacağız gerçek x değişkeni veya onun olumsuzu x ve xˆ'yi gösterir. Farklı değişkenler tarafından tanımlanan birkaç değişmezin Boolean kesişimi, yani. X = xˆ 1 xˆ 2 formunun ifadesi. . . xˆl denir temel bağlaç . Tüm değişkenlerin farklı olması gerekliliği aşağıdaki şekilde belirlenir. Bağlaç birkaç özdeş değişmez değer içeriyorsa, bağlacın değişme, birleşme ve eşgüçlülüğü nedeniyle, eşdeğer formüle geçerek yalnızca bir değişmez değer bırakmak mümkündür (örneğin, x 1 x 1 = x 1). Eğer bağlaç bir değişken ve onun olumsuzlanmasını içeriyorsa, x x = 0 olduğundan ve herhangi bir Y formülü için Y x x = 0 olduğundan formül 0 sabitine eşdeğerdir.

  Birkaç temel bağlacın ayrılmasına denir ayırıcı normal form , veya DNF . Örneğin,

  x 1 x 3 + x 2 x 3 x 4 + x 1 x 2 x 3 x 5 .

  Belirli bir DNF'nin her temel birleşimindeki değişkenlerin bileşimi aynıysa, o zaman DNF denir mükemmel . Verilen örnek mükemmel olmayan bir DNF'dir. Tam tersine formül

  x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4 +x 1 x 2 x 3 x 4

  mükemmel bir form var.

  Boolean cebirinde toplama ve çarpma simetrik işlemler olduğundan ve toplamayı her zaman çarpma olarak, çarpmayı da toplama olarak yorumlayabildiğiniz için ikili bir kavram vardır - birleşik normal form (KNF ), temel ayrımların bir birleşimi olan ve mükemmel bağlaç formu (SKNF ). Simetrik yarı halkalar için dualite ilkesinden, DNF ile ilgili herhangi bir ifadenin, toplamanın (ayrılma) çarpma ile, çarpmanın (bağlaç) toplama ile, sabit 0'ın sabit 1 ile, sabit ile değiştirilmesiyle elde edilen CNF ile ilgili ikili bir ifadeyle yanıtlandığı sonucu çıkar. 1 sabiti ile 0, ikili (ters) sıralı sıra ilişkisi. Bu nedenle, yalnızca DNF'yi incelemeye odaklanacağız.

  Teorem 1.4. 0 sabiti dışındaki herhangi bir Boolean işlevi, bir SDNF olarak temsil edilebilir.

  ◀X σ derken σ = 1 ise x formülünü, σ = 0 ise x formülünü kastettiğimiz konusunda hemfikir olalım. f(y 1 , . . , y n) fonksiyonu (t) vektörü üzerinde 1 değerini alsın. 1 , . . . , t n ) (böyle bir vektöre denir kurucu birim ). Daha sonra temel bağlaç da bu kümede 1 değerini alır, ancak diğer tüm n boyutlu Boolean vektörlerinde kaybolur. Formülü düşünün

  burada toplam (birleşim), verilen fonksiyonun 1 değerini aldığı argüman değerlerinin tüm kümelerine (t 1, . . ., t n) kadar uzanır. Bu tür kümelerin kümesinin boş olmadığına dikkat edin, dolayısıyla toplam en az bir terim içerir.

  Formül Φ'nin bunlar için ve yalnızca söz konusu fonksiyonun 1 olduğu değişkenlerin değerleri için 1 olduğunu görmek kolaydır. Bu, Ψ formülünün f fonksiyonunu temsil ettiği anlamına gelir.

  Sonuç 1.1. Standart temel tamamlandı.

  ◀ Aslında, eğer bir fonksiyon 0 sabiti değilse, o zaman standart bir temele dayalı bir formül olan SDNF biçiminde de temsil edilebilir. 0 sabiti örneğin f(x 1, x 2, . . ., x n) = x 1 x 1 formülüyle temsil edilebilir.

  Örnek 1.2.Üç değişkenli m(x 1, x 2, x 3) (Tablo 1.4) adlı bir fonksiyonu düşünün. çoğunluk işlevi ̆. Bu işlev, bağımsız değişkenlerinin yarısından fazlası 1 değerine sahipse 1 değerini alır. Bu nedenle buna genellikle oylama işlevi denir. Bunun için bir SDNF oluşturalım.

  Standart temelin eksiksizliği, diğer eksiksiz işlev sistemlerinin seçilmesini mümkün kılar. F kümesinin tamlığı aşağıdaki hususlarla belirlenebilir. Üç standart veri yolu fonksiyonunun her birinin F üzerinde bir formülle temsil edilebildiğini varsayalım. Daha sonra Teorem 1.3'e göre F özdeşliği tamamlanmış olacaktır.

  Örnek 1.3. Modulo 2 toplama, çarpma ve sabit 1 işlemleri kümesine denir Zhegalkin temeli . Toplama modulo 2 ve çarpma Z2 halkasının temel işlemleridir; bunların yardımıyla oluşturulan ifadeler Z2 halkası üzerindeki polinomlardır. Bu durumda sabit 1 serbest terimi yazmak için gereklidir. xx = x olduğundan, polinomdaki tüm faktörlerin derecesi 1'dir. Bu nedenle, bir polinom yazarken derece kavramı olmadan da yapabilirsiniz. Zhegalkin esasına göre formül örnekleri:

  xy⊕x⊕y, x⊕1, xyz⊕xz⊕x⊕y⊕1.

  Böyle herhangi bir formüle Zhegalkin polinomu denir. Aslında Zhegalkin polinomu Z2 halkası üzerinde bir polinomdur.

  Standart bazın toplama ve olumsuzlama işlemlerini temsil eden Zhegalkin temeli üzerinde formüller oluşturmak zor değildir (iki bazın çarpımı yaygındır):

  x+y=x⊕y⊕xy, x =x⊕1.

  Bu nedenle Zhegalkin temeli tam bir settir.
  Herhangi bir Boole fonksiyonu için Zhegalkin polinomunun benzersiz bir şekilde tanımlandığı gösterilebilir.

  (daha doğrusu terimlerin sırasına göre). Az sayıda değişken içeren Zhegalkin polinomunun katsayıları belirsiz katsayılar yöntemi kullanılarak bulunabilir.

  Örnek 1.4. Tek bir fonksiyon kümesini ele alalım: Schaeffer vuruşu*. Bu set, aşağıdaki kolaylıkla doğrulanabilir kimliklerle tamamlanmıştır:

  x =x|x, xy=x|y =(x|y)|(x|y), x+y=x |y =(x|x)|(y|y).

  Örnek 1.5. Tek bir fonksiyondan oluşan Peirce oku da tamdır. Bunun testi Schaeffer felç vakasına benzer. Ancak bu sonuca simetrik yarı halkalar için dualite ilkesi temel alınarak da ulaşılabilir.

  *Schaeffer'in felci ikili bir operasyondur ancak ilişkisel değildir. Bu nedenle infix formunu kullanırken dikkatli olmalısınız: sonuç, işlem sırasına bağlıdır. Bu durumda, parantez kullanarak işlem sırasının açıkça belirtilmesi önerilir; örneğin write (x | y) | z, x değil | y | z, her iki form da eşdeğer olmasına rağmen.