Логіка для всіх / Навчальні матеріали

Короткий вступ в логіку висловлювань

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

Про все це написано багато розумних книжок різними авторами в різний час на різних мовах ... Можна знайти багато "повчальних" посилань в інтернеті ... Я не прагну осягнути неосяжне (хоча іноді дуже хочеться), моя мета - постаратися піднести матеріал як інструмент для вирішення ряду цікавих задач зазвичай буває навпаки :) - завдання служать для розуміння, осмислення і запам'ятовування пройденого).

Це короткий вступ, зрозуміло, не вичерпує тему повністю, і якщо у вас виникають питання, питайте.

Для початку кілька визначень від mega.km.ru (Можна пропустити :)):

ЛОГІКА ВИСЛОВЛЮВАНЬ, розділ логіки, в якому питання про істинність або хибність висловлювань розглядається і вирішується на основі вивчення способу побудови висловлювань з т.зв. елементарних (надалі не розкладаються і не аналізованих) висловлювань за допомогою логічних операцій кон'юнкції ( "і"), диз'юнкції ( "або"), заперечення ( "не"), імплікації ( "якщо ..., то ...") і ін. Логіку висловлювань, що задається системою постулатів (аксіом і правил виводу), називають обчисленням висловлювань.

ВИСЛОВЛЮВАННЯ, думка, виражена розповідним пропозицією і що може бути істинною або помилковою.

АНАЛІТИЧНА ВИСЛОВЛЮВАННЯ, висловлювання, істинність або хибність якого може бути встановлена ​​виключно на основі аналізу його граматичної чи логічної структури. Приклади справжніх аналітичних висловлювань логічні закони.

МІРКУВАННЯ, форма мислення, що представляє собою поєднання понять, з яких одне (суб'єкт) визначається і розкривається через інше (предикат).

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

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

Отже, які бувають висловлювання?

Поки досить того, що висловлювання може бути простим або складним, істинним або хибним. Наприклад, висловлювання "Йде дощ" - просте, а справжнє воно чи хибне залежить від того, яка погода зараз за вікном. Якщо дійсно не перестаючи ллє дощ, то висловлювання - істинне, а якщо нещадно палить сонце, і марно чекати дощу, то висловлювання "Йде дощ" буде хибним.

А можна взяти для прикладу більш певне (в сенсі значення істинності) висловлювання "Місяць - супутник Землі" - просте і щире. А ось "Сонце - супутник Землі" буде хибним висловлювання (і простим). Ускладнюємо завдання: "Місяць - супутник Землі і Сонце - супутник Землі". На цей раз наше висловлювання складне, тому що воно складається з двох простих, і, що найважливіше, це висловлювання хибне, так вже влаштована логічна (пропозіціональная) зв'язка "і" (сполучення). Якщо вона об'єднує істинні висловлювання - складне висловлювання буде істинним, а в усіх інших випадках - хибним. А скільки всього випадків? Кожне висловлювання може бути істинним або хибним, якщо розглядати два висловлювання, то отримаємо 4 комбінації: обидва істинні, обидва помилкові, одне істинне, інше помилкове, і навпаки.

Розглянемо тепер висловлювання "Місяць - супутник Землі або Сонце - супутник Землі" - складне і справжнє. На цей раз сполучною ланкою виступає "або" (диз'юнкція), яка приймає помилкове значення тільки коли всі вхідні висловлювання - хибні, якщо хоча б одне справжнє, то все диз'юнктивне висловлювання - істинне.

Але ми ще можемо перетворити вислів "Місяць - супутник Землі" в помилкове, а "Сонце - супутник Землі" в справжнє, якщо скажемо "Невірно, що Місяць - супутник Землі" і "Невірно, що Сонце - супутник Землі". Так діє на висловлювання зв'язка "не" (заперечення): істинні висловлювання перетворює в помилкові, а хибні - в справжні. Тепер висловлювання "Місяць - супутник Землі і невірно, що Сонце - супутник Землі" - справжнє, "Невірно, що Місяць - супутник Землі або Сонце - супутник Землі" - помилкове.

Ще одна цікава зв'язка "якщо ..., то ..." (імплікація). Розглянемо висловлювання "Якщо Місяць - супутник Землі, то і Сонце - супутник Землі". Здоровий глузд підказує, що це висловлювання хибне, але істинним буде "Якщо Місяць - супутник Землі, то невірно, що Сонце - супутник Землі". Висловлення ж "Якщо Сонце - супутник Землі, то і Місяць - супутник Землі" - справжнє, не дивлячись на гадану абсурдність. І вислів "Якщо Сонце - супутник Землі, то все що завгодно" - теж справжнє. У таких випадках мені подобається висказивaніе "Якщо я - балерина, то Місяць - зелена" або що-небудь подібне.

Перелічити всі можливі комбінації логічних значень двох висловлювань можна за допомогою такої таблиці:

Два висловлювання - 4 рядки в таблиці. Три різних висловлювання - 8 комбінацій, 4 - 16 і т.д. n висловлювань - 2n комбінацій.

abc

1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0

Які символи краще використовувати для позначення логічних зв'язок? Фантазія в цій області безмежна ... :) Важко знайти дві книги, в яких автори дотримувалися б однакових позначень. Проте, деяка логіка :) в цьому є. Але далеко не всі символи можуть бути відтворені в електронному тексті, тому часто вдаються до включення в текст невеликих графічних файлів ...
Зупинимося поки на наступних позначеннях:

• заперечення
• "Невірно що ...», «не ..."
• кон'юнкція
• "... і ..."
• a & b (a, b - Кон'юнктів).
• диз'юнкція
• "... або ..."
• a v b (a, b - диз'юнкт).
• імплікація
• "якщо то ..."
• a => b (a - підстава, b - наслідок).
• еквівалентність (рівнозначність)
• "... тоді і тільки тоді ...", "... якщо і тільки якщо ..."

Зазвичай логічні значення результатів застосування зв'язок записуються в вигляді таблиць (т.зв. таблиці істинності). Але уявлення цих таблиць широко варіюється. Для позначення висловлювань, логічних значень і зв'язок використовують як прописні, так і малі літери. Для позначення істинності і хибності використовують, відповідно, "1" і "0", "І" та "Л", "t" (true) і "f" (false) ... Кому-то зручніше спочатку виписувати "0" , а потім "1", а кому-то - навпаки. Нижче представлені різні способи зображення таблиці істинності на прикладі диз'юнкції. Я віддаю перевагу перший варіант.

або b і і і і л і л і й л л л

Таблиці для зв'язок:

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

Диз'юнкцію "або" часто називають "нестрогой диз'юнкція". А сувору ді'юнкцію "або ..., або ..." позначають символом "v" з точкою зверху або подвійним "v" (перевернуте на 90 градусів проти годинникової стрілки "<<"), ймовірно існують і інші позначення. Відмінність таблиці істинності для суворої диз'юнкції від таблиці істинності для нестрогой диз'юнкції в першому рядку: коли значення а і b істинні, "або а, або b" - помилково.

І кілька корисних формул:

1. ~~ a == a - закон зняття подвійного заперечення
2. a & a == a - закон ідемпотентності
3. a v a == a - закон ідемпотентності
4. a & 0 == 0
5. a & 1 == a
6. a v 0 == a
7. a v 1 == 1
8. a & ~ a == 0 - закон суперечності
9. a v ~ a == 1 - закон виключеного третього
10. ~ (A & b) == ~ a v ~ b - закон де Моргана
11. ~ (A v b) == ~ a & ~ b - закон де Моргана
12. a & b == ~ (~ a v ~ b) - закон де Моргана
13. a v b == ~ (~ a & ~ b) - закон де Моргана
14. a => b == ~ a v b - вираз імплікації через заперечення і диз'юнкцію
15. a <=> b == (a => b) & (b => a)
16. a & (b v a) == a - закон поглинання
17. a v (b & a) == a - закон поглинання
18. a & (~ a v b) == a & b
19. a v (~ a & b) == a v b
20. (A & b) v (a & ~ b) == a - закон склеювання
21. (A v b) & (a v ~ b) == a - закон склеювання

1. a & b == b & a - коммутативность кон'юнкції
2. a v b == b v a - коммутативность диз'юнкції
3. a & (b & c) == (a & b) & c - асоціативність кон'юнкції
4. a v (b v c) == (a v b) v c - асоціативність диз'юнкції
5. a & (b v c) == (a & b) v (a & c) - дистрибутивность кон'юнкції щодо диз'юнкції
6. a v (b & c) == (a v b) & (a v c) - дистрибутивность диз'юнкції відносно кон'юнкції

На своєму досвіді я переконалася, що вводити пропозіціональние зв'язки (на урокаx логіки) припадає вже при розгляді деяких завдань (про лицарів і брехунів) з книги Р.Смалліана "Як же називається ця книга?" (Смалліановскіе завдання я пропонувала на перших уроках). Нагадаю, що лицарі це особистості, які завжди говорять тільки правду, а брехуни, відповідно, завжди брешуть.

Спробуємо розібратися в таких завданнях:

Raymond Smullyan. WHAT IS THE NAME OF THIS BOOK? The Riddle of Dracula and Other Logical Puzzles.

29.
Suppose A says, "Either I am a knave or B is a knight."
What are A and B?

30.
Suppose A says, "Either I am a knave or else two plus two equals five."
What would you conclude?

33.
Suppose A says, "Either I am a knave, but B is not."
What are A and B?

29.
Припустимо, що А каже: "Або я брехун, або У лицар".
Хто з двох персонажів А і В лицар і хто брехун?

30.
Припустимо, що А каже: "Або я брехун, або два плюс два - п'ять".
До якого висновку можна прийти на підставі цього твердження?

33.
Припустимо, що А висловлює твердження: "Я брехун, а В не брехун".
Хто з остров'ян А і В лицар і хто брехун?

29.
Запишемо висловлювання А в символьній формі: {A-л v Bp}. Розглянемо 2 випадки:

• A - лицар: {0 v Bp == 1}, диз'юнкція буде істинної толькоеслі {Bp == 1}, тобто В - лицар.
• A - неправдомовець {1 v Bp == 0}, така диз'юнкція не може битьложной, отже, А - трохи брехун.

Відповідь: А - лицар, В - лицар.

30.
Bисказиваніе А в символьній формі: {A-л v 0}. Розглянемо 2 випадки:

• A - лицар: {0 v 0 == 1}
• A - неправдомовець {1 v 0 == 0}

Обидва вирази невірні. Рішення немає (автор брехун :)).

33.
B цьому випадку: {A-л & Bp}:

• A - лицар: {0 & Bp == 1}, кон'юнкція не може бути істинною, якщо хоча б один з Кон'юнктів хибне висловлювання.
• A - неправдомовець {1 & Bp == 0}, щоб кон'юнкція була помилковою при одному дійсному Кон'юнктів, другий повинен бути хибним, тобто якщо А - брехун, висловлювання "В - лицар" - помилкове.

Відповідь: А і В - брехуни.

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

І ще кілька випадків:

Following are several problem from the island of knights and knaves where knights always tell truth whereas knaves always lie.

1. If anybody on the island says "If I'm a knight then P." then the speaker must be a knight and P is true.
2. A makes the following statement: "If I am a knight then so is B." What are A and B?
3. Someone asks A, "Are you a knight?" He replies, "If I am a knight then I'll eat my hat". Must he eat his hat?
4. A says, "If I am a knight then 2 + 2 = 4." Is A a knave or a knight?
5. A says, "If B is a knight then I am a knave." What are A and B?

Якщо хтось на острові лицарів і брехунів скаже: "Якщо я лицар, то X", цей хтось обов'язково виявиться лицарем, а висловлювання X - істинним. Переконаємося в цьому:

Припустимо, що хтось це А. Запишемо висловлювання {А-р => X}. Якщо А - брехун, то {А-р == 0}. Вираз {0 => X == 0} буде вірним ні при яких значеннях висловлювання X, тому що імплікація з помилковим підставою може бути тільки істинної. А якщо А - лицар, то {А-р == 1} і в виразі {1 => X == 1} значеніe висловлювання X має бути істинним.

Припустимо, A стверджує: "Якщо я лицар, то і B - лицар." Дотримуючись попереднього міркування, можна переконатися, що і A, і B - лицарі.

Якщо ж на питання "Ви лицар?" A відповість: "Якщо я лицар, то я з'їм свого капелюха", то аналогічним чином неважко переконатися в тому, що А все-таки доведеться з'їсти капелюха.

У разі, коли A вимовляє: "Якщо я лицар, то 2 + 2 = 4", A знову буде лицарем.

Набагато цікавіше, якщо А стверджує: "Якщо B лицар, то я брехун." Якщо А - лицар, то {В-р => 0 == 1}; вираз вірний тільки якщо {В-р == 0}, тобто У - брехун. Припустивши, що А - брехун, отримуємо {В-р => 1 == 0}. Це вираження не буде вірним ні за яких значення висловлювання "В - лицар". Отже, А - лицар, а B - брехун.

Сайт управляється системою uCoz