Mantıksal bir işlevin birleştirici normal biçimi. "Ayrık matematik ders kitabı dnf, sdnf, knf, sknf

Herhangi bir mantıksal formül için, özdeş dönüşümlerin yardımıyla, ona eşdeğer sonsuz sayıda formül oluşturmak mümkündür. Mantık cebirinde, ana görevlerden biri kanonik formları (yani, tek bir kurala, bir kanona göre oluşturulmuş formüller) aramaktır.

Mantıksal bir fonksiyon değişkenlerin ayrılması, birleşimi ve olumsuzlanması yoluyla ifade edilirse, bu temsil biçimine normal denir.

Normal formlar arasında mükemmel normal formlar ayırt edilir (fonksiyonların benzersiz bir şekilde yazıldığı formlar).

Mükemmel Ayırıcı Normal Form (SDNF)

Tanım. Bir formül, bir dizi değişkenin birleşiminden veya olumsuzlamalarından oluşuyorsa, temel bağlaç olarak adlandırılır.

Örnekler: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

Tanım. Bir formül, tekrarlanmayan temel bağlaçların bir ayrımıysa, ayırıcı normal biçim (DNF) olarak adlandırılır.

DNF aşağıdaki biçimde yazılır: F 1 ∨ F 2 ∨ ... ∨ F n, burada F i bir temel bağlaçtır

Örnekler: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3, ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Tanım. k değişkenli bir mantıksal formül, aşağıdaki durumlarda mükemmel ayrık normal biçim (SDNF) olarak adlandırılır:
1) formül bir DNF'dir, burada her temel bağlaç x 1, x 2, ..., x k ve üzerinde k değişkenin birleşimidir. i. yer bu bağlaç ya x i değişkeni ya da onun olumsuzlamasıdır;
2) böyle bir DNF'deki tüm temel bağlaçlar ikili olarak farklıdır.

Örnek: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)

Mükemmel birleştirici normal form (SKNF)

Tanım. Bir formül, belirli sayıda değişkenin veya bunların olumsuzlamalarının ayrılmasıyla oluşturulmuşsa, temel ayrım olarak adlandırılır.

Örnekler: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

Tanım. Bir formül, tekrar etmeyen temel ayrımların bir birleşimi ise, birleşik normal biçim (CNF) olarak adlandırılır.

CNF aşağıdaki biçimde yazılır: F 1 ∧ F 2 ∧ ... ∧ F n, burada F i bir temel ayrımdır

Örnekler: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

Tanım. Aşağıdaki durumlarda k değişkenli bir mantıksal formüle mükemmel birleşik normal biçim (CDNF) denir:
1) formül CNF'dir, burada her bir temel ayrım, k değişken x 1, x 2, ..., x k değişkeninin bir ayrımıdır ve bu ayrımın i-inci yerinde ya x i değişkeni ya da onun olumsuzlamasıdır;
2) böyle bir CNF'deki tüm temel ayrımlar ikili olarak farklıdır.

Örnek: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)

dikkat, ki 0 veya 1'e özdeş olmayan herhangi bir mantıksal işlev, SDNF veya SKNF olarak temsil edilebilir..

Doğruluk tablosuna göre SDNF oluşturmak için algoritma

1. İşlev değerinin bire eşit olduğu tüm tablo satırlarını seçin.
2. Bu tür her satır için, tüm değişkenlerin birleşimini aşağıdaki gibi yazın: bu kümedeki bazı değişkenlerin değeri 1'e eşitse, o zaman değişkenin kendisini bağlaca dahil ederiz, aksi takdirde - olumsuzlaması.
3. Ortaya çıkan tüm bağlaçları ayırma işlemleriyle bağlarız.

Doğruluk tablosuna göre SKNF oluşturmak için algoritma

1. İşlev değerinin sıfıra eşit olduğu tüm tablo satırlarını seçin.
2. Bu tür her satır için, tüm değişkenlerin ayrımını aşağıdaki gibi yazın: bu kümedeki bazı değişkenlerin değeri 0'a eşitse, o zaman değişkenin kendisini bağlaca dahil ederiz, aksi takdirde - olumsuzlaması.
3. Ortaya çıkan tüm ayrılmaları bağlaç işlemleriyle bağlarız.

Algoritmaların analizi, doğruluk tablosunun satırlarının çoğunda işlevin değeri 0'a eşitse, mantıksal formülünü elde etmek için SDNF'yi, aksi takdirde - SKNF'yi oluşturmanın daha iyi olduğunu gösterir.

Örnek: Üç değişkenli bir mantıksal fonksiyonun doğruluk tablosu verildi. Yapı mantıksal formül bu işlevi uygulamak.

Çünkü doğruluk tablosunun çoğu satırında, fonksiyonun değeri 1'dir, sonra SKNF'yi oluştururuz. Sonuç olarak, aşağıdaki mantıksal formülü elde ederiz:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Ortaya çıkan formülü kontrol edelim. Bunu yapmak için fonksiyonun doğruluk tablosunu oluşturalım.

Orijinal doğruluk tablosunu ve mantıksal formül için oluşturulmuş olanı karşılaştırarak, fonksiyon değerlerinin sütunlarının aynı olduğunu not ediyoruz. Bu, mantıksal işlevin doğru şekilde oluşturulduğu anlamına gelir.

Normal form mantıksal formül, temel olmayan formüllerin ima, eşdeğerlik ve olumsuzlama işaretleri içermez.

Normal form iki şekilde gelir:

konjonktif normal form (CNF)- birkaç ayrılığın birleşimi, örneğin, $ \ left (A \ vee \ overline (B) \ vee C \ right) \ wedge \ left (A \ vee C \ sağ) $;

ayırıcı normal form (DNF)- çeşitli bağlaçların ayrılması, örneğin, $ \ left (A \ wedge \ overline (B) \ wedge C \ sağ) \ vee \ left (B \ wedge C \ sağ) $.

SKNF

Mükemmel birleştirici normal form (SKNF) üç koşulu karşılayan bir CNF'dir:

özdeş temel ayrımları içermez;

yan tümcelerin hiçbiri aynı değişkenleri içermez;

her temel ayrılma, verilen CNF'den her bir değişkeni içerir.

Aynı şekilde doğru olmayan herhangi bir Boole formülü SKNF'de gösterilebilir.

Doğruluk tablosuna göre SKNF oluşturma kuralları

Fonksiyonu 0 olan her bir değişken kümesi için toplam yazılır ve 1 değerine sahip değişkenler olumsuzlama ile alınır.

SDNF

Mükemmel Ayırıcı Normal Form (SDNF) üç koşulu karşılayan bir DNF'dir:

özdeş temel bağlaçlar içermez;

bağlaçların hiçbiri aynı değişkenleri içermez;

her temel bağlaç, verilen DNF'deki her değişkeni, ayrıca aynı sırada içerir.

Aynı şekilde yanlış olmayan herhangi bir Boole formülü, ayrıca SDNF'de benzersiz bir şekilde temsil edilebilir.

Doğruluk tablosuna göre SDNF oluşturma kuralları

Fonksiyonu 1'e eşit olan her bir değişken kümesi için çarpım yazılır ve 0 değerine sahip değişkenler olumsuzlama ile alınır.

SKNF ve SDNF bulma örnekleri

örnek 1

Doğruluk tablosuna göre mantıksal bir fonksiyon yazın:

Resim 1.

Çözüm:

SDNF'yi oluşturmak için kuralı kullanalım:

Şekil 2.

SDNF'yi alıyoruz:

SKNF'yi oluşturmak için kuralı kullanalım.

Basit bağlaç aranan bağlaç bir veya birkaç değişkenler, de Bugün nasılsın her biri değişken karşılar olumsuzluk daha fazla bir zamanlar (veya kendisi, veya ona olumsuzlama).

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

ayırıcı normal form(DNF) aranan ayrılma basit bağlaçlar.

Örneğin, ifade DNF'dir.

