Розділ «4.2. Класична символічна логіка»

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

де символи Т і F позначають метавластивості виразу "бути істинним" і "бути хибним". Отже, кожна з двох можливостей (гілок) замкнена, оскільки в них проста атомарна формула А водночас істинна (Т(А) та хибна (F(A), що є явною суперечністю. У такий спосіб формула -o -o А = А - тотожно-істинна.

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

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

Наведемо приклад обґрунтування того, що формула виду (А V В) -> (В V А) є тотожно-істинною методом побудови таблиці істинності:

Відповідь: оскільки при всіх наборах істиннісних значень для А та В формула виду (А V В) -> (В V А) набуває значення "істинне", то вона - тотожно-істинна формула (аксіома, тавтологія).

Визначення або обґрунтування семантичної властивості будь-якої довільної складної формули в логіці висловлювань може здійснюватися і на синтаксичному рівні, тобто на підставі аналізу зовнішнього вигляду (структури) самої формули. Для цього використовують розв'язувальну процедуру - зведення формули до її кон'юнктивної нормальної форми (КНФ) або диз'юнктивної нормальної форми (ДНФ).

Якщо нормальна форма є формулою, яка містить лише логічні операції кон'юнкції, диз'юнкції та заперечення, то кон'юнктивою нормальною формою називають формулу, яка є кон'юнкцією елементарних диз'юнкцій (тобто диз'юнкцій простих формул або їх заперечень), а диз'юнктивною нормальною формою називають формулу, що є диз'юнкцією елементарних кон'юнкцій (тобто кон'юнкції простих формул або їх заперечень). Наприклад, формула виду ("o А, V А2) л А8 є КНФ, а саме - кон'юнкцією таких двох елементарних диз'юнкцій, як і А, V А2 та А,; формула виду (-"А1 Л А^) V А, V А4 є ДНФ, а саме - диз'юнкцією таких трьох елементарних кон'юнкцій, як -" А1 Л А2, А3, А4, а формула виду А, V А2 Л А3 не є ні КНФ, ні ДНФ.

Формула тотожно-істинна, якщо в кожну елементарну диз'юнкцію її КНФ одночасно входить будь-яка її проста формула разом зі своїм запереченням (таке входження ще називають регулярним). Наприклад, КНФ для формули (А -> В) -> (-ч В -" -і А) має вигляд (Ач В V -> А) л (-> В V В V -> А). Оскільки і перша елементарна диз'юнкція (А V В V -o А) містить регулярне входження А та -o А, і друга елементарна диз'юнкція ("o В V В V -"А) містить регулярне входження -"В і В, то й кон'юнкція цих двох істинних диз'юнктивних формул є істинною формулою, а отже, є істинною і та формула, для якої було знайдено саме цю КНФ.

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

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

У процесі зведення формул до КНФ чи ДНФ здебільшого o використовують закони дистрибутивності, подвійного заперечення, законів де Моргана (про них розглянемо далі).

Рівносильні формули логіки висловлювань

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

Рівносильну формулу можна отримати внаслідок заміни пропозиційних зв'язок на підставі відношення залежності між ними. Визначають, що для будь-якої формули можна назвати рівносильну для неї формулу, яка містить символи -і, V, V. Наприклад, формулу виду -1 А V-" В можна замінити формулою виду -" (А л В), що означає -oА /-іВ = -" (А л В); формулу виду А -> В можна замінити формулою -" А V В, що означає А -> В = -і А V В; формулу А V В можна замінити формулою -" (-"А Л В), що означає А V В =->(-* А Л -> В).

Рівносильні формули називаються законами логіки висловлювань.

Закони логіки висловлювань (ЛВ) - рівносильні, тотожно-істинні формули, що входять до структури класичної символічної логіки як формальної системи. До них належать: закон тотожності, закон несуперечності, закон виключеного третього, закон асоціативності, закон дистрибутивності, закон ідемпотентності, закон комутативності, закон контра позиції, закон поглинання, закон подвійного заперечення, закони де Моргана та ін.

Закон тотожності визначає, що кожне висловлювання є логічним наслідком самого себе. Формальний вираз закону А-> А.

Закон несуперечності визначає, що висловлювання А неправильне, якщо водночас істинні його ствердження і його заперечення. Формальний вираз закону -1 (А л -> А).

Закон виключеного третього визначає, що висловлювання А або істинне, або хибне за значенням істинності, але не може бути водночас істинним і хибним. Формальний вираз закону А 1 А.