Spójna postać normalna funkcji logicznej. „Podręcznik matematyki dyskretnej dnf, sdnf, knf, snf

Dla dowolnej formuły logicznej, za pomocą identycznych przekształceń, można skonstruować nieskończenie wiele równoważnych jej formuł. W algebrze logiki jednym z głównych zadań jest poszukiwanie form kanonicznych (czyli formuł skonstruowanych według jednej reguły, kanonu).

Jeśli funkcja logiczna jest wyrażona przez alternatywę, koniunkcję i negację zmiennych, to ta forma reprezentacji nazywana jest normalną.

Wśród form normalnych wyróżnia się doskonałe formy normalne (takie, w których funkcje są zapisane w unikalny sposób).

Idealna dysjunktywna forma normalna (SDNF)

Definicja. Formuła nazywana jest koniunkcją elementarną, jeśli tworzy ją koniunkcja wielu zmiennych lub ich negacji.

Przykłady: y, ¬ y, x 1 ∧ ¬ x 2 ∧ x 3 ∧ x 4

Definicja. Formuła nazywana jest rozłączną formą normalną (DNF), jeśli jest rozłączeniem niepowtarzających się elementarnych spójników.

DNF zapisujemy w postaci: F 1 ∨ F 2 ∨ ... ∨ F n, gdzie F i jest koniunkcją elementarną

Przykłady: ¬ x 1 ∧ x 2 ∨ x 1 ∧ ¬ x 2 ∨ x 1 ∧ ¬ x 2 ∧ x 3, ¬ y 1 ∨ y 1 ∧ y 2 ∨ ¬ y 2

Definicja. Formuła logiczna w k zmiennych nazywana jest idealną rozłączną postacią normalną (SDNF), jeśli:
1) formuła jest DNF, w której każda elementarna koniunkcja jest koniunkcją k zmiennych x 1, x 2, ..., x k i dalej i-te miejsce ta koniunkcja jest albo zmienną x i, albo jej negacją;
2) wszystkie elementarne spójniki w takim DNF są parami różne.

Przykład: (¬ x 1 ∧ x 2 ∧ x 3) ∨ (x 1 ∧ ¬ x 2 ∧ x 3) ∨ (x 1 ∧ x 2 ∧ ¬ x 3)

Idealna spojówka normalna (SKNF)

Definicja. Formuła nazywana jest alternatywą elementarną, jeśli jest utworzona przez alternatywę pewnej liczby zmiennych lub ich negacji.

Przykłady: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3

Definicja. Formuła nazywana jest koniunkcyjną formą normalną (CNF), jeśli jest koniunkcją niepowtarzających się elementarnych dysjunkcji.

CNF ma postać: F 1 ∧ F 2 ∧ ... ∧ F n, gdzie F i jest alternatywą elementarną

Przykłady: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)

Definicja. Formuła logiczna w k zmiennych nazywana jest idealną spójną postacią normalną (CDNF), jeśli:
1) formuła to CNF, w której każda elementarna alternatywa jest alternatywą k zmiennych x 1, x 2, ..., x k, a na i-tym miejscu tej alternatywy znajduje się albo zmienna x i albo jej negacja;
2) wszystkie elementarne dysjunkcje w takim CNF są parami różne.

Przykład: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)

Zauważ, że każda funkcja logiczna, która nie jest identycznie równa 0 lub 1, może być reprezentowana jako SDNF lub SKNF.

Algorytm konstruowania SDNF zgodnie z tabelą prawdy

1. Zaznacz wszystkie wiersze tabeli, w których wartość funkcji jest równa jeden.
2. Dla każdego takiego wiersza zapisz koniunkcję wszystkich zmiennych w następujący sposób: jeżeli wartość jakiejś zmiennej w tym zbiorze jest równa 1, to w koniunkcji uwzględniamy samą zmienną, w przeciwnym razie - jej negację.
3. Wszystkie powstałe spójniki łączymy za pomocą operacji alternatywnych.

