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

Страницы:
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 

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

Введем понятия элементарной дизъюнкции, конституэнты нуля и конъюнктивной нормальной формы. Эти понятия не являются двойственными понятиями элементарной конъюнкции, конститу­энты единицы и ДНФ, как это имеет место в алгебре логики. Элементарной дизъюнкцией назовем такую дизъюнкцию узнаваний букв, в которую каждое узнавание буквы может входить не более одного раза и ни одна из переменных не может входить не более к-1 раз. Элементарной дизъюнкцией, не со­держащей ни одного дизъюнктивного члена, будем считать формулу 0. Иными словами, никакая пере­менная не может быть представлена в элементар­ной дизъюнкции всеми своими узнаваниями, хотя бы одно из узнаваний должно отсутствовать. При­мерами элементарных дизъюнкций при A={a, b, c}, B={x1, x2, x3} могут служить формулы:

x" v x] ; x" v xxc v x2; x2 v x2 v x" v xf . Формула

x" v x] v x[ v x"

не является элементарной дизъюнкцией, так как в нее входят все узнавания буквы для перемен­ной x1. Такая формула выражает тождественно ис­тинный предикат.

Любую конъюнкцию произвольного числа раз­личных элементарных дизъюнкций назовем конъ­юнктивной нормальной формой (КНФ) предиката. В качестве КНФ не содержащей ни одного конъ­юнктивного члена, примем формулу 1. Пример

КНФ:

(x" v x2)(x" v xf v x2)(x2 v x2 v x" v xf) .

Любую элементарную дизъюнкцию, в которой встречаются все переменные алгебры конечных предикатов, причем каждая из них входит к-1 раз в составе узнаваний букв с различным показате­лями, назовем конституантой нуля. Условимся в конституэнте нуля все узнавания букв располагать в порядке роста номеров переменных, а для оди­наковых переменных — в порядке роста номеров букв, играющих роль показателей узнаваний бук­вы. Пример конституэнты нуля (в той же алгебре): x" v xl* v x2 v x2 v x" v xf.

Используя знак отрицания, можно записывать конституэнты нуля в более компактной форме, близкой к форме записи конституэнты единицы. Конституэнту нуля, приведенную в предыдущем примере, запишем так:

xf v x" v x\ .

Последняя форма записи конституэнты нуля инверсна форме записи конституэнты единицы: в ней вместо знаков конъюнкции стоят знаки дизъ­юнкции, а над узнаваниями букв появились знаки отрицания.

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

Кроме конъюнкции и дизъюнкции предикатов, рассмотренных ранее, введем в алгебре конечных предикатов еще одну двухместную операцию им­пликацию предикатов з, определив ее следующим равенством:

A з B=A v B . (22)

def

Буквы А и В обозначают произвольные формулы

алгебры конечных предикатов. Знак = обозначает

def

равенство предикатов по определению. Операцию з будем считать младшей по отношению к опера­циям л и v. Это значит, что при отсутствии в фор­муле скобок, регулирующих порядок выполнения операций, операция импликации должна выпол­нятся после выполнения операций конъюнкции и дизъюнкции.

Свойства импликации предикатов совпадают со свойствами импликации высказываний [3]. Вы­пишем наиболее важные из них — рефлексивность импликации:

АзА=1, (23) транзитивность импликации:

(АэВ)(ВзС)э(АзС)=1, (24)

свойства логических констант:

0зА=1, (25)

1зА=А, (26)

Аз0= А, (27)

Аз1=1, (28)

закон дедукции:

А(АзВ)зВ=1, (29)закон контрапозиции:

АзВ= В з А , закон импортации:

ззС))з(АВзС)=1,

(30) (31)

закон акспортации:

(АВзСззС))=1, (32) закон приведения к абсурду:

АА зВ=1. (33)

Используя операцию импликации, тождество (19) можно записать без знаков отрицания:

f(x1,

f\    XX...Xl з)

("1,"2,..,"l)   12 l

(34)

В соответствии с этим первое и второе следствия теоремы о конъюнктивном разложении запишутся в виде:

f(x1,

xn)

= (X"1 з f ("1, X2V.., Xn )) л л(xa2 зf("2,X2,^, Xn))л„. Л(xak з f("k, X2,^, Xn )).

(35)

