Комбінаторика
(х, х) є А І.
якщо хру
, то у
х
для
будь - якого
х, у є А, тобто
якщо (х, у) є Р, то
(у, х)
Р для будь-якої
пари (х, у) є А І.
якщо хру і урz, то хрz для будь-яких х, у, z є А, тобто якщо (х, у) є Р і (у, z) є Р, то і (х, z) є Р для будь яких пар (х, у) (у, z) є А І.
Так відношення р: „ х < у у множині А = {1, 2, 3, 4, 5} є відношенням строгого порядку, тому що воно антирефлексивне, антисиметричне, транзитивне.
Відношення р називається відношенням нестрогого (часткового) порядку, якщо воно рефлексивне, антисиметричне і транзитивне.
Так, відношення „число х – дільник числа у” у множині А = {1, 2, 3, 4, 5} є відношенням часткового порядку, тому що воно транзитивне, рефлексивне і антисиметричне.
У математиці та її застосуваннях особливу роль відіграють такі відношення порядку р, які дають можливість порівняти довільні різні елементи певної множини А. Ці відношення називаються відношеннями лінійного порядку у множині А.
Відношення строгого (нестрогого) порядку називається відношенням лінійного строгого (нестрогого) порядку, якщо для будь-яких різних елементів х і у із А здійснюється одне із відношень хру або урх.
Проілюструємо сказане на прикладі. Нехай А – множина студентів групи. Р – відношення „студент х вищий за студента у”. Це відношення антирефлексивне, антисиметричне і транзитивне.
Значить, воно відношення строгого порядку. Якщо в даній множині А немає студентів однакового росту, то тоді про будь-яких двох студентів можна сказати, що або студент х вищий за у або студент у вищий студента х. Отже, відношення Р є відношенням строгого лінійного порядку.
Множина А називається лінійною упорядкованою, якщо в А введено відношення Р і для будь-якої пари (х, у) є А І, якщо х ≠ у, то хру або
урх.
Так, множина натуральних чисел лінійно упорядкована відношенням строгого порядку „менше”, тобто N = {1, 2, 3, 4, ....}
Розділ 3. СИМВОЛІКА МАТЕМАТИЧНОЇ ЛОГІКИ
§ 3. 1. Поняття висловлення
Під математичною логікою або символічною логікою розуміють логіку, що розвивається за допомогою математичних методів. Математичний апарат до логіки вперше застосував у XIX ст. англійський математик Джордж Буль.
Д. Буль (1815 – 1864 р.р.), батько відомої англійської письменниці Войнич (її чоловік був революціонером), автора роману „Овод”. Темп розвитку математичної логіки різко зростає у XIX ст. У 90-х роках ХХ ст.. математична логіка дістає широке застосування в технічних науках, наприклад, електротехніці. Зараз вона є складовою частиною теоретичного фундаменту кібернетики.
Основним поняттям математичної логіки є висловлювання. Висловлювання належить до первинних понять, воно не визначеється через інші поняття, а вводяться за допомогою опису.
Під висловлюванням
розуміють
будь-яке твердження,
відносно якого
можна з’ясувати,
істинне воно
чи хибне. Наприклад,![]()
Діагональ квадрата не сумірна з його стороною – „і” висловлювання
5 > 8 – „х” висловлення
О котрій годині ти повернешся вчора додому? – не є висловленням.
Висловлення позначаються малими латинськими буквами: p, q, r, s, ......
Множину усіх висловлювань, яку позначимо буквою S, ділять на дві підмножини (класи)
Т – клас усіх істинних висловлювань
F – клас усіх хибних висловлювань
Два висловлювання p і q називаються рівносильними (логічно рівними), якщо вони належать до одного й того самого класу і записують
p
q
Із означення рівносильності висловлювань виникають властивості:
р
рЯкщо р
q,
то q
р
– симетричністьЯкщо р
q
і q
r,то
р
r
– транзитивність
§ 3. 2. Операції над висловленнями
У розмовній мові для сполучення двох речень вживають слова: і, або, якщо ...... то, тоді і тільки тоді, не. З’ясуємо те значення, в якому ці слова вживаються в логіці.
а) Логічне множення (кон’юнкція)
Логічним добутком (кон’юнкцією) двох висловлень p і q називається
таке
висловлення
„p
і q”,
яке істинне
тоді і тільки
тоді, коли p
і q
одночасно
істинні. Позначається:
p
q.
Згідно з означенням маємо таку таблицю істинності для кон’юнкції.
-
p
q
p
qi i i i x x x i x x x x
Приклад. Нехай висловлення р буде “5<8”, а висловлення q – “ 8 < 13 “, тоді кон’юнція цих висловлень буде “ I ”, бо істинне p i q .
Переважно скорочено таку кон’юнкцію записують як подвійну нерівність 8 < 5 < 13
Властивості кон’юнкції
1)
Комутативна
(переставна
властивість)
p
q
q
p
-
p
q
p
qq
pі і і і і х х х х і х х х х
х
х
![]()
2) Асоціативна
(сполучна)
властивість
(p
q)
s
p
(q
s)
|
p |
q |
s |
(p
|
(p
|
(q
|
(q
|
| і | і | і | і | і | і | і |
| і | х | х | х | х | х | х |
| х | і | х | х | х | х | х |
| х | х | і | х | х | х | х |
| х | і | і | х | х | і | х |
| і | х | і | х | х | х | х |
| і | і | х | і | х | х | х |
| х | х | х | х | х | х | х |
![]()
![]()
![]()
![]()
Означення кон’юнкції двох висловлювань розповсюдна на будь-яке скінченне число висловлювань
рі
= р1
р2
р3
р4
…
рn
б) Логічне додавання (диз’юнкція)
Диз’юнкцією або логічною сумою двох висловлень p і q називається висловлення “p і q „ яке істинне тоді і тільки тоді, коли істинне хоча б одне із висловлювань і хибне коли вони обидва хибні.
Позначення диз’юнкції: p v q
Таблиця істинності:
-
p
q
p v q
i i i i x і x i і x x x
Закони диз’юнкції
1) Комутативний:
p v
q
q v
p
-
p
q
p v q
q v p
і і і і і х і і х і і і х х
х
х
![]()
2) Асоціативний
закон диз’юнкції
(p
v
q)
v
s
p
v
(q
v
s)
|
p |
q |
s |
p v q |
(p v q) v s |
q v s |
p v (q v s) |
| і | і | і | і | і | і | і |
| і | х | х | і | і | х | і |
| х | і | х | і | і | і | і |
| х | х | і | х | і | і | і |
| х | і | і | і | і | і | і |
| і | х | і | і | і | і | і |
| і | і | і | і | і | і | і |
| х | х | х | х |
|
х |
|
![]()
![]()
3) Дистрибутивні закони, які пов’язують кон’юнкцію і диз’юнкцію
(p
v
q)
s
(p
s)
v
(q
s)
(p
q)
v
s
(p v
s)
(q v
s)
Довести дома самостійно.
в) Заперечення висловлення
Запереченням висловлення р називається висловлення „не р“, яке істинне, коли р хибне, і хибне коли р істинне.
Позначення
:
.
-
р

і х х і
Закони заперечення
1) Заперечення заперечення висловлення рівносильне висловленню р:
![]()
р
2) Закон суперпозиції
p
![]()
![]()
х
-
р

p


і х х х і х
3) Закон включення третього
q
v
i
Кожне
висловлення
q
або істинне
або хибне, третього
не може бути
q
v
=
i
-
q

q v

і х i х і i
4) Закони де Моргана
v
![]()
![]()
![]()
![]()
![]()
Заперечення кон’юнкції двох висловлень рівносильне диз’юнкції заперечень і заперечення диз’юнкції рівносильне кон’юнкції заперечень цих висловлень.
v
![]()
-
р
q
p
q


v

і i i х x x x i x x і x i i x i x i i x i x x x
xx x
x
г) Логічне слідування (імплікація)
Слідуванням
(імплікацією)
двох висловлень
p і
q
називається
висловлення
“якщо p,
то q„,
яке хибне тоді
і тільки тоді,
коли p
– істинне, а q
– хибне. Позначається
імплікація:
p
q
-
p
q
p
qi i i i x x x i і x x i
Операцію імплікації двох висловлень можна виразити через операцію заперечення і диз’юнкцію:
p
q
v
q
-
p
q
p
q
v
qi i i x і i x x x х x i і i і x x i i і
![]()
![]()
![]()
д) Еквіваленція (рівносильність) двох висловлень
Еквіваленцією (рівносильністю) двох висловлень p і q називається висловлення „р тоді, і тільки тоді, коли q, яке істинне тоді і тільки тоді, коли p і q одночасно істинні, або одночасно хибні“
Позначається:
p
q
, p
q
Еквіваленція
(p
q)
(p
q
q
p)
-
p
q
p
q
p
qq
pp
q
q
pi i і i і і i x х x і х x i х і х х x x і i i і
![]()
![]()
![]()
§ 3.3. Предикати
(неозначуване висловлення або висловлювальна форма)
Розглянемо речення
х – парне число
Поет х написав поему “ Сон”.
Ці речення не є висловленням, бо неможна сказати чи вони “і” чи “х“. Якщо змінну в першому реченні замінити числом, а в другому прізвищем поета, то вони перетвореться у висловлення.
Предикатом називається твердження, в яке входять вільні змінні і яке при заміні їх коректними значеннями стає висловленням.
Це є одномісні предикати.
Для кожного предиката треба, вказати множину значень, які може приймати змінна х. Цю множину називають областю визначення предиката і в першому прикладі область визначення – N, у другому - множина прізвищ поетів.
Предикат позначають великими буквами:
P(x),
Q(x),
R(x),
S(x),
де х
Х.
Множина
тих значень
змінних, при
яких предикат
набуває істиного
значення називається
областю
істинності
предиката
і позначається
Т.
Область істиності
є підмножиною
області визначення
Т
Х.
У першому
прикладі Т =
{x
| x
N
i є
парне}
У другому прикладі Т = { Шевченко }
Предикат в який входить дві змінні називаються двомісним. Приклади:
x > y;
“Поет х написа поему у “
Двомісні предикати позначаються P(x, y), Q(x, y) які визначені на множенні Х Ч У.
В математиці зустрічаються багато предикатів, причому деякі з них мають спеціальні позначення
„х = у“;
„х <
у“; „х
║ у“;
„х
у“ і
т.д.
В математиці зустрічається і трьох, чотирьох і т.д. місні предикати. Приклади:
1. Число х ділиться на число у і на число z.
2. Всі числа, які діляться на х і у, діляться і на z.
3. Сума чисел х і у дорівнює добутку чисел U і V.
4. а1х1 + а2х2 + а3х3 + … + аnxn = b n–місний предикат
Нехай Q (a, b) – двомісний предикат.
(a - b)І = аІ – 2ab + bІ. Цей предикат перетворюється на істинне висловлення при всіх дійсних значеннях „a” і „b”. Областю істинності предиката Q є множина всіх дійсних чисел R. Такий предикат називається тотожно істинним.
Рівності, рівняння, нерівності та їх системи, що розглядаються в математиці, з точки зору логіки – предикати.
§ 3. 4. Квантори.
У математиці часто використовують вирази „для всіх”, „для кожного”, „яке б не було”, „існує”, „знайдеться хоча б одне”.
Для позначення
цих виразів
вживаються
символи, які
називаються
кванторами:
квантор загальності
, який позначається
,
у звичайній
мові йому відповідає
вираз „для
кожного”, „для
всякого”, „для
всіх”.
Нехай
Р(х) – „Трикутник
х прямокутний»,
то вираз (
х
є Х)
Р(х) читається:
Будь-який трикутник прямокутний
Кожний трикутник прямокутний
Всі трикутники прямокутні
Усі ці висловлення є хибними. Отже, в результаті квантифікації (приписуванні кватора) предикат перетворюється у висловлення. Цей квантор називається квантором загальності.
Розглянемо
ще квантор
існування, який
позначається
.
У звичайній
мові йому відповідає
вираз: „існує”,
„знайдеться
хоча б одне”.
Нехай Р(х): „х > 5”
Вираз (
х є R)
(х > 5) читається:
Існує дійсне число х таке, що х > 5
знайдеться таке дійсне число х, яке > 5
хоча б одне дійсне число > 5
В результаті квантифікація, навішування квантора на змінну предикат перетворився у висловлення.
Над предметами, так само, як і над множинами можна проводити операції кон’юнкцію, диз’юнкцію, заперечення, імплікацію і еквіваленцію.
§ 3. 5. Поняття про теореми.
Які б ми розділи математики не розглядали скрізь ми зустрічаємось з твердженнями, які називаємо теоремою.
Теорема – це математичне твердження, істинність якого з’ясовується доведенням (міркуванням).
Формулювання будь-якої теореми складається з двох частин: умови і