Дискретная математика

86 Отметим, что полная система функций может содержать всего одну функцию. Например, полна система 0-{(pi}, где (pi=(pi(x,y)=x/ у. Это означает, ^ггo функция fi(x,y)=xl у не принадлежит ни одному из классов функций Pfl, Pj, S, MviL. В общем случае полная система может иметь много функций, но базис, оказывается, имеет не более четырех функций, именно, имеет место следующее утверждение. Следствие 3.9. Из всякой полной системы можно выделить полную подсистему, содержащую не более четырех функций. Доказательство. Пусть G={fi, / 2 , , . , , - полная система функций. Согласно теоремы 3.24 в G найдутсяф у н к ц и и ^ Р р , и J / g ' I . Тогда система Gi-ffi, f j , /„„ f s , f } - полная система. Может быть, что в G; некоторые функции совпадают, но все равно их не более пяти. Имеем fi^Po, следовательно,/;(1D,...,0j=l. Если то f j не монотонная функция и тогда {fi,f j , f^, f}~ полная система. Если то f(10,...,10)=l, а следовательно,у; не самодвойственная функция и тогда {fi,f j , fm ft} полная система. Таким образом, всегда можно выделить полную подсистему, содержащую не более четырех функций. § 19. Приложение теории булевых функций к анализу и синтезу контактных (переключагельиых) схем Рассмотрим приложение теории булевых функций к анализу и синтезу контактных (переключательных) схем. Контакты (переключатели) можно рассматривать как булевы переменные и обозначать буквамих у. z,... или теми же буквами с числовыми индексами: х/, ..., V/, у2 г/, z^,... Каждая из переменных может принимать одно и только одно из двух возможных значений: если контакта: разомкнут, то полагаем х=0, если контакт д: замкн>'т, то jc=l. Под контактной (переключательной) схемой понимается схема, состоящая из замкнутых и разомкнутых контактов, соединенных параллельно или последовательно, или смешанным образом. Отрицанием контакта х называется контакт, равный 1, если х=0, и равный О, еслил:=1. Отрицание контакта д- обозначается через ]х. Очевидно, что последовательное соединение двух контактов х и у моделируется конъюнкцией переменных х иу, а параллельное соединение - их дизъюнкцией, см. рис, 3.2.