Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Булева алгебра
|
|
Булевы функции двух переменных. Все 16 функций двух переменных приведены в табл. 6, где указаны условные обозначения, названия и чтения функций (в скобках даны встречающиеся в литературе варианты).
Шесть из приведенных функций не зависят от x1 или x2 (или от обоих вместе). Это две константы (у0 = 0 и у15 = 1), повторения (у3 = х1 и у5 = х2) и отрицания (у10 = 
и у12 = 
), являющиеся функциями одной переменной (х1 или x 2). Из остальных десяти функций две (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 и x2 (и x1 и 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, то она вырождается в соответствующую константу и называется тождественным нулем или тождественной единицей.
Например, 
; 
; 
; 
и т. п.
Date: 2016-02-19; view: 465; Нарушение авторских прав