Математическая логика

1. МАТЕМАТИЧЕСКАЯ ЛОГИКА

2. Предмет математической логики

3.

ЛОГИКА — междисциплинарная отрасль
наук, изучающая
законы причинно-следственной связи в
окружающем мире;
проявление
законов
причинноследственной связи в рациональном
мышлении человека (законы правильного
мышления);
отражение
законов
причинноследственной
связи
в
языках
(естественных и искусственных).

4.

Логика возникла в VI—IV вв. до н. э. как
«анализ мышления», т.е. анализ принципов
правильных рассуждений.
Основоположник
логики
–
древнегреческий ученый Аристотель (384322 гг. до н. э.), который в сочинениях
«Аналитики» впервые изложил идею
дедуктивного вывода.

5.

Математическая
логика
занимается
задачами формализации правильных способов
рассуждений с помощью математического
аппарата.
Главная цель – изучение математических
рассуждений с целью точного определения
понятия «математическое доказательство».
Первый исследователь этого направления немецкий математик Г.Лейбниц (1646—1716).

6.

Этапы развития математической логики:
Английский математик Дж.Буль (1815—1864)
создал алгебру логики.
Немецкий математик Г.Фреге (1848—1925)
разработал логико-математические языки и
теорию их осмысления (так называемую
семантику).
Итальянский математик Дж.Пеано (1858—
1932)
изложил
арифметику
на
языке
математической логики.

7.

В XIX веке математическая логика стала
основой всех наук:
открытие неевклидовой геометрии,
поиски обоснования математического
анализа,
открытие парадоксов, т.е. рассуждений,
приводящих к противоречиям.
Анализ парадоксов привел к созданию
программы
Д.Гильберта
(1862—1943)
обоснования
математики
на
основе
аксиоматического подхода.

8.

Главная
задача
современной
математической
логики
–
изучение
формальных
теорий,
представляющих
собой множества теорем, получающихся из
исходных аксиом с помощью дедуктивных
умозаключений.

9.

Бурное развитие математической логики и
теории алгоритмов в наше время обусловлено:
распространением
информационнокоммуникационных технологий на основе
современной компьютерной техники,
необходимостью создания теоретических
основ обработки и передачи информации,
математического моделирования самых
разнообразных задач и процессов.

10.

Основная
логики.
задача
формальной
База знаний:
Предложение:
Задача (формальная): проверить, что
выводится из
по законам формальной
логики.
Задача
(неформальная):
выяснить,
является ли предложение
следствием
утверждений базы знаний Г.

11.

Приложение 1.
Экспертные системы
База знаний
— база знаний экспертной
системы.
Предложение
— запрос к базе знаний.
Аппарат логического вывода — ядро
экспертной системы.

12.

Приложение 2.
Программирование
Вычисление
программы
—
последовательное
преобразование
интерпретатором одних состояний данных
в другие согласно заданному алгоритму.
Логический вывод (доказательство) —
последовательное построение по законам
формальной логики одних утверждений из
других, исходя из заданной базы знаний.

13.

Программа
База знаний
Вызов программы
Запрос
Вычисление программы
Логический
(доказательство)
Интерпретатор программ
Правила вывода
вывод
Однако успешное вычисление программы
завершается
результатом,
но
не
всякое
доказательство, даже если оно корректно, является
«результативным» (конструктивным).
Теоремы существования можно доказать, не
предъявив при этом искомого объекта.

14. Логика высказываний

15.

Высказывание
повествовательное
предложение, о котором можно судить,
истинное оно или ложное.
Обозначаются высказывания A,B,C,…
Истинностное значение высказывания A
обозначается символом (A) и определяется по
формуле:
(A)=1, если высказывание A истинно, и
(A)=0, если A ложно.

16. Алгебра высказываний

17.

Из высказываний путем соединения их
различными способами (с помощью связок
«не», «и», «или», «следует», «равносильно»)
можно составлять новые, более сложные
высказывания.
При этом главное внимание уделяется
истинностно-функциональным комбинациям, в
которых истинность или ложность новых
высказываний определяется истинностью или
ложностью составляющих их высказываний.
Определение.
Алгеброй
высказываний
называется множество всех высказываний P с
логическими операциями , , , , .

18. Формулы алгебры высказываний

19.

Свойства
алгебры
высказываний
P
описываются с помощью формул, которые
строятся из переменных символов с помощью
знаков логических операций. Такие формулы
приято называть также пропозициональными
формулами
Cимволы логических операций , , , , ,
которые называются пропозициональными
связками.
Переменные символы X,Y,Z,…, которые
используются для обозначения высказываний и
которые называются пропозициональными
переменными.

20.

Определение.
Формулы
алгебры
высказываний индуктивно определяются по
правилам:
1) каждая пропозициональная переменная
является формулой,
2) если , – формулы, то формулами
являются также выражения
( ), , , , .
Множество
всех
формул
высказываний обозначим FАВ .
алгебры

21.

Если в формулу входят переменные
X 1 ,..., X n , то записывают ( X 1 ,..., X n ) .
Из индуктивного определения формул
следует, что если в формулу вместо
переменных X1,..., X n подставить произвольные
конкретные высказывания A1 ,..., An , то получится
некоторое сложное высказывание ( A1,..., An ) .
Истинностное значение
высказывания
( ( A1 ,..., An ))
определяется истинностными
значениями
исходных
высказываний
( A1 ),..., ( An ) согласно таблицам истинностных
значений логических операций , , , , .

22.

Формула определяет функцию n
F ,
переменных
которая
каждому
упорядоченному набору ( ( X 1 ),..., ( X n )) n
элементов
множества
{0,1}
ставит
в
соответствие элемент ( ( X 1 ,..., X n )) этого же
множества.
Функция F называется истинностной
функцией
формулы
и
графически
представляется истинностной таблицей.
Такая таблица содержит 2n строк и имеет
2n
2 возможных
одно
из
распределений
значений 0 и 1 в последнем столбце.

23.

Пример.
Формула ( X Y X Y )
имеет следующую истинностную таблицу:
X
0
0
1
1
Y
0
1
0
1
X
1
1
0
0
Y X Y X Y X Y X Y
1
1
1
1
0
0
0
1
1
0
1
0
0
0
1
0

24.

Определение. Формула называется:
тавтологией
(или
тождественно
истинной формулой) и обозначается | ,
если
ее
истинностная
функция
тождественно равна 1;
противоречием
(или
тождественно
ложной формулой), если ее истинностная
функция тождественно равна 0;
выполнимой, если ее истинностная функция
не равна тождественно 0;
опровержимой, если ее истинностная
функция не равна тождественно 1.

25.

Тавтологии являются общими схемами
построения истинных высказываний и в этом
смысле выражают некоторые логические законы.
Примеры таких законов являются:
| X X – закон исключенного третьего,
| X X – закон двойного отрицания,
| ( X X ) – закон противоречия,
| ( X Y ) ( Y X ) – закон контрапозиции.

26. Логическая равносильность формул

27.

Определение. Формулы , называются
логически
равносильными
(или
просто
равносильными), если | .
Для обозначения логически эквивалентных
формул используется символическая запись
, или просто .
Такие выражения называются логическими
равенствами или просто равенствами формул.

28.

Лемма. Справедливы следующие равенства
формул:
1) X (Y Z ) ( X Y ) Z , X (Y Z ) ( X Y ) Z
– свойства ассоциативности дизъюнкции и
конъюнкции;
2) X Y Y X , X Y Y X – свойства
коммутативности дизъюнкции и конъюнкции;
X X X
3) X X X ,
– свойства
идемпотентности дизъюнкции и конъюнкции;
4) X (Y Z ) ( X Y ) ( X Z ) ,
X (Y Z ) ( X Y ) ( X Z )
–
законы
дистрибутивности конъюнкции относительно
дизъюнкции
и
дизъюнкции
относительно
конъюнкции;

29.

( X Y ) X Y
5) ( X Y ) X Y ,
–
законы де Моргана;
6) ( X Y ) X X , ( X Y ) X X – законы
поглощения;
7) X X – закон двойного отрицания;
X Y ( X Y )
8) X Y X Y ,
–
взаимосвязь импликации с дизъюнкцией и
конъюнкцией;
9) X Y ( X Y ) (Y X ) ,
X Y ( X Y ) ( X Y )
–
взаимосвязь
эквивалентности
с
импликацией,
дизъюнкцией и конъюнкцией.

30.

Лемма (Правило замены). Если формулы ,
равносильны, то для любой формулы (X ) ,
содержащей
переменную
X,
выполняется
равенство: ( ) = ( ) .
Это правило означает, что при замене в любой
формуле ( ) некоторой ее подформулы
на равносильную ей формулу получается
формула ( ) , равносильная исходной
формуле .
Такие переходы называются равносильными
преобразованиями формул.

31.

Пример.
Формула ( X Y ) Z с помощью
равенств 5),7),8) из леммы 2.4.1 равносильно
преобразовывается следующим образом:
( X Y ) Z ( X Y ) Z
( ( X Y )) Z ( X Y ) Z .

32. Нормальные формы формул алгебры высказываний

33.

Отношение равносильности является
отношением эквивалентности на множестве
всех формул FАВ, которое разбивает это
множество
на
классы
эквивалентности
[ ] { FАВ : } , определяемые формулами
FАВ .
Из лемм следует, что для каждой формулы
FАВ можно
указать
равносильные
ей
формулы специального вида, содержащие
только символы логических операций , , .

34.

Определение.
Литерой
называется
пропозициональная переменная X или ее
отрицание X . Для обозначения литеры
используется символ X , где {0,1} и по
1
X
X , X 0 X .
определению
Определение.
Конъюнктом
(соответственно, дизъюнктом) называется
литера или конъюнкция (соответственно,
дизъюнкция) литер.
Конъюнкт
(дизъюнкт)
называется
совершенным,
если
он
содержит
все
пропозициональные
переменные
рассматриваемой формулы.

35.

Определение. Конъюнктивной нормальной
формой (сокращенно КНФ)
называется
дизъюнкт или конъюнкция дизъюнктов.
Дизъюнктивной
нормальной
формой
(сокращенно ДНФ) называется конъюнкт или
дизъюнкция конъюнктов.
При этом КНФ (соответственно, ДНФ)
называется совершенной, если совершенны все
ее дизъюнкты (соответственно, конъюнкты).
Теорема 1. Любая формула равносильна
некоторой ДНФ и некоторой КНФ.

36.

Алгоритм приведения формулы
к ДНФ
(соответственно, к КНФ):
1) выражаем все входящие в формулу
импликации и эквивалентности через конъюнкцию,
дизъюнкцию и отрицание;
2) согласно законам де Моргана все отрицания,
стоящие перед скобками, вносим в эти скобки и
сокращаем все двойные отрицания;
3)
согласно
законам
дистрибутивности
преобразуем формулу так, чтобы все конъюнкции
выполнялись раньше дизъюнкций (соответственно,
чтобы все дизъюнкции выполнялись раньше
конъюнкций).

37.

Теорема
2.
( X 1 ,..., X n )
Любая выполнимая формула
равносильна формуле вида
где
дизъюнкция
берется
по
всем
1,..., n {0,1}n,
упорядоченным наборам
удовлетворяющим условию F 1,..., n 1 .
Такая формула определяется однозначно (с
точностью до порядка членов конъюнкций и
дизъюнкций) и называется совершенной
дизъюнктивной
нормальной
формой
(сокращенно СДНФ) формулы .

38.

Теорема 3. Любая опровержимая формула
( X 1 ,..., X n ) равносильна формуле вида
где конъюнкция берется по всем упорядоченным
1,..., n {0,1}n, удовлетворяющим
наборам
условию F 1,..., n 0 .
Такая формула определяется однозначно (с
точностью до порядка членов конъюнкций и
дизъюнкций)
и
называется
совершенной
конъюнктивной нормальной формой (сокращенно
СКНФ) формулы .

39.

Алгоритм нахождения СДНФ и СКНФ
формулы ( X 1,..., X n ) :
1. Составить истинностную таблицу
формулы и добавить два столбца
«Совершенные конъюнкты» и «Совершенные
дизъюнкты».
2. Если при значениях ( X 1 ) k1,..., ( X n ) kn
значение ( ( X 1 ,..., X n )) формулы равно 1, то
в соответствующей строке таблицы в столбце
«Совершенные
конъюнкты»
записываем
X1k1 X nk n
конъюнкт
и
в
столбце
«Совершенные дизъюнкты» делаем прочерк.
При этом X i1 X i и X i0 X i .

40.

3. Если при значениях ( X 1 ) m1,..., ( X n ) mn
истинностное значение ( ( X 1 ,..., X n )) формулы
равно 0, то в соответствующей строке таблицы в
столбце «Совершенные дизъюнкты» записываем
X11 m1 X n1 mn
дизъюнкт
и
в
столбце
«Совершенные конъюнкты» делаем прочерк.
X1
…
Xn
...
( X 1 ,..., X n )
… … … ...
k1 … k n ...
… … … ...
m1 … mn ...
…
1
…
0
…
…
…
…
...
Совершенные Совершенные
конъюнкты
дизъюнкты
…
…
–
X1k1 X nk n
…
…
–
X11 m1 X n1 mn
…
…

41.

4. СДНФ формулы равна дизъюнкции
полученных
совершенных
конъюнктов:
( X1k1 X nk n ) … .
5. СКНФ формулы равна конъюнкции
полученных
совершенных
дизъюнктов:
( X11 m1 X n1 mn ) … .

42. Логическое следование формул

43.

Определение. Формула называется
логическим следствием формул 1,..., m , если
при любой подстановке в эти формулы вместо
X 1 ,..., X n
их
переменных
конкретных
A1 ,..., An
высказываний
из
истинности
высказываний 1 ( A1,..., An ),..., m ( A1,..., An ) следует
истинность высказывания ( A1,..., An ) .
Символическое обозначение 1,..., m | называется логическим следованием.
Формулы 1,..., m называются посылками и
формула – следствием логического
следования 1,..., m | .

44.

Определение.
называется
логически
Множество
формул
противоречивым,
следует
любая
(в
если
том
1 ,..., m
из
него
числе
и
тождественно ложная) формула . Символически
это записывается
.
В противном случае множество формул
1 ,..., m называется выполнимым.
Лемма
(Транзитивность
логического
следования). Если 1,..., m | и для любого
значения 1 i m выполняется 1,..., k | i , то
1 ,..., k | .

45.

Лемма (Критерии логического следования).
Условие 1,..., m | равносильно каждому из
следующих условий:
a) 1 ... m | ,
b) | 1 ... m ,
c) 1 , , m , | .
В частности, | равносильно | .
Отсюда также следует, что равносильно
тому, что | и | .

46.

Основные правила логического следования:
1) правило отделения (или правило модус
поненс – от латинского modus ponens)
, | ;
2) правило контрапозиции
| ;
3) правило цепного заключения
1 2 , 2 3 | 1 3 ;
4) правило перестановки посылок
1 ( 2 3 ) | 2 ( 1 3 ) .

47.

Следующие задачи равносильны:
а) проверка тождественной истинности
формул;
б) проверка логического следования формул;
в) проверка тождественной ложности формул;
г) проверка противоречивости множества
формул;
д) проверка противоречивости множества
дизъюнктов.

48. Методы проверки тождественной истинности формул

49.

Основные методы проверки тождественной
истинности формул:
1. Прямой метод.
2. Алгебраический метод.
3. Метод резолюций.

50. Логика предикатов

51. Понятие предиката

52.

Определение.
Предикатом
называется
утверждение, содержащее переменные x1 ,..., xn ,
которое превращается в высказывание при замене
этих переменных конкретными объектами из
некоторой области возможных значений.
Обозначаются предикаты P,Q,...
Переменные x1 ,..., xn , называются предметными
или индивидуальными переменными. Число
предметных переменных в предикате называется
его арностью или местностью.
Более точно, предикат P с n предметными
переменными называется n-арным или n-местным
предикатом и обозначается P x1 ,..., xn .

53.

Предикат P x1 ,..., xn является функцией,
которая
каждому
набору
значений
x1 a1 ,..., xn an его n предметных переменных
x1 ,..., xn ставит в соответствие некоторое
P a1 ,..., an ,
высказывание
имеющее
определенное
истинностное
значение
( P a1 ,..., an ) .
Если
отвлечься
от
содержания
высказываний и учитывать только их
истинностные значения, то предикат можно
рассматривать как функцию со значениями в
множестве 0,1 .

54.

Рассматривая такую функцию на некотором
фиксированном множестве M допустимых
значений предметных переменных предиката,
получим n-арное отношение на множестве M,
состоящее из всех таких упорядоченных
наборов a1 ,..., an n элементов a1 ,..., an M , для
P a1 ,..., an
которых
является
истинным
высказыванием.
Такое n-арное отношение обозначается
+
символом P и называется множеством
истинности предиката P на множестве M.

55.

Определение. Предикат P x1 ,..., xn на множестве
M называется:
тождественно истинным, если для любых
x1 a1 M ,..., xn an M
значений
высказывание P a1 ,..., an истинно, т.е. P+=Mn;
тождественно ложным, если для любых
значений x1 a1 M ,..., xn an M высказывание
P a1 ,..., an ложно, т.е. P+ = ;
выполнимым, если для некоторых значений
x1 a1 M ,..., xn an M
высказывание
P a1 ,..., an истинно, т.е. P+ ;
опровержимым, если для некоторых значений
x1 a1 M ,..., xn an M
высказывание
P a1 ,..., an ложно, т.е. P+ Mn.

56. Алгебра предикатов

57.

Определение.
Результатом действия квантора общности
x1 по переменной x1 на n-местный предикат
P x1 ,..., xn называется (n 1)-местный предикат
x1 P( x1 , x2 ,..., xn ) , который зависит от
переменных x2 ,..., xn и который при значениях
x2 a2 ,..., xn an в том и только том случае
истинен на множестве M допустимых
значений переменной x1, если при любых
x1 a1 M
значениях
высказывание
P a1 , a2 ,..., an истинно.

58.

Определение.
Результатом
действия
квантора
существования x1 по переменной x1 на nместный предикат P x1 ,..., xn называется
(n 1)-местный предикат x1 P( x1 , x2 ,..., xn ) ,
который зависит от переменных x2 ,..., xn и
который при значениях x2 a2 ,..., xn an в том и
только том случае истинен на множестве M
допустимых значений переменной x1, если
x1 a1 M
при
некотором
значении
высказывание P a1 , a2 ,..., an истинно.

59.

Определение.
Алгеброй предикатов называется множество
всех предикатов P с логическими операциями
, , , ,
и операциями квантификации
x , x для всех предметных переменных x.

60. Формулы алгебры предикатов

61.

Свойства алгебры предикатов P описываются
с помощью специальных формул, которые
строятся из символов предикатов и предметных
переменных
с
помощью
специальных
вспомогательных символов – скобок и знаков
логических операций над предикатами.

62.

Алфавит алгебры предикатов состоит из
следующих символов:
x1 , x2 ,...,
1) предметные
переменные
которые используются для обозначения
элементов множества допустимых значений,
2) n-местные предикатные символы P,Q,...,
которые используются для обозначения nместных
предикатов
на
множестве
допустимых значений,
3) символы логических операций
, , , , , , ,
4) вспомогательные символы (,) и другие.

63.

Формулы алгебры предикатов определяются по
индукции следующим образом:
1) для любого n-местного предикатного символа P и
любых n предметных переменных x1 ,..., xn
выражение P x1 ,..., xn есть формула, которая
называется элементарной (или атомарной)
формулой;
2) если , – формулы, то формулами являются
также выражения
( ) , , , , ;
3) если – формула и x – предметная переменная,
то формулами являются также выражения x ,
x ; при этом переменная x и формула
называется областью действия соответствующего
квантора.

64.

Если в формулу входят переменные x1 ,..., xn ,
то записывают ( x1 ,..., xn ) .
Вхождение предметной переменной x в
формулу называется связным, если она
находится в области действия одного из этих
кванторов; в противном случае вхождение
предметной переменной x в формулу
называется свободным.
Формула
без
свободных
вхождений
переменных называется замкнутой формулой
или предложением.

65. Интерпретации формул алгебры предикатов

66.

Область интерпретации – непустое множество
M, которое является областью возможных
значений всех предметных переменных.
P
n-местным
предикатным
символам
присваиваются конкретные значения PM nместных предикатов на множестве M.
P PM
Соответствие
:
называется
интерпретацией предикатных символов.
Область
интерпретации
M
вместе
с
интерпретацией
предикатных
символов
называется интерпретацией формул алгебры
предикатов и обозначается (M , ) или просто M.

67.

При наличии интерпретации M конкретные
значения предметным переменным формул
алгебры
предикатов
присваиваются
с
помощью отображения множества всех
предметных переменных X в область
интерпретации M.
Такие отображения называются оценками
предметных переменных.

68.

Выполнимость формулы в интерпретации M
M |
при оценке
обозначается
и
определяется следующим образом:
1) если P x1 ,..., xn для n-местного предикатного
символа P и предметных переменных x1 ,..., xn ,
то M | тогда и только тогда, когда
высказывание PM ( x1 ),..., ( xn ) истинно;
2) если для формулы , то M | тогда
и только тогда, когда неверно, что M | ;
3) если 1 2 для формул 1 , 2 , то M |
тогда и только тогда, когда M | 1 и M | 2 ;

69.

4) если 1 2 для формул 1 , 2 , то M | тогда
и только тогда, когда M | 1 или M | 2 ;
5) если 1 2 для формул 1 , 2 , то M |
тогда и только тогда, когда неверно, что M | 1 и
M | 2 ;
6) если 1 2 для формул 1 , 2 , то M |
тогда и только тогда, когда M | 1 , M | 2
одновременно верны или нет;
7) если x для некоторой формулы , то M |
тогда и только тогда, когда M | для всех оценок
, отличающихся от оценки возможно только на
элементе x;
8) если x для некоторой формулы , то M |
тогда и только тогда, когда M | для некоторой
оценки , отличающейся от оценки возможно
только на элементе x.

70.

Определение. В интерпретации M формула
называется:
общезначимой
(или
тождественно
истинной), если M | при любых оценках
;
выполнимой, если M | для некоторой
оценки ;
опровержимой, если для некоторой оценки
неверно, что M | ;
тождественно ложной, если для любой
оценки неверно, что M | .

71.

Формула общезначима в интерпретации M, если
при подстановке в нее вместо n-арных предикатных
символов P их интерпретаций PM она превращается
в тождественно истинный на множестве M
предикат. Символическая запись M | .
Формула в интерпретации M выполнима,
опровержима или тождественно ложна, если при
подстановке в нее вместо n-арных предикатных
символов P их интерпретаций она превращается
соответственно в выполнимый, опровержимый или
тождественно ложный на множестве M предикат
PM .

72. Проблема общезначимости формул алгебры предикатов

73.

Определение. Формула называется тождественно
истинной, если она тождественно истина в любой
интерпретации M. Такая формула называется также
общезначимой формулой, или тавтологией алгебры
предикатов и обозначается | . Множество всех
тавтологий алгебры предикатов обозначим TАП. .
Определение. Формула называется тождественно
ложной или противоречием, если она тождественно
ложна в любой интерпретации M.
По определению противоречивость формулы
равносильна условию | .
Определение. Формула называется выполнимой, если
она выполнима хотя бы в одной интерпретации M,
которая называется моделью этой формулы.

74.

