Материал: discrete_mathematics

(б) Студент знає математичну логіку. Отже, він зможе розв'язати логічну задачу.

(в) Студент не знає математичної логіки. Отже, він не зможе розв'язати логічну задачу.

(г) Студент не розв'язав логічну задачу. Отже, він не знає математичної логіки.

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

(а) Якщо студент не прочитає підручник з математичної логіки, то він не набуде необхідних знань. Однак студент прочитав підручник з логіки. Отже, він набув необхідних знань.

(б) Якщо певний елемент обчислювальної машини має дефект, то машина не працюватиме. Обчислювальна машина не працює, отже, її певний елемент має дефект.

(в) Шахіст N не буде чемпіоном, якщо не виграє цю партію. Однак N виграв цю партію. Отже, N буде чемпіоном.

(г) Якщо всі засновки наслідковості істинні й наслідковість правильна, то висновок – істинний. У цій наслідковості висновок хибний. Отже, або в наслідковості не всі засновки істинні, або вона неправильна.

(д) Для того, щоб скласти іспит з дискретної математики, мені необхідно дістати підручник або конспект. Я дістану підручник тільки в тому разі, якщо мій приятель не поїде додому. Однак він поїде додому тільки тоді, коли я дістану конспект. Отже, я складу іспит з дискретної математики.

10.Записати нижченаведені міркування у вигляді наслідковості (на базі алгебри висловлень) і визначити її коректність.

1)(а) Число ділиться на 9 тільки тоді, коли воно ділиться на

3.(б) Це число не ділиться на 9. Отже, воно не ділиться й на 3.

2)(а) Для того щоб число 2007 було простим, необхідно, щоб 2007 не було кратне 6. (б) 2007 кратне 6 тільки тоді, коли 2007 кратне 2. (в) 2007 не кратне 2. Отже, 2007 – просте число.

3)(а) Якщо в розкладі занять на сьогодні є лекція з алгебри, то немає лекції з дискретної математики. (б) Заняття з французької мови є тільки тоді, коли є практикум із програмування. (в) Немає лекції з математичного аналізу, якщо немає заняття з французької мови. (г) Лекція з алгебри є в розкладі занять на

42

сьогодні. Отже, у розкладі занять на сьогодні немає лекції з математичногоаналізу.

4)(а) Будь-який дріб – раціональне число. (б) Кожне ціле число є раціональним. Отже, кожне ціле число – дріб.

5)(а) Будь-який дріб – раціональне число. (б) Кожне ціле число є раціональним. Отже, будь-який дріб – ціле число.

11. Визначити, чи є задана множина висловлень несупе-

(з) {a ~ ¬ b, ¬ a → ¬ c, a c, c → b}.

12. Перевірити, чи є несуперечною множина висловлень:

1)Дмитро успішно складе іспит із дискретної математики тоді й тільки тоді, коли регулярно виконуватиме домашні завдання.

2)Якщо Дмитро раціонально організує свій робочий час, то він регулярно виконуватиме домашні завдання.

3)Дмитро поїде на екскурсію до Львова тоді, коли успішно складе іспит з дискретної математики.

4)Дмитро раціонально організує свій робочий час і поїде на екскурсію до Львова.

13. Визначити коректність логічного висновку в міркуванні

Крадіжку могли здійснити або А, або Б, або В. Однак крадіжку здійснив А. Отже, крадіжку не здійснили ні Б, ні В.

14.Перевірте формальними методами правильність таких логічних міркувань поліцейського детектива: Якщо Джон не зу-

стрічав у цю ніч Сміта, то або Сміт – убивця, або Джон бреше. Якщо Сміт – убивця, то Джон не зустрічав Сміта в цю ніч,

івбивство відбулося після опівночі. Якщо вбивство відбулося після опівночі, то або Сміт – убивця, або Джон бреше. Отже, Сміт – убивця.

15.Шість студентів А, Б, В, Г, Д, Е купили по лотерейному квитку. Після розіграшу виявилось, що два з них виграли. На запитання, хто саме виграв, студенти дали такі відповіді: А: ви-

грали я та Д; Б: виграли я та Е; В: виграли А та Е; Г: виграли Г

43

та Б; Д: "виграли Е та Д. У чотирьох із відповідей лише одна частина твердження правильна, а в одній – обидві неправильні. Чиї лотерейні білети виграли?

16.Хтось із трьох студентів А, Б, В розбив вікно. А сказав, що він і Б вікно не розбивали; Б сказав, що А цього не робив, а розбив вікно В; В сказав, що він також не розбивав, а це зробив А. Як пізніше виявилось, один зі студентів двічі сказав неправду, інший – двічі сказав правду, а серед тверджень третього одне правильне, а інше – ні. Хто розбив вікно?

17.Троє обвинувачуваних А, Б, В дають свідчення. А: Б ви-

нен, а В – ні; Б: Якщо А винен, то В – теж; В: Я не винен, але хоч один із двох інших – винен.

(а) Вважаючи, що Б та В кажуть правду, установити, хто саме винен.

(б) Якщо всі троє невинні, то хто з них сказав правду, а хто – неправду?

1.6. Секвенції і секвенційні форми для логіки висловлень

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

Ідея секвенційних методів дуже проста. Розглянемо наслідкове твердження A1, A2, …, Ak B B. За означенням воно буде іс-

тинним тоді й тільки тоді, коли для всіх значень пропозиційних змінних з істинності A1, A2, …, Ak випливає істинність B.

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

44

що A1, A2, …, Ak є істинними, а B – хибним. Якщо в процесі перетворень дійдемо суперечності, тобто отримаємо формулу, що є одночасно істинною та хибною, то наше припущення буде спростовано. Отже, наслідкове твердження – істинне.

Ідея пошуку суперечності покладена в основу секвенційного методу. Розглянемо загальніший вигляд наслідкового твердження: A1, A2, …, Ak B1, B2, …, Bm. Для секвенційних методів такі твердження записуються як

A1, A2, …, Ak → B1, B2, …, Bm

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

Для роз'яснення секвенційного методу розглянемо простий приклад, а саме: доведемо істинність наслідкового твердження

←(A B) B←A ←B.

Припустимо, що це твердження є неправильним, тобто існує такий набір значень пропозиційних змінних, що формула ←(A B) є істинною, а формула ← A ← B – хибною. Ці припу-

щення записуватимемо у вигляді

1← (A B), 0 ← A ← B,

тобто істинні формули проіндексуємо (розмітимо) знаком 1, а хибні – знаком 0. Отримаємо дві індексовані формули, які утво-

рюють розмічену секвенцію.

Далі спробуємо спростити формули цієї секвенції. Головною операцією першої формули є заперечення. Тому ←(A B) буде

істиною тоді й тільки тоді, коли A B буде хибою. Таким чином, початкова секвенція перетворена на нову секвенцію

0 A B, 0 ← A ← B.

Далі спрощуватимемо формулу A B, яка має бути хибною. Го-

ловною операцією цієї формули є диз'юнкція.

Диз'юнкція буде хибною тоді й тільки тоді, коли її аргументи будуть одночасно хибними. У нашому випадку аргументами ди- з'юнкції є А та В. Тому індексовану формулу 0 A B можна замі-

нити на дві індексовані формули 0 А та 0 В. Тим самим секвенція

0 A B, 0 ← A ← B

45

перетворилась на нову секвенцію

0 A, 0 B, 0 ← A ← B.

В останній секвенції є лише одна складена (неатомарна) формула

0 ← A ← B,

яка свідчить, що формула ← A ← B має бути хибною.

Кон'юнкція набуває значення хиби у трьох випадках (див.

табл. 1.2):

1)коли перший і другий аргументи кон'юнкції є хибними;

2)коли перший аргумент є хибою, а другий – істиною;

3)коли перший аргумент є істиною, а другий – хибою. Ці три випадки можна замінити двома спрощеними випадками:

1)перший аргумент кон'юнкції є хибою;

2)другий аргумент кон'юнкції є хибою.

Тому далі для кон'юнкції (як і для диз'юнкції) розглядатимемо лише по два випадки.

Отже, формула ← A ← B будехибною тоді й тільки тоді, коли:

1)← A – хибне або

2)←B – хибне.

Це означає, що секвенція

0 A, 0 B, 0 ← A ← B

перетворилась на дві секвенції:

0 A, 0 B, 0 ← A та 0 A, 0 B, 0 ← B.

У першій із них неатомарною є формула 0 ←A, яку заміняємо на 1 A. Отримано секвенцію

0 A, 0 B, 1 A.

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

Тепер проаналізуємо другу секвенцію

0 A, 0 B, 0 ← B.

Перетворюючи 0 ← B на 1 В, отримуємо секвенцію

0A, 0 B, 1 В.

Уцій секвенції суперечність виникає для формули B . Отже, і ця

секвенція не може спростувати початкове наслідкове твердження.

46