2.6. Введение в методы теории доказательств
Рассмотренные выше предикаты определяют принадлежность точки геометрическому множеству через простые арифметические вычисления и операции алгебры логики. Это наводит на мысль, что многие другие математические построения можно сделать очень наглядными, если пользоваться логическими символами и логическими законами. Развивая эту точку зрения, были формализованы и развиты методы теории доказательств.
Суть этих методов состоит в следующем. Вначале формируется предметный язык, в терминах которого суждения данной теории записываются в виде формул. Например, в теории множеств элементами такого языка являются символы обозначения элементов множеств, операции принадлежности, включения, объединения множеств и другие. К числу примеров формул теории множеств относятся: x A A B, C = A B и другие.
Затем описывается аксиоматика предметной области и определяется эквивалентный ей класс формул математической логики. На основании законов математической логики описываются правила вывода, с помощью которых можно переходить от одних формул к другим.
С этой целью в теории доказательств вводятся новые понятия. К их числу относятся кванторы, выводимые формулы и тавтологии или общезначимые формулы.
Под квантором понимается характеристика степени значения предиката от входящих в него предметных переменных. Используются два квантора: всеобщности и существования. Квантор всеобщности обозначается . Например символы «x» читаются так: «Для всех x …». Квантор существования обозначается «». Символы x читаются соответственно: «Существует x такой, что …».
Если существует вывод формулы F из формул F1, F2,…, Fn, по данным правилам, то говорят что F выводима и пишут F1, F2,…, Fn ├ F.
Формула называется тавтологией или общезначимой, если она истинна при любых значениях входящих в нее переменных. Например, x x x = 1. Тавтология определяет логический закон. Ее обозначение «╞». Основной задачей теории доказательств является получение тавтологий, например, более простых из более сложных или обладающих другими полезными качествами.
В качестве примера рассмотрим применение методов теории доказательств к выводу закона теории множеств:
A - (A B) = A - B.
Введем предикат принадлежности P(x A) следующим образом:
1 Если X a,
P(x A) =
0 Если X a.
Аналогично построим предикат
1 Если X a,
P(xA) =
0 Если X a.
Непосредственно убеждаемся в том, что P( x A) = =P(x A).
Поставим во взаимно‑однозначное соответствие аксиомам и операциям теории множеств формулы математической логики. Из этих формул мы будем применять следующие:
x A B P(x A B) = P(x A) P(x B);
x A B P(x A B) = P(x A) & P(x B);
x A - B P(x A - B) = P(x A) P(x B);
На основании этих эквивалентностей переходим к доказательству закона теории множеств:
P(x A - (A B)) = P(x A) & P(x A B) =
= P(x A) & P(x A B) =
= P(x A) & (P(x A) & P(x B)) =
= P(x A) ) & (P(x A) P(x B)) =
= (P(x A)) & P(x A)) (P(x A) & P(x B)) =
= 0 (P(x A) & P(x B)) = P(x A) & P(x B)).
Имеем окончательно: x A - (A B)╞ x A - B.
Задачи
В задачах 2.1 — 2.15 построить таблицы истинности для следующих функций алгебры логики:
F(x, y, z) = x & y V (x V z).
F(x, y, z) = z (x V y).
F(x, y, z) = x & y (x V y).
F(x, y, z) = (x & y & z) (x V y).
F(x, y, z) = (x V z) y.
F(x, y, z) = (x y) z.
F(x, y, z) = (x y) & (y z).
F(x, y, z) = x & (y z) V y.
F(x, y, z) = (x V y V z).
F(x, y, z) = (x y) & (y z).
F(x, y, z) = (x z) y.
F(x, y, z) = (y V z) (x V z).
F(x, y, z) = x (y V z).
F(x, y, z) = (x y) & (y x) & z..
F(x, y, z) = z V x & y.
В задачах 2.16 — 2.25 упростить выражения, используя известные свойства операций и законы математической логики:
x & (x & y V z) & (x V z).
(x V y) & (y V x & z).
x & (y x) & (x V z).
(x y)& x &y.
(x & y ) (z & x).
(x & y z) & x & z.
(x & z V x &y ) & (z y).
(x V y &z V x &y & z) & x & y.
(x y) & (yx).
(x & y & z V x & z) & y.
В задачах 2.26 — 2.35 построить С.Д.Н.Ф. (совершенные дизъюнктивные нормальные формы) по таблицам истинности, которые приведены ниже.
2.28 x y z F 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0
2.29 x y z F 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0
2.30 x y z F 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0
2.31 x y z F 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0
2.32 x y z F 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0
2.33 x y z F 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0
2.34 x y z F 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1
2.35 x y z F 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0
В задачах 2.36 — 2.44 построить предикаты принадлежности некоторой произвольной точки A(x, у) областям, определяемым следующими геометрическими фигурами:
Кругом радиуса r = 5 с центром в точке (5,5).
Кругом радиуса r = 10 с центром в точке (-5,5).
Треугольником, вершины которого имеют координаты: A(5, 5), B(5, 0), C(0, 5).
Квадратом с центром в начале координат и стороной a = 7.
Любым прямоугольником, две стороны которого расположены на осях координат. Длины этих сторон: по оси абсцисс -5, по оси ординат — 10.
Кольцом с центром в начале координат. Его радиусы: r = 4, R = 6.
Кольцом с центром, смещенным от начала координат на 3 единицы вправо и 2 единицы вверх. Его радиусы: r = 4, R = 6.
Областью, ограниченной параболой y = x2 и отрезком вещественной оси [-1,1].
Областью, ограниченной прямой у = x и отрезком вещественной оси [0, 5].
В задачах 2.45 — 2.50 доказать следующие тождества вначале на языке теории множеств, а затем — на языке теории доказательств:
A (A B) = A
A (A B) = A
A (B C) = (A B) (A C)
A (B C) = (A B) (A C)
I \ (A B) = (I \ A) (I \ B)
I \ (A B) = (I \ A) (I \ B).