Поняття логіки висловлень

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

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

Математична логіка вивчає та модулює тільки оповідальні речення. Наказові, окличні та питальні речення знаходяться поза сферою розгляду. Скорочені речення виключаються тому, що можуть мати подвійне значення. Наприклад, на питання «чи не спізнилися ви на лекцію?» скорочена відповідь «так» незрозуміла. В цьому випадку у відповіді необхідно більш повне твердження, яке могло б бути формалізоване. Для формалізації підійде речення: «Я спізнився на лекцію». Математична логіка не вивчає внутрішню структуру і зміст речень, а обмежується розгляданням їх істиннісних властивостей, тобто чи зображують вони істину або хибність. У зв'язку з цим із розглядання виключені оповідальні речення, для яких неможливо визначити, істинне воно або хибне. Очевидно, що таке зображення природної мови не є повним, але воно необхідне для застосування логіки висловлень.

Визначення

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

Визначення

Істина або хибність, приписана деякому висловленню, називається істиннісним значенням цього висловлення. Позначається: «Істина» — I, Т (True) або 1, «Хибність» — X, F (False) або 0.

Приклад. Визначити, які з даних речень є висловленнями: «Волга впадає в Чорне море», «Волга впадає в Каспійське море», «Який сьогодні день?», «Відстань від Землі до Сонця дорівнює 150000000 км».

Розв'язок. Перші два речення є висловленнями, причому перше є хибним висловленням, а друге — істинним. Третє речення висловленням не є (за визначенням), оскільки воно не оповідальне. Четверте речення також не є висловленням, тому що його істинність або хибність залежить від потрібної точності.

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

Визначення

Атомами (елементарними висловленнями) називаються висловлення, які відповідають простим оповідальним реченням, тобто не мають складових частин.

Як символи для позначення атомів використовуються великі букви латинського алфавіту А, В, С, ... або великі букви з індексами. Кожна буква у міркуванні повинна позначати одне і тільки одне елементарне висловлення.

Визначення

Логіка висловлень — це алгебраїчна структура ({X, І}, Ù, Ú, ¯, ®, ~, X, І) з носієм – двійковою множиною {X: «Хибність», І: «Істина»}, операціями— логічними зв'язками (Ù — кон'юнкція, Ú — диз'юнкція, ¯ — заперечення, ® — імплікація, ~ — еквівалентність) і константами: X — хибність і І — істина.

В розділі 4.2.3 глави 4 було визначено алгебру логіки, як алгебраїчну структуру (В, Ù, Ú, ¯, ®, ~, 0, 1), що створена двійковою множиною В = {0, 1} разом з операціями кон'юнкції, диз'юнкції, заперечення, імплікації, еквівалентності і константами 0 і l. Оскільки операції алгебри логіки і логіки висловлень однакові, а між множинами-носіями даних алгебраїчних структур {0, 1} і {Х,І} можна провести взаємно однозначну відповідність, приходимо до висновку, що вказані алгебраїчні структури ізоморфні (див. п. 3.2). Тому всі твердження, що зроблені у главі 4 відносно алгебри логіки, справедливі і для логіки висловлень, зокрема, комутативний, асоціативний та інші закони з п. 4.2.

Складні речення природної мови складаються з простих речень і службових слів («якщо», «і», «то», «або» і тощо). В граматиці зазначені службові слова називаються зв'язками (або сполучниками), оскільки вони об'єднують прості речення в одне складне. Наприклад, два речення «Ми поїдемо влітку до Криму» і «Ми поїдемо влітку в гори» можна об'єднати зв'язкою «або» в одне складне речення «Ми поїдемо влітку до Криму, або ми поїдемо влітку в гори». Тут зв'язку «або» не можна приєднати ані до першого, ані до другого простого речення, вона обслуговує одночасно обидва простих речення і тому називається бінарною. Розглянемо зворот «неправильно, що...», який вживається з ціллю заперечення. Наприклад, у реченні «Неправильно, що жителів у Києві менше, ніж у Харкові» відбувається заперечення речення «В Києві менше жителів, ніж у Харкові». Зв'язка «неправильно, що ...» є унарною, тому що застосовується до одного речення. Крім розглянутих, у природній мові існують зв'язки :«якщо..., то...», «чи», «і», «або», «ні... ні...», «...тоді і тільки тоді, коли...» й ін.

Операції логіки висловлень — логічні зв'язки — розглядаються як формальні позначення зв'язок, що їм відповідають, природної мови (таблиця 6.1).

Таблиця 5.1. Логічні зв'язки в логіці висловлень

Операції Ù, Ú, ®, ~ є бінарними логічними зв'язками, на відміну від операції Ø яка є унарною. Користуючись введеними логічними зв'язками, можна з елементарних висловлень будувати складні висловлення, що називаються формулами або молекулами.

