29
правок
Изменения
Нет описания правки
* '''Отрицание'''
Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.
==Задача о минимизации контактной схемы==
{{Определение
|definition =
Две контактные схемы называются '''эквивалентными''', если они реализуют одну и ту же булеву функцию или одну и ту же систему функций.
}}
{{Определение
|definition =
'''Сложностью''' контактной схемы называется число
ее контактов.
}}
Задача минимизации контактных схем состоит в том, чтобы по данной схеме <tex>S</tex> найти схему <tex>T</tex> , эквивалентную <tex>S</tex> и имеющую наименьшую сложность.
Один из путей решения этой задачи состоит в следующем:
* Осуществляем переход от контактной схемы <tex>S</tex> к её булевой функции <tex>F(S)</tex>.
* Упрощаем <tex>F(S)</tex>, то есть отыскиваем функцию <tex>G</tex> (на том же базисе, что и <tex>F(S)</tex>), равносильную <tex>F(S)</tex> и содержащую меньше вхождений атомарных формул.
* Строим схему <tex>T</tex>, реализующую функцию <tex>G</tex>.
==Ссылки==