Таким образом, формула :
общезначимая (или тождественно истинная,
M |
тавтология),
если
в
любой
интерпретации M при любых оценках ;
запись | ;
выполнимая, если M | в некоторой
интерпретации M для некоторой оценки ;
опровержимая, если в некоторой
интерпретации M для некоторой оценки
неверно, что M | ;
тождественно ложная, если в любой
интерпретации M для любой оценки
неверно, что M | .

75. Тавтологии алгебры предикатов

76.

Любая тавтология алгебры высказываний
является тавтологией алгебры предикатов.
Более того, тавтологии алгебры высказываний
дают возможность легко получать тавтологии
алгебры предикатов с помощью следующего
очевидного результата.
Лемма 1. Если X 1 ,..., X n – тавтология
алгебры высказываний, то для любых формул
алгебры предикатов 1,..., n формула 1 ,..., n
является тавтологией алгебры предикатов.

77.

С другой стороны, в алгебре предикатов можно
получить много принципиально новых тавтологий с
помощью следующих свойств кванторов.
Лемма 2. Для любых формул , следующие
формулы являются тавтологиями:
1. x x , x x ,
x x , x x ;
2. x y y x , x y y x ;
3. x ( ) x x ,
x ( ) x x ;

78. Логическая равносильность формул алгебры предикатов

79.

Определение. Формулы алгебры предикатов
, называется логически равносильными, если
результат применения к ним логической
операции эквивалентность является
тавтологией.
В этом случае записывают , или просто
.
Таким образом, означает, что | .

80.

Теорема 1 (Взаимосвязь между кванторами).
Для любой формулы справедливо равенство:
x y y x , x y y x .
С другой стороны, если в формулу
предметные переменные x,y входят свободно,
то равенство
y x x y
не выполняется, так как в этом случае формула
y x x y
не является тавтологией.

81.

Теорема 2. Пусть формула (x) не содержит
предметную переменную y и формула ( y )
получается из (x) заменой всех свободных
вхождений переменной x на предметную
переменную y.
Тогда формулы x (x) и x (x) будут
логически
равносильны
соответственно
формулам y ( y) и y ( y) , т.е. выполняются
равенства:
x ( x) y ( y) и x ( x) y ( y) .

82.

Теорема 3 (Законы де Моргана для кванторов). Для
любой
формулы
справедливы
следующие
утверждения:
x x , x x ,
x x , x x .
Теорема 4 (Взаимосвязь кванторов с конъюнкцией и
дизъюнкцией). Для любых формул , справедливы
следующие утверждения:
x ( ) x x ,
x ( ) x x .
Если в формулу предметная переменная x не входит
свободно, то справедливы также утверждения:
x x , x x , где
– символ одной из операций , .

83.

Теорема
6
(Взаимосвязь
кванторов
с
импликацией). Если в формулу предметная
переменная x не входит свободно, то для любой
формулы справедливы следующие утверждения:
x ( ) x , x ( ) x .
Если же предметная переменная x не входит
свободно в формулу , то для любой формулы
справедливы утверждения:
x ( ) x , x ( ) x .

84.

Следствие
7.
Любая
формула
представляется в следующем виде:
K1 x1 ... K n xn ,
где K1 ,..., K n – некоторые кванторы и –
формула без кванторов.
Таким образом, каждая формула логически
равносильна формуле K1 x1 ... K n xn , в которой
все кванторы стоят в самом начале формулы и
которая называется предваренной нормальной
формой (сокращенно ПНФ) формулы .

85.

Алгоритм приведения формулы к ПНФ:
1) преобразуем формулу в эквивалентную ей
формулу , которая не содержит импликации и
эквивалентности и в которой отрицание
действует только на элементарные формулы;
2) в все кванторы последовательно выносим
вперед по теореме 5, при этом кванторы
общности x выносятся из конъюнкции и
кванторы существования x выносятся из
дизъюнкции, а для выноса кванторов общности
x из дизъюнкции и кванторов существования
x из конъюнкции переименовываем связанные
переменные x в новые переменные y, которые не
входят в рассматриваемую формулу.