Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

РОЗШИФРОВКА МОНОТОННИХ ФУНКЦІЙ

Відомо, що в загальному випадку для однозначного визначення функції алгебри логіки необхідно знати значення функції у всіх точках булевого куба. Якщо ж функція належить до певного класу, більш вузькому, ніж безліч всіх функцій алгебри логіки, то для однозначного визначення значень функцій у всіх точках Е п не обов'язково знати значення функцій у всіх точках Е п , а іноді досить знати на деякому підмножині Е п . Так для однозначного визначення симетричної функції досить знати її значення на п наборах, по одному з кожного шару куба.

Завдання розшифровки монотонної функції полягає в наступному. Заданий оператор Л /, що обчислює для довільної точки а Е Е п значення монотонної функції / (х) в цій точці а, тобто / (а). Питання: як мінімальним числом звернень до оператора А / повністю відновити таблицю значень монотонної функції / (я)?

Очевидно, що робота будь-якого алгоритму F, вирішального зазначене завдання, буде полягати в наступному. Алгоритм вибирає деяку точку а Е Е п і з допомогою оператора А / обчислює значення функції / (х) в точці а. Отримане значення функції в точці а заноситься в таблицю значень досліджуваної функції. За монотонності визначаються значення / (х) в інших точках Е п . Потім по деякому правилу вибирається інша точка Е п , і процес повторюється до тих пір, поки таблиця значень не опиниться заповненої повністю.

Паре - алгоритм F і монотонна функція / - зіставляємо число v? (F, /), яка дорівнює кількості звернень до оператора Л / в процесі відновлення таблиці значень функції / с допомогою алгоритму F.

позначимо

де М п - безліч монотонних функцій п змінних;

де мінімум береться по всім алгоритмам, вирішальним завдання розшифровки.

Нехай N - деякий клас булевих функцій п змінних і / Е N. Безліч G (f y N) точок їх Е " називаються що дозволяє для пари (/, N), якщо з того, що функція g Е N, і на безлічі G ( f, N) значення функцій / і g збігаються, слід, що / = д.

Вирішальне безліч називається тупиковим що дозволяє безліччю для пари (/, JV), якщо ніяке його власне підмножина не є вирішальним для пари (/, N).

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

Теорема 7. Має місце

Доведення. Нижня оцінка [27 |. З єдиності тупикового дозволяє безлічі монотонної функції / (х 1, ..., х п ) слід, що необхідно відновити її значення в усіх точках (7 (/, М п ). Розглянемо функцію

Безліч її верхній нулів є [п / 2] -й шар куба Е п , а нижніх одиниць - ([п / 2] 4 1) -й шар. Звідки відразу випливає, що

Верхня оцінка [6). Як ми вже відзначали, для довільної монотонної функції / (xi, ..., х п ) з властивості б) леми 4 випливає, що якщо значення функції /(xi,...,x n ) відомо в усіх вершинах ланцюгів довжини п - 2 р - 1, то в кожному ланцюзі довжини п- 2р + 1 існує найбільше дві (сусідні) вершини, де значення / (хi, ..., х п ) залишаються невизначеними. Розглянемо два випадки.

1) п = 2 к. Тоді по лемі 4 є С * - З * -1 ланцюгів довжини 1, і С * -1 ланцюгів довжини більше 1. Для першої групи ланцюгів нам треба одне звернення до оператора А / , а для другої - два. отже

2) п = 4 1. Тоді все З ? ланцюгів мають довжину понад 1, і для кожної з них потрібно два звернення до оператора А /. отже

?

Теорема доведена.

вправи

  • 1.28. Для даної навчальної вибірки, заданої парою таблиць (Т Ь Т 2 ) знайти всі тупикові тести і визначити, до якого класу буде віднесений вектор (1010), якщо скористатися описаними вище тестовими алгоритмами, а саме
  • а) алгоритмом А [14],
  • б) алгоритмом Л 2 [29],
  • в) алгоритмом Аз (47, 48],
  • г) алгоритмом голосування по тестах, де в якості опорного взято безліч тупикових тестів,

за умови, що пара таблиць (Т, Т 2 ) має вигляд

  • 1.29. Перерахувати все монотонні функції, залежні (не обов'язково істотно) від змінних: ri, х 2 .
  • 1.30. Знайти число тр (3) монотонних булевих функцій від 3-х змінних.
  • 1.31. Перерахувати, описане в лемі Апсель покриття булевого куба Е п попарно не перетинаються ланцюгами за умови, що а) n = 2,
  • б) n = 3,
  • в) n = 4.

:

 
<<   ЗМІСТ   >>