Аналитические формы представления логических функций

 

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

Существуют две основные аналитические формы записи логических функций: дизъюнктивная и конъюнктивная.

Рассмотрим дизъюнктивные формы представления логических функций.

Выражение вида

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

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

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

Методика приведения логической функции к ДНФ следующая:

- выполнить все операции инверсии, применяемые к логическим выражениям (группе переменных);

- раскрыть все скобки;

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

Пример 3.1 Приведем к ДНФ логическую функцию

Выполним операцию инверсии:

Теперь раскроем скобки и произведем все упрощения:

Итак, ДНФ функции имеет вид:

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

Простейшим методом перехода от ДНФ к СДНФ является метод «домножения» членов ДНФ на недостающие переменные.

Для преобразования ДНФ в СДНФ следует каждую элементарную конъюнкцию, не содержащую все n переменных, домножить на «1», образованную дизъюнкцией недостающей переменной и ее инверсии:

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

Пример 3.2 Приведем к СДНФ функцию

Первую конъюнкцию домножим на а вторую – на так как функция зависит от трех переменных – x₁, x₂, x₃:

Произведя упрощения, получаем искомую СДНФ:

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

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

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

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

Так, полученная в примере 3.2 СДНФ содержит три конституенты единицы, значит функция f(x) задана на трех рабочих наборах. Перейдем от СДНФ к рабочим наборам и символической форме (база – x₁x₂x₃):

Итак, f(x) = 1 в случаях:

1) x₁ = 0, x₂ = 1, x₃ = 1;

2) x₁ = 0, x₂ = 1, x₃ = 0;

3) x₁ = 1, x₂ = 1, x₃ = 0.

На всех остальных наборах f(x) = 0.

Символическая форма записи имеет вид:

СДНФ логической функции, тождественно равной 1, содержит полный набор (2ⁿ) конституент единицы.

Рассмотрим конъюнктивные формы представления логических функций.

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

Если логическая функция, зависящая от n переменных, записана в виде конъюнкции элементарных дизъюнкций, каждая из которых не обязательно включает в себя все n переменных, то такая форма записи называется конъюнктивной нормальной формой (КНФ). Иначе говоря, конъюнктивной нормальной формой логической функции называется конъюнкция любого конечного множества попарно различных элементарных дизъюнкций. Например:

 

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

- заданную функцию проинверсировать и получить ДНФ инверсной функции;

- ДНФ инверсной функции проинверсировать еще раз;

- на каждом этапе следует проводить все упрощения согласно законам алгебры логики (закон повторения, закон поглощения и т.д.).

В результате получим КНФ исходной функции.

Пример 3.3 Приведем к КНФ функцию

Проинверсируем заданную функцию и получим ДНФ инверсной функции:

Проинверсируем еще раз полученную ДНФ:

Итак, получили КНФ исходной функции

Второй метод получения КНФ произвольной функции заключается в следующем:

- выполнить все операции инверсии, применяемые к логическим выражениям (группе переменных);

- применить последовательно необходимое число раз распределительный закон относительно умножения

- провести все упрощения по законам алгебры логики (закон поглощения, закон повторения и т.д.).

Пример 3.4 Приведем данным методом к КНФ функцию

Выполняем операцию инверсии:

Применяем к полученному выражению распределительный закон последовательно несколько раз и проводим упрощения:

Если каждая элементарная дизъюнкция, входящая в КНФ, содержит в прямом или инверсном виде все n переменных, от которых зависит функция, то такая форма называется совершенной конъюнктивной нормальной формой (СКНФ). Преобразование КНФ в СКНФ производится методом «прибавления» недостающих переменных к членам КНФ.

Для преобразования КНФ в СКНФ следует каждой элементарной дизъюнкции, не содержащей все n переменных, добавить 0, образованный конъюнкцией недостающей переменной и ее инверсии:

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

Пример 3.5 Пусть требуется преобразовать в СКНФ логическую функцию, заданную в КНФ:

Так как функция зависит от трех переменных, то добавим в первую дизъюнкцию а во вторую – получим:

Теперь применим для первой и второй скобок распределительный закон и, проведя упрощения по закону повторения, получим:

Итак, искомая СКНФ

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

Элементарные дизъюнкции, входящие в СКНФ функции, называются конституентами нуля (макстермами).

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

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

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

Десятичное (восьмеричное) представление этих чисел есть запрещенные числа для данной функции.

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

Так, полученная в примере СКНФ содержит три конституенты нуля, значит функция f(x) задана на трех запрещенных наборах:

Это значит, что f(x) = 0 в случаях:

1)

2)

3)

На всех остальных наборах f(x) = 1.

 

Символическая форма записи имеет вид:

СКНФ логической функции, тождественно равной нулю, содержит полный набор (2ⁿ) конституент нуля.

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

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

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

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

Конъюнкция полученных таким образом элементарных дизъюнкций представляет собой СКНФ функции.

Таблица 3.1

x3

x2

x1

f(x)

Так, например, для логической функции, заданной таблицей соответствия (Таблица 3.1), СДНФ и СКНФ имеют следующий вид:

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

Запись, при которой каждый член нормальной формы содержит все переменные, от которых зависит логическая функция, называется совершенной (СДНФ или СКНФ).