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

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

y^x^vx1^). (б)

От формулы всегда можно перейти к таблице обозначаемого ею предиката. Для этого нужно по формуле вычислить значения предиката для все­возможных наборов значений аргументов. Вы­числим, к примеру, значения предиката f(x, y, z, t), представленного формулой (б) для наборов значе­ний аргументов (м, а, м, а) и (м, а, п, а):

/(м, а, м, а)=аааа(ммм^мпмп)= = 1-1-(1-1v0-0)=1-(1v0)=1-1=1,

/(м, а, п, а)=аааа(ммп^мппп)= = 1-1-(1-0v0-1)=1-(0v0)=1-0=0.

Аналогичные вычисления для всевозможных четырехбуквенных наборов, составленных из букв а, м, п (их всего 34=81), показывают, что предикат f «узнаёт» два слова мама и папа: он ставит им в со­ответствие значение 1, то есть истину. Остальным словам предикат f ставит в соответствие значение 0, то есть ложь.

Возникает вопрос, полна ли введенная нами ал­гебра конечных предикатов, то есть для каждого ли конечного предиката найдется обозначающая его формула? Оказывается, что алгебра конечных пре­дикатов полна. Действительно, тождественно лож­ный предикат может быть записан в виде формулы 0.

Предикат, принимающий значение 1 только на одном наборе значений аргументов (ст1, "2,..., "n), можно представить формулой x"1 x"2...x"n . Пре­дикат, принимающий значение 1 на произвольных

наборах (СТц, "12,..., "1n), ("21, "22,..., "2n),..., ("m1,

"m2,..., "mn), может быть представлен формулой:

x"11 x"12     x"1n v x"21 x"22     x"2n v    v x"m1 x"m2     x"mn

