Тождества также отражают правила эквивалентной замены одного логического элемента другим

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

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

Примеры записи ФАЛ от трёх аргументов в нормальных формах:

дизъюнктивной - у_ДНФ = х₀х₁х₂ Ú х₀х₁ Ú х₁х₂,

конъюнктивной - у_КНФ = (х₀ Ú х₁ Ú х₂)(х₀ Ú х₁).

Примеры записи ФАЛ от трёх аргументов в совершенных формах:

дизъюнктивной - у_СДНФ = х₀х₁х₂ Ú х₀х₁х₂,

конъюнктивной - у_СКНФ = (х₀ Ú х₁ Ú х₂)(х₀ Ú х₁ Ú х₂).

Произвольная функция от n аргументов может быть выражена как в виде СДНФ, так и в виде СКНФ.

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

В СДНФ (СКНФ) записывается столько членов, сколько единиц (нулей) содержит функция в таблице. Каждый член функции соответствует набору аргументов, обращающих её в 1 (0), и если в этом наборе значение аргумента равно нулю (единице), то в член функции входит его инверсия.

Таким образом, каждый член функции в СДНФ представляет функцию конституенты единицы, а в СКНФ - конституенты нуля.

№ набора
х1
х0
у

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

Поскольку функция имеет две единицы, то в СДНФ она будет содержать два члена, один из которых соответствует нулевому набору, а другой - третьему.

На нулевом наборе оба аргумента имеют нулевое значение, следовательно, соответствующий член функции будет иметь вид: х₁х₀. Второй член функции запишется в виде х₁х₀, поскольку на третьем наборе оба аргумента имеют значение единицы. Таким образом, функция в СДНФ будет иметь вид: у_СДНФ = х₁х₀ Ú х₁х₀.

В СКНФ функция также будет содержать два члена, соответствующих первому и второму наборам. На первом наборе х₀ имеет значение 1, следовательно, в соответствующий член функции войдёт его инверсия: х₁ Ú х₀. На втором наборе значение 1 имеет х₁, следовательно второй член функции запишется как х₁ Ú х₀. Таким образом, функция в СКНФ будет иметь вид: у_СКНФ = (х₁ Ú х₀)(х₁ Ú х₀).

Далее приводятся основные законы и тождества алгебры логики, поскольку они лежат в основе второго и третьего этапов синтеза КЦУ.

2.5. Основные законы и тождества алгебры логики.

Законы и тождества алгебры логики используются для преобразования ФАЛ. Относительно дизъюнкции, конъюнкции, инверсии и исключающее ИЛИ справедливы следующие тождества:

1) х Ú х = х, 4) х Ú х = 1, 7) х Ú 1 = 1, 10) х Ú 0 = х,

2) х Ù х = х, 5) х Ù х = 0, 8) х Ù 1 = х, 11) х Ù 0 = 0,

3) х Å х = 0, 6)х Å х = 1, 9) х Å 1 = х, 12) х Å 0 = х.

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

Относительно тех же логических операций справедливы следующие законы:

1. Закон двойной инверсии х = х. Здесь х может быть как простой пе- ременной, так и логическим выражением.

2. Сочетательный закон х₀ Ù (х₁ Ù х₂) = (х₀ Ù х₁) Ù х₂,

х₀ Ú (х₁ Ú х₂) = (х₀ Ú х₁) Ú х₂,

х₀ Å (х₁ Å х₂) = (х₀ Å х₁) Å х₂.

Дата добавления: 2014-01-07