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

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

aoa=a, aAa=a, (23)

ao (aAb)=a, aA(aob)=a, (24)

aa 1=1, aA0=0, aA1=a, ao0=a, (25)

a1jOa2j0...cakj=1, (1<j<n), (26)

ahj Aahj =0, (і!*І2, 1<i*1, i2<k, 1<j<n). (27)

Тождества (20) — (27) назовем аксиомами аб­страктной алгебры конечных предикатов. Любая ал­гебраическая система, удовлетворяющая перечис­ленным требованиям, изоморфна [7] описанной ранее алгебре конечных предикатов. Чтобы перей­ти от абстрактного определения алгебры конечных предикатов к прежнему ее определению, следует множество Мпроинтерпретировать как множество всевозможных k-ичных я-местных предикатов, элементы 0 и 1 — как тождественно ложный и тож­дественно истинный предикаты, элементы atj как предикаты xai , операции о и A как дизъюнкцию и конъюнкцию предикатов.

Заметим, что только что приведенное опреде­ление абстрактной алгебры конечных предикатов допускает еще одну, двойственную первой, интер­претацию. А именно, множество M, как и прежде, интерпретируем как множество всевозможных k-ичных я-местных предикатов, элементы 0 и 1 — как тождественно истинный и тождественно лож­ный предикаты, элементы aij как предикаты вида:

