Законы построения отрицания

Приведем основные пары равносильных формул, позволяющие строить отрицания к предложениям, содержащим всевозможные логические связки. Каждый закон будем иллюстрировать содержательным примером.

Пусть буквы А и В обозначают произвольные предложения.

1°. Закон двойною отрицании. Отрицание к отрицанию, А равносильно А:

Этот закон очевидным образом вытекает из определения операции отрицания.

Пример 3.1.1. Предложение «Неверно, что число (-2) не целое» означает, что число (-2) целое. •.

2°. Отрицание к дизьюнк’ции. Отрицание к дизъюнкции, А и В равносильно конъюнкции отрицаний, А и В:

Докажем это правило с помощью построения таблицы истинности.

Пример 3.1.2. Построим отрицание к предложению «Функция является четной или нечетной», которое имеет структуру AvB, где А = «Функция является четной», В = «Функция является нечетной».

Отрицание: «Функция нс является четной и нс является нечетной».

В данном примере предложение В не является отрицанием А. Можно привести пример функции, при котором отрицание является верным высказыванием. •.

А вот предложение вида «А или не А», где фраза «не А» понимается именно как отрицание к А, всегда принимает истинное значение, так как формула Av~a есть тавтология. Тогда отрицание к этому предложению всегда ложно. По первым двум правилам отрицание формулируется так: «Нс А и А». Здесь утверждается, что предложение А одновременно ложно и истинно, чего не может быть.

3°. Отрицание к конъюнкции. Отрицание к конъюнкции, А и В равносильно дизъюнкции отрицаний, А и В:

Докажите этот закон самостоятельно.

Пример 3.1.3. Дано предложение: «Число больше 0, но меньше 5». Отрицание: «Число нс больше 0 или не меньше 5». Символически это запишется так:

Вывод: при построении отрицания к предложениям «А и В» и «А или В» союзы «и» и «или» меняются друг на друга.

Сформулированные правила построения отрицания к конъюнкции и дизъюнкции называются законами де Моргана (Огастес де Морган — шотландский математик, 1806−1871).

Наряду с законом 3° часто бывает полезно применить другой закон.

4°. Выражение отрицания к конъюнкции через импликацию

Докажите этот закон самостоятельно.

Тогда отрицание к предложению «Число больше 0, но меньше 5» можно сформулировать гак: «Если число больше 0, то оно не меньше 5».

5°. Отрицание к импликации

Докажите самостоятельно.

Пример 3.1.4. Дано предложение: «Если число рациональное, то оно целое». Отрицание: «Число рациональное, но не целое». •.

Заметим, что правила 4° и 5° являются взаимно двойственными в том смысле, что, взяв любое из правил и заменив знаки д и -" друг на друга, мы получим другое правило данной пары.

Рассмотрим пример на использование нескольких законов.

Пример 3.1.5. Петя пообещал, что сегодня вечером при условии, если Катя не позовет его в кино, он сделает домашнее задание или посмотрит телевизор. В каких случаях Петя не выполнит данное им обещание?

Запишем обещание Пети формулой. Для этого введем обозначения предложений.

А = «Катя позовет Петю в кино»,.

В = «Петя выполнит домашнее задание»,.

С = «Петя посмотрит телевизор».

Теперь обещание Пети можно выразить формулой: ~U^Z?vC.

Построим и преобразуем отрицание, используя вначале правило 5°, затем правило 2°:

Таким образом, Петя нс выполнит обещание в одном случае: Катя нс позовет его в кино, но он не выполнит домашнее задание и не посмотрит телевизор. •.

6°. Отрицании к кванторам.

Равносильность указанных формул была обоснована в предыдущем параграфе.

Пример 3.1.6. Рассмотрим множество учеников некоторого класса. Пусть А (х) обозначает предложение: «Ученик х отличник».

Тогда предложение «Неверно, что все ученики класса отличники» (или, по-другому, «Не все ученики класса отличники») равносильно утверждению «В классе найдется ученик, не являющийся отличником». А предложение «В классе нс существует отличника» означает, что любой ученик класса нс является отличником.

Интересно отметить, что если мы имеем в виду не какой-то конкретный класс, то предложение А является двуместным предикатом. Другая переменная в этом случае будет обозначать класс какой-то школы. Однако рассмотренные законы нс зависят от того, сколько переменных содержится в предложении А. И вообще, вместо букв А и В к рассмотренные выше законы можно подставлять любые формулы. •.

Пусть требуется опровергнуть утверждение, заданное формулой /хА (х) (то есть доказать, что это утверждение ложно). Для этого надо доказать, что истинно его отрицание, которое в соответствии с законом 6° имеет вид 3, y~U (, y). Значит, нужно привести пример хотя бы одного объекта х, для которого предложение А (х) неверно. Такой объект называется контрпримером к утверждению V. y/J (y).

Пример 3.1.7. Опровергнем утверждение «Все целые числа положительны». Контрпример: целое число (-3) не является положительным. Есть другие примеры целых неположительных чисел. Но для полного доказательства достаточно только одного контрпримера. •.

На основе рассмотренных законов можно выработать общие правила формулировки отрицания к типам предложений, рассмотренных в пункте 2.2.

Пусть имеется предложение: «Для любого х, такого, что А (.х), выполняется В (х)». Для того чтобы сформулировать отрицание к этому предложению, построим отрицание к формуле V* (Л (*)—"#(*)).

Последовательно применим законы 6° и 5°:

Получим предложение: «Существует х, такое, что А (х для которого неверно, что В (х)».

Пусть имеется предложение: «Существует х, такое, что А (х), для которого В (х)». Для того чтобы сформулировать отрицание к этому предложению, построим отрицание к формуле Зх (Л (х)л/?(х)). Последовательно применим законы 6° и 4°:

Получим предложение: «Ни для одного х, такого, что А (х), не выполняется В (х)».

На языке ограниченных кванторов имеем следующее правило.

7°. При построении отрицания к предложениям вида /ха (_Х)В (х) и ЗхуЦх) В (х) знаки кванторов меняются друг на друга, отрицание переносится на предикат В (х), а ограничение А (х) остается неизменным:

Пример 3.1.8. Построим отрицания к предложениям и выясним, какие из них верны, а какие ложны:

• а) Любое целое число, делящееся на 6, делится на 4.
• б) Некоторые числа, делящиеся на 6, делятся на 4.

Для решения поставленной задачи введем два предиката, определенных для целых чисел:

А (х) = «х делится на 6» или, используя знак делимости, А (х) = (х:6),.

В (х) = «х делится на 4» = (х:4).

Пункт а). Имеем формулу Vx (Л (х)-«Я (х)). Отрицание к ней имеет вид.

3.V (Л (лг)лТВ (.г)).

Формулируем отрицание: «Существует целое число, делящееся на 6, но не делящееся на 4».

Так как существует число 18, делящееся на 6, но нс на 4, то отрицание предложения является истинным высказыванием, а исходное предложение — ложным.

Пункт б). Предложение имеет логическую структуру Зх (А (х)лВ (х)). Отрицание к формуле имеет вид Vx (А (х) —«~|#(х)).

Формулируем отрицание: «Любое целое число, делящееся на 6, нс делится на 4».

Здесь исходное предложение верно, так как, например число 12 делится и на 6, и на 4. Отрицание к предложению ложно. •.

Пример 3.1.9. Построим отрицание к предложению из примера 2.2.2. Предложение «Найдется такое положительное рациональное число а, что все положительные числа, меньшие а, будут иррациональными» имеет символическую запись (3a>, 6f€Q) (Vx>0,rправилу 7°: (Va>, aeQ) (Зд^Ю^^Ддге!). Утверждение «Действительное число не является иррациональным» равносильно утверждению «Число рациональное». Поэтому формулу можно переписать так:

Сформулируем отрицание: «Для любого положительного рационального числа а существует положительное число, меньшее а, являющееся рациональным».

Отрицание является истинным высказыванием, так как какое бы положительное рациональное число а мы не взяли, положим, что х=а/2. Число х очевидно положительное, меньше а. При этом х рациональное, как частное от деления двух рациональных чисел. Таким образом, исходное утверждение неверно. •.

Пример 3.1.10. Построим отрицание к предложению из примера 2.2.3. Предложение «При любом положительном числе е существует такое положительное число с, что при всех х, по модулю больших с, значение —.

X

(I Л будет меньше е" записывается формулой: (Ve>0) (3с>0) > с) — < s .

<^х)

Заметим, что это предложение верно. Действительно, при любом s возьмем с = 2/е. Тогда для любого значения *, которое по модулю будет больше с, выполняется неравенство |1/д:|<1/с. Так как с = 2/е, то 1/с = 0,5е, что меньше 8. Значит, выражение |1/д;| будет меньше 8.

Строим отрицание:

читаемое так: «Существует такое положительное число 8, что при любом положительном числе с найдется число х, по модулю большее с, для которого число — будет не меньше е».

х

Так как было доказано, что исходное предложение верно, значит, отрицание является ложным утверждением.

Итак, для того чтобы опровергнуть некоторое предложение, то сеть доказать, что оно ложно, можно сформулировать отрицание к этому предложению и доказать его истинность. •.