Логика. логіка. Математична логіка та теорія алгоритмів

• Название: Математична логіка та теорія алгоритмів
• Анкор: Логика
• Дата: 15.05.2022
• Размер: 1.6 Mb.
• Имя файла: логіка.pdf
• Тип: Навчальний посібник; #530647
• страница: 9 из 18

Приклад 6. Розглянемо двомісний предикат «
1

 y
x
», заданий на множині натуральних чисел, та зв’яжемо квантором загальності змінну х. Отримаємо одномісний предикат «
)
1
(



y
x
x
», який буде тотожно істинним для будь-якого значення y.
Відмітимо, що якщо є n-місний предикат, то його змінні можна по черзі зв’язувати одним із кванторів. Якщо зв’язати кванторами всі змінні деякого предиката, то отримаємо висловлення.
Приклад 7. Як приклад розглянемо предикат «
z
y
x


», заданий на множині дійсних чисел.
Зв’яжемо всі його змінні кванторами так
«
)
(
z
y
x
z
y
x





» і одержимо істинне висловлення. Дійсно, для будь-яких двох

63
дійсних чисел x і y можна вказати таке дійсне число z, що
z
y
x


(для цього достатньо покласти
1



y
x
z
).
Перед введенням поняття формули логіки предикатів розглянемо ще деякі важливі поняття, а саме поняття області дії квантора, вільного і зв’язаного входжень предметної змінної.
Область дії квантора – це предикат, до якого відноситься цей квантор.
Входження предметної змінної x в даний предикат називається зв’язаним, якщо x є змінною квантора або знаходиться в області дії квантора за цією змінною. В протилежному випадку входження предметної змінної називається
вільним.
Предметна змінна називається вільною в даному предикаті, якщо всі її входження в цей предикат вільні; зв’язаною – якщо всі її входження зв’язані;
частково вільною або частково зв’язаною – якщо є вільні і зв’язані входження цієї змінної в предикат.
Приклад 8. Розглянемо предикат «
)
0
(
)
(
2





x
y
x
y
x
». Областю дії квантора існування буде предикат «
)
(
2
y
x
y


», областю дії квантора загальності буде предикат «
2
y
x 
», змінна y є зв’язаною змінною, а змінна x – частково зв’язаною, оскільки має одне вільне та одне зв’язане входження.
Якщо одномісний предикат
Р(х
) задано на скінченній множині елементів
}
,...,
,
{
2 1
k
с
с
с
M 
, то операція зв’язування квантором загальності
)
( x
xP

рівносильна кон’юнкції
)
(
)
(
)
(
2 1
k
c
P
c
P
c
P



, а операція зв’язування квантором
існування
)
(x
xP

рівносильна диз’юнкції
)
(
)
(
)
(
2 1
k
c
P
c
P
c
P



При формулюванні тверджень мовою логіки предикатів часто зустрічаються речення чотирьох типів, які в арістотелевій логіці називаються
категоричними судженнями і мають зміст та символічний запис:
А: загальностверджувальне судження "всі S суть Р" (всі елементи х,які мають властивість S, мають і властивість Р) -
))
(
)
(
(
x
P
x
S
x


;
Е: загальнозаперечувальне судження "будь-яке S не є Р" (будь-який елемент
х, який має властивість S,не має властивості Р)-
)
)
(
)
(
(
x
P
x
S
x


;
I: частково стверджувальне судження "деякі S суть Р" (деякі елементи
х, які мають властивість S, мають і властивість Р) -
))
(
)
(
(
x
P
x
S
x


;
О: частково заперечувальне судження "деякі S не є Р" (деякі елементи х, які мають властивість S,не мають властивості Р) -
)
)
(
)
(
(
x
P
x
S
x


;

64
Комбінуючи речення А-O, можна записувати у символічній формі досить складні твердження.
Запитання для самоконтролю
1. Що називається n-місним предикатом, заданим на множині
М=
n
M
M
M



2 1
? Як позначаються предикати?
2. Що таке предметні змінні, предметні константи, значення істинності предиката для відповідного набору?
3. Який предикат називається: а)тотожно істинним, б)тотожно хибним, в)виконуваним, г)спростовним? Наведіть приклади предикатів кожного типу.
4. Що називаєтьсяобластю істинності предиката
)
,...,
,
(
2 1
n
x
x
x
P
заданого на множині
n
M
M
M
M




2 1
?
5. Як визначаються операції заперечення, кон’юнкція, диз’юнкція, імплікація та еквіваленція в логіці предикатів?
6. Що називається зв’язуванням квантором загальності за змінною
i
x
предиката
)
,...,
,
(
2 1
n
x
x
x
P
, заданого на множині
n
M
M
M
M




2 1
?
7. Що називається зв’язуванням квантором існуванняза змінною
i
x
предиката
)
,...,
,
(
2 1
n
x
x
x
P
, заданого на множині
n
M
M
M
M




2 1
?
8. Що таке область дії квантора? Які змінні називаються зв’язаними, вільними, частково зв’язаними або частково вільними?
9. Як пов’язані операції зв’язування квантором загальності та кон’юнкція в логіці предикатів?
10. Як пов’язані операції зв’язування квантором існування та диз’юнкція в логіці предикатів?
ВПРАВИ
3.1. Визначити, які з наступних речень будуть предикатами та вказати їх місність: a)
4 і 6 діляться на 3 без остачі; b)
х – парне число; c)
х і у чотирикутники; d)
f(x) – диференційовна функція; e) кожен день неділі – середа; f) сьогодні четвер і буде хороша погода; g) у будь-якому трикутнику можна провести три висоти.

