Материал: discrete_mathematics

–висловлення 24 кратне 6 є достатньою умовою для вислов-

лення 24 кратне 3;

–24 кратне 3 тоді, коли 24 кратне 6;

–24 кратне 6 тільки тоді, коли 24 кратне 3.

Для пункту (б) маємо:

–висловлення 45 кратне 3 і 45 кратне 5 є необхідною умовою для висловлення 45 кратне 15;

–висловлення 45 кратне 15 є достатньою умовою для вислов-

лення 45 кратне 3 і 45 кратне 5;

–45 кратне 3 і 45 кратне 5 тоді, коли 45 кратне 15. ◄

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

1.Чи є наведений вираз простим висловленням? Якщо вираз

євисловленням, то вказати, яким саме – істинним чи хибним.

(а) Число 434 кратне 7.

(б) Астрономічний рік складається із 365 днів. (в) Осінь – це пора року.

(г) Осінь – найкраща пора року. (д) Київ – столиця України. (е) 7 < 7. (є) 7 ≤ 7.

(є) 2 × 2 = 4.

(ж) Існує опуклий многокутник із чотирма гострими кутами. (з) Бісектриса трикутника ділить його площу на рівновеликі

частини.

(и) Це речення розташовано на сторінці з парним номером. (і) Усі слова цього речення містять принаймні одну голосну

літеру.

(ї) Нехай усе буде гаразд. (й) Ця задача нескладна.

(к) Число 777 менше Евересту.

(л) Справджується нерівність x < 2.

2. Нехай задано елементарні висловлення:

a – 5 – ціле число; b – 11 – парне число; c – 12 – просте число; d – Число 18 кратне 3.

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

12

3. Визначити істинність чи хибність складеного висловлення, використавши його логічну структуру й виходячи із відомих значень істинності елементарних висловлень, з яких воно складається.

(а) Число 333 кратне 3, але не кратне 11. (б) Число 54 кратне 6 або 8.

(в) Принаймні одне із чисел 11, 23 або 26 парне. (г) –3 > –4 та (–1/3) > (–1/4).

(д) –3 > –4, але (–3)2 < (–4)2. (е) Якщо 4 < 5, то 42 < 52.

(є) Якщо число 36 кратне 6, то число 36 кратне 3. (ж) Якщо число 15 кратне 6, то число 15 кратне 3. (з) Якщо число 15 кратне 3, то число 15 кратне 6. (и) Якщо 3 < 4 та 4 < 2, то 3 < 2.

(і) 72 кратне 48 тоді й тільки тоді, коли 72 кратне 8 та 72 кратне 6.

(ї) Неправильно, що 2 < 3 і 4 < 3. Неправильно, що принаймні одне із чисел 35, 57, 77 просте.

(й) Неправильно, що виконується хоч б одна з нерівностей

2 < 3 чи 3 < 2.

(к) 144 кратне 24 тоді й тільки тоді, коли 144 кратне 8 та 144 кратне 3.

4. Сформулювати наведене твердження у вигляді Якщо …,

то …:

(а) Із нерівності x < 3 випливає нерівність x ≤ 3.

(б) Я успішно складу іспит з математичної логіки тоді, коли регулярно робитиму домашні завдання.

(в) Необхідно знати означення понять, щоб правильно зрозуміти формулювання математичної задачі.

(г) Щоб чотирикутник був ромбом, достатньо, щоб він був квадратом.

(д) Число 24 кратне 6 тільки тоді, коли воно кратне 3.

5. Записати словами у вигляді твердження імплікацію чотирма різними способами, використовуючи вирази: необхідна умо-

ва; достатня умова; тоді, коли, тільки тоді, коли:

13

(а) (2 > 3) → (1 > 2); (б) (42 кратне 21) → (42 кратне 7); (в) (2 > 3) → (1 > 2);

(г) Якщо 3 > 2, то 3 ≥ 2. (д) Якщо 4 < 5, то 42 < 52.

(е) Якщо 3 < 4 і 4 < 2, то 3 < 2.

6. Із хибної нерівності 1 > 2, застосовуючи відомі рівносильні перетворення математичних виразів, вивести:

(а) хибну нерівність 5 > 7; (б) правильну нерівність 5 < 7.

1.2. Формули алгебри висловлень. Таблиця істинності. Тавтології

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

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

Алфавіт найбільш поширеної формальної мови алгебри висловлень складається з трьох груп символів:

1)символи елементарних висловлень і пропозиційних змінних: a, b, c, … та x, y, z, … (інколи з індексами);

2)символи операцій: , , ¬, →, ~ ;

3)допоміжні символи – круглі дужки: (і).

Із символів цього алфавіту будують пропозиційні формули або просто формули алгебри висловлень за індуктивним правилом:

1) усі пропозиційні змінні та елементарні висловлення є формулами;

14

2)якщо A та B – формули, то вирази (A B), (A B), (¬ A), (A → B), (A ~ B) також є формулами (для всіх цих виразів формули A та B є підформулами);

3)інших формул, крім тих, що побудовані за правилами 1) та 2), немає.

Формули алгебри висловлень позначатимемо великими латинськими літерами.

Приклад 1.5.

1. Визначити, чи є послідовність символів формулою алгебри висловлень.

(а) (((x → y) z) ~ ((¬ x) → (y z)));

(б) (((¬ x) y) → (x ~ ((¬ y) x).

► Для цього за допомогою індексів спочатку занумеруємо порядок виконання операцій у першій послідовності символів (у багатьох випадках ця процедура виконується неоднозначно). Ма-

тимемо такий вираз: (((x →1 y) 2 z) ~6 ((¬3x) →5 (y 4 z))) (зручно відповідний номер записувати над операцією). Подамо його у

вигляді (F1 ~6 F2), де F1 = ((x →1 y) 2 z) і F2 = ((¬ 3x) →5 (y 4 z)).

У свою чергу, формула F1 має вигляд (F11 2 F12) і розкладається на підформули F11 = (x →1 y) і F12 = z, а формула F2 має вигляд (F21 →5 F22) і розкладається на підформули F21 = (¬ 3x) і

F22 = (y 4 z).

Вираз F12 є формулою згідно з п. 1) в означенні пропозиційної формули. А кожна з решти підформул F11, F21 та F22 утворюється відповідно до п. 2) цього означення:

F11 = (F111 →1 F112),

Отже, ми продемонстрували, що ця формула побудована із пропозиційних змінних

F12 = z, F111 = x, F112 = y, F211 = x, F221 = y, F222 = z

за викладеними вище правилами.

При спробі аналогічно розкласти другу послідовність символів на певному кроці отримаємо вираз (F1 ~ F2, який не має за-

15

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

2. Виписати всі підформули формули:

(((x → y) z) ~ ((¬x) → (y z))).

► Скориставшись процедурою, що описана в попередньому

пункті, дістанемо, що F1, F2, F11, F12, F21, F22, F111, F112, F211, F221,

F222 – це всі підформули даної формули. ◄

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

Нехай p1, p2, …, pn – це всі пропозиційні змінні, що входять до формули A; позначатимемо цей факт A(p1, p2, …, pn). Формулі A(p1, p2, …, pn) поставимо у відповідність функцію f(p1, p2, …, pn), що означена на множині впорядкованих наборів (p1, p2, …, pn), де кожне pi набуває значення у множині B = {0, 1}, і значенням функції f є 0 або 1. Значення функції f на наборі значень a1, a2, …, an її змінних p1, p2, …, pn дорівнює значенню формули A(p1, p2, …, pn) при підстановці до неї замість пропозиційних змінних p1, p2, …, pn значень a1, a2, …, an, відповідно. Зауважимо, що кількість елементів в області визначення функції f дорівнює 2n.

Приклад1.6. Обчислити значення формули алгебри висловлень

(((a → (¬ b)) → (b ((¬ c) → a))) ~ (¬ a))

на наборі (1,1,0) значень її змінних, тобто за умови, що a = 1, b = 1, c = 0.

16