Cтраница 2
Пусть S - схема, реализующая К - в базисе В и состоящая из п V-элементов и инвертора. [16]
Если элемент Е реализует константу 0, то, в силу правильности схемы Sp, Е - V-элемент. [17]
Поэтому выходы всех, кроме последнего, V-элементов схемы Sp подаются только на () - входы V-элементов. [18]
Проделав аналогичные преобразования нужное число раз, получим минимальную правильную схему для К - в базисе В, в которой выходы всех V-элементов, кроме последнего, подаются только на () - входы V-элементов. [19]
Итак, доказано, что произвольная минимальная схема SM для К - в базисе Bit состоит из двух инверторов и п - 1 V-элементов. Очевидно, что последний элемент схемы SM - инвертор, так как иначе бы на один вход V-элемента подавалась бы функция, существенно зависящая от п переменных, для реализации которой достаточно двух инверторов и п - 2 V-элементов. [20]
Таким образом во всех трех случаях после преобразования получается минимальная правильная схема Sp для К - в базисе В, в которой V-эле-мент EQ имеет наименьший номер среди всех V-элементов, выходы которых подаются на входы инверторов. В схеме Sp выход инвертора Е подается на входы t - 1 элементов, в то время как выход инвертора Е схемы Sp подавался на входы t элементов. [21]
Кроме того, тогда каждый вход схемы Sp и выход каждого элемента, кроме последнего, подается на вход только одного элемента, причем в силу правильности схемы Sp на входы V-элементов и на () - входы &-элемен-тов подаются последние q входов схемы и выходы всех, кроме последнего, &-элементов, и только они. [22]
Рассмотрим множество S всех схем, реализующих конъюнкцию К - в базисе БЫ и удовлетворяющих условиям а) и б) определения правильной схемы, в которых, кроме того, выход V-элемента с наибольшим номером подается на вход инвертора, а выходы остальных V-элементов - только на () - входы V-элементов. [23]
Проделав аналогичные преобразования нужное число раз, получим минимальную правильную схему для К - в базисе В, в которой выходы всех V-элементов, кроме последнего, подаются только на () - входы V-элементов. [24]
Кроме того, тогда каждый вход схемы Sp и выход каждого элемента, кроме последнего, подается на вход только одного элемента, причем в силу правильности схемы Sp на входы &-элементов и на () - входы V-элементов подаются первые р входов схемы и выходы всех V-элементов, и только они. [25]
Рассмотрим множество S всех схем, реализующих конъюнкцию К - в базисе БЫ и удовлетворяющих условиям а) и б) определения правильной схемы, в которых, кроме того, выход V-элемента с наибольшим номером подается на вход инвертора, а выходы остальных V-элементов - только на () - входы V-элементов. [26]
Кроме того, тогда каждый вход схемы Sp и выход каждого элемента, кроме последнего, подается на вход только одного элемента, причем в силу правильности схемы Sp на входы &-элементов и на () - входы V-элементов подаются первые р входов схемы и выходы всех V-элементов, и только они. [27]
Рассмотрим множество S всех схем, реализующих конъюнкцию К - в базисе БЫ и удовлетворяющих условиям а) и б) определения правильной схемы, в которых, кроме того, выход V-элемента с наибольшим номером подается на вход инвертора, а выходы остальных V-элементов - только на () - входы V-элементов. [28]
Таким образом, никакой вход схемы не подается на вход инвертора. Следовательно первый элемент является V-элементом. [29]
Обозначим через d число V-элементов в схеме Sp, а через s - число V-элементов схемы Sp, у которых на () - вход подаются входные переменные. Тогда выходы не более, чем d - s V-элементов подаются на () - входы V-элементов. Выходы остальных V-элементов ( а их не менее s) подаются на входы инверторов, так как в силу правильности схемы S, на ( -) - входы V-элементов выходы V-элементов подаваться не могут. [30]