Автор неизвестен - Информация, язык, интеллект - страница 43

Страницы:
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  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122 

а єА

ма всех основных законов дизъюнктивной ал­гебры одноместных предикатов полна при лю­бом А. Основываясь на этих законах можно доказать, к примеру, что {a,a,b} = {a,b}, {a,b} = {b,a}, {a,b} и {с} = {a, с} и {b,c}, 0u{a,b} = {a,b}. Чтобы сде­лать это, составляем соответствующие доказывае­мым соотношениям равенства алгебры одномест­ных предикатов: xa v xa v xb = xa v xb, xa v xb = xb v xa, (xa v xb) v xc = (xa v xc) v (xb v xc) ,

0 v (xa v xb) = xa v xb

и устанавливаем, что эти равенства являются ее тождествами.

1. Дизъюнктивно-конъюнктивная алгебра

Консервативно расширим дизъюнктивную ал­гебру одноместных предикатов, дополнительно введя в ее базис операцию конъюнкции. Благода­ря этому, получаем избыток в базисе вновь сфор­мированной дизъюнктивно-конъюнктивной ал­гебры одноместных предикатов. Избавимся от этого избытка за счет консервативного сужения базиса элементов полученной алгебры. Сдела­ем это вначале на конкретном примере. Берем следующий базис элементов исходной алгебры: 0, x1, x2, x3, x4, x5, x6, что соответствует носителю алгебры M = {1, 2, 3, 4, 5, 6} (x є{1, 2, 3, 4, 5, 6}). Ему соответствует система множеств: 0, {1}, {2},

{3}, {4}, {5}, {6}.

Таблица 1

Располагаем предметы в прямоугольной таб­лице с размерами 3 х 2 и формируем из них новые множества в виде взаимно перпендикулярных по­лос (табл. 1). Эти полосы снабжаем номерами 1, 2, 3, 4, 5. Введенным множествам соответствуют пре­дикаты:Pj (x) = x1 v x4, Р2 (x) = x2 v x5, Р3 (x) = x3 v x6, Р4 (x) = x1 v x2 v x3, Р5 (x) = x4 v x5 v x6.

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

0 = Р1 ((x), x1 = Рі (x^4(x), x2 = P2 (x )P4 (x), x3 = Р3 (x 4 (x), x4 = Рі ((x), x5 = Р2 ((x), x6 = Р3 ((x).

Поэтому базис элементов новой алгебры полон. Он также несократим.

Расположим теперь те же предметы в верши­нах некоторого гиперкуба наименьшей подходя­щей размерности. В нашем примере размерность гиперкуба следует взять равной трем, то есть надо воспользоваться кубом. У куба 8 вершин, это не меньше, чем необходимо для размещения шести предметов, у квадрата же всего 4 вершины, что не­достаточно. Располагаем в вершинах куба предме­ты 1, 2, 3, 4, 5, 6 множества А исходной дизъюн­ктивной алгебры предикатов. Формируем из них на гранях куба шесть новых множеств, снабжая их номерами 1, 2, 3, 4, 5, 6 (рис. 1). Введенным мно­жествам соответствуют предикаты:

Р1 (x) = x1 v x3 v x5, Р2 (x) = x2 v x x v x6,

Р3 (x) = x1 v x2 v x5 v x6, Р4 (x) = x3 v x4,

Р5 (x) = x1 v x2 v x3 v x4, Р6 (x) = x5 v x6.

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

0 = Р (x^ (x), x1 = Р1 (x^ МР5 (x),

x2 = Р2 (x^ ( (x ), x 3 = P(x Р (x^ (x ), x x = Р2 (x^ (x^ (x ), x 5 = Р1 (x^ (x^ ( x),

x6 = Р2 (x Р (x^ (x).

Поэтому базис элементов новой алгебры полон. Он также несократим.

2. Минимизация базиса элементов

Отыщем размерность n гиперкуба, которая обеспечивает наименьшее число базисных элемен­тов в дизъюнктивно-конъюнктивной алгебре од­номестных предикатов. Пусть \А\ = k . Тогда размер h стороны гиперкуба размерности n равняется

h = фс . (3)

Число h совпадает с числом предметов, распола­гаемых на одной грани гиперкуба. Число N базис­ных элементов в новой алгебре равно

N = nh. (4)

Иначе говоря,

1

N = nnfk = nkn .

(5)

0

Отыскиваем n , исходя из условия: dN dn

Производим дифференцирование:

 

dN = d(nkn) = dn^ + rd (kn) = dn      dn      dn dn

Страницы:
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  78  79  80  81  82  83  84  85  86  87  88  89  90  91  92  93  94  95  96  97  98  99  100  101  102  103  104  105  106  107  108  109  110  111  112  113  114  115  116  117  118  119  120  121  122 


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

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

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

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

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

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