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

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

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

Рассмотрим пример представления конечно­го алфавитного оператора с помощью конечного предиката. Пусть нам дан оператор FX=Y, преоб­разующий двухбуквенные слова X=x1x2 русского алфавита в однобуквенные слова Y=y1 того же ал­фавита. Вид преобразования указан в табл. 2. Это­му алфавитному оператору ставим в соответствие предикат t=f(x1, x2, y1), описываемый табл. 3. В та­блице указаны не все столбцы, а только те из них, у которых в последней строке стоит значение 1. По­лагаем, что во всех отсутствующих столбцах преди­кат принимает значение 0.

Таблица 2

Х

до

ре

ми

фа

ля

си

У

а

о

у

и

е

я

Таблица 3

x1

д

р

м

ф

л

с

x2

о

е

и

а

я

и

y1

а

о

у

и

е

я

t

1

1

1

1

1

1

Поскольку в русском алфавите 33 буквы, то общее число столбцов таблицы должно было бы составлять 333=30 тысяч. В связи со столь резким увеличением размера таблицы у читателя может сложиться впечатление, что представление опера­торов в виде конечных предикатов не дает никаких преимуществ и даже усложняет дело, однако это не так. Дело в том, что конечные предикаты, в отли­чие от конечных алфавитных операторов, которые пришлось бы описывать средствами многозначной логики, допускают весьма удобную аналитическую запись, сходную с формулами алгебры логики [6]. К разработке этой аналитической записи мы сей­час и приступаем.

5. Формулы алгебры конечных предикатов

Для того чтобы получить возможность записы­вать конечные предикаты в виде формул, мы вве­дем специальную алгебраическую систему, которая называется алгеброй конечных предикатов. Точнее, будет введена не одна алгебра, а целое семейство таких алгебр. Каждая алгебра конечных предика­тов полностью характеризуется алфавитом букв А, состоящим из к символов a1, а2, ак, и алфа­витом переменных В, состоящим из п символов x1, x2,..., xn. Средствами алгебры конечных предика­тов с алфавитом букв А={а1, а2,..., ак} и алфавитом переменных B={x1, x2,..., xn} может быть записан любой n-местный к-ичный предикат f(x1, x2,..., xn), заданный над алфавитом А. Мы будем считать, что буквы и переменные алфавитов А и В пронумеро­ваны.

Введем понятие формулы алгебры конечных пре­дикатов с алфавитом букв {а1, а2, ак} и алфа­витом переменных {x1, x2,..., xn}. Формулы будем строить из следующих символов: букв а1, а2,..., ак, переменных x1, x2,..., xn, знаков дизъюнкции v и конъюнкции л, открывающей и закрывающей ско­бок (, ), логических констант 0 и 1, называемых со­ответственно ложью и истиной. Понятие формулы алгебры конечных предикатов определим индук­тивно с помощью следующей системы из четырех правил: 1) символы 0 и 1 называем формулами; 2) все выражения вида а^), где индекс i находится в пределах от 1 до к, а индекс j в пределах от 1 до п называем формулами; 3) если выражения А и В яв­ляются формулами, то выражение ^vB) называем формулой; 4) если выражения А и В формулы, то выражение лВ) — тоже формула.

Каждую формулу будем рассматривать как обо­значение некоторого предиката fx1, x2,..., xn), за­данного над алфавитом {а1, а2,..., ак}. Закон соот­ветствия между формулами и обозначаемыми ими предикатами определяем индуктивно следующими правилами: 1) формула 0 обозначает тождествен­но ложный предикат, то есть предикат, равный 0 для всех наборов значений аргументов; 2) формула 1 обозначает тождественно истинный предикат, то есть предикат, равный 1 для всех наборов значений аргументов; 3) формула a(xj) обозначает предикат, равный 1 для всех тех наборов значений аргумен­тов, у которых xj=ai, и равный 0 — для всех осталь­ных наборов. Пусть формула А обозначает преди­кат f, а формула В предикат g; тогда: 4) формула ^vE) обозначает предикат, равный 0 для всех тех наборов значений аргументов, при которых f=0 и g=0, и равный 1 — для остальных наборов; 5) фор­мула (АлЕ) обозначает предикат, равный 1 для всех тех наборов значений аргументов, при которых f =1 и g=1, и равный 0 — для остальных наборов.

Предикат ^vB) называется дизъюнкцией или логической суммой, а предикат (АлЕ) конъюнк­цией или логическим произведением предикатов А и В. Функция, которая ставит в соответствие лю­бым предикатам А и В предикат ^vB), называет­ся операцией дизъюнкции или логического сложения предикатов. Аналогично функцию, сопоставляю­щую произвольным предикатам А и В предикат (АлЕ), назовем операцией конъюнкции или логиче­ского умножения предикатов. Операции дизъюнк­ции и конъюнкции будем называть элементарными операциями алгебры конечных предикатов. Пусть x, y — логические переменные. Функция xvy со значениями 0v0=0, 0v1=1, 1 v0=1, 1 v1=1 называ­ется функцией дизъюнкции, а функция xлy со зна­чениями 0л0=0, 0л1=0, 1 л0=0, 1 л1=1 — функцией конъюнкции. В ряде случаев формулы алгебры ко­нечных предикатов удобно рассматривать как зна­чения соответствующих предикатов, то есть как логические константы. При такой интерпретации записи вида ^vE) и (АлЕ) можно рассматривать как функции дизъюнкции и конъюнкции, а входя­щие в их состав выражения А и В как логические переменные.

Каждую формулу вида ai(xj) удобно рассматри­вать как одноместный предикат, зависящий толь­ко от переменной xj и определяемый следующим образом:

[1, если x, = a,

a (xj) = l0       j (3)

J    10, если    ф at.

Предикат ai(xj) как бы "узнаёт" одну единствен­ную букву ai среди возможных букв алфавита А, поэтому назовем его предикатом узнавания буквы ai или просто узнаванием буквы ai, зависящим от переменной x,. Всего имеется кп различных узна­ваний букв. Действуя на различные узнавания букв операциями дизъюнкции и конъюнкции, много­кратно и в различном порядке, мы получаем раз­личные предикаты. Узнавания букв будем считать элементарными предикатами алгебры конечных пре­дикатов. Совокупность элементарных операций и элементарных предикатов образует базис алгебры конечных предикатов.

Рассмотрим пример формулы алгебры конеч­ных предикатов. Пусть к=3, п=4, a1=а, a2=м, a3=i, x1=x, x2=y, x3=z, x4=t. Выражение

((аООла^Жм^ЖппШ) (a)

есть формула алгебры конечных предикатов. Действительно, согласно второму правилу, вы­ражения а(y), а(і), м(x), м(z), п(x), п(z) — фор­мулы. С помощью четвертого правила из имею­щихся уже формул строим следующие формулы: (аО')ла(О), (м(xм(z)), (п(xп(z)). Из двух по­следних формул по третьему правилу образуем формулу ((м(xм(z))v(п(xп(z))). Наконец, при­меняя четвертое правило к формулам (аОа^)), ((мм^ЖОпп^))), получаем формулу (а).

Недостатком введенных формул является то, что они выглядят неоправданно громоздкими. Это хорошо видно на приведенном примере. Этот не­достаток мы компенсируем тем, что будем пользо­ваться сокращенной записью формул. При пере­ходе от полной записи формулы к сокращенной будем опускать внешние скобки, то есть формулы ^vE) и (АлЕ) мы будем писать в виде АvE и АлЕ. Далее, узнавания букв ai(xj) будем записывать в бо­лее краткой и удобной форме xai , называя букву ai в этой записи показателем узнавания буквы. На­конец, знак конъюнкции в сокращенных записях формул будем заменять точкой или же вовсе опу­скать АлЕ=АВ=АВ.

Кроме того, в записях формул будем опускать все те скобки, наличие которых не обязательно для правильного понимания смысла формулы. Если скобки, регулирующие порядок выполнения действий в сокращенной записи формулы не ука­заны, то, по принимаемому нами соглашению о старшинстве операций, вначале будем выполнять операции конъюнкции и лишь затем — операции дизъюнкции, например запись AvEлC следует по­нимать как формулу Av(EлC). Этим соглашением операция конъюнкции принимается старшей по отношению к операции дизъюнкции. При отсут­ствии скобок в формуле условимся первой из одно­типных операций выполнять ту, знак которой сто­ит в формуле левее, например, AvEvC=(AvE)vC, АлЕлС=(АлЕС. Принятые нами правила сокра­щения записи формул таковы, что при необходимо -сти всегда можно от сокращенной записи формулы перейти к самой формуле. Применяя, к примеру, только что рассмотренные способы сокращенной записи, формулу (а) можно представить в более компактном и удобном для чтения виде:

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

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

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

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

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