ПРИНЦИПИ ЛОГІЧНОГО ПРОГРАМУВАННЯ

Основи математичної логіки

З аристотелевской логіки випливає математична логіка - наука про правильну побудову умовиводів, тобто ланцюжків суджень, які доводяться (випливають) одна з одною. На відміну від класичної математики, яка оперує зі змінними, які можуть приймати нескінченне число значень, математична логіка найчастіше оперує з бінарними змінними, які приймають значення істина або брехня. Таким чином, якщо деяка предметна область (домен) описується п логічними змінними, то максимально можливе число станів дорівнює 2 ". Обмежене число станів домену робить можливим доказ на основі таблиць істинності, які добре знайомі тим, хто вивчав дискретну математику, в якій булеві функції визначаються виключно за допомогою таблиць істинності.

В інтелектуальних системах найчастіше знаходять застосування два різновиди логіки: пропозіціональная логіка і логіка першого порядку.

Пропозіціональная логіка (логіка нульового порядку) -

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

Логіка першого порядку - логіка, також оперує з бінарними висловлюваннями (предикатами), які мають один або більше аргументів. Число аргументів предиката називається його арность. Принципова відмінність логіки першого порядку від пропозіціональной логіки полягає в тому, що предикат представляє собою безліч екземплярів, які визначаються значеннями аргументів. Отже, тут уже неможливо обійтися булеві зв'язками, а необхідно використовувати квантори існування (3) і загальності (V).

Розглянемо класичний приклад, який використовується практично у всіх підручниках: якщо яблуко червоне і ароматне, то воно смачне. Для тих, хто вивчав булеву алгебру, очевидно, що дане правило містить кон'юнкцію вхідних змінних. Визначимо змінні A, R і Т, які відповідають відповідно за аромат, колір і смак, і складемо таблицю істинності, використовуючи функцію кон'юнкції (табл. 1.1).

Таблиця 1.1

Кон'юнкція T = AaR

Але чи випливає з вихідного твердження, що зелене або жовте яблуко не може бути смачним? Ні, тому що крім кон'юнкції в даному твердженні використовується імплікація X -> Y (якщо X то У, де X - антецедент, У - консеквент). Таблиця істинності для імплікації виглядає наступним чином (табл. 1.2).

Таблиця 1.2

Таблиця істинності для імплікації

З табл. 1.2 випливає, що імплікація помилкова в єдиному випадку - якщо антецедент істинний, а консеквент хибна. Іншими словами, з істинності консеквента не слід істинність антецедента. Якщо підставити в правило імплікації кон'юнкцію А л R (яблуко ароматне і червоне), то ми отримаємо табл. 1.3.

Таблиця 13

Таблиця істинності для імплікації А л R -> Т

Доведемо за допомогою цієї таблиці істинності наступне твердження. Нехай А = 1, R - 1, А л R - »7. Потрібно довести, що 7 = 1.

Доведення. Оскільки А - 1 і R - 1, фільтруємо таблицю істинності (див. Табл. 1.3), залишаючи в ній лише рядки, в яких А = 1 і R = 1. Залишаються дві останні рядки, яким відповідають значення 7 = 0 і 7 = 1. Імплікація Д л 7? -> 7 істинна тільки в останньому рядку, де 7 = 1. Затвердження доведено (якщо яблуко ароматне і червоне, то воно смачне).

Розглянемо тепер інший приклад. Дано: Л = 1,7? = О, А л R-> Т. Доведемо, що 7 '= 1 (якщо яблуко ароматне, але не червоне, то воно смачне).

Доведення. Отфильтруем табл. 1.3, залишивши в ній тільки рядки, в яких А = 1,7? = 0 (п'ята і шоста рядки). Імплікація А л R - »• 7 істинна для обох комбінацій змінних: (А = 1, 7? = 0, 7 = 0) і (Л = 1, 7? = 0, 7 = 1). Отже, ароматне, але не червоне яблуко може бути смачним, а може і не бути.

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