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

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

Перейти к: навигация, поиск

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

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

Текущая версия Ваш текст
Строка 1: Строка 1:
-
== По заданной ФАЛ построить ее сокращенную ДНФ, ДНФ Квайна, ДНФ сумма тупиковых, все тупиковые ДНФ ==
+
== From Ebaums Inc to MurkLoar. ==
-
 
+
We at EbaumsWorld consider you as disgrace of human race.
-
=== Определения ===
+
Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
-
 
+
Dig yourself a grave - you will need it.
-
==== Функция алгебры логики ====
+
-
'''Функция алгебры логики''' — функция, переводящая вектор из n-элементов множества B = {0, 1} в элемент множества B. То есть, для каждого набора нулей и единиц у функции определено значение, равное нулю или единице.
+
-
 
+
-
=== Построение сокращённой ДНФ ===
+
-
 
+
-
==== Определения ====
+
-
 
+
-
===== Буква x<sup>&sigma;</sup> =====
+
-
Есть алфавит ''X''(n) = {''x''<sub>1</sub>, &hellip; ''x''<sub>n</sub>}. '''Буква ''x''<sub>i</sub><sup>&sigma;</sup>''' есть ''x''<sub>i</sub>, если &sigma; = 1, и ''x̅''<sub>i</sub>, если &sigma; = 0.
+
-
 
+
-
===== Конъюнкция ранга r =====
+
-
'''Конъюнкция ранга r''' ''K'' = ''x''<sub>i<sub>1</sub></sub><sup>&sigma;<sub>1</sub></sup>&hellip;''x''<sub>i<sub>r</sub></sub><sup>&sigma;<sub>r</sub></sup>, 0 &le; r &le; n; ''K'' = 0 при ''r'' = 0.
+
-
 