Algorytm konstruowania SKNF zgodnie z tabelą prawdy

1. Zaznacz wszystkie wiersze tabeli, w których wartość funkcji jest równa zero.
2. Dla każdego takiego wiersza zapisz alternatywę wszystkich zmiennych w następujący sposób: jeśli wartość jakiejś zmiennej w tym zbiorze jest równa 0, to w spójniku uwzględniamy samą zmienną, w przeciwnym razie - jej negację.
3. Wszystkie powstałe alternatywy łączymy za pomocą operacji koniunkcyjnych.

Analiza algorytmów pokazuje, że jeśli na większości wierszy tabeli prawdy wartość funkcji jest równa 0, to dla uzyskania jej wzoru logicznego lepiej jest skonstruować SDNF, w przeciwnym razie SKNF.

Przykład: podano tabelę prawdy funkcji logicznej trzech zmiennych. Budować formuła logiczna realizacji tej funkcji.

Ponieważ w większości wierszy tabeli prawdy wartość funkcji wynosi 1, a następnie konstruujemy SKNF. W rezultacie otrzymujemy następującą formułę logiczną:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Sprawdźmy otrzymaną formułę. Aby to zrobić, zbudujmy tabelę prawdy funkcji.

Porównując oryginalną tabelę prawdy i tę zbudowaną dla formuły logicznej, zauważamy, że kolumny wartości funkcji są takie same. Oznacza to, że funkcja logiczna jest zbudowana poprawnie.

Forma normalna Formuła logiczna nie zawiera znaków implikacji, równoważności i negacji formuł nieelementarnych.

Forma normalna występuje w dwóch formach:

spojówka normalna (CNF)- połączenie kilku alternatyw, np. $ \ left (A \ vee \ overline (B) \ vee C \ right) \ wedge \ left (A \ vee C \ right) $;

rozłączna postać normalna (DNF)- alternatywa kilku spójników, na przykład $ \ left (A \ klin \ overline (B) \ klin C \ right) \ vee \ left (B \ klin C \ right) $.

SKNF

Idealna spojówka normalna (SKNF) to CNF, który spełnia trzy warunki:

nie zawiera identycznych dysjunkcji elementarnych;

żadna z klauzul nie zawiera tych samych zmiennych;

każda elementarna alternatywa zawiera każdą zmienną z danego CNF.

Dowolna formuła logiczna, która nie jest identycznie prawdziwa, może być reprezentowana w SKNF.

Zasady konstruowania SKNF zgodnie z tabelą prawdy

Dla każdego zestawu zmiennych, dla których funkcja ma wartość 0, zapisywana jest suma, a zmienne o wartości 1 są przyjmowane z negacją.

SDNF

Idealna dysjunktywna forma normalna (SDNF) jest DNF, który spełnia trzy warunki:

nie zawiera identycznych spójników elementarnych;

żaden ze spójników nie zawiera tych samych zmiennych;

każda elementarna koniunkcja zawiera każdą zmienną z danego DNF, ponadto w tej samej kolejności.

Każda formuła logiczna, która nie jest identycznie fałszywa, może być reprezentowana w SDNF, co więcej, w unikalny sposób.

Zasady konstruowania SDNF zgodnie z tabelą prawdy

Dla każdego zestawu zmiennych, dla których funkcja jest równa 1, zapisywany jest iloczyn, a zmienne o wartości 0 są przyjmowane z negacją.

Przykłady znajdowania SKNF i SDNF

Przykład 1

Napisz funkcję logiczną zgodnie z jej tabelą prawdy:

Obrazek 1.

Rozwiązanie:

Użyjmy reguły do ​​konstruowania SDNF:

Rysunek 2.

Otrzymujemy SDNF:

Wykorzystajmy regułę konstruowania SKNF.

Prosty spójnik nazywa spójnik jeden lub kilka zmienne, w ten każdy zmienny spotyka się nie jeszcze jeden czasy (lub samo, lub ją negacja).

Na przykład jest prostym spójnikiem,

Dysjunktywny normalna Formularz(DNF) nazywa dysjunkcja prosty spójniki.

Na przykład wyrażenie to DNF.

Doskonały dysjunktywny normalna Formularz(SDNF) nazywa więc dysjunktywny normalna forma, w który v każdy spójnik są wliczone wszystko zmienne dany lista (lub sami, lub ich zaprzeczenia), Ponadto v jeden oraz Tom to samow porządku.

Na przykład wyrażenie to DNF, ale nie SDNF. Wyrażenie to SDNF.

Podobne definicje (z zastąpieniem spójnika przez alternatywę i vice versa) obowiązują dla CNF i SKNF. Oto dokładne sformułowania.

Prosty dysjunkcja nazywa dysjunkcja jeden lub kilka zmienne, w ten każdy zmienny wchodzi nie jeszcze jeden czasy (lub samo, lub ją negacja) Na przykład wyrażenie jest prostą alternatywą,

Łączący normalna Formularz(CNF) nazywa spójnik prosty alternatywy(na przykład wyrażenie to CNF).

Idealna forma normalna łącząca (SCNF) to CNF, w której każda prosta alternatywa zawiera wszystkie zmienne z danej listy (zarówno same, jak i ich negacje) i w tej samej kolejności.

Na przykład wyrażenie jest SKNF.

Oto algorytmy przejścia z jednej formy do drugiej. Oczywiście w konkretnych przypadkach (przy pewnym kreatywnym podejściu) zastosowanie algorytmów jest bardziej pracochłonne niż proste przekształcenia z wykorzystaniem określonego typu tej formy:

a) przejście z DNF do CNF

Algorytm tego przejścia jest następujący: umieszczamy dwie negacje nad DNF i stosując reguły de Morgana (bez dotykania górnej negacji) sprowadzamy negację DNF z powrotem do DNF. W takim przypadku musisz otworzyć nawiasy za pomocą reguły absorpcji (lub reguły Blake'a). Negacja (górna część) otrzymanego DNF (znowu zgodnie z regułą de Morgana) natychmiast daje nam CNF:

Zauważ, że CNF można również uzyskać z początkowego wyrażenia, jeśli wyjmiemy w poza nawiasami;

b) przejście z CNF do DNF

To przejście odbywa się przez proste otwarcie nawiasów (w tym przypadku ponownie stosuje się zasadę absorpcji)

Tak więc mamy DNF.

Odwrotne przejście (z SDNF do DNF) wiąże się z problemem minimalizacji DNF. Zostanie to omówione bardziej szczegółowo w rozdz. 5, tutaj pokażemy, jak uprościć DNF (lub SDNF) zgodnie z regułą Blake'a. Ten DNF nazywa się skrócony DNF;

c) skrót DNF (lub SDNF) przez reguła Blake

Stosowanie tej zasady składa się z dwóch części:

Jeżeli wśród rozłącznych terminów w DNF są terminy , to do całej alternatywy dodajemy termin DO 1 DO 2. Wykonujemy tę operację kilka razy (może być sekwencyjna, może być jednocześnie) dla wszystkich możliwych par terminów, a następnie stosujemy zwykłą absorpcję;

Jeśli dodany termin był już zawarty w DNF, można go całkowicie odrzucić, na przykład

lub

Oczywiście skrót DNF nie jest jednoznacznie zdefiniowany, ale wszystkie zawierają tę samą liczbę liter (na przykład istnieje DNF , po zastosowaniu do niego reguły Blake'a, możesz dojść do DNF równoważnego temu):

c) przejście z DNF do SDNF

Jeśli w jakimś prostym spójniku brakuje zmiennej, na przykład z, wstaw do niego wyrażenie, a następnie rozwiń nawiasy (w tym przypadku nie piszemy powtarzających się terminów rozłącznych). Na przykład:

