Тема „Формальні системи. Алгебра висловлювань”

Формальні системи – це системи операцій над об’єктами, які розуміють як послідовності символів (тобто як слова у фіксованих алфавітах); самі операції також є операціями на символами.

Означення 1. Під формальною системою будемо розуміти деяку абстрактну (математичну) систему, що складається з множини аксіом та множини правил виведення, яку можна реалізувати машинним способом.

Означення 2. Аксіоми – це твердження про задані об’єкти і взаємозв’язки між ними, сформульовані у вигляді рядків деякої мови.

Означення 3. Правилами виведення називають чітко сформульовані процедури, які дають змогу повторювати нові рядки з тих, що існують.

Нові рядки є теоремами формальної системи. Позначимо формальну систему через F, множину аксіом, як і множину рядків, –через (₁, ₂, …, _n). Правило виведення в найзагальнішому вигляді можна подати обчислювальною функцією R(, ₁, ₂, …, _k) з кількістю аргументів (k + 1). Тут за аргументи використано рядки. Функція набуває значення істинності або хибності (І, Х). Якщо R(, ₁, ₂, …, _k) = І, то кажуть, що рядок  безпосередньо виводиться з рядків ₁, ₂, …, _k за правилом виведення. Надаючи далі правилу виведення деякої конкретної форми, дістаємо формальні системи окремого вигляду, які дають змогу ефективно розв’язувати деякий клас прикладних задач.

Означення 4. Доведенням в F теореми (рядка) називається скінченна послідовність рядків ₁, ₂, …, _l така, що кожний рядок з цієї послідовності є або аксіомою в F, або безпосередньо виводиться з деякої множини рядків, кожний з яких передує _I у послідовності; теоремою є останній рядок в послідовності.

Приклад. Нехай задано алфавіт A = {a, b, c, d, e, f}, з якого складено рядки формальної системи. Множина аксіом формальної системи: 1) abffe; 2) eedca; 3) ffb.

Правила виведення:

R₁(ff, eedca, abffe) = I;

R₂(abca, ffb, ff, eedca) = I.

Знайдемо можливе виведення в цій формальній системі, нумеруючи для зручності кожний рядок виведення:

1. eedca – аксіома 2;

2) abffe – аксіома 1;

3) ff – безпосередньо виводиться з (1), (2) та R₁;

4) ffb – аксіома 3;

5) abca – безпосередньо виводиться з (1), (2), (4) й R₂.

Отже, формальна система виводить як теорему рядок abca.

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

Аксіоматичний спосіб опису висловлювань

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

Наприклад, твердження „3 > 2” і „2  2 = 5” є висловлюваннями: перше – істинне, друге – хибне. Твердження „Трикутник називається рівностороннім, якщо всі його сторони рівні”, як і будь-яке інше означення, не є висловлюванням, а будь-яка терема, наприклад, „Якщо функція f(x), яка визначена в деякому околі точки x₀, диференційована в x₀, то вона в цій точці неперервна” – висловлювання. Нас не буде цікавити зміст висловлювань, а тільки їх істинність. Будемо позначати висловлювання буквами p, q, r, s, … Домовимось слова „істинно” і „хибно” позначати відповідно символами 1 і 0.

Над висловлюваннями визначені такі операції: заперечення, диз’юнкція, кон’юнкція, імплікація, еквівалентність. Нехай p і q – висловлювання, тоді:

1. запереченням p ( ) висловлювання p називається висловлюван­ня, яке є хибним, коли p істинне; та істинним, коли p хибне;

2. диз’юнкцією p  q висловлювань p і q називається висловлювання, яке є хибним, коли p і q хибні; і істинним – в інших випадках;

3. кон’юнкцією p  q висловлювань p і q називається висловлювання, яке є істинним, коли істинні p і q; і хибним в інших випадках;

4. імплікацією p  q висловлювань p і q називається висловлювання, яке є хибним, коли p істинне, а q хибне; і істинним – в інших випадках;

5. еквівалентністю p ~ q висловлювань p і q називається висловлювання, яке є істинним тоді і тільки тоді, коли p і q мають однакові істинностні значення.

Всі визначені раніше операції задаються в таблиці істинності

p	q		p  q	p  q	p  q	p ~ q
0	0	1	0	0	1	1
0	1	1	1	0	1	0
1	0	0	1	0	0	0
1	1	0	1	1	1	1

Запереченню відповідає зв’язка „не”, диз’юнкції – „або”, кон’юнкції – „та”, імплікації – „якщо …, то”, еквівалентності – „тоді і тільки тоді, коли …”

Позначимо через P множину всіх висловлювань. У множині P визначена унарна операція  і бінарні операції , , , ~, відносно яких множина P є замкнутою (тобто разом з деяким набором висловлювань у множині P містяться результати бінарних операцій над цими елементами). Отже, виникає алгебра висловлювань.

Застосовуючи до довільних елементів P ці операції, ми одержимо складні висловлювання – елементи множини P.

Наприклад,

(p  )  (r ~ p); (r  (p  s)) ~ q.

Написані формули називаються формулами алгебри висловлювань.

Формули алгебри висловлювань будемо позначати f(p, q, r, …, t) або U, V, …

