Минимальные и тупиковые формы булевых функций. Метод импликантных матриц поиска тупиковых схем

Определение 2.1. Функция j(х₁, х₂, …, х_n), входящая в функцию f(х₁, х₂, …, х_n) называется импликантой этой функции.

Определение 2.2. Функция j(х₁, х₂, …, х_n) называется простой им­пли­кантой функции f(х₁, х₂, …, х_n), если сама функция j входит в функ­цию f, но никакая собственная часть функции j в f не входит.

Теорема 2.2.1 (теорема Квайна). Если в совершенной дизъ­юнк­тив­ной нормальной форме переклю­ча­тель­ной функции выполнить все опе­ра­ции неполного склеивания, а затем все операции поглощения, то в результате будет получена сокращенная дизъ­юнк­тивная нормальная фор­ма этой функции, или дизъюнкция всех ее простых импликант.

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

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

2.3. Метод импликантных матриц

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

.

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

Таблица 2.3.1.

Дата добавления: 2015-07-26; просмотров: 182; Нарушение авторских прав

Мы поможем в написании ваших работ!