4.5. Логические операции и формулы. Булевы функции можно рассматривать как логические операции над величинами, принимающими значения 0 или 1. Отрицание — это одноместная операция, а конъюнкция, дизъюнкция, импликация и эквиваленция — двухместные операции. При этом выражения X, Y, ,X Y, X В, А В, А В являются логическими формулами.
Более сложные формулы получаются замещением входящих в них переменных другими логическими формулами, которые обычно заключаются в скобки. Например, положив и , из формулы получаем формулу . Каждая формула определяет булеву функцию. Ее значения при различных значениях переменных А, В, С определяются по таблице истинности, построенной на основании таблиц истинности, приведенных в п. 4.2 и п. 4.3.
Равносильность функций (и определяющих их формул) понимается в смысле равносильности отображений (см. п. 3.2).
4.6. Булева алгебра — это тройка B = [F Z2 ], где F — множество всех булевых функций, = {¯, , } — множество трех логических операций: отрицание, конъюнкция, дизъюнкция. Из определения логических операций легко следует справедливость тождеств (свойств) булевой алгебры:
коммутативность
= , = ;
ассоциативность
= , = ;
дистрибутивность
= , = ;
поглощение нуля
;
умножение на единицу
;
свойства отрицания
, .
4.7. Тождественные преобразования. Приведенные свойства позволяют получить ряд других важных законов и тождеств уже без обращения к таблицам истинности:
, (законы де Моргана),
(законы поглощения),
(законы идемпотентности),
а также тождества:
,
,
, , , ,
и т.д.
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. Множество истинности предиката — это множество всех значений переменной , при которых данный предикат является истинным высказыванием.
Строго говоря, предикат — это отображение
: 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-местный предикат — высказывание.
Запись с восклицательным знаком !у читается «существует единственный у», а высказывание (х) (!у) Р(х, у) читается «для любого х существует и притом единственный у, для которого Р(х, у)».
Упражнение. Приведите пример, показывающий неравносильность высказываний (х) (у) Р(х, у) и (у) (х) Р(х, у).
Математический анализ Множества. Декартово произведение двух множеств. Отображения функции, обратная функция. Эквивалентность множеств. Счетность множества...
Группы: мк-301, мт-301 Понятия множества и отображения, способы задания множеств. Алгебра множеств и подмножеств. Теорема об отображении множества самого...
1 Содержание дисциплины Множества, подмножества. Булевы операции над множествами и их свойства. Законы Д’Моргана. Отношения, функциональные отношения, отображения....
1-й и 2-й семестры Множества и отображения Множество и его элементы. Примеры множеств. Отношение включения и его свойства. Операции над множествами: пересечение, объединение,...
, X Y, X В, А В, А В являются логическими формулами.
и 
, из формулы 
получаем формулу 
. Каждая формула определяет булеву функцию. Ее значения при различных значениях переменных А, В, С определяются по таблице истинности, построенной на основании таблиц истинности, приведенных в п. 4.2 и п. 4.3.
, 
= 
;
= 
, 
= 
;
= 
, 
= 
;
;
;
, 
.
, 
(законы де Моргана), 
(законы поглощения),
(законы идемпотентности),
,
,
, 
, 
, 
, 
= 
:
:
«Число х — положительное» — одноместный предикат, предложение 
«х > у» — двуместный предикат, предложение 
«
» — n-местный предикат. 
— это множество всех значений переменной 
, при которых данный предикат является истинным высказыванием. 
— это отображение
в множество Z2; при этом D называется областью определения предиката. Тогда множество истинности предиката 
D элемента 1 Z2.
. 
и 
, определенных на множестве 
. Тогда из 4.10, 4.3, 2.11 и 2.12 следует
, 
,
, 
.
,
.
«
» 3-местный предикат, определенный на множестве 
. Связав любую переменную квантором (общности или существования), мы получим 2-местный предикат, например, 
.■
, то n-местный предикат превратится в (n – k)-местный. Причем 0-местный предикат — высказывание.