Визначення

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

1.Атом є формула.

2.Якщо А і В — формули, то (А Ù В), (A Ú В), (А ® В), (А ~ В)і ØА — також формули.

3.Ніяких формул, крім породжених вказаними вище правилами, не існує.

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

Визначення

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

Для висловлення, що містить п атомів, можна скласти 2ⁿ інтерпретацій, як і для n‑місної булевої функції.

Поряд з висловленнями, істиннісне значення яких незалежне від ситуації, можна вважати однозначно визначеним, як, наприклад, «2 ´ 2 = 4» = I, існують висловлення, які можуть приймати різні значення. Наприклад, висловленню «Завтра буде дощ» можна надавати значення і «Істина», і «Хибність» залежно від конкретної ситуації.

Формули логіки висловлень можна задавати таблицями істинності подібно до булевих функції. Наведемо таблицю істинності для логічних зв'язок логіки висловлень (таблиця 5.2).

Таблиця 5.2. Таблиця істинності логічних зв'язок

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

Заперечення. Заперечення ØА істинне тоді і тільки тоді, коли А хибне. Ця унарна операція відповідає запереченню у звичайній мові, яке може мати різні синтаксичні вирази, наприклад, речення «Неправильно, що у Івана є час» рівнозначне реченню «У Івана немає часу».

Кон'юнкція. Висловлення А а В, що називається кон'юнкцією А і В, істинне тоді і тільки тоді, коли істинні обидва висловлення А і В. Ця логічна операція відповідає у природній мові зв'язці «і», що з'єднує два речення.

Приклад. Записати у вигляді формули логіки висловлень і визначити істиннісне значення таких висловлень:

І — «6 ділиться на 3, і 10 більше 5»;

II— «6 ділиться на 3, і 7 більше 10».

Розв'язок. Виділимо атоми. їх три:

А — «6 ділиться на З», В — «10 більше 5»,

С— «7 більше 10».

Тоді висловлення І буде відповідати формулі А Ù В, висловлення II — формулі А Ù С Будемо вважати, що висловлення А і В істинні, а висловлення С хибне. Використовуючи істиннісні значення висловлень А, В, С,визначимо значення висловлень І і II:

А Ù В = І Ù І = І; А Ù С = І Ù Х = Х.

Диз'юнкція. Висловлення A Ú В,що називається диз'юнкцією А і В, хибне тоді і тільки тоді, коли хибні обидва висловлення А і В.

Ця логічна операція відповідає поєднанню висловлень природної мови за допомогою зв'язки «або», що вжита у розумінні «або, що не виключає»: «правильне А, або правильне В, або обидва висловлення правильні».

Приклад. Записати у вигляді формули логіки висловлень і визначити істиннісне значення таких висловлень:

І — «5 + 2 = 10 або 5 ´ 2 = 10»,

ІІ — «6 - 3 = 2 або 3 ´ 2 = 5».

Розв'язок. Виділимо атоми:

А — «5 + 2 = 10»; С— «6 - 3 = 2»;

В — «5 ´ 2 = 10»; D— «3 ´ 2 = 5».

Тоді висловлення І буде відповідати формулі A Ú В,висловлення II — формулі С Ú D. Висловлення В істинне, а висловлення А, С і D хибні, тому:

A Ú В = Х Ú І = І; C Ú D = X Ú X = I

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

В імплікації А ® В висловлення А називається засновком (умовою, антецедентом), В — наслідком (висновком, консеквентом). Причинно-наслідковий зв'язок між А і В, що виражається імплікацією, на природній мові описується такими зворотами: «якщо А,то В»,«А є достатньою підставою для В», «В, тому що А», «В, за умови виконання А», «А тягне В» тощо.

Використовувані в точних науках поняття достатньої та необхідної умов можна формально виразити за допомогою імплікації. Саме для двох фактів (подій) А і В висловлення А ®В означає, що «А є достатньою умовою для В» і одночасно, що «B є необхідною умовою для А». Необхідність B для А виражається також у формі «В тільки, якщо А». Твердження «А є необхідною і достатньою умовою для B» еквівалентне подвійній імплікації А « В, або

(А ® B) Ù (B ® А) = А « B.

Розглянемо кілька прикладів.

У висловленні «Якщо число п — парне (А), то п ділиться на 4 (В)» умова А буде необхідною, але недостатньою. Жодне непарне число на 4 не ділиться, і в той же час є парні числа, які не діляться на 4. Отже, правильна імплікація B ® А,вихідне висловлення А ® B хибне.

У висловленні «Якщо йде дощ (А), то на небі хмари (В)» умова А буде достатньою, але не необхідною. Існують випадки, коли на небі є хмари, але дощу немає. Тут правильне вихідне висловлення А ® В.

