Синтез и минимизация логических функций

↑

⇐ ПредыдущаяСтр 4 из 7Следующая ⇒

ЛЕКЦИЯ 2

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

Наиболее удобными формами аналитического представления оказались дизъюнктивная и конъюнктивная нормальные формы записи (ДНФ и КНФ).

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

                       f( a,b,c) = ab + a^Øbc + ac.                               (2.1)

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

Подобным образом определяется и конъюнктивная нормальная форма, например,

                f(a,b,c) = (a + c)(a + ^Øb)(a + b + c).                           (2.2)

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

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

                    f(a,b,c) = aØbc + abØc + aØbØc.                             (2.3)

Также определяется совершенная конъюнктивная нормальная форма (СКНФ), например,

                     f(a,b,c) = (a +b + c)(aØ b+ c)                           (2.4)

Алгоритм перехода от табличного задания к СДНФ следующий:

1. Составить конъюнкцию для столбцов таблицы истинности, в которых функция F равна 1. Если значение переменной A, B, C … в столбце равно 0, то записывается отрицание этой переменной.

2. Записать дизъюнкцию составленных конъюнкций. Пример приведен в табл. 2.1.

Т а б л и ц а 2.1

Познавательные статьи:



Алгоритмические операторы Matlab

Конструирование и порядок расчёта дорожной одежды

Исследования учёных: почему помогают молитвы?

Почему терпят неудачу многие предприниматели?