Способы задания логических функций

В общем случае логическая функция Y может зависеть от нескольких переменных Х₁, Х₂ …Х_n. Говорят, что функция Y определена, если известны ее значения для всех возможных наборов двоичных переменных. Функция Y не определена, когда некоторые сочетания переменных по условию задачи невозможны. В этом случае функцию можно доопределить, приписав ей значение «1» либо «0», по соображениям удобства реализации [10].

Логическая функция может быть задана:

1) словесно;

2) таблицей истинности;

3) алгебраически;

4) графически.

Пример словесного описания: функция f(x₁,x₂) принимает значение 1, когда значения переменных равны: x₁ = x_2. При неравенстве переменных x₁¹x₂ функция принимает значение 0.

Наиболее часто связь между логической функцией и логическими переменными задается в виде таблицы истинности, состоящей из n+1 столбцов и 2ⁿ строк или в алгебраической форме.

Значения наборов переменных в таблице истинности располагают в лексикографическом порядке(в порядке возрастания),как в примере для n=3 в таблице 2.1.

Таблица 2.1.

Таблица истинности позволяет просто и наглядно отразить функциональную зависимость, но не дает возможности определить структуру логического устройства, которое способно реализовать такие преобразования. Определить структуру логического устройства можно, исходя из алгебраической формы записи [4-8].

Булева функция g(x) называется импликантой булевой функции f(x), если для любого набора аргументов, на которых g(x)=1, f(x) также равна единице.

, (2.1.)

где некоторый набор аргументов.

Свойства импликант:

1. Между импликантой и самой функцией существует отношение включения g(x) Ì f(x).

2. Можно утверждать, что для любого набора аргументов, на котором функция равна нулю, ее импликанта также равна нулю.

3. Если g(x) и j(x) являются импликантами функции f(x), то их дизъюнкция также является импликантой этой функции.

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

Простейшими примерами импликант могут служить конъюнктивные термы, входящие в ДНФ данной функции [2-10].

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

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

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

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

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

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

Пример 2.1. Функция

представлена не в ДНФ, так как последний член не является простой конъюнкцией аргументов.

Пример 2.2. Функция является примером ДНФ.

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

а) записать булеву функцию в виде

в) с помощью законов Де Моргана спустить черту отрицания до отдельных букв и по закону двойного отрицания уничтожить двойные черточки;

г) с помощью первого закона дистрибутивности уничтожить все произведения сумм и произвести поглощение [11].