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

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

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

3.

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

4.

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

5.

ЛОГИКА (ФОРМАЛЬНАЯ)
изучает
формы,
в
которых
проявляются
законы
причинноследственных
связей,
вне
зависимости от содержания (смысла)
тех явлений (предметов), к которым
эти законы относятся.

6.

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

7.

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

8.

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

9.

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

10.

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

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

12.

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

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

14.

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

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

16.

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

17.

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

18.

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

19.

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

20.

Пример.
Формула ( 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

21.

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

22.

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

23.

Новые
тавтологии
можно
получить
помощью следующего правила.
Правило подстановки:
если
1 ,..., n
| ( X 1 ,..., X n ) ,
тавтологией
( 1 ,..., n ) .
то для любых формул
является
формула
с

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

25.

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

26.

Лемма. Справедливы следующие равенства
формул:
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 )
–
законы
дистрибутивности конъюнкции относительно
дизъюнкции
и
дизъюнкции
относительно
конъюнкции;

27.

( 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 )
–
взаимосвязь
эквивалентности
с
импликацией,
дизъюнкцией и конъюнкцией.

28.

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

29.

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