Галуев Г.А. Математическая логика и теория алгоритмов
Подождите немного. Документ загружается.
Математическая Логика и Теория Алгоритмов стр. 21 из 64
© 2003 Галуев Геннадий Анатольевич
(индивидные) переменные X
1
,...,X
n
,..., предметные (индивидные) константы а
1
,…,а
n
,…,
функциональные буквы
k
n
1
1
f,...,f , а также указанные выше кванторы ∀ и ∃.
Предикатные
k
n
1
1
A,...,A и функциональные
k
n
1
1
f,...,f буквы могут иметь аргументы,
которые в этом случае указываются справа от них в скобках (
)X(A ,)X(f
1
1
2
2
). Аргумен-
ты отделяются друг от друга запятой (
)Y,X(A
2
1
). Количество аргументов определяет
верхний индекс
)X,X,X,X(A ,)Z,Y,X(f
4321
4
2
3
1
, а нижний индекс используется для инди-
видуализации предикатных и функциональных букв.
Из функциональных букв (
k
n
f ), предметных переменных (X
1
,...,X
n
) и констант
(а
1
,…,а
n
) могут быть построены термы. Дадим индуктивное определение терма.
a) Всякая предметная переменная (X
i
) или константа (а
i
) есть терм.
b) Если
k
n
f функциональная буква и t
1
,...,t
k
– термы, то )t,...,t(f
k1
k
n
тоже есть
терм.
c) Выражение является термом тогда и только тогда, когда это следует из a) и
b).
Из предикатных букв и термов можно получать элементарные формулы. Так если
k
n
A предикатная буква, t
1
,...,t
k
термы, то )t,...,t(A
k1
k
n
- элементарная формула.
Формулы исчисления предикатов определяются так:
a) Всякая элементарная формула есть формула.
b) Если А и В формулы и y – предметная переменная, то каждое из выраже-
ний (⎤А), (А→В), (∀yA), (∃yB) – есть формулы.
c) Выражение является формулой лишь тогда, когда оно получено в соответ-
ствии с a) и b).
В выражениях
(∀yA) и (∃yА) формула А называется областью действия соответст-
венно кванторов ∀y и ∃y.
Будем придерживаться введённого в исчислении высказываний соглашения о
более экономном употреблении скобок. Будем считать, что кванторы ∀y и ∃y распола-
гаются между связками
∨
¬
,&,
и связками
↔
→,
(т.е.
↔
∃
→
¬
∀ ,&
и т.д.)
Вместо выражения
(
)
(
)
(
)
(
)
21
2
21
1
11
, xxAxAx →∀ можно использовать запись
() ( )
21
2
21
1
11
, xxAxAx →∀ , т.е. можно убрать внешние скобки. При восстановлении скобок
связки анализируются последовательно в порядке
↔
→
∃
∀
∨
¬
,,,,,&, , и область дейст-
вия из этих операторов вместе с ним заключается в скобки. Для операторов
∃
∀
¬
,,
область действия располагается справа от оператора и либо выделяется скобками,
либо нет, если это наименьшая формула с учетом уже расставленных скобок. Для
операторов
,,,&, ↔→∨ области действия располагаются с обеих сторон от каждого из
них и заключается в скобки аналогичным образом.
Рассмотрим на примере процесс восстановления скобок для правильного чтения
и анализа формул.
Пусть задано выражение:
x∀ y⎤∀ z∀
()
(
)
(
)
(
)()
yDyxyBxyxCyxBzyxA
↔
∃
∀
→∨ ,,&,,,
Восстановим скобки:
1.
()
()
()
(
)
(
)
(
)
yDyxByxyxCyxBzyxAzyx ↔∃∀→∨∀⎤∀∀ ,,&,,,
2.
()
()
()
(
)()
(
)
(
)
yDyxByxyxCyxBzyxAzyx ↔∃∀→∨∀⎤∀∀ ,,&,,,
3.
()
()
()
(
)()
()
(
)
(
)
yDyxByxyxCyxBzyxAzyx ↔∃∀→∨∀⎤∀∀ ,,&,,,
4.
()()()
()()
()
(
)()
()
(
)
(
)()
yDyxByxyxCyxBzyxAzyx ↔∃∀→∨∀∀⎤∀ ,,&,,,
5.
()()()
()()
()
(
)()
()
(
)
(
)
(
)()
yDyxByxyxCyxBzyxAzyx ↔∃∀→∨∀∀⎤∀ ,,&,,,
6.
()()()
()()
()
(
)()
()
(
)
(
)
(
)
()
()
yDyxByxyxCyxBzyxAzyx ↔∃∀→∨∀∀⎤∀ ,,&,,,
7.
(
)()()
()()
(
)
(
)
(
)
()
()
(
)
(
)
()
(
)
()
yDyxByxyxCyxBzyxAzyx ↔∃∀→∨∀∀⎤∀ ,,&,,,
Математическая Логика и Теория Алгоритмов стр. 22 из 64
© 2003 Галуев Геннадий Анатольевич
Введение кванторов в формулу разбивает множество входящих в нее перемен-
ных на два подмножества: свободных
и связанных переменных. Определим эти поня-
тия.
Вхождение переменной X в данную формулу называется связанным, если X яв-
ляется переменной входящего в эту формулу квантора
x
∀
или
x
∃ или находится в
области действия входящего в формулу квантора; в противном случае вхождение пе-
ременной в формулу называется свободным.
Отметим, что одна и таже переменная может входить в формулу несколько раз
и в одном случае вхождение этой переменной может быть связанное а, в другом –
свободное.
Переменная называется свободной (связанной) если
в данной формуле суще-
ствуют только свободные (связанные) ее вхождения.
В рассмотренном выше примере (расстановка скобок в формуле) переменная X
имеет связанное вхождение, а переменная Y и связанное и свободное.
Понятие свободной и связанной переменных широко используется в математи-
ке. Выражение, содержащее свободную переменную, зависит от значения этой пере-
менной, а выражение, содержащее
связанную переменную, представляет результат
операции, примененной к области изменения этой переменной.
Например в выражении
∑
=
n
i
i
a
1
n – свободная переменная
i - связанная переменная
i
a - константа
Связанную переменную можно не меняя смысла и конечного результата заме-
нить на любую другую, имеющую ту же область изменения, например:
∑
=
n
j
j
a
1
.
Если в выражении подставить вместо свободной переменной какое-либо ее
конкретное значение из области ее изменения, то мы как правило получим осмыс-
ленный, конкретный результат, но эта же операция, примененная к связанной пере-
менной приводит к бессмыслице.
Например:
∑
=
4
1i
i
a
∑
=
n
i
a
1
4
Если одна и таже переменная входит в выражение и как свободная, и как свя-
занная, то представляемая этим выражением величина зависит только от значения
этой переменной в ее свободных вхождениях.
Приведенные результаты справедливы и для логических операций
xиx
∃
∀ , ко-
торые связывают соответствующие переменные (в данном случае переменную X).
Применение кванторов к формулам называется операцией квантификации или
навешивание кванторов. Нам потребуется далее операция подстановки.
Операция подстановки терма t вместо переменной X в формулу A состоит в од-
новременной замене каждого свободного вхождения X в A на вхождение t.
Если формула A зависит от X, то этот факт обычно
обозначается как A(x). Ре-
зультат подстановки t вместо X в A(x) записывается в виде A(t).
Операция подстановки, которая дает A(t) всегда должна производиться вместо
первоначальной переменной X в первоначальной формуле A(x).
Например: пусть A(x) есть
(
)
(
)
xcxSR ,, , тогда A(t) есть
()()
tctSR ,, ; а A(c)
есть
()()
cccSR ,, . Если подставить t не в первоначальную формулу A(x) а в A(c) вместо
C, то получим A(t) есть
()()
tttSR ,,
, что не совпадает с первоначальным A(t) есть
()()
tctSR ,, .
Математическая Логика и Теория Алгоритмов стр. 23 из 64
© 2003 Галуев Геннадий Анатольевич
Если X не является свободной переменной формулу A(x), то результат опера-
ции подстановки A(t) есть само первоначальное выражение A(x).
Если требуется в некоторой формуле A одновременно произвести подстановку
вместо переменных
n
xx ,,
1
K соответственно термов
n
tt ,,
1
K , то исходную формулу бу-
дем обозначать
()
n
xxA ,,
1
K , а результат подстановки -
(
)
n
ttA ,,
1
K .
Будем говорить, что терм t свободен для переменной x в A(x), если никакое
свободное вхождение x в A(x) не входит в область действия какого-нибудь квантора
y∀ или
y
∃ , где y – переменная, входящая в терм t.
Будем говорить, что подстановка
t вместо
x
в )(xA свободна, если t свободен для
x
в
)(xA
.
Отметим, что :
А) всякий терм, не содержащий переменных, свободен для любой переменной в
любой формуле;
б) терм
t свободен для любой переменной в формуле A , если никакая перемен-
ная терма
t не является связанной переменной в
A
;
в)
i
x свободно для
i
x в любой формуле;
г) всякий терм свободен для
i
x в
A
не содержит свободных вхождений
i
x .
Лекция №5
Интерпретация формул в исчислении предикатов.
Выполнимость формул.
Аксиоматическое построение исчисления предикатов.
Предваренные нормальные формулы.
В исчислении высказываний интерпретация формул есть приписывание пропози-
ционным буквам, входящим в формулу, истинностных значений (истина, ложь). Для
определения интерпретации формулы исчисления предикатов нужно указать пред-
метную область (область значений предметных переменных) и значения констант,
функциональных и предикатных символов, встречающихся в формуле.
Дадим определение интерпретации
.
Под интерпретацией
будем понимать всякую систему, состоящую из непустого
множества
D , называемого областью интерпретации и какого-либо соответствия, от-
носящегося каждой предикатной букве
n
j
A некоторое отображение
n
D во множество
{1,0}, каждой функциональной букве
k
j
f некоторую функцию (отображение)
k
D в D и
каждой предметной константе
i
a - некоторый элемент D . При заданной интерпрета-
ции предметные переменные
1
x , …,
n
x , … мыслятся пробегающими область D этой
интерпретации, а логическим связкам
→,&,v
и т.д. и кванторам
∃∀,
придается их
обычный смысл.
Для данной интерпретации всякая формула без свободных переменных (замк-
нутая формула) представляет собой высказывание, которое имеет некоторое опреде-
ленное истинностное значение (истина или ложь). Всякая формула со свободными
переменными есть истинностная функция этих переменных, определенная на области
интерпретации; при этом для некоторых значений предметных переменных
n
xx,..., эта
функция принимает значение 1, а для других – 0.
Введем понятие выполнимости
и истинности формулы в исчислении предика-
тов.
Определим предварительно одноместную функцию
*
S со значениями из D и оп-
ределенную на множестве всех термов
t , если задана последовательность
,...),(
21
bbS = элементов из D и некоторая интерпретация I.
Математическая Логика и Теория Алгоритмов стр. 24 из 64
© 2003 Галуев Геннадий Анатольевич
Если терм t есть предметная переменная ,
i
x то ;)(
*
bitS = если терм t есть пред-
метная константа, то
)(* tS совпадает с интерпретацией этой константы в D ; если
n
f функциональная буква, интерпретируемая операцией ,
g
и
n
tt ,...,
1
термы, то
))(*),...,(*()),...,((*
11 nn
n
j
tStSgttfS = .
Таким образом,
*S
- функция, определяемая последовательностью
S
и интер-
претацией I и отображающая множество всех термов в
D . Иными словами, для любой
последовательности
,...),(
21
bbS = и для любого терма t величина )(* tS есть элемент
множества
D , который получается в результате подстановки при каждом
i
элемента
i
b на места всех вхождений переменной
i
x в терм t и затем выполнения всех операций
интерпретации, соответствующих функциональным буквам терма
t .
Например, если
t есть )),(,(
1
daDcS и
,...),(
21
bbS
=
, областью интерпретации слу-
жит множество действительных чисел,
1
S интерпретируется как сложение, а D - как
умножение, то
)(* tS представляет число
413
*bbb
+
(в предположении, что переменные
dcba ,,, упорядочены по алфавиту).
Так как все логические операции могут быть выполнены через базис
,, →⎤ а
кванторы
x
∃ и
x∀
связаны соотношением
x
∃
x∀
есть ))(( xAx
¬
∀¬ ,
то можно дать следующее индуктивное определение того, что формула
A вы-
полнена на последовательности
,...),(
21
bbS = из
∞
D при данной интерпретации I:
o
•
1 Если
A
есть элементарная формула
),...,(
1 n
n
j
ttA
и
n
j
B
есть соответствующее ей отображение в интерпретации, то фор-
мула
A
считается выполненной на последовательности S в том и только в том случае,
когда
1))(*),...,(*(
1
=
n
n
j
tStSB .
o
•
2 Формула
A⎤
выполнена на
S
тогда и только тогда, когда формула A не
выполнена на
S .
o
•
3
BA →
выполнена на
S
тогда и только тогда, когда A не выполнена на
S или когда формула
B
выполнена на S .
o
•
4 Формула Ax
i
∀ выполнена на S тогда и только тогда, когда формула
A
вы-
полнена на любой последовательности из
∞
D , отличающейся от
S
не более чем своей
i компонентой.
Таким образом, формула
A выполнена на последовательности ,...),(
21
bbS = тогда
и только тогда, когда подстановка при каждом
i символа, представляющего
i
b , на
места всех свободных вхождений
i
x в
A
приводит к истинному в данной интерпрета-
ции I предложению.
Формула
A называется истинной (в данной интерпретации) тогда и только то-
гда, когда она выполнена на всякой последовательности из
∞
D .
Формула
A
называется ложной (в данной интерпретации) если она не выполне-
на ни на одной последовательности из
∞
D .
Данная интерпретация называется моделью для данного множества формул Г,
если каждая формула из Г истинная в данной интерпретации.
Формула
A называется логически общезначимой (в исчислении предикатов),
если она истинна в каждой интерпретации.
Формула
A называется выполнимой (в исчислении предикатов), если существу-
ет интерпретация, в которой
A выполнима (в смысле введенного выше определения)
хотя бы на одной последовательности из
∞
D .
Математическая Логика и Теория Алгоритмов стр. 25 из 64
© 2003 Галуев Геннадий Анатольевич
Будем называть формулу
A
противоречием (в исчислении предикатов), если
формула
A⎤ является логически общезначимой (т.е. формула A ложна во всякой ин-
терпретации):
Говорят, что формула
A
является логическим следствием (в исчислении преди-
катов) множества формул Г, если во всякой интерпретации формула
A выполнена на
каждой последовательности, на которой выполнены все формулы из Г.
Формулы называются логически элементарными (в исчислении предикатов),
если каждая из них является логическим следствием другой.
С учетом введенных понятий и определений перейдем к изложению аксиомати-
ческого построения исчислений предикатов.
Аксиоматическое построение исчисления предикатов.
Теории первого порядка. Исчисление предикатов первого порядка.
В исчислении высказываний изучение таблиц истинности пропозиционных форм
дает эффективный метод проверки, является ли данная формула тавтологией (обще-
значимой, тождественно истинной – т.е. истинной при любых значениях пропозици-
онных букв). В исчислении предикатов, где предметные области могут быть беско-
нечны, аналогичный подход неприемлем. Здесь возникает необходимость в аксиома-
тизации и
построении соответствующей теории. Рассматриваемые далее теории отно-
сятся к так называемым теориям первого порядка, в которых не допускаются, напри-
мер, такие конструкции как предикаты, аргументы которых в свою очередь являются
предикатами.
Символами всякой теории К первого порядка служат: пропозиционные связ-
ки
→⎤, ; знаки ),(, ; предметные переменные ,...,....,,
21 n
xxx ; предикатные буквы
)1,( ≥jnA
n
j
; функциональные буквы )1,( ≥jnf
n
j
; предметные константы )1( ≥ia
i
.
Функциональные буквы и предметные константы в некоторых теориях могут и
отсутствовать.
Введенные ранее определения терма и формулы, а также определения связок
,,&, ↔V через →⎤, :
BA& есть
)( BA ¬→⎤
B
A∨ есть
BA →⎤
BA ↔ есть
)(&)( ABBA →→
остаются в силе.
Аксиомы каждой теории К первого порядка разбиваются на два класса: логиче-
ские аксиомы и собственные (нелогические) аксиомы.
К логическим аксиомам теории первого порядка относятся следующие:
1.
)( ABA →→
2.
))()(()(( CABACBA →→→→→→
3.
))(()( BABAB →→⎤→→⎤⎤
4.
)()( tAxAx
ii
→∀ ,
где
)(
i
xA - это формула теории
K
и t есть терм, свободный для
i
x в )(
i
xA .
5.
)()( BxABAx
ii
∀→→→∀ , если формула A не содержит
i
x свободно.
Здесь
CBA ,, - произвольные формулы.
Собственные аксиомы меняются от теории к теории и не могут быть сформули-
рованы в общем виде. Теория первого порядка, не содержащая собственных аксиом,
называется исчислением предикатов первого порядка
.
Правилами вывода во всякой теории являются правило
MP
B
BAA →,
,
Математическая Логика и Теория Алгоритмов стр. 26 из 64
© 2003 Галуев Геннадий Анатольевич
и правило обобщения (сокращенно Gen от английского слова Generalization)
Ax
A
i
∀
.
Моделью теории первого порядка называется всякая интерпретация, в которой
истинны все аксиомы этой теории. Нетрудно показать, что если правила
MP
и Gen
применяются к истинным в данной интерпретации формулам, то результатом являют-
ся формулы, также истинные в этой интерпретации. Следовательно, всякая теорема
теории истинна во всякой ее модели.
Существует также доказательство того, что множество логических следствий
выбранных аксиом теории K в точности совпадает с множеством теорем теории К. В
частности, для исчисления предикатов
первого порядка множество его теорем совпа-
дает с множеством всех логически общезначимых формул (тождественно истинных
формул, тавтологий).
Отметим необходимость ограничений в схемах аксиом 4 и 5.
Если отказаться от ограничения из схемы 4, то можно получить следующее:
Пусть
)(
1
xA
есть ),(
21
2
12
xxAx⎤∀ и t есть
2
x
. Видно, что при этом терм t не свободен для
1
x в )(
1
xA .
Тогда частный случай схемы 4 таков:
)())((
21
2
1221
2
121
xxAxxxAxx →⎤∀⎤∀∀ )(
∗
В качестве интерпретации взамен, например, множество целых чисел и
2
1
A - от-
ношение равенства т.е.
,1)(
21
2
1
=xxA если
21
xx
=
. Тогда посылкав )(∗ (т.е. выражение
перед знаком
→) истина, а заключение (выражение после знака → в )(∗ ложно, по-
этому вся импликация
)(∗ имеет значение ложь (0).
В случае схемы 5 отказ от ограничений также приводит к неприятным послед-
ствиям. Если
A
и
B
есть
11
1
1
)(( xxA входит свободно), то частный случай схемы аксиом 5
таков
))()(())()((
1
1
111
1
11
1
11
1
11
xAxxAxAxAx ∀→→→∀ )(
∗
∗
Нетрудно убедиться, что (**) имеет значение 0 (ложь), если
)(
1
1
1
xA выполнено
для некоторых, но не для всех
1
x из предметной области.
Предваренные нормальные формы в исчислении предикатов.
В исчислении предикатов аналогично исчислению высказываний применяются
нормальные формы. Предваренные нормальные формы используются в исчислении
предикатов для упрощения процедур доказательств.
Говорит, что формула
A
исчисления предикатов находится в предваренной
нормальной форме тогда и только тогда, когда формула имеет вид
MxQxQxQ
nn
...
2211
, )(
∗
где каждое
ii
xQ есть или
i
x∀ или
i
x
∃
;,...,1 ni
=
M
- формула не содержащая кванторов.
nn
xQxQ ....
11
- называют префиксом, а
M
- матрицей формулы
A
Приводятся формулы к виду (*) с помощью эквивалентных преобразований,
в результате чего получаются новые формулы, логически эквивалентные первона-
чальным.
Для эквивалентных преобразований используются законы, установленные
теоремой (см. 2.1 – 2.10) для пропозиционных связок, а также следующие, специ-
фические для исчисления предикатов, соотношения:
Математическая Логика и Теория Алгоритмов стр. 27 из 64
© 2003 Галуев Геннадий Анатольевич
GxQxFGxQxF ∨↔∨ )())((
(5.1)
GxQxFGxQxF &)(&))(( ↔
)()( xFxxxF ⎤∃↔⎤∀
(5.2)
)()( xFxxxF ⎤∀↔⎤∃
Здесь
F
формула, содержащая переменную
x
свободно, G - формула, не содер-
жащая переменную
x
.
Законы (5.1), очевидно, истинны, т.к. формула
G не содержит переменную
x
и
поэтому может быть внесена в область действия соответствующего квантора. Приве-
дем еще два закона исчисления предикатов.
)(&)())((&))(( xHxxFxxHxxF ∀
↔
∀∀
(5.3)
)()())(())(( xHxxFxxHxxF ∨∃
↔
∃∨∃
Из законов 5.3 видно, что кванторы
∀
и
∃
можно распределить по & и V соот-
ветственно, т.е. операция навешивания квантора
)( xx
∃
∀
дистрибутивна относительно
операций &(V).
Однако следует знать, что сами кванторы
x
∀
и
)( x
∃
не дистрибутивны относи-
тельно операций V и & , т.е. неверно, что
)()())(())(( xHxxFxxHxxF ∨∀
↔
∀∨∀
(5.4)
)(&)())((&))(( xHxxFxxHxxF ∃
↔
∃∃
В случае, подобном (5.4), следует одну связанную переменную переименовать
в другую, например в Z, после чего воспользоваться законами (5.1).
(
)()())(())(())(())( zHxzFxzzHxxFxxHxxF ∨
∀
∀
↔
∀
∨∀
↔
∀∨∀ (5.5)
(
)(&)())((&))(())((&))( zHxzFxzzHxxFxxHxxF
∃
∃
↔
∃
∃
↔
∃∃ (5.6)
В 5.5, 5.6 предполагается, что формула
)(xF не зависит от переменной Z.
Используя законы (z.1 – z.10), (5.1), (5.2), (5.3), (5.5) и (5.6) любую формулу
исчисления предикатов можно перевести в предваренную нормальную форму. Для
этого формулы приводятся к виду, содержащему только связки &,
¬,V и кванторы;
операции инверсии с помощью законов Де Моргана (z.6) и закона двойного отрица-
ния (z.1) проносят внутрь формулы, после чего кванторы группируются в начале
формулы с помощью законов (5.1)-(5.3), (5.5) и (5.6). Свободные переменные при
этом трактуются как константы.
Приведем пример такого преобразования:
Пусть формула А имеет вид
)()( xxQxxP ∃→⎤∀
из исходной формулы последовательно получаем
⎤
↔∃∀⎤ )())(( xxQVxxP
(по 2.10)
↔∃∀↔ )())(( xxQVxxP (по 2.1.)
↔∃∀↔ ))(())(( xxQVxxP
замена связанной переменной
x
и
z
.
Математическая Логика и Теория Алгоритмов стр. 28 из 64
© 2003 Галуев Геннадий Анатольевич
↔∃∀↔ )))(()(( zzQVxPx
по (5.1.)
)()( zVQxzPx∃∀↔ по (5.1)
Последняя формула и есть предваренная нормальная форма исходной формулы.
Основным применением исчисления предикатов также как и исчисления выска-
зываний является доказательство теорем. Рассмотрим этот вопрос.
Лекция №6.
Доказательство теорем в исчислении предикатов.
Скулемовские стандартные формы.
Литеры, дизъюнкты. Эрбрановский универсум и базис.
Семантическое дерево.
В исчислении высказываний мы показали, что теоремы являются тавтологиски-
ми, т.е.
общезначимыми формами и каждая тавтология исчисления высказываний является
теоремой. Для исчисления предикатов мы также показали, что для исчисления пре-
дикатов первого порядка (а именно его мы и рассматриваем) множество его теорем
совпадает с множеством логически общезначимых формул
. Теорема о дедукции (см
стр.11) исчисления высказываний сводит задачу о выводимости некоторой формулы
A
из множества формул
{}
n
AA ...,
1
=Γ к доказательству справедливости выражения:
├
)...)((...(
21
AAAA
n
→→→→ )(∗
Теоремы о непротиворечивости (cм. стр.13) и о полноте (стр.14) исчисления
высказываний говорят о том, что формула
A
есть теорема тогда и только тогда, когда
эта формула является тавтологией. С помощью закона из (2.10), а именно
BABA ∨¬↔→ нетрудно показать, что
))...)(...((
21
AAAA
n
→→→
эквивалентно
VAAVVAVA
n
⎤⎤⎤ ...
21
поэтому вместо теоремы (*) можно доказать теорему
├
VAAVVAVA
n
⎤⎤⎤ ...
21
(**)
Из определения операции
¬ следует, что если (**) теорема, то
VAAVVAVA
n
⎤⎤⎤ ...
21
есть тавтология , тождественно истинное или эквивалентное ему выражение
AAAA
n
⎤&&...&&
2
есть противоречие. Этот факт и положен в основу доказательства теорем в исчисле-
нии высказываний.
Этот же результат справедлив и для исчисления предикатов первого порядка.
Однако, в отличие от исчисления высказываний, здесь (в исчислении предикатов)
количество возможных интерпретаций бесконечно и доказать общезначимость (т.е.
формула эта тавтология) или противоречивость (т.е
. формула это противоречие)
формулы путем перебора всех интерпретаций невозможно.
Эрбраном в 1930 г. показано, что существуют интерпретации (Н-
интерпретации) такие, что если формула истинна (ложна) в этих интерпретациях, то
она логически общезначима (противоречива). Формула при этом представляется в так
называемой скулемовской стандартной форме.
Математическая Логика и Теория Алгоритмов стр. 29 из 64
© 2003 Галуев Геннадий Анатольевич
Рассмотрим, что это за форма.
Пусть формула
A
находится в предваренной нормальной форме MxQQxQx
nn
...
21
,
где формула
M
без кванторов в конъюнктивной нормальной форме (конъюнкция
дизъюнкций (
)...)(&)(
2121
XVXVXX ⎤ .
Пусть
r
Q - квантор существования )(
∃
в префиксе
nn
XQXQ ...
1¬
)1( nr ≤≤ . Если ни-
какой квантор всеобщности
)(∀ не стоит в префиксе левее
r
Q , выберем новую кон-
станту
c , отличную от других констант, входящих в
M
; заменим все
r
x , входящие в
M
на c и вычеркнем
rr
xQ из префикса.
Если
sms
QQ
...,,1
- список всех кванторов всеобщности )(
∀
, встречающихся левее
r
Q )1(
...,,1
rSS
m
≤〈≤ , выберем новый
m
местный функциональный символ
m
f , отлич-
ный от других функциональных букв, заменим все
r
X в
M
на )(
...,1 sms
xxf и вычеркнем
rr
XQ из префикса. Затем весь этот процесс применим для
оставшихся кванторов существования в префиксе
nn
XQXQ ...,,
11
. Тогда последняя по-
лученная в результате этой процедуры формула есть скулемовская стандартная фор-
ма формулы A . Константы C и функции
m
f , используемые для замены переменных
кванторов существования, называются скулемовскими
.
Таким образом, в префиксе стандартной (скулемовской) формы кванторы суще-
ствования отсутствуют.
Например: Приведем формулу вида
),(),( ZXQYPXzyx →∃∃∀
к скулемовской стандартной форме. Приведем матрицу
M
к конъюнктивной нор-
мальной форме
)),(),(( zxQyxPzyx ∨⎤∃∃∀
Затем, так как перед кванторами
y
∃
и z
∃
есть один квантор
x∀
, то переменные
y и
z
заменяются соответственно одноместными функциями
(
)
xf и )(xg
)).(,())(,((( xgxQxfxPx ∨⎤∀
Отметим, что вид функций
f и
g
, использованных в этом примере, явно не оп-
ределяется, что приводит к неединственности стандартных форм (скулемовских) при
выборе того или иного вида скулемовских функций.
Введем следующие определения.
• Литера есть элементарная формула или ее отрицание.
• Дизъюнкт есть дизъюнкция литер. Дизъюнкт, содержащий
r
литер, назы-
вается
r
- литерным дизъюнктом. Однолитерный дизъюнкт называется еди-
ничным дизъюнктом.
Если дизъюнкт не содержит литер он называется пустым дизъюнктом
. Так как
пустой дизъюнкт не содержит литер, которые могли бы быть истинными, то пустой
дизъюнкт всегда ложен
и обозначается как O .
Множество дизъюнктов из
S есть конъюнкция всех дизъюнктов из S , где каждая
переменная из
S считается управляемой квантором всеобщности )(∀ . Благодаря это-
му соглашению стандартная форма (скулемовские) может быть представлена множе-
ством дизъюнкторов.
Например: стандартная форма
))())(,((&))())(,(( xRxgxQxRxfxPx ∨∨⎤∀
может быть представлена множеством
}
{
)()(,(),())(,( xRxgxQxRxfxP ∨∨⎤ .
Математическая Логика и Теория Алгоритмов стр. 30 из 64
© 2003 Галуев Геннадий Анатольевич
Покажем теперь, что удаление кванторов существования сохраняет противоре-
чивость формулы:
Т
Т
е
е
о
о
р
р
е
е
м
м
а
а
I
I. Пусть
S
множество дизъюнкторов, которые представляют стандарт-
ную форму (скулемовскую) формулы
A
. Тогда
A
противоречива тогда и только тогда,
когда
S противоречиво.
Следует отметить, что согласно
т
т
е
е
о
о
р
р
е
е
м
м
е
е
I
I, стандартная форма
S формы A экви-
валентна
A , если A противоречива.
Если
A
противоречива, то не обязательно AS
↔
.
По определению множество дизъюнкторов невыполнимо (противоречиво) тогда и
только тогда, когда оно ложно при всех интерпретациях на всех областях. Все облас-
ти, из-за их бесконечного числа, перебрать разумеется невозможно. Однако сущест-
вует одна специальная область,
H
, такая, что S невыполнимо тогда и только тогда,
когда
S
ложно при всех интерпретациях на этой области. Эту область
H
называют эр-
бановским универсумом множества
S
и определяют следующим образом.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Пусть
0
H - множество констант, встречающихся в
S
. Если никакая
константа не встречается в
S
, то
0
H состоит из одной константы, скажем
{
}
aH =
0
. Для
,....2,1,0=i пусть
1+i
H есть объединение
i
H и множества всех термов вида
)...,,(
1 n
n
ttf
при всех n для всех функций
n
f , встречающихся в S , где )...,1( njt
j
= при-
надлежит
i
H . Тогда
i
H называется множеством констант i - го уровня для S , а
∞H называется эрбрановским универсумом.
Очевидно, что если
S не содержит функциональных букв, то
∞
H
есть множество
констант из
S .
Например:
Пусть
{}
)()(),( xQxPaPS ∨⎤= , тогда
{
}
aHHH
=
=
=
=
∞
...
10
.
Пусть
{}
))(()(),( xfPxPaPS ∨⎤= , тогда
{
}
aH
=
0
,
{
}
)(,
1
afaH
=
,
{}
))((),(,
2
affafaH = ,
…
{}
.)...))),..((...((...,)),((),(, affffaffafaH =∞ .
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Пусть
S - множество дизъюнктов. Тогда множество элементарных
формул вида
),...,(
1 n
n
ttP для всех предикатов
n
P
, встречающихся в S , где
n
tt ...,
1
- эле-
менты эрбрановского универсума, называется эрбрановским базисом
S .
Поясним смысл термина предикат. Возьмем высказывание (выражаемое предло-
жением): «Сократ есть человек». Часть этого высказывания «есть человек» называ-
ется предикатом или сказуемым. «Сократ» же субъект т.е. подлежащее. Если читать
«Х есть человек», имея в виду математическое понятие переменной, то предикат –
сказуемое высттупает в роли пропозиционной функции. Каждому значению незави
-
симой переменной Х эта функция ставит в соответствие некоторое высказывания, ко-
торое может быть истинным или ложным. В исчислении предикатов предикатом назы-
вают всякую пропозиционную функцию
),...,(
1 n
xxP с любым числом 0≥n независимых
переменных.
Продолжим теперь наше изложение.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Основной пример дизъюнкта
C из множества дизъюнктов S есть
дизъюнкт, полученный заменой переменных в
C на члены эрбрановского универсума.
Дадим теперь определение
H
- интерпретации.
О
О
п
п
р
р
е
е
д
д
е
е
л
л
е
е
н
н
и
и
е
е
.
. Пусть
S - множество дизъюнктов,
H
- эрбрановский универсум S ,
I
- интерпретация S над
H
. Говорят, что
I
есть
H
- интерпретация множества S , или
она удовлетворяет следующим условиям.
1. I отображает все константы из
S в самих себя;
2. Пусть
f есть n - местный функциональный символ и
n
hh ...,
1
- элементы
H
; в I
через
f обозначается функция, которая отображает
n
n
Hhh ∈),...,(
1
в
Hhhf
n
∈)...,(
1
.