Редактирование: Основы Кибернетики, Алгоритмы решения задач/Задачи на ДНФ

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

== По заданной ФАЛ построить ее сокращенную ДНФ, ДНФ Квайна, ДНФ сумма тупиковых, все тупиковые ДНФ ==

=== Определения ===

==== Функция алгебры логики ====
'''Функция алгебры логики''' — функция, переводящая вектор из n-элементов множества B = {0, 1} в элемент множества B. То есть, для каждого набора нулей и единиц у функции определено значение, равное нулю или единице.

=== Построение сокращённой ДНФ ===

==== Определения ====

===== Буква x&sigma; =====
Есть алфавит ''X''(n) = {''x''1, &hellip; ''x''n}. '''Буква ''x''i&sigma;''' есть ''x''i, если &sigma; = 1, и ''x̅''i, если &sigma; = 0.

===== Конъюнкция ранга r =====
'''Конъюнкция ранга r''' ''K'' = ''x''i1&sigma;1&hellip;''x''ir&sigma;r, 0 &le; r &le; n; ''K'' = 0 при ''r'' = 0.

===== Элементарная конъюнкция =====
'''Элементарная конъюнкция''' — конъюнкция, у которой все переменные в буквах различны: ''x''ik&sigma;l &ne; ''x''il&sigma;l при k &ne; l

===== Импликанта =====
Элементарная конъюнкция ''К'' называется '''импликантой''' ''f'', если ''K'' ∨ ''f'' = ''f''.

===== Простая импликанта =====
Импликанта ''К'' функции ''f'' называется '''простой импликантой''', если при вычёркивании любой буквы ''K'' получается элементарная конъюнкция, которая не является импликантой ''f''.

===== Сокращённая ДНФ =====
'''Сокращённая ДНФ''' — дизъюнкция всех простых импликант ''f''

==== Геометрический метод (с использованием единичного куба) ====
* Рисуем единичный куб (для 6 и более переменных это уже затруднительно)
{|width="100%"
 !Единичный куб для двух переменных
 !Единичный куб для трёх переменных
 !Единичный куб для четырёх переменных
 |-
 |style="text-align:center"|[[Изображение:Cube 2d.png|240px]] 
 |style="text-align:center"|[[Изображение:Cube.png|240px]] 
 |style="text-align:center"|[[Изображение:Cube 4d.png|240px]] 
 |-
 !colspan="3"|Единичный куб для пяти переменных
 |-
 |colspan="3" style="text-align:center"|[[Изображение:Cube 5d.png|720px]] 
 |}
* Отмечаем все грани максимальной размерности, во всех точках которых функция равна единице
* Отмечаем все грани размерности на единицу меньше, во всех точках которых функция равна единице
* &hellip;
* Отмечаем все вершины, в которых функция равна единице

Таким образом, мы наглядно получаем максимальные грани, видим местоположение ядровых точек и&nbsp;т.&nbsp;п.

[[Изображение:Reduced_dnf_cube.png|thumb|Разметка куба для функции ''f''&nbsp;=&nbsp;(0110&nbsp;1111)]]
===== Пример =====
Построить сокращённую ДНФ для функции ''f'' = (0110 1111). С использованием единичного куба.

'''Решение.'''
Размеченный куб представлен справа. Как видно из иллюстрации, можно выделить следующие максимальные грани:
* (1 &minus; &minus;) &rarr; ''x''1
* (&minus; 1 0) &rarr; ''x''2''x''3
* (&minus; 0 1) &rarr; ''x''2''x''3

В реузльтате получим сокращённую ДНФ ''x''1 ∨ ''x''2''x''3 ∨ ''x''2''x''3

==== Метод Блейка ====
Пусть у нас имеется произвольная ДНФ функции ''f''. Определим два преобразования:
* ''x''A ∨ ''x''B &rarr; ''x''A ∨ ''x''B ∨ AB
* A ∨ AB &rarr; A
Тогда, если сначала применять к имеющейся ДНФ первое преобразование, пока это возможно, а потом — второе, то получим сокращённую ДНФ.