65 3.2. Вказати приклади тотожно істинних, тотожно хибних, виконуваних та спростовних предикатів, заданих на множині: a). цілих чисел; b). простих чисел; c). {-1,0,1}.
3.3. Для кожного з наступних висловлень знайти предикати, які перетворюються в дане висловлення при заміні предметних змінних їх деякими значеннями з області задання предиката: a). 6>2+3; b). гори Карпати знаходяться в Україні; c). через точку А(1;0) можна провести пряму, паралельну до прямої b.
3.4. Визначити які з входжень змінних у формулу є вільними, а які зв’язаними: a)


)
,
(
)
,
(
z
y
Q
y
x
xP
y



; b)


)
,
,
(
)
(
)
,
(
z
y
x
zQ
y
y
yR
y
x
P
x






; c)


)
,
(
)
,
(
)
,
(
y
x
yQ
y
x
xR
y
x
yP





; d)


)
(
)
,
,
(
)
,
(
x
R
z
y
x
zQ
y
x
xP




3.5. Визначити множини істинності наступних предикатів: a)
P(x)= «
2

x
», М – множина дійсних чисел; b)
P(x)= «х парне і просте число», М – множина натуральних чисел; c)
P(x)= «х взаємно просте з 5», М – множина цілих чисел; d)
P(x)= «x>х+1», М – множина від’ємних чисел.
3.6. Визначити множини істинності наступних предикатів, заданих на множині
М, та зобразити їх на площині: a)
)
,
(
)
,
(
y
x
Q
y
x
P

, де P(x,y) = «
2

 y
x
»,Q(x,y) = «
9 2
2

 y
x
», М –множина дійсних чисел; b)
)
,
(
y
x
Q
, де Q(x,y) = «
10 2
2

 y
x
», М – множина цілих чисел; c)
)
,
(
)
,
(
y
x
Q
y
x
P

, де P(x,y) = «
y
x 
»,Q (x,y) = «
)
ln( y
e
x 
», М – множина дійсних чисел; d)
)
,
(
)
,
(
y
x
Q
y
x
P

, де P(x,y) = «
y
x 
»,Q (x,y) = «
3

 y
x
», М – множина дійсних чисел; e)
)
,
(
)
,
(
y
x
Q
y
x
P

, де P(x,y)= «
1 3

 y
x
»,Q (x,y)= «
y
x

 3
», М – множина дійсних чисел;

66
f)
)
,
(
)
,
(
y
x
P
y
x
Q

, де P(x,y)= «
1 3

 y
x
»,Q (x,y)= «
y
x

 3
», М – множина дійсних чисел; g)
)
,
(
)
,
(
y
x
Q
y
x
P

, де P(x,y)= «
1 3

 y
x
»,Q (x,y)= «
10 2
2

 y
x
», М – множина дійсних чисел.
3.7. Нехай на множині людей задано предикати P(x,y) = « х батько у», Q(x,y)= «х мати у», R(x,y) = «х син у» та S(x,y) = «х дочка у». Виразити через них наступні предикати: a)
«х брат у»; b)
«х тітка у»; c)
«х бабуся у з боку матері»; d)
«х і у - двоюрідні сестри»; e)
«х і у - внуки z»;
3.8.Записати речення у символічній формі, увівши потрібні предикати: a) жодне парне число, більше 2, не просте; b) добуток двох довільних чисел не є простим числом; c) добуток двох парних чисел є парне число; d)
існують неперервні функції, які не диференційовані; e) кожне дійсне число, за виключенням нуля, має обернене; f) деякі автобуси не зупиняються на цій зупинці’ g) кожний, в кому є упертість, може вивчити логіку; h) всі судді юристи, але не всі юристи – судді; i) ви можете обманювати декого весь час, ви можете обманювати всіх деякий час, але ви не можете обманювати всіх і весь час.
3.9. Предикати P(x,y), R(x,y) та Q(x) за дано на множині
}
,
,
{
c
b
a
таблицями значень:
P(x,y)
R(x,y)
Побудувати таблиці значень предикатів: a)


)
,
(
)
(
y
x
xP
y
x
Q



; b)
)
,
(
)
,
(
y
x
yR
y
x
xP



;
x\y
a
b
c
a
1 1
0
b
0 1
0
c
0 1
1
x\y
a
b
c
a
1 0
1
b
1 1
1
c
0 0
1
x
Q(x)
a
1
b
0
c
1

67
c)


)
,
(
)
,
(
)
(
y
x
R
y
x
P
x
x
Q



; d)


)
,
(
)
,
(
)
(
y
x
R
y
x
P
x
Q
y
x




; e)


)
(
)
,
(
)
,
(
x
Q
y
x
R
y
x
P
y



3.10. Для предикатів P(x,y) та Q(x), заданих на множині
}
,
,
{
c
b
a
, скласти таблиці значень так, щоб предикат R(x,y) був: a). тотожно істинним, якщо
)
,
(
)
(
)
,
(
y
x
yP
x
Q
y
x
R



; b). тотожно хибним, якщо
)
,
(
)
(
)
,
(
y
x
P
x
xQ
y
x
R



; c). виконуваним, якщо
)
(
)
,
(
)
(
)
,
(
x
Q
y
x
yP
x
xQ
y
x
R





3.11. Студент вирішив кожну прослухану лекцію повторювати дома. В кінці семестру виявилось що він не виконав свого рішення. Запишіть цей факт мовою логіки предикатів.
3.12. Випадок в магазині. Юнак вирішив купити туфлі в подарунок брату але забув розмір його ноги. Тоді продавець сказав йому: «В нашому магазині для будь-якої ноги знайдуться туфлі підходящого розміру». На що юнак відповів:
«Тоді дайте мені туфлі, що підходять до будь-якої ноги». Чи правильно юнак зрозумів продавця?
3.13. На множині натуральних чисел з нулем вибрано такі атомарні предикати:








;
,
0
,
,
1
)
,
,
(
3 2
1 3
2 1
3 2
1
x
x
x
x
x
x
x
x
x
S






,
0
,
,
1
)
,
,
(
3 2
1 3
2 1
3 2
1
x
x
x
x
x
x
x
x
x
D
Виразити через них такі предикати: a).
2 1
x
x 
; b).
1
x
– просте число; c).
0 1

