Таблица истинности для конкретного вида f(a,b,c)

↑

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

Таблица истинности для конкретного вида f(a,b,c)

a

b

c

f

               f(a,b,c) = abc + ^Øabc +^Øa^Øbc + a^Øb^Øc.                                (2.5)

Алгоритм перехода от табличной формы к СКНФ:

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

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

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

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

Также определяется минимальная конъюнктивная нормальная форма МКНФ как эквивалентное исходному логическое выражение, содержащее минимальное количество наипростейших элементарных дизъюнкций.

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

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

Во втором случае удобно пользоваться диаграммами Карно.

Для трех переменных диаграмма имеет следующий вид (табл. 2.2):

Т а б л и ц а 2.2

Диаграмма Карно при объединении двух конъюнкций

b

^Ø b

a

^Øa

^Øc

c

^Øc

Каждая конъюнкция в СДНФ отражается единицей в соответствующей клетке. В приведенном примере это конъюнкции ab. Каждая конъюнкция в СДНФ отражается единицей в соответствующей клетке. В приведенном примере это конъюнкции ab^Øc и a^Øb ^Øc.

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

ab^Øc + a^Øb ^Øc = a^Øc(b +^Øb) = a^Øc.

В основе минимизации лежит известное тождество булевой алгебры: a+^Øa = 1.

Однако с помощью диаграмм Карно можно визуализировать и сделать более простым и наглядным процесс минимизации. Здесь объединяемые единицы отмечены фоном ячейки, при выполнении «на бумаге» следует обвести их линией (табл. 2.3).

Т а б л и ц а 2.3

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



Формы дистанционного обучения

Передача мяча двумя руками снизу

Значение правильной осанки для жизнедеятельности человека

Основные ошибки при выполнении передач мяча на месте