Основні поняття теорії множин сторінка 7

42
Перевірити, чи є один з предикатів наслідком іншого.
Розв’язок.
З таблиць значень видно, що
   


   


2 1
,
|
,
1
,
|
,
1
x y
f
x y
x y
f x y
 

Отже, предикат f
1
є логічним наслідком предиката f
2
4.2. Квантори
Нехай f(x) — одномісний предикат, визначений на множині А.
Універсальним висловлюванням,яке відповідає предикату f(x), називається вислов- лювання "усі елементи множини А задовольняють предикат f(x)", яке є істинним тоді і тільки тоді, коли предикат f(x)є тотожно істинним. Універсальне висловлювання позна- чається
 
x f x

і читається для всіх a
A

f(a) є істинним. Знак

називається кван-
тором загальності.
Екзистенціальним висловлюванням,яке відповідає предикату f(x), називається ви- словлювання "хоча б один елемент множини А задовольняє предикат f(x)" яке є хибним тоді і тільки тоді, коли предикат f(x)є тотожно фальшивим. Універсальне висловлювання позначається
 
x f x

і читається існує таке a
A

, що f(a) є істинним. Знак

називається
квантором існування.
Квантори впливають на предикати, які розташовані безпосередньо за операцією
квантифікації.
Приклад 4.7. Нехай значення предикатів
1 2
3
,
,
f f
f вказані у наступній таблиці:
Тоді
 
 
1 1
1,
1
x f x
x f x

 

,
 
 
2 2
0,
1
x f
x
x f
x




,
 
 
3 3
0,
0
x f
x
x f
x




Якщо предикат f(x) визначений на скінченій множині


1 2
,
,
,
m
A
a a
a

, то операції
квантифікації (навішування кванторів) можна записати наступним чином:
 
 
 
 
1 2
m
x f x
f a
f a
f a



 
,
 
 
 
 
1 2
m
x f x
f a
f a
f a



 
Після виконання операції квантифікації по змінній ця змінна стає пов’язаною. В ре- зультаті навішування квантора на одномісний предикат отримується нуль-місний пре- дикат (константа 0 або 1). Якщо змінна не пов’язана ніяким квантором, то вона нази- вається вільною. Вільна змінна може приймати усі значення із відповідної базисної мно- жини.
Квантори можна також застосовувати (можливо неодноразово) і до багатомісних предикатів. Кожне застосування операції квантифікації по одному аргументу зменшує
x
f
1
(x)
f
2
(x)
f
3
(x)
a
1 1
0
b
1 0
0
c
1 1
0

43 кількість вільних змінних (і відповідно місність предиката) на 1.
Приклад 4.8. Двомісний предикат f(x, y) має наступну таблицю значень:
Вказати таблиці значень предикатів а)
 
 
 
 
,
,
,
,
,
,
,
x f x y
x f x y
y f x y
y f x y




, б)
 
 
 
 
,
,
,
,
,
,
,
x y f x y
x y f x y
x y f x y
x y f x y
 
 
 
 
, в)
 
 
 
 
,
,
,
,
,
,
,
y x f x y
y x f x y
y x f x y
y x f x y
 
 
 
 
Розв’язок. а) Позначимо
 
 
 
 
1 2
,
,
,
g y
x f x y
g
y
x f x y
 
 
,
 
   
 
1 2
,
,
,
h x
y f x y h x
y f x y
 

Тоді
 
 
1
,
0
g a
x f x a
 

,
 
 
1
,
1
g b
x f x b
 

,
 
 
1
,
0
g c
x f x c
 

,
 
 
1
,
0
g d
x f x d
 

 
 
2
,
1
g a
x f x a
 

,
 
 
2
,
1
g b
x f x b
 

,
 
 
2
,
1
g c
x f x c
 

,
 
 
2
,
1
g d
x f x d
 

Предикати g
1
(y) та g
2
(y) мають наступні таблиці значень:
Для предиката h
1
(x)маємо:
 
 
1 1
1,
1
h
y f
y
 

,
 
 
1 2
2,
0
h
y f
y
 

,
 
 
1 3
3,
0
h
y f
y
 

,
 
 
1 4
4,
0
h
y f
y
 

