Повна версія

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

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


<<   ЗМІСТ   >>

ПОВНОТА ДЛЯ ІНФОРМАЦІЙНИХ ГРАФІВ

Якщо нам дана ЗІП I = (X y V y p) і базове безліч Т = ( F , G ), то виникає питання, а чи можна побудувати інформаційний граф над базовим безліччю Т, вирішальний цю задачу /? Якщо для будь-якого запису у; ? V = {yi, ... , ук} Ху "р € F, то відповідь на це питання позитивний, і граф, зображений на малюнку 2.5, вирішує завдання /.

В даному розділі дається більш повну відповідь на це питання. Нехай нам дано тип S = (X y Y y p) y де X - безліч запитів, Y - безліч записів, р - відношення пошуку, заданий на X х У, і базове безліч Т = { F y G ).

Скажімо, що базове безліч Т повно для типу S = у Y y р ), якщо для будь-якої ЗІП I = ( Х у V y р) типу S існує ІГ U над базовим безліччю Т у вирішальний ЗІП /.

Справедливий наступний результат, що відноситься до проблеми повноти для ІГ.

Теорема 10. Нехай задані безлічі запитів X, записів Y, ставлення пошуку р на X х Y і базове безліч Т - (F y G), таке, що предикат тотожна 1 належить множині F. Тоді Т буде повним для типу S = у Y , р) тоді і тільки тоді, коли для будь-якого запису у 6 Y такий, що 0 (у у р) ф 0, функцію Ху, р { х ) можна представити формулою виду

де fij 6 FuG.

Доведення. Достатність.

Нехай нам дана довільна ЗІП I = (X y V y p) y де V = {yi> ••? • » УK } Q Y. За припущенням кожну з функцій

Xyi, p ( x ) (i = 1, А :) можна представити формулою де fuj Е FUG, I = l, k.

Без обмеження спільності можна вважати, що кожна кон'юнкція ДТЦ flij ( x ) містить предикат з F, причому цей предикат стоїть першим в кон'юнкції. В іншому випадку ми завжди можемо додати предикат тотожна 1.

ІГ, вирішальний ЗІП /, будемо будувати в такий спосіб.

Спочатку візьмемо до + 1 вершину і оголосимо одну з них коренем, а інші оголосимо листям і подумки перенумеруем, починаючи з 1 до А :. Потім для кожного I Е {1, Лг} виконаємо наступне.

Припишемо / -му листу (позначимо його од) запис у /.

Якщо 0 (yi, p) ф 0, то проведемо з кореня в лист сц щ орієнтованих ланцюгів, причому г-я ланцюг (г = 1, п /) буде складатися з ГПЦ ребер. Тепер для кожного г (г Е {1, п /}) виконаємо наступне. Якщо flij € F, то je ребро г-й ланцюга оголосимо предикатним і припишемо йому предикат fuj. Якщо fujG (тобто fuj = де д € С, а п 6 N), то вершину / ?, з якої виходить je ребро i-го ланцюга, оголосимо перемикальної пріпішем їй перемикач д ) j -му ребру г-й ланцюга пріпішем число рр, з вершини р випустимо ще г - 1 ребро, де г - потужність області значень перемикача д> і порівняти їм взаємно однозначно числа з безлічі {1, г} {п}.

Неважко бачити, що в цьому випадку

Оскільки ця умова виконується для всіх листя, то відповідно до теореми 9 побудований ІГ вирішує ЗІП I.

Необхідність .

Нехай Т повно для відносини р. Візьмемо довільну запис у Е Y таку, що 0 {у, р) ф 0. Нехай V - будь-яка бібліотека, що містить запис у .

Так як Т повно, то існує ІГ U , вирішальний ЗІП I =

( X , У, р). Розглянемо безліч Ьц (у) листя ІГ U , яким

відповідає запис у. Так як U вирішує завдання /, то відповідно до теореми 9

Оскільки кожна з функцій ip a (x) є функція провідності від кореня до листа а, а функція провідності за визначенням є диз'юнкція кон'юнкція деяких предикатів з F UG, то необхідність доведена, що і доводить теорему. ?

вправи

  • 2.25. Нехай S = } Х, =) - тип пошуку ідентичних об'єктів, базове безліч має вигляд Т - (0, С), де безліч перемикачів G задається співвідношенням (2.8). Чи буде повно базове безліч Т для типу 5?
  • 2.26. Завдання включає пошуку, описана у вправі 2.14,

ь

може бути задана типом Sbooi = пУВ П УУ) , де В п - п-мірний ь

логічний куб, У - відношення пошуку на В п х В п , яке визначається наступним співвідношенням

Наведіть приклад базового безлічі, повного для типу Sbooi • Наведіть приклад мінімального за потужністю базового безлічі, повного для типу Sbooi-

 
<<   ЗМІСТ   >>