d) przejście z CNF do SKNF

To przejście odbywa się w sposób podobny do poprzedniego: jeśli w prostej alternatywie brakuje jakiejś zmiennej (np. z, następnie dodajemy do niego wyrażenie (nie zmienia to samej alternatywy), po czym rozszerzamy nawiasy korzystając z prawa dystrybucji:

W ten sposób SKNF uzyskuje się z CNF.

Należy zauważyć, że minimalny lub skrócony CNF jest zwykle uzyskiwany z odpowiedniego DNF.

Wprowadźmy pojęcie alternatywy elementarnej.

Elementarna alternatywa jest wyrazem formy

Spójna forma normalna (CNF) funkcji logicznej jest koniunkcją dowolnego skończonego zbioru parami różnych elementarnych dysjunkcji. Na przykład funkcje logiczne

są połączeniami elementarnych alternatyw. W związku z tym są napisane w spojówkowej formie normalnej.

Dowolną funkcję logiczną podaną przez wyrażenie analityczne można sprowadzić do CNF, wykonując następujące operacje:

Korzystanie z reguły inwersji, jeśli operacja negacji jest stosowana do wyrażenia logicznego;

Stosując aksjomat rozdzielności w odniesieniu do mnożenia:

Zastosowania operacji absorpcji:

Wyjątki w alternatywach powtarzających się zmiennych lub ich negacji;

Usunięcie wszystkich tych samych elementarnych rozłączeń, z wyjątkiem jednego;

Usunięcie wszystkich klauzul, które jednocześnie zawierają zmienną i jej negację.

Ważność wymienionych operacji wynika z podstawowych aksjomatów i relacji tożsamościowych algebry logiki.

Spójną formę normalną nazywamy doskonałą, jeśli każda elementarna alternatywa w niej zawarta zawiera, w formie prostej lub odwrotnej, wszystkie zmienne, od których zależy funkcja.

Konwersja CNF do doskonałego CNF odbywa się poprzez wykonanie następujących operacji:

Dodatki do każdej elementarnej alternatywy koniunkcji zmiennych i ich negacji, jeśli nie są zawarte w tej elementarnej alternatywie;

Stosując aksjomat dystrybucyjności;

Usunięcie wszystkich identycznych dysjunkcji elementarnych, z wyjątkiem jednego.

Dowolna funkcja logiczna może być reprezentowana w doskonałym CNF, z wyjątkiem:

identycznie równy jeden(). Charakterystyczną właściwością doskonałego CNF jest to, że reprezentacja w nim funkcji logicznej jest unikalna.

Elementarne alternatywy zawarte w doskonałej funkcji CNF nazywane są składnikami zerowymi. Każdy składnik zera zawarty w idealnym CNF znika na pojedynczym zestawie wartości zmiennych, który jest zbiorem zerowym funkcji. W konsekwencji liczba zerowych zbiorów funkcji logicznej pokrywa się z liczbą zerowych składników zawartych w jej idealnym CNF.

Stała funkcji logicznej zero w idealnym CNF jest reprezentowana przez koniunkcję 2n stała zero. Sformułujmy regułę kompilacji SCNF funkcji logicznej zgodnie z tabelą korespondencji.

Dla każdego wiersza tabeli przeglądowej, w którym funkcja jest równa zero, kompilowana jest elementarna alternatywa wszystkich zmiennych. W tym przypadku sama zmienna jest uwzględniana w alternatywie, jeśli jej wartość jest równa zero, lub negacji, jeśli jej wartość jest równa jeden. Wynikające z tego elementarne dysjunkcje są połączone znakiem spójnika.

Przykład 3.4. Dla funkcji logicznej z(x), podanej w tabeli korelacji 2.2, definiujemy formę doskonałego połączenia.

Dla pierwszego wiersza tabeli, który odpowiada zestawowi zer funkcji 000, znajdujemy składnik zera. Po wykonaniu podobnych operacji dla drugiej, trzeciej i piątej linii definiujemy pożądaną idealną funkcję CNF:

Należy zauważyć, że dla funkcji, których liczba zestawów jednostek przekracza liczbę zestawów zerowych, bardziej zwięzłe jest zapisanie ich w postaci SKNF i odwrotnie.

Formy normalne funkcji logicznych Reprezentacja funkcji Boole'a w postaci alternatywy spójnych członów jednostki Ki 2,7 nazywana jest rozłączną formą normalną DNF tej funkcji. zawierają dokładnie jedną na raz wszystkie zmienne logiczne wzięte z negacjami lub bez nich, wtedy ta forma reprezentacji funkcji nazywana jest doskonałą dysjunktywną formą normalną SDNF tej funkcji. Jak widać, kompilując funkcję SDNF, należy oddzielić wszystkie mintermy, dla których funkcja przyjmuje wartość 1.

Jeśli ta praca Ci nie odpowiadała, na dole strony znajduje się lista podobnych prac. Możesz także użyć przycisku wyszukiwania

Wykład 1.xx

Formy normalne funkcji logicznych

Reprezentacja funkcji Boole'a w postaci alternatywy spójników (jednostka składowa) K i

, (2.7)

nazywa rozłączna forma normalna(DNF) tej funkcji.

Jeśli wszystkie spójniki w DNF są minterms , czyli zawierają dokładnie po jednej na raz wszystkie zmienne logiczne, brane z negatywami lub bez nich, wtedy ta forma reprezentacji funkcji nazywa siędoskonała dysjunktywna forma normalna(SDNF ) tej funkcji. SDNF nazywa się doskonały ponieważ każdy wyraz w alternatywie zawiera wszystkie zmienne; dysjunktywny ponieważ główną operacją we wzorze jest alternatywa. Koncepcja "normalna forma„Oznacza jednoznaczny sposób zapisania formuły realizującej daną funkcję.

W związku z powyższym, Twierdzenie 2.1 implikuje następujące twierdzenie.

Twierdzenie 2. Dowolna funkcja logiczna(nie identycznie równe 0) można przesłać do SDNF, .

Przykład 3. Niech mamy funkcję zdefiniowaną w tabeli f (x 1, x 2, x 3) (Tabela 10).

Tabela 10

Na podstawie wzoru (2.6) otrzymujemy:

Jak widać, kompilując funkcję SDNF, należy skomponować alternatywę wszystkich mintermów, dla których funkcja przyjmuje wartość 1.

Reprezentacja funkcji Boole'a w postaci koniunkcji terminów rozłącznych (składnik zera) D i

, (2.8)

nazywa spójna forma normalna(CNF) tę funkcję.

Jeśli wszystkie rozłączne terminy CNF są Maksterma , czyli zawierać dokładnie jeden wszystkie logiczne zmienne funkcji podjęte z lub bez negacji, wtedy taki CNF nazywa sięidealna spojówka normalna forma(SKNF) tę funkcję.

Twierdzenie 3. Dowolna funkcja logiczna(nie równa się identycznie 1) może być reprezentowany w SKNF, co więcej, taka reprezentacja jest jedyna.

Dowód twierdzenia można przeprowadzić podobnie do dowodu Twierdzenia 2.1 na podstawie następującego lematu Shannona o dekompozycji koniunkcyjnej.

lemat Shannona ... Dowolna funkcja logiczna f (x 1, x 2, ..., x m) z m zmienne mogą być reprezentowane w następujący sposób:

. (2.9)

Należy zauważyć, że obie formy reprezentacji funkcji logicznej (DNF i CNF) są teoretycznie równe w swoich możliwościach: każda formuła logiczna może być reprezentowana zarówno w DNF (z wyjątkiem identycznego zera), jak i w CNF (z wyjątkiem identycznej jednostki ). W zależności od sytuacji reprezentacja funkcji w takiej czy innej formie może być krótsza.

W praktyce najczęściej stosuje się DNF, ponieważ ta forma jest bardziej znana człowiekowi: od dzieciństwa jest bardziej przyzwyczajony do dodawania dzieł niż do mnożenia sum (w ten drugi przypadek intuicyjnie chce otworzyć nawiasy i tym samym przejść do DNF).

Przykład 4. Dla funkcji f (x 1, x 2, x 3 ) podane w tabeli. 10, napisz to do SKNF.

W przeciwieństwie do SDNF, podczas kompilowania SCNF w tabeli prawdy funkcji logicznej, musisz spojrzeć na kombinacje zmiennych, dla których funkcja przyjmuje wartość 0, i skomponować koniunkcję odpowiednich maxterms,ale zmienne muszą być brane z odwrotną inwersją:

Należy zauważyć, że nie można przejść bezpośrednio z funkcji SDNF do jej SKNF lub odwrotnie. Próba takich przekształceń skutkuje odwrotnością funkcji pożądanych. Wyrażenia funkcji SDNF i SKNF można uzyskać bezpośrednio tylko z tabeli prawdy.

Przykład 5. Dla funkcji f (x 1, x 2, x 3 ) podane w tabeli. 10, spróbuj przejść z SDNF do SKNF.

Korzystając z wyniku z przykładu 2.3, otrzymujemy:

Jak widać, w ramach ogólnej inwersji uzyskuje się SKNF funkcji logicznej, która jest odwrotna w stosunku do funkcji uzyskanej w przykładzie 2.4:

ponieważ zawiera wszystkie maxterms, które nie znajdują się w wyrażeniu dla SKNF rozważanej funkcji.

1. Korzystając z właściwości operacji (patrz Tabela 9) tożsamość (), sum modulo 2 (), implikacja (), przechodzimy do operacji AND, OR, NOT (w bazie logicznej).

2. Korzystając z własności negacji i praw de Morgana (patrz Tabela 9), uzyskujemy, że operacje negacji odnoszą się tylko do pojedynczych zmiennych, a nie do całych wyrażeń.

3. Korzystając z własności operacji logicznych AND i OR (patrz Tabela 9), otrzymujemy postać normalną (DNF lub CNF).

4. W razie potrzeby przejdź do doskonałych formularzy (SDNF lub SKNF). Na przykład, aby uzyskać SKNF, często trzeba użyć właściwości:.

Przykład 6. Konwertuj funkcję logiczną na SKNF

Wykonując kolejno kroki powyższego algorytmu, otrzymujemy:

Wykorzystując właściwość absorpcji otrzymujemy:

W ten sposób uzyskaliśmy funkcje CNF f (x 1, x 2, x 3 ). Aby uzyskać jego SKNF, każdą alternatywę, w której brakuje jakiejkolwiek zmiennej, trzeba powtórzyć dwukrotnie - z tą zmienną i z jej negacją:

2.2.6. Minimalizowanie funkcji logicznych

Ponieważ tę samą funkcję logiczną można przedstawić jako s formuły osobiste, a następnie znalezienie najprostszego pho r mule, który definiuje funkcję Boolean, upraszcza obwód logiczny implementujący funkcję Boolean. do cji. Minimalny kształt l O funkcja geologicznaw pewnym sensie możemy założyć, że zawiera minimalną liczbę superpozycji funkcji Do podstawa, w tym nawiasy. Trudno jednak skonstruować skuteczny a ja algorytm takiej minimalizacji z uzyskaniem minimalnego nawiasu r my.

Rozważmy prostszy problem minimalizacji w syntezie układów kombinacyjnych, w którym poszukuje się nie minimalnej postaci nawiasu funkcji, ale jej minimalnego DNF. Istnieją proste, wydajne algorytmy do tego zadania.

Metoda Quine'a

Funkcja do zminimalizowania jest reprezentowana w SDNF, a wszystkie możliwe operacje niepełnego sklejenia są do niej stosowane

, (2.10)

a następnie wchłanianie

, (2.11)

i ta para kroków jest stosowana wielokrotnie. W ten sposób możliwe jest obniżenie rangi terminów. Ta procedura jest powtarzana, aż nie pozostanie żaden termin, który można skleić z innym terminem.

Zauważ, że lewa strona Równania (2.10) można by od razu zminimalizować w prostszy i bardziej oczywisty sposób:

Ta metoda jest zła o tyle, że przy tak bezpośredniej minimalizacji wyrazy koniunkowe albo znikają, choć nadal zdarzają się przypadki ich użycia do sklejania i wchłaniania z pozostałymi wyrazami.

Należy zauważyć, że metoda Quine'a jest dość czasochłonna, więc prawdopodobieństwo popełnienia błędów podczas transformacji jest dość duże. Ale jego zaletą jest to, że teoretycznie może być używany dla dowolnej liczby argumentów, a wraz ze wzrostem liczby zmiennych konwersje stają się mniej skomplikowane.

Metoda mapy Karnaugh

Metoda map (tabel) Karnaugha jest bardziej wizualnym, mniej czasochłonnym i niezawodnym sposobem minimalizowania funkcji logicznych, ale jej zastosowanie ogranicza się praktycznie do funkcji 3-4 zmiennych, maksymalnie 5-6 zmiennych.

Mapa Carnota Jest dwuwymiarową tabelaryczną formą przedstawiania tabeli prawdy funkcji Boole'a, która pozwala łatwo znaleźć minimalną wartość DNF funkcji logicznych w graficznej formie wizualnej. Każda komórka tabeli jest powiązana z minterm funkcji SDNF, która ma zostać zminimalizowana, tak że dowolna oś symetrii tabeli odpowiada strefom, które są wzajemnie odwrotne w dowolnej zmiennej. Taki układ komórek w tabeli ułatwia określenie sklejających się terminów SDNF (różniących się znakiem inwersji tylko jednej zmiennej): są one ułożone symetrycznie w tabeli.

Tabele prawdy i mapy Karnota dla funkcji AND i OR dwupasmowych mi zmienne pokazano na ryc. 8. W każdej komórce karty zapisany jest znak a funkcja na argumencie odpowiadającym tej komórce n Towarzyszu

A) I b) LUB

