Лекционный курс по основам информатики, страница 9

– логическое сложение, описывает работу логического элемента ИЛИ.

Vi	x1,x0
0	0 0	0
1	0 1	1
2	1 0	1
3	1 1	1

Функция сложения по модулю два (исключающее ИЛИ, неравнозначность)

– сложение по модулю два, применяется для арифметического сложения

Vi	x1,x0
0	0 0	0
1	0 1	1
2	1 0	1
3	1 1	0

Функция Пирса, логическое сложение с отрицанием, отрицание дизъюнкции (стрелка Пирса, ИЛИ-НЕ)

– логическое сложение с отрицанием ИЛИ-НЕ

Vi	x1,x0
0	0 0	1
1	0 1	0
2	1 0	0
3	1 1	0

Функция Шеффера, отрицание логического умножения (штрих Шеффера И-НЕ)

– логическое умножение с отрицанием И-НЕ

Vi	x1,x0
0	0 0	1
1	0 1	1
2	1 0	1
3	1 1	0

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

4.9. Теоремы разложения

В теории логических функций особо важное значение имеет теорема разложения Шеннона: любую функцию F(v) можно разложить по переменной x_p в форме:

По принципу двойственности получается двойственная теорема разложения:

С теоремой разложения связаны тождества

4.10. Представление логической функции в виде СДНФ и СКНФ

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

- где f функция 3х переменных.

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

- где f функция 3х переменных.

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

- где f функция 3х переменных.

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

- где f функция 3х переменных.

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

- где f функция трех переменных.

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

- где f функция 3х переменных.

4.10.1. Первичные термы

Терм - это переменные, инверсии переменных, их конъюнкция и дизъюнкция.

Первичные термы: - переменные и их инверсии.

Для первичных термов будем использовать обозначение - где e_p = 0 или 1. В общем случае - подставляем сюда значения e_p = 0 или 1 получим:

при e_p = 0 то

при e_p = 1 то

Такое обозначение облегчает формализацию общих соотношений для логических функций:

4.10.2. Минтермы и макстермы

Минтерм: - конъюнкция всех переменных, которые входят в прямом виде, если значение данной переменной в точке определения равно 1, либо в инверсном виде, если значение переменной равно 0.

Обозначение термов позволяет в общем виде записать конъюнкцию любого числа аргументов.

Минимальным термом – минтермом: - называется функция n переменных:

Vi	x1,x0
0	0 0
1	0 1
2	1 0
3	1 1

где v=(x_n-1,…,x₀), e_p = 0 или 1

Из данного определения следует, что имеется 2ⁿ – различных минтермов n переменных т.к. минтерм представляет n разрядное двоичное число от 0 до 2ⁿ –1.

Запишем все минтермы двух переменных

Макстерм - это дизъюнкция всех переменных, которые входят в прямом виде, если значение данной переменной в точке области определения равно 0, либо в инверсном виде, если значение переменной равно 1.

Vi	x1,x0
0	0 0
1	0 1
2	1 0
3	1 1

Максимальным термом – макстермом: - называется функция n переменных

где v=(x_n-1,…,x₀),
e_p = 0 или 1

Запишем все макстермы двух переменных

4.10.3. Запись функции в виде СДНФ и СКНФ

Возьмем функцию двух переменных x₁x₀. Применим к ней терему разложения для переменной x₁.

Далее каждую из функций и разложим по переменной x₀.

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

В общем виде представление функции в СДНФ:

Так как значение функции то если и если отсюда СДНФ можно представить в виде:

где i₁ – номера точек, в которых функция .

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

Возьмем инверсию СДНФ: из данного соотношения на основании закона двойственности получим: а так как общий вид СКНФ:

Так как значение функции то если и если отсюда СКНФ можно представить в виде:

где i₀ – номера точек, в которых функция .

4.10.4. Совершенные нормальные формы в базисах И-НЕ и ИЛИ-НЕ

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

Преобразуем СДНФ функции с помощью законов двойного отрицания и де Моргана:

Данная форма представления функции называется совершенной нормальной формой (СНФ) в базисе И-НЕ, так как она требует использования только функций (операций) И-НЕ.

Проведем аналогичные действия с СКНФ:

Данная форма представления функций называется СНФ в базисе ИЛИ-НЕ, так как она требует использования только функций (операций) ИЛИ-НЕ.

4.11. Минимизация логических функций

Одной из основных задач, возникающих при синтезе комбинационных схем (КС), является минимизация логических функций, которые эти КС реализуют. Чем проще логическое выражение, описывающее функцию, тем проще и дешевле реализующая ее КС.

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

Существуют два метода минимизации: