Багатозначна логіка

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

Вперше багатозначна логіка з'явилася через заперечення аристотелева закону виключеного третього. Відповідно до цього закону диз'юнктивне висловлення р Ú Ø р є тавтологія, а атомарне висловлення р у аристотелевій логіці завжди або істинне, або хибне. Оскільки в аристотелевій логіці будь-яке висловлення може приймати тільки одне з двох значень істинності (істину або хибність), вона одержала назву двозначної логіки. В 1921 році Я. Лукашевич у маленькій статті на двох сторінках розглядає трьохзначну логіку, тобто таку логіку, в якій будь-яке висловлення р може приймати одне з трьох можливих значень істинності. Незалежно від Лукашевича Е. Пост аналізує m-значну логіку, в якій висловлення р може приймати одне з m можливих значень істинності, де m — будь-яке ціле число, більше за 1. У випадку, коли m більше за 2, логіку називають багатозначною. В 1930 році Лукашевич і Тарський приступають до подальшого вивчення m-значної логіки. В 1932 році поняття m-значної логіки узагальнюється Г. Рейхенбахом, що розглядає нескінченнозначну логіку, в якій для висловлення р існує нескінченна множина значень істинності.

Видатний вчений А. Гейтінг приблизно у то й же час побудував двозначну символічну логіку, виходячи з потреб інтуїціониської математичної школи. Ця логіка, на відміну від аристотелевої, не приймає беззаперечно законів виключеного третього і подвійного заперечення. Внаслідок цього закони створеної зі спеціальними цілями логіки Гейтінга, як і закони багатозначних логік, відрізняються від законів Аристотеля. Тому такі логіки називають неаристотелевими. Символічна двозначна логіка, побудована Гейтінгом у роботі «Принципи математики», належить до неаристотелевих логік, відрізняючись від аристотелевої іншою інтерпретацією імплікації.

Подібно неевклідовим геометріям неаристотелеві логіки також знайшли собі застосування. Нескінченнозначна логіка була задумана Г. Рейхенбахом як фундамент математичної теорії ймовірності. А у 1933 році Т. Швицький помітив, що багатозначні логіки можуть бути використовувані у сучасній квантовій фізиці. Багато аспектів такого використання були досліджені Г. Біркгофом і Г. Рейхенбахом. Використання інтуїціоністами логіки Гейтінга також свідчить про математичні цінності нових логік.

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

Таблиця 5.11. Таблиця істинності кон'юнкції

Таблиця 5.11 побудована таким чином: у лівому стовпці знаходяться можливі значення істинності для висловлення р, а у верхньому рядку — можливі значення істинності для висловлення q. Знаючи значення істинності вказаних висловлень, можна знайти значення їх кон'юнкції у комірці, що стоїть на перетині рядку, що відповідає значенню істинності р, і стовпця, відповідного значенню істинності q. Оскільки, за визначенням, кон'юнкція істинна в тому і тільки в тому випадку, коли обидва висловлення р і q істинні, значення І стоїть у лівій верхній комірці таблиці, а врешті — X. Зазначимо, що таблиця заповнюється на підставі одного лише визначення операції кон'юнкції.

Тепер перейдемо до трьохзначної логіки і позначимо три можливі значення істинності висловлення через І, «?» і X. Знов складемо таблицю істинності операції кон'юнкції (таблиця 5.12). Оскільки кон'юнкція істинна, коли обидва висловлення р і q істинні, ліва верхня комірка таблиці повинна містити значення І, крім того, І не може знаходитися ні в якій іншій комірці таблиці. Таким чином, залишається вісім комірок, в кожній з яких може бути записано або значення X, або значення «?». Всього одержується 2⁸ = 256 способів заповнення таблиці. Звідси маємо, що у трьохзначній логіці існує 256 різних визначень кон'юнкції.

Таблиця 5.12. Шаблон таблиці істинності кон'юнкції у трьохзначній логіці

В таблицях 5.13 і 5.14 наведено дві з 256 можливих таблиць істинності, операції кон'юнкції у трьохзначній логіці.

Таблиця 5.13. Таблиця істинності кон'юнкції у трьохзначній логіці (Лукашевич та ін.)

Таблиця 5.14. Таблиця істинності кон'юнкцїі у трьохзначній логіці (Бочар)

Таблиця істинності 5.13 була запропонована Лукашевичем, Постом і Россером. Вона будується відповідно до угоди, за якою значення «?» більш хибне, ніж І, але менш хибне, ніж X, а значення кон'юнкції співпадає із значенням істинності більш хибного із складових висловлень.

Відмінне від описаного визначення кон'юнкції дає Бочар (таблиця 5.14). За Бочаром символ «?» означає нерозв'язність, а кон'юнкція висловлень р і q вважається нерозв'язною у випадку нерозв'язності хоча б одного із складових висловлень.

Розглянемо таблицю істинності операції заперечення. У випадку заперечення єдине обмеження полягає у тому, що Øр не може бути істинним при істинності висловлення р,і Øр не може бути хибним у випадку хибності р. Вказане обмеження повністю визначає таблицю істинності для заперечення у двозначній логіці і припускає 12 можливих способів визначення заперечення у трьохзначній. Нижче наведено дві з 12 можливих для заперечення таблиць істинності операції заперечення. Таблиця істинності 5.15, що запропонована Постом, заснована на угоді, згідно з якою операції заперечення привласнюється наступне за порядком значення аргументу. Таблиця істинності 5.16 була запропонована Бочаром, Лукашевичем і Россером, які виходили з того, що Ø(Øр) повинне бути еквівалентне р.

Таблиці істинності інших логічних операцій можуть бути побудовані на підставі їх визначення за допомогою операцій кон'юнкції та заперечення. Оскільки кон'юнкція та заперечення незалежні, а решта операцій може бути через них виражена, то існує взагалі 256 ´ 12 = 3072 різних трьохзначних логік. Таким чином, кількість різних можливих структур багатозначної логіки надзвичайно велика.

Таблиця 5.15. Таблиця істинності заперечення у трьохзначній логіці (Пост)

Таблиця 5.16. Таблиця істинності заперечення у трьохзначній логіці (Бочар та ін.)

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

Визначення

Дійсне число Т(р) з інтервалу [0, 1], яке ставиться у відповідність висловленню р, називають значенням істинності висловлення р.

Значення істинності Т(р) можна розуміти як ймовірність того, що висловлення р істинне, причому два висловлення, що мають одне й те ж значення істинності, можна вважати логічно еквівалентними. Значення істинності Т(р) = 1 означає істинність, а значення Т(р) = 0 — хибність висловлення р. Заперечення Øр визначається за допомогою значення істинності таким чином: Т(Øр) = 1 - Т(р).В трьохзначній логіці, наприклад, як значення істинності можна прийняти числа 0, 1/2 і 1. Якщо значення істинності Т(р) = 1/2, то значення істинності Øр також дорівнює 1/2, і р виявляється логічно еквівалентним своєму запереченню. Таке висловлення може бути назване сумнівним, причому заперечення цього висловлення також виявляється сумнівним. Зазначений підхід свідчить про наявність тісного зв'язку між багатозначними логіками і теорією ймовірностей.

Багатозначна логіка розглядає однорідні логічні функції, що визначені на множині (0, 1, ..., k - 1), яка складається з k елементів. В силу однорідності сама функція k-значної логіки від п змінних приймає значення з тієї ж скінченної множини.

Визначення

Функції k-значної логіки визначені і приймають значення, що входять до деякої множини В_k = {0, 1, ..., k - 1}, що називається алфавітом цієї логіки.

Функцію k-значної логіки однозначно визначає її таблиця значень (істинності). Множину всіх функцій k-значної логіки позначають P_k. Кількість функцій P_k, що залежать від п змінних, дорівнює . Як і у двозначній логіці, висловлення зображуються у вигляді формул k-значної логіки. Елементарні функції зображують узагальнення аналогічних функцій двозначної логіки. Розглянемо основні функції k‑значної логіки.

Унарні функції

1. Циклічне заперечення:

Øх = х + l(mod k),

де у mod k — залишок від ділення у на k.

Таким чином, ця елементарна функція зображує узагальнення заперечення у розумінні «циклічного» зміщення значень:

2.Заперечення Лукашевича:

.

Наведена елементарна функція N_x є іншим узагальненням операції заперечення у розумінні «дзеркального» відображення значень.

3. Узагальнене заперечення:

Елементарна функція І^σ(х)при σ ¹ k – 1 є узагальненням деяких властивостей заперечення.

4. Характеристична функція:

Функція J^σ(x) — характеристична функція значення а при σ ¹ k – 1 зображує узагальнення операції заперечення.

Бінарні функції

1. Узагальнення кон'юнкції:

min(x_i, х_j).

2. Інше узагальнення кон'юнкції:

x_i х_j (mod k).

3. Узагальнення диз'юнкції:

max(x_i, х_j).

Визначення

Система функцій f₁... f_n називається повною, якщо будь-яка функція з P_k може бути зображена у вигляді формули, що складається з цих функцій.

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

В k-значній логіці існує k констант f₀ =0, f₁ = 1, ..., f_k-1 = k - 1. Серед функцій однієї змінної найбільш часто використовуваними є такі:

1) Характеристичні функції i-го порядку — f₀(x), f₁(x), f₂(x),що визначені в таблиці 5.17.

Таблиця 5.17. Функції однієї змінної у трьохзначній логіці

2) Заперечення Лукашевича N_x = k - 1 - х.

3) Функція циклічного заперечення Øх = х + 1 (mod). Таблиці істинності вказаних функцій у трьохзначній логіці будуть мати вигляд, що зображений у таблиці 5.17. Серед функцій двох змінних найбільш важливе значення мають такі:

1) значна диз'юнкція — x₁ Ú х₂= mах(x₁, х₂).

2) значна кон'юнкція — х₁Ù х₂ = mіn(х₁, х₂).

3) Функція Шеффера — Веббах — х₁|х₂ = x₁ Ú х₂ + l(mod k).

4) Додавання за модулем k – x₁+ x₂ (mod k).

5) Множення за модулем k – х₁* х₂ (mod k).

Значення даних функцій при k = 4 зображено в таблиці 5.18.

Таблиця 5.18. Функції двох змінних у чотиризначній логіці

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

Запитання

1. Що розуміють під багатозначною логікою?

2. Які існують різновиди багатозначних логік?

3. Скільки різних визначень кон'юнкції існує у чотиризначній логіці?

4. Складіть таблицю істинності кон'юнкції у трьохзначній логіці.

5. В чому полягає єдине обмеження операції заперечення у багатозначній логіці?

6. Дайте визначення поняттю значення істинності висловлення.

7. Сформулюйте визначення алфавіту k-значної логіки.

8. Скільки існує різних функцій k-значної логіки від п змінних?

9. Запишіть формули основних унарних функцій k- значної логіки.

10.Назвіть найважливіші бінарні функції k-значної логіки.

11.Яка система функцій й-значної логіки називається повною?

12.Назвіть найбільш часто використовувані функції однієї змінної.

13.Складіть таблицю основних функцій двох змінних у чотиризначній логіці.

Завдання

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

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

3. За аналогією з двохзначною логікою доведіть справедливість дистрибутивного закону у k-значній логіці.

4. Побудуйте таблиці істинності функцій однієї змінної у чотиризначній логіці.

5. Запишіть формули ДДНФ і ДКНФ у k-значній логіці.