7Л. Логічні побудови та логічні моделі

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

Як уже зазначалося, логічне виведення за дедукцією (від загальних пра­вил до часткових наслідків) є одним з основних механізмів мислення, до того ж цілком бездоганним з погляду логіки. Саме цей вид логічного виве­дення найбільш вивчений і найкраще піддається формалізації [129,144,167, 172, 272].

Можна розглядати, як мінімум, дві задачі пов'язаних з автоматизацією дедуктивних побудов:

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

■ задача перевірки справедливості даного твердження. Часто вона тра­ктується як задача автоматичного доведення теорем і формулю­ється таким чином. Дана деяка теорія (логічна модель); потрібно встановити, чи є певне твердження теоремою, тобто чи можна його вивести з аксіом даної теорії. Автоматизація дедуктивних побудов знаходить широке практичне за­стосування, наприклад, в експертних системах. Як ще один приклад мож­на згадати програмні системи, які аналізують математичні тексти, написа­ні спрощеною математичною мовою, та перевіряють правильність дове­день, що містяться у цих текстах.

Механізм автоматичного доведення теорем було покладено в основу однієї з основних парадигм сучасного програмування —логічного програ­мування. Програма розглядається як набір логічних формул разом з теоре­мою, що має бути доведена. Найвідомішим представником логічного про­грамування є мова Пролог [26, 172, 292].

Логічні моделі є одним з основних засобів задання знань. Позитивною характеристикою логічних моделей виступає однозначність теоретичного обґрунтування і можливість реалізації формально точних логічних побу­дов; недоліком — формальний процедурний стиль мислення. Людська ло­гіка — інтелектуальна модель з нечіткою структурою. У цьому полягає її відмінність від формальної логіки.

' • Логічною моделлю називається формальна система, що задається \ четвіркою <Т, Р, А, В>. Тут Т — множина базових елементів (алфа- - віт), Р — множина синтаксичних правил, на основі яких конструю­ються правильно побудовані формули; А — множина аксіом, тобто формул, які приймаються за істинні, В — множина правил виведення.

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

Логічні моделі та продукційні системи (розд. 8) основний акцент роб­лять саме на дедуктивному логічному виведенні.

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

7.2. Короткий вступ до числення предикатів

Предикатом називається деяка логічна функція від довільного числа аргументів, яка приймає одне з двох можливих значень — "істина " або "хибність ". Предикат можна розуміти як певне твердження, істинність якого залежить від змінних — об'єктів, про які йдеться в цьому тверджен­ні. Як приклад можна навести фразу "Xбільше за 2 Цей предикат є функ­цією від аргументу X і набуває значення "істина ", наприклад, при Х= З, і "хибність " при X = 1.

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

що мови програмування логічного типу є найзручнішими для роботи з базами знань.

Числення предикатів використовує такі основні елементи:

1. константи (константні терми) с,, с₂, ...;

2. змінні (змінні терми) х,,х₂, ...;

3. функціональні літери/,,/₂,

4. предикатні літерир_х,р₂,

5. логічні символи ~> , <-», &, v, V, 3;

6. спеціальний символ □.

Елементарне твердження складається з предиката і зв'язаних з ним тер- мів. Складні твердження будуються з елементарних за допомогою логіч­них зв'язок. Серед них можна виділити логічні зв'язки: "і" (and, &), "або " (or, v), "ні" (not, ~) та імплікацію (—>). Імплікація посідає особливе місце, оскільки вона використовується для побудови правил виведення і читаєть­ся "якщо ..., тоді ...".

Наступний перелік містить опис зв'язків, які використовуються в логіці, та їх змістовних інтерпретацій. Тут а та Ь означають будь-які твердження.

Зв'язок	Запис	Інтерпретація
Заперечення	~ а	"не є а"
Кон'юнкція	а&Ь	"а та b"
Диз'юнкція	a v b	"а або b"
Імплікація		"з а випливає Ьп
Тотожність (еквіва­лентність, рівність)	a<r*b	"а еквівалентне Ь"

Наприклад, запис: чоловік (женя) v жінка (женя) є однією з формалізацій запису твердження, що людина Женя може бути або чоловіком, або жінкою. Аналогічно,

чоловік (X) —> людина (X) означає, що якщо дехто на ім'я Хє чоловіком, то він є і людиною. Для імплікації та тотожності справедливі такі твердження:

а -» b дорівнює ( ~ a) v b, а <-> b дорівнює (а & b) v (~ а & - Ь), a<r±b дорівнює (а -» b) & (Ь -» а).

З кожним предикатом може бути пов'язаний квантор — елемент, який визначає, за яких умов предикат перетворюється на істинне висловлюван­ня. Розрізняють квантор узагальнення (V) і квантор існування (3).

