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

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

Приклад 2. Побудувати деяку інтерпретацію для формули


z
y
x
f
xP
,
),
(
1 1
3 1

Наша формула містить тримісний предикат, один функціональний символ, дві вільні та одну зв’язану змінну. За область інтерпретації оберемо множину всіх дійсних чисел. Функціональному символу поставимо у відповідність унарну операцію піднесення до квадрата
2 1
1
)
(
x
x
f

. Предикатний символ позначимо тримісним предикатом

)
,
,
(
3 1
z
y
x
P
«
z
y
x


». В цій інтерпретації ми отримали формулу


z
y
x
x



2
, яка буде виконуватись на тих наборах дійсних чисел, для яких
0

 z
y
і
y
z
x



Формули логіки предикатів в деякій фіксованій інтерпретації поділяються на: істинні (виконуються для будь-якого набору з області інтерпретації), хибні
(не виконуються на жодному наборі з області), виконувані (виконуються хоч на одному наборі) та спростовні (не виконуються хоч на одному наборі).
Якщо формула логіки предикатів істинна в будь-якій інтерпретації, то така формула називається загальнозначущою або логічно загальнозначущою (ЛЗЗ).
Логічно загальнозначущу формулу називають тавтологією логіки предикатів.
Якщо формула логіки предикатів хибна в будь-якій інтерпретації, то вона називається тотожно хибною або суперечністю логіки предикатів. Якщо формула логіки предикатів виконувана (спростовна) хоча б в одній інтерпретації, то така формула називається виконуваною (спростовною).
Інтерпретація називається моделлю для даної множини Г формул логіки предикатів, якщо кожна формула з Г істинна в даній інтерпретації.
Якщо ми маємо деяку формулу алгебри висловлення
)
,...,
,
(
2 1
n
a
a
a
А
, то при застосуванні підстановки
)
(
,...,
,
,...,
,
2 1
2 1
А
S
n
n
a
a
a



, де
n



,...,
,
2 1
– довільні формули логіки предикатів, ми отримаємо деяку формулу логіки предикатів, яку називають
окремим випадом формули алгебри висловлень. Це правило дає можливість на основі тотожно істинних формул алгебри висловлень будувати, використовуючи

70
правило підстановки, загальнозначущі формули логіки предикатів – окремі
випадки тавтологій алгебри висловлень.
Приклад 3. Формула логіки предикатів




)
(
)
,
(
)
,
(
(
)
(
x
xP
y
x
yQ
y
x
Q
y
x
xP







є загальнозначущою, оскільки одержана підстановкою




a
b
b
a
S
y
x
yQ
x
xP
b
a





)
(
)
,
(
)
(
, застосованою до формули алгебри висловлень
)
(
)
(
a
b
b
a



, що є законом контрапозиції.
Приклад 4. Чи буде формула логіки предикатів


)
(
)
(
)
(
)
(
x
Q
x
Q
x
P
x
x





виконуваною? ЛЗЗ?
Знайдемо умови, які повинні задовольняти предикати в інтерпретації.
Припустимо, що існує інтерпретація

на множині М:
1
))
(
(

x


. Тобто
M
a 

0
і
існують інтерпретації предикатних символів
)
(x
P
і
)
(x
Q
-
)
(
0
x
P
і
)
(
0
x
Q
- такі, що:


1
)
(
)
(
)
(
0 0
0 0




a
Q
x
Q
x
P
x
Це рівносильно системі умов:











1
)
(
,
1
)
(
)
(
0 0
0 0
a
Q
x
Q
x
P
x
Останню систему можна переписати так:










1
)
(
,
1
)
(
)
(
0 0
0 0
a
Q
x
Q
x
P
M
x
Умови системи не суперечать одна одній. Тобто:
)
(x
Q
повинен бути спростовним і на всіх значеннях множини інтерпретації, де
)
(x
Q
набуває хибних значень,
)
(x
P
також повинен набувати хибних значень, або бути тотожно хибним.
Наприклад, нехай
)
(x
Q
=«
3

x
» і
)
(x
P
=«
6

x
» на множині
Z
M 
. Одержимо формулу


)
3
(
)
3
(
)
6
(



x
x
x
x



, яка набуває істинних значень на всіх цілих числах
}
|
3
{
Z
k
k
x


. Таким чином
)
(x

- виконувана.
Можна розглянути інтерпретацію нашої формули на одноелементній множині
}
{a
M 
. На цій множині


)
(
)
(
x
Q
x
P
x


та
)
(x
Q
перейдуть відповідно в
)
(
)
(
a
Q
a
P

і
)
(a
Q
, які позначимо
q
p 
і
q
. Тоді матимемо формулу алгебри висловлень, яка є спростовною. Дійсно:
q
p
q
q
p
q
q
p







)
(
)
(

71
Остання формула алгебри висловлень є спростовною. Отже, задана формула логіки предикатів
)
(x

не є істинною в даній інтерпретації, і, як наслідок, не є
ЛЗЗ.
Приклад
5.
Довести, що формула логіки предикатів


)
(
)
(
)
(
x
xP
x
xQ
x
xP





є ЛЗЗ.
Припустимо, що наша формула є спростовною. Тобто існує така
інтерпретація на деякій множині М, на якій предикатні символи
)
(x
P
і
)
(x
Q
мають
інтерпретації
)
(
0
x
P
і
)
(
0
x
Q
, і


0
)
(
)
(
)
(
0 0
0






x
xP
x
xQ
x
xP
Остання рівність рівносильна системі









0
)
(
)
(
,
1
)
(
0 0
0
x
xP
x
xQ
x
xP
Використовуючи означення операцій квантування та імплікації прийдемо до рівносильної системи














,
0
)
(
,
1
)
(
,
1
)
(
0 0
0 0
0
x
P
M
x
x
Q
M
x
x
P
M
x
яка містить суперечність. Отже наше припущення про спростовність формули


)
(
)
(
)
(
x
xP
x
xQ
x
xP





є невірним. А тому вона є логічно загальнозначущою.
Запитання для самоконтролю
1. Які типи символів становлять алфавіт логіки предикатів?
2. Що називається термом?
3. Що називається формулою логіки предикатів? Що таке атомарна
(елементарна) формула?
4. Яка формула логіки предикатів називається замкненою, відкритою?
5. Що називається інтерпретацією формули логіки предикатів
)
,...,
(
1
n
x
x

?
6. Які типи формул логіки предикатів в фіксованій інтерпретації існують?
7. Яка формула називається логічно загальнозначущою? Наведіть приклад ЛЗЗ формули.
8. Яка формула називається виконуваною? Наведіть приклад.
9. Що таке модель множини формул?
10. Що називають окремим випадом формули алгебри висловлень?
ВПРАВИ
3.14. Перевірити чи утворюють наступні слова формули логіки предикатів:

72
a)




)
,
,
(
)
(
)
,
(
z
y
x
zQ
y
y
yR
y
x
P
x
x







; b)


)
(
)
,
,
(
)
,
(
x
R
z
y
x
zQ
y
x
xP




; c)


)
,
,
(
)
(
z
y
x
yP
z
x
y
R
x





; d)




)
(
)
(
)
(
)
(
x
xQ
x
xP
x
Q
x
P
x






3.15. Записати наведені нижче математичні твердження за допомогою формул логіки предикатів: a)
існують такі дійсні числа x, y, z, що
2 2
2
z
y
x


