Всего на сайте:
282 тыс. 988 статей

Главная | Математика

Булева алгебра  Просмотрен 663

Булевы функции двух переменных. Все 16 функций двух переменных приведены в табл. 6, где указаны условные обозначения, названия и чтения функций (в скобках даны встречающиеся в литературе варианты).

Шесть из приведенных функций не зависят от x1 или x2 (или от обоих вместе). Это две константы (у0 = 0 и у15 = 1), повторения (у3 = х1 и у5 = х2) и отрицания (у10 = и у12 = ), являющиеся функциями одной переменной (х1 или x2). Из остальных десяти функций две (y4 и y11) отличаются от соответствующих им (y2 и y13) лишь порядком расположения аргументов и поэтому не являются самостоятельными. Поэтому из 16 булевых функций двух переменных только восемь являются оригинальными (у1, у2, у6, у7, у8, у9, у13, у14).

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

Таблица 6

Булевые функции двух переменных

x1 x2 0 0 1 1 0 1 0 1 Обозначения Названия Чтение
y0 0 0 0 0 Константа 0 (тождественный нуль, всегда ложно) Любое 0
y1 0 0 0 1 x1x2; ( ; ) Конъюнкция (совпадение, произведение, пересечение, логическое «и») x1 и x2x1 и x2)
y2 0 0 1 0 ( ; ) Отрицание импликации (совпадение с запретом, антисовпадение, запрет) x1, но не x2
y3 0 0 1 1 X1 Повторение (утверждение, доминация) первого аргумента Как x1
y4 0 1 0 0 ( ; ) Отрицание обратной импликации (обратное антисовпадение) Не x1, но x2
y5 0 1 0 1 x2 Повторение (утверждение, доминация) второго аргумента Как x2
y6 0 1 1 0 x1 + x2 ( ; ) Сумма по модулю 2 (неравнозначность, антиэквивалентность) x1 не как x2 (или x2 или x1)
y7 0 1 1 1 (x1 + x2; ) Дизъюнкция (разделение, логическая сумма, сборка, логическое «или») x1 или x2 (x1 или хотя бы x2)
y8 1 0 0 0 ( ; ) Стрелка Пирса (функция Вебба, отрицание дизъюнкции, логическое «не – или») Ни x1,ни x2
y9 1 0 0 1 x1 ~ x2 ( ; ) Эквиваленция (равнозначность, эквивалентность, взаимозависимость) x1 как x2 (x1, если и только если x2)
y10 1 0 1 0 (x2; ~x2; x2) Отрицание (инверсия) второго аргумента (дополнение к первой переменной) Не x2
y11 1 0 1 1 ( ; ) Обратная импликация (обратное разделение с запретом, обратная селекция) Если x2, то x1 (x1 или не x2)
y12 1 1 0 0 (x1; ~x1; x1) Отрицание (инверсия) первого аргумента (дополнение к первой переменной) Не x1
y13 1 1 0 1 ( ; ) Импликация (разделение с запретом, следование, селекция) Если x1, то x1 (не x1 или x2)
y14 1 1 1 0 x1 / x2 ( ; ) Штрих Шеффера (отрицание конъюнкции, несовместность, логическое «не – и») Не x1 или не x2
y15 1 1 1 1 Константа 1 (тождественная единица, всегда истино) Любое 1

 

зависящиеот всех переменных, являются невырожденными. Так, среди функций одной переменной имеются две вырожденные (константы 0 и 1, которые можно рассматривать как функции от нуля переменных), функции двух переменных содержат те же константы и четыре функции одной переменной и т. д.

Зависимость между булевыми функциями.Из табл. 6 видно, что между функциями имеются зависимости (i = 0, 1, ... ..., 15), на основании которых можно записать соотношения для констант и , для функции одной переменной х = и для функций двух переменных:

x1x2 = ; = ; x1 + x2 = ; = ,

или

x1/x2 = ; = ; x1 ~ x2 = ; = .

Из этих зависимостей следует, что любая функция двух переменных (включая константы) выражается в аналитической форме через совокупность шести функций, содержащей отрицание и любую из каждой пары функций {y0, y15},{y1, y14},{y2, y13}, {y6, y9}, {y7, y8}. Например, такой совокупностью могут служить функции: константа 0, отрицание`х, конъюнкция х1x2, дизъюнкция ,эквиваленция х1 ~ x2 и импликация . Как уже упоминалось в (1. 5. 8), они используются в исчислении высказываний.

Выбранная таким способом совокупность шести функций является избыточной. Можно показать, что импликация и эквиваленция выражаются через остальные функции этой совокупности:

;

.

Для этого достаточно построить таблицу соответствия и сравнить ее с табл. 6:

x1 x2      
     
     
     

 

Таким образом, комплект элементарных функций сокращается до четырех: константа 0, отрицание , конъюнкция x1x2 и дизъюнкция . Этот комплект обладает существенными удобствами и часто применяется на практике, но и он может быть сокращен. Так, из законов де Моргана и свойства двойного отрицания вытекают тождества:

; x1x2 = .

Отсюда следует, что булевы функции выражаются через отрицание и конъюнкцию или через отрицание и дизъюнкцию.

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

;

x1x2 = (x1/x2)/(x1/x2); .

Булевы функции многих переменных. С помощью суперпозиции функций, т. е. подстановки в логические формулы вместо переменных некоторых булевых функций, можно получить более сложные функции от любого числа переменных. Например, подставляя в выражение аb формулы и , а также , получаем . Таблица соответствия для сложных формул записывается на основании общей таблицы для элементарных функций. Для данного примера она имеет вид:

x1 x2 x3

 

Если на всех наборах значений переменных функция принимает значение 0 или 1, то она вырождается в соответствующую константу и называется тождественным нулем или тождественной единицей.

Например, ; ; ; и т. п.

Предыдущая статья:Понятие логической функции Следующая статья:Тождественные преобразования
page speed (0.0158 sec, direct)