Курс: Дискретная математикаСодержание
Список определений
Список теорем
Термины
Обозначения
Примеры
Задачи
Аксиомы и правила вывода
Математическая логика
Аксиоматический метод
Для любого натурального числа n: n'№ 0.
Аксиома 1.
Для любых натуральных чисел m и n: если m'=n',
то m = n. Аксиома 2.
Пусть A является подмножеством множества w со следующими свойствами:
- 0 О A;
- для любого натурального числа n: если n О A, то n' О A.
Тогда A = w.
Аксиома 3 (индукции).
Логика высказываний
{ F } |– F. Аксиомы.
| G |– F G |– G | (В&) |
| |
G |– F & G |
| Правило введения конъюнкции
|
| Правила удаления конъюнкции
| G И { F } |– G | (ВЙ) |
| |
G |– F Й G |
| Правило введения импликации
| G |– F G |– FЙ G | (УЙ) |
| |
G |– G |
| Правило удаления импликации
Правило удаления посылки
| G И { F } |– ^ | (В¬) |
| |
G |– ¬F |
| Правило введения отрицания
| G И { ¬F } |– ^ | (У¬) |
| |
G |– F |
| Правило удаления отрицания
| G |– F G |– ¬F | (В^) |
| |
G |– ^ |
| Правило сведения к противоречию
| Правило противоречия
|
| Правила введения дизъюнкции
| G |– F Ъ G G И F |– C G И G |– C |
(У Ъ) |
|
|
G |– C |
Правило удаления дизъюнкции
Логика предикатов
| G |– F(v) | (В") |
| |
G |– " v F(v) |
| Правило введения квантора всеобщности
| G |– " v F(v) | (У") |
| |
G |– F (t) |
| Правило удаления квантора всеобщности
| G |– F(t) | (В$) |
| |
G |– $ v F(v) |
| Правило введения квантора существования
| G |– $ v F(v) G И { F(v) }|– C | (У$) |
| |
G |– C |
| Правило удаления квантора существования
Ж |–
t = t Аксиома равенства
| G |– t1 = t2 G |– F(t1) | (З=) |
| |
G |– F(t2) |
|
G |– t1 = t2 G |– F(t2) |
|
G |– F(t1) |
| Правила замены