Материал: 5540

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

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

Переменные х1 и х2 определяют некоторую логическую функцию у = f(х1, х2), которая в случае дизъюнкции может быть записана как

Между таблицей истинности и диаграммой Эйлера – Вена существует взаимно однозначное соответствие. Поэтому число единиц для у всегда будет совпадать с числом заштрихованных областей на диаграмме.

Пересечению множеств А и В соответствует класс С3. Тот факт, что х принадлежит одновременно двум множествам А и В, можно представить выражением:

х А В (х А) (х В),

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

единицами, а все единицы – нулями, то в итоге получим таблицу истинности для конъюнкции (таблица 2.2). Этот факт определяет взаимную двойственность конъюнкции и дизъюнкции.

31

Таблица 2.2 – Таблица истинности для конъюнкции

Для любой логической операции можно найти двойственную.

Для любого подмножества А и универсального множества U выполняются тождества

АА U, А А Ø.

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

Дополнение к любой логической переменной х, т.е. x (не х), называется в логике отрицанием х.

Тавтология – это всегда истинное логическое выражение. Противоречие, напротив, всегда ложное выражение.

Для классов А В С0 (рисунок 2.3) и А В С0 С1 С2

(рисунок 2.4) вводят новые операции, которые соответственно называют

стрелка Пирса (или функция Вебба) и штрих Шеффера:

32

(х1 х2) (х1 | х2) = 1, (х1 х2) (х1 | х2) = 0.

Из таблиц истинности для этих операций (таблицы 2.3 и 2.4) видно, что

Разности множеств А и В (рисунок 2.5) А \ В = С1 соответствует логическая функция у = х1 – х2 (таблица 2.5), её дополнением служит

импликация (таблица 2.6):

у х1 х2 х1 х2.

А В

Рисунок 2.5 – Разность множеств А и В

Симметрическая разность (строгая дизъюнкция, сумма по модулю два)

двух множеств А и В (рисунок 2.6) есть объединение двух разностей (таблица 2.7).

33

Рисунок 2.6 – Симметрическая разность множеств А и В

Таблица 2.7 – Объединение двух разностей

Эквивалентность (рисунок 2.7) определяется теми элементами множеств А и В, которые для них являются общими. Однако элементы, не входящие ни в А, ни в В, также считаются эквивалентными (таблица 2.8).

А В

Рисунок 2.7 – Эквивалентность

Таблица 2.8 – Эквивалентные элементы

Из условия дополнительности операций вытекают следующие соотношения:

34

Функция n переменных, где каждая переменная принимает значение из множества {0, 1}, а сама эта функция при любом наборе значений переменных принимает значение из того же множества {0, 1} называется

функцией Буля или функцией алгебры логики n переменных:

(упорядоченные наборы) длиной n, состоящие из символов 0 и 1. При этом каждому варианту кортежа должен быть поставлен в соответствие единственный элемент из множества {0, 1} – значение булевой функции.

Всего у булевой функции n переменных может быть 2n аргументов.

Число различных функций алгебры логики n переменных равно 22n .

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

Пример 2.1. Составьте таблицу истинности для булевых функций двух переменных.

Решение. Таблица истинности для булевых функций двух переменных

(таблица 2.9) имеет 22 = 4 строки и содержит 222 16 функций.

Таблица 2.9 – Таблица истинности для булевых функций двух переменных

35