§ 5.6. Замена переменных

Понятие замены переменных в булевой алгебре аналогично понятию замены переменных в обычной алгебре. Если элементарные высказывания и совершается замена переменных, то, полагая

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

Пример. Рассмотрим преобразование элементов в элементы

Вычислим по отношению к

Так как в наборе (5.21) имеются все 22 чисел от 0 до 3, то, следовательно, функции (5 20) независимы и преобразование допустимо.

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

В технических приложениях теории электрических цепей эта задача интерпретируется следующим образом. Пусть имеется некоторый набор проводников На каждый проводник может подаваться либо высокий, либо низкий потенциал. Будем считать, что высокому уровню потенциала соответствуют значения а низкому уровню — значения

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

со входами и выходным проводником

Спрашивается, какой сигнал будет на проводнике если сигналы на исходных проводниках заданы.

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

и совершается преобразование (5.20), то и, следовательно,

Рис. 5.1

В более общем случае требуется одновременно преобразовать несколько функций от переменных к переменным Например, наряду с (5.23) может быть задана функция

которая в результате преобразования (5.20) переходит в функцию

причем

Замена переменных (5.19) в функциях эквивалентна переходу от вычисленных относительно вычисленных относительно Этот переход в случае независимых функций (5.19) сводится к перестановке столбцов в наборе:

В результате получается набор

Перестановка столбцов выполняется при помощи перестановочной булевой матрицы которая должна строиться таким образом, чтобы

где матрица, составленная из набора (5.27); -матрица, составленная из набора (5.28), причем индекс относится к номеру преобразуемой строки (номер функций а индексы - номера разрядов в соответственно.

В частном случае, когда должно быть, согласно , где функции считаются известными. Это условие определяет перестановочную матрицу когда замена переменных (5.19) задана. Например, в случае преобразования (5.20) матрица должна переводить набор представляющий собой просто в набор изображающих чисел вычисленных относительно т. е. в набор (5.21). Таким образом, матрица должна удовлетворять уравнению

Легко видеть, что в (5.30) столбец с номером переводится в столбец с номером столбец с номером переводится в столбец с номером столбец с номером ставится на место столбца с номером и столбец с номером смещается на место столбца с номером Если в матрице элементы с указанными значениями индексов положить равными 1, а остальные — равными 0, т. е. взять

то (5.30) удовлетворится. При этом преобразование функций заданных (5.23) и (5.25), получится из соотношения (5.29):

и, таким образом,

В общем случае перестановочная матрица соответствующая заданному преобразованию переменных (5.19), строится аналогично: если столбец с номером базиса

переводится в столбец с номером набора изображающих чисел вычисленных относительно базиса то матричный элемент а все другие элементы

Перестановочная квадратная булева матрица содержащая только одну единицу в каждом столбце и в каждой строке, допускает обратную матрицу равную транспонированной матрице т. е. и, таким образом,

где единичная матрица.

Например, для матрицы (5.31) обратная матрица

Умножая (5.29) справа на транспонированную матрицу получим

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

Например, используя матрицу (5.33), можно получить обратное к (5.20) преобразование переменных:

или

причем если функции заданы выражениями (5.24) и (5.26), то в переменных согласно (5.34), получим:

Рассмотрим обратную задачу. Предположим, что функции заданы. Требуется найти такое преобразование переменных вида (5.19), которое переводило бы функции в функции при всех

В отличие от предыдущего случая решение данной задачи существует не всегда и, кроме того, может быть неоднозначным. Например, для -Вкогда изображающие числа функций отличаются не только порядком расположения разрядов, но и их содержимым, не существует замены переменных с независимыми функциями которая переводила бы функцию в функцию

Если наборы изображающих чисел (5.27) и (5.28) отличаются только порядком расположения столбцов, то задача решается при помощи (5.29). При этом перестановочная матрица строится так же, как и в прямой задаче. Укажем для каждой колонки набора (5.27), на какое место ее следует перевести с таким расчетом, чтобы в результате получился набор (5.28). Тогда, если колонка переводится в колонку элемент а все другие элементы Например, пусть

Тогда поскольку изображающие числа

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

Соответствующее данной перестановочной матрице преобразование переменных определится при помощи (5.29), если положить Относительно базиса получим

откуда

Обратное преобразование по отношению к данному получается как

т. е.

Найденное преобразование переменных — не единственное преобразование, удовлетворяющее условию

Если положить

то другое возможное преобразование будет

Всего же в данном случае существует различных перестановочных матриц . В отдельных случаях к замене переменных может сводиться задача нахождения решения специальных булевых уравнений. Предположим, что разведчик, проводивший в течение какого-то времени наблюдения за действиями войск противника с целью получить сведения о тактике вооруженных сил, представил своему командованию доклад следующего содержания [14]:

1. На холмистой местности в ясные дни локализованные атаки пехоты проводились в сопровождении дальнобойной артиллерии, а не танков.

2. На плоской местности в ночное время или при плохой погоде применялась легкая артиллерия и никогда не предпринималось общее наступление пехоты на широком фронте, поддерживаемое тяжелыми танками.

3. На холмистой местности ночью или при плохой погоде в дневное время использовались тяжелые танки с локализованными атаками пехоты или же применялась дальнобойная артиллерия с наступлением пехоты на широком фронте.

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

На основе этого донесения требуется определить:

1) как влияют на тактику пехоты: плоская местность; ночное время; плохая погода;

2) при каких условиях будет предпринято наступление на широком фронте, использована дальнобойная артиллерия, использованы тяжелые танки;

3) если предположить, что битва происходит на равнине в ясный день, то какова будет тактика противника.

Для того чтобы решить эту задачу, выделим прежде всего основные понятия, использованные в донесении разведчика:

1) местность — или плоская, или холмистая, но не одновременно плоская и холмистая;

2) время проведения операции — или день, или ночь;

3) погода — хорошая или плохая;

4) атака пехоты — или локализованная, или наступление на широком фронте. Заметим здесь же, что все битвы происходили с атаками пехоты;

5) артиллерия — дальнобойная или легкая;

6) танки — тяжелые или легкие, причем легкие танки вообще не участвовали в сражениях.

В соответствии с перечисленными понятиями введем в рассмотрение следующие элементарные высказывания: А — местность плоская; А — местность холмистая; В — ночь; В — день; С — плохая погода; С —хорошая погода; А— наступление пехоты на широком фронте; А — локализованная атака пехоты; В — дальнобойная артиллерия; В — легкая артиллерия; С — тяжелые танки; С — без танков.

Четыре пункта в донесении разведчика могут быть представлены следующими булевыми соотношениями:

Вычислим по отношению к базисам соответственно изображающие числа булевых функций в левых и правых частях приведенных соотношений эквивалентности:

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

и, согласно (5.29), искомое преобразование переменных есть

Отсюда:

Обратное преобразование переменных осуществляется матрицей

(кликните для просмотра скана)

Отсюда:

И, наконец, разрешая (5.37) относительно переменных, помеченных штрихами, получим

или в явном виде

Соотношения (5.35) и (5.37) допускают следующую интерпретацию:

а) на плоской местности будет применяться легкая артиллерия;

б) в ночное время противник будет применять дальнобойную артиллерию и тяжелые танки или же легкую артиллерию без танков;

в) при плохой погоде либо будет предпринято наступление пехоты на широком фронте, поддержанное дальнобойной артиллерией, либо будут проводиться локализованные атаки пехоты, сопровождаемые огнем легкой артиллерии, либо локализованные атаки пехоты будут поддерживаться тяжелыми танками, либо еще может быть предпринято наступление пехоты на широком фронте с дальнобойной артиллерией без поддержки танков.

Соотношения (5.36) и (5.38) допускают следующую интерпретацию:

г) наступление на широком фронте будет предпринято или на плоской местности при хорошей погоде, или на холмистой местности при плохой погоде (в дневное время), или при хорошей погоде ночью;

д) дальнобойная артиллерия будет применяться на холмистой местности;

е) тяжелые танки будут применяться на плоской местности в дневное время или на холмистой местности ночью.

Для ответа на третий вопрос составим произведение элементов и выразим его через элементы, помеченные штрихами. Для первого варианта решения (5.35) получим

Следовательно, в сражении, которое происходит на равнинной местности днем при хорошей погоде будет применено наступление пехоты на широком фронте, поддержанное легкой артиллерией и тяжелыми танками.

Для второго варианта решения (5.37) найдем

следовательно, результат не отличается от первого варианта.