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

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

1      1 d(±)

= 1 • kn + nkn Ink—— = dn

1               1        1     1 k

--kn (1 + n In k(- A2)) = kn (1 - —).

n2 n5

 

 

 

2

 

 

3


 

 

61

Поскольку kn ф 0 , то согласно условию (5), имеем

1 - М = 0, n

откуда

n = In k . (6)

Размер h* стороны гиперкуба размерности n равен:

1

h* = </k =ln    = kln k .

Учитывая, что

,        ±- 1 ln h = 1n(k1n k) = ln k = 1, ln k

окончательно получаем:

h* = є = 2,7. (7)

Наименьшее число Nmin базисных элементов в новой алгебре равно:

 

 

Окончательно:

Nmin = Є lnk . (8)

Результаты подсчетов по формулам (6) и (8) приве­дены в табл. 2.

Таблица 2

 

k

10

102

105

1010

*

n

3

5

12

23

N

min

7

13

31

62

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

3. Булева алгебра

Консервативно расширим дизъюнктивно-ко­нъюнктивную алгебру одноместных предикатов, дополнительно введя в ее базис операцию отрица­ния. Благодаря этому, мы получаем булеву алгебру одноместных предикатов с избыточным базисом. Избавляемся от этого избытка за счет консерва­тивного сужения базиса элементов в этой алгебре. Выше мы нашли, что h* = 2,7 . Поэтому нам доста­точно произвести сужение базиса элементов лишь в двух случаях, когда h = 3 и h = 2. Сначала сделаем это на конкретном примере. Пусть h = 3 . Прини­маем, для примера, k = 27. Согласно (3) имеем

h = Vk,

откуда

lg h = 11g k , n

следовательно

 

3 lgh

В нашем примере получаем при h = 3 следую­щую размерность n3 гиперкуба:

lg27 1,4314

3    lg3 0,4771

Согласно равенству (4) число N3ДК базисн^гх эле­ментов дизъюнктивно-конъюнктивной алгебры при h = 3 равно:

^ДК = n3h = 3 3 = 9 .

Согласно закону отрицания, в булевой алгебре число N3E базисных элементов можно уменьшить на треть, следовательно N3 = 6 .

Пусть теперь h = 2 . По-прежнему, для примера, принимаем k = 27 . Размерность n2 гиперкуба при h = 2 согласно (9) равна:

= lg27 = -М314 = 4,7. 2    lg2 0,3010

Итак n2 = 5 . Число N2ДК базисных элементов ди­зъюнктивно-конъюнктивной алгебры при h = 2 согласно (4) равно:

N2 ДК = n2h = 5 2 = 10.

Согласно закону отрицания, в булевой алгебре число N2 можно уменьшить наполовину, следо­вательно:

= 5.

Таким образом,

N2* < N3* (5<6),

а это означает, что при h = 2 базис булевой алгебры более экономный, чем при h = 3 .

От примера перейдем к общему рассмотрению. Можем записать:

k = 2^ = 3n3.

Следовательно:

n2lg2 = n3lg3 .

Итак:

= lg2 = 0,3010 = 063

n2   lg3   0,4771    , .

Вместе с тем,

N3 ДК = n3 3; N2 ДК = n2 2;

N3* = 2 N3^ = 2 n3 3 = 2n3 ;

3     3    3      3   3 3

N2* = 1 N2ДК = 1 n2 2 =Окончательно:

N^ = — = 2 ^ = 2 • 0,63 = 1,26. (10)

 

Итак, для любого числа k булева алгебра одно­местных предикатов при h = 3 имеет базисных эле­ментов на 26% больше, чем при h = 2. Минималь­ное число базисных элементов в булевой алгебре одноместных предикатов равно

 

Из равенства

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

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

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

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

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