,
 
 
1 1
5 5,
0
h
y h
y
 

Так само обчислюється предикат h
2
(x).Значення предикатів h
1
(x) та
h
2
(x) наведені у наступній таблиці: б)-в) Наведемо лише деякі значення
 
 
1
,
0
x y f x y
x h x
 
 

,
 
 
2
,
1
x y f x y
x h x
 
 

 
 
1
,
1
x y f x y
x h x
 
 

,
 
 
2
,
1
y x f x y
y g
y
 
 

4.3. Властивості операцій квантифікації:
1. Якщо предикат f не залежить від змінної у, то
 
 
 
,
,
x f x
y f x




  
— правила перейменування пов’язаних змінних.
2.
 
 
 
,
,
,
,
x y f x y
y x f x y
 
 


  
— правила перестановки однойменних кван-
торів.
3.
 
 


 
 


x f x
g
x f x
g
x f x
g
x f x
g





 



 
 
— правила внесення під знак квантора (g не залежить від х).
4.
 
 
 
 


x f x
x g x
x f x
g x

 
 

— пронесення квантора загальності через кон’юнкцію.
5.
 
 
 
 


x f x
x g x
x f x
g x

 
 

— пронесення квантора існування через диз’юнкцію.
y
x
a
b
c
d
1 1
1 1
1 2
1 1
1 0
3 0
1 0
0 4
0 1
0 0
5 1
1 0
0
y
g
1
(y)
g
2
(y)
a
0 1
b
1 1
c
0 1
d
0 1
x
h
1
(x)
h
2
(x)
1 1
1 2
0 1
3 0
1 4
0 1
5 0
1

44 6.
 
 
 
 
x f x
x f x
x f x
x f x


 



 

— закони де Моргана для кванторів.
Приклад 4.9. Побудувати таблицю значень предиката
 
 
,
,
x f x y
z g x z

 
, за умови, що таблиці значень предикатів f та g мають вигляд:
f
:
y
x
2 5
8 9
g:
y
x
2 5
8 9
a
1 1
1 1
a
1 1
1 1
b
1 1
1 0
b
0 1
1 1
c
0 0
1 0
c
0 0
1 1
d
0 0
1 0
d
0 0
0 0
e
1 1
1 0
e
0 0
0 0
Розв’язок.
Застосуємо першу та шосту властивості операцій квантифікації. Результатом виконання операцій над предикатами є двомісний предикат
 
 
 
 
 
 
 
1 1
,
,
,
,
,
h x y
x f x y
z g x z
x f x y
y g x y
f y
g x
 
 
 
 


, де
 
 
 
 
1 1
,
,
,
f y
x f x y
g x
y g x y
 
 
(ми застосували правило перейменування для змінних z та у). Таблиці значень предикатів f
1
та g
1
:
y
2 5
8 9
x
a
b
c
d
e
f
1
(y)
0 0
1 0
g
1
(x)
1 1
1 0
0
 
 
 
1 1
,2 2
0 1 1
h a
f
g a


  
,
 
 
 
1 1
,5 5
0 1 1
h a
f
g a


  
, …
 
 
 
1 1
,8 8
1 0
0
h d
f
g d


  
, …
 
 
 
1 1
,9 9
0 0 1
h e
f
g e


  
Тоді отримуємо наступну таблицю для
 
,
h x y
:
y
x
2 5
8 9
a
1 1
1 1
b
1 1
1 1
c
1 1
1 1
d
1 1
0 1
e
1 1
0 1

45
4.3. Аналіз міркувань
Засоби логіки предикатів використовуються для формулювання думок та запису тверджень.
Приклад 4.10. Записати речення а) кожний другокурсник успішно склав іспит з історії або програмування; б) сума двох додатних чисел — додатне число; в) кожне дійсне число крім нуля має обернене число, яке визначається однозначно. за допомогою предикатів та кванторів.
Розв’язок. а) Нехай А — множина усіх другокурсників. Розглянемо наступні предикати на мно- жині А:
f(x): x склав іспит з історії;
g(x): x склав іспит з програмування.
Тоді речення можна записати у вигляді
 
 


x f x
g x


