Если каждый член дизъюнктивной (конъюнктивной) нормальной функции содержит все аргументы, то такая форма представления функции называется совершенной дизъюнктивной (конъюнктивной) нормальной формой.
Если в функции дизъюнктивной (конъюнктивной) формы инверсия применяется лишь непосредственно к аргументам, то такая форма представления функции называется дизъюнктивной (конъюнктивной) нормальной формой.
Примеры записи ФАЛ от трёх аргументов в нормальных формах:
дизъюнктивной - уДНФ = х0х1х2 Ú х0х1 Ú х1х2,
конъюнктивной - уКНФ = (х0 Ú х1 Ú х2)(х0 Ú х1).
Примеры записи ФАЛ от трёх аргументов в совершенных формах:
дизъюнктивной - уСДНФ = х0х1х2 Ú х0х1х2,
конъюнктивной - уСКНФ = (х0 Ú х1 Ú х2)(х0 Ú х1 Ú х2).
Произвольная функция от n аргументов может быть выражена как в виде СДНФ, так и в виде СКНФ.
Функция в любой из совершенных форм может быть получена на основе таблицы истинности или, при достаточном опыте, её скобочной записи. При этом используется следующее правило.
|
|
В СДНФ (СКНФ) записывается столько членов, сколько единиц (нулей) содержит функция в таблице. Каждый член функции соответствует набору аргументов, обращающих её в 1 (0), и если в этом наборе значение аргумента равно нулю (единице), то в член функции входит его инверсия.
Таким образом, каждый член функции в СДНФ представляет функцию конституенты единицы, а в СКНФ - конституенты нуля.
№ набора | ||||
х1 | ||||
х0 | ||||
у |
Поясним правило записи функции в совершенной форме на примере следующей таблицы истинности:
Поскольку функция имеет две единицы, то в СДНФ она будет содержать два члена, один из которых соответствует нулевому набору, а другой - третьему.
На нулевом наборе оба аргумента имеют нулевое значение, следовательно, соответствующий член функции будет иметь вид: х1х0. Второй член функции запишется в виде х1х0, поскольку на третьем наборе оба аргумента имеют значение единицы. Таким образом, функция в СДНФ будет иметь вид: уСДНФ = х1х0 Ú х1х0.
В СКНФ функция также будет содержать два члена, соответствующих первому и второму наборам. На первом наборе х0 имеет значение 1, следовательно, в соответствующий член функции войдёт его инверсия: х1 Ú х0. На втором наборе значение 1 имеет х1, следовательно второй член функции запишется как х1 Ú х0. Таким образом, функция в СКНФ будет иметь вид: уСКНФ = (х1 Ú х0)(х1 Ú х0).
Далее приводятся основные законы и тождества алгебры логики, поскольку они лежат в основе второго и третьего этапов синтеза КЦУ.
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. Сочетательный закон х0 Ù (х1 Ù х2) = (х0 Ù х1) Ù х2,
х0 Ú (х1 Ú х2) = (х0 Ú х1) Ú х2,
х0 Å (х1 Å х2) = (х0 Å х1) Å х2.