Функции алгебры логики. Логический базис (стр. 2 из 3)

-повторители 1-го и 2-го аргументов;

– инверсии 1-го и 2-го аргументов;

– функция И (конъюнкция), логическое умножение;

– функция И-НЕ (базис Шеффера);

– функция ИЛИ (дизъюнкция), логическое сложение;

– функция ИЛИ-НЕ (базис Пирса);

– функция неравнозначности, реализуется ЛЭ “Исключающее ИЛИ” (сумматор по модулю два);

– функция равнозначности реализуется ЛЭ “Исключающее ИЛИ-НЕ”.

Рассмотренные элементарные функции двух аргументов

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

Функции n переменных, значения которых заданы во всех точках области определения, считаются полностью определенными ФАЛ. Если какая-либо функция имеет запрещенные наборы переменных и ее значения на указанных наборах не определены, то такая ФАЛ называется не полностью определенной. Такие наборы будем отмечать в таблицах истинности (*) и при необходимости доопределять их значениями 0 и 1. Эти вопросы будут рассматриваться позже.

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

ДНФ – дизъюнктивная нормальная форма записи ФАЛ представляется в виде суммы (дизъюнкции) ряда элементарных членов (минтермов), каждый из которых является произведением (конъюнкцией) аргументов или их инверсий. Термин “нормальная форма” предполагает, что в логическом выражении, задающем функцию, последовательно выполняются не более двух базовых операций (кроме инверсии).

Запишем ФАЛ в ДНФ:

; (1)

Функцию (3.19) можно записать в виде дизъюнкции минтермов:

,

где

- конъюнкции аргументов ФАЛ, называемые минтермами.

СДНФ – совершенная дизъюнктивная нормальная форма записи ФАЛ представляется в ДНФ, где в каждом элементарном члене (минтерме), имеющем одинаковую размерность, представлены все аргументы функции или их инверсии.

Запишем ФАЛ в СДНФ:

. (2)

Если записать ФАЛ в виде:

, (3)

то форма представления данной функции не является СДНФ, так как второй минтерм не содержит аргумента

, а также не является ДНФ, так как третий минтерм не является элементарным.

Функцию

можно упростить (минимизировать) и представить минимальной ДНФ (МДНФ).

(4)

Полученные элементарные члены МДНФ называются импликантами.

КНФ – конъюнктивная нормальная форма записи ФАЛ, представляется в виде произведения (конъюнкции) ряда элементарных членов (макстермов), которые являются суммой (дизъюнкцией) аргументов ФАЛ.

Запишем функцию

в КНФ:

. (5)

СКНФ – совершенная конъюнктивная нормальная форма записи ФАЛ представляется в КНФ, где в каждом элементарном члене (макстерме) представлены все аргументы функции либо их инверсии.

Запишем функцию

в СКНФ:

. (6)

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

На основании общей табл. 1 составим таблицу истинности функции неравнозначности

и запишем ее в СДНФ и СКНФ.

На наборах N(2,3), где функция принимает значения 1, записываем ФАЛ в СДНФ, а на наборах N(1,4) – в СКНФ. При записи ФАЛ в СДНФ аргументы x=0 записываются с инверсией

, а в СКНФ – без инверсии.

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