Ryż. osiem. Przykład odwzorowania Karnota dla funkcji dwóch zmiennych

W mapie Karnota jest tylko jedna 1 dla funkcji I, więc nie można jej do niczego przykleić. Wyrażenie na funkcję minimum będzie zawierało tylko wyraz odpowiadający temu 1:

f = x r.

W mapie Karnota dla funkcji OR są już trzy jedynki i możliwe jest wykonanie dwóch par klejących, przy czym 1 odpowiada terminowi xy , jest używany dwukrotnie. W wyrażeniu na funkcję minimum należy wpisać terminy dla par, które mają być sklejone, pozostawiając w nich wszystkie zmienne, które nie zmieniają się dla tej pary, a usuwając zmienne, które zmieniają ich wartość. Do klejenia poziomego otrzymujemy x , a dla pionu - tak , w wyniku otrzymujemy wyrażenie

f = x + y.

Na ryc. 9 pokazuje tablice prawdy dwóch funkcji trzech zmiennych ( a ) i ich mapy Karnot ( b i c). Funkcja f 2 różni się od pierwszego tym, że nie jest zdefiniowany na trzech zestawach zmiennych (jest to sygnalizowane myślnikiem w tabeli).

Przy określaniu minimalnego DNF funkcji stosuje się następujące zasady. Wszystkie komórki zawierające 1 są łączone w zamknięte prostokątne obszary, które nazywane są k -kostki, gdzie k = log 2 K, K - ilość 1 w polu prostokątnym. Ponadto każdy obszar powinien być prostokątem z 2 komórkami k, gdzie k = 0, 1, 2, 3,…. Dla k = Nazywa się 1 prostokąt jeden jest sześcianem i zawiera 2 1 = 2 jednostki; dla k = 2 prostokąt zawiera 2 2 = 4 jednostki i nazywa się dwie kostki; dla k = 3 obszar 2 3 = 8 jednostek nazywa się trzy sześciany ; itd. Jednostki, których nie można połączyć w prostokąty, można nazwać zero-kostki zawierające tylko jedną jednostkę (2 0 = 1). Jak widać, z parzystymi k obszary mogą być kwadratowe (ale nie konieczne), a dla nieparzystych k - tylko prostokąty.