Акуратне рекурсивне означення формули таке:

1. довільні висловлювання p, q, r, … є формулами;

2. якщо U і V формули, то (U), (V), U, V, (U)  (V), (U)  (V), (U)  (V), (U) ~ (V) є формулами;

3. тільки вирази, наведені в пунктах 1), 2) є формулами алгебри висловлювань.

Формули алгебри висловлювань f(p, q, r, …, t) і (p, q, r, …, t) називаються рівносильними, якщо для довільних істинних значень висловлювань p, q, r, …, t вони набувають однакові істинності значення (f  ).

Формула F = f(p, q, r, …, t) називається тавтологією, якщо висловлювання F істинне при довільних істинних значеннях p, q, r, …, t (f(p, q, r, …, t)  1).

Довільна формула U = f(p, q, r, …, t) при істинних значеннях висловлюваннях p, q, r, …, t набуває деяке істинне значення. Для їх визначення універсальним способом будуються таблиці істинності. Однак ці таблиці швидко ускладнюються з ростом кількості вихідних висловлювань. Інший спосіб полягає в використанні законів алгебри логіки. Вони перевіряються за допомогою таблиць істинності, а потім використовуються для спрощення. Наведемо ці закони, при цьому 0 і 1 означають хибне та істинне висловлювання:

1а) p  q = q  p,	1б) p  q = q  p,
2а) p  (q  r) = (p  q)  r,	2б) p  (q  r) = (p  q)  r,
3а) p  (q  r) = (p  q)  (p  r),	3б) p  (q  r) = (p  q)  (p  r),
4а) p  0 = p,	4б) p  1 = p,
5а) p  1 = 1,	5б) p  0 = 0,
6а) p  = 1,	6б) p  = 0,
7а) p  p = p,	7б) p  p = p,
8а) p  (p  q) = p,	8б) p  (p  q) = p,
9а) =  ,	9б) =  .

Для розв’язання складніших питань логіки висловлювань використовуються аксіоматичні теорії.

Аксіоматичні теорії – це формальні системи, які відповідають численню висловлювань. Як і кожні формальні системи, вони містять алфавіт, систему аксіом, правила виведення.

Аксіоматична теорія будується таким чином:

• визначається набір символів теорії Т, тобто скінченних послідовностей, які називаються виразами теорії Т;

• визначається множина формул, тобто підмножин виразів теорії Т;

• визначається підмножина формул, які називаються аксіомами теорії Т;

• задається множина R₁, …, R_m відношень між формулами, які називаються правилами виведення.

Означення 5. Якщо формула А і формули A₁, …, A_j знаходяться в деякому відношенні R_i, то А є безпосереднім висновком із формул A₁, …, A_j, сформульованим за правилом R_i.

Означення 6. Виведенням є будь-яка послідовність формул A₁, …, A_n, в якій для будь-якого і формула А_і є або аксіомою, або висновком з яких-небудь попередніх формул.

Означення 7. Формула А називається теоремою теорії Т, якщо в ній існує виведення, в якому останньою формулою є А. Це виведення називається виведенням формули А. Отже, теореми аксіоматичної теорії – це формули, які можуть бути виведені за певним правилом.

Означення 8. Формула А називається висновком із множини формул Г, якщо існує така послідовність формул A₁, …, A_n, що A_n = A і для будь-якого і, 1  i  n, А_і є або аксіомою, або формулою із Г, або висновком із деяких попередніх формул. Ця послідовність називається виведенням А з Г. Елементи Г називаються посилками виведення, або гіпотезами. Цей факт будемо позначати як Г А (тобто А є висновком Г).

Якщо множина Г складається із формул B₁, …, B_k, то це можна записати як B₁, …, B_k А. Якщо Г – порожня множина, то в цьому випадку писатимемо А (це означає, що А - аксіома).

Розглянемо деякі властивості поняття вивідності з системи гіпотез. Нехай Г – довільна множина формул Г = {A₁, …, A_k; B₁, …, B_k; C₁, …, C_k; D₁, …, D_k}, A, B, C – довільні формули. Тоді:

1. Г, A A. Справді, виведення А з системи гіпотез Г, А складається з однієї формули А;

2. якщо Г, A, B C, то Г, B, A C.

3. якщо Г А і B – формула з Г, то Г, B A. Справді, як виведення А з системи гіпотез Г, B можна взяти виведення A з системи гіпотез Г;

4. якщо Г A, Г B і A, B C, то Г C. Нехай A₁, …, A_n – виведення А з Г; B₁, …, B_n – виведення B з Г, C₁, …, C_k – виведення C з A, B. Тому C₁, …, C_k є виведенням C з Г;

5. якщо Г, A B та Г А, то Г B (правило вилучення гіпотези, що виводиться). Нехай B₁, …, B_n – виведення B з Г, A. Якщо в ньому не зустрічається формула А, то маємо виведення B з Г. Якщо в цьому виведенні зустрічається формула A, то нехай , …, – усі входження формули А у виведення. Нехай також A₁, …, A_m – виведення A з Г. Тоді , …, ; A₁, …, A_m; , …, ; A₁, …, A_m; , …, ; A₁, …, A_m; , …,B_n – виведення В з Г.