Борисенко О.А. Дискретна математика
Подождите немного. Документ загружается.
Дискретна математика
Продовження таблиці 1.2
Варіант
Діаграма Ейлера
/А /\ /Г\
29
ЗО
Ж
31
32
в
/ Д^/ \
33
41
Борисенко О. А.
Продовження таблиці 1.2
Варіант
Діаграма Ейлера
34
® 35
®
36
©
37
38
&
42
Дискретна математика
43
44
Дискретна математика
Таблиця 1.3. Набори номерів діаграм Ейлера
Варіант
Номери діаграм Ейлера
1
1, 12, 23,34
2 2, 13, 24, 35
3 3, 14, 25, 36
4
4,15,26,37
5
5, 16,27,38
6 6, 17, 28, 39
7 7, 18,29,39
8 8, 19,30,41
9
9, 20,31,42
10
10,21,32,43
11
11,22, 33,44
12 12, 7, 22, 45
13
13,8,23,46
14
14, 9, 24, 47
15
15, 1,25, 30
16 16, 2, 26,31
17 3, 17, 27, 32
18 4, 18,28,33
19 5, 19, 29, 34
20
6, 20, ЗО, 35
21
7,21,31,36
22
8, 22, 32, 37
23 9, 12, 33,38
24
10, 13,34,39
25
1, 10, 20, 40
26 2, 11,21,41
27 3, 12, 22, 42
28
4, 13,46, 43
29
5, 14, 47, 44
30 6, 15, 23,45
45
ЕЛЕМЕНТИ
МА
ТЕМА ТИЧНОЇ ЛОГІКИ
Борисенко О. А.
РОЗДІЛ 1. ЛОГІЧНІ ОПЕРАЦІЇ І ФУНКЦІЇ
Лекція 6
ЧИСЛЕННЯ ВИСЛОВЛЮВАНЬ
1. Висловлювання
У численні висловлювань об'єктом дослідження є
висловлювання (висловлення).
Означення 1. Будь-яке твердження, яке може бути істинним
або хибним, називається висловлюванням.
Істинним висловлюванням приписується значення 1, хибним -
0. З одного або кількох висловлювань можна скласти нові
висловлювання. їх ще називають складеними висловлюваннями. При
цьому окремі висловлювання позначатимемо великими літерами
латинського алфавіту А, В, С, ... .
Приклад 1. Висловлюваннями будуть: А = "Вісім - парне
число"; В = "Вісім ділиться на два"; С = "Вісім ділиться на три";
Д = "Київ - столиця України". З них висловлювання А, В і Д -
істинні, а висловлення С - хибне. Це записується як А = В =
С
=
0, Д= 1.
Приклад 2. Складеним буде висловлення: "Якщо вісім - парне
число, то вісім ділиться на два". Це висловлення істинне, тобто
дорівнює 1.
Для об'єднання простих висловлювань у складені застосовують
логічні операції.
2. Операції над висловлюваннями
1. Логічна операція "Константа нуль'' створює висловлювання,
яке завжди є хибним. Позначається "Р
=
0".
2. Логічна операція "Константа одиниця" створює
висловлювання, яке завжди є істинним. Позначається "Р
=
1".
3. Логічна операція "Змінна А" створює висловлювання Р = А,
яке дорівнює 0 тоді і лише тоді, коли А дорівнює 0, і 1, коли А
дорівнює 1. Читається: "Висловлювання залежить лише від А ".
4. Логічна операція "НІ" створює висловлювання Р = А , яке є
істинним тоді і лише тоді, коли А хибне, і хибне, коли А є істинним.
Читається: "Не А" або "Невірно, що А".
50
Дискретна математика
5. Логічна операція '7" (кон'юнкція, добуток, логічне
множення) створює складене висловлювання Р = А л В (А
•
В, АВ,
А & В), яке є істинним тоді і лише тоді, коли обидва висловлювання А
і В істинні, і хибним, коли хоча б одне з цих висловлювань хибне.
Читається: "А і В".
6. Логічна операція "АБО" (диз'юнкція, сума, логічне
додавання) створює складене висловлювання Р = А V В (А + В, А або
В), яке є хибним тоді і лише годі, коли обидва висловлювання А і В
хибні, і істинним, коли хоча б одне висловлювання А чи В істинне.
Читається: "А або В".
7. Логічна операція "Якщо - то" (імплікація) створює складене
висловлювання Р = А -» В, яке є хибним тоді і лише тоді, коли А
істинне, а В - хибне. Для інших випадків значень, які приймають
висловлювання А і В, воно істинне. Читається: "Якщо А, то В".
8. Логічна операція "Заборона з В" (заперечення імплікації
А -»В) створює складене висловлення Р = А& В = А-*В, яке є
істинним тоді і лише тоді, коли А істинне, а В хибне. Для інших
випадків значень, які приймають висловлювання А і В, воно хибне.
Читається: "Невірно, якщо А, то В".
9. Логічна операція "Заборона з А" (заперечення імплікації
В
—»
А) створює складене висловлювання Р = В А А
=
В -» А, яке є
істинним тоді і лише тоді, коли В істинне, а А хибне. Для інших
випадків значень, які приймають висловлювання А і В, воно хибне.
Читається: "Невірно, якщо В, то А".
10. Логічна операція "Рівнозначність" (еквівалентність)
створює складене висловлювання Р = А ~ В (А = В), яке є істинним
тоді і лише тоді, коли обидва висловлювання А і В істинні або хибні
одночасно. Для інших випадків значень, які приймають
висловлювання А і В, воно хибне. Читається: "А рівнозначне 5".
11. Логічна операція "Нерівнозначність" (сума за модулем два)
створює складене висловлювання Р = А® В (А Ф В) , яке є істинним
тоді і лише тоді, коли одне висловлювання є істинним, а друге -
хибним. Для інших випадків значень, які приймають висловлювання А
і В, воно хибне. Читається: "А нерівнозначне до 5", або "Сума за
модулем 2".
12. Логічна операція "Стрілка Пірса" (функція Вебба, операція
Пірса) створює складене висловлювання Р = А-ІВ = А\/В, яке є
51
Борисенко О. А.
істинним тоді і лише тоді, коли обидва висловлювання А і В хибні
одночасно. Для інших випадків значень, які приймають
висловлювання А і В, воно хибне. Читається: "Ні А, ні В".
13. Логічна операція "Операція Шефера" (Штрих Шефера)
створює складене висловлювання Р
—
А\В = А д В, яке є хибним тоді
і лише тоді, коли обидва висловлювання А і В є істинні одночасно.
Для інших випадків значень, які приймають висловлювання А і В,
воно істинне. Читається: "Невірно, що А і В".
Математика - це жінка, а логіка - її одяг.
М.Клайн
52
Дискретна математика
Лекція 7
ЛОГІЧНІ ФУНКЦІЇ
1. Означення логічної функції
Означення 1. Функція Р від п аргументів (змінних)
Х2,
..., Х
п
,
яка гак само, як і її змінні, може приймати лише два значення - 0 і 1,
називається логічною (двійковою, булевою).
Розглянуті вище логічні операції над висловлюваннями можуть
бути використані для побудови логічних функцій. Ці операції разом з
побудованими з їх допомогою логічними функціями створюють
алгебру логіки. У ній висловлювання в логічних функціях
замінюються логічними змінними, і щодо них виконуються необхідні
для розв'язання тієї чи іншої задачі логічні операції. їх найбільш
уживаний склад був розглянутий у попередній лекції.
2. Набори значень змінних логічної функції
Означення 2. Сукупність а
1;
а
2
, ...,
а„
значень п змінних х\, х
2
,
..., х„ називається набором і позначається а\, а
2
, ..., а„, де а ,• є {0,1},
/=1,2,..., п.
Розмістимо, наприклад, набори для трьох аргументів у вигляді
двійкових чисел у спеціальній таблиці - таблиці наборів. Очевидно,
що їх число дорівнює 8. Зліва в цій таблиці у вигляді номерів
зазначимо десяткові еквіваленти двійкових наборів (див. табл. 2.1). Це
дозволяє досить легко перейти від десяткового запису номеру набору
до його двійкового вигляду.
Таблиця 2.1. Набори значень двійкових змінних
Номер
набору
Х\
*2
х
3
0 0
0
0
1
0 0
1
2
0
1 0
3 0 1 1
4
1 0 0
5 1
0
1
6 1 1 0
7
1 1 1
53