Ryż. dziewięć. Przykład odwzorowania Karnota dla funkcji trzech zmiennych

Te obszary mogą się nakładać, to znaczy, że te same komórki mogą wejść różne obszary... Następnie minimalna wartość DNF funkcji jest zapisywana jako alternatywa wszystkich spójników odpowiadających k - kostki.

Każdy ze wskazanych regionów na mapie Karnota jest reprezentowany w minimalnym DNF przez spójnik, którego liczba argumentów jest k mniej niż całkowita liczba argumentów funkcji m , czyli ta liczba jest równa m - k ... Każda koniunkcja minimalnego DNF składa się tylko z tych argumentów, które dla odpowiedniego obszaru mapy mają wartości albo bez inwersji, albo tylko z inwersjami, czyli nie zmieniają swoich wartości.

Zatem przy zakrywaniu komórek mapy obszarami zamkniętymi należy dążyć do tego, aby liczba obszarów była minimalna, a każdy obszar zawierał największą możliwą liczbę komórek, ponieważ w tym przypadku liczba członków w minimalnym DNF będzie być minimalna, a liczba argumentów w odpowiedniej koniunkcji będzie minimalna.

Dla funkcji mapy Karnota na ryc. dziewięć, znaleźliśmy

ponieważ dla górnego obszaru zamkniętego zmienne x 1 i x 2 sprawa bez inwersji, dla niższych x 1 ma znaczenie z inwersją i x 3 - bez inwersji.

