Тема 12. ПРОДУКЦІЙНІ СИСТЕМИ ПСШІ

ПЕРЕЛІК ЗНАНЬ ТА НАВИЧОК

Після опанування теми студент має знати:

• відомі формальні моделі систем продукцій (СП);

• формальні реляційні моделі обчислень СП;

• визначення продукційної системи, продукції, факту, ситуації, кон’юнкції фактів, сфери застосування продукції;

• ядро продукції та склад;

• архітектуру програмних систем продукцій ПСП;

• склад БЗ та основні частини;

• операції над БЗ;

• динамічне управління даними в процесі висновку; має вміти:

• пояснити склад ядра продукції та його частин;

• записати в узагальненій формі правило-продукцію;

• використати при складанні БЗ правила;

• побудувати цикл «розпізнавання — дія» (пошук за зразком);

• користуватися системою висновку за зразком;

• керувати системою продукцій (механізмом виведення);

• застосувати типи виконання пошуку систем продукцій.

ЗМІСТ ПИТАНЬ З ТЕМИ

12.1. Формальні моделі систем продукцій

Серед найвідоміших формальних моделей СП слід назвати реляційну модель А. С. Клещова, К-системи В. Е. Кузнецова, реляційні моделі S.Vere і модель керованої СП M. Georgeff. Яхно Т. М. була запропонована модель алгебри СП, яка узагальнює перелічені вище моделі й дозволяє описувати поведінку СП в найзагальнішому вигляді.

Системи продукцій почали розвиватися із середини 70-х років з появою прикладних програмних систем спеціальної архі-

Реляційна модель обчислень, запропонована А. С. Клещовим, використовує як мову опису числення предикатів першого порядку. Елементами множини станів є конституанти, які є атомарними формулами вигляду: P(c

1 ,…, c k ), де Р

— деякий k-арний предикативний символ, а c i , с

2 , ..., с k

— константи. Множина переходів між елементами множини станів задається за допомогою теорії Т в мові числення предикатів першого порядку L, кожна пропозиція якої містить у точності один знак імплікації.

Для кожної множини конституант S визначимо пов’язану з ним структуру M s мови L за допомогою таких умов:

• усі M s мають один і той самий рахунковий універсум;

• у M s істинні ті і тільки ті конституанти, які входять в S.

Через M ? позначатимемо структуру, відповідну порожній множині конституант. Нехай Т — множина пропозицій мови L вигляду ф ? ?, де ф і ?

— кон’юнкції конституант, S

0 — кінцева множина конституант така, що,

0 s M не є моделлю Т. Тоді процес обчислень за програмою Т над початковими даними S

0 визначається таким чином.

Для кожного ? ? Т позначимо: ? ? , ? ?

— множина конституант, що входять в умову і в наслідок а відповідно. Нехай на i-му кроці обчислено множину конституант S i таких, що S

0 ? S i . Якщо

деяке ? ? Т помилкове в структурі i s M, то ? ??= ii SS

1 . деяке ? ? Т помилкове в структурі i s M, то ? ??= ii SS

1 .

Вибір на i-ому кроці пропозицій ? ? Т, помилкових у структурі i s M відповідає різному порядку виконання дій при обчисленнях.

Процес обчислень закінчується, якщо для деякого t структура t s M — модель Т; S t називатимемо результатом обчислення.

Аналогічно визначається висновок у разі, коли в правилах мови використовуються змінні та квантори, тобто правила мають вигляд ??

1 , …, ? n (? ? ? u

1 , …, u m ?).

А. С. Клещовим досліджено коректність обчислень у реляційній моделі та доведено, що результат обчислень не залежить від порядку застосування продукцій. Ці дослідження послужили теоретичним підґрунтям для технологічного комплексу СИНАП.

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

—часткове» над правилами. У К-системах введено відношення «загальне

—часткове» над продукці

ями таким чином: якщо ? = {x i /t i } — підстановка, а р, q — продукції, і p = q?, де q? — це продукція, що одержується з q заміною всіх входжень змінних x i на t i те продукція р є окремим випадком продукції q, а q — узагальнення продукції р.

У К-системах уведено кілька типів узагальнень: підстановлювальне, категоріальний синтез, відкидання посилок, досліджені властивості цих узагальнень. На підставі цих понять вводиться поняття виключення з правила.

Правило р є виключенням з q (а q — загальне правило стосовно до р), якщо область визначення правила р є строго окремим випадком області визначення правила q. У К-системах реалізована (вбудована) така стратегія вибору правил: виключення завжди мають більший пріоритет, ніж загальні правила. Дана стратегія близька до стратегії, реалізованої в мові РЕФАЛ.

Запропонований підхід виправданий з погляду здорового глузду і був успішно застосований до завдань, пов’язаних із синтаксичним аналізом природних мов.

Формальна модель СП, запропонована S. Vere, називається кції, і p = q?, де q? — це продукція, що одержується з q заміною всіх входжень змінних x i на t i те продукція р є окремим випадком продукції q, а q — узагальнення продукції р.

У К-системах уведено кілька типів узагальнень: підстановлювальне, категоріальний синтез, відкидання посилок, досліджені властивості цих узагальнень. На підставі цих понять вводиться поняття виключення з правила.

Правило р є виключенням з q (а q — загальне правило стосовно до р), якщо область визначення правила р є строго окремим випадком області визначення правила q. У К-системах реалізована (вбудована) така стратегія вибору правил: виключення завжди мають більший пріоритет, ніж загальні правила. Дана стратегія близька до стратегії, реалізованої в мові РЕФАЛ.

Запропонований підхід виправданий з погляду здорового глузду і був успішно застосований до завдань, пов’язаних із синтаксичним аналізом природних мов.

Формальна модель СП, запропонована S. Vere, називається ями таким чином: якщо ? = {x i /t i } — підстановка, а р, q — продукції, і p = q?, де q? — це продукція, що одержується з q заміною всіх входжень змінних x i на t i те продукція р є окремим випадком продукції q, а q — узагальнення продукції р.

У К-системах уведено кілька типів узагальнень: підстановлювальне, категоріальний синтез, відкидання посилок, досліджені властивості цих узагальнень. На підставі цих понять вводиться поняття виключення з правила.

Правило р є виключенням з q (а q — загальне правило стосовно до р), якщо область визначення правила р є строго окремим випадком області визначення правила q. У К-системах реалізована (вбудована) така стратегія вибору правил: виключення завжди мають більший пріоритет, ніж загальні правила. Дана стратегія близька до стратегії, реалізованої в мові РЕФАЛ.

Запропонований підхід виправданий з погляду здорового глузду і був успішно застосований до завдань, пов’язаних із синтаксичним аналізом природних мов.

Формальна модель СП, запропонована S. Vere, називається реляційною СП і визначається як п’ятірка PLVC,,,,

0 ?.

Тут С — множина констант (що позначаються рядковими буквами); V — кінцева множина символів змінних, що набувають значення в області констант (позначаються заголовними буквами); L — множина літералів вигляду (е

1 e

2 ... е n ) або ¬(e

1 e

2 . . . е n ), n ? 1, е i ? С ? V; ?

— початкова ситуація, що визначається як кон’юнкція літералів;

0

Р — кінцева множина правил вигляду ???µ, де ? — умова застосовності (антецедент), ? — наслідок (консеквент), µ — аспект (грань), ?, ?, µ — кон’юнкції літералів. Для того щоб відокремити аспект від антецедента, його підкреслюватимемо в правилах.

Іншою цікавою формальною моделлю СП є К-системи, запропоновані В. Е. Кузнецовим. Як уже зазначалося, одна з основних проблем щодо виведення висновку в СП — це вибір відповідних правил для застосування. Помічено, що база продукцій, представлена у вигляді сотень локальних правил, не описує в явному вигляді відношення «загальне

Продукції призначені для опису всіляких перетворень початзастосовуватися до ситуації кількома способами, оскільки різні підстановки можуть задовольняти умові ?.

кової ситуації до деякої ситуації ?. Продукція ?µ = ? застосовна до ситуації ? тоді і тільки тоді, коли ?? ? ?, де ? — відповідна підстановка вигляду: {t

1 /?

1 , …, t n /? n }, де t i — терми, ? i

— змінні.

Наприклад, нехай ? = (асе)(bес). Продукція ()()() XbbXcaac?

Наприклад, нехай ? = (асе)(bес). Продукція XbbXcaac? застосовна до цієї ситуації, оскільки (асе) = (acX){e/X},(ace) ? ?.

Зауважимо, що в загальному випадку продукція ?=µ? може кової ситуації до деякої ситуації ?. Продукція ?µ = ? застосовна до ситуації ? тоді і тільки тоді, коли ?? ? ?, де ? — відповідна підстановка вигляду: {t

1 /?

1 , …, t n /? n }, де t i — терми, ? i

— змінні.

Наприклад, нехай ? = (асе)(bес). Продукція ()()() XbbXcaac? застосовна до цієї ситуації, оскільки (асе) = (acX){e/X},(ace) ? ?.

Зауважимо, що в загальному випадку продукція ?=µ? може

Надалі кон’юнкція літералів розглядається як множина. Визначимо над ними такі операції, як об’єднання (?), перетин (?), підмножина (?) і доповнення (—). ретворить ? на

Якщо продукція ?=µ?=p застосовна до ситуації ?, то р пе

Якщо продукція ?=µ?=p застосовна до ситуації ?, то р пе???µ??????=???µ??????=? . () ???µ??????=???µ??????=? ? .

Вважатимемо, що ? ? безпосередньо виводиться з ? за продукцією р. (caX){e/X} = (cae)(bec)

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

Усі вказані моделі описуються як окремі випадки запропонованої моделі алгебри.

Дослідження формальних моделей супроводжувалося проведенням серії експериментів щодо створення прикладних систем продукцій для різних ПРГ.

Продукція — це пара «умова-дія», «ситуація-дія», «причинанаслідок», «умова-висновок» і т. ін., яка визначає одну порцію знань, необхідних для вирішення завдання. Умовна частина правила — це зразок (шаблон), який визначає, коли це правило може

Продукційним правилом називають вираз вигляду: (i); Q; P; A

1 , A

2 , ..., A n > B

1 , B

2 , ..., B k; N, де i

— ім’я продукції, яким може виступати деяка лексема, що відбиває суть даної продукції або її порядковий номер; Q

— елемент, що характеризує сферу застосування продукції A

1 , A

2 , ..., A n > B

1 , B

2 , ..., B k

— ядро продукції, «>» — знак секвенції, A i — i-та передумова (умова) правила, Bj

— j-ий висновок(наслідок, дія) правила, Р — умова застосовності ядра продукції, N

— постумови продукції.

Продукційні правила читаються в такий спосіб: якщо передумови A

1 та A

2 та ... A n є правильними, то виконати дії B

1 та B

2 та ... B k .

Продукційна система — це модель обчислень, що забезпечує управління процесом розв’язання задачі за зразком і складається з набору продукційних правил, робочої пам’яті і циклу управління «розпізнавання-дія».

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

Фактом є впорядкований список вигляду: ( f A ,e

1 ,...,e n ), де f ? F, f : s

1 ? s

2 ? ... ? s n-1 ? s n , e i ? TR, mun(e i ) = s i , i = 1...n.

У цих позначеннях ситуацією назвемо кінцеву кон’юнкцію фактів. Надалі через D позначатимемо множина усіляких ситуацій. Зазначимо, що поняття ситуації відповідає поняттю поточного стану бази даних або робочої пам’яті.

Якщо всі е i , (i = 1... n) у факті ? константи, то факт назвемотермінальним. Оскільки серед фактів ситуації можуть бути нетермінальні, то, в загальному випадку, їй відповідає неєдиний набір множини носіїв системи, алгебри.

Для простоти викладу надалі обмежимо терми у визначенні факту константами і змінними, що не порушує спільності викладу, оскільки терми із функціональними символами можуть бути записані в ситуації без них збільшенням числа змінних. Наприклад, відношення х + у ? 2 запишеться у вигляді (+, х, у, z) ? ? (?, z, 2,1).

Змінні позначатимемо буквами x, у, z. Тоді рівняння х + у = 5 запишемо у вигляді такого факту: (+, x, у, 5), а система співвідношень х + y = 5, у ? 0, х ? 3 у вигляді ситуації: d

0 = (+, x, у, 5) ? ? (?, у, 0,1) ? (?, 3, x, 1).

бути застосовано для вирішення якого-небудь етапу завдання. Частина дії визначає відповідний крок у розв’язанні задачі.

Визначена таким чином ситуація є множиною кон’юнктивно зв’язаних фактів, і тому надалі поводитимемося з нею як з множиною, використовуючи операції об’єднання, перетину, різниці і відношення включення ?.

Продукцією назвемо пару < q, r >, у якій q — ситуація, що називається умовою застосовності продукції, r

— програма, r? R, що називається дією, причому q і r пов’язані співвідношенням var(q) ? out(r).

Системою продукцій назвемо кінцеву множину пар Рr = = {< q, r >}. Стверджуватимемо, що d

2 безпосередньо виводиться з d

1 за допомогою продукції pr = <q,r>,

21 dd pr ???, якщо знайдеться така підстановка, ?, що d

1 ? q? а

Системою продукцій назвемо кінцеву множину пар Рr = = {< q, r >}. Стверджуватимемо, що d

2 безпосередньо виводиться з d

1 за допомогою продукції pr = <q,r>,

21 dd pr ???, якщо знайдеться така підстановка, ?, що d

1 ? q? а = {< q, r >}. Стверджуватимемо, що d

2 безпосередньо виводиться з d

1 за допомогою продукції pr = <q,r>,

21 dd pr ???, якщо знайдеться така підстановка, ?, що d

1 ? q? а з d

1 за допомогою продукції pr = <q,r>,

21 dd pr ???, якщо знайдеться така підстановка, ?, що d

1 ? q? а d

2 = r(q) (d

1 q).

Продукцією назвемо пару < q, r >, у якій q — ситуація, що називається умовою застосовності продукції, r

— програма, r? R, що називається дією, причому q і r пов’язані співвідношенням var(q) ? out(r).

Системою продукцій назвемо кінцеву множину пар Рr = = {< q, r >}. Стверджуватимемо, що d

2 безпосередньо виводиться з d

1 за допомогою продукції pr = <q,r>,

21 dd pr ???, якщо знайдеться така підстановка, ?, що d

1 ? q? а d

2 = r(q?) ? (d

1 q?).

Якщо знайдеться послідовність продукцій

рr

1 , рr

2 , ..., pr k , pr i Pr, i = 1...k, k 0, і станів бази d

0 , d

1 , ..., d k таких, що kk dprprdprd ? ?? ...

2110 то говоримо, що d k виводиться з d

0 , і *

0 dd???

1 ,...,

0

1 dd k prpr ????? або, а pr

1 , рr

2 , ..., pr k назвемо послідовністю застосовних d

0 продукцій.

Якщо k dd??? *

0 и ?pr () k pr k dddd= ? => ? ???, то d k назвемо результативною ситуацією d

0 .

Однозначність обчислень над диз’юнктивною БЗ.

Узагальнимо введені поняття на ситуацію з диз’юнктивними фактами. Нехай d k

— множина кон’юнктивно зв’язаних фактів. Тоді диз’юнктивним станом бази назвемо будь-яку кінцеву мно{} mk k dd ...1= =.

Основні поняття збігаються з уведеними вище. Визначимо висновок по продукції в диз’юнктивній базі. {} mk k dd ...1= = і продукція pr = . pr

1 ,…, pr k

Якщо k dd??? *

0 и ?pr k pr k dddd= ? => ? ???, то d k назвемо результативною ситуацією d

0 .

Однозначність обчислень над диз’юнктивною БЗ.

Узагальнимо введені поняття на ситуацію з диз’юнктивними фактами. Нехай d k

— множина кон’юнктивно зв’язаних фактів. Тоді диз’юнктивним станом бази назвемо будь-яку кінцеву мно{} mk k dd ...1= =.

Основні поняття збігаються з уведеними вище. Визначимо висновок по продукції в диз’юнктивній базі. {} mk k dd ...1= = і продукція pr = . жину D d2?, {} mk k dd ...1= =.

Основні поняття збігаються з уведеними вище. Визначимо висновок по продукції в диз’юнктивній базі. {} mk k dd ...1= = і продукція pr = . жину D d2?, mk k dd ...1= =.

Основні поняття збігаються з уведеними вище. Визначимо висновок по продукції в диз’юнктивній базі. {} mk k dd ...1= = і продукція pr = r>.

Нехай задано: {} mk k dd ...1= = і продукція pr = r>.

Нехай задано: mk k dd ...1= = і продукція pr = . {}

