4 Еквівалентність алгоритмічних систем

Алгоритмічні системи (машини Тьюрінга, нормальні алгоритми Маркова та частково рекурсивні функції )приводять до точних формальних визначень обчислюваної функції (за Марковим, за Тьюрінгом, ЧРФ), а значить уточнюють поняття алгоритму.

Зупинимось на спільних рисах даних алгоритмічних систем.

Спільні риси даних алгоритмічних систем

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

(для ЧРФ - це рекурсивна схема,

для НАМ – це нормальна схема,

для МТ – це програма МТ).

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

(для ЧРФ – це чіткі правила обчислення з використанням операцій суперпозиції, примітивної рекурсії, мінімізації,

для НАМ – це правила виконання підстановок

для МТ – це виконання кроків МТ за програмою.

2. В кожній алгоритмічній системі вказується єдиний спосіб представлення вхідної і вихідної інформаціїї (тобто значень аргументів і значень функцій).

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

Справедливе наступне твердження.

Класи ЧРФ, функцій обчислюваних за Тьюрінгом, функцій обчислюваних за Марковим співпадають між собою.

Тобто алгоритмічні системи ЧРФ, НАМ, МТ – еквівалентні. Це значить, що наукові результати отримані за допомогою алгоритмів однієї з алгоритмічних систем можуть бути отримані і в рамках іншої іншої алгоритмічної системи. Деякі задачі краще, легше розв'язувати в рамках однієї алгоритмічної системи, а деякі в рамках іншої. Не можна відмовлятися від жодної з них.

5 Математична логіка. Логіка висловлень

5.1 Теоретичні поняття і визначення

Математична логіка являється потужним інструментом для формалізації і представлення знань у пам'яті комп'ютера. Розділ математичної логіки - логіка предикатів являється математичною основою представлення знань. Прикладом предиката є вираз "число х ділиться на число y". Якщо ж замість х та у підставити натуральні числа 14 та 7, то дістанемо окреме істинне висловлення "число 14 ділиться на число 7"

Поняття висловлення являється базовим для подальшої теорії.

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

Основними поняттями в логіці висловлень є прості (елементарні) висловлення і операції над ними. Значення істинного висловлення позначають 1, значення істинності хибного висловлення позначають 0. Прості висловлювання позначають великими буквами латинського алфавіта А, В, …. А₁, В₁….

Над висловлюваннями установлюються операції, застосовуючи які до простих висловлювань, дістають складні висловлювання. Розглянемо такі операції: заперечення, кон'юнкція, диз'юнкція, імплікація, еквівалентність.

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

1 Заперечення висловлення А (або А) і читають "не А".

Таблиця істинності для заперечення має такий вигляд

А	Заперечення А, А
0	1
1	0

2 Кон'юнкцією (логичний добуток) двох висловлень А, В позначають А  В (АВ), читають "А і В".

Висловлення А В істинне тоді і тільки тоді, коли обидва висловлення А,В будуть істинними.

Таблиця істинності для кон'юнкції має такий вигляд:

А	В	АВ
0	0	0
0	1	0
1	0	0
1	1	1

3 Диз'юнкцію (логичну суму) двох висловлень А, В позначають АВ, читають "А або В".

Висловлення А В є хибним тоді і тільки тоді, коли хибні обидва висловлення А, В .

Таблиця істинності для диз'юнкції має такий вигляд:,

А	В	АВ
0	0	0
0	1	1
1	0	1
1	1	1

4 Імплікація двох висловлень А, В позначається АВ, читається "А імплікує В" (якщо А то В).

Висловлення А  В є хибним тоді і тільки тоді, коли А істинне,а В хибне.

Таблиця істинності для імплікації має такий вигляд:

А	В	АВ
0	0	1
0	1	1
1	0	0
1	1	1

5 Еквівалентність

Складне висловлення А  В (читається А еквівалентне В)

Висловлення АВ є істине тоді і тільки тоді, коли А і В обидва істинні або обидва хибні.

Таблиця істинності для еквівалентності має вигляд:

А	В	А  В
0	0	1
0	1	0
1	0	0
1	1	1

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

Усяке складне висловлення, яке складається з деяких простих висловлень, А, В, С …. за допомогою операцій , , , ,  і дужок, називається формулою логіки висловлень.

Дужки у формулі призначені для визначення послідовності виконання операцій.

Щоб зменшити кількість дужок у формулах, застосовують такий порядок старшості логічних операцій: , , , ,  .

Дамо формальне визначення правильно побудованої формули.

Правильно побудованими формулами (ППФ) в логіці висловлень являються такі формули: 1 Елементарне висловлення є ППФ; 2 Якщо А є ППФ, то А є теж ППФ; 3 Якщо А та В – ППФ, то (А  В) , (А  В), (А  В), (А В) є теж ППФ; 4 Ніяких інших формул в логіці висловлень немає.

Щоб визначити таблицю істинності будь-якої ППФ, треба застосовувати таблиці істинності для операцій, які входять в ППФ.

Щоб зменшити кількість дужок у формулах, застосовують такий порядок старшості логічних операцій (пріорітет операцій):

, , , , 

Зустрічаються такі формули, які істинні (їх значення 1) при будь-яких значеннях істинності простих висловлень, що входять до формули. Їх називають тотожно істинними формулами, або тавтологіями.
	Приклад	А		 А
	А   А	1	1	0
		0	1	1

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

_{Приклади}

1. А  А

А		 А
1	0	0
0	0	1

2 А   А

А		 А
1	0	0
0	0	1

Властивості тавтологій і суперечностей

1 Формула F є тавтологією тоді і тільки тоді, коли формула F є суперечністю.

2 Якщо А та (А  В) тавтології, то формула В теж тавтологія.

3 Нехай F- тавтологія. Тоді тавтологією буде формула F₁, отримана з F підстановкою ППФ замість висловлень, які входять до F.

Тобто, підстановка в тавтологію приводить до тавтології.

Приклад

F = A   А – тавтологія. Замість А підставимо ППФ, наприклад В  С. Тоді утвориться формула

F₁ = (В  С)   (В  С), яка теж буде тавтологією.

Введем поняття рівносильних формул.

Нехай дано 2 формули , складені з висловлень А_1, А_2,….А_n. Ці 2 формулиназивають рівносильними, якщо значення їх істинності однакові при довільних допустимих значеннях істинності висловлень А_1, А_2,….А_n.

Між рівносильними формулами ставлять знак  . Наприклад, АВ  А  В

Справеливе таке твердження:

Коли 2 формули А та В рівносильні, то формула А  В буде

тотожно істинною, і навпаки: з тотожної істинності формули А  В

випливає рівносильність формул А, В.

Повні системи логічних зв'язок

Ми вище розглянули кілька логічних операцій , , , , .

Не всі з розглянутих логічних операцій незалежні одна від одної. Так операцію імплікації () можна зобразити через  і .

Тобто АВ  А  В.

А		В	А		В
1	1	1	0	1	1
1	0	0	0	0	0
0	1	1	1	1	1
0	1	0	1	1	0

Виявляється, що за допомогою цих 2-х логічних зв'язок (, ) можна виразити інші логічні зв'язки.

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

Наприклад, повними системами логічних зв'язок є такі системи логічних зв'язок: (, ), (, ), (,).

Відновлення формул логіки висловлень за таблицями істинності.

Для формули логіки висловлень будується таблиця істинності, яка відповідає цій формулі.

А тепер побудуємо формулу логіки висловлень за таблицями істинності. Розглянемо приклад:

Таблиця істинності має вигляд

А	В	С	F(A,B,C)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Існує декілька формул, які відповідають цій таблиці істинності.

Це, наприклад, диз'юнктивна нормальна форма (ДНФ)

Для F(A,B,C) ДНФ має вигляд

F(A,B,C) = А  В С  А В С  А  В С  А  В  С.

Це диз'юнкція кон'юнкцій.

ДНФ булевої (логічної) ф-ції - це диз'юнкція кон'юнкцій тих наборів значень аргументів, де дана ф-ція дорівнює 1.

Щоб одержати ДНФ треба

1 У таблиці істинності вибрати ті набори аргументів, на яких формула дорівнює 1.

2 Сполучити ці аргументи знаками кон'юкції.

3 Над тими аргументами, які у вибраних наборах дорівнюють 0, поставити знак операції заперечення. В результаті отримаємо елементарні кон'юнкції.

2. Між елементарними кон'юнкціями поставити знаки операції

диз'юнкції.

Диз'юнкція побудованих елементарних кон'юнкцій і буде шуканою формулою.

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

• чи є формула тавтологією, або суперечністю;

• чи є формули логічно еквівалентними і т. д.

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

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

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

Тотожно-істинні висловлення мають входити в будь-яку теорію як загальнологічні закони.

Породження тотожно-істинних висловлень і є основною задачею числення висловлень.