Свойства логических операций.

Док-во. Для доказательства любой из приведённых формул требуется построить таблицы истинности для частей формулы, стоящих слева и справа от символа эквивалентности Û, для всех значений истинности входящих в формулу высказываний, и показать, что они совпадают. Докажем, например, формулу 8. Таблица истинности:

Значения истинности для левой и правой частей формулы совпадают при любых истинностях входных высказываний, следовательно, левая и правая части формулы действительно эквивалентны. (Отметим аналогию между этой формулой и формулой 10. из раздела "1. Элементы терии множеств").

В дальнейшем мы будем отождествлять высказывание и его значение истинности, т.е. считать, что А = 1, если А - истинно, и А = 0, если А - ложно.

2.2. Кванторы.

В этом разделе мы расширим понятие термина "высказывание", чтобы ввести в рассмотрение утверждения вида х>7. Строго говоря, это утверждение не является высказыванием в смысле опр.2.1.1, так как мы не можем сказать, истинно оно или ложно (оно истинно, если, например, xÎ[12,15] и ложно, если xÎ[ 2, 5]). Тем не менее, утверждения, содержащие переменные x, y, z,… с областями возможных значений X, Y, Z,…, обладающие тем свойством, что для каждого набора переменных xÎ X, yÎ Y, zÎ Z,…истинность утверждения может быть установлена, в дальнейшем тоже будем называть высказываниями. Зависимость высказываний А, В, … от переменной x будем обозначать как А(х), В(х),… xÎ X. Подмножество Х(А)ÍХ множества Х такое, что для любого хÎХ(А) высказывание А(х) истинно, будем называть областью истинности высказывания А (так, для высказывания х>-2, X=[-5, 5] будет Х(А) = (-2, 5]).

Кванторы - логические операции, с помощью которых по некоторому высказыванию А(х) получают новые высказывания, характеризующие область истинности высказывания А(х).

Опр. 2.2.1. Квантором всеобщности (обозначение - ") высказывания А(х), xÎ X, называется логическая операция, имеющая значение "истина", если высказывание А(х) истинно для любого элемента xÎ X, и значение "ложь" в противоположном случае (т.е. в случае, когда хотя бы для одного xÎ X высказывание А(х) ложно).

Формула "хÎХ, А(х) читается как "для любого х, принадлежащего Х, справедливо А(х)"; "все х из Х удовлетворяют условию А(х)" и т.д. Формальное определение квантора всеобщности:

Примеры: высказывание ("хÎ[-2,4], x²>-2) - истинно, высказывание ("хÎ[-2,4], x²>16) - ложно, высказывание ("хÎN, x²>0) - истинно, высказывание ("хÎR, x²>0) - ложно.

Опр. 2.2.2. Квантором существования (обозначение -$) высказывания А(х), xÎ X, называется логическая операция, имеющая значение "истина", если высказывание А(х) истинно хотя бы для одного элемента xÎ X, и значение "ложь" в противоположном случае (т.е. в случае, когда высказывание А(х) ложно для всех xÎ X).

Формула $хÎХ, А(х) читается как "существует (найдётся) (хотя бы один) элемент х, принадлежащий Х, для которого справедливо А(х)". Формальное определение квантора существования:

Примеры: высказывание ($хÎ[-2,4], x² > 20) - ложно, высказывание ($хÎ[-2,4], x² > 10) - истинно, высказывание ($хÎN, x² = 0) - ложно, высказывание ($хÎR, x² = 0) - истинно.

Опр. 2.2.3. Квантором существования и единственности (обозначение -$!) высказывания А(х), xÎ X, называется логическая операция, имеющая значение "истина", если на множестве X существует элемент x, для которого высказывание А(х) истинно, и такой элемент единственен, и значение "ложь" в противоположном случае (т.е. в случае, когда высказывание А(х) ложно для любого элемента xÎ X либо А(х) истинно более чем для одного элемента xÎ X).

Формула $! хÎХ, А(х) читается как "существует единственный элемент х, принадлежащий Х, для которого справедливо А(х)”. Формальное определение квантора существования и единственности:

Примеры: высказывание ($! хÎ[-2,4], x² ³ 16) - истинно, высказывание ($!хÎ[-2,4], x² > 15) - ложно, высказывание ($!хÎN, x² £ 1) - истинно, высказывание ($!хÎR, x² £ 1) - ложно.

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

.

При проведении математических рассуждений (доказательство теорем от противного, формулировки противоположных теорем и т.д.) часто приходится строить отрицания некоторых утверждений. Рассмотрим простой пример. Пусть дано определение: "Группа называется хорошей, если любой (")студент этой группы - хороший", требуется построить логически следующее из этого определения новое - определение плохой группы. Правильный ответ: "Группа называется плохой, если хотя бы один ($)студент этой группы - плохой". Этот пример подсказывает следующие правила взаимодействия кванторов существования и единственности с операцией отрицания:

1. ù("хÎХ, А(х))Û$хÎХ, ùА(х);

2. ù($хÎХ, А(х))Û"хÎХ, ùА(х).

Док-во. Докажем первую эквивалентность. Если истинно высказывание ù("хÎХ, А(х)) (не для "хÎХ истинно А(х)), то $хÎХ, для которого А(х) ложно, т.е. истинно ùА(х). Импликация ù("хÎХ, А(х))Þ $хÎХ, ùА(х) доказана. Если истинно высказывание $хÎХ, ùА(х) (существует хÎХ, для которого А(х) ложно), то не для любого хÎХ истинно А(х), т.е.ù("хÎХ, А(х)). Импликация $хÎХ,ùА(х) Þ ù("хÎХ, А(х))доказана. По формуле 12 таблицы Свойства логических операцийиз доказанных импликаций следует эквивалентность левой и правой частей первой формулы.

Аналогично доказывается вторая формула. Формулы 1 и 2 имеют простой смысл. Именно, если мы хотим опровергнуть утверждение "хÎХ, А(х) (для любого х из Х верно А(х)), достаточно найти хотя бы один х, для которого А(х) неверно: $хÎХ, ùА(х). Если опровергается утверждение $хÎХ, А(х) "существует х, для которого верно А(х)", необходимо доказать, что А(х) неверно для любого х: "хÎХ, ùА(х).

Задание. Самостоятельно доказать формулу 2.

Если высказывание А(х) содержит несколько кванторов, то операция отрицания меняет каждый из них. Так, отрицание утверждения "число b есть предел функции f(x) в точке x=a…."

запишется так:

ù .

2.3. Математические теоремы, их виды и логическая структура.