Множества, отображения, логика (стр. 5 )

 (законы поглощения),

 (законы идемпотентности),

а также тождества:

,

,

, , , ,

и т.д.

4.8. С помощью таблиц истинности доказывается, что

 = :

X	Þ	Y			Ú	Y
1	1	1		0	1	1
1	0	0		0	0	0
0	1	1		1	1	1
0	1	0		1	1	0

 

Аналогично доказывается, что :

X	Û	Y		X	Þ	Y	Ù	Y	Þ	X
1	1	1		1	1	1	1	1	1	1
1	0	0		1	0	0	0	0	1	1
0	0	1		0	1	1	0	1	0	0
0	1	0		0	1	0	1	0	1	0

 

4.9. Предикат — это предложение с одной или несколькими переменными, которое становится высказыванием, если переменные принимают конкретные значения. Предикат с n переменными называется n-местным. Например, предложение  «Число х — положительное» — одноместный предикат, предложение  «х > у» — двуместный предикат, предложение  «» — n-местный предикат.

4.10. Множество истинности предиката  — это множество всех значений переменной , при которых данный предикат является истинным высказыванием.

Строго говоря, предикат  — это отображение

j: D ¾® Z2,

некоторого подмножества  в множество Z2; при этом D называется областью определения предиката. Тогда множество истинности предиката  — это полный прообраз  Ì D элемента 1 Î Z2.

Множество истинности предиката  будем обозначать с помощью квадратных скобок: [].

4.11. Связь логики с теорией множеств. Из 4.10, 4.2, 2.14 следует, что .

4.12. Пусть даны два n-местных предиката  и , определенных на множестве . Тогда из 4.10, 4.3, 2.11 и 2.12 следует

, ,

или, проще,

, .

Для импликации и эквиваленции получаем:

,

.

4.13. Кванторы. Переменную в предикате можно связать квантором общности или квантором существования.

Квантор общности произошел от английского слова All (все), обозначается символом " и читается «любой, всякий, каждый»; символ " есть просто перевернутая буква А.

Квантор существования произошел от английского слова Exist (существовать), обозначается символом $ и читается «существует, имеется, найдется»; символ $ — это перевернутая буква Е.

Пример 1. Высказывание A = «Каждый день Красавице дарят розы» может быть формализовано как двуместный предикат P(x, y) = «В день х человек y дарит розы Красавице», у которого переменная х связана квантором общности ", а на переменную у навешан квантор существования $:

А = ("х) ($у) Р(х, у).■

Пример 2. Пусть «» 3-местный предикат, определенный на множестве . Связав любую переменную квантором (общности или существования), мы получим 2-местный предикат, например, .■

Вообще, если навесить по одному квантору на k переменных n-местного предиката, , то n-местный предикат превратится в (n – k)-местный. Причем 0-местный предикат — высказывание.

Запись с восклицательным знаком $!у читается «существует единственный у», а высказывание ("х) ($!у) Р(х, у) читается «для любого х существует и притом единственный у, для которого Р(х, у)».

Упражнение. Приведите пример, показывающий неравносильность высказываний ("х) ($у) Р(х, у) и ($у) ("х) Р(х, у).

4.14. Отрицание предиката с кванторами. Отрицание предиката  можно записать в «категоричной» форме:

,

а можно записать в более мягкой форме, заменив:

квантор " — на квантор $,

квантор $ — на квантор ",

предикат — на его отрицание:

 = .

Пример 3. Высказывание «Неверно, что у всех студентов есть мобильные телефоны» можно записать в равносильной — с точки зрения математической логики — форме: «Существует студент, у которого нет мобильника», или, иначе, «Не у всех студентов есть мобильники».■

Упражнение. Как будет выглядеть отрицание фразы «Каждому — свое»?