Метод непосредственного упрощения. Часть 2

2) Упростить функцию

.

Применим к трем последним членам закон поглощения

;

.

К первому и последнему членам снова применим закон поглощения:

.

Результат представлен на рис. 3.4.

Рис. 3.4.  К примеру 2

Метод непосредственного упрощения. Часть 1

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

При проектировании системы наибольший интерес представляет та форма функции, на которую расходуется минимальное количество элементов.

Примеры

1) В некоторой схеме управления имеются три входа  а, b  и  с. Сигнал на выходе должен появиться, когда имеются сигналы на двух любых или на всех трех входах (рис. 3.1).

Согласно приведенным условиям функция будет иметь следующий вид:

.

Рис. 3.1.  К примеру 1

Прибавим два раза член  abc.

На рис. 3.2  представлена схема, соответствующая полученному результату.

Применив к последнему выражению распределительный закон  х + yz = (x + y)(x + z),  поищем другое решение :

y = ab + ac + bc = a
(b + c) + bc = [a (b
+ c) + b] [a (b + c) + c] =

= (b + a)(b + b + c)(c + a)(c + b + c) = (a + b)(b + c)(a + c).

Этому результату соответствует функциональная схема, показанная на рис. 3.3.

Рис. 3.2.  К примеру 1

Рис. 3.3.  К примеру 1

Совершенные дизъюнктивные и конъюнктивные нормальные формы

Дизъюнктивная (конъюнктивная) нормальная форма называется совершенной, если все её элементарные конъюнкции (дизъюнкции) являются конституентами единицы (соответственно нуля).

Любая логическая функция имеет одну и только одну совершенную дизъюнктивную нормальную форму (СДНФ) и одну и только одну совершенную конъюнктивную нормальную форму (СКНФ).

Например :

Функцию  f = х + у  можно записать в СДНФ в виде

.

От любой нормальной формы можно перейти к совершенной нормальной форме при помощи равносильных преобразований. Такой переход называется развертыванием.

Для этого необходимо :

-        ввести недостающие переменные в каждое произведение умножением его на равносильность вида 

, где  х – недостающая переменная;

-        раскрыть скобки, применяя коммутативный закон (ху = ух);

-        избавиться от повторяющихся произведений на основании закона тавтологии  (х + х = х).

Пример

Рассмотрим нормальную форму:

.

Преобразуем её:

.

Аналогично можно перейти и к совершенной конъюнктивной нормальной форме.

Совершенные нормальные формы обладают следующими особенностями:

1) Если при каком-либо наборе значений переменных функция равна единице, то в СДНФ только один из её членов принимает единичное значение.

2) Если функция равна нулю, то в СКНФ только один из её членов принимает нулевое значение.

Конституенты единицы и нуля

Элементарные конъюнкции (дизъюнкции) называются конституентами единицы (нуля), если они содержат все независимые переменные функции.

Например :

Для функции f (х1, х2, х3,
х4) элементарные конъюнкции

;   

 являются конституентами единицы, а элементарные дизъюнкции 

; 

 являются конституентами нуля.

Для функции  n  переменных конституенты единицы имеют вид 

,  а конституенты нуля 

.

Конституента единицы принимает единичное значение тогда и только тогда, когда все буквы принимают единичные значения (это происходит только на одном наборе).

Например :

Конституенте единицы 

  соответствует набор  1010, при котором  она  принимает  единичное  значение; на всех же остальных наборах – 0.

Нормальные формы дизъюнкций и конъюнкций. Часть 2

Пример

.

а) Избавиться от знаков инверсии, применяя законы Де Моргана:

б) Раскрыть скобки, применяя первый закон дистрибутивности

х (у + z) = х у + х z

 .

в)  Привести конъюнкции к элементарным

.

Чтобы привести данную функцию к конъюнктивной нормальной форме, нужно применить несколько раз второй дистрибутивный закон

х + у z = (х + у) (х + z)

Тогда :

Нормальные формы дизъюнкций и конъюнкций. Часть 1

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

Например :

.

Конъюнктивной нормальной (КНФ) называется конъюнкция любого числа элементарных дизъюнкций.

Например :

.

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

избавиться от инверсий над целыми выражениями, перейдя к форме, в которой имеются инверсии только отдельных переменных;

раскрыть скобки, применяя закон дистрибутивности;

привести конъюнкции (дизъюнкции) к элементарным.

Элементарные конъюнкции и дизъюнкции

Элементарной конъюнкцией называется выражение, представляющее собой конъюнкцию любого числа независимых переменных, входящих в данное выражение с инверсией или без нее не более одного раза.

Например :

х у z ;  

;  

;  

;  

;   z 1;  1 – элементарные конъюнкции.

; 

;

 – не являются элементарными конъюнкциями.

Элементарной дизъюнкцией называется выражение, представляющее собой дизъюнкцию любого числа независимых переменных, входящих в данное выражение с инверсией или без нее не более одного раза.

Например :

х + у + z ; 

; 

;  х ;  у + 0 ;  0 – элементарные дизъюнкции.

х у + z ;  х +
у + х – не элементарные дизъюнкции.

Количество переменных в элементарном выражении называется его длиной
и определяет его ранг.

Например :

Конъюнкция 

 является конъюнкцией третьего ранга.

Выражение одних логических функций через другие

Для записи любого логического выражения достаточно иметь только две логические функции  НЕ,
И ; либо НЕ, ИЛИ.

Допустим, что схема  ИЛИ  не существует. Возможно ли любую булеву функцию реализовать только с помощью схем 
И  и  НЕ ?

Это можно проанализировать на основании теоремы Де Моргана.

.

&

х

у

х + у

Представим полученный результат в виде функциональной схемы на бесконтактных логических элементах (рис. 1.8).

Рис. 1.8.  Схема элемента  ИЛИ  на элементах 
И  и  НЕ

Для второго случая

.

Результат представлен на рис. 1.9.

1

х

у

х у

 

Рис. 1.9.  Схема элемента  И  на элементах 
И  и  ИЛИ

Законы алгебры логики

1)         Закон нулевого множества

0 х = 0;

0 х1 х2 … хn
= 0.

Произведение любого числа переменных обращается в нуль, если хотя бы одна переменная имеет значение нуль.

2)         Закон тавтологии

х х = х;

х х … х = х;

х
+ х = х;

х
+ х + х +…+ х = х.

Истина, повторенная несколько раз, остается истиной.

3)         Закон двойной инверсии

.

Отрицание отрицания величины равно самой величине.

4)         Переместительные (коммутативные) законы

х у = у х;

х
+ у = у + х.

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

5)         Сочетательные (ассоциативные) законы

х
(у z) = (xy) z = xyz;

x + (y + z) = (x + y) + z = x
+ y + z.

Для записи умножения или сложения скобки можно опустить.

6)         Распределительные (дистрибутивные) законы

x (y + z) = xy + xz;

x + y z = (x + y) (x + z).

7)         Законы поглощения

x (x + y) = x;%

Логические функции. Часть 4

3) Элемент  И  в простейшем случае имеет два входа и выполняет логическую операцию умножения (конъюнкцию), которую обозначают знаком умножения (точкой) или знаком  " Ù ".

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

Рис. 1.4.  Элемент 
И

В контактных схемах логическое умножение реализуют путем последовательного соединения контактов (рис. 1.4, б).