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

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

– проекцію похилої АВ на площину α. Нехай пряма m, що лежить у площині α, перпендикулярна до СВ. Із означення перпендикуляра до площини (АСα) випливає, що АСm. Отже, пряма m перпендикулярна до прямих СВ і АС, що лежать у площині (АВС). Тоді m(АВС). Звідки mАВ.
Формальне доведення.
Аналіз доведення
1.
СВ=Пр
α
АВ; припущення;
2.
(СВ=Пр
α
АВ)

(АСα); з означення проекції;
3.
(АСα);
МР(1,2);
4.


m
; припущення;
5.
(АСα)





m
; правило введення

(ВК);
6.
(АСα)





m
AC
m




; з означення перпендикулярності прямої та площини;
7.
m
AC 
;
МР(5,6);
8.
BC
m 
; припущення;
9.

 

BC
m
AC
m



;
ВК(7,8);
10.

 





ABC
m
BC
m
AC
m





раніше доведена теорема;
11.


ABC
m 
;
МР(9,10);
12.


ABC
AB 
; аксіома;
13. (


ABC
m 
)




ABC
AB 

;
ВК(11,12);
14. (


ABC
m 
)






AB
m
ABC
AB




з означення;
15.
AB
m 
МР(13,14)
Запитання для самоконтролю
1. Яка формула називається А називається вивідною з множини формул Г? Що називається припущеннями або гіпотезами у цій вивідності?
2. Що називається виводом (формальним доведенням) з припущень та чому його відмінності з формальним виводом теорем числення висловлень L
1
?
3. Що таке метатеоріяданої формалізованої теорії? Як називаються її твердження?
4. Які властивості має вивідність з припущень у числення висловлень L
1
?

57 5. Сформулюйте метатеорему дедукції та її наслідки.
6. Які похідні правила виведення мають місце в численні висловлень L
1
?
ВПРАВИ
2.1
Виписати всі підформули заданої формули:


c
b
a
c
b
a





2.2
З’ясувати, чи буде слово формулою, використовуючи аналіз його структури (дерево аналізу):






b
a
c
b
a




(
2.3 Вказати приклади теорем числення висловлень L
1 з виводом довжини n, які одержані з аксіом заданої групи : a) застосуванням правила підстановки, п=3, група аксіом ІІ; b) застосуванням правил MP і підстановки п=4, групи аксіом ІІ і IV; c) застосуванням правил MP і підстановки п=4, групи аксіом ІІІ і I.
2.4
Побудуйте формальне доведення теорем теорії L
1
, користуючись лише основними правилами виводу: a)


a
a
a


; b)
a
a
a


; c)
a
a
a


; d)
a
a
b


; e)
c
c
a

 )
(
f)
a
b
b
a



; g)





 

b
b
a
; h)


b
b
a
a



2.5
Проаналізувати, чи є наступна послідовність формул доведенням для формули
b
a
b
a



?
1)
b
a
a


;
2)




a
b
b
a



;
3)






a
b
a
b
a
a





;
4)
a
b
a


;
5)
b
a
b


;
6)




b
b
a
b
a
b





;
7)
b
b
a


;

58 8)








c
b
a
c
a
b
a






;
9)

 
 



b
a
b
a
b
b
a
a
b
a









;
10)

 

b
a
b
a
b
b
a






;
11)
b
a
b
a



2.6
Обґрунтувати вивідність формул із припущень: a)


c
d
a
b
c
b
a




,
,
; b)
a
a
b
b
a


 ,
; c)


c
a
b
a
c
b
a




,
,
; d)
c
b
c
a
c
b
a




,
,
2.7
Встановити існування похідних правил виведення з метатеореми 2.2.3.
2.8
Використовуючи метатеорему дедукції, довести: a)








c
a
b
c
b
a






; b)








c
c
a
a
c
a






; c)










b
c
a
b
a
c
a







; d)






c
a
b
c
b





; e)

 

a
b
b
a




2.9 Навести змістовне доведення і побудувати формальне доведення теорем: a)
Сума кутів трикутника дорівнює 180 0
b)
Сума кутів опуклого п-кутника дорівнює 180 0
(п-2) c)
Дві прямі, паралельні третій прямій, паралельні між собою. d)
Діагоналі паралелограма в точці перетину діляться навпіл. e)
Якщо площина перпендикулярна до однієї з двох паралельних прямих, то вона перпендикулярна і до другої прямої. f)
Діагоналі ромба перетинаються під прямим кутом.

59
3. ЛОГІКА ПРЕДИКАТІВ
3.1. ПРЕДИКАТИ ТА ОПЕРАЦІЇ НАД НИМИ.
Нехай M – непорожня підмножина декартового добутку
n
M
M
M



2 1
деяких множин (n≥1).
n-місним предикатом, заданим на множині М, називається речення, що містить n змінних
n
x
x
x
,...,
,
2 1
, яке перетворюється на висловлення при підстановці замість цих змінних відповідних конкретних значень
n
a
a
a
,...,
,
2 1
, для яких
M
a
a
a
n

)
,...,
,
(
2 1
Тобто, на змістовному рівні, n-місний предикат – це відображення
}
0
,
1
{
:

M
P
від n змінних, яке приймає значення в множинні висловлень.
В подальшому викладі будемо використовувати наступні позначення:
)
,...,
,
(
2 1
n
x
x
x
P
– предикат;
n
x
x
x
,...,
,
2 1
– предметні змінні; елементи множин, що їх пробігають предметні змінні – предметні константи;
)
,...,
,
(
2 1
n
a
a
a
P
– значення
істинності предиката для відповідного набору елементів.
Відмітимо, що для кожного конкретного набору елементів з множини, на якій задано наш предикат, він перетворюється на висловлення, яке є або істинним
(тоді значення предиката для цього набору дорівнює одиниці), або хибним (тоді значення предиката для цього набору буде хибним). Також вкажемо, що не зменшуючи загальності міркувань, будь-яке висловлення будемо вважати 0- місним предикатом.
Приклад 1. Речення «х ділиться на 2 без остачі» є одномісним предикатом на множині натуральних чисел. Позначимо його
)
(x
P
. Тоді при підстановці замість х конкретних натуральних чисел будемо отримувати конкретні висловлення, які будуть або істині, або хибні. Так «4 ділиться на 2 без остачі» –
істинне висловлення, і тому
1
)
4
(

P
, а «3 ділиться на 2 без остачі» – хибне висловлення і
0
)
3
(

P
Приклад 2. Речення «
2 2
2
z
y
x


» є тримісним предикатом на множині цілих чисел. Позначимо його
)
,
,
(
z
y
x
P
. Тоді
1
)
5
,
4
,
3
(

P
, а
0
)
1
,
1
,
1
(

P
Предикат
)
,...,
,
(
2 1
n
x
x
x
P
, заданий на множині
n
M
M
M
M




2 1
, називається:
1) тотожно істинним, якщо для будь-якого набору предметних констант
M
a
a
a
n

)
,...,
,
(
2 1
він перетворюється в істинне висловлення, тобто
1
)
,...,
,
(
2 1

n
a
a
a
P
;

60 2) тотожно хибним, якщо для будь-якого набору предметних констант
M
a
a
a
n

)
,...,
,
(
2 1
він перетворюється в хибне висловлення, тобто
0
)
,...,
,
(
2 1

n
a
a
a
P
;
3) виконуваним, якщо
існує такий набір предметних констант
M
a
a
a
n

)
,...,
,
(
2 1
, для якого значення істинності
1
)
,...,
,
(
2 1

n
a
a
a
P
;
4) спростовним, якщо
існує такий набір предметних констант
M
a
a
a
n

)
,...,
,
(
2 1
, для якого значення істинності
0
)
,...,
,
(
2 1

n
a
a
a
P
Приклад 3. На множині дійсних чисел предикат «
1

 x
x
» є тотожно
істинним, а отже і виконуваним предикатом. На цій же множині предикат «
0

x
»
є виконуваним і спростовним предикатом одночасно. На множині натуральних чисел предикат «
x
x

 1
» є тотожно хибним, а отже і спростовним.
Множиною (областю) істинності предиката
)
,...,
,
(
2 1
n
x
x
x
P
, заданого на множині
n
M
M
M
M




2 1
, називається множина всіх наборів
M
a
a
a
n

)
,...,
,
(
2 1
, для кожного з яких
1
)
,...,
,
(
2 1

n
a
a
a
P
. Цю множину надалі позначатимемо
P
M
Відмітимо, що
M
M
P

Приклад 4. Розглянемо предикат «
0

x
» на множині дійсних чисел.
Множиною істинності цього предиката буде множина всіх невід’ємних дійсних чисел. Множиною істинності предиката «
0 2

x
», заданого на множині дійсних чисел, буде порожня множина, оскільки квадрат будь-якого дійсного числа завжди більший за нуль або дорівнює йому. Множиною істинності предиката
«
4

x
», заданого на множині натуральних чисел буде множина


3
,
2
,
1
Тепер розглянемо основні операції над предикатами. Далі будемо вважати, що предикати
)
,...,
,
(
2 1
n
x
x
x
P
і
)
,...,
,
(
2 1
n
x
x
x
Q
задано на одній і тій самій множині
n
M
M
M
M




2 1
Запереченням предиката
)
,...,
,
(
2 1
n
x
x
x
P
називається предикат, заданий на тій же множині, який перетворюється в хибне висловлення для будь-якого набору з множини істинності заданого предиката
)
,...,
,
(
2 1
n
x
x
x
P
, і в істинне – для всіх інших наборів значень предметних змінних, і позначається
)
,...,
,
(
2 1
n
x
x
x
P
Кон’юнкцією предикатів
)
,...,
,
(
2 1
n
x
x
x
P
та
)
,...,
,
(
2 1
n
x
x
x
Q
називається n-місний предикат (заданий на множині
n
M
M
M
M




2 1
), який перетворюється в
істинне висловлення для всіх тих і тільки тих значень змінних, при яких перетворюються в істинні висловлення обидва задані предикати.

61
Пропонуємо читачеві спробувати самостійно дати означення операцій диз’юнкції, імплікації та еквіваленції. Відмітимо лише, що вони означаються аналогічно до операції кон’юнкції.
Оскільки, в результаті однієї з операцій над предикатами P i Q утвориться новий предикат, то можна говорити про його множину істинності. Очевидно постає запитання, а чи можна якось пов’язати множину істинності результату з множинами істинності вихідних предикатів? Відповідь на це питання дає наступна теорема.
Теорема 3.1.1. Нехай предикати
)
,...,
,
(
2 1
n
x
x
x
P
і
)
,...,
,
(
2 1
n
x
x
x
Q
задано на одній
і тій же множині
n
M
M
M
M




2 1
, і нехай предикат
)
,...,
,
(
2 1
n
x
x
x
R
утворюється внаслідок однієї з логічних операцій, тоді для множини істинності предиката R справедливі наступні рівності:
1)
P
R
M
M
M
\

, якщо
P
R 
;
2)
Q
P
R
M
M
M


, якщо
Q
P
R


;
3)
Q
P
R
M
M
M


, якщо
Q
P
R


;
4)
)
\
(
\
Q
P
R
M
M
M
M

,
Q
P
R


;
5)






Q
P
Q
P
R
M
M
M
M
M
M




\
, якщо
Q
P
R


Доведення цієї теореми нескладне, і випливає з означення логічних операцій над предикатами та означення і властивостей операцій над множинами.
Приклад 5. Розглянемо два одномісні предикати задані на множині натуральних чисел. Предикат
)
(x
P
означає «х ділиться на 2», предикат
)
(x
Q
– «х ділиться на 3». Множинами істинності цих предикатів очевидно будуть множини


)
2
(
)
(
|

x
N
x
x
M
P



і


)
3
(
)
(
|

x
N
x
x
M
Q



. Нехай
)
(x
R
результат однієї з логічних операцій, виконаних над предикатами
)
(x
P
і
)
(x
Q
. Тоді множина
істинності предикату
)
(x
R
буде мати наступний вигляд, в залежності від операції:
1)


)
2
(
)
(
|

x
N
x
x
M
R



, якщо
P
R 
;
2)


)
6
(
)
(
|

x
N
x
x
M
R



, якщо
Q
P
R


;
3)




)
3
(
)
2
(
)
(
|


x
x
N
x
x
M
R




, якщо
Q
P
R


;
4)




)
3
(
2
(
)
(
|


x
x
N
x
x
M
R




, якщо
Q
P
R


;
5)




)
3
(
)
2
(
)
6
(
)
(
|



x
x
x
N
x
x
M
R





, якщо
Q
P
R


В логіці предикатів використовують ще так звані операції зв’язування квантором (операції квантифікації або квантування).

62
Зв’язування квантором загальності за змінною
i
x
називається логічна операція, яка кожному n-місному предикату
)
,...,
,
(
2 1
n
x
x
x
P
, заданому на множині
n
M
M
M
M




2 1
, ставить у відповідність (n-1)-місний предикат, що позначається
)
,...,
,..,
(
1
n
i
i
x
x
x
P
x

, і який перетворюється в істинне висловлення при підстановці замість
k
x
будь-яких конкретних значень
)
1
,
(
n
k
i
k
M
a
k
k




тоді і тільки тоді, коли одномісний предикат
)
,...,
,..,
(
1
n
i
a
x
a
P
тотожньо істинний на множині
i
M
По іншому це можна записати так







)
,...,
,...,
(
,
0
;
)
,...,
,...,
(
,
1
)
,...,
,...,
(
1 1
1
предикат
й
спростовни
a
x
a
P
якщо
предикат
істиний
тотожно
a
x
a
P
якщо
x
x
x
P
x
n
i
n
i
n
i
i
Зв’язування квантором існування за змінною
i
x
називається логічна операція, яка кожному n-місному предикату
)
,...,
,
(
2 1
n
x
x
x
P
, заданому на множині
n
M
M
M
M




2 1
, ставить у відповідність (n-1)-місний предикат, що позначається
)
,...,
,..,
(
1
n
i
i
x
x
x
P
x

, і який перетворюється в хибне висловлення при підстановці замість
k
x
будь-яких конкретних значень
)
1
,
(
n
k
i
k
M
a
k
k




тоді і тільки тоді, коли одномісний предикат
)
,...,
,..,
(
1
n
i
a
x
a
P
тотожно хибний на множині
i
M
Інакше кажучи,







)
,...,
,...,
(
,
1
;
)
,...,
,...,
(
,
0
)
,...,
,...,
(
1 1
1
предикат
й
виконувани
a
x
a
P
якщо
предикат
хибний
тотожно
a
x
a
P
якщо
x
x
x
P
x
n
i
n
i
n
i
i