; b) будь-який опуклий чотирикутник має площу; c) якщо кожна з двох прямих паралельна третій, то вони паралельні між собою; d) для довільного дійсного числа х:
1
)
sin(
1



x
; e)
існують три точки, що не належать одній прямій.
3.16. Побудувати інтерпретації для наступних формул: a)


)
,
(
)
,
(
2 1
2 1
x
y
P
y
x
P
y
x



; b)


)
,
(
)
,
(
2 1
2 1
x
y
P
y
x
P
y
x



; c)
))
(
),
(
(
1 2
1 1
2 1
y
f
x
f
yP
x

; d)
))
(
),
(
,
(
)
(
1 2
1 1
2 2
2 1
z
f
y
f
x
zP
y
x
xP




; e) показати, що при інтерпретації формули
)
(
)
(
x
xP
x
xP



на довільній одноелементній множині завжди отримується істинне висловлення, а на двоелементній – не завжди.
3.17. Записати деяку інтерпретацію формули над множиною
}
,
,
{
c
b
a
і записати таблицю значень отриманого предиката: a).


)
,
(
)
,
(
)
,
(
y
x
yR
y
x
xQ
y
x
yP





; b).


)
,
(
)
,
(
)
,
(
z
x
R
x
y
yQ
z
x
xP




; c).
)
(
)
,
,
(
)
,
(
x
R
z
y
x
zQ
y
x
xP




3.18. Навести приклад формули F логіки предикатів, для якої виконується наступна умова: a). F є тотожно істиною на всіх скінченних множинах і виконуваною на всіх нескінченних; b). F є виконуваною на деякій нескінченній множині і тотожно хибною на всіх скінченних множинах; c). F виконувана на скінченних множинах з парною кількістю елементів і тотожно хибна на всіх інших скінченних множинах.

