Булевы функции. Основные формулы булевой алгебры. Аналитическая запись булевых функций в булевом базисе. Дешифраторы. Мультиплексоры, страница 3

На практике часто возникает необходимость преобразовать функцию, аргументы которой связаны операцией Шеффера или Пирса к выражению, содержащему только операции конъюнкции, дизъюнкции и отрицания. Если символы отрицания расположены над одиночными символами переменных, то такая булева функция называется нормальной. Именно такие представления функций наиболее просто воспринимаются человеком. Для подобного преобразования в литературе обычно используют правила де Моргана, однако существует очень простой прием, позволяющий сразу записать искомый результат:

1) заменить в выражении операции Пирса и Шеффера на операции И-НЕ и ИЛИ-НЕ соответственно;

2) подсчитать число инверсий над каждой буквой, если оно четно, то в преобразуемое выражение эта буква будет входить без отрицания, если нечетно – с отрицанием;

3) подсчитать число инверсий над каждой логической операцией, если число инверсий четно, то операция не меняется, если нечетно, то логическая операция заменяется дуальной логической операцией.

Пример:

Для функций Шеффера и Пирса можно вывести тождества, похожие на правила склеивания и поглощения:

,  действительно,  ,

,

,                            

Аналитическая запись булевых функций в булевом базисе.

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

Пример: если рассмотреть функцию трех аргументов , то

, ,  -конституенты единицы. Напишем несколько выражений не являющихся конституентами 1:  (не все аргументы),  - используя правило де Моргана, получим: , а это противоречит определению конституенты 1.

Следствие: любая конституента 1 равна 1 только на одном наборе аргументов, на остальных наборах эта конституента равна нулю.

Для того чтобы определить набор на котором конституента 1 равна 1 следует найти такие значения аргументов, которые дают значение 1 каждому члену произведения. Пример: , если , а это возможно только на наборе 101.

Теорема: Любая булева функция может быть записана в виде дизъюнкции конституент 1, соответствующих тем наборам на которых функция равна 1.

Доказательство. Выберем в таблице истинности произвольный набор. При этом возможны два случая:

Если на данном наборе функция равна 1, то из множества конституент выберем конституенту равную 1 на этом наборе (на остальных наборах она будет равна нулю) и записываем ее в формулу. Учитывая свойство дизъюнкции 1+…=1,  мы обеспечиваем единичное значение функции на этом наборе.

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

После рассмотрения всех наборов мы получим аналитическую запись булевой функции в дизъюнктивной совершенной нормальной форме (ДСНФ).

Алгоритм перехода к ДСНФ:

- Выбрать в таблице истинности все наборы на которых функция равна единице.

- Записать конституенты 1 равные единице на этих наборах. При этом, если аргумент в наборе равен 1, то в конституенту единицы этого набора он записывается без отрицания. Если же аргумент в наборе равен нулю, то он записывается с отрицанием.

- Полученные конституенты соединить операцией дизъюнкции.

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

Любая конституента нуля равна нулю только на одном наборе, на остальных наборах она равна 1.

Теорема. Любая булева функция может быть записана как конъюнкция конституент нуля, записанных для наборов,  где функция равна нулю.