Якщо и позначає змінну, аг — твердження, то запис Vw г означає, що "г справджується для всіх и ", а запис 3иг означає, що "існує и, для якої г справджується". Перший квантор називають квантором узагальнення, оскільки кажуть про будь-що у всесвіті ("для будь-якого и, ... "). Для зруч­ності запису позначатимемо його all. Другий називається квантором існуван­ня, оскільки вказує на існування деяких об'єктів {"існує и таке, що ... "). Для зручності запису його позначатимемо exists. Ось приклади використання цих кванторів: All (X, чоловік (X) -» людина (ЛГ)) означає, що для будь-якої змінної X, якщо вона означає чоловіка, то озна­чатиме і людину також, або ж для будь-якого X, якщо X— чоловік, то X— людина; або ж: всі чоловіки — люди. За тим самим принципом: exists (Z, батько (Іван, Z) & жінка (Z)) означає, що існує певний об'єкт, що може бути позначений змінною Z. При цьому Іван є батьком Z і Z — жінка. Ми можемо прочитати це таким чином: існує Zтаке, що Іван є батьком ZiZ — жінка; або: Іван має дочку.

У логіці предикатів елементарним об'єктом, який має значення "істи­на", є атомарна формула (літерал). Атомарна формула містить символьні позначення предиката і термів, які відіграють роль аргументів цього пре­диката. Узагальнено позначення предиката є ім'ям відношення, яке існує між аргументами.

Атомарна формула записується як позначення предиката і має такий вигляд: Р (/і, t₂, t„),

де Р — позначення предиката, a t\, t₂, ..., t„ — терми. Число термів для кожного предиката фіксоване і називається його арніс- тю. Терми визначаються так:

1. константний терм — терм;

2. змінний терм — терм;

3. якщо арність функціональної літери/є я, a t_u t₂, ...,t_n — терми, тоді /Оь t₂, ..t_n) також терм.

Вірно побудована формула отримується в результаті комбінування ато­марних формул за допомогою логічних зв'язок.

Символ □ позначає хибну замкнуту формулу і визначає поняття "про­тиріччя". Так, формула Л -> □ означає хибність А, вона еквівалентна фор­мулі ~ А.

Серед формул можна виокремити спеціальний клас формул: тотожньо істинні формули, які називають тавтологіями. Приклад тавтології:

Літерал називається позитивним, якщо він не стоїть під знаком запе­речення.

Літерал називається негативним, якщо він стоїть під знаком запере­чення.

8 Диз'юнктом (або фразою теорії) називється диз'юнкція деякої кіль­кості атомарних формул.

У теорії і практиці автоматичного доведення теорем найвживанішими є фрази спеціального типу, які називаються фразами Хорна (або хорнів- ськими диз'юнктами).

І Фразою Хорна називається диз 'юнкція довільної кількості атомарних •: формул, з яких позитивною є не більше ніж одна (тобто у фразі Хорна лише одна атомарна формула може не стояти під знаком заперечення). Фрази Хорна по суті є імплікаціями. Справді, розглянемо фразу ~Av~Bv~CvD (кожний з літералів А, В, С, D може залежати від довільної кількості констант і змінних, тут це несуттєво). Усі літерали, крім Д є негативними, отже, дана фраза являє собою фразу Хорна. Але відповідно до правил де Моргана вона еквівалентна фразі ~ (ABC) v D. А це, в свою чергу, є іншою формою запису імплікації (твердження D ви­пливає з кон'юнкції тверджень А, В, Q.

Для конкретних застосувань іноді потрібно привести логічні формули до спеціального вигляду. Прикладом може послужити пренексна нормаль- на форма.

Пренексною нормальною формою називається запис логічної форму- \ лиу вигляді:

^ К\Х\ К₂х₂... К„х_п М,

't де Кі — один з кванторів (існування чи узагальнення), М — деяка кон 'юнктивна нормальна форма, тобто кон'юнкція деякої кількості диз'юнктів.

Пренексну нормальну форму легко побудувати шляхом тотожних пе­ретворень логічних формул.

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

Приклад 7.1. Нехай маємо формулу Зх: Р (х). По суті це означає, що можна вказати деяку предметну константу с, невизначену, для якої твер­дження Р (с) є істинним. Тоді квантор існування усувається явним введен­ням цієї предметної константи. Таким чином, здійснюється перехід від формули Зх: Р (х) до формули Р (с). Константа с називається константою Сколема.

Приклад 7.2. Нехай маємо формулу У у Зх: Р (х, у). Тут квантор існуван­ня перебуває в області дії квантора узагальнення, і процедура дещо усклад­нюється. Знову ж таки ми можемо вказати деякий елемент с, для якого твердження Р (с, у) є істинним, але тепер с залежить від змінної у. Тому від формули Vу Зх: Р (х, у) можна перейти до формули У у Р (h (у), у). Тут h (у) — деяка функція, в цілому невизначена. Вона має назву функція Сколема.

Квантори узагальнення усуваються механічно на основі стандартної до­мовленості: вважається, що якщо фраза залежить від деяких змінних, то всі вони зв'язані квантором узагальнення. Наприклад, якщо x,y,z — змін­ні, то від формули Vx \/у Vz Р (х, у, z) здійснюється перехід до формули P(x,y,Z).

Для детальнішого ознайомлення з основами числення предикатів реко­мендуємо звернутися до відповідного підручника з математичної логіки, наприклад [112, 179].