Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 15

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

A(x01 vx"2 v... vx"r ) v AB(x01 vx"2 v ... vx"r) v

vB(xvx°r+2 v... vx"s ) v AB(xvx°r+2 v ... v

vs ) AB(x01 v x"2 v... vx"s ) v vA(x01 vx"2 v...v . vr ) vB(xvr+2 v... v° ) AB(xa1 v

vxa2 v... vxak) v A(x01 vx"2 v... vx"r ) vB(xV

vx"r+2 v... v xas) AB v A(xa1 v x"2 v ... v x"r) v

vB(xv x°r+2 v... v x°s) .

3) Исходную ДНФ пополняем дизъюнктивны­ми членами из системы, полученной на втором шаге алгоритма. В нашем примере имеем:

f      x2 V x1 x2 V x1 x3 V     x2     V x1 x2 x3 V x2 x3 .

4) Применяем всюду, где только возможно, опе­рацию дизъюнктивного поглощения A v AB A . В результате выполнения этого шага алгоритма по­лучаем сокращенную ДНФ конечного предиката. В примере сокращенная ДНФ имеет вид:

5) От сокращенной ДНФ переходим к минималь­ной ДНФ по методу, описанному в пункте б). В при­мере получаем следующую минимальную ДНФ:

Переходим к описанию алгоритма минимиза­ции формул алгебры конечных предикатов, обоб­щающего метод Нельсона минимизации формул алгебры логики. Исходной информацией при минимизации для этого алгоритма служит произ­вольно выбранная КНФ предиката, для которой отыскивается минимальная ДНФ. Рассмотрим пример. Пусть А={а, b, с}, B={x1, х2, х3}. Предикат fзадан следующей КНФ:

f (xa v x2C)(x2 v x2b v x3a).

1) Раскрываем скобки и уничтожаем все нуле­вые дизъюнктивные члены. В примере получаем:

2) Применяем операцию дизъюнктивного по­глощения. В результате получаем сокращенную ДНФ. В нашем примере применение операции дизъюнктивного поглощения не приводит к упро­щениям, поэтому формула, выведенная на первом шаге алгоритма, есть сокращенная ДНФ.

3) По методу, описанному в пункте б), перехо­дим от сокращенной ДНФ к минимальной ДНФ, которая в примере равна:

Отметим, что в рассмотренном примере ис­ходная КНФ предиката f имеет пять узнаваний букв, это меньше, чем в минимальной ДНФ, где их шесть. Этим примером демонстрируется важность задачи отыскания минимальной КНФ в алгебре конечных предикатов. Решение указанной задачи излагается в следующем пункте.

4. Конъюнктивная минимизация формул алгебры предикатов

г) отыскание минимальной конъюнктивной нормальной формы. В алгебре логики имеет место принцип двойственности, в силу которого методы отыскания минимальной КНФ оказываются со­вершенно аналогичными методам отыскания ми­нимальной ДНФ. В алгебре конечных предикатов при k>2 положение иное. Здесь мы лишены прин­ципа двойственности, он теперь утрачивает силу, операции конъюнкции и дизъюнкции теперь уже не равноправны. Поэтому методы конъюнктивной минимизации должны рассматривается специаль­но, здесь нельзя обойтись ссылкой на аналогию с методами дизъюнктивной минимизации.

Предикат g назовем имплицентой предиката f если на любом наборе значений аргументов, для которого g=0, имеем также f=0. Будем говорить, что имплицента g накрывает своими нулями нули предиката f. Элементарную дизъюнкцию g назовем собственной частью элементарной дизъюнкции f если g может быть получена из f выбрасыванием некоторых узнаваний букв. Например, элемен­тарная дизъюнкция xxa v x\ v x3 есть собственная часть элементарной дизъюнкции v xb v x2 v x3i .

Назовем простой имплицентой предиката f любую элементарную дизъюнкцию, обладающую следую­щими свойствами: она является имплицентой пре­диката f и никакая ее собственнная часть не явля­ется имплицентой предиката f

Конъюнкция любого числа имплицент конеч­ного предиката является имплицентой этого пре­диката. Систему S имплицент конечного предика­та f назовем полной, если любой нуль из таблицы значений предиката f накрывается нулями хотя бы одной имплиценты системы S. Тому или иному конечному предикату может соответствовать, во­обще говоря, несколько различных полных систем имплицент. Конъюнкция всех имплицент полной системы имплицент некоторого конечного преди­ката выражает собой этот предикат. Система всех простых имплицент любого конечного предиката есть его полная система. Конъюнкция всех про­стых имплицент конечного предиката выражает собой этот предикат, назовем ее сокращенной КНФ данного конечного предиката.

Конъюнктивным ядром конечного предиката на­зовем множество всех таких его простых импли-цент, исключение каждой из которых из системы всех простых имплицент делает систему неполной. Элементы конъюнктивного ядра входят в состав любой полной системы простых имплицент. Си­стему простых имплицент конечного предиката назовем приведенной, если она полна и никакое ее собственное подмножество не является полной системой. Конъюнкцию всех простых имплицент приведенной системы назовем тупиковой конъюн­ктивной нормальной формой предиката. Выбирая из числа тупиковых КНФ одну с наименьшим числом узнаваний, получаем минимальную КНФ.

Рассмотрим метод конъюнктивной минимиза­ции формул алгебры конечных предикатов, обоб­щающий метод Квайна-Мак-Класки. Исходной информацией при минимизации служит СКНФ предиката, для которого отыскивается минималь­ная КНФ. Рассмотрим пример. Пусть А={a, b, c}, B={x1, х2, х3}. Предикат задан следующей СКНФ:

f = (xa v x2a v x3a)(xa v x2b v x3a) Л

v    v    )(v    v    )(xf v x2 v    )Л

л(xf v x'2 v x'b)(xf v x'2 v x3).

СКНФ представлена в сокращенной записи с использованием знаков отрицания. Последующей обработке подвергается сама СКНФ, а не ее сокра­щенная запись.

Ниже описывается алгоритм минимизации: 1) Всюду, где это возможно, применяем опера­цию неполного конъюнктивного склеивания, осно­ванного на тождестве

(A v xa)(A v xaj) = (A v xa)(A v xa )A , (41)

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа