Основные элементарные функции.

Логически операцию объединения двух множеств можно охарактеризовать слова­ми: элемент х принадлежит множеству А или множеству В. При этом связка “или” одновременно означает и связку “и”. Факт принадлежности элемента х множеству А обозначается как х  А. Поэтому то, что х принадлежит А или/и В, выражается формулой.

,

где  — символ логической связки или, которая называется дизъюнкцией.

С точки зрения логики, вместо одной предметной переменной х удобно ввести две логические переменные х₁ и х₂. Областью определения х₁ и х₂ будут уже не числа натурального ряда, а только два логических значения: 1 для истинного значения и 0 для ложного.

Рассмотрим два множества:  и .

Допустим, что х =7. Поскольку это число не принадлежит ни множеству А, ни множеству В, то и логические значения переменных будут:  и . Эта ком­бинация переменных отвечает классу . Теперь предположим, что выбрано число 4. Оно входит как в А, так и в В. Следовательно,  и , что соответст­вует классу . Существуют еще два варианта, например для числа х =6 имеем , , и для x =8 — значения , , которые отвечают классам  и .

Переменные х₁ и х₂ определяют некоторую логическую функцию:

y=f(х₁, х₂),

которая в случае дизъюнкции может быть записана как пропозиционная связка:

.

Легко усматривается, что число 7 не входит в объединенное множество А В, поэтому при  и  значение логической функции у равно нулю. Когда же выбираются числа 4, 6 или 8, то все они непременно попадут в заштрихованную область диаграммы, следовательно, при этих значениях функция  равна едини­це. Все это удобно оформить таблицей (табл. 1), которую называют таблицей истинности.

Между таблицей истинности и диаграммой Эйлера — Венна существует вза­имно однозначное соответствие. Поэтому число единиц для у всегда будет сов­падать с числом заштрихованных областей на диаграмме Четыре комбинации аргументов х₁ и х₂ будут отвечать четырем областям С _i. Кроме того, нетрудно подсчитать, что число комбинаций нулей и единиц для функции у равно 16, зна­чит и общее число возможных операций на двух множествах тоже равно этому же числу.

Рассмотрим пересечение тех же множеств.

А В ={1, 2, 4, 6} {2, 3, 4, 8, 9}={2, 4}= С₃,

То, что х принадлежит одновременно двум множествам А и В, можно представить выражением

где  - символ логической связки “и”, кото­рая называется конъюнкцией и может обозначаться также значком &. Если в табли­це истинности для конъюнкции (табл. 1.) все нули заменить единицами, а все едини­цы — нулями, то в итоге получим таблицу истинности для дизьюнкции.

Этот факт определяет взаимную двойственность конъюнкции и дизъюнкции.

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

Для любой логической операции можно найти двойственную. Представим себе операцию, в результате которой окажутся заштрихованными области  и , образующие множество А. Затем еще одну операцию, которая охватит две другие области  и , не входящие в А, что обозначается как . Если объединить заштрихованные области на обеих диаграммах, то получим все множество 1; пересечение же А и  даст пустое множество 0, в котором не содержится ни одного элемента:

,

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

 - тавтология,

 - противоречие.

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

Множество А дополняет множество  до фундаментального множества U (или 1), отсюда название, дополнительное множество А или дополнение как опе­рация. Дополнение к логической переменной х, т.е.  (не-х), называется в логике чаще всего отрицанием х.

Тогда могут быть введены следующие функции:

 - стрелка Пирса,

 - штрих Шефера.

Разностью между двумя множествами являлась совокупность элементов первого множества, которые не принадлежали второму. Т.е., продолжая предыдущий пример,

.

Тогда соответствующая булева функция, представленная в табл. 1, будет иметь вид:

.

Дополнением к разности служит импликация:

.

Замечание. Если утверждается, что “элементы множества А включены в множество В ”, то область  обязательно должна быть заштрихована, так как она соответствует истине, а область  с такой же необходимостью должна быть оставлена белой, поскольку ей отвечает прямо противоположное утверждение. Относительно об­ластей  и , находящихся в А, заметим следующее. Мы не имеем права остав­лять их белыми, поскольку они прямо не противоречат первому утверждению; но, так как логика двузначная, мы обязаны все же области, попадающие в , за­штриховать. В трехзначной логике эти области должны быть заштрихованы как-то иначе, а в таблице истинности для импликации (табл. 1) на месте пер­вой и третьей строк для  должны стоять не 1, а 1/2, что отвечает состоянию неоп­ределенности. При этом в классической двузначной логике импликация передается словами “если А, то В”.

Симметрическая разность двух множеств дает нам следующую булеву функцию:

,

называемую в литературе “сложение по модулю 2” и дополнением к ней будет являться функция эквивалентности:

.

 

Табл. 1. Таблица истинности основных элементарных функций.

0	0	1	0	0	1	0	1	1	1	0
0	1	1	0	1	1	1	0	1	0	0
1	0	0	0	1	0	1	0	1	0	1
1	1	0	1	1	1	0	1	0	0	0