===== Пример =====
Построить сокращённую ДНФ по имеющейся ДНФ

x1x2x3 ∨ x1''x2''x3 ={применяем первое правило}= x1x2x3 ∨ x1''x2''x3 ∨ x1x3 ={применяем второе правило дважды}= x1x3

==== Метод Нельсона ====
Метод Нельсона использует КНФ функции ''f''. Для построения сокращённой ДНФ по КНФ достаточно раскрыть скобки и привести подобные методом поглощения (A ∨ AB &rarr; A)

===== Пример =====
Построить сокращённую ДНФ по имеющейся КНФ 
f(x1,x2,x3)=(''x''3 ∨ ''x''1)(x1 ∨ x2 ∨ ''x''3)

f = ''x''3x1 ∨ ''x''3x2 ∨ ''x''3''x''3 ∨ <strike>(''x''</strike>1<strike>x</strike>1<strike>)</strike> ∨ ''x''1x2 ∨ ''x''1''x''3
= ''x''3 ∨ ''x''3x1 ∨ ''x''3x2 ∨ ''x''1''x''3 ∨ ''x''1x2
= ''x''3 ∨ ''x''1x2

==== Метод с использованием карт Карно ====
Данный метод удобен для функций от 4 переменных (его также можно использовать для функций от 3 переменных, но для них обычно используются другие методы). Он основан на нахождении блоков единиц на построенной специальном образом карте значений функции. Карта строится следующим образом: по вертикали выписываются переменные ''x''1, ''x''2; по горизонатли — ''x''3, ''x''4. Пары переменых выписываются в порядке (00), (01), (11), (10). После чего в таблицу заносятся значения функции для данных значений переменных. Рассмотрим построение карты для функции f = (f0000f0001f0010f0011 f0100f0101f0110f0111 f1000f1001f1010f1011 f1100f1101f1110f1111):

{|
 !rowspan="2" colspan="2"|&nbsp;
 !''x''3
 !0
 !0
 !1
 !1
 |-
 !''x''4
 !0
 !1
 !1
 !0
 |-
 !''x''1
 !''x''2
 !&nbsp;
 !colspan="4"|&nbsp;
 |-
 !0
 !0
 !&nbsp;
 |f0000
 |f0001
 |f0011
 |f0010
 |-
 !0
 !1
 !&nbsp;
 |f0100
 |f0101
 |f0111
 |f0110
 |-
 !1
 !1
 !&nbsp;
 |f1100
 |f1101
 |f1111
 |f1110
 |-
 !1
 !0
 !&nbsp;
 |f1000
 |f1001
 |f1011
 |f1010
 |}

Далее на полученной карте находим все максимально возможные блоки единиц вида 2k &times; 2l; k, l &isin; '''N''', учитывая тот факт, что карта закольцована. Блоки могут пересекаться, но не должны включать друг друга. Далее для каждого блока выписывается вектор, в котором в случае, если переменная в пределах этого блока меняла значение, знак «–», если же не меняет, то её значение в пределах блока. Для позиций вектора ''i'', в которых стоит знак &sigma; &isin; {0, 1}? в ЭК добавляется xi&sigma;. Дизъюнкция всех полученных ЭК и есть сокращённая ДНФ.

===== Пример =====
Найдём сокращённую ДНФ для функции ''f'' = (1010 0110 0111 1101) методом карт Карно.

'''Решение''' 
Строим карту: 
[[Изображение:Karno.png|240px]]

На основании карты получаем следующие блоки:
* (0 0 &minus; 0) = ''x''1''x''2''x''4
* (0 &minus; 1 0) = ''x''1''x''3''x''4
* (&minus; 0 1 0) = ''x''2''x''3''x''4
* (&minus; 1 0 1) = ''x''2''x''3''x''4
* (1 1 0 &minus;) = ''x''1''x''2''x''3
* (1 0 1 &minus;) = ''x''1''x''2''x''3
* (1 &minus; &minus; 1) = ''x''1''x''4