Kusursuz ayırıcı normal form(SDNF) aranan böyle ayırıcı normal form, de hangisi v Her bağlaç dahildir Tümü değişkenler verilen liste (veya kendileri, veya onların inkar), Dahası v bir ve Ses aynısıTamam.

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

CNF ve SKNF için de benzer tanımlar (bağlaçların ayrılma ile değiştirilmesi ve bunun tersi) geçerlidir. İşte tam formülasyonlar.

Basit ayrılma aranan ayrılma bir veya birkaç değişkenler, de Bugün nasılsın her biri değişken girer olumsuzluk daha fazla bir zamanlar (veya kendisi, veya ona olumsuzlama) Örneğin, bir ifade basit bir ayırmadır,

bağlaç normal form(CNF) aranan bağlaç basit ayrılıklar(örneğin, ifade CNF'dir).

Mükemmel bir birleşik normal biçim (SCNF), her basit ayrımın verilen listenin tüm değişkenlerini (kendilerini veya olumsuzlamalarını) ve aynı sırada içerdiği bir CNF'dir.

Örneğin, ifade SKNF'dir.

İşte bir formdan diğerine geçişler için algoritmalar. Doğal olarak, belirli durumlarda (belirli bir yaratıcı yaklaşımla), algoritmaların kullanımı, bu formun belirli bir türünü kullanan basit dönüşümlerden daha zahmetlidir:

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

Bu geçişin algoritması şu şekildedir: DNF'nin üzerine iki olumsuzluk koyuyoruz ve de Morgan kurallarını kullanarak (üst olumsuzluğa dokunmadan), DNF'nin olumsuzluğunu DNF'ye geri getiriyoruz. Bu durumda, parantezleri absorpsiyon kuralını (veya Blake'in kuralını) kullanarak açmanız gerekir. Elde edilen DNF'nin olumsuzlanması (üstte) (yine de Morgan kuralına göre) bize hemen CNF'yi verir:

Çıkarırsak, CNF'nin ilk ifadeden de elde edilebileceğini unutmayın. de parantez dışında;

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

Bu geçiş, parantezlerin basit bir şekilde açılmasıyla gerçekleştirilir (bu durumda yine absorpsiyon kuralı kullanılır)

Böylece DNF'yi elde ettik.

Ters geçiş (SDNF'den DNF'ye), DNF'yi en aza indirme sorunuyla ilişkilidir. Bu, Bölüm'de daha ayrıntılı olarak tartışılacaktır. 5, burada DNF'nin (veya SDNF'nin) Blake kuralına göre nasıl basitleştirileceğini göstereceğiz. Bu DNF'nin adı kısaltılmış DNF;

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

Bu kuralın uygulanması iki kısımdan oluşur:

DNF'deki ayrık terimler arasında terimler varsa , sonra tüm ayrılmaya terimi ekliyoruz İLE 1 İLE 2. Bu işlemi tüm olası terim çiftleri için birkaç kez yapıyoruz (sıralı olabilir, aynı anda olabilir) ve sonra olağan absorpsiyonu uygularız;

Eklenen terim DNF'de zaten mevcutsa, tamamen atılabilir, örneğin,

veya

Elbette, kısaltılmış DNF benzersiz olarak tanımlanmamıştır, ancak hepsi aynı sayıda harf içerir (örneğin, bir DNF vardır). , Blake'in kuralını ona uyguladıktan sonra, buna eşdeğer bir DNF'ye gelebilirsiniz):

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

Bazı basit bağlaçların bir değişkeni yoksa, örneğin, z, ifadeyi içine ekleyin ve ardından parantezleri genişletin (bu durumda, tekrarlanan ayrık terimler yazmayız). Örneğin:

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

Bu geçiş, öncekine benzer bir şekilde gerçekleştirilir: basit bir ayırmada bir değişken yoksa (örneğin, z, sonra ona bir ifade ekleriz (bu, ayrılığın kendisini değiştirmez), ardından dağıtım yasasını kullanarak parantezleri genişletiriz):

Böylece SKNF, CNF'den elde edilir.

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

