правой части A ∩ (B ∩ C).
Поскольку ответы для всех строк «Левой части» те же самые, что и для «Правой части», тождество является доказанным. Табличный метод особенно удобен при построении доказательств с использованием компьютера.
Алгебраический метод основывается на идее разбиения доказательства на шаги, при этом переход от одного шага к следующему осуществляется за счет применения какого-либо закона алгебры множеств (например, закона ассоциативности, дистрибутивности, поглощения и т. д.). Доказательство требует хорошего знания базисных законов алгебры множеств, а также определенный опыт их применения. Рассмотрим метод на следующем примере. Пусть требуется доказать, что
(A ∩ C)\(A ∩ B ∩ C) = A ∩ ВС ∩ C.
При переходе от одного шага к другому будем указывать (в правой части соответствующей строки) причины, позволяющие делать такие переходы:
В этом примере левое выражение преобразовано в правое. Это преобразование облегчается тем обстоятельством, что известно, какое выражение должно быть получено. В то же время можно и правое выражение привести к левому. Чтобы понять, как это сделать, достаточно просмотреть первое преобразование от конца к началу. Какой путь легче, не всегда бывает сразу ясно, поэтому иногда необходимо попробовать оба способа, чтобы добиться правильного результата.
1.10. Математическая индукция
Имеется следующее существенное свойство множества натуральных чисел:
N = {1, 2, 3, …}, которое используется при построении различных доказательств.
Принцип математической индукции
Пусть Р – некоторое утверждение, определенное на положительных целых N, т. е. утверждение Р(n) либо истинно, либо ложно для каждого n из N. Если для Р выполняются два следующих свойства:
1) P(1) истинно;
2) P(n+1) истинно, если истинно P(n), тогда Р истинно для каждого положительного целого.
Обычно этот принцип используется как аксиома для доказательства других результатов. Используем его для доказательства следующего результата.
Путь Р будет утверждением, что сумма первых n натуральных чисел, возведенных в куб, равна
, т. е.
Легко видеть, что P(n) истинно при n = 1, т. е. P(1): 13 =
Допустим теперь, что P(n) истинно и докажем, что P(n+1) также будет истинно. Для этого прибавим к обеим частям выражения для P(n) следующее слагаемое (n+1)3:
Преобразуем далее правую часть
Таким образом, P(n+1) истинно, когда истинно P(n). Теперь по принципу математической индукции утверждение Р истинно для всех n. Иногда принцип математической индукции записывают в более удобном для использования виде
1) P (1) истинно.
2) P (n + 1) истинно, если истинно P
