Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




1. (ù ùА) Û (А). 7. ((АÙВС) Û (АÙ(ВÙС)).
2. ( ù (АÚВ)) Û (ùАÙùВ). 8. ((АÚВС) Û ((АÙС)Ú(ВÙС)).
3. ( ù (АÙВ)) Û (ùАÚùВ). 9. ((АÙВС) Û ((АÚС)Ù(ВÚС)).
4. (АÚВ) Û (ВÚА). 10. (АÞВ) Û ( ù АÚВ).
5. (АÙВ) Û (ВÙА). 11. (АÞВ) Û ( ù ВÞù А).
6. ((АÚВС) Û (АÚ(ВÚС)). 12. (АÛВ) Û (АÞВ)Ù(ВÞА).

Док-во. Для доказательства любой из приведённых формул требуется построить таблицы истинности для частей формулы, стоящих слева и справа от символа эквивалентности Û, для всех значений истинности входящих в формулу высказываний, и показать, что они совпадают. Докажем, например, формулу 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], x2>-2) - истинно, высказывание ("хÎ[-2,4], x2>16) - ложно, высказывание ("хÎN, x2>0) - истинно, высказывание ("хÎR, x2>0) - ложно.

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

ù .

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


Поделиться:

Дата добавления: 2015-07-26; просмотров: 73; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.011 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты