1
/
5
formüller KNF'de:
¬ A ∧ (B ∨ C), (\ displaystyle \ neg A \ wedge (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 \ wedge B) \ vee C,)
A ∧ (B ∨ (D ∧ E)). (\ displaystyle A \ kama (B \ vee (D \ kama E))).
Ancak CNF'de olmayan bu 3 formül, CNF'de aşağıdaki formüllere eşdeğerdir:
¬ B ∧ ¬ C, (\ displaystyle \ neg B \ wedge \ neg C,)
(A ∨ C) ∧ (B ∨ C), (\ displaystyle (A \ vee C) \ wedge (B \ vee C),)
A ∧ (B ∨ D) ∧ (B ∨ E). (\ displaystyle A \ kama (B \ vee D) \ kama (B \ vee E).)
CNF'nin Oluşturulması
CNF oluşturmak için algoritma
1) Formülde yer alan tüm mantıksal işlemlerden kurtulun, bunları ana olanlarla değiştirin: bağlaç, ayrılma, olumsuzlama. Bu, eşdeğer formüller kullanılarak yapılabilir:
A → B = ¬ A ∨ B, (\ displaystyle A \ sağ ok B = \ neg A \ vee B,)
A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B). (\ displaystyle A \ leftrightarrow B = (\ neg A \ vee B) \ wedge (A \ vee \ neg B).)
2) İfadenin tamamına atıfta bulunan olumsuzlama işaretini, formüllere dayalı bireysel değişken ifadelere atıfta bulunarak olumsuzlama işaretleri ile değiştirin:
¬ (A ∨ B) = ¬ A ∧ ¬ B, (\ displaystyle \ neg (A \ vee B) = \ neg A \ wedge \ neg B,)
¬ (A ∧ B) = ¬ A ∨ ¬ B. (\ displaystyle \ neg (A \ wedge B) = \ neg A \ vee \ neg B.)
3) Çifte olumsuzlama işaretlerinden kurtulun.
4) Gerekirse bağlaç ve ayrılma işlemlerine dağılım özelliklerini ve soğurma formülünü uygulayın.
Bir CNF oluşturmaya bir örnek
CNF'ye formülü getirelim
F = (X → Y) ∧ ((¬ Y → Z) → ¬ X). (\ displaystyle F = (X \ sağ ok Y) \ kama ((\ neg Y \ sağ ok Z) \ sağ ok \ neg X).)
formülü dönüştürelim F (\ görüntü stili F) içermeyen bir formüle → (\ displaystyle \ sağ ok):
F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ ¬ Y ∨ Z) ∨ ¬ X). (\ displaystyle F = (\ neg X \ vee Y) \ kama (\ neg (\ neg Y \ sağ ok 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 olumsuzları 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) \ arazi (\ neg B \ lor C) \ arazi (B \ lor \ neg C).)
Basit ayrılma(ayrılma dahil) veya ayrık(İngilizce ayırma) bir veya daha fazla değişkenin veya bunların olumsuzlamalarının ayrılmasıdır ve her değişken bir defadan fazla gerçekleşmez.
Basit ayrılma
- tamamlayınız her değişken (veya olumsuzlaması) içinde tam olarak bir kez görünüyorsa;
- monoton değişken negatifler içermiyorsa.
Konjonktif normal form, CNF(eng. birleştirici normal biçim, CNF) bir Boole işlevinin birkaç basit tümcenin birleşimi biçimine sahip olduğu normal biçim.
CNF örneği:$ f (x, y) = (x \ lor y) \ arazi (y \ lor \ neg (z)) $
SKNF
Mükemmel bağlaç normal biçimi, SKNF(mükemmel konjonktif normal form, PCNF) aşağıdaki koşulları karşılayan bir CNF'dir:
- aynı basit ayrımlara sahip değil
- her basit ayrılma tamamlandı
SKNF örneği:$ f (x, y, z) = (x \ lor \ neg (y) \ lor z) \ arazi (x \ lor y \ lor \ neg (z)) $
teorem: Kimliğe eşit olmayan herhangi bir $ f (\ vec (x)) $ Boole işlevi için onu tanımlayan bir SKNF vardır.
Kanıt:$ \ neg (f) (\ vec x) $ fonksiyonunun tersi, üzerinde $ f (\ vec x) $'ın sıfıra eşit olduğu demetlerde bire eşit olduğundan, o zaman $ \ neg (f) için SDNF (\ vec x) $ aşağıdaki gibi yazılabilir:
$ \ neg (f) (\ vec x) = \ bigvee \ limitler_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n) ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ kama x_ (2) ^ (\ sigma_ (2)) \ kama ... \ kama x_ (n) ^ (\ sigma_ (n) ))) $, burada $ \ sigma_ (i) $, $ x_ (i) $ için olumsuzlamanın varlığını veya yokluğunu belirtir
İfadenin sol ve sağ taraflarının tersini bulun:
$ f (\ vec x) = \ neg ((\ bigvee \ limitler_ (f (x ^ (\ sigma_ (1)), x ^ (\ sigma_ (2)), ..., x ^ (\ sigma_ (n) ))) = 0) (x_ (1) ^ (\ sigma_ (1)) \ kama x_ (2) ^ (\ sigma_ (2)) \ kama ... \ kama x_ (n) ^ (\ sigma_ (n) ))))) $
Sağ tarafta elde edilen ifadeye de Morgan kuralını iki kez uygulayarak, şunu elde ederiz: $ f (\ vec x) = \ bigwedge \ limitler_ (f (x ^ (\ sigma_1), x ^ (\ sigma_2)), \ dots , x ^ (\ sigma_n)) = 0) $ $ (\ neg (x_1 ^ (\ sigma_1)) \ vee \ neg (x_2 ^ (\ sigma_2)) \ vee \ nokta \ vee \ neg (x_n ^ (\ sigma_n) ))) $
Son ifade SKNF'dir. SKNF, özdeş olarak sıfır olmayan herhangi bir fonksiyon için kurulabilen SDNF'den elde edildiğinden, teorem ispatlanmıştır.
Doğruluk tablosuna göre SKNF oluşturmak için algoritma
- Doğruluk tablosunda, fonksiyonun değerinin 0 $'a eşit olduğu değişken kümelerini işaretliyoruz.
- İşaretlenen her küme için, tüm değişkenlerin ayrılmasını aşağıdaki kurala göre yazarız: eğer bir değişkenin değeri $ 0 $ ise, o zaman değişkenin kendisi ayırmaya dahil edilir, aksi takdirde olumsuzlaması.
- Ortaya çıkan tüm ayrılmaları bağlaç işlemleriyle bağlarız.
Medyan için SKNF oluşturmaya bir örnek
1). Doğruluk tablosunda, fonksiyonun değerinin 0 $'a eşit olduğu değişken kümelerini işaretliyoruz.
| x | y | z | $ \ açı x, y, z \ aralık $ |
| 0
| 0
| 0
| 0
|
| 0
| 0
| 1
| 0
|
| 0
| 1
| 0
| 0
|
| 0
| 1
| 1
| 1
|
| 1
| 0
| 0
| 0
|
| 1
| 0
| 1
| 1
|
| 1
| 1
| 0
| 1
|
| 1
| 1
| 1
| 1
|
2). İşaretli her küme için, tüm değişkenlerin birleşimini aşağıdaki kurala göre yazarız: eğer bir değişkenin değeri $ 0 $ ise, o zaman değişkenin kendisini ayırmaya dahil ederiz, aksi takdirde olumsuzlaması.
| x | y | z | $ \ açı x, y, z \ aralık $ |
|
| 0
| 0
| 0
| 0
| $ (x \ lor y \ lor z) $ |
| 0
| 0
| 1
| 0
| $ (x \ lor y \ lor \ negatif (z)) $ |
| 0
| 1
| 0
| 0
| $ (x \ lor \ neg (y) \ lor z) $ |
| 0
| 1
| 1
| 1
|
|
| 1
| 0
| 0
| 0
| $ (\ neg (x) \ lor y \ lor z) $ |
| 1
| 0
| 1
| 1
|
|
| 1
| 1
| 0
| 1
|
|
| 1
| 1
| 1
| 1
|
|
3). Ortaya çıkan tüm ayrılmaları bağlaç işlemleriyle bağlarız.
$ \ langle x, y, z \ rangle = (x \ lor y \ lor z) \ arazi (\ neg (x) \ lor y \ lor z) \ arazi (x \ lor \ neg (y) \ lor z) \ arazi (x \ lor y \ lor \ negatif (z)) $
Bazı işlevler için SKNF örnekleri
Pierce'ın Oku: $ x \ aşağı ok y = (\ neg (x) \ lor (y)) \ kara ((x) \ lor \ neg (y)) \ kara (\ neg (x) \ lor \ neg (y) ) $
Özel veya: $ x \ oplus y \ oplus z = (\ neg (x) \ lor \ neg (y) \ lor z) \ arazi (\ neg (x) \ lor y \ lor \ neg (z)) \ arazi (x \ lor \ neg (y) \ lor \ neg (z)) \ arazi (x \ lor y \ lor z) $
Normal formlar mantıksal işlevler Bir Boole işlevinin Ki 2.7 biriminin bileşenlerinin bağlaç terimlerinin bir ayrımı şeklinde 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.
Çalışmanızı sosyal medyada paylaşınBu ç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, çünkü bu form bir kişiye daha aşinadır: çocukluktan itibaren, toplamları çarpmaktan ziyade iş eklemeye daha alışkındır (ikinci durumda, 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. NS 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.
Daha fazlasını düşünün Basit görev fonksiyonun minimum parantez formunun değil, minimum DNF'sinin arandığı kombinasyonel devrelerin sentezinde minimizasyon. 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.
Denklemin (2.10) sol tarafının daha basit ve daha açık bir şekilde hemen en aza indirilebileceğini unutmayın:
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 ve sayı olarak kullanılabilmesidir. dönüşüm değişkenleri o kadar karmaşık değil.
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ç. dokuz. Üç değişkenli fonksiyonlar için bir Karnot haritası örneği
Bu alanlar örtüşebilir yani aynı hücreler farklı alanlara girebilir. 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 daha küçük toplam fonksiyon argümanları 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ına ve her alanın mümkün olduğunca şunları içermesine dikkat edilmelidir: daha fazla hücreler, çünkü bu durumda minimum DNF'deki üye sayısı minimum olacak ve karşılık gelen bağlantıdaki argüman sayısı minimum olacaktır.
Şekil 1'deki Karnot harita işlevi için. dokuz, 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. dokuz, 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ı çeşit 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ç. on. 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. on, v.
Pirinç. 12. 5 değişkenli bir fonksiyon için Karnot haritasının görüntüsü
Pirinç. 13. 6 değişkenli bir fonksiyon için Karnot haritasının görüntüsü
İlginizi çekebilecek diğer benzer çalışmalar.
|
| 9020.
|
|
İKİLİLİK İLKESİ. DEĞİŞKENLERDE BOOLE FONKSİYONLARININ GENİŞLETİLMESİ. MÜKEMMEL AYIRICI VE BİRLEŞTİRİCİ NORMAL FORMLAR |
96,34 KB |
|
|
Bu teorem doğası gereği yapıcıdır, çünkü her işlevin onu mükemmel bir DN biçiminde uygulayan bir formül oluşturmasına izin verir. F. Bunu yapmak için, her fonksiyonun doğruluk tablosunda, içinde bulunduğu tüm satırları işaretliyoruz. |
| 6490.
|
|
Mantıksal fonksiyonların tanımı ve minimizasyonu |
187.21 KB |
|
|
Sözlü biçimde, bir fonksiyonun argümanları ile değerleri arasındaki ilişki ifade edilir. Örnek: Üç bağımsız değişkenli bir işlev, işlevin herhangi iki veya daha fazla bağımsız değişkeninin ne zaman eşit olduğunu değerlendirir. Tüm argüman değerleri kümeleri için fonksiyonun değerlerini içeren bir doğruluk tablosu oluşturmaktan oluşur. Bu örnekte doğruluk tablosuna göre DNF şeklinde böyle bir girdi alıyoruz... |
| 6707.
|
|
İlişkisel veritabanı tasarımı. Klasik yaklaşımda tasarım problemleri. Normalleştirme ilkeleri, normal formlar |
70,48 KB |
|
|
İlişkisel veritabanı projesi nedir Bu, tüm özniteliklerin tanımlandığı, ilişkinin birincil anahtarlarının belirtildiği ve ilişkinin bütünlüğü koruma ilkeleriyle ilgili bazı ek özelliklerinin belirtildiği, birbiriyle ilişkili ilişkiler kümesidir. Bu nedenle, veritabanının tasarımı çok doğru ve doğrulanmış olmalıdır. Aslında veritabanı projesi, uzun süre ve birçok kullanıcı tarafından kullanılacak olan geleceğin yazılım paketinin temelidir. |
| 4849.
|
|
Devlet işlevlerini yerine getirme biçimleri ve yöntemleri |
197.3 KB |
|
|
"İşlev" terimi, yerli ve yabancı Bilimsel edebiyat uzakta aynı değer... Felsefi ve genel sosyolojik terimlerle, "belirli bir ilişkiler sistemindeki bir nesnenin özelliklerinin dışsal bir tezahürü" olarak kabul edilir; bireylerin veya organların bir dizi olağan veya özel eylemleri olarak |
| 17873.
|
|
3. sınıf öğrencilerinde mantıksal UUD oluşumu |
846,71 KB |
|
|
Mantıksal oluşum sorununun psikolojik ve pedagojik yönleri evrensel eylem NS küçük okul çocukları Mantıksal UUD oluşumunu değerlendirme yöntemleri. Sistemde evrensel eğitim eylemlerinin geliştirilmesi için bir kavramın geliştirilmesi Genel Eğitim yeni sosyal ihtiyaçları karşılar. Modern eğitim sisteminin en önemli görevi, evrensel eğitim eylemleri UUD'nin oluşturulmasıdır. Evrensel eğitim eylemlerinin oluşumu, okul zorluklarını önlemenin anahtarıdır. |
| 2638.
|
|
Kendinden kilitlemeli sistemlerde mantıksal bağlantıların teknik uygulaması |
1.04 MB |
|
|
Kendinden kilitlemeli sistemlerde mantıksal bağlantıların teknik uygulaması Üç basamaklı ve dört basamaklı AB için kontrol algoritmalarının teknik uygulaması, röle kontağı ve temassız ayrık ve entegre mantık elemanları kullanılarak gerçekleştirilebilir ... |
| 10203.
|
|
ACİL DURUMLARIN OLUŞMASI VE GELİŞİMİNİN YAPISAL VE MANTIKSAL MODELLERİNİN OLUŞTURULMASI İÇİN RİSK ODAKLI YAKLAŞIM KAVRAMININ UYGULANMASI |
70,8 KB |
|
|
Genel risk analizi Çalışma ortamı, insan emeğini üretken ve fiziksel olarak daha az zor, ancak daha tehlikeli kılan güçlü teknolojik sistemler ve teknolojilerle doludur. Risk, tehlikeli bir durumun başlangıcının beklenmedikliği ve aniliği ile karakterize edilir. Her gün sayısız riskle karşı karşıyayız, ancak çoğu bunların bir kısmı potansiyel olarak kalır.Risk teorisi, bir kişi üzerindeki olumsuz etkinin yanı sıra sağlığına ve yaşamına verilen zararın nicel bir değerlendirmesini sağlar. |
| 11576.
|
|
İşlem kavramı, türleri ve biçimleri. Gerekli işlem şekline uyulmamasının sonuçları |
49,82 KB |
|
|
Geçersiz türde bir işlemin tanınması. Uygulanan değer dönem ödevi bir işlem kavramını basitleştirmek, yani daha erişilebilir bir biçimde kamuya sunmaktır. |
| 6213.
|
|
fonksiyon yaklaşımı |
3.08 MB |
|
|
İlki, analitik veya çizelgesel olarak verilen bazı fonksiyonların orijinaline yakın, ancak hesaplamalar için daha basit ve daha uygun başka bir fonksiyonla değiştirilmesinden ibarettir. Örneğin, bir işlevi bir polinomla değiştirmek, sayısal entegrasyon ve türev için basit formüller elde etmenizi sağlar; tablonun yaklaşık bir fonksiyonla değiştirilmesi, ara noktalarında değerler elde etmenizi sağlar. Ayrıca, belirli bir segmentteki bir fonksiyonun, bu segmentte verilen fonksiyonun değerlerinden ayrık bir nokta kümesinde kurtarılmasının ikinci sorunu ortaya çıkar. Bu sorunun cevabı... |
| 14058.
|
|
Devlet işlevlerinin evrimi |
29,99 KB |
|
|
Rus devleti hukuki bir olgu olarak, her şeyden önce, cumhuriyetçi bir yönetim biçimine sahip demokratik bir federal yasal sosyal laik devlet olarak temel anayasal niteliklerinin yanı sıra devletin amacının da gerçekleşmesini sağlamalıdır. Devletin temel amacı Sanat tarafından belirlenir. |
Önerme cebirinin ayırıcı ve birleştirici normal biçimleri.İfadelerin mantığının her işlevi için bir doğruluk tablosu oluşturabilirsiniz. Ters problem de her zaman çözülebilir. Birkaç tanım sunalım.
temel bağlaçlar (bağlaçlar) değişkenlerin bağlaçları veya her bir değişkenin en fazla meydana geldiği olumsuzlamaları olarak adlandırılır.
bir Zamanlar.
Ayrık normal form(DNF), temel bağlaçların ayrılması şeklinde olan bir formüldür.
temel cümleler (maddeleri) olumsuzlamalı veya olumsuzlamasız değişkenlerin ayrılmaları olarak adlandırılır.
Bağlaç normal formu(CNF), temel ayrımların birleşimi şeklinde olan bir formüldür.
Önermeler cebirinin her işlevi 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üştürme formüllerini kullanarak Boole işlemlerine gidin.
2. Yakın olumsuzlamalara sahip formüllere gidin, yani olumsuzlamaların değişkenlerin üzerinde olmadığı bir formüle gidin - de Morgan yasalarını uygulamak için.
3. Parantezleri genişletin - dağıtım yasalarını uygulayın.
4. Tekrarlanan terimleri bir kez alın - iktidarsızlık yasası.
5. Soğurma ve yarı soğurma yasalarını uygular.
Örnek 6. DNF formüllerini bulun:.
Boole cebri tutar dualite ilkesi... Aşağıdaki gibidir.
fonksiyon denir çift eğer fonksiyona. Onlar. verilen bir fonksiyona dual olan bir fonksiyon bulmak için, argümanların olumsuzlamalarından fonksiyonun olumsuzluğunu inşa etmek gerekir.
Örnek 7. Dual to fonksiyonunu bulun.
Arasında temel fonksiyonlar 1 mantığının cebiri dual ile 0'dır ve tam tersi, x dual ile x, dual, dual ve tersidir.
Fonksiyonu temsil eden formül F 1'de tüm bağlaçlar değiştirilirse
ayrılmada, birleşmede ayrılma, 1'den 0'a, 0'dan 1'e, sonra * dual fonksiyonunu temsil eden F * formülünü elde ederiz.
Konjonktif normal form (CNF), DNF için ikili bir kavramdır, bu nedenle şemaya göre inşa etmek kolaydır:
Örnek 8. Formülün CNF'sini 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 birleşik), mükemmel formların bir sınıfı SDNF ve SKNF ayırt edilebilir.
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 üründe yalnızca bir kez görünür.
Herhangi bir DNF, tüm değişkenleri içermeyen bağlaçları bölerek SDNF'ye indirgenebilir, ör. eksik değişken x i için toplama, dağıtım yasası kullanılarak çarpılır
Örnek 9. DNF örneği 6 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 X i bağlacı değişkeni içermeyen bir bağlaç terimi eklenerek ve dağılım yasası uygulanarak herhangi bir CNF, SKNF'ye indirgenebilir.
Örnek 10. CNF'yi SKNF'ye getirin:
SKNF'yi oluşturmak için şemayı kullanabilirsiniz
Örnek 11.Örnek 6'daki formül için SKNF'yi bulun.
Her işlevin SDNF'si vardır ve ayrıca benzersizdir. Her işlevin bir SKNF'si ve ayrıca tek işlevi vardır.
Çünkü SDNF ve SKNF, formüllerle benzersiz olarak tanımlanır, formülün doğruluk tablosuna göre oluşturulabilirler.
SDNF'yi oluşturmak için, F'nin 1 değerini aldığı satırları seçmek ve onlar için mükemmel elementer bağlaçları yazmak gerekir. Doğruluk tablosunun gerekli satırındaki bir değişkenin değeri bire eşitse, tam konjonktürde olumsuzlama olmadan, sıfır ise olumsuzlama ile alınır. Daha sonra mükemmel bağlaçlar (sayıları tablodakilerin sayısına eşittir) ayrılma işaretleri ile bağlanır.
SKNF'yi doğruluk tablosuna göre oluşturmak için, içinde F = 0 olan doğruları seçip mükemmel temel ayrımları yazmalı ve sonra bunları bağlaç işaretleriyle birleştirmelisiniz. Doğruluk tablosunun gerekli satırında (F = 0) değişkenin değeri sıfıra tekabül ediyorsa, o zaman mükemmel bir yan tümcede, bir ise - o zaman olumsuzlama ile alınır.
Örnek 12.Örnek 6'daki formül için doğruluk tablosunu kullanarak SDNF ve SKNF'yi bulun.
Tablo 14, yalnızca F = 10101101'in son değerini gösterir. Genişletilmiş bir doğruluk tablosu oluşturarak bu ifadenin geçerliliğine kendiniz ikna olmalısınız.
Tablo 14
