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

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

Теорема 3.3.1. Якщо

і

– формули логіки предикатів, то:
1) формула

є логічним наслідком формули

тоді і тільки тоді, коли

 
– загальнозначуща формула;
2) якщо формула

є логічним наслідком формули

, і формула

в даній
інтерпретації істинна, то і формула

є істинною в даній інтерпретації;
3) формули

і

рівносильні тоді і тільки тоді, коли

 
– загальнозначуща формула.
Відмітимо, що для формул логіки предикатів мають місце всі
рівносильності алгебри висловлень.

75
Окремим випадком формули А алгебри висловлень називається формула логіки предикатів, одержана з А підстановкою замість пропозиційних змінних довільних формул логіки предикатів.
Окремий випадок будь-якої тавтології алгебри висловлень
є загальнозначущою формулою (тавтологією) логіки предикатів. Наприклад, формула
)
(
)
(
x
xA
x
xA



тавтологія, бо є окремим випадком тавтології
p
p 
Аналогічно, рівносильність
)
(
)
(
x
xA
x
xA



формул логіки предикатів є окремим випадком закона подвійного заперечення алгебри висловлень
p
p 
Але крім цього є ще ряд рівносильностей, що стосуються операцій навішування кванторів істинності та загальності.
Теорема 3.3.2. Мають місце наступні рівносильності формул логіки предикатів:
1)
)
(
)
(
),
(
)
(
2 2
1 1
2 2
1 1
x
P
x
x
P
x
x
P
x
x
P
x






(перейменування зв’язаних змінних);
2)
)
(
)
(
,
)
(
)
(
x
P
x
x
xP
x
P
x
x
xP






(закони де Моргана для кванторів);
3)


)
(
)
(
)
(
)
(
2 1
2 1
x
P
x
P
x
x
xP
x
xP






,


)
(
)
(
)
(
)
(
2 1
2 1
x
P
x
P
x
x
xP
x
xP






;
4)


2 1
2 1
)
(
)
(
P
x
P
x
P
x
xP





,


2 1
2 1
)
(
)
(
P
x
P
x
P
x
xP





;
5)


2 1
2 1
)
(
)
(
P
x
P
x
P
x
xP





,


2 1
2 1
)
(
)
(
P
x
P
x
P
x
xP





;
Рівносильності 3)–5) мають назву пронесення кванторів через кон’юнкцію та диз’юнкцію.
6)


2 1
2 1
)
(
)
(
P
x
P
x
P
x
xP





,


2 1
2 1
)
(
)
(
P
x
P
x
P
x
xP





;
7)


)
(
)
(
1 2
1 2
x
P
P
x
x
xP
P





,


)
(
)
(
1 2
1 2
x
P
P
x
x
xP
P





Рівносильності 6)–7) мають назву пронесення кванторів через імплікацію.
Відмітимо наступне: рівносильності 4)-7) виконуються при умові, що
2
P
не містить вільних входжень змінної x.
Якщо виконуємо перехід від однієї формули до рівносильної їй формули, то такий перехід називається рівносильним перетворенням. Перетворюючи формулу за допомогою рівносильних перетворень, ми будемо або спрощувати її, або отримувати іншу, рівносильну їй формулу спеціального виду. Нижче ми розглянемо формули двох спеціальних видів – зведені та пренексні форми логіки предикатів.
Зведеною формою (ЗФ)для даної формули логіки предикатів називається така рівносильна їй формула, яка або елементарна, або містить лише операції заперечення, кон’юнкції, диз’юнкції, навішування кванторів існування та

76
загальності, причому заперечення стосуються лише елементарних підформул даної формули.
В логіці предикатів має місце наступна теорема.
Теорема 3.3.3. Для кожної формули логіки предикатів існує зведена форма.
Приклад 1. Знайти ЗФ для формули
)
(
)
,
(
2 2
2 2
1 1
1
x
P
x
x
x
P
x



Виконаємо наступні рівносильні перетворення:
).
(
)
,
(
)
(
)
,
(
)
(
)
,
(
2 2
2 2
1 1
1 2
2 2
2 1
1 1
2 2
2 2
1 1
1
x
P
x
x
x
P
x
x
P
x
x
x
P
x
x
P
x
x
x
P
x











Пренексною нормальною формою (ПНФ) або випередженою нормальною
формою (ВНФ) для даної формули логіки предикатів називається така її зведена форма, яка або не має операцій квантування, або вони виконуються останніми.
Тобто
ПНФ деякої формули логіки предикатів
)
(x

має вигляд:
}
,
{
,
2 1








k
x
x
x
, де

не містить операцій квантування і називається матрицею ПНФ
Теорема 3.3.4. Для кожної формули логіки предикатів існує пренексна нормальна форма.
Приклад 2. Знайти ПНФ (ВНФ) для формули
)
(
)
,
(
2 2
2 2
1 1
1
x
P
x
x
x
P
x



В попередньому прикладі ми знайшли ЗФ для даної формули. Застосуємо до неї закон пронесення квантора існування і отримаємо формулу


)
(
)
,
(
2 2
2 2
1 1
1
x
P
x
x
x
P
x



, яка ще не утворює ПНФ. У підформулі
)
(
2 2
2
x
P
x

, згідно рівносильності (1) виконаємо перейменування зв’язаної предметної змінної
2
x
в нову предметну змінну
3
x
. Отримаємо нову формулу


)
(
)
,
(
3 2
3 2
1 1
1
x
P
x
x
x
P
x



Тепер, згідно рівносильності (5), отримаємо


)
(
)
,
(
3 2
2 1
1 3
1
x
P
x
x
P
x
x



. Неважко переконатися, що це і є ПНФ для формули
)
(
)
,
(
2 2
2 2
1 1
1
x
P
x
x
x
P
x



При аналізі формул логіки предикатів на виконуваність зручно мати формулу, яка не містить кванторів існування, а її матриця представлена у кон’юнктивній нормальній формі (кнф). Вилучення кванторів існування із префікса ПНФ проводять за допомогою введення сколемівських сталих та
сколемівських функцій за правилом:
1. Знайти перший зліва на право квантор існування. Якщо він знаходиться у префіксі на першому місці, то замість змінної, яка зв’язана цим квантором, скрізь у матриці поставити деяку сколемівську сталу, яка у формулі ще не зустрічалась, а квантор існування видалити.

77 2. Якщо квантор існування не на першому місці префікса, наприклад
i
n
x
x
x
x




2 1
то замість змінної х
і
скрізь у матриці поставити деяку сколемівську функцію f(х
1
х
2
,...х
п
), яка у формулі ще не зустрічалась, а квантор існування видалити.
3.Перейти до пункту 1, аж поки не видалиться останній квантор існування.
У результаті таких перетворень отримується нова формула:
)
(
*
2 1
B
x
x
x
A
n
s




, яка називається сколемівською стандартною формою (ССФ).
Приклад
3.
Розглянемо покроково сколемізацію формули
))
,
(
)
,
,
(
)
,
(
(
t
v
R
w
v
z
Q
y
x
P
t
w
v
z
y
x
A









1. Замість х вводимо сталу а :
))
,
(
)
,
,
(
)
,
(
(
t
v
R
w
v
z
Q
y
a
P
t
w
v
z
y







;
2. Комбінація кванторів
v
z
y



читається «для довільних у та z існує і може трактуватись, як означення деякої функції. Після підстановки цієї функції у матрицю отримаємо нову формулу:
))
),
,
(
(
)
),
,
(
,
(
)
,
(
(
t
z
y
f
R
w
z
y
f
z
Q
y
a
P
t
w
z
y






;
3.Комбінація кванторів
t
w
z
y




рівносильна існуванню функції f=g(y,z,w).
Вилучаємо останній квантор
існування
і маємо
ССФ для
А:
)))
,
,
(
),
,
(
(
)
),
,
(
,
(
)
,
(
(
w
z
y
g
z
y
f
R
w
z
y
f
z
Q
y
a
P
w
z
y
A
s






У ССФ сколемівські функції і сталі вибираються довільно, тому у загальному випадку формули А та
s
A
не рівносильні. Але при дослідженні типу формули корисне твердження :
Теорема 3.3.5. Формула А є суперечністю тоді і тільки тоді, коли її сколемівська стандартна форма
s
A
є суперечністю.
Запитання для самоконтролю
1. Яка формула

називається логічним наслідком множини формул
}
,...,
,
{
2 1
n



?
2. Що таке силогізми? Як їх записують за допомогою категоричних суджень?
3. Які дві формули логіки предикатів називаються рівносильними?
4. Які рівносильності називають законами перейменування зв’язаних змінних?
5. Які рівносильності називають законами де Моргана для кванторів?
6. Які рівносильності називають законами пронесення кванторів?
7. Які рівносильності називають законами перейменування зв’язаних змінних?
8. Що називається зведеною формою (ЗФ) для даної формули логіки предикатів?
9. Що називається пренексною або випередженою нормальною формою (ПНФ,
ВНФ) для даної формули логіки предикатів?

78 10. Що називається сколемівською стандартною формою (ССФ)
для даної формули логіки предикатів?
11. Які алгоритми побудови рівносильних ЗФ та ПНФ для даної формули логіки предикатів?
12. В чому суть процесу сколемізації
формули логіки предикатів?
ВПРАВИ
3.21. Перевірити, чи правильно стоїть знак |= у співвідношеннях; a)
)
,
(
|
)
,
(
y
x
yP
x
y
x
yP
x





; b)
R
x
xP
R
x
P




)
(
|
)
(
; c)


)
(
|
)
(
)
(
)
(
x
R
x
P
x
R
x
P
x




; d)


)
(
)
(
|
)
(
)
(
x
xR
x
xP
x
B
x
P
x






3.22. Використовуючи поняття логічного наслідку, перевірити, чи будуть логічними такі міркування: a)
Ніхто не може розв’язати задачу не знаючи алгоритму розв’язку. Студент не розв’язав задачу. Отже студент не знає алгоритму розв’язку. b)
Будь-яка людина смертна. Вовк смертний. Отже вовк – людина. c)
Кожен студент за весь термін навчання пропускає хоч одну пару. Викладачі не поважають студентів, які пропускають пари. Отже викладачі не поважають всіх студентів. d)
Не всі алгебраїчні числа є раціональними. Всі раціональні числа – дійсні.
Отже, деякі алгебраїчні числа не належать до дійсних чисел. e)
Кожна нескінченна множина має зчисленну підмножину. Множина всіх
ірраціональних чисел нескінченна. Кожна множина має потужність не меншу, ніж будь-яка її підмножина. Отже потужність множини ірраціональних чисел не менша ніж зчисленна. f)
Деякі неперервні функції диференційовані в області їхнього означення.
Існують тригонометричні функції, які диференційовані в області їхнього означення. Отже, деякі тригонометричні функції неперервні. g)
Кожний математик мислить логічно. Той, хто мислить логічно, не робить логічних помилок. Іван робить логічні помилки. Отже, Іван – не математик.
3.23. Перевірити, чи існують наступні рівносильності: a)


)
,
,
(
)
,
(
)
,
,
(
)
,
(
z
y
x
Q
y
x
P
x
z
y
x
xQ
y
x
xP






; b)


)
(
)
,
(
)
(
)
,
(
z
Q
y
x
P
y
x
z
Q
y
x
yP
x







;

79
c)


)
,
,
(
)
,
(
)
,
,
(
)
,
(
z
y
x
Q
y
x
P
z
x
y
z
y
x
zQ
x
y
x
yP









; d)
)
,
,
(
)
,
,
(
z
y
x
P
x
y
z
y
x
xP
y





3.24. Побудувати зведені і пренексні нормальні форми та сколемівські стандартні форми для наступних формул логіки предикатів: a)


)
(
)
,
,
(
)
,
(
x
R
z
y
x
zQ
y
x
xP




; b)




)
,
,
(
)
(
)
,
(
z
y
x
zQ
y
y
yR
y
x
P
x
x







; c)


)
,
(
)
,
(
)
,
(
y
x
P
z
y
yQ
y
x
yP
x





; d)


)
(
)
(
)
,
(
x
xR
x
Q
y
x
yP
x





; e)


)
(
)
,
(
)
,
,
(
x
xR
z
y
zQ
z
y
x
yP
x






; f)




)
(
)
,
(
)
(
)
(
z
zR
y
x
Q
x
P
y
x
xP






3.25. Розв’язати наступні рівняння, системи рівнянь та нерівності, попередньо записавши відповідні їм формули: a)
0
)
3 2
)(
2
)(
1
(




x
x
x
; b)











;
0
)
3
)(
2
)(
1
(
,
0
)
2
)(
3
)(
1
(
y
x
x
x
y
x
x
x
c)
0 4
1 2
2



x
y
; d)









;
0 2
3
,
0 4
5 2
2
y
y
x
x
e)
0 9
)
3 2
)(
1
(
2




x
x
x
; f)
5 1 

x
; g)
8 6
2


 x
x
3.4. МЕТОД РЕЗОЛЮЦІЙ
Основна ідея методу резолюцій, який розглядається у логіці висловлень, зберігається і у логіці предикатів. Нагадаємо основні означення і факти.
Бінарною резольвентою
)
,
(
2 1
D
D
R
двох диз’юнктів
2 1
, D
D
називається диз’юнкція літералів, що залишається після видалення пари контрарних.
Наприклад, якщо
p
D 
1
,
q
p
D


2
то
q
D
D
R

)
,
(
2 1
. Тут резольвента є висновком, який отримується за правилом modus ponens з посилок р та
q
p 
Аналогічно резольвента
q
p
D



1
і
t
q
D


2
ілюструє правило силогізму:
t
p
D
D
R


)
,
(
2 1
. Отже, правило резолюцій є сильнішим з усіх схем логічного

80
висновку. Це випливає з теореми, яка справедлива у самому загальному випадку.