Короткі теоретичні відомості

Мінімізація нормальних форм усюди визначених булевих функцій.

Елементарна кон’юнкція Е називається імпликантоюбулевої функції f, якщо E->f=l.

Імпліканта В називається простою,якщо при видаленні будь-якої букви з неї вона перестає бути імпликантою булевої функції Г.

Скороченою ДНФ називається ДНФ, що складається з усіх простих імплікант даної булевої функції.

Ядрова імпліканта - імпліканта, видалення якої з ДНФ деякої булевої функції f приводить до ДНФ, не рівносильної £

Мінімальна ДНФданої функції f - ДНФ, що має найменше число символів перемінних із усіх ДНФ, що задають функцію f.

Тупикової ДНФфункції f називається така її ДНФ, що складається з простих импликант, що видалення з неї будь-якої кон’юнкції порушує рівносильність ДНФ даної функції.

Складністю ДНФ (КНФ) називається кількість символів перемінних, використаних у записі формули.

Скорочена ДНФ може бути отримана зі ДДНФ послідовним застосуванням, поки це можливо, формули неповного склеювання

Імплікантна таблиця n-арною бф f- прямокутна таблиця двома входами. Строки позначаються простими імплікантами функції f, а столбчики –двоїчними кортежами довжиною n, на яких функція , . Якщо імпліканта накриває двоїчний кортеж , то на перетині i-тої строки и j-того стовбчика таблиці ставиться *. Всі інші клітини таблиці залишаються порожніми.

Поиск по сайту: