Лекции мат логика. Курс лекций по элементам математической логике Балашиха 2014 г 1

• Название: Курс лекций по элементам математической логике Балашиха 2014 г 1
• Анкор: Лекции мат логика
• Дата: 15.05.2022
• Размер: 0.79 Mb.
• Имя файла: logika_lekcii_1.pdf
• Тип: Курс лекций; #530181
• страница: 4 из 5

§4.2. Предикаты. Логические операции над предикатами Предикат (лат. praedicatum – сказанное) – то, что высказывается в суждении об объекте. Предикат отображает наличие того или иного признака у предмета. Другими словами, предикаты — отображения произвольных множеств во множество высказываний. Определение 4.1 Пусть x
1
,x
2
,…,x n
— символы переменных произвольной природы. Эти переменные будем называть предметными. Пусть наборы переменных (x
1
,x
2
,…,x n
) принадлежат множеству M=(M
1
,M
2
,…M
n
), которое будем называть предметной областью (те. x i

M
i
, где М называются областью определения переменной х i
). Предикатом местности n (местным предикатом, определенным на предметной области M, называют логическую функцию принимающую либо значение И либо значение Л. Пример 4.2.1. D(x
1
,x
2
) = Натуральное число х делится (без остатка) на натуральное число х — двуместный предикат, определенный на множестве пар натуральных чисел M=N

N. Очевидно, D(4,2) = И, D(3,5) = 0. Пример 4.2.2. Q(x) ==«x
2
<-1, х — одноместный предикат, определенный на множестве действительных чисел М. Ясно, что Q(-1) = Л,
Q(5) = Ли вообще предикат Q(x) — тождественно ложен, те Л для всех х. Пример 4.2.3. В(x,у,z) х х,у,z

R.» — трехместныйпредикат,
определенный на R
3
. Очевидно, что В(1,1,-2)=Л, В(1,1,2)=И.
Предикат Р, определенный на M, называется тождественно истинным, если он принимает значение И при любых значениях предметных переменных Предикат Р называется тождественно ложным, если он принимает значение Л

41 при любых значениях предметных переменных. Предикат Q из примера 4.2.2. является тождественно ложным. Поскольку предикаты — это функции со значениями во множестве высказываний, где введены логические операции, то эти операции естественно определяются и для предикатов. Пусть P и Q — предикаты, определенные на. Тогда
1.
)
x
,
,
x
,
x
(
P
)
x
,
,
x
,
x
(
P
n
2 1
n
2 1




2.
)
x
,
,
x
,
x
(
Q
)
x
,
,
x
,
x
(
P
)
x
,
,
x
,
x
)(
Q
P
(
n
2 1
n
2 1
n
2 1






3.
)
x
,
,
x
,
x
(
Q
)
x
,
,
x
,
x
(
P
)
x
,
,
x
,
x
)(
Q
P
(
n
2 1
n
2 1
n
2 1






4.
)
x
,
,
x
,
x
(
Q
)
x
,
,
x
,
x
(
P
)
x
,
,
x
,
x
)(
Q
P
(
n
2 1
n
2 1
n
2 Предикаты Р и Q, определенные на M, называются равносильными пишут Р, если P(x
1
,x
2
,…,x n
)=Q(x
1
,x
2
,…,x для любого набора (x
1
,x
2
,…,x n
) предметных переменных из Теорема 4.2.1 Множество местных предикатов, определенных на M, образует булеву алгебру предикатов. То, для них справедливы основные эквивалентности (см. §1.6).
§4.3. Кванторы. Логика предикатов Пусть P(x
1
,x
2
,…,x n
) — местный предикат, определенный на M. Зафиксируем x i
=a. Определим (местный предикат Q(x
1
,x
2
,…,x k-1
, x k+1
,x n
) следующим образом Q(x
1
,x
2
,…,x k-1
,x k+1
,x n
)=P(x
1
,x
2
,…,x k-1
,a,x k+1
,x n
). Говорят, что предикат Q(x
1
,x
2
,…,x k-1
, x k+1
,x n
) получен из предиката P(x
1
,x
2
,…,x n
) фиксацией значения й переменной x i
=a. Определение 4.3.1. Пусть Р(х) — одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое

xP(x) (читается для любого х
Р(х)»}, которое истинно тогда и только тогда, когда Р(х) — тождественно

42 истинный предикат. О высказывании

xP(x) говорят, что оно получено из предиката Р навешиванием квантора всеобщности попеременной х. Определение 4.3.2. Пусть Р(х) — одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое

xP(x) (читается существует х
Р(х)»), которое ложно тогда и только тогда, когда Р(х) — тождественно ложный предикат. О высказывании

xP(x) говорят, что оно получено из предиката Р навешиванием квантора существования попеременной х. Замечание 1. Обозначения

и

для кванторов — это перевернутые латинские буквы Аи Е соответственно, которые являются первыми буквами в английских словах All — все, Exist — существовать. Замечание 2. Высказывания можно считать предикатами, не содержащими переменных, те. местными предикатами (или предикатами любой местности. Пусть P(x
1
,x
2
,…,x n
) — местный предикат, определенный на M. Зафиксируем в нем значения переменных x
1
,x
2
,…,x k-1
,x k+1
,x n
. На полученный одноместный предикат Q(x к) навесим квантор всеобщности (существования, получим высказывание. Тем самым фиксированному набору значений переменных x
1
, x
2
,…, x k-1
, x k+1
, x n
с помощью квантора всеобщности существования) поставлено в соответствие высказывание. Говорят, что этот местный предикат переменных x
1
,x
2
,…,x k-1
,x k+1
,x n
получен из исходного предиката P(x
1
,x
2
,…,x n
) навешиванием квантора всеобщности (существования) пой переменной. Этот предикат обозначают

x к n
) (

x к n
)). Об й переменной (которой уже нет) говорят, что она связана квантором всеобщности (существования. Пример 4.3.1. Пусть D(x1,x2) = Натуральное число х делится (без остатка) на натуральное число х — двухместный предикат. Навесим последовательно на его переменные кванторы. Ясно, что
1)

x1

x2D(x1,x2)=0 2)

x2

x1D(x1,x2)=0 3)

x1

x2D(x1,x2)=1

43 4)

x2

x1D(x1,x2)=1 5)

x1

x2D(x1,x2)=1 6)

x2

x1D(x1,x2)=1 7)

x1

x2D(x1,x2)=0 8)

x1

x2D(x1,x2)=1. Теорема 4.3.1. Разноименные кванторы, вообще говоря, не коммутируют. Сравнение 7 ив последнем примере доказывает это утверждение. Алфавит логики предикатов содержит следующие символы
1) символы предметных переменных – обычно строчные латинские буквы с индексами или без них
2) символы предикатов – обычно прописные латинские буквы с индексами или без них
3) логические символы , &, ,
,

 
;
4) символы кванторов –
,
 
;
5) скобки и запятую. Слово в алфавите логике предикатов называется формулой, если оно удовлетворяет следующему индуктивному определению
1) Если P – символ предиката, x
1
, x
2
,..., x
n
– символы предметных переменных, то P(x
1
,x
2
,...,x
n
) – формула. Такая формула называется атомарной. Все предметные переменные атомарных формул свободные, связанных переменных нет.
2) Пусть A – формула. Тогда тоже формула. Свободные и связанные переменные формулы
A

– это соответственно свободные и связанные переменные формулы A.
3) Пусть A и B – формулы, причем нет таких предметных переменных, которые были бы связаны водной формуле и свободны в другой. Тогда
& ,
,
A
B A
B

,
A
B A
B

есть формулы, в которых свободные переменные формул A и B остаются свободными, а связанные переменные формул A и B остаются связанными.
4) Пусть A – формула, содержащая свободную переменную x. Тогда
,
xA
xA


тоже формулы, Переменная x в них связана. Остальные переменные, которые в формуле A свободны, остаются свободными, а переменные, которые

44 в формуле A связаны, остаются связанными. Говорят, что формула A есть область действия квантора.
5) Слово в алфавите логики предикатов 1–5 является формулой только в том случае, если это следует из правил 1–4. Заметим, что по определению формулы никакая переменная не может быть одновременно свободной и связанной. Обычно, связки и кванторы упорядочиваются по приоритету следующим образом

,

,

, &,

,

, Пример 4.3.2. Рассмотрим классический силлогизм Аристотеля Все люди смертны. Сократ – человек. Следовательно, Сократ – смертен. Пусть
( )
P x
– означает быть человеком,
( )
D x
– быть смертным, s – Сократ. Тогда данный силлогизм может быть представлен в виде следующей формулы

 

( )
( ) &
( )
( )
x P x
D x
P s
D Пример 4.3.3. Рассмотрим афоризм Козьмы Пруткова Нет столь великой вещи, которую не превзошла бы величиной большая. На множестве всех вещей введем предикат ( , )
P y x – вещь y больше вещи x . Тогда данный афоризм формально может быть записан так


( , )
x
yP y x
  Данный предикат эквивалентен
( , )
x yP y x
 
, что дает новую формулировку афоризму « Для любой вещи всегда найдется еще большая. Теорема 4.3.2. основные равносильности, содержащие кванторы) Имеют место следующие равносильности
1. Законы де Моргана
)
x
(
P
x
)
x
(
xP



,
)
x
(
P
x
)
x
(
xP



2. Коммутативность
)
y
,
x
(
xP
y
)
y
,
x
(
yP
x





,
)
y
,
x
(
xP
y
)
y
,
x
(
yP
x





3. Дистрибутивность
)
x
(
xQ
&
)
x
(
xP
))
x
(
Q
&
)
x
(
P
(
x




,
)
x
(
xQ
)
x
(
xP
))
x
(
Q
)
x
(
P
(
x






4. Ограничение действия кванторов

45
)
y
(
Q
)
x
(
xP
))
y
(
Q
)
x
(
P
(
x





,
)
y
(
Q
&
)
x
(
xP
)
y
(
Q
&
)
x
(
P
(
x



5. Для любого двухместного предиката
1
)
y
,
x
(
yP
x
)
y
,
x
(
xP
y






6.
( , )
( , )
xP x y
uP u y

 
,
( , )
( , )
xP x y
uP u y

 Пример 4.3.4. Определить таблицу истинности предиката
( , )
( , )
xP x у x у, где предикаты определены таблицами Решение. Очевидно, что
( , )
( , )
xP x у x у , ))
( , )
( , )
xP x у x уху есть двуместный предикат. Построим таблицу истинности предиката
1
( , )
( )
xP x у
у



:
)
А
(
1

=
)
А
,
x
(
xP

=0,
)
В
(
1

=
)
В
,
x
(
xP

=1,
)
С
(
1

=
)
С
,
x
(
xP

=0 те. Найдем значения ух 1
0
)
А
,
0
(
Q
)
А
(
)
А
,
0
(
1







;
0 0
0
)
А
,
1
(
Q
)
А
(
)
А
,
1
(
1







1 1
0
)
А
,
2
(
Q
)
А
(
)
А
,
2
(
1







,
;
1 0
1
)
В
,
0
(
Q
)
В
(
)
В
,
0
(
1







и т.д. для каждого значения из исходной таблицы истинности. Получим, таблицу истинности предиката , )
( , )
xP x у x у Формулы F и G равносильны (в логике предикатов, если они равносильны на всех множествах (обозначаетс: F=G).

46 Формулы, в которых из логических символов имеются только символы
{ ,&, }


, причем символ «

» отрицания встречается лишь перед символами предикатов, будем называть приведенными формулами. Для любой формулы существует равносильная ей приведенная формула, причём множества свободных и связанных переменных этих формул совпадают. Такая формула называется приведенной формой данной формулы. Приведенная формула называется пренексной нормальной (нормальной, если она не содержит символов кванторов или все символы кванторов стоят вначале формулы (те. логические символы и символы предикатов стоят в области действия каждого квантора. Известно, что для любой приведенной формулы существует равносильная ей нормальная формула той же длины. Такая формула называется нормальной формой данной приведенной формулы. Пример 4.3.5. С помощью законов равносильности логики предикатов, проверить будут ли равносильны следующие пары формул
 

( )
( )
x F x
G и
 
 
( )
( )
x F x
x G x

 Решение. 1) Рассмотрим
{5,6}
M

и предикаты F(x)={5 делится на x без остатка, x M

, G(x)={3 делится на x без остатка, x
M

. Тогда
 
( )
x F x

=1,
 
( )
x G x

=0, следовательно,
 
 
( )
( )
0
x F x
x G x

 Так как,
 
 
 
 
 

( )
( )
(5)
(5)
(6)
(6)
1 0
0 0
0 1 1
x F x
G x
F
G
F
G






  
   
, то можно заключить, что формулы неравносильны.
2) Приведем к пренексной нормальной форме
 
 
 
 
 
 
( )
( )
( ) &
( )
( ) &
( )
x F x
x G x
x F x
x G x
x F x
x G x

 
 

 


 
 
( ) &
( )
(
) ( ) & (
) ( )
u F u
v G v
x F x
x G x
 

 


 
 


( ) &
( )
(
)
( ) & ( )
u
F u
v G v
x F x
G x


 

 



  
(
)
( ) & ( )
( ) & ( )
x
u
v
F u
G v
F x
G x


 






47
 
  


( )
( )
( ) & ( )
( ) & ( )
x
F x
G x
x F x
G x
F x
G x


 


 
 
 
 
( ) & ( )
( ) & ( )
( ) & ( )
( ) & ( )
x F x
G x
x F x
G x
u F u
G u
x F x
G x
 
 
 
 

  
( ) & ( )
( ) & ( )
x
u
F u
G u
F x
G x


 Так как, пренексные нормальные формы не совпадают, то можно заключить, что формулы неравносильны. Глава V. Формальные теории
§5.1. Определение формальной теории Формальная теория (или исчисление

— это
1. множество A символов, образующих алфавит
1. множество F слов в алфавите A, F

A, которые называются формулами
3. подмножество B формул, B

F, которые называются аксиомами
4. множество отношений R на множестве формул, которые называются правилами вывода. Множество символов A может быть конечным или бесконечным. Обычно для образования символов используют конечное множество букв, к которым, если нужно, приписываются в качестве индексов натуральные числа. Множество формул F обычно задается индуктивным определением, например, с помощью формальной грамматики. Как правило, это множество бесконечно. Множества A ив совокупности определяют язык или сигнатуру формальной теории. Множество аксиом B может быть конечным или бесконечным. Если множество аксиом бесконечно, то, как правило, оно задается с помощью конечного множества схем аксиом и правил порождения конкретных аксиом из схемы аксиом.

48 Множество правил вывода R, как правило, конечно. Итак, исчисление

есть четверка (A, F, B, R). Выводом в исчислении

называется последовательность формул
F
1
,F
2
,…,F
n такая, что для любого k (1

k

n) формула F
k есть либо аксиома исчисления

, либо непосредственное следствие каких-либо предыдущих формул, полученное по правилу вывода. Формула G называется теоремой исчисления

(выводимой вили доказуемой в

), если существует вывод F
1
,F
2
,…,F
n
,G который называется выводом формулы G или доказательством теоремы G. Записывается это следующим образом
F
1
,F
2
,…,F
n
├ G. Исчисление

называется непротиворечивым, если не все его формулы доказуемы. Можно дать другое определение непротиворечивости Исчисление называется непротиворечивым, если в нем не являются выводимыми одновременно формулы F и

F (отрицание F). Исчисление

называется полным (или адекватным, если каждому истинному высказыванию М соответствует теорема теории Формальная теория

называется разрешимой, если существует алгоритм, который для любой формулы теории определяет, является ли эта формула теоремой теории

или нет. Интерпретацией формальной теории в область интерпретации называется функция I, которая каждой формуле формальной теории однозначно сопоставляет некоторое содержательное высказывание относительно объектов множества. Это высказывание может быть истинным или ложным. Если высказывание является истинным, то говорят, что формула выполняется в данной интерпретации. Интерпретация I называется моделью множества формул, если все формулы этого множества выполняются в интерпретации I. Интерпретация I называется моделью формальной теории, если все формулы этой теории выполняются в

49 интерпретации I (то есть все выводимые формулы оказываются истинными в данной интерпретации.