Якщо ж нас цікавлять інші особи крім другокурсників, то потрібно додатково розглянути предикат h(x): х — другокурсник. Тоді речення можна записати у вигляді
 
 
 


x h x
f x
g x



Цей приклад можна розв’язати, замінивши одномісні предикати
 
f x та
 
g x більш загальним двомісним предикатом
 
,
l x y : х склав іспит з дисципліни у, визначеним, на приклад, на множинах людей та навчальних дисциплін. Тоді отримаємо запис
 

 



,історія
,програмування
x h x
l x
l x



б) Уведемо змінні х та y та перепишемо це речення так: "Два довільні додатні числа
х та y дають у сумі додатне число". Тоді отримаємо шуканий запис

 
 



0 0
0
x y
x
y
x
y
 




 
Базисною множиною є множина дійсних чисел. в) Для запису першої частини речення можна спочатку переписати його у вигляді
"Для кожного дійсного числа х, відмінного від нуля, існує таке дійсне число у,що
1
xy

". Для опису однозначності можемо скористатися тим, що для довільного z, яке є оберненим до х має виконуватися умова z y

. Остаточно отримуємо:












0 1
1
x
x
y
xy
z
xz
z
y


 
  
  
Приклад 4.11. Проаналізувати міркування
1) Усі люди смертні;
2) Сократ — людина;
Отже, Сократ смертний.
Розв’язок.
Нехай А — множина усіх живих істот. Уведемо у розгляд наступні предикати на

46 множині А:
f(x): х — людина,
g(x): x — смертний,
і нехай а = Сократ. Тоді міркування запишеться у такому вигляді:
1)
 
 


x f x
g x


(усі люди смертні).
2) f(a) (Сократ — людина).
Висновок g(a) (Сократ — смертний).
Для перевірки правильності міркування потрібно перевірити, чи випливає висновок міркування із засновків 1) та 2). Для цього потрібно дослідити, чи є тотожно фальшивим предикат
 
 


 
 
x f x
g x
f a
g a




Внесемо
 
 
f a
g a

у область дії квантора. Отримаємо
 
 


 
 
 
 


 
 


 
x f x
g x
f a
g a
x
f x
g x
f a
g a
x h x




 



 
, де
 
 
 


 
 
h x
f x
g x
f a
g a




Оскільки
 
 
 


 
 
 
 
 
 
 
 
0 0
0
h a
f a
g a
f a
g a
f a
f a
g a
g a
f a
g a










  
, то предикат h(x) не є тотожно істинним.
Тому
 
0
x h x


, а отже міркування є вірним.
4.4. Задачі для самостійного розв’язування
1. Вказати, яким є (тотожно істинним, тотожно фальшивим чи виконуваним) предикат
 
f x
, визначений на множині натуральних чисел. Відповідь обґрунтувати.
1)
 
2
:
8 15 0
f x
x
x



2)
 
: cos
0
f x
x

3)
 
4
:
16
f x
x

4)
 
3
:
1
f x
x
 
5)
 
2
:
10 24 0
f x
x
x



6)
 
1
: 3 9
x
f x

7)
 
4
: log
2
f x
x
 
8)
 
5
: log
2
f x
x

9)
 
:
f x
х — просте число.

47 10)
 
1
:
4 2
x
f x
  
 
 
2. Перевірити, чи є один з предикатів
 
f x ,
 
g x , визначених на множині цілих чисел, наслідком іншого. Відповідь обґрунтувати.
1)
 
:
f x х — парне число,
 
2
:
10 16 0
g x
x



2)
 
2
:
2 15 0
f x
x
x



,
 
:
g x х — непарне число.
3)
 
:
f x
х — просте число,
 
2
:
5 6
0
g x
x
x

 
4)
 
:
f x х — просте число,
 
2
:
7 10 0
g x
x
x



5)
 
:
f x
х — просте число,
  



2
:
7 16 39 0
g x
x
x
x




6)
 
:
f x
х — парне число,
 
2
:
2 4
0
g x
x
x

 
7)
 
:
f x х — непарне число,
 
2 9
20
:
0 4
x
x
g x
x




8)
 
:
1 3
f x
x
 
,
 
2
:
5 7
0
g x
x
x

 
9)
 
2
: 4 12 9
0
f x
x
x

 
,
 
: 2 5
0
g x
x
 
10)
 
: 2 1 / 2
x
f x
 
,
 
2
:
10 25 0
g x
x
x



3. Операції над предикатами
1) Вказати множину істинності предиката
 
 


,
,
x f x y
g x y


, якщо
 
,
:
f x y
x
y

— однорідний двомісний предикат, визначений на множині


1,2,3,4,5,6,7,8
A

,
 
,
g x y — однорідний двомісний предикат на множині А, множина істинності якого рівна
         


2,5 , 3,2 , 4,7 , 7,7 , 7,8 .
2) Знайти множину істинності предиката
 
 


,
x f x y
g x


, якщо предикати
 
,
:
f x y
x
y

— просте число та
 
:
g x
остача від ділення
2 7
x

на 4 рівна 1 або 3 визначені на множині


1,2,3,4,5,6,7,8
A

3) Предикати
 
1
,
:
1
y
f x y
x


— ціле число та
 
2
:
10 16 0
g x
x
x



визначені на мно- жині A = {2, 3, 5, 7, 9, 11}. Перевірити, чи є один із предикатів
 
,
y f x y

та
 
g x наслідком іншого.
4) Знайти
 
 


,
x
y f x y
g x
 

, якщо предикати
 
,
:
f x y
2 2
x
y

— просте число,
 
2
: 2 3
g x
x

кратне 5 визначені на множині


1,2,3,4,5,6,7,8
A

5) Вказати таблицю значень предиката
 
 
,
,
x f x y
y g x y

 
, якщо двомісні предикати
 
,
:
f x y
2 2
10
y
x


та
 
,
:
g x y " x
y

кратне 6" визначені на множинах


1 1,3,4,7,8,9
A

та


2 5,0,3,5,7
A
 

48 6) Вказати множину істинності предиката
 
   


,
f x y
y g y
h x
 

, якщо преди- кати
 
,
:
f x y
x
y

— просте число,
 
2
:
3
g x
x

кратне 4,
 
h x : х кратне 3 визна- чені на множині


1,2,3,4,5,6,7,8
A

7) Предикати
 
2
,
:
1
y
f x y
x


— ціле число та
 
2
:
9 14 0
g x
x
x



визначені на множині A = {2, 3, 5, 7, 9, 11}. Перевірити, чи є один із предикатів
 
,
y f x y

та
 
g x
наслідком іншого.
8) Вказати множину істинності предиката
 
 


,
,
x f x y
g x y


, якщо
 
2
,
:
f x y
x
y

— однорідний двомісний предикат, визначений на множині


1,2,3,4,5,6,7,8
A

,
 
,
g x y
— однорідний двомісний предикат на множині А, множина істинності якого рівна
               


1,2 , 2,4 , 3,2 , 3,5 , 4,7 , 5,3 , 7,7 , 7,8 .
9) Вказати таблицю значень предиката
 
 
,
,
x g x y
y f x y

 
, якщо двомісні преди- кати
 
,
:
f x y
" x
y

кратне 4" та
 
,
:
g x y
2 3
8
y
x


визначені на множинах


1 1,3,4,7,8,9
A

та


2 5,0,3,5,7
A
 
10) Знайти
 
 


,
x
y f x y
g x
 

, якщо предикати
 
,
:
f x y
"
2
x
y

— просте число",
 
:
g x
" 2 3
x
y

кратне 7" визначені на множині


2,3,4,5,6,7,8
A

4. Проаналізувати міркування
1) а) Кожний атлет сильний. б) Кожний, хто сильний і розумний, досягне успіху. в) Петро — розумний атлет.
Отже, Петро досягне успіху.
2) а) Усі хижаки — жорстокі істоти. б) Усі акули — хижаки і морські істоти. в) Деякі акули не їдять людей.
Отже, деякі жорстокі істоти не їдять людей або не є морськими істотами.
3) а) Усі, хто успішно склав іспит з програмування, володіють хоча б однією мовою програмування. б) Степан володіє мовою С++. в) С++ є мовою програмування.
Отже, Степан успішно склав іспит з програмування.
4) а) Кожний програміст може написати цю програму за один день, якщо хто-небудь може її написати за один день. б) Тарас програміст. в) Тарас не може написати цю програму за один день.
Отже, ніхто не може написати цю програму за один день.
5) а) Деякі цілі числа — від’ємні. б) Усі натуральні числа — цілі.

49 в) Нема жодного від’ємного натурального числа.
Отже, деякі цілі числа не є натуральними.
6) а) Іван мало вчиться. б) Кожний, хто мало вчиться, не зможе скласти іспит з вищої математики, хіба що йому пощастить або допоможе товариш. в) Жодний товариш не допоможе Івану.
Отже, якщо Івану не пощастить, то він не зможе скласти іспит.
7) а) Деякі паралелограми — ромби, а деякі — прямокутники. б) Усі квадрати одночасно є ромбами і прямокутниками. в) Усі прямокутники — паралелограми.
Отже, усі квадрати — паралелограми.
8) а) Деякі лікарі розумні. б) Усі розумні люди вміють читати. в) Деякі лікарі добре заробляють.
Отже, деякі лікарі вміють читати і добре заробляють.
9) а) Усі чоловіки люблять грати у спортивні ігри. б) Футбол — спортивна гра. в) Петро чоловік.
Отже, Петро любить грати у футбол.
10) а) Усі машини коштують дорого або є старими та зламаними. б) Новий велосипед Сашка недорогий. в) Велосипед Сашка не є зламаним.
Отже, велосипед Сашка — не машина.

50
РЕКОМЕНДОВАНА ЛІТЕРАТУРА
1. Капітонова Ю. В., Кривий С. Л., Летичевський О. А., Луцький Г. М. Основи дискретної математики. — К.: Наукова думка, 2002. — 580 с.
2. Бондаренко М.Ф., Білоус Н.В., Руткас А.Г. Комп’ютерна дискретна математика. —
Харків: "Компанія Сміт", 2004. — 480 с.
3. Бардачов Ю. М., Соколова Н. А., Ходаков В. Є. Дискретна математика. — К.: Вища школа, 2002. — 287 с.
4. Андрійчук В. І., Комарницький М. Я., Іщук Ю. Б. Вступ до дискретної математики.
— К.: Центр навчальної літератури, 2004. — 254 с.
5. Нікольський Ю. В., Пасічник В. В., Щербина Ю. М. Дискретна математика. —
К.: Видавнича група BHV, 2007. — 368 с.
6. Ядренко М. Й., Оленко А. Я. Дискретна математика. навчально-методичний посібник. — К.: Київський університет ім. Т. Шевченка, 1995. — 83 с.
7. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера.
М.: Энергоатомиздат, 1988. — 480 с.
8. Новиков Ф. А. Дискретная математика: Учебник для вузов. 2-е изд. Стандарт третьего поколения. — СПб.: Питер, 2013. — 432 с.
9. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. — 5-е изд., исправл. — М.: ФИЗМАТЛИТ, 2004. — 256 с.
10. Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике:
Учеб. пособие. — 3-е изд., перераб. — М.: ФИЗМАТЛИТ, 2005. — 416 с.
11. Андерсон Д. Дискретная математика и комбинаторика. — СПб.: Вильямс, 2003. —
958 с.
12. Латонин Л. А., Макаренков Ю. А., Николаева В. В., Столяр А. А. Математическая логика: Учеб. пособие. — Мн.: Выш. шк., 1991. — 269 с.
13. Нефедов В. Н., Осипова В. А. Курс дискретной математики. — М.: Изд-во МАИ,
1992. — 264 с.
14. Вітенько І. В. Математична логіка: Курс лекцій. — Ужгород: УжДУ, 1971. —
224 с.
15. Цейтлін Г. Є. Елементи теорії булевих функцій. — К: Техніка, 1973. — 76 с.
16. Яблонский С. В., Лупанов О. Б. Дискретная математика и математические вопросы кибернетики. — М.: Наука, 1974. — 312 с.
17. Яблонский С. В. Введение в дискретную математику: Учеб. пособие для вузов /
Под ред. В. А. Садовничего. — 4-е изд., стер. — М.: Высшая школа; 2003. — 384 с.