- •Элементы дискретной математики
- •1. Начальные понятия и модели
- •1.1. Множества
- •1.1.1. Понятие множества
- •1.1.2. Представление множеств
- •1.1.3. Операции над множествами
- •1. Объединение множеств
- •2. Пересечение множеств
- •3. Разность множеств
- •5. Степень множества
- •1.1.4. Мощность множеств
- •Определение
- •Определение
- •Упражнение. Показать, что если a равномощно b, а b равномощно c, то a равномощно c.
- •Теорема 1.1
- •Доказательство
- •Упражнение
- •Теорема 1.3
- •1.2.1. Основные понятия
- •1.2.2. Произведение отображений
- •1.3. Логика доказуемости и истинности
- •1.3.1. Высказывания
- •1.3.2. Парадоксы
- •Квантор существования
- •Квантор всеобщности
- •1.3.4. Доказуемость и выводимость
- •1.3.5. Структура утверждений и доказательств
1.3.5. Структура утверждений и доказательств
ТЕОРЕМ
Формулировки утверждений или теорем, которые приходится доказывать в различных областях деятельности, бывают одного из следующих двух видов.
1. ”Если A, то B“. Такое утверждение называется достаточными условиями, когда в предположении истинности соотношений, представляемых A, следует истинность соотношений B. Говорят, что условия A являются достаточными для B.
Доказательство такого утверждения использует соотношения, входящие в A, и, возможно, другие известные соотношения с целью получения вывода, содержащего B, если используется схема получения следствий или противоречия, если применяются рассуждения от противного.
2. “A тогда и только тогда, когда B“. Такое утверждение называется критерием. В этом утверждении A называется необходимыми условиями, а B достаточными условиями. Оно эквивалентно двум утверждениям приведенного ранее вида: ”Если A, то B“ и ”Если B, то A“. Поэтому доказательство критерия состоит из двух частей. Доказательство первого из приведенных утверждений называется доказательством необходимости, а второго доказательством достаточности.
Если в произвольном критерии переставить правое и левое соотношения, то наименования таких соотношений как необходимого и достаточного также поменяются. Доказательство необходимости исходного критерия превратится в доказательство достаточности нового критерия. Аналогично, доказательство достаточности исходного критерия превращается в доказательство необходимости для нового критерия.