[0, если x, = а,-,

1, если x, ф а.

(28)

Операции о и A интерпретируем как конъюнк­цию и дизъюнкцию предикатов. Интересно отме-об алгебре конечных предикатов

тить, что в пределах каждой из этих двух интерпре­таций абстрактной алгебры конечных предикатов при к>2 двойственности не наблюдается (такая двойственность имеет место в алгебре логики и в алгебре конечных предикатов при к=2). Хотя при замене знака о на A и знака 0 на 1, и наоборот, набор тождеств (20) — (25) остается тем же самым, однако тождества (26) и (27) не переходят друг в друга.

Выводы

Может показаться, что алгебра конечных пре­дикатов есть обобщение алгебры логики. Так, мы видим, что обе алгебры относятся к классу булевых алгебр. Кроме того, в частном случае, когда к=2 и A={0,1}, тождества (18) и (19) превращаются соот­ветственно в закон исключенного третьего xv x = 1 и закон противоречия xx =0 алгебры логики. Здесь обозначено x1=x, x0= x. Все тождества (4) — (19) алгебры конечных предикатов в этом случае по форме совпадают с тождествами алгебры логики. И все же неверно было бы утверждать, что алгебра логики — это частный случай алгебры конечных предикатов.

Дело в том, что смысл, вкладываемьгй в опера­цию отрицания x в алгебре логики и в предикат узнавания нуля x0 в алгебре конечных предикатов при k=2, A={0, 1}, различен. В то время как в алге­бре логики операцией отрицания можно действо­вать на любую булеву функцию, в алгебре конеч­ных предикатов при k=2, A={0, 1} положение иное: узнаванием нуля разрешается действовать лишь на буквенные аргументы х1, х2,..., хп, на предикаты же действовать узнаванием нуля не разрешается. В алгебре конечных предикатов выражения вида A0, где A — произвольная формула, не являются фор­мулами. А в алгебре логики выражения типа A это формулы.

Таким образом, алгебра логики не является частным случаем алгебры конечных предикатов. В этом обстоятельстве кроется объяснение того факта, что, как было отмечено выше, алгебра ко­нечных предикатов (без 0 и 1 и при к>2) несокра­тима. В алгебре же логики набор ее базисных (эле­ментарных) операций (отрицание, дизъюнкция и конъюнкция) можно сократить без потери данной алгеброй свойства полноты (например, можно ис­ключить операцию дизъюнкции), чего не могло бы случиться, если бы алгебра логики была частным случаем алгебры конечных предикатов. Алгебра конечных предикатов при к=2 и A={0, 1}, как алге­браическая система, насколько нам известно, в ли­тературе специально не рассматривалась. Однако она неявно присутствует во многих руководствах по алгебре логики. Так, например, в литературе можно встретить термин формулы с тесными отри­цаниями, обозначающий формулы алгебры логики, у которых отрицания могут стоять только непо­средственно над независимыми переменными [8]. К такого рода формулам алгебры логики относят­ся, в частности, дизъюнктивные и конъюнктивные нормальные формы, а также скобочные формы. Эти формы реализуют в виде двухступенчатых или многоступенчатых комбинационных схем, на вхо­ды которых поступают двоичные сигналы вместе с их отрицаниями [1].

Список литературы: 1. Глушков, В.М. Введение в киберне­тику. [Текст] / В.М. Глушков К.: Изд. АН УССР, 1964.

— 324 с. 2. Энциклопедия кибернетики [Текст] / Т. 1. — К.: Изд. АН УССР, 1974. — 608 с. 3. Глушков, В.М. Алгебра, языки, программирование [Текст] / В.М. Глушков, Г.Е. Цейтлин, Е.Л. Ющенко — К.: Наук. думка, 1974. — 318 с. 4. Новиков, П.С. Элементы математической логики [Текст] / П.С. Новиков М.: Наука, 1973. — 400 с. 5. Шрейдер, Ю.А. Равенство, сходство, порядок [Текст] / Ю.А. Шрейдер

М.: Наука, 1971. — 256 с. 6. Дискретная математика и математические вопросы кибернетики [Текст] / Под ред. С.В. Яблонского и О.Б. Лупанова. М.: Наука, 1974. — Т. 1. — 311 с. 7. Мальцев, А.И. Алгебраические системы [Текст] / А.И. Мальцев М.: Наука. — 1970. — 394 с. 8. Лавров, И.А. Задачи по теории множеств, математиче­ской логике и теории алгоритмов [Текст] / И.А. Лавров, Л.Л. Максимова М.: Наука, 1975. — 247 с.

Поступила в редколлегию 25.05.2011

УДК 519.7

Про алгебру екінченних предикатів / М.Ф. Бондарен­ко, Ю.П. Шабанов-Кушнаренко // Біоніка інтелекту: наук.-техн. журнал. — 2011. — № 3 (77). — С. 3-13.

Розробляється математична мова опису структур і функцій систем природного інтелекту. Введені поняття скінченного алфавітного оператора, алгебри скінченних предикатів і формул алгебри скінченних предикатів.

Табл. 3. Бібліогр.: 8 найм.

UDC 519.7

About algebra of final predicates / M.F. Bondarenko, Yu.P. Shabanov-Kushnarenko // Bionics of Intelligense: Sci. Mag. — 2011. — № 3 (77). —P. 3-13.

The mathematical language of structures and functions of the natural intellect systems description is developed. The concepts of finite alphabetical operator, algebras of finite predicates and formulas of finite predicates algebra, are en­tered.

Tab. 3. Ref.: 8 items.

БИОНИКА ИНТЕЛЛЕКТА. 2011. 3 (77). С. 14-29

ХНУРЭ

УДК 519.7

intelligence

М.Ф. Бондаренко, Ю.П. Шабанов-Кушнаренко

ХНУРЭ, г. Харьков, Украина

НОРМАЛЬНЫЕ ФОРМЫ ФОРМУЛ АЛГЕБРЫ КОНЕЧНЫХ ПРЕДИКАТОВ

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

ТЕОРИЯ ИНТЕЛЛЕКТА, ПРЕДИКАТ, АЛГЕБРА КОНЕЧНЫХ ПРЕДИКАТОВ, ДНФ, СДНФ, МИНИМИЗАЦИЯ ФОРМУЛ

Введение

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

1. Совершенная дизъюнктивная нормальная форма

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

x1 ax2b^/x'2'x'i'yvx1 bx2cx3 c.

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

x"1 x°2...x°nn = A x"i . Здесь ст1, "2 ,     "n некоторые фиксированные

n

буквы алфавита А, знак A обозначает операцию

логического перемножения n членов, i индекс, изменяющийся в пределах от 1 до n, по которому ведется перемножение.

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

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

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

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

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