В результате получаем сокращённую ДНФ ''x''1''x''2''x''4 ∨ ''x''1''x''3''x''4 ∨ ''x''2''x''3''x''4 ∨ ''x''2''x''3''x''4 ∨ ''x''1''x''2''x''3 ∨ ''x''1''x''2''x''3 ∨ ''x''1''x''4

==== Построение сокращенной ДНФ по совершенной ДНФ при помощи алгоритма Квайна ====
Алгоритм Квайна построения сокращенной ДНФ по совершенной ДНФ:
0) i:=1
1)Пока возможно к слагаемым ранга n-i+1 применять неполное склеивание:
 xK v (not x)K = xK v (not x)K v K
2)пока возможно поглощение
3) i++; if (i<=n) goto 0

=== Построение ДНФ Квайна ===

ДНФ, которую получают путем выбрасывания всех простых импликант, соответствующих максимальным граням, которые покрываются ядром, называется '''ДНФ Квайна'''.

Алгоритм построения ДНФ Квайна:

1.      получить сокращенную ДНФ;

2.      найти ядровые грани;

3.      удалить импликанты, покрываемые ядром.

Полученная ДНФ, является ДНФ Квайна.

=== Построение ДНФ &Sigma;T (суммы тупиковых) ===

см ниже

=== Построение всех тупиковых ДНФ ===
Пусть мы ищем все тупиковые решения для ФАЛ f. Выпишем таблицу M(''таблицу Квайна''), в которой столбцам соответствуют элементы из ''Nf'' (наборы, на которых функция принимает значение 1), строкам соответствуют максимальные грани. В ячейке стоит 1, если грань, соответствующая строке содержит набор, соответствующий столбцу.

Затем выписываем КНФ функции покрытия следующим образом:

Пусть каждой строке соответствует некоторая переменая ''yi''.

Для каждого столбца, переменные, соотвествующие строкам в которых в данном столбце стоит 1, запишем через логическое или. Функция покрытия равна произведению таких сумм для каждого столбца.

==== Пример ====
Есть функция g: ''Ng = {&alpha;1 = (100), &alpha;2 = (110), &alpha;3 = (010), &alpha;4 = (011), &alpha;5 = (001), &alpha;6 = (101) }''.

Множество максимальных граней = ''{N1,&hellip;,N6}'', где ''Ni={&alpha;i,&alpha;i+1}'', причем &alpha;7=&alpha;1.

Таблица Квайна:

<center>[[Изображение:mKvaina.png]]</center>

ФАЛ покрытия: ''F(y) = (y6 &or; y1)(y1 &or; y2)(y2 &or; y3)(y3 &or; y4)(y4 &or; y5)(y5 &or; y6).''

Раскрывая скобки и приводя подобные, получаем:

''F(y) = y1y3y5 &or; y2y4y6 &or; y1y2y4y5 &or; y2y3y5y6 &or; y1y3y4y5''.

Это соответствет тупиковым покрытиям ''1 = N1N3N5; 2 = N2N4N6; и т.д.''

==== Пример ====
Построить все тупиковые ДНФ для ФАЛ ''f'' = (1010 0110 0111 1101).

'''Решение.'''

Сокращённая ДНФ для данной функции есть ''x''1''x''2''x''4 ∨ ''x''1''x''3''x''4 ∨ ''x''2''x''3''x''4 ∨ ''x''2''x''3''x''4 ∨ ''x''1''x''2''x''3 ∨ ''x''1''x''2''x''3 ∨ ''x''1''x''4 (как было получено [[#Метод с использованием карт Карно|ранее]]). Выпишем все точки, где ЭК принимают значение, равное единице, следующим образом:
{|
 !ЭК
 !''x''1''x''2''x''4
 | ∨ 
 !''x''1''x''3''x''4
 | ∨ 
 !''x''2''x''3''x''4
 | ∨ 
 !''x''2''x''3''x''4
 | ∨ 
 !''x''1''x''2''x''3
 | ∨ 
 !''x''1''x''2''x''3
 | ∨ 
 !''x''1''x''4
 |-
 !&alpha;i
 |&alpha;1&nbsp;=&nbsp;(0000) &alpha;2&nbsp;=&nbsp;(0010)
 |&nbsp;
 |&alpha;2&nbsp;=&nbsp;(0010) &alpha;3&nbsp;=&nbsp;(0110)
 |&nbsp;
 |&alpha;2&nbsp;=&nbsp;(0010) &alpha;4&nbsp;=&nbsp;(1010)
 |&nbsp;
 |&alpha;5&nbsp;=&nbsp;(0101) &alpha;6&nbsp;=&nbsp;(1101)
 |&nbsp;
 |&alpha;7&nbsp;=&nbsp;(1100) &alpha;6&nbsp;=&nbsp;(1101)
 |&nbsp;
 |&alpha;4&nbsp;=&nbsp;(1010) &alpha;8&nbsp;=&nbsp;(1011)
 |&nbsp;
 |&alpha;9&nbsp;=&nbsp;(1001) &alpha;8&nbsp;=&nbsp;(1011) &alpha;6&nbsp;=&nbsp;(1101) &alpha;10&nbsp;=&nbsp;(1111)
 |}

Построим таблицу (таблицу Квайна), у которой по строкам указаны ЭК, а по столбцам — точки, где функция принимает значение, равное единице. На пересечении ЭК и точки будет стоять значение ЭК в этой точке (фактически, входит ли данная точка в характеристическое множество данной ЭК, или нет). Для наглядности, единицы выделены.
{|style="text-align:center"
 !&nbsp;
 !&alpha;1
 !&alpha;2
 !&alpha;3
 !&alpha;4
 !&alpha;5
 !&alpha;6
 !&alpha;7
 !&alpha;8
 !&alpha;9
 !&alpha;10
 |-
 !K1&nbsp;=&nbsp;''x''1''x''2''x''4
 !1 
 !1 
 |0 
 |0 
 |0 
 |0 
 |0 
 |0 
 |0 
 |0 
 |-
 !K2&nbsp;=&nbsp;''x''1''x''3''x''4
 |0 
 !1 
 !1 
 |0 
 |0 
 |0 
 |0 
 |0 
 |0 
 |0 
 |-
 !K3&nbsp;=&nbsp;''x''2''x''3''x''4
 |0 
 !1 
 |0 
 !1 
 |0 
 |0 
 |0 
 |0 
 |0 
 |0 
 |-
 !K4&nbsp;=&nbsp;''x''2''x''3''x''4
 |0 
 |0 
 |0 
 |0 
 !1 
 !1 
 |0 
 |0 
 |0 
 |0 
 |-
 !K5&nbsp;=&nbsp;''x''1''x''2''x''3
 |0 
 |0 
 |0 
 |0 
 |0 
 !1 
 !1 
 |0 
 |0 
 |0 
 |-
 !K6&nbsp;=&nbsp;''x''1''x''2''x''3
 |0 
 |0 
 |0 
 !1 
 |0 
 |0 
 |0 
 !1 
 |0 
 |0 
 |-
 !K7&nbsp;=&nbsp;''x''1''x''4
 |0 
 |0 
 |0 
 |0 
 |0 
 !1 
 |0 
 !1 
 !1 
 !1 
 |}

Далее, определим ядровые точки, то есть те &alpha;i, у которых в столбце только одна единица. Таковыми являются &alpha;1, &alpha;3, &alpha;5, &alpha;7, &alpha;9, &alpha;10. Соответственно, ядровыми гранями являются те грани, которые соответствуют конъюнкциям, которым принадлежат ядровые вершины (смотрим на строки, в которых хотя бы для одного из выбранных столбцов &alpha;i стоит единица), то есть K1, K2, K4, K5, K7. Дизъюнкция этих конъюнкций есть пересечение тупиковых.

Для нахождения всех тупиковых ДНФ построим КНФ, элементарныё дизъюнкции которой будут состоять из БП, соответствующих тем конъюнкциям, в которые входит рассматриваемая точка &alpha;i (то есть, всего дизъюнкций столько же, сколько есть точек, где фугкция принимает единичное значение, причём первая дизъюнкция будет содержать те БП, которые соответствуют тем ЭК, которым принадлежит &alpha;1 (в данном примере это K1), вторая — те, которые соответствуют ЭК, которым принадлежит &alpha;2 (K1, K2, K3), и так далее):

После раскрытия и приведения подобных получим ДНФ, состоящих из ЭК, которые будут соответствовать тупиковым ДНФ, причём БП в ЭК будут соответствовать ЭК, входящим в тупиковую ДНФ:

K1 & (K1 ∨ K2 ∨ K3) & K2 & (K3 ∨ K6) & K4 & (K4 ∨ K5 ∨ K7) & K5 & (K6 ∨ K7) & K7 & K7 = K1K2K4K5K7 & (K1 ∨ K2 ∨ K3) & (K3 ∨ K6) & (K4 ∨ K5 ∨ K7) & (K6 ∨ K7) = K1K2K4K5K3K7 ∨ K1K2K4K5K6K7

ДНФ K1K2K3K4K5K7 ∨ K1K2K4K5K6K7 соответствует тупиковым ДНФ
{|
 !K1 ∨ K2 ∨ K3 ∨ K4 ∨ K5 ∨ K7
 |''x''1''x''2''x''4 ∨ ''x''1''x''3''x''4 ∨ ''x''2''x''3''x''4 ∨ ''x''2''x''3''x''4 ∨ ''x''1''x''2''x''3 ∨ ''x''1''x''4
 |-
 !K1 ∨ K2 ∨ K4 ∨ K5 ∨ K6 ∨ K7
 |''x''1''x''2''x''4 ∨ ''x''1''x''3''x''4 ∨ ''x''2''x''3''x''4 ∨ ''x''1''x''2''x''3 ∨ ''x''1''x''2''x''3 ∨ ''x''1''x''4
 |}

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Шаблон:Курс Основы Кибернетики

Получено с http://esyr.name/wiki/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D1%8B_%D0%9A%D0%B8%D0%B1%D0%B5%D1%80%D0%BD%D0%B5%D1%82%D0%B8%D0%BA%D0%B8%2C_%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BD%D0%B0_%D0%94%D0%9D%D0%A4

@@ Строка 60: / Строка 60: @@
 * (&minus; 0 1) &rarr; <span style="border-top:solid 1px">''x''</span><sub>2</sub>''x''<sub>3</sub>
-В результате получим сокращённую ДНФ ''x''<sub>1</sub> ∨ ''x''<sub>2</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>2</sub>''x''<sub>3</sub>
+В реузльтате получим сокращённую ДНФ ''x''<sub>1</sub> ∨ ''x''<sub>2</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>2</sub>''x''<sub>3</sub>
 ==== Метод Блейка ====
@@ Строка 158: / Строка 158: @@
 В результате получаем сокращённую ДНФ <span style="border-top:solid 1px">''x''</span><sub>1</sub><span style="border-top:solid 1px">''x''</span><sub>2</sub><span style="border-top:solid 1px">''x''</span><sub>4</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub>''x''<sub>3</sub><span style="border-top:solid 1px">''x''</span><sub>4</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>2</sub>''x''<sub>3</sub><span style="border-top:solid 1px">''x''</span><sub>4</sub> ∨ ''x''<sub>2</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub>''x''<sub>4</sub> ∨ ''x''<sub>1</sub>''x''<sub>2</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub> ∨ ''x''<sub>1</sub><span style="border-top:solid 1px">''x''</span><sub>2</sub>''x''<sub>3</sub> ∨ ''x''<sub>1</sub>''x''<sub>4</sub>
-нужно обьединить в прямоугольник единицу (с координатами [1;1]) с единицей ,у которой координаты [4;1]
-нужно обьединить в прямоугольник единицу (с координатами [4;1]) с единицей ,у которой координаты [4;4]
-прокомментировал getbraine e-mail v000du@gmail.com
 ==== Построение сокращенной ДНФ по совершенной ДНФ при помощи алгоритма Квайна ====
@@ Строка 171: / Строка 165: @@
     xK v (not x)K = xK v (not x)K v K
 )пока возможно поглощение
-) i++;  if (i<=n) goto 1
+) i++;  if (i<=n) goto 0
 === Построение ДНФ Квайна ===
