Материал: discrete_mathematics

на базі алгебри висловлень, якщо B набуває значення 1 на всіх тих наборах значень p1, p2, …, pn, на яких усі Ai (i = 1, 2, …, k) набувають значення 1. Формули A1, A2, …, Ak при цьому нази-

вають засновками чи припущеннями.

Те, що B є логічним висновком з A1, A2, …, Ak на базі алгебри висловлень, позначають

A1, A2, …, Ak B B.

Вираз

A1, A2, …, Ak B B

називають твердженням про наслідковість (висновковість), або наслідковісним (висновковісним) твердженням. Можна також уживати термін наслідковість (висновковість1).

Зокрема, якщо k = 1, то формулу

B(p1, p2, …, pn)

називають логічним висновком (логічним наслідком) фор-

мули A1(p1, p2, …, pn) і часто позначають A1 B.

Неважко переконатись, що формула B є логічним висновком із формул A1, A2, …, Ak (тобто A1, A2, ..., Ak B B) тоді й тільки то-

ді, коли формула A1 A2 ... Ak → B є тавтологією.

Приклад 1.16.

1. Довести наслідковісне твердження: a b, ¬ c → ¬ b B c.

Побудуємо таблиці істинності для кожної ізформул, що входятьдо складу твердження (для зручності об'єднаємо ці таблиці до однієї).

1 Терміни введено авторами.

37

Аналізуючи таблиці, маємо, що тільки на наборі (1,1,1) обидва засновки нашого твердження набувають значення 1. На цьому самому наборі висновок також набуває значення 1. Наслідковісне твердження доведено.

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

(а) Якщо Андрій поїде до Харкова, то Віктор поїде до Києва. Андрій поїде в Харків або в Одесу. Якщо Андрій поїде в Одесу, то Ольга залишиться у Львові. Однак Ольга не залишилась у Львові. Отже, Віктор поїде до Києва.

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

► Позначимо елементарні висловлення, з яких складено пер-

ше з міркувань, так: a – Андрій поїде у Харків, b – Віктор поїде в Київ, c – Андрій поїде в Одесу, d – Ольга залишиться у Львові.

Відповідні формули-засновки, що задають логічну структуру цих висловлень, є такими: a → b, a c, c → d, ¬ d. Висновок – b. Отже, задачу зведено до перевірки такої вивідності:

a → b, a c, c → d, ¬ d B b.

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

Аналогічний аналіз зробимо й для другого міркування. У цьому разі маємо такі елементарні висловлення: a – Я допуще-

ний до іспитів, b – Я отримав залік з математичної логіки, c – Я навчився розв'язувати логічні задачі. Відповідні формули-

засновки, що задають логічну структуру висловлень наведеного міркування, є такими: b → a, c → b, ¬c. Висновок – ¬ a.

Побудувавши таблиці істинності, отримаємо, що, наприклад, на наборі (1,0,0) усі засновки нашої вивідності набувають значення 1. Однак на цьому наборі висновок ¬ a набуває значення 0. Отже, наведені логічні міркування некоректні. ◄

38

Неважко переконатись, що мають місце корисні й часто використовувані вивідності

A B B A, A B B B та A B А B, B B А B,

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

A B A, A B B та A А B, B А B.

Множину висловлень

M = {A1(p1, p2, …, pn), A2(p1, p2, …, pn), …, Ak (p1, p2, …, pn)}

називають несуперечною (сумісною), якщо існує такий набір значень для p1, p2, …, pn, на якому кон'юнкція A1 A2 … Ak набуває значення 1 (про висловлення A1, A2, …, Ak тоді кажуть, що вони сумісні). Якщо на всіх наборах значень p1, p2, …, pn кон'юнкція A1 A2 … Ak набуває значення 0, кажуть, що висловлення A1, A2, …, Ak несумісні або множина висловлень M

суперечна.

Приклад 1.17.

1. Визначити, чиє множина висловлень

{a ~ ← b, ← a → ← c, a c, c → b}

несуперечною.

Побудувавши таблицю істинності для формули

(a ~ ← b) (← a → ← c) (a c) (c → b),

отримаємо, що існує набір (1,0,0), на якому ця формула набуває значення 1. Отже, задана множина висловлень несуперечна.

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

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

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

3)Андрій поїде на відпочинок до Одеси тоді, коли складе іспит з дискретної математики.

4)Андрій використає навчальний посібник з дискретної математики й поїде на відпочинок до Одеси.

Позначимо елементарні висловлення, з яких складена задана множина, так: a – Андрій складе іспит з дискретної математики, b – Андрій регулярно виконуватиме домашні завдання, c – Андрій використає навчальний посібник з дискретної математики, d – Андрій поїде на відпочинок до Одеси. Відповідні фор-

мули, що задають логічну структуру наведених висловлень:

39

a ~ b, c → b, a → d, c d.

Неважко підібрати (навіть не будуючи таблиці істинності) набір, на якому всі чотири останні формули набувають значення 1. Таким набором буде (1,1,1,1). Отже, задана множина висловлень несуперечна.

3. Слідчий допитує трьох свідків: А, Б, В. Свідок А стверджує, що Б говорить неправду. Б наполягає на тому, щоб слідчий не вірив показанням В. В каже, що ані А, ані Б не говорять правди. Визначити, хто з трьох свідків говорить правду.

Розглянемо такі елементарні висловлення: a – А говорить правду, b – Б говорить правду, c – В говорить правду. З умов задачі матимемо множину висловлень:

a ~ ¬ b, b ~ ¬ c, c ~ (¬ a ¬ b).

Ця множина несуперечна й усі три висловлення істинні тільки для набору значень (0,1,0). Отже, правду каже лише свідок Б. ◄

Завдання для самостійної роботи

(є) a ¬ c, a → d, b → c, ¬b → d B d;

(ж) a → (b c), d → a B (¬ b ¬ c) → ¬ d.

2.Побудувавши відповідні таблиці істинності, визначити, чи

єправильною така наслідковість:

(ж) a b, a → c, b → c B ¬ c → ¬ a.

3. Розташувати наведені формули в такому порядку, щоб кожна з них була логічним висновком усіх попередніх: 1) ¬ a ~ b; 2) a → (¬ a → b); 3) a ¬ b; 4) ¬ a → b; 5) a ¬ (¬ b a).

40

4. Формули A1, A2, A3, B1, B2 задано таблицями істинності:

Визначити, чи має місце таке наслідковісне твердження:

7.Чи є твердження Студент погано працював протягом семестру, тому не склав іспит з дискретної математики логіч-

ним висновком із твердження Якщо студент добре працюва-

тиме протягом семестру, то він успішно складе іспит з дискретної математики?

8.Нехай задано такий засновок: Якщо студент не знає ма-

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

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

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

41