f ^ x2,^, xn ) = (f("1,"/V,"n )=0(x1a1 x"2...x"n з 0). (36)

Последнее тождество называется импликатив-ным разложением предиката. Оно показывает, что любой конечный предикат может быть представ­лен в виде суперпозиции операций конъюнкции и импликации, действующих на всевозможные узна­вания букв, и на тождественно ложный предикат 0. Вместе с тем, как указывалось выше, при к>2 пре­дикат 0 можно выразить в виде конъюнкции неко­торых узнаваний букв, например, x"1 x"2 = 0 . Таким образом, мы приходим к еще одной полной алгебре конечных предикатов. Ее базис составляют опера­ции конъюнкции и импликации и всевозможные узнавания букв. Чтобы иметь возможность разли­чать обе введенные алгебры, первую назовем дизъ­юнктивной алгеброй конечных предикатов, а вторую — импликативной. Импликативная алгебра может быть получена из дизъюнктивной заменой в ее ба­зисе операции дизъюнкции операцией имплика­ции, и наоборот. Кроме двух найденных, существу­ет множество других алгебр конечных предикатов. В частности, любой набор операций, удовлетворя­ющий условиям теоремы Поста [4], вместе со все­возможными узнаваниями букв можно принять в качестве базиса полной алгебры конечных преди­катов. В роли полной системы элементарных опе­раций также подходит любая система операций, через которые выражаются операции конъюнк­ции и дизъюнкции или операции конъюнкции и импликации. По-видимому, существуют и другие базисы, задающие полные алгебры конечных пре­дикатов. Еще предстоит сформулировать критерий полноты для алгебр конечных предикатов.

В данной статье в качестве языка для записи ко­нечных предикатов принята дизъюнктивная алге­бра и различные ее консервативные расширения. Удобство дизъюнктивной алгебры конечных пре­дикатов состоит в том, что на ее языке кратко и изящно записываются законы истинности и лож­ности. Эти законы в любой алгебре конечных пре­дикатов будут играть особую роль. По существу, они представляют собой требования, выполнение которых необходимо и достаточно для корректно­го введения переменных на конечных множествах. Закон истинности задает область изменения пере­менной, а закон ложности обеспечивает попарное различие всех элементов множества, на котором заданна переменная. В любой другой алгебре за­коны истинности и ложности будут записываться в виде гораздо более громоздких выражений. В даль­нейшем дизъюнктивную алгебру и ее консерватив­ные расширения будем называть просто алгеброй конечных предикатов.

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

Существует целое множество дизъюнктивных и конъюнктивных нормальных форм, соответ­ствующих одному и тому же конечному предикату. Представляет интерес следующая задача: выбрать из этого множества такую форму, в которую входит наименьшее число узнаваний букв. Назовем эту задачу канонической задачей минимизации формул алгебры конечных предикатов. Умение минимизи­ровать формулы, как будет показано ниже, полезно при решении уравнений теории интеллекта, а так­же при построении схем, реализующих функции интеллекта. Дизъюнктивные и конъюнктивные нормальные формы, получаемые в результате ка­нонической минимизации, назовем минимальными ДНФ и КНФ. Проблема канонической минимиза­ции в алгебре конечных предикатов имеет много общего с одноименной проблемой в алгебре ло­гики. Все излагаемые в этой статье методы можно рассматривать как обобщение известных в алгебре логики методов канонической минимизации [5]:

а) Отыскание минимальной дизъюнктивной нор­мальной формы. Здесь мы наметим последователь­ность действий, которые должны быть выполнены при нахождении минимальной ДНФ. Предикат g назовем импликантой предиката f, если на любом наборе значений аргументов, для которого g=1, имеем также f=1. Будем говорить, что импликан-та g накрывает своими единицами единицы пре­диката f. Элементарную конъюнкцию g назовем собственной частью элементарной конъюнкции f, если g может быть получена из f выбрасываниемнекоторых узнаваний букв. Например, элементар­ная конъюнкция x1"x3b есть собственная часть эле­ментарной конъюнкции x1"x2cx3b. Назовем простой импликантой предиката f любую элементарную конъюнкцию, обладающую следующими свой­ствами: она есть импликанта предиката f и ника­кая ее собственная часть не является импликантой предиката f.

Страницы:
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 самых важных уроков библии

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

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

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

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