Temel ayrılma kavramını tanıtalım.

Temel bir ayrım, formun bir ifadesidir.

Mantıksal bir fonksiyonun birleşik normal formu (CNF), herhangi bir sonlu ikili farklı temel ayrımların birleşimidir. Örneğin, mantıksal işlevler

temel ayrımların bağlaçlarıdır. Bu nedenle, birleştirici normal biçimde yazılırlar.

Analitik bir ifade tarafından verilen keyfi bir mantıksal işlev, aşağıdaki işlemler gerçekleştirilerek CNF'ye indirgenebilir:

Bir boolean ifadeye olumsuzlama işlemi uygulanırsa, tersine çevirme kuralının kullanılması;

Çarpma ile ilgili olarak dağılım aksiyomunu kullanarak:

Absorpsiyon işleminin kullanımları:

Tekrarlanan değişkenlerin ayrılmalarında veya bunların olumsuzlamalarında istisnalar;

Biri hariç tüm aynı temel ayrımların kaldırılması;

Aynı anda bir değişken içeren tüm yan tümceleri ve onun olumsuzlanmasını kaldırmak.

Listelenen işlemlerin geçerliliği, mantık cebirinin temel aksiyomlarından ve özdeşlik ilişkilerinden kaynaklanmaktadır.

Bağlaçlı normal biçim, içerdiği her temel ayrım, işlevin bağlı olduğu tüm değişkenleri doğrudan veya ters biçimde içeriyorsa, mükemmel olarak adlandırılır.

CNF'nin mükemmel CNF'ye dönüştürülmesi, aşağıdaki işlemler gerçekleştirilerek gerçekleştirilir:

Değişkenlerin bağlaçlarının her bir temel ayrımına eklemeler ve bu temel ayrıma dahil edilmemişlerse olumsuzlamaları;

Dağılım aksiyomunu kullanarak;

Biri hariç tüm özdeş temel ayrımların kaldırılması.

Herhangi bir mantıksal işlev, aşağıdakiler dışında mükemmel bir CNF'de temsil edilebilir:

aynı şekilde bire eşit(). Mükemmel bir CNF'nin ayırt edici bir özelliği, içindeki mantıksal bir fonksiyonun temsilinin benzersiz olmasıdır.

Mükemmel CNF işlevine dahil edilen temel ayrımlara sıfır bileşen denir. Mükemmel CNF'ye dahil edilen sıfırın her bileşeni, fonksiyonun sıfır kümesi olan değişkenlerin tek bir değer kümesinde kaybolur. Sonuç olarak, bir mantıksal fonksiyonun sıfır kümelerinin sayısı, mükemmel CNF'sine dahil edilen sıfır bileşenlerinin sayısı ile çakışır.

Mükemmel bir CNF'de sıfırın mantıksal fonksiyon sabiti, sıfırın 2n sabiti bağlacı ile temsil edilir. Mantıksal bir fonksiyonun SCNF'sini bir yazışma tablosuna göre derlemek için bir kural formüle edelim.

Fonksiyonun sıfıra eşit olduğu arama tablosunun her satırı için, tüm değişkenlerin temel bir ayrımı derlenir. Bu durumda, değeri sıfıra eşitse değişkenin kendisi ayırmaya, değeri bire eşitse olumsuzlamaya dahil edilir. Ortaya çıkan temel ayrımlar, bağlaç işaretiyle birleştirilir.

Örnek 3.4. Karşılık tablosu 2.2 tarafından verilen mantıksal fonksiyon z (x) için, mükemmel birleşik formu tanımlarız.

000 fonksiyonunun sıfır kümesine karşılık gelen tablonun ilk satırı için sıfırın bileşenini buluyoruz. İkinci, üçüncü ve beşinci satırlar için benzer işlemleri yaptıktan sonra, istenen mükemmel CNF fonksiyonunu tanımlarız:

Unutulmamalıdır ki, birim küme sayısı sıfır küme sayısını aşan işlevler için, bunları SKNF biçiminde yazmak daha kompakttır ve bunun tersi de geçerlidir.

