Логіка - Карамишева Н.В. - 4.2.1. Логіка висловлювань

4.2.1. Логіка висловлювань

Логічні висловлювання - суть тавтології, які показують внутрішні відношення, але самі не кажуть нічого... Вони - аналітичні висловлювання.

Л. Вітгенштайн

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

У межах логіки висловлювань можуть бути побудовані морфологічні системи (формально-логічні теорії без дедуктивної частини, тобто без аксіом і правил виведення) та логічні числення (формально-логічні теорії, на синтаксичному рівні котрих задаються системи їхніх аксіом і строго визначена сукупність правил виведення). Більшість класичних формально-логічних теорій логіки висловлювань побудовано у формі логічних числень. Перше числення висловлювань отримало назву "класичне числення висловлювань" (КЧВ) - формалізація висловлювань засобами особливої мови та здійснення логічних операцій над ними з метою перетворення простих висловлювань на складні та їх перетворення на нові складні висловлювання.

Класична логіка висловлювань (КЛВ) є основою сучасної символічної логіки, на базі якої створюються нові формально-логічні системи (логічні числення). Ідею логічного числення вперше сформулював німецький філософ, логік, математик Г. Ляйбніц. Історично першу систему логіки висловлювань, або алгебру логіки, створив англійський логік Дж. Буль, в якій використовували алгебраїчні методи для вирішення певних логічних задач. Подальший розвиток логіки висловлювань здійснювали логіки та математики - О. де Морган, Б. Шредер, Г. Фреге, Б. Рассел й ін.

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

Семантика визначає змістовний аспект неформальних відношень між висловлюваннями у термінах "висловлювання", "властивість", "відношення".

Логічну властивість висловлювання виражає термін "істиннісне значення висловлювання", який визначають суто формально, у процесі абстрагування від конкретного змісту висловлювання. У класичній логіці висловлювань висловлюванню надають два значення істинності: "істина" (і); "хибність" (#), відповідно ця формально-логічна система двозначна за значеннями істинності.

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

Мова логіки висловлювань - система символів, котрі називаються алфавітом. Алфавіт:

1. Символи для позначення простих висловлювань (пропозиційні змінні) - А, В, С, ... (або р, </, г, я; р{, р2, р ).

2. Символи, що позначають істиннісні значення висловлювань - "і", "*".

3. Символи для позначень пропозиційних зв'язок (логічні сполучники, логічні постійні):

- кон'юнкції л;

- нестрогої диз'юнкції V;

- строгої диз'юнкції X;

- імплікації ->;

- еквівалентності =;

- заперечення

4. Допоміжні (розділові, технічні) символи - (ліва дужка, права дужка).

Структура логіки висловлювань, побудованої у формі логічного числення: алфавіт, правила побудови формул із символів алфавіту; аксіоми, правила дедуктивного виведення із аксіом нових формул (доведення теорем) на підставі принципу логічного слідування; правила інтерпретації.

Правила побудови формул із символів алфавіту:

1.А - формула (кожна пропозиційна змінна є правильно побудованою формулою).

2. Якщо Л є довільною та правильно побудованою формулою, то -" А також є правильно побудованою формулою.

3. Якщо А, В - довільні формули, то й А Л В - формула; А V В - формула; А -> В - формула; А = В - формула.

4. Жодних інших формул у логіці висловлювань немає.

Формули поділяють на прості (елементарні, атомарні) й складні (молекулярні). Формула виду А є простою, а формула виду А у В - складною. Складні формули утворюють з простих за допомогою логічних операцій кон'юнкції, диз'юнкції, імплікації, еквівалентності, заперечення.

Подаємо приклади таких формул у логіці висловлювань:

- А л В - складне кон'юнктивне висловлювання (чит.: А і В);

- Л V В - складне диз'юнктивне висловлювання (чит.: А або В);

- А JL В - складне диз'юнктивне висловлювання (чит.: або А, або В);

- А - В - складне імплікативне висловлювання (чит.: якщо А, то В);

- А s В - складне еквівалентне висловлювання (чит.: якщо і лише якщо А, то В);

--'А - заперечення (чит.: неправильно, що А);

--1 В - заперечення (чит.: неправильно, що В).

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

Аналітична таблиця - метод розкладання складних формул на прості (елементарні, підформули), що здійснюють за правилами редукції (лат. reductio - повернення назад). Це схема зображення всіх формул, отриманих за правилами редукції. Правила редукції формулюють для всіх пропозиційних зв'язок: кон'юнкції, диз'юнкції, імплікації, еквівалентності, заперечення. Наприклад, якщо формула виду А Л В зображає кон'юнкцію, то вона розкладається на формули А, В, при чому ліворуч перед формулою, що редукується, ставлять символ Г, а всі формули, розташовані справа від символу редукування, позначають символом V. Якщо після застосування правил редукції стосовно конкретної складної формули отримують будь-яку просту формулу та її заперечення, то складну формулу називають замкненою.

Загальна аналітична таблиця для всіх пропозиційних зв'язок має таке зображення:

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

де символи Т і 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 використовують закони дистрибутивності, подвійного заперечення, законів де Моргана (про них розглянемо далі).