У висловленні «Якщо геометрична фігура — квадрат (А), то вона — рівнобічний прямокутник (В)» умова А буде і необхідною і достатньою для виконання B: А«В.

Приклад. Записати у вигляді формули логіки висловлень і побудувати таблицю істинності висловлення «Якщо йде дощ, то над моєю головою відкрита парасолька». Розв'язок. Введемо атоми:

А — «йде дощ»;

B — «над моєю головою відкрита парасолька».

Тоді висловлення «Якщо йде дощ, то над моєю головою відкрита парасолька» буде відповідати формулі А ® В. Результати інтерпретації цього висловлення наведено у таблиці 5.3.

Таблиця 5.3. Таблиця істинності висловлення

Другий рядок таблиці 5.3 вказує на відсутність причинно-наслідкового зв'язку між подіями А і В.

Еквівалентність (еквіваленція). Якщо А і В — висловлення, то висловлення А ~ В істинне тоді і тільки тоді, коли А і В або обидва істинні, або обидва хибні.

Ця операція відповідає у природній мові зворотам: «...тоді і тільки тоді, коли...», «для того щоб..., необхідно і достатньо...». Наприклад, «Вивчення дискретної математики буде успішним тоді і тільки тоді, коли буде освоєна математична логіка».

Використовуючи таблицю істинності еквівалентності, можні довести, що вираз А~В еквівалентний виразу (А ® В) Ù (В ® А). Таким чином, логічна еквівалентність зображує імплікацію в обох напрямках, тому вираз «А істинне тоді і тільки тоді, коли В істинне» означає, що «А тягне В, і В тягне А».

Заміняючи імплікацію її записом у вигляді ДКНФ (А ® В = Ø A Ú В), одержимо:

А ~ В = (А ® В) Ù (В ® А) = (ØА Ú В) Ù (ØВ Ú А),

А ~ B = (ØA Ú B) Ù (ØВ Ú A). (5.1)

Формула (5.1) дає ДКНФ для еквівалентності. За принципом двоїстості (п. 4.3) ДДНФ для еквівалентності має вигляд:

A ~ B = A Ù B ÚØ A ÙØ B. (5.2)

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

I — «Для того щоб 2 ´ 2 = 4, необхідно і достатньо, щоб 2 + 2 = 4»;

II — «2 ´ 2 = 5 рівносильно тому, що 3 ´ 3 = 8».

Розв'язок. Введемо позначення атомів:

А — 2 ´ 2 = 4; В — 3 ´ 3 = 8;

С — 2 + 2 = 4; D — 2 ´ 2 = 5.

Висловлення І відповідає формулі А ~ С,висловлення II — формулі D ~ В. Будемо вважати, що атоми А і С істинні, а атоми В і D — хибні, і визначимо істиннісні значення складних висловлень:

А ~ С = І ~ І = І; D ~ B = X~X = I.

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

Наприклад, такі вирази бездужок дорівнюють формулам з дужками:

А ® В Ù С = А ® (В Ù С);

С ~ А Ù В ® С = С ~ ((А Ù В) ® С).

Будь-якій формулі логіки висловлень можна поставити у відповідність деяке складне висловлення природної мови і навпаки, «правильні» складні речення можна записати у вигляді формули логіки висловлень. Аналіз складного речення необхідно починати з визначення такого факту: чи є воно скороченим варіантом більш розповсюдженого складного речення? Скорочений варіант слід замінити повним варіантом речення. Далі виділити прості речення та взяти їх в дужки, залишаючи поза дужками службові слова, що поєднають прості речення. Процес взяття у дужки повторюється доти, доки цілком усе складне речення не виявиться взятим у дужки. Після цього сполучники та звороти природної мови замінюються відповідними логічними зв'язками, а прості речення — атомарними формулами.

Приклад. Записати у вигляді формули логіки висловлень таке речення: «Оскільки я ліг пізно спати, я проспав і через це не пішов на пару».

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

«(Оскільки (я ліг пізно спати), (я проспав)) і через це не (пішов на пару)».

Всі три речення зв'язані службовими словами, що виражають логічні відношення. Крім цього, перед третім простим реченням стоїть частка «не», що відповідає логічній операції «заперечення». Третє просте речення не є повним, оскільки розділяє спільний підмет «я» з другим простим реченням. Доповнимо третє речення відсутнім підметом і введемо атоми Р, Q, S таким чином:

Р — «Я ліг пізно спати»;

Q— «Я проспав»;

S — «Я пішов на пару».

Замінимо прості речення символами атомів, а службові слова — логічними зв'язками, одержимо формулу логіки висловлень:

(Р ® Q) ® ØS.

Приклад. Побудувати формулу і таблицю істинності для висловлень: «Якщо студент не підготувався до іспиту або йому попався складний білет, то він не складе іспит на позитивну оцінку». Визначити, в яких випадках це висловлення виявиться хибним.

Розв'язок. Виділимо прості висловлення і послідовність їх поєднання службовими словами за допомогою дужок: «Якщо ((студент не підготувався до іспиту) або (йому попався складний білет)), то (він не складе іспит на позитивну оцінку)». Позначимо атоми:

А— «Студент підготувався до іспиту»;

В— «Студенту попався складний білет»;

С— «Студент складе іспит на позитивну оцінку».

Одержана формула має вигляд: (ØА Ú В) ® ØС.

Побудуємо відповідну таблицю істинності (таблиця 5.4).

Таблиця 5.4. Таблиця істинності (ØА Ú В) ® ØС

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

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

Визначення

Формула називається тотожно істинною (тавтологією або загальнозначущою), якщо вона приймає значення «Істина» на всіх інтерпретаціях (наборах значень змінних). Формула називається тотожно хибною (суперечливою або нездійсненною), якщо вона приймає значення «Хибність» на всіх інтерпретаціях. Формула називається незагальнозначущою, нейтральною або несуперечливою, якщо вона на одних інтерпретаціях приймає значення «Істина», а на інших— «Хибність». Усі формули, які не належать до суперечливих, утворюють множину здійсненних формул.

Визначення

Міркування називається правильним, якщо воно виражається тотожно істинною формулою.

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

Довести, що формула є тавтологією, можна двома способами:

1. Побудувати таблицю істинності цієї формули. Тоді, якщо у таблиці істинності на всіх інтерпретаціях функція приймає значення «Істина», то відповідне до формули міркування є тавтологією.

2. Застосувавши до формули тотожні перетворення, звести її за допомогою тотожних перетворень до виду одного з логічних законів. Якщо в результаті перетворень одержимо значення «Істина», то формула — тавтологія.

Запитання

1. Який вид речень моделює формальна логіка?

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

3. Дайте визначення поняттю «висловлення».

4. Що мають на увазі під істиннісним значенням висловлення?

5. Які висловлення називаються атомами?

6. Дайте визначення логіки висловлень.

7. Що у логіці висловлень називають логічними зв'язками, наведіть їх.

8. Покажіть, що алгебра логіки і логіка висловлень ізоморфні. Який з цього маємо висновок?

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

10.Наведіть приклади формул логіки висловлень, що містять будь-які логічні зв'язки, і відповідних до них речень природної мови.

11.Сформулюйте алгоритм запису складного речення природної мови у вигляді формули логіки висловлень.

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

Завдання

1. Чи є такі формули загальнозначущими, суперечливими або несуперечливими:

а) Ø(ØА) ® А;

б) (А ® В) ® (В ® А);

в) (А Ù (В® А)) ® А;

г) (A Ú ØВ) Ú (ØA Ú В).

2. Розставити різними способами дужки у таких формулах:

а) -A Ú -В Ù С;

б) А ® В ® С ® D.

3. Виключити якомога більше число дужок у формулі:

а) (Ø((A)Ú (C))) Ú (В);

б) (((А) ® (В)) ® (C) Ú ((А) ® ((В) ® (С)));

в) ((В) ~ (Ø(С))) Ú (((А) ® (А)) ® ((В) Ú (D)));

г) Ø((Ø((A) Ú (В))) Ø (С)) ® ((Ø((С) ® (D))) Ú E));

д) (Ø((В) ~ (С))) Ù ((Ø(E))Ú (Ø(А)));

e) ((Ø((А) ® (В))) Ú (Ø((C) Ú (D)))Ù Ø(F)).

4. Побудуйте складні висловлення з використанням тільки зазначених операцій:

а) еквівалентність;

б) імплікація і кон'юнкція;

в) заперечення, кон'юнкція і диз'юнкція.

5. Доведіть, що заперечення висловлення «А є достатня та необхідна умова для В» еквівалентне висловленню «ØА є достатня і необхідна умова для ØВ».

6. Побудуйте висловлення, еквівалентне A Ú В, використовуючи тільки операції заперечення і кон'юнкції.

7. Побудуйте складне висловлення, еквівалентне A Ú В, використовуючи тільки операції кон'юнкції і заперечення.

8. Побудуйте складне висловлення, еквівалентне А Ù В, використовуючи тільки операції диз'юнкції і заперечення.

9. Побудуйте два складних висловлення, еквівалентних А ® В, використовуючи тільки:

а) операції диз'юнкції і заперечення;

б) заперечення і кон'юнкції.

10. Використовуючи тотожності, спростіть формули логіки висловлень:

а) Ø (A Ú В Ú С) (А (В Ú ØС)) Ù ØВ;

б) (A Ú В) Ù ØС Ú A Ú ØС Ú B Ú A.