Материал: 5540

Условием (или посылкой) этой теоремы является предложение «Натуральное число n делится на 6», а заключением – предложение «(Натуральное) число n делится на 3».

Вформе «если ..., то ...» можно записывать разные утверждения. Например, рассмотрим следующее утверждение: «Если число n делится на 6, то число n нечётное». В этом примере из предположения истинности условия утверждения уже не следует истинность заключения. Поэтому сформулированное утверждение не является теоремой.

Вкаждой теореме можно выделить заключение и условие этой теоремы. Условие теоремы называется достаточным условием для заключения теоремы.

Так, в теореме «Если натуральное число n делится на 6, то число n делится на 3» условие «Число n делится на 6» достаточно для того, чтобы число n делилось на 3.

Заключение теоремы называют необходимым условием для условия этой теоремы.

Так, в теореме «Если натуральное число n делится на 6, то число n делится на 3» заключение «Число n делится на 3» необходимо, чтобы «Число n делилось на 6». Другими словами, если натуральное число n не делится на 3, то число n не может делиться на 6.

Для каждой теоремы можно записать обратное утверждение,

противоположное утверждение и противоположное обратному.

Импликацию В А, полученную из А В перестановкой условия и заключения, называют конверсией (обратным высказыванием) для А В .

Снова рассмотрим теорему: «Если натуральное число n делится на 6, то число n делится на 3». Утверждение, обратное к этой теореме, имеет следующий вид: «Если натуральное число n делится на 3, то число n делится на 6». Полученное в этом примере обратное утверждение не является теоремой, потому что из делимости натурального числа n на 3 не следует делимость числа n на 6. В этом очень легко убедиться на примере: число 9 делится на 3, но не делится на 6.

Рассмотрим теперь теорему «Если натуральное число n делится на 2 и делится на 3, то число n делится на 6». Утверждение, обратное к этой

66

теореме, имеет следующий вид: «Если натуральное число n делится на 6, то число делится на 2 и делится на 3».

В этом примере полученное обратное утверждение является теоремой. Таким образом, утверждение, обратное к некоторой теореме, иногда

тоже является теоремой, а иногда не является теоремой.

Импликацию А В , полученную из А В заменив и условие, и заключение их отрицаниями, называют инверсией (противоположным

Полученная таблица позволяет сделать следующие выводы. Условное высказывание и его контрапозиция являются

равносильными (логически эквивалентными).

Высказывание обратное и противоположное условному являются равносильными (логически эквивалентными).

Импликация не обладает переместительным свойством, т.е. если

Итак, прямая и обратная импликации не равны между собой, но прямая и обратная теоремы не всегда имеют противоположный смысл.

67

Существуют такие высказывания, для которых одновременно справедливы и прямая, и обратная импликации, т.е. А В и В А. Такие логические операции называются эквиваленцией. На языке логических операций это

Вслучае, если условие теоремы содержит слова «необходимо и достаточно», при её доказательстве нужно доказать не только прямую теорему, но и обратную.

Слова необходимо и достаточно можно заменить словами «тогда и только тогда, когда», логическую операцию импликации – эквиваленцией.

Например, рассмотрим известную теорему, которая имеет следующую формулировку: «Натуральное число n делится на 3 тогда и только тогда, когда сумма цифр числа n делится на 3».

Такая формулировка объединяет в себе две взаимно обратное теоремы. Теорема 1. Если натуральное обратное число n делится на 3, то

сумма цифр числа n делится на 3.

Теорема 2. Если сумма цифр натурального числа n делится на 3, то число n делится на 3.

Вэтом примере условие делимости на 3 суммы цифр натурального числа n является необходимым и достаточным для делимости числа n на 3.

Всвою очередь условие делимости на 3 натурального числа n является необходимым и достаточным для делимости на 3 суммы цифр числа n.

Пример 3.8. Какие из следующих шести приведённых ниже

импликаций являются по отношению друг к другу обратными,

68

противоположными, противоположными обратным? Какие из них являются теоремами?

1) если каждое из натуральных чисел делится на 7, то и их сумма делится на 7;

2)если ни одно из двух чисел не делится на 7, то их сумма не делится на 7;

3)если хотя бы одно из двух чисел делится на 7, то и сумма делится на 7;

4)если сумма двух чисел делится на 7, то каждое слагаемое делится на 7;

5)если сумма двух чисел не делится на 7, то ни одно из слагаемых не делится на 7;

6)если сумма двух чисел не делится на 7, то хотя бы одно из слагаемых не делится на 7.

Решение. Пусть А – утверждение, что каждое из двух слагаемых делится на 7; В – сумма делится на 7; С – по крайней одно из слагаемых делится на 7.

Тогда приведённые выше импликации можно записать:

5)В С ;

6)В А .

Таким образом, 1 и 4, 2 и 5 импликации являются взаимнообратными; 2 и 3, 4 и 6 – взаимно противоположными; 1 и 6, 3 и 5 являются противоположными; 1 и 6 импликации являются теоремами.

Задача 3.14. В каждой из приведённых ниже импликаций выделите условие и заключение. Сформулируйте импликацию, противоположную данной и обратную противоположной. Определите, истинны они или ложны.

1)если вы находитесь в Африке, то вы находитесь южнее Москвы.

2)если я учусь в школе, то мне больше, чем два года.

3)если последняя цифра числа 17 равна 5, то оно делится на 5.

4)если сумма цифр числа 25 делится на 3, то это число делится на 3.

5)если сумма цифр числа 23 делится на 5, то это число делится на 5. Задача 3.15. Для каждой из приведённых ниже импликаций

69

сформулируйте обратную, противоположную и противоположную обратной. Какие из них являются теоремами?

1.Если число делится на 9, то сумма его цифр делится на 3.

2.Если натуральное число делится на 3 и на 5, то оно делится на 15.

3.Произведение двух положительных чисел положительно.

3.7 Нормальные формы формул логики высказываний

В алгебре высказываний используют две нормальные формы:

дизъюнктивную (ДНФ) и конъюнктивную нормальные формы формулы

(КНФ).

Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

ДНФ есть формула, имеющая вид дизъюнкции элементарных конъюнкций, т.е.

элементарных конъюнкций содержит пропозициональную переменную и её отрицание F F , то следует удалить всю элементарную конъюнкцию, т.к. F F 0 .

Процедура приведения к ДНФ:

1. Все отрицания «спустить» до переменных применяя правило:

2. Раскрыть скобки применяя закон:

70