1
Министерство образования Российской федерации
Воронежский государственный университет
конспекты лекций и упражнения по курсу
МАТЕМАТИЧЕСКАЯ ЛОГИКА
/Логика предикатов/
пособие для студентов специальностей 01.03.01, 01.05.01, 02.03.01
Воронеж
2015
Стр.1
3
Оглавление
2. Логика предикатов ................................................................................................................ 4
2.1. Язык прикладной логики предикатов .................................................................................. 4
2.1.1. Элементы языка прикладной логики предикатов. ................................................... 4
2.1.2. Кванторы. Свободные и связанные переменные. .................................................... 5
2.1.3. Основные свойства кванторов. .................................................................................. 5
2.1.4. Ограниченные кванторы. ............................................................................................ 6
2.1.5. Упражнение. ................................................................................................................ 6
2.1.6. Пример формализации в языке прикладной логики предикатов. .......................... 7
2.1.7. Правило обобщения. ................................................................................................... 8
2.1.8. Упражнение. ................................................................................................................ 8
2.1.9. О формализации определений. .................................................................................. 9
2.1.10. Упражнение. ............................................................................................................ 10
2.2. Следствие в прикладной логике предикатов ..................................................................... 10
2.2.1. Применение правил общности. ................................................................................ 10
2.2.2. Обозначения сложных выражений. Ограниченные кванторы. ............................. 11
2.2.3. Пример с подстроками. ............................................................................................ 11
2.2.5. Обратное применение правил общности. ............................................................... 12
2.2.7. Квантор существования и единственности............................................................. 14
2.2.8. Упражнение. .............................................................................................................. 14
2.2.9. Упражнение. .............................................................................................................. 14
2.3. Основные теоремы логики предикатов .............................................................................. 14
2.3.1. Теорема о кванторах, отрицании, конъюнкции и дизъюнкции. ........................... 15
2.3.2. Теорема о кванторах и импликации. ....................................................................... 16
2.3.3. Упражнение. .............................................................................................................. 17
2.3.4. ЕА-формализация. ..................................................................................................... 17
2.3.5. Упражнение. .............................................................................................................. 18
2.3.6. О силлогизмах Аристотеля....................................................................................... 19
2.3.7. Упражнение. .............................................................................................................. 20
Литература ................................................................................................................................... 20
Стр.3
6
Правило (л) есть обобщение свойства дизъюнкции: если дизъюнкция ложна,
то ложны все ее операнды.
В правилах существования мы использовали нетрадиционный знак | , которому
мы придаем следующий смысл: если выполнено то, что написано
слева от него, то можно ввести в рассмотрение новую (т.е. не участвовавшую
ранее в данном рассуждении) константу n, для которой верно написанное
справа от этого знака. Например, если доказано, что уравнение
имеет хотя бы одно решение, т.е. ( )[ ( ) 0] , то можно обозначить новой
f ( ) 0x
x f x
для данного рассуждения буквой n одно из его решений (без уточнения того,
какое это именно решение) и в дальнейшем пользоваться истинным утверждением
f
( ) 0n
. Аналогично, если известно, что утверждение x f x 0
ложно, то можно ввести новую константу n, для которой f n( ) 0.
2.1.4. Ограниченные кванторы.
Как уже отмечалось, в логике предикатов действует соглашение о том, что
все предметные переменные имеют одну и ту же область изменения D. В математических
теориях часто рассматриваются объекты различной природы:
числа, множества, функции и т.п. Все они составляют единую предметную
область D, а если некоторый квантор должен относиться только к части этой
области, то на переменную, по которой он применяется, накладывают ограничение.
Пример:
N)[
n
( : 0) ( :nn
опр
x A x B x
x A x B x
( : ( )) ( ) ,
опр
( )[ ( )
( : ( )) ( )( )[ ( ) ( )] .
x A x B x( )]
x A x B x
Например, утверждение (6) в обычных кванторах принимает вид
1
N
n
( )[ 0 ( )[
2.1.5. Упражнение.
Записать данные формулы на обычном языке и определить, истинны ли они
в теории.
1. ( :
2. ( :a a
a a
3
4. ( :a a
a
. R
RN .
) ( :x x ax
a
x x
) ( :n n n x]
)[
RR .
( :
)[ 1 0]
6. RR .0]]
5
(c
. R R)[ 1 0]
2
)[ (x ax
)[ (x
RR .
(
) ( :x x ax
)[x x c
(y ay
0)[ ( :x x ax
)[ 1 0]
R)[ 1 0] ( :x x ax
R)[ 1 0]].
R)[ 1 0]] .
nn
]].
1
] .
(6)
Ограниченные кванторы не являются новыми логическими операциями;
они сводятся к обычным кванторам с помощью следующих определений:
( )[ ( ) ]
Стр.6
7
7.
9. 0] .
2
10. 0].
8. ( , )[
(a R R R)[
(a R R R)[
RR .
2
(a a: 0) (x ax x
( , ,
)[
R)[ 4
) (x
) (c
2
1 2
a b c b ac x x ax bx c ax bx c
22
1 0]
2
) (c ax x c
) (x ax x c
2.1.6. Пример формализации в языке прикладной логики предикатов.
Рассмотрим на следующем примере дополнения к процедуре формализации,
рассмотренной в 1.2.4 и 1.2.6. Эти дополнения относятся к таким формам
предложений, как “Для любого... выполнено...” и “Существует..., для
которого выполнено...” .
Для любых вещественных ,,
при некотором вещественном x.
Очевидно, утверждение “ 2
abc верно, что если ac то ax bx c
0,
ax bx c
0
2
0
можно без изменения смысла и логической формы преобразовать в “Существует
вещественное x, для которого 2
при некотором вещественном x”
ax bx c
0
язык прикладной логики предикатов дает формулу
) ( :c c ac
0]].
( :a a R) ( :b b R R)[ 0 ( :x x ax bx c
R)[
1 1x x2 ]]
1
0
2
2
2
0
”. Теперь перевод на
2
(7)
Группу следующих друг за другом одноименных кванторов часто записывают
в виде одного квантора по нескольким переменным. Кроме того, если это не
может вызвать недоразумений, в круглых скобках рядом с квантором не указывают
отдельно имя переменной, а пишут сразу предикат, ограничивающий ее
значения:
0]].
(a b c ac
,
,
a b c ac
,
,
R R R)[ 0 (x ax bx c
R)[
R)[
2
0].
R R R, 0 (x ax bx c
2
(8)
Если для записи данного предложения воспользоваться знаком следования в
теории, то квантор общности не нужен:
(9)
Напомним, это соотношение означает, что в любой интерпретации, в которой
истинны все аксиомы и определения теории вещественных чисел и посылки
данного умозаключения, будет истинным и заключение. Квантор
общности по всем a, b, c уже включен в эту формулировку. Формула (9) не
принадлежит языку прикладной логики предикатов, так как знак “” не
принадлежит алфавиту этого языка; он входит (как и знак логического следствия)
в метаязык логики, на котором изучаются предложения, написанные
на языке логики. Отметим, что для реального математического языка запись
(7) в виде (9) наиболее типична. Заметим также, что (9) эквивалентно тому,
что в данной теории истинна импликация
a 0].
R R R ac
b
c
0 (x ax bx c
R)[
2
(10)
Стр.7
8
Нетрудно видеть, что (7)| (10), но (10)| (7). Однако в следующем пункте будет
показано, что из истинности (10) в теории вытекает истинность в этой
теории утверждения (7).
2.1.7. Правило обобщения.
входит свободно в аксиомы и определения этой теории, то в ней истинно и
предложение ( ) ( )
Если в некоторой теории истинно предложение ()
z P z .
Для доказательства предположим, что последняя формула не является истинной,
т.е. не следует логически из аксиом и определений рассматриваемой
теории. Тогда найдётся такая интерпретация I аксиом, определений и предиката
P, в которой истинны аксиомы и определения, а утверждение ()
Pz
ложно хотя бы для одного значения zz0
мы получим интерпретацию z
()
из предметной области данной интерпретации.
Добавив
к интерпретации I интерпретацию переменной z как константы 0
I , в которой аксиомы и определения попрежнему
истинны (так как z в них не входит в свободном виде), а предложение
()
Pz , принявшее вид Pz , ложно. Но это противоречит тому, что
()0
Pz истинно. Утверждение доказано.
Чаще всего правило обобщения используется в следующей форме:
если для некоторой теории выполнено соотношение ( )
( )
.
z P z Q z( )]
P z Q z , причём
буква z не входит свободно в аксиомы и определения этой теории, то в ней
истинно предложение ( )[ ( )
Это утверждение есть непосредственное следствие правила обобщения, поскольку
из его условия, очевидно, вытекает истинность в данной теории импликации
( )
P z Q z .
( )
Например, из истинности утверждения (10) в теории вещественных чисел
(аксиомы и определения которой не содержат свободных вхождений букв
a,b,c) вытекает истинность в этой теории утверждения (7). Это обычный путь
доказательства утверждений вида (7): сначала вводят допущения, написанные
в левой части (9), затем из этих допущений-посылок выводят как следствие в
данной теории правую часть (9) и, наконец, делают вывод, что справедливо
(7). Правило обобщения есть формальное обоснование этой привычной и интуитивно
понятной методики доказательства утверждений с квантором общности.
2.1.8.
Упражнение.
Формализовать данный предикат в языке прикладной логики предикатов.
Определить, является ли он истинным.
1. Неравенство x2 0 справедливо для любого действительного x.
z ,
Pz , причём буква z не
Стр.8