Вспомогательные материалы

Вспомогательные материалы:

Курс: Дискретная математика

Содержание
Список определений
Список теорем
Термины
Обозначения
Примеры
Задачи

Аксиомы и правила вывода

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

Аксиоматический метод
Для любого натурального числа n: n' 0.

Аксиома 1.


Для любых натуральных чисел m и n: если m'=n', то m = n.

Аксиома 2.


Пусть A является подмножеством множества w со следующими свойствами:
  1. 0 О A;
  2. для любого натурального числа n: если n О A, то n' О A.
Тогда A = w.

Аксиома 3 (индукции).


Логика высказываний
{ F } |– F.

Аксиомы.


G |– F G |– G
(В&)
G |– F & G

Правило введения конъюнкции


G |– F & G
(У&)
G |– F


G |– F & G

G |– G

Правила удаления конъюнкции


G И { F } |– G
Й)
G |– F Й G

Правило введения импликации


G |– F G |– FЙ G
Й)
G |– G

Правило удаления импликации


G И {G} |– F
(УП)
G |– F

Правило удаления посылки


G И { F } |– ^
(В¬)
G |– ¬F

Правило введения отрицания


G И { ¬F } |– ^
(У¬)
G |– F

Правило удаления отрицания


G |– F G |– ¬F
^)
G |– ^

Правило сведения к противоречию


G |– ^
^)
G |– F

Правило противоречия


G |– F
Ъ)
G |– F Ъ G


G |– G

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)

Правила замены