Niezdefiniowane wartości na mapie na ryc. dziewięć, v można go przedłużyć, zastępując go zerem lub jedynką. W przypadku tej funkcji można zauważyć, że korzystniejsze jest zastąpienie obu niezdefiniowanych wartości przez 1. W tym przypadku powstają dwa regiony, które są Różne rodzaje 2 kostki. Wtedy wyrażenie dla funkcji minimum DNF będzie wyglądać następująco:

Podczas konstruowania zamkniętych obszarów dozwolone jest zwijanie mapy Karnaugha do cylindra zarówno w poziomie, jak iw pionie. r osie z połączeniem przeciwległych krawędzi r ty, czyli jednostki znajdujące się na krawędziach mapy symetrii Carnota h ale można je również łączyć.

Mapy Karnaugha można rysować na różne sposoby (rysunek 10).

b

Ryż. dziesięć. Różne sposoby rysowania map Karnaugh
dla funkcji 3 zmiennych

Jednak najdogodniejsze warianty odwzorowań Karnota dla funkcji 2-4 zmiennych pokazano na ryc. 11 tabel, ponieważ dla każdej komórki, którą pokazują a wszystkie zmienne są w formie bezpośredniej lub odwrotnej.

b

Ryż. jedenaście. Najwygodniejszy obraz map Karnot
dla funkcji 3 ( a) i 4 (b) zmienne

Dla funkcji 5 i 6 zmiennych metoda pokazana na rys. dziesięć, v .

Ryż. 12. Obraz mapy Karnota dla funkcji 5 zmiennych

Ryż. 13. Obraz mapy Karnota dla funkcji 6 zmiennych