* * * n       -^1^2    '''   -^1^2    * n '

Таким образом, любой конечный предикат мо­жет быть записан на языке алгебры конечных пре­дикатов.

Алгебра конечных предикатов не только пол­на, но даже в некотором смысле избыточна. Так, мы видим, что введенная в ней первым правилом формула 1 нам не понадобилась для записи произ­вольных предикатов. Обозначаемый формулой 1 тождественно истинный предикат может быть вы­ражен с помощью других средств алгебры конеч­ных предикатов, например, в форме дизъюнкции всевозможных конъюнкций видаx"1 x"2...x"n . В случае, когда k>2, то есть когда алфавит A содержит по крайней мере две буквы а1 и а2, можно обойтись и без формулы 0. Обозначаемый этой формулой тождественно ложный предикат может быть запи­сан, например, в виде формулы xf1 xf2.

Исключим из этого определения формулы ал­гебры конечных предикатов первое правило, вво­дящее формулы 0 и 1; кроме того, предположим, что k>2, и рассмотрим вопрос, можно ли в этих условиях еще более упростить определение фор­мулы при сохранении полноты алгебры. Оказыва­ется, что при принятых предположениях алгебра конечных предикатов несократима в том смысле, что любые дальнейшие сокращения в оставшихся правилах образования ее формул ведут к неполно­те данной алгебры. Действительно, исключим из числа формул одно из выражений: a^xj), вводимое вторым правилом. Тогда мы не сможем образовать формулу для обозначения предиката, обращающе­гося в 1 на всех тех наборах значений аргументов, у которых xj=ai, и в 0 — на всех остальных наборах. Если же мы исключим третье правило, тогда станет невозможным представление в виде формулы тож­дественно истинного предиката. Исключая чет­вертое правило, мы не сможем представить в виде формулы тождественно ложный предикат.

Таким образом, формулы 0 и 1 не обязательны для алгебры конечных предикатов. Их введение не расширяет выразительные возможности этой алге­бры, поскольку и без этих формул алгебра конеч­ных предикатов полна. Символы 0 и 1 включены в число формул лишь потому, что они обеспечивают дополнительные удобства при пользовании алге­брой конечных предикатов. Заметим, что формула 0 для полноты алгебр, у которых k=1, необходима. Алгебры этого типа не представляют серьезно­го интереса для теории интеллекта ввиду их вы­рожденности. Алфавит А таких алгебр состоит из одной буквы a1. Предикаты, охватываемые этими алгебрами, принимают значения лишь на одном наборе значений аргументов (a1, а1,..., а1), в кото­ром буква a1 встречается n раз. Алгеброй охватыва­ется всего два предиката 0 и 1.

6. Тождества алгебры конечных предикатов

Приступим к изучению свойств алгебры конеч­ных предикатов. Сначала рассмотрим ее основные тождества. Назовем тождественными формулы, выражающие один и тот же предикат. Факт тож­дественности формул будем обозначать знаком = . Для равенства значений предикатов будем исполь­зовать знак =. Пусть A, B, C произвольные фор­мулы алгебры конечных предикатов. Справедливы следующие тождества: законы коммутативности

АуВ=ВуА, (4)

AB=BA; (5)

законы ассоциативности

(AvB)vC=Av(BvC), (6)

(AB)C=A(BC); (7)

законы дистрибутивности

(AvB)C=ACvBC, (8)

ABvC=(AvC)(BvC); (9)

законы идемпотентности

AvA=A, (10)

AA=A; (11)

законы элиминации (поглощения)

AvAB=A, (12)

A(AvB)=A. (13)

Названия для приведенных тождеств заимство­ваны из алгебры логики, где рассматриваются со­впадающие с ними по форме законы. Однако в алгебре логики формулы обозначают не конечные предикаты, а булевы функции [7]. Справедливость тождеств легко проверяется перебором всевозмож­ных значений предикатов A, B, C. Например, до­кажем первый закон коммутативности: 0v0=0v0, 0v1 =1 v0, 1 v0=0v1, 1 v1 =1 v1. Справедлив, кроме того, ряд тождеств, в которых участвуют логиче­ские константы:

Av1=1, (14) A-0=0, (15) A-1=A, (16)

Av0=A. (17)

Пусть х произвольная буквенная переменная. Имеет место следующее тождество:

xa1 vxa2 v... vxak = 1. (18)

Действительно, какую бы букву алфавита А мы ни подставили вместо х в левую часть равенства

(18) , всегда один из дизъюнктивных членов, а вме­сте с ним и вся дизъюнкция, обращается в 1. Тож­дество (18) назовем законом истинности. Пусть а и b произвольные, но отличающиеся друг от друга (афЬ) буквы алфавита А. Имеют место следующие тождества:

xaxb=0. (19)

Действительно, какую бы букву мы ни подста­вили вместо х в левую часть равенства (19), всегда хотя бы один из конъюнктивных членов обратится в 0, а вместе с ним обратится в 0 и вся левая часть равенства (19). Тождество (19) назовем законом ложности. Закон истинности в некотором смысле можно рассматривать как аналог закона исклю­ченного третьего алгебры логики, а закон ложно­сти как аналог закона противоречия [1].

С абстрактной точки зрения введенная нами алгебра конечных предикатов есть дистрибутивная решетка с нулем и единицей [8]. А именно это есть множество всех n-местных k-ичных предика­тов с заданными на нем бинарными операциями дизъюнкции и конъюнкции, для которых выпол­няются аксиомы (4) — (17) дистрибутивной решет­ки с нулем и единицей. Роль нуля в алгебре конеч­ных предикатов выполняет тождественно ложный предикат 0, роль единицы — тождественно истин­ный предикат 1. Важно заметить, что в алгебре ко­нечных предикатов выполняются сверх этого еще и тождества (18) и (19). Как будет показано ниже, наличие этих тождеств позволяет ввести в алгебре конечных предикатов третью, унарную операцию — отрицание и рассматривать эту алгебру как буле­ву алгебру [7]. В силу наличия тождеств (18) и (19) алгебра конечных предикатов оказывается более богатой свойствами, чем булева алгебра, взятая в чистом виде.

Интересно выяснить вопрос: полна ли систе­ма тождеств, введенных нами в алгебре конечных предикатов. Иными словами, можно ли с помо­щью этих тождеств доказать тождественность лю­бых двух формул алгебры конечных предикатов, обозначающих один и тот же предикат? Несколько позже будет доказано, что система тождеств (4) —

(19) в указанном смысле полна. Эта система тож­деств разбивает все множество формул алгебры конечных предикатов на классы эквивалентности [7] таким образом, что каждому из этих классов может быть взаимно однозначно сопоставлен свой конечный предикат.

Не все из перечисленных тождеств, однако, необходимы для достижения полноты. Поэтому число тождеств в системе можно сократить. На­пример, справедливость тождеств (14) и (15) может быть доказана на основе остальных тождеств: Av1=1vA=1vA-1=1v1-A=1; A-0=0-A=0-(0vA)=0.

Из совокупности остальных тождеств выводит­ся второй закон дистрибутивности (9):

ABv C=ABv Cv CB=ABv Cv CAv CB=

=ABv CCv CAv CB=BAv CAvBCv CC=

=(BvO)AAv(BvC)C=

=A(Bv Cv C(Bv C)=(AvC)(Bv C).

Было бы интересно указать какую-нибудь не­сократимую полную систему тождеств алгебры ко­нечных предикатов, удобную в роли системы акси­ом для этой алгебры.

Алгебру конечных предикатов можно опреде­лить абстрактно как некую алгебраическую си­стему [8]. Рассмотрим множество М, в котором со­держатся, по крайней мере, два элемента 0 и 1 и к-п элементов ay (1<i<k, 1<j<n). Пусть на множестве М заданы две операции о и А, удовлетворяющие сле­дующим аксиомам:

aob=boa, aAb=bAa, (20)

(aob)oc=ao (boc), (aAb)Ac=aA(bAc), (21)

(aob)Ac=(aAc)o(bAc), (aAb)oc=(aoc)A(boc), (22)

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

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

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

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

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