@@ Строка 356: / Строка 350: @@
 Далее, определим ядровые точки, то есть те &alpha;<sub>i</sub>, у которых в столбце только одна единица. Таковыми являются &alpha;<sub>1</sub>, &alpha;<sub>3</sub>, &alpha;<sub>5</sub>, &alpha;<sub>7</sub>, &alpha;<sub>9</sub>, &alpha;<sub>10</sub>. Соответственно, ядровыми гранями являются те грани, которые соответствуют конъюнкциям, которым принадлежат ядровые вершины (смотрим на строки, в которых хотя бы для одного из выбранных столбцов &alpha;<sub>i</sub> стоит единица), то есть K<sub>1</sub>, K<sub>2</sub>, K<sub>4</sub>, K<sub>5</sub>, K<sub>7</sub>. Дизъюнкция этих конъюнкций есть пересечение тупиковых.
-Для нахождения всех тупиковых ДНФ построим КНФ, элементарныё дизъюнкции которой будут состоять из БП, соответствующих тем конъюнкциям, в которые входит рассматриваемая точка &alpha;<sub>i</sub> (то есть, всего дизъюнкций столько же, сколько есть точек, где функция принимает единичное значение, причём первая дизъюнкция будет содержать те БП, которые соответствуют тем ЭК, которым принадлежит &alpha;<sub>1</sub> (в данном примере это K<sub>1</sub>), вторая — те, которые соответствуют ЭК, которым принадлежит &alpha;<sub>2</sub> (K<sub>1</sub>, K<sub>2</sub>, K<sub>3</sub>), и так далее):
+Для нахождения всех тупиковых ДНФ построим КНФ, элементарныё дизъюнкции которой будут состоять из БП, соответствующих тем конъюнкциям, в которые входит рассматриваемая точка &alpha;<sub>i</sub> (то есть, всего дизъюнкций столько же, сколько есть точек, где фугкция принимает единичное значение, причём первая дизъюнкция будет содержать те БП, которые соответствуют тем ЭК, которым принадлежит &alpha;<sub>1</sub> (в данном примере это K<sub>1</sub>), вторая — те, которые соответствуют ЭК, которым принадлежит &alpha;<sub>2</sub> (K<sub>1</sub>, K<sub>2</sub>, K<sub>3</sub>), и так далее):
 K<sub>1</sub> & (K<sub>1</sub> ∨ K<sub>2</sub> ∨ K<sub>3</sub>) & K<sub>2</sub> & (K<sub>3</sub> ∨ K<sub>6</sub>) & K<sub>4</sub> & (K<sub>4</sub> ∨ K<sub>5</sub> ∨ K<sub>7</sub>) & K<sub>5</sub> & (K<sub>6</sub> ∨ K<sub>7</sub>) & K<sub>7</sub> & K<sub>7</sub>

Редактирование: Основы Кибернетики, Алгоритмы решения задач/Задачи на ДНФ

Материал из eSyr's wiki.

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты