У цій роботі ми розглянемо як інструмент для визначення істинності тверджень. Потім ми розглянемо розширення числення висловлювань до числення предикатів. Це розширення дозволить нам будувати міркування над цілою низкою конструкцій таких, як цикли. Ми також розглянемо ідеї еквівалентності, общезначимости або тавтології для доказу.
Початок обчислення висловлювань було покладено роботами Джоржа Буля. Помітивши схожість у властивостях логічних операцій ОR і AND з властивостями арифметичних операцій множення і додавання, він створив числення для обчислення істинності тверджень подібно до того, як правила арифметичних операцій дозволяють обчислювати значення арифметичних виразів. У створеному ним обчисленні Буль позначив символами як окремі твердження, так і цілі конструкції з тверджень.
Будь-яке висловлювання в цьому обчисленні може мати одне з двох значень: істина (true) або брехня (false). Нижче наведені приклади тверджень:
Сума двох сторін трикутника більше або дорівнює третій стороні цього трикутника.
2х2 = 4.
"Кожен мисливець бажає знати, де сидять фазани" (перші букви слів у цій фразі визначають порядок кольорів у спектрі зліва направо).
Для того, щоб суворо визначити спосіб запису подібних тверджень Буль запропонував поняття висловлювання.
У таблиці 5.1. перераховано назви та позначення всіх логічних операцій, що використовуються у висловлюваннях.
Таблиця 5.1.
| Ø | NOT | заперечення |
| Ú | OR | диз'юнкція |
| Ù | AND | конь'юнкція |
| Þ | імплікація | |
| Û | тотожність |
Визначення 5.1. Висловлення - вираз, побудоване за такими правилами:
true і false - висловлювання;
Будь-яка змінна типу {true, false} - висловлювання (такий тип називають boolean);
Якщо р - висловлювання, то (Øр) - висловлювання;
Якщо p і q - висловлювання, то (pÚq), (pÙq), (pÞq), (pÛq) - висловлення.
Зверніть увагу на спосіб визначення висловлювання, а саме, на пункти 3 і 4 визначення 5.1. Ці пункти визначають висловлювання через вже існуючі висловлювання. З таким прийомом, коли визначається поняття визначають, використовуючи саме це поняття, ми зустрінемося ще не раз. Цей прийом називається рекурсією.
Може виникнути побоювання "порочного кола" в такому визначенні. Однак, на підставі пунктів 1 і 2, де поняття висловлювання визначається через поняття логічного значення і змінної логічного типу, "зациклення" не відбувається.
Приклади 5.1.
Нехай p, q і r - змінні типу boolean.
Тоді наведені нижче вирази - це висловлювання:
| 1. | p | 6. | (PÚq) |
| 2. | q | 7. | (PÙq) |
| 3. | false | 8. | (PÞq) |
| 4. | (Øр) | 9. | (PÚ (rÙq)) |
| 5. | true | 10. | (PÞ (qÙ (rÛp)) |
Те, що вирази 1,2,3,4,5 - висловлювання, випливає з пунктів 1,2,3 визначення 5.1. Для виразів 9,10 - це випливає з пунктів 2 і 4. Для виразів 9, 10 - це випливає з пункту 2 і послідовного застосування пункту 4 визначення.
Наприклад:
(PÞ (qÙ (rÛp))
rÞp - висловлювання за пунктом 4. Позначимо його s1.
(QÙs1) - висловлювання знову за пунктом 4. Позначимо його s2.
(PÞs2) - вислів з того ж самого пункту 4.
Приклад 5.2. Нижче наведені вирази не є висловленнями.
(Pq)
(Pq) Øр
Вираз 1 не є таким, тому що імена двох змінних стоять поруч і не розділені знаком логічної операції.
Вираз 2 не є висловлюванням, по-перше, тому, що (pq) - не висловлювання, по-друге, тому, що вираз sØр, - де s і p - висловлювання, не задовольняє ні одному з 4-х пунктів визначення 5.1.
Особливу увагу слід звернути на дужки. Їх можна опускати якщо це не вносить неоднозначності. Наприклад, замість (Øр) можна писати Øр, а замість (pÚq) - pÚq. Однак, неуважне поводження з дужками може призвести до неоднозначності. Наприклад, вираз pÚqÙr можна трактувати або як ((pÚ) qÙr), або (pÚ (qÙr)). Для того, щоб уникнути такої неоднозначності, п'яти логічним операціям приписується пріоритет, який враховується при обчисленні значення виразу. Операція заперечення Ø - має найвищий пріоритет, за нею йде Ù, потім слід Ú, Þ і Û в тому порядку як вони вказані. Тому, вираз pÚqÙr повинно трактуватися лише як (pÚ (qÙr)).
5.1.1. Твердження російською мовою у формі висловлювань.
Не будь-пропозиція російською мовою може бути виражено у вигляді висловлювання. Наприклад, запрошення типу "Увійдіть", команди типу "Стій", "Сидіти", питання типу "Ти був сьогодні на лекції Смілянського?" Не можна уявити у вигляді висловлювань. Тим не менш, існує значна безліч пропозицій, званих твердженнями, які можна представити у вигляді яких висловлювань, або предикатів (про останні ми поговоримо пізніше).
На будь-якому природному мовою, яким є російська мова, одну і ту ж думку можна висловити по-різному. Використовуючи висловлювання, ми будемо втрачати багато смислові відтінки фрази російською мовою, але основна думка буде збережена. Це висловлювання буде одним і тим же для багатьох фраз російською мовою.
Наприклад, якщо позначити твердження "Вася задоволений" буквою р, то висловом Øр можна представити наступне твердження:
"Вася не задоволений".
"Це не той випадок, коли Вася задоволений".
"Вася буде не задоволений".
"Вася був не задоволений".
Зверніть увагу, обчислення висловлювань не охоплює часовий аспект фрази. Аналогічно, наведені нижче твердження можна записати у вигляді висловлювання pÙq, надавши належні значення змінним p і q:
10 £ x £ 100
Петя племінник Васі.
Вася дядько Петра.
Хоча декабристи викривали рабовласництво, багато з них мали кріпаків.
Перше з цих пропозицій складається з двох фраз: "Число х більше або дорівнює 10" і "Число х менше або дорівнює 100". Однак, ці фрази "заховані" за допомогою математичних позначень.
Друга і третя фрази містять в неявному вигляді два твердження. Перше: У Васі є або брат, чи сестра. Друга: У цього брата або біля цієї сестри є син Петя.
Слово "хоча" в четвертій фразі грає роль союзу "і" і виконує роль протиставлення.
При використанні логічної операції Ú у висловлюваннях можуть виникнути труднощі, пов'язані з неоднозначністю союзу "або" в російській мові. Коли мати говорить синові: "Я куплю тобі цукерку або жуйку", як правило, вона має на увазі тільки одне з двох. Коли викладач говорить, що він допустить до іспиту тільки тих студентів хто здасть реферат чи залік, то, звичайно, він не прожене студента, який здасть і залік і реферат.
Перший випадок називається виключає Ú, другий - включає. У численні висловів зазвичай використовується включає Ú.
У висловлюванні pÞq, р називається причиною, q - наслідком, а саме висловлювання - імплікацією або проходженням. Прикладом імплікації може служити фраза
"Якщо ти будеш читати по одній сторінці в день, то ти навчишся читати".
Якщо позначити слова "ти будеш читати хоча б по одній сторінці в день" як p, а "ти навчишся читати", як q, то цю фразу можна записати як
pÞq
Це ж вислів буде відповідати і фразою
"Ти навчишся читати, якщо ти будеш читати хоча б по одній сторінці в день".
Однак, у використанні "якщо" в російській мові є тонкощі. Наприклад, розглянемо фрази:
"Я куплю квиток, якщо в цьому кінотеатрі йде" Анаконда ".
"Я куплю квиток, тільки якщо в цьому кінотеатрі йде" Анаконда ".
Якщо позначити буквою p слова "Я куплю квиток", а буквою s - "у цьому кінотеатрі йде" Анаконда ", то першою фразою буде відповідати вираз
s Þ p,
оскільки не ясно, що буде робити мовець, якщо в кінотеатрі йде "Термінатор".
Другий фразою відповідає вираз
p Þ s
тому що вона стверджує, що я можу купити квиток тільки за однієї умови - в кінотеатрі йде "Анаконда".
Іншою важливою властивістю імплікації є те, що між p і q насправді не передбачається жодного причинно-наслідкового зв'язку.
Наприклад, фразі
"Якщо 1 +1 = 2, то Сонце - центр Сонячної системи"
відповідає вираз
pÞq
Однак, зрозуміло, що між двома фактами "1 +1 = 2" і "Сонце - центр Сонячної системи" немає зв'язку. Таким чином, причинно-наслідковий зв'язок - ще один приклад, виразність в природній мові і не охоплюється в обчисленні висловлювань.
Вираз pÛq використовується, коли один вислів імплікує інше і навпаки. Наприклад, якщо АВС - трикутник зі сторонами а, b, c, то a2 + b2 = c2 тоді і тільки тоді, коли АВС - прямокутний.
Якщо позначити p - a2 + b2 = c2, q - АВС - прямокутний, то вся фраза може бути записана як
pÛq,
тобто pÞq і qÞ p істинні одночасно.
Обчислення істинності висловлювань.
У розділі 1 ми вже стикалися з поняттям стану набору змінних.
Визначення 5.2. Нехай p1 ... .... pn - набір всіх змінних типу boolean, що зустрічаються в деякому висловлюванні. Тоді безліч конкретних значень цих мінно називається їх станом.
Розглянемо вираз pÚq. Набір його змінних {p, q}. Оскільки кожна із змінних може приймати тільки одне з двох значень true, або false, то все безліч можливих станів для цього набору складається з 4-х пар:
(T, T), (T, F), (F, T), (F, F).
(Скрізь далі ми будемо використовувати в цій главі скорочення Т замість true, F замість false). Тепер для кожного стану достатньо вказати значення цього виразу і функція pÚq буде визначена. Це робиться за допомогою, так званих, таблиць істинності. Нижче показано таблиця істинності для pÚq (Таблиця 5.2.).
Таблиця 5.2.
Таблиця істинності для pÚq
| p | q | pÚq |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
За цією таблицею добре видно, що в обчисленні висловлювань використовується саме включає Ú. Оскільки всі вираз істинний коли тільки p - істинно, або тільки q - істинно, або і p і q - обидва істинними.
У таблиці 5.3. наведені таблиці істинності для всіх операцій обчислення висловлювань.
Таблиця 5.3.
Таблиця істинності для а) - заперечення, б) - кон'юнкції,
в) - імплікації, г) - еквівалентності.
| a) | б) | в) | г) | ||||
| p | Øр | pq | pÙq | pq | pÞq | pq | pÛq |
| T | F | TT TF | T F | TT TF | T F | TT TF | T F |
| F | T | FT FF | F F | FT FF | T T | FT FF | F T |
Слід прокоментувати таблицю істинності для імплікації в стані p = F, q = T. Згадаймо наш приклад,
якщо
Це висловлювання не містить твердження, що якщо "Анаконда" не йде в цьому кінотеатрі, то я не куплю квиток. Таким чином, навіть якщо p = F, тобто "Анаконда" не йде в цьому кінотеатрі, я можу купити квиток.
Таблиця істинності може бути побудована для висловлення будь-якої складності. Наприклад, розглянемо вираз
(PÚq) Þ Øp
Побудуємо спочатку таблицю істинності для (pÚq), позначивши цей вираз через s, потім побудуємо таблицю істинності для Øp, позначивши цей вираз через r, і, нарешті, побудуємо таблицю істинності для s Þ r. У таблиці 5.4. показаний цей процес.
Таблиця 5.4.
Таблиця істинності для виразу (pÚq) Þ Øp.
| p | q | s = pÚq | r = Øp | s Þ r |
| T | T | T | F | F |
| T | F | T | F | F |
| F | T | T | T | T |
| F | F | F | T | T |
Неважко бачити, що кількість рядків у таблиці істинності росте як ступінь 2 від числа змінних у виразі. Один із способів скорочувати число рядків - опускати ті стани, які не впливають на результат. Наприклад, у виразі pÚq, якщо p = T, то не важливо, яке значення у q, - значення всього виразу буде T. У таблиці 5.5. показано застосування цього прийому.
Таблиця 5.5.
Обчислення значення виразу (pÙq) Þ (rÚ (pÞS)),
не використовуючи незначні стану.
| p | q | r | s | (PÙq) | Þ | (RÚ | (PÞs)) |
| F | - | - | - | F | T | - | - |
| - | F | - | - | F | T | - | - |
| T | T | T | - | T | T | T | - |
| T | T | F | T | T | T | T | T |
| T | T | F | F | T | F | F | F |
Неважко бачити, обчислення "в лоб" таблиці істинності для цього виразу зажадало б таблиці з 24 = 16 рядків. Використовуючи прийом незначущих станів, вдається скоротити число розглянутих станів до 5.
Тавтологія.
Висловлювання, які істинні при будь-якому стані своїх змінних, відіграють особливу роль і називаються загальнозначущими або тавтологія.
Визначення 5.2. Тавтологія - висловлювання, значення якого - Т на будь-якому стані змінних цього виразу. Протиріччя - вислів, значення якого - F, на будь-якому стані змінних цього виразу.
Для доказу твердження, що деякий вираз - тавтологія, у нас поки що є лише таблиці істинності. Доведемо, що pÚØp - тавтологія. Нижче показано таблиця істинності для pÚØp (Таблиця 5.6.)
Таблиця 5.6.
Таблиця істинності для pÚØp
| p | Øp | pÚØp |
| T | F | T |
| F | T | T |
Ця таблиця підтверджує наше інтуїтивне уявлення про те, що утвердження і його заперечення не можуть бути істинними одночасно. Ця тавтологія в обчисленні висловлювань називається законом виключення третього.
Міркування за допомогою обчислення висловлювань.
Перш за все, треба забезпечити спосіб порівняння двох висловлювань на еквівалентність, для того, щоб, при необхідності, замінювати одне одним. Так само, нам буде потрібно техніка для виявлення тавтологію, більш потужна, ніж таблиця істинності. І, нарешті, ми розглянемо методи міркувань, які можуть бути корисні для вирішення логічних проблем, сформульованих на природній мові. Все це нам потрібно для аналізу різних властивостей як алгоритмів, так і програм на мові програмування Pascal.
Еквівалентність.
Розглянемо висловлювання
(PÚq) Ù (pÚØq).
Його таблиця істинності представлена в таблиці 5.7.
Таблиця 5.7.
Таблиця істинності для (pÚq) Ù (pÚØq)
| p | q | (PÚq) Ù (pÚØq) |
| T | T | T |
| T | F | T |
| F | T | F |
| F | F | F |
неважко помітити, що останній рядок в цій таблиці збігається зі стовпцем для p. Тому, можна сказати, що з цієї точки зору вираз (pÚq) Ù (pÚØq) еквівалентно p, і скрізь, де ми зустрінемо цей вислів, ми можемо його замінити на p.
Як ми вже відзначали, однією з наших турбот є спрощення складних висловлювань. Тому, для спрощення виразів, ми визначимо, що означає для двох виразів бути еквівалентними і замінимо більш складне на менш складне.
Визначення 5.3. Два висловлювання називаються еквівалентними, якщо вони на одних і тих же станах своїх змінних приймають одні і ті ж значення.
Іншими словами, якщо ці висловлювання мають однакові таблиці істинності, то вони еквівалентні. Таким чином, один спосіб встановити еквівалентність двох висловлювань - обчислити їх таблиці істинності і порівняти. Ми, однак, скористаємося іншим способом.
Теорема 5.1. Два висловлювання p і q - еквівалентні (позначається p º q) тоді і тільки тоді, коли pÛq - загальнозначуще.
Нехай p º q. Значить таблиці істинності для p та q збігаються. Отже, на тих станах, де p = Т, q = Т також, а де p = F, то й q = F. Звідси випливає, що pÛq завжди Т (оскільки ми маємо або ТÛТ, або FÛF), тобто pÛq - загальнозначуще або тавтологія.
Нехай pÛq-загальнозначуще. Тоді якщо p = Т, то q повинно бути Т, а якщо p = F, то й q повинно бути F.
Таким чином, на одних і тих же станах ці вирази приймають однакові значення. Отже, таблиці істинності для p та q збігаються. Останнє означає за визначенням, що p º q.
(Доказ закінчено.)
Ця теорема показує, що встановити еквівалентність можна, довівши общезначімость спеціального висловлювання.
Властивості еквівалентності.
Основні, часто використовувані властивості еквівалентності наведені в таблиці 5.8.
Таблиця 5.8.
Властивості еквівалентності
| I. | Комутативність | II. | Асоціативність |