1...1 / += = mk k dd по продукції pr, якщо знайдуться такі ? (підстановка), k(1 ? k ? m), що

1...1 / += = mk k dd по продукції pr, якщо знайдуться такі ? (підстановка), k(1 ? k ? m), що рr

1 , рr

2 , ..., pr k , pr i ? Pr, i = 1...k, k ? 0, і станів бази d

0 , d

1 , ..., d k таких, що kk dprprdprd ? ?? ...

2110 то говоримо, що d k виводиться з d

0 , і пишемо

1 *

0 dd???

1 ,...,

0

1 dd k prpr ????? або, а pr

1 , рr

2 , ..., pr k назвемо послідовністю застосовних d

0 продукцій.

Якщо k dd??? *

0 и ?pr () k pr k dddd= ? => ? ???, то d k назвемо результативною ситуацією d

0 .

Однозначність обчислень над диз’юнктивною БЗ.

Узагальнимо введені поняття на ситуацію з диз’юнктивними фактами. Нехай d k

— множина кон’юнктивно зв’язаних фактів. Тоді диз’юнктивним станом бази назвемо будь-яку кінцеву множину D d2?, {} mk k dd ...1= =.

Основні поняття збігаються з уведеними вище. Визначимо висновок по продукції в диз’юнктивній базі.

Нехай задано: {} mk k dd ...1= = і продукція pr = r>.

Вважаємо, що з d диз’юнктивний стан БЗ виводиться {}

1...1 / += = mk k dd по продукції pr, якщо знайдуться такі ? (підстановка), k(1 ? k ? m), що pr

1 ,…, pr k

k +1k dq??, m+1 = () (k ?). k dq??, d m+1 = r?(q?) (d k ?q?).

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

Диз’юнктивний висновок є повним перебором альтернативних варіантів, основний недолік якого — комбінаторне зростаннядиз’юнктів. Проте висновок з відношенням неспільності, незважаючи на всі засоби оптимізації, заснований на алгоритмі повного перебору. Тому у формальній моделі необхідно розробити засоби для представлення евристичних функцій скорочення перебору та управління висновком.

Сфера застосування

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

Ядро продукції складається з двох частин:

• антецедент (передумова, умови правила) — являє собою комбінацію передумов правила (припущень про наявність деяких властивостей, що набувають значення істина або хибність з визначеним ступенем вірогідності), з’єднаних логічними зв’язуваннями (ТА, АБО і т. д.), призначену для розпізнання ситуації, коли це правило має спрацювати: правило спрацьовує, якщо факти з робочої пам’яті задовольняють умовам передумови правила, після цього правило вважається відпрацьованим. Передумови зазвичай бувають подані у формі вектора об’єкт

— атрибут — значення. Упевненість у вірогідності передумови залежить від того, наскільки достовірною є оцінка передумов;

• консеквент (висновок, наслідки правила) — містить опис дій, які мають бути виконані над робочою пам’яттю у разі виконання відповідних передумов. Іноді використовується й інша термінологія, відповідно до якої передумови називаються лівою частиною правила, а дії — правою.

Ядра продукцій можна класифікувати за різними ознаками. Перш за все всі ядра поділяють на два великі типи: детерміновані та недетерміновані. Інтерпретація ядра в цьому випадку може, наприклад, виглядати так: якщо А, то можливо В. У детермінованих ядрах при актуалізації ядра і при здійснимості А права частина ядра виконується обов’язково; у недетермінованих ядрах В може виконуватися і не виконуватися.

Отже, секвенція ? у детермінованих ядрах реалізується за необхідності, а в недетермінованих — за можливістю.

Можливість може визначатися деякими оцінками реалізації ядра. Наприклад, якщо задана вірогідність виконання В при актуалізації А, то продукція може бути такою: якщо А, то з вірогідні-

Детерміновані продукції можуть бути однозначними і альтернативними. У другому випадку в правій частині ядра вказуютьсяальтернативні можливості вибору, які оцінюються спеціальними вагами вибору. Як такі ваги можуть використовуватися імовірнісні оцінки, лінгвістичні, експертні оцінки і т. п. (наприклад, якщо А, то найчастіше треба робити В

1 , рідше В

2 ).

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

У системі, що базується на правилах, кількість продукційних правил визначає розмір БЗ. Деякі найскладніші системи мають БЗ з більш ніж 5000 продукційних правил. Тому при складанні БЗ необхідно використовувати такі правила:

• Використовувати мінімально достатню множину умов при визначенні продукційного правила.

• Уникати продукційних правил, що суперечать.

• Конструювати правила, спираючись на структуру, властиву ПРГ.

Робоча пам’ять містить опис поточного стану ПРГ в процесі міркувань. Цей опис є зразком, який зіставляється з умовною частиною продукції з метою вибору відповідних дій при розв’язуванні задачі. Якщо умова деякого правила відповідає вмісту робочої пам’яті, то може виконуватися дія, пов’язана з цією умовою. Дії продукційних правил призначені для зміни змісту робочої пам’яті.

Цикл «розпізнавання-дія» (пошук за зразком). Поточний стан модельованої ПРГ відображається в робочій пам’яті у вигляді сукупності образів, кожний з яких представляється за допомогою фактів. Потім вибираються ті правила, для яких зразки, що представляються передумовами правил, зіставлені з образами в робочій пам’яті. Якщо таких правил більше за одне, то вони утворюють конфліктну множину, а продукції, що містяться в конфліктній множині, називаються допустимими. Відповідно до вибраного механізму вирішення конфлікту вибирається і активізується одна з продукцій конфліктної множини. Активація правила означає виконання його дії. При цьому змінюється зміст робочої пам’яті. Після того, як вибране правило спрацювало, цикл управління повторюється для модифікованої робочої пам’яті. Процес закінчується, якщо вміст робочої пам’яті не відповідає жодним умовам.

стю р реалізувати В. Можливі інші способи задання оцінки реалізації ядра.

Розглянемо формалізм нормальних алгоритмів Маркова, в якому правила висновку реалізуються на основі операторів підстановки.

У системах нормальних алгоритмів Маркова виведеність трактується в конструктивному сенсі — як отримання з початкового слова (зразка) інших слів. Це так званий висновок за зразком (що знайшов застосування, наприклад, у системах, що використовують фрейми і семантичні мережі). Канонічна продукційна система Поста також є системою висновку за зразком.

Нехай x

1 , x

2 , ..., x m — попарно різні змінні, які мають області визначення D

1 , D

2 , ..., D m відповідно. Якщо змінна х зв’язана деяким значенням

1 j d з D j , то будемо замість х, писати

1 j d. Зразок ?

— це конструкція , = ? ? ? ? ? ? ? ? m21 m21 y ..., ,y ,y x...,,x,x ? де кожному x i зіставлений терм у i , що є або самою змінною х i , (якщо вона не зв’язана), або, якщо

1 j d= i x. якщо

1 j d= i x.

Наприклад ? ? ? ? ? ? ? ? = bax xxx ?

1

321

1 , а ? D

2 , b ? D

3 .

Нехай задано два зразки ?

1 і ?

2 . Говоримо, що з ?

1 і ?

2 виво, ?? , якщо виконані такі умо

— це конструкція , = ? ? ? ? ? ? ? ? m21 m21 y ..., ,y ,y x...,,x,x ? де кожному x i зіставлений терм у i , що є або самою змінною х i , (якщо вона не зв’язана), або, якщо

1 j d= i x.

Наприклад ? ? ? ? ? ? ? ? = bax xxx ?

1

321

1 , а ? D

2 , b ? D

3 .

Нехай задано два зразки ?

1 і ?

2 . Говоримо, що з ?

1 і ?

2 виводиться зразок ?

3 , і записуємо це:

21 , ?? , якщо виконані такі умо

3 ? ви:

1) ?

1 і ?

2 містятьзагальні змінні;

2) нехай x i

— одна (будь-яка) із загальних змінних, тоді x i і в

1 , і в

2 або зв’язана одним і тим самим значенням, або як мінімум одна з них не зв’язана зовсім;

3) ?

3 утворюється шляхом включення (без дублювання) усіх змінних з ?

1 і ?

2 . При цьому, якщо загальна змінна x i зв’язана,

скажімо в

1 , значенням i = , а в

2 вільна (не зв’язана), то в

3iматиме значення а. У цьому випадку говорять, що змінні в

3 успадковують значення відповідних змінних в