73 3.19. Перевірити, чи буде формула логіки предикатів логічно загальнозначущою: a)
)
(
)
(
y
yQ
x
P


; b)




)
(
)
(
)
(
)
(
y
Q
x
xP
y
Q
x
P
x





; c)


)
(
)
(
)
,
(
z
zQ
y
Q
y
x
P
x




d)




)
(
)
(
x
P
x
x
xP



; e)




)
(
)
(
)
(
)
(
x
xQ
x
xP
x
Q
x
P
x






; f)


)
,
(
)
,
(
)
,
(
y
x
yR
y
x
xQ
y
x
yP





g)

 

)
(
)
(
)
(
)
(
x
xQ
x
xP
x
Q
x
P
x






; h)


)
,
(
)
(
)
,
(
y
x
yP
x
Q
y
x
P
x




i)




)
(
)
(
)
(
)
(
y
Q
x
P
y
y
yQ
x
P





3.20. Перевірити, чи буде виконуваною формула логіки предикатів: a)


)
,
,
(
)
,
(
z
y
x
zQ
y
x
P
y
x




; b)
)
(
)
(
y
P
x
xP


; c)


)
(
)
(
y
P
x
P
y
x



; d)


)
(
)
,
(
y
Q
y
x
P
x


; e)


)
,
(
)
(
)
,
(
y
x
yP
x
Q
y
x
P
x




; f)


)
,
,
(
)
,
(
z
y
x
zQ
y
x
P
y
x




; g)
)
(
)
,
,
(
)
,
(
x
R
z
y
x
zQ
y
x
xP




h)


)
(
)
(
)
,
(
z
zQ
y
Q
y
x
P
x




; i)




)
(
)
(
)
(
)
(
x
xQ
x
xP
x
Q
x
P
x






j)
)
,
(
)
,
(
y
x
yP
x
y
x
yP
x





3.3. ВІДНОШЕННЯ РІВНОСИЛЬНОСТІ В ЛОГІЦІ ПРЕДИКАТІВ.
ЗВЕДЕНА ТА ПРЕНЕКСНА НОРМАЛЬНІ ФОРМИ
В логіці предикатів, як і в алгебрі висловлень, введемо поняття логічного наслідку та задамо відношення рівносильності на множині формул логіки предикатів.
Формула

називається логічним наслідком множини формул
}
,...,
,
{
2 1
n



, якщо вона виконується на всіх наборах елементів з області довільної
інтерпретації, на яких виконується кожна формула
)
1
(
,
n
i
i



. Позначення:





|
,...,
,
2 1
n
Якщо множина складається лише з однієї формули
}
{

, то кажуть що формула

є логічним наслідком формули


74
Найбільш часто вживані схеми логічного висновку - силогізми Арістотеля.
Це схеми, що складаються з трьох простих висловлень типуА, E,I та O, з яких перші два - посилки, а третє - висновок. У кожному з силогізмів розглядаються три властивості (предикати) S, М та Р. Перша (велика) посилка пов’язує М і Р, друга (мала) пов’язує М і S, а висновок пов’язує S і Р. У залежності від положення М у посилках, розрізняють чотири фігури силогізму:
І
II
III
IV
МхР, SyM
|=
SzP
РхМ, SyM
|=
SzP
МхР, MyS
|=
SzP
РхМ, MyS
|=
SzP
Тут буквами х, у та z позначено одне з чотирьох висловлень типу А, Е, І чи
О, що пов’язує властивості S, М та Р. Отже, у кожній фігурі є 4 4∙4 = 64 модуси силогізму. Всього різних модусів силогізму 256. Арістотель встановив, що правильними з них є лише 19 (по 4 у І та II фігурах, 6 у III і 5 у IV фігурі).
Силогізми позначають трьома літерами (ААА, ЕIO, АЕЕ і т.п.) за виглядом висловлень, які пов’язують властивості. Для полегшення запам’ятовування правильних силогізмів кожному присвоюють ім’я (Barbara, Ferio, Camestresі т.п.)
- латинське слово, яке містить тільки ті голосні букви, що входять до позначення силогізму. Наприклад, Barbara це силогізм ААА першої фігури MAP,
SAM
⊨SAP, який можна прочитати «Всі М Р. Всі S

М. Отже, всі S

Р» або записати формулами логіки предикатів
))
(
)
(
(
x
P
x
M
x


,



|
))
(
)
(
(
x
M
x
S
x
))
(
)
(
(
x
P
x
S
x


. Прикладом такого судження може бути: «Всі ромби - паралелограми. Всі квадрати - ромби. Отже, всі квадрати
— паралелограми».
Дві формули логіки предикатів називаються рівносильними, якщо перша є логічним наслідком другої і навпаки. Позначення:

 