Mantıksal işlevlerin normal biçimleri Bir Boole işlevinin Ki 2.7 biriminin bileşenlerinin bağlaç terimlerinin ayrılması biçiminde temsiline, bu işlevin DNF'sinin ayırıcı normal biçimi denir. Negatiflerle veya onlarsız alınan tüm mantıksal değişkenleri birer birer tam olarak içeriyorsa, bu fonksiyon temsili formuna bu fonksiyonun SDNF'sinin mükemmel ayırıcı normal formu denir. Gördüğünüz gibi, SDNF fonksiyonunu derlerken, fonksiyonun 1 değerini aldığı tüm mintermlerin bir ayrımını yapmanız gerekiyor.

Bu çalışma size uymadıysa sayfanın alt kısmında benzer çalışmaların bir listesi bulunmaktadır. Arama butonunu da kullanabilirsiniz

Ders 1.xx

Mantıksal işlevlerin normal biçimleri

Bir Boole fonksiyonunun bağlaç terimlerinin ayrılması şeklinde temsili (bileşen birim) ben

, (2.7)

aranan ayrık normal form(DNF) bu işlevin.

DNF'deki tüm bağlaç terimleri ise mintermler , yani, negatiflerle veya onlarsız alınan tüm mantıksal değişkenleri birer birer içerirler, o zaman fonksiyonun bu temsil biçimine denir.mükemmel ayırıcı normal form(SDNF ) bu işlevin. SDNF denir kusursuz çünkü ayrıktaki her terim tüm değişkenleri içerir; ayırıcı çünkü formüldeki ana işlem ayırmadır. Kavram "normal form”Belirli bir işlevi uygulayan bir formül yazmanın açık bir yolu anlamına gelir.

Yukarıdakilerin ışığında, Teorem 2.1 aşağıdaki teoremi ifade eder.

Teorem 2. Herhangi bir boole işlevi(aynı şekilde 0'a eşit değil) SDNF'ye gönderilebilir, .

Örnek 3. Tablo tanımlı bir fonksiyonumuz olsun f (x 1, x 2, x 3) (Tablo 10).

Tablo 10

Formül (2.6)'ya dayanarak, şunu elde ederiz:

Gördüğünüz gibi, SDNF fonksiyonunu derlerken, fonksiyonun 1 değerini aldığı tüm mintermlerin bir disjunction'ını oluşturmanız gerekiyor.

Ayrık terimlerin bir birleşimi şeklinde bir Boole fonksiyonunun temsili (sıfırın bileşeni) ben

, (2.8)

aranan bağlaç normal formu(CNF) bu işlev.

Tüm ayırıcı CNF terimleri ise makstermalar , yani, tam olarak mantıksal bir tane içerir fonksiyon değişkenleri olumsuzlamalı veya olumsuzlamasız alındığında, böyle bir CNF'ye denirmükemmel bağlaç normal form(SKNF) bu işlev.

Teorem 3. Herhangi bir boole işlevi(eşit değil 1) SKNF'de temsil edilebilir, dahası, böyle bir temsil sadece bir tanesidir..

Teoremin ispatı, aşağıdaki Shannon lemmasına bağlı olarak Teorem 2.1'in ispatına benzer şekilde gerçekleştirilebilir.

Shannon'ın lemması ... Herhangi bir boole işlevi f (x 1, x 2, ..., x m) m'den değişkenler aşağıdaki gibi temsil edilebilir:

. (2.9)

Mantıksal bir işlevin (DNF ve CNF) her iki temsil biçiminin de yeteneklerinde teorik olarak eşit olduğuna dikkat edilmelidir: herhangi bir mantıksal formül hem DNF'de (özdeş sıfır hariç) hem de CNF'de (aynı birim hariç) temsil edilebilir. ). Duruma bağlı olarak, işlevin şu veya bu biçimde temsili daha kısa olabilir.

Uygulamada, DNF en sık kullanılır, bu form bir kişiye daha tanıdık geldiğinden: çocukluktan itibaren, toplamları çarpmaktan çok eser eklemeye alışkındır (içinde son durum sezgisel olarak parantezleri açma ve böylece DNF'ye gitme arzusu vardır).

Örnek 4. f (x 1, x 2, x 3) fonksiyonu için ) tablo ile verilmiştir. 10, SKNF'ye yazın.

SDNF'den farklı olarak, SCNF'yi mantıksal bir fonksiyonun doğruluk tablosunda derlerken, fonksiyonun 0 değerini aldığı değişkenlerin kombinasyonlarına bakmanız ve karşılık gelen maksimum terimlerin birleşimini oluşturmanız gerekir,ancak değişkenler ters çevirme ile alınmalıdır:

SDNF işlevinden doğrudan SKNF'sine geçmenin veya tam tersinin imkansız olduğuna dikkat edilmelidir. Bu tür dönüşümlerin denenmesi, istenenlerin ters fonksiyonlarıyla sonuçlanır. SDNF ve SKNF işlevleri için ifadeler, yalnızca doğruluk tablosundan doğrudan elde edilebilir.

Örnek 5. f (x 1, x 2, x 3) fonksiyonu için ) tablo ile verilmiştir. 10, SDNF'den SKNF'ye geçmeyi deneyin.

Örnek 2.3'ün sonucunu kullanarak şunları elde ederiz:

Gördüğünüz gibi, genel inversiyon altında, örnek 2.4'te elde edilen fonksiyona göre ters olan mantıksal fonksiyonun SKNF'si elde edilir:

çünkü söz konusu fonksiyonun SKNF ifadesinde olmayan tüm maksimum terimleri içerir.

1. İşlemlerin (bkz. Tablo 9) kimlik (), toplam modulo 2 (), implication () özelliklerini kullanarak AND, OR, NOT (Boolean bazında) işlemlerine geçiyoruz.

2. Olumsuzlamanın özelliklerini ve de Morgan yasalarını kullanarak (bkz. Tablo 9), olumsuzlama işlemlerinin tüm ifadelere değil, yalnızca bireysel değişkenlere atıfta bulunduğunu elde ederiz.

3. AND ve OR mantıksal işlemlerinin özelliklerini kullanarak (bkz. Tablo 9), normal formu (DNF veya CNF) elde ederiz.

4. Gerekirse, mükemmel formlara gidin (SDNF veya SKNF). Örneğin, SKNF almak için genellikle şu özelliği kullanmanız gerekir:.

Örnek 6. Boole İşlevini SKNF'ye Dönüştür

Yukarıdaki algoritmanın adımlarını sırayla gerçekleştirerek şunları elde ederiz:

Absorpsiyon özelliğini kullanarak şunları elde ederiz:

Böylece, CNF fonksiyonlarını elde ettik. f (x 1, x 2, x 3 ). SKNF'sini elde etmek için, herhangi bir değişkeni olmayan her bir ayırma işlemini bu değişkenle ve olumsuzlamasıyla iki kez tekrarlamanız gerekir:

2.2.6. Boole İşlevlerini En Aza İndirme

Aynı mantıksal işlev şu şekilde temsil edilebildiğinden s kişisel formüller, ardından en basit pho'yu bulmak r Boole işlevini tanımlayan katır, Boole işlevini uygulayan mantık devresini basitleştirir. için. Minimum şekil lÖ jeolojik fonksiyonbazı temelde, fonksiyonun minimum sayıda süperpozisyonunu içerdiğini varsayabiliriz.İle parantezler dahil olmak üzere temel. Ancak, etkili bir yapı oluşturmak zordur. ben minimum parantezin elde edilmesiyle bu tür bir minimizasyon için bir algoritma biz.

Bir fonksiyonun minimum parantez formunun değil, minimum DNF'sinin arandığı kombinasyonel devrelerin sentezinde daha basit bir minimizasyon problemini ele alalım. Bu görev için basit, verimli algoritmalar var.

Quine'ın yöntemi

Küçültülecek işlev SDNF'de temsil edilir ve tüm olası eksik yapıştırma işlemleri ona uygulanır.

, (2.10)

ve sonra emilim

, (2.11)

ve bu adım çifti birden çok kez uygulanır. Böylece terimlerin sıralamasını düşürmek mümkündür. Bu prosedür, başka bir terime yapıştırılabilecek hiçbir terim kalmayana kadar tekrarlanır.

dikkat, ki Sol Taraf Denklem (2.10) daha basit ve daha açık bir şekilde hemen minimize edilebilir:

Bu yöntem kötüdür, çünkü böyle doğrudan bir minimizasyonla, kalan terimlerle yapıştırma ve emme için kullanım durumları olmasına rağmen, birleşik terimler ya ortadan kalkar.

Quine'ın yönteminin oldukça zaman alıcı olduğunu, bu nedenle dönüşümler sırasında hata yapma olasılığının oldukça yüksek olduğunu belirtmek gerekir. Ancak avantajı, teoride herhangi bir sayıda argüman için kullanılabilmesi ve değişken sayısı arttıkça dönüşümlerin daha az karmaşık hale gelmesidir.

Karnaugh harita yöntemi

Karnaugh haritaları (tablolar) yöntemi, mantıksal işlevleri en aza indirmenin daha görsel, daha az zaman alan ve güvenilir bir yoludur, ancak kullanımı pratik olarak 3-4 değişkenli, maksimum - 5-6 değişkenli işlevlerle sınırlıdır.

Karnot Haritası Bir Boole işlevinin doğruluk tablosunu temsil eden iki boyutlu bir tablo biçimidir; bu, mantıksal işlevlerin minimum DNF'sini grafiksel bir görsel biçimde kolayca bulmanızı sağlar. Tablonun her bir hücresi, minimize edilecek SDNF fonksiyonunun mintermiyle ilişkilidir ve böylece tablonun herhangi bir simetri ekseni, herhangi bir değişkende karşılıklı olarak ters olan bölgelere karşılık gelir. Tablodaki hücrelerin bu düzenlemesi, yapıştırma SDNF terimlerini belirlemeyi kolaylaştırır (sadece bir değişkenin ters çevirme işareti farklıdır): bunlar tabloda simetrik olarak düzenlenirler.

İki şeridin AND ve OR işlevleri için doğruluk tabloları ve Karnot haritaları e değişkenler Şekil 1'de gösterilmektedir. 8. Kartın her hücresine bir işaret yazılır a bu hücreye karşılık gelen argümandaki işlev n yoldaş

A) VE b) VEYA

Pirinç. sekiz. İki değişkenli fonksiyonlar için bir Karnot haritası örneği

Karnot haritasında And işlevi için yalnızca bir 1 vardır, bu nedenle hiçbir şeye yapıştırılamaz. Minimum fonksiyonun ifadesi yalnızca bu 1'e karşılık gelen terimi içerecektir:

f = xy.

VEYA işlevi için Karnot haritasında, zaten üç 1 vardır ve 1'i terime karşılık gelen iki yapıştırma çifti yapmak mümkündür. xy , iki kez kullanılır. Minimum fonksiyon ifadesinde, yapıştırılacak çiftler için terimleri yazmanız, bu çift için değişmeyen tüm değişkenleri bırakmanız ve değerlerini değiştiren değişkenleri çıkarmanız gerekir. Yatay yapıştırma için elde ederiz x , ve dikey için - y , sonuç olarak ifadeyi alırız

f = x + y.

İncirde. 9, üç değişkenli iki fonksiyonun doğruluk tablolarını gösterir ( a ) ve Karnot haritaları ( b ve c). fonksiyon f 2 ilkinden farklıdır, çünkü üç değişken grubu üzerinde tanımlanmamıştır (bu, tabloda bir kısa çizgi ile belirtilmiştir).

Bir fonksiyonun minimum DNF'sini belirlerken aşağıdaki kurallar kullanılır. 1 içeren tüm hücreler kapalı dikdörtgen alanlarda birleştirilir. k -küp, burada k = log 2 K, K - dikdörtgen bir alanda miktar 1. Ayrıca, her alan 2 hücreli bir dikdörtgen olmalıdır. k, burada k = 0, 1, 2, 3,…. k = için 1 dikdörtgen denir biri küptür ve 2 1 = 2 birim içerir; k = için 2 dikdörtgen 2 içerir 2 = 4 birim ve denir iki küp; k = 3 için 2 3'ün bölgesi = 8 birim denirüç küp ; vb. Dikdörtgenlerde birleştirilemeyen birimler çağrılabilir. sıfır küp yalnızca bir birim içeren (2 0 = 1). Hatta gördüğünüz gibi k alanlar kare olabilir (ancak gerekli değildir) ve bir tuhaflık için k - sadece dikdörtgenler.

Pirinç. 9. Üç değişkenli fonksiyonlar için bir Karnot haritası örneği

Bu alanlar üst üste gelebilir yani aynı hücreler girebilir. farklı bölgeler... Daha sonra fonksiyonun minimum DNF'si, karşılık gelen tüm bağlaç terimlerinin bir ayrımı olarak yazılır. k - küpler.

Karnot haritasında belirtilen bölgelerin her biri, minimum DNF'de bir bağlaçla temsil edilir; bu, içindeki argümanların sayısıdır. k toplam işlev argümanı sayısından daha az m , yani, bu sayı eşittir m - k ... Minimum DNF'nin her bir birleşimi, yalnızca haritanın karşılık gelen alanı için ya tersine çevrilmemiş ya da yalnızca tersine çevrilmiş değerlere sahip olduğu, yani değerlerini değiştirmediği argümanlarından oluşur.

Bu nedenle, haritanın hücrelerini kapalı alanlarla kaplarken, alan sayısının minimum olmasını ve her alanın mümkün olan en fazla sayıda hücreyi içermesini sağlamak için çaba gösterilmelidir, çünkü bu durumda minimum DNF'deki üye sayısı olacaktır. minimum olacak ve karşılık gelen bağlaçtaki argüman sayısı minimum olacaktır.

Şekil 1'deki Karnot harita işlevi için. 9, bulduk

çünkü üst kapalı alan için değişkenler x 1 ve x 2 alt için ters çevirme olmadan madde x 1 ters çevirme ile ilgili konular ve x 3 - ters çevirme yok.

Şekil 2'deki haritadaki tanımsız değerler. 9, v sıfır veya bir ile değiştirilerek genişletilebilir. Bu fonksiyon için her iki tanımsız değeri de 1 ile değiştirmenin daha avantajlı olduğu görülebilir. Farklı türde 2 küp. Daha sonra minimum DNF işlevi için ifade aşağıdaki gibi olacaktır:

Kapalı alanlar inşa ederken, Karnaugh haritasının hem yatay hem de dikey olarak bir silindire daraltılmasına izin verilir. r karşıt kenarların birleşimi ile eksenler r yani, Carnot simetri haritasının kenarlarında bulunan birimler H ancak birleştirilebilir.

Karnaugh haritaları farklı şekillerde çizilebilir (Şekil 10).

bir b

Pirinç. 10. Karnaugh haritaları çizmenin farklı yolları
3 değişkenli bir fonksiyon için

Ancak 2-4 değişkenli fonksiyonlar için Karnot haritalarının en uygun varyantları Şekil 2'de gösterilmiştir. 11 tablo, çünkü gösterdikleri her hücre için a tüm değişkenler doğrudan veya ters biçimdedir.

bir b

Pirinç. on bir. Karnot Haritalarının En Uygun Görüntüsü
fonksiyonlar için 3 ( a) ve 4 (b) değişken

5 ve 6 değişkenli fonksiyonlar için Şekil 2'de gösterilen yöntem. 10, v.

Pirinç. 12. 5 değişkenli bir fonksiyon için Karnot haritasının görüntüsü

Pirinç. on üç. 6 değişkenli bir fonksiyon için Karnot haritasının görüntüsü