+
-
===== Элементарная конъюнкция =====
+
-
'''Элементарная конъюнкция''' — конъюнкция, у которой все переменные в буквах различны: ''x''<sub>i<sub>k</sub></sub><sup>&sigma;<sub>l</sub></sup> &ne; ''x''<sub>i<sub>l</sub></sub><sup>&sigma;<sub>l</sub></sup> при 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''<sub>1</sub>
+
-
* (&minus; 1 0) &rarr; ''x''<sub>2</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub>
+
-
* (&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>
+
-
 
+
-
==== Метод Блейка ====
+
-
Пусть у нас имеется произвольная ДНФ функции ''f''. Определим два преобразования:
+
-
* <span style="border-top:solid 1px">''x''</span>A ∨ ''x''B &rarr; <span style="border-top:solid 1px">''x''</span>A ∨ ''x''B ∨ AB
+
-
* A ∨ AB &rarr; A
+
-
Тогда, если сначала применять к имеющейся ДНФ первое преобразование, пока это возможно, а потом — второе, то получим сокращённую ДНФ.
+
-
 
+
-
===== Пример =====
+
-
Построить сокращённую ДНФ по имеющейся ДНФ
+
-
 
+
-
x1x2x3 ∨ x1<span style="border-top:solid 1px">''x2''</span>x3 ={применяем первое правило}= x1x2x3 ∨ x1<span style="border-top:solid 1px">''x2''</span>x3 ∨ x1x3 ={применяем второе правило дважды}= x1x3
+
-
 
+
-
==== Метод Нельсона ====
+
-
Метод Нельсона использует КНФ функции ''f''. Для построения сокращённой ДНФ по КНФ достаточно раскрыть скобки и привести подобные методом поглощения (A ∨ AB &rarr; A)
+
-
 
+
-
===== Пример =====
+
-
Построить сокращённую ДНФ по имеющейся КНФ
+
-
f(x<sub>1</sub>,x<sub>2</sub>,x<sub>3</sub>)=(<span style="border-top:solid 1px">''x''</span><sub>3</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub>)(x<sub>1</sub> ∨ x<sub>2</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>3</sub>)
+
-
 
+
-
f = <span style="border-top:solid 1px">''x''</span><sub>3</sub>x<sub>1</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>3</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>3</sub> ∨ <strike>(<span style="border-top:solid 1px">''x''</span></strike><sub>1</sub><strike>x</strike><sub>1</sub><strike>)</strike> ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub>x<sub>2</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub>
+
-
= <span style="border-top:solid 1px">''x''</span><sub>3</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>3</sub>x<sub>2</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub> ∨ <span style="border-top:solid 1px">''x''</span><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>1</sub>x<sub>2</sub>
+
-
 
+
-
==== Метод с использованием карт Карно ====
+
-
Данный метод удобен для функций от 4 переменных (его также можно использовать для функций от 3 переменных, но для них обычно используются другие методы). Он основан на нахождении блоков единиц на построенной специальном образом карте значений функции. Карта строится следующим образом: по вертикали выписываются переменные ''x''<sub>1</sub>, ''x''<sub>2</sub>; по горизонатли — ''x''<sub>3</sub>, ''x''<sub>4</sub>. Пары переменых выписываются в порядке (00), (01), (11), (10). После чего в таблицу заносятся значения функции для данных значений переменных. Рассмотрим построение карты для функции f = (f<sub>0000</sub>f<sub>0001</sub>f<sub>0010</sub>f<sub>0011</sub> f<sub>0100</sub>f<sub>0101</sub>f<sub>0110</sub>f<sub>0111</sub> f<sub>1000</sub>f<sub>1001</sub>f<sub>1010</sub>f<sub>1011</sub> f<sub>1100</sub>f<sub>1101</sub>f<sub>1110</sub>f<sub>1111</sub>):
+
-
 
+
-
{|
+
-
!rowspan="2" colspan="2"|&nbsp;
+
-
!''x''<sub>3</sub>
+
-
!0
+
-
!0
+
-
!1
+
-
!1
+
-
|-
+
-
!''x''<sub>4</sub>
+
-
!0
+
-
!1
+
-
!1
+
-
!0
+
-
|-
+
-
!''x''<sub>1</sub>
+
-
!''x''<sub>2</sub>
+
-
!&nbsp;
+
-
!colspan="4"|&nbsp;
+
-
|-
+
-
!0
+
-
!0
+
-
!&nbsp;
+
-
|f<sub>0000</sub>
+
-
|f<sub>0001</sub>
+
-
|f<sub>0011</sub>
+
-
|f<sub>0010</sub>
+
-
|-
+
-
!0
+
-
!1
+
-
!&nbsp;
+
-
|f<sub>0100</sub>
+
-
|f<sub>0101</sub>
+
-
|f<sub>0111</sub>
+
-
|f<sub>0110</sub>
+
-
|-
+
-
!1
+
-
!1
+
-
!&nbsp;
+
-
|f<sub>1100</sub>
+
-
|f<sub>1101</sub>
+
-
|f<sub>1111</sub>
+
-
|f<sub>1110</sub>
+
-
|-
+
-
!1
+
-
!0
+
-
!&nbsp;
+
-
|f<sub>1000</sub>
+
-
|f<sub>1001</sub>
+
-
|f<sub>1011</sub>
+
-
|f<sub>1010</sub>
+
-
|}
+
-
 
+
-
Далее на полученной карте находим все максимально возможные блоки единиц вида 2<sup>k</sup> &times; 2<sup>l</sup>; k, l &isin; '''N''', учитывая тот факт, что карта закольцована. Блоки могут пересекаться, но не должны включать друг друга. Далее для каждого блока выписывается вектор, в котором в случае, если переменная в пределах этого блока меняла значение, знак «–», если же не меняет, то её значение в пределах блока. Для позиций вектора ''i'', в которых стоит знак &sigma; &isin; {0, 1}? в ЭК добавляется x<sub>i</sub><sup>&sigma;</sup>. Дизъюнкция всех полученных ЭК и есть сокращённая ДНФ.
+
-
 
+
-
===== Пример =====
+
-
Найдём сокращённую ДНФ для функции ''f'' = (1010 0110 0111 1101) методом карт Карно.
+
-
 
+
-
'''Решение'''<br />
+
-
Строим карту:<br />
+
-
[[Изображение:Karno.png|240px]]
+
-
 
+
-
На основании карты получаем следующие блоки:
+
-
* (0 0 &minus; 0) = <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>
+
-
* (0 &minus; 1 0) = <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>
+
-
* (&minus; 0 1 0) = <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>
+
-
* (&minus; 1 0 1) = ''x''<sub>2</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub>''x''<sub>4</sub>
+
-
* (1 1 0 &minus;) = ''x''<sub>1</sub>''x''<sub>2</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub>
+
-
* (1 0 1 &minus;) = ''x''<sub>1</sub><span style="border-top:solid 1px">''x''</span><sub>2</sub>''x''<sub>3</sub>
+
-
* (1 &minus; &minus; 1) = ''x''<sub>1</sub>''x''<sub>4</sub>
+
-
 
+
-
В результате получаем сокращённую ДНФ <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
+
-
 
+
-
==== Построение сокращенной ДНФ по совершенной ДНФ при помощи алгоритма Квайна ====
+
-
Алгоритм Квайна построения сокращенной ДНФ по совершенной ДНФ:
+
-
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 1
+
-
 
+
-
=== Построение ДНФ Квайна ===
+
-
 
+
-
ДНФ, которую получают путем выбрасывания всех простых импликант, соответствующих максимальным граням, которые покрываются ядром, называется '''ДНФ Квайна'''.
+
-
 
+
-
Алгоритм построения ДНФ Квайна:
+
-
 
+
-
1. получить сокращенную ДНФ;
+
-
 
+
-
2. найти ядровые грани;
+
-
 
+
-
3. удалить импликанты, покрываемые ядром.
+
-
 
+
-
Полученная ДНФ, является ДНФ Квайна.
+
-
 
+
-
=== Построение ДНФ &Sigma;T (суммы тупиковых) ===
+
-
 
+
-
см ниже
+
-
 
+
-
=== Построение всех тупиковых ДНФ ===
+
-
Пусть мы ищем все тупиковые решения для ФАЛ f. Выпишем таблицу M(''таблицу Квайна''), в которой столбцам соответствуют элементы из ''N<sub>f</sub>'' (наборы, на которых функция принимает значение 1), строкам соответствуют максимальные грани. В ячейке стоит 1, если грань, соответствующая строке содержит набор, соответствующий столбцу.
+
-
 
+
-
Затем выписываем КНФ функции покрытия следующим образом:
+
-
 
+
-
Пусть каждой строке соответствует некоторая переменая ''y<sub>i</sub>''.
+
-
 
+
-
Для каждого столбца, переменные, соотвествующие строкам в которых в данном столбце стоит 1, запишем через логическое или. Функция покрытия равна произведению таких сумм для каждого столбца.
+
-
 
+
-
==== Пример ====
+
-
Есть функция g: ''N<sub>g</sub> = {&alpha;<sub>1</sub> = (100), &alpha;<sub>2</sub> = (110), &alpha;<sub>3</sub> = (010), &alpha;<sub>4</sub> = (011), &alpha;<sub>5</sub> = (001), &alpha;<sub>6</sub> = (101) }''.
+
-
 
+
-
Множество максимальных граней = ''{N<sub>1</sub>,&hellip;,N<sub>6</sub>}'', где ''N<sub>i</sub>={&alpha;<sub>i</sub>,&alpha;<sub>i+1</sub>}'', причем &alpha;<sub>7</sub>=&alpha;<sub>1</sub>.
+
-
 
+
-
Таблица Квайна:
+
-
 
+
-
<center>[[Изображение:mKvaina.png]]</center>
+
-
 
+
-
ФАЛ покрытия: ''F(y) = (y<sub>6</sub> &or; y<sub>1</sub>)(y<sub>1</sub> &or; y<sub>2</sub>)(y<sub>2</sub> &or; y<sub>3</sub>)(y<sub>3</sub> &or; y<sub>4</sub>)(y<sub>4</sub> &or; y<sub>5</sub>)(y<sub>5</sub> &or; y<sub>6</sub>).''
+
-
 
+
-
Раскрывая скобки и приводя подобные, получаем:
+
-
 
+
-
''F(y) = y<sub>1</sub>y<sub>3</sub>y<sub>5</sub> &or; y<sub>2</sub>y<sub>4</sub>y<sub>6</sub> &or; y<sub>1</sub>y<sub>2</sub>y<sub>4</sub>y<sub>5</sub> &or; y<sub>2</sub>y<sub>3</sub>y<sub>5</sub>y<sub>6</sub> &or; y<sub>1</sub>y<sub>3</sub>y<sub>4</sub>y<sub>5</sub>''.
+
-
 
+
-
Это соответствет тупиковым покрытиям ''1 = N<sub>1</sub>N<sub>3</sub>N<sub>5</sub>; 2 = N<sub>2</sub>N<sub>4</sub>N<sub>6</sub>; и т.д.''
+
-
 
+
-
==== Пример ====
+
-
Построить все тупиковые ДНФ для ФАЛ ''f'' = (1010 0110 0111 1101).
+
-
 
+
-
'''Решение.'''
+
-
 
+
-
Сокращённая ДНФ для данной функции есть <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> (как было получено [[#Метод с использованием карт Карно|ранее]]). Выпишем все точки, где ЭК принимают значение, равное единице, следующим образом:
+
-
{|
+
-
!ЭК
+
-
!<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>
+
-
|-
+
-
!&alpha;<sub>i</sub>
+
-
|&alpha;<sub>1</sub>&nbsp;=&nbsp;(0000)<br />&alpha;<sub>2</sub>&nbsp;=&nbsp;(0010)
+
-
|&nbsp;
+
-
|&alpha;<sub>2</sub>&nbsp;=&nbsp;(0010)<br />&alpha;<sub>3</sub>&nbsp;=&nbsp;(0110)
+
-
|&nbsp;
+
-
|&alpha;<sub>2</sub>&nbsp;=&nbsp;(0010)<br />&alpha;<sub>4</sub>&nbsp;=&nbsp;(1010)
+
-
|&nbsp;
+
-
|&alpha;<sub>5</sub>&nbsp;=&nbsp;(0101)<br />&alpha;<sub>6</sub>&nbsp;=&nbsp;(1101)
+
-
|&nbsp;
+
-
|&alpha;<sub>7</sub>&nbsp;=&nbsp;(1100)<br />&alpha;<sub>6</sub>&nbsp;=&nbsp;(1101)
+
-
|&nbsp;
+
-
|&alpha;<sub>4</sub>&nbsp;=&nbsp;(1010)<br />&alpha;<sub>8</sub>&nbsp;=&nbsp;(1011)
+
-
|&nbsp;
+
-
|&alpha;<sub>9</sub>&nbsp;=&nbsp;(1001)<br />&alpha;<sub>8</sub>&nbsp;=&nbsp;(1011)<br />&alpha;<sub>6</sub>&nbsp;=&nbsp;(1101)<br />&alpha;<sub>10</sub>&nbsp;=&nbsp;(1111)
+
-
|}
+
-
 
+
-
Построим таблицу (таблицу Квайна), у которой по строкам указаны ЭК, а по столбцам — точки, где функция принимает значение, равное единице. На пересечении ЭК и точки будет стоять значение ЭК в этой точке (фактически, входит ли данная точка в характеристическое множество данной ЭК, или нет). Для наглядности, единицы выделены.
+
-
{|style="text-align:center"
+
-
!&nbsp;
+
-
!&alpha;<sub>1</sub>
+
-
!&alpha;<sub>2</sub>
+
-
!&alpha;<sub>3</sub>
+
-
!&alpha;<sub>4</sub>
+
-
!&alpha;<sub>5</sub>
+
-
!&alpha;<sub>6</sub>
+
-
!&alpha;<sub>7</sub>
+
-
!&alpha;<sub>8</sub>
+
-
!&alpha;<sub>9</sub>
+
-
!&alpha;<sub>10</sub>
+
-
|-
+
-
!K<sub>1</sub>&nbsp;=&nbsp;<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>
+
-
!1 <!-- 1 -->
+
-
!1 <!-- 2 -->
+
-
|0 <!-- 3 -->
+
-
|0 <!-- 4 -->
+
-
|0 <!-- 5 -->
+
-
|0 <!-- 6 -->
+
-
|0 <!-- 7 -->
+
-
|0 <!-- 8 -->
+
-
|0 <!-- 9 -->
+
-
|0 <!-- 10 -->
+
-
|-
+
-
!K<sub>2</sub>&nbsp;=&nbsp;<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>
+
-
|0 <!-- 1 -->
+
-
!1 <!-- 2 -->
+
-
!1 <!-- 3 -->
+
-
|0 <!-- 4 -->
+
-
|0 <!-- 5 -->
+
-
|0 <!-- 6 -->
+
-
|0 <!-- 7 -->
+
-
|0 <!-- 8 -->
+
-
|0 <!-- 9 -->
+
-
|0 <!-- 10 -->
+
-
|-
+
-
!K<sub>3</sub>&nbsp;=&nbsp;<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>
+
-
|0 <!-- 1 -->
+
-
!1 <!-- 2 -->
+
-
|0 <!-- 3 -->
+
-
!1 <!-- 4 -->
+
-
|0 <!-- 5 -->
+
-
|0 <!-- 6 -->
+
-
|0 <!-- 7 -->
+
-
|0 <!-- 8 -->
+
-
|0 <!-- 9 -->
+
-
|0 <!-- 10 -->
+
-
|-
+
-
!K<sub>4</sub>&nbsp;=&nbsp;''x''<sub>2</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub>''x''<sub>4</sub>
+
-
|0 <!-- 1 -->
+
-
|0 <!-- 2 -->
+
-
|0 <!-- 3 -->
+
-
|0 <!-- 4 -->
+
-
!1 <!-- 5 -->
+
-
!1 <!-- 6 -->
+
-
|0 <!-- 7 -->
+
-
|0 <!-- 8 -->
+
-
|0 <!-- 9 -->
+
-
|0 <!-- 10 -->
+
-
|-
+
-
!K<sub>5</sub>&nbsp;=&nbsp;''x''<sub>1</sub>''x''<sub>2</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub>
+
-
|0 <!-- 1 -->
+
-
|0 <!-- 2 -->
+
-
|0 <!-- 3 -->
+
-
|0 <!-- 4 -->
+
-
|0 <!-- 5 -->
+
-
!1 <!-- 6 -->
+
-
!1 <!-- 7 -->
+
-
|0 <!-- 8 -->
+
-
|0 <!-- 9 -->
+
-
|0 <!-- 10 -->
+
-
|-
+
-
!K<sub>6</sub>&nbsp;=&nbsp;''x''<sub>1</sub><span style="border-top:solid 1px">''x''</span><sub>2</sub>''x''<sub>3</sub>
+
-
|0 <!-- 1 -->
+
-
|0 <!-- 2 -->
+
-
|0 <!-- 3 -->
+
-
!1 <!-- 4 -->
+
-
|0 <!-- 5 -->
+
-
|0 <!-- 6 -->
+
-
|0 <!-- 7 -->
+
-
!1 <!-- 8 -->
+
-
|0 <!-- 9 -->
+
-
|0 <!-- 10 -->
+
-
|-
+
-
!K<sub>7</sub>&nbsp;=&nbsp;''x''<sub>1</sub>''x''<sub>4</sub>
+
-
|0 <!-- 1 -->
+
-
|0 <!-- 2 -->
+
-
|0 <!-- 3 -->
+
-
|0 <!-- 4 -->
+
-
|0 <!-- 5 -->
+
-
!1 <!-- 6 -->
+
-
|0 <!-- 7 -->
+
-
!1 <!-- 8 -->
+
-
!1 <!-- 9 -->
+
-
!1 <!-- 10 -->
+
-
|}
+
-
 
+
-
Далее, определим ядровые точки, то есть те &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>), и так далее):
+
-
 
+
-
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>
+
-
 
+
-
После раскрытия и приведения подобных получим ДНФ, состоящих из ЭК, которые будут соответствовать тупиковым ДНФ, причём БП в ЭК будут соответствовать ЭК, входящим в тупиковую ДНФ:
+
-
 
+
-
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> = K<sub>1</sub>K<sub>2</sub>K<sub>4</sub>K<sub>5</sub>K<sub>7</sub> & (K<sub>1</sub> ∨ K<sub>2</sub> ∨ K<sub>3</sub>) & (K<sub>3</sub> ∨ K<sub>6</sub>) & (K<sub>4</sub> ∨ K<sub>5</sub> ∨ K<sub>7</sub>) & (K<sub>6</sub> ∨ K<sub>7</sub>) = K<sub>1</sub>K<sub>2</sub>K<sub>4</sub>K<sub>5</sub>K<sub>3</sub>K<sub>7</sub> ∨ K<sub>1</sub>K<sub>2</sub>K<sub>4</sub>K<sub>5</sub>K<sub>6</sub>K<sub>7</sub>
+
-
 
+
-
ДНФ K<sub>1</sub>K<sub>2</sub>K<sub>3</sub>K<sub>4</sub>K<sub>5</sub>K<sub>7</sub> ∨ K<sub>1</sub>K<sub>2</sub>K<sub>4</sub>K<sub>5</sub>K<sub>6</sub>K<sub>7</sub> соответствует тупиковым ДНФ
+
-
{|
+
-
!K<sub>1</sub> ∨ K<sub>2</sub> ∨ K<sub>3</sub> ∨ K<sub>4</sub> ∨ K<sub>5</sub> ∨ K<sub>7</sub>
+
-
|<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>''x''<sub>4</sub>
+
-
|-
+
-
!K<sub>1</sub> ∨ K<sub>2</sub> ∨ K<sub>4</sub> ∨ K<sub>5</sub> ∨ K<sub>6</sub> ∨ K<sub>7</sub>
+
-
|<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> ∨ ''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>
+
-
|}
+
-
 
+
-
{{Курс Основы Кибернетики}}
+

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. 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
Личные инструменты
Разделы