x
; d).
1
x
– НСД чисел
2
x
та
3
x
3.2. ФОРМУЛИ ЛОГІКИ ПРЕДИКАТІВ. ІНТЕРПРЕТАЦІЯ ФОРМУЛ.
ВИКОНУВАНІ ТА ЛОГІЧНО ЗАГАЛЬНОЗНАЧУЩІ ФОРМУЛИ
Алфавітом логіки предикатів є наступні категорії символів:
1) предметні змінні;
2) предметні константи;
3) функціональні символи
n
i
f
(і – порядковий номер, n – арність, кількість аргументів);

68 4) предикатні символи
n
i
P
(і – порядковий номер, n – місність);
5) символи логічних операцій:






,
,
,
,
,
,
;
6) допоміжні символи: (, ).
Слова, які записані за допомогою алфавіту, поділяються на терми та формули. Термами є будь-яка предметна змінна або константа, а також значення функціонального символу для набору, кожен елемент якого є термом. Предикатні символи, в застосуванні їх до термів, дають елементарні формули логіки предикатів.
Формулами логіки предикатів є:
1) будь-які елементарні формули;
2) слова виду:
)
(
),
(
),
(
),
(
,
)
(













, де

і

– формули логіки предикатів;
3) якщо

формула логіки предикатів, а
i
x
вільна змінна цієї формули, то слова


)
(

i
x

і


)
(

i
x

також є формулами логіки предикатів.
4) всі інші слова, крім тих, які утворюються за правилами 1)-3), не є формулами логіки предикатів.
Приклад 1. Перевірити, чи утворюють наступні слова формули логіки предикатів: «








)
,
(
)
(
2 1
2 2
1 1
1 1
1
x
x
P
x
x
P
x



», «




)
,
(
)
,
(
2 1
2 2
2 1
2 1
x
x
P
x
x
P

».
Слово








)
,
(
)
(
2 1
2 2
1 1
1 1
1
x
x
P
x
x
P
x



не є формулою логіки предикатів, оскільки






)
,
(
)
(
2 1
2 2
1 1
1 1
x
x
P
x
x
P


є формулою згідно пунктів 1)-3), але в цій формулі змінна
1
x
є частково вільною, а тому навішування квантора існування не відповідає пункту 3) і, згідно 4), слово








)
,
(
)
(
2 1
2 2
1 1
1 1
1
x
x
P
x
x
P
x



не утворює формулу логіки предикатів.
Слово




)
,
(
)
,
(
2 1
2 2
2 1
2 1
x
x
P
x
x
P

утворює формулу логіки предикатів. Дійсно, слова
)
,
(
2 1
2 1
x
x
P
і
)
,
(
2 1
2 2
x
x
P
є формулами згідно пункту 1). А слова
)
,
(
2 1
2 1
x
x
P
,


)
,
(
)
,
(
2 1
2 2
2 1
2 1
x
x
P
x
x
P

і




)
,
(
)
,
(
2 1
2 2
2 1
2 1
x
x
P
x
x
P

є формулами логіки предикатів згідно пункту 2). Отже формула




)
,
(
)
,
(
2 1
2 2
2 1
2 1
x
x
P
x
x
P

є формулою логіки предикатів.
Формула, яка не має вільних входжень предметних змінних, називається замкнутою. В протилежному випадку формула є відкритою.

69
Інтерпретацією формули логіки предикатів
)
,...,
(
1
n
x
x

називається система, яка складається з непорожньої множини
n
M
M
M
M




2 1
, яку називають областю інтерпретації, і деякої відповідності, яка кожному предикатному символу
n
i
P
ставить у відповідність певний n-місний предикат, заданий на множині М, кожному функціональному символу
n
i
f
– деяку n-арну операцію, кожній константі
i
a
– деякий конкретний елемент із
i
M