Замена переменных

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

(6.13)

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

Пример. Преобразовать элементы А и В в элементы А¢ и В¢:

(6.13а)

Вычислим по отношению к базису b [А¢, В¢]

(6.14)

Так как в наборе (6.14) имеются все 2² чисел от 0 до 3, то, следовательно, функции (6.13а) независимы и преобразование допустимо.

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

(6.15)

Для нахождения #G₁{А¢, В¢, С¢, ...) вычислим #А, #В, # С, ... по отношению к b[А¢, В¢, С¢, ...] и произведем над ними действия, посредством которых формируется функция F₁(A, В, С, ...) из элементов А, В, С, ... . Полученный результат и будет #G₁ (А¢, В¢, С¢, ...) по отношению к b[А¢, В¢, С,¢ ...]. Например, если

(6.16)

и совершается преобразование (6.13а), то #G(A¢, В¢) = (1001) ´ (0101) + (0110)×(1010)×0011 и, следовательно,

(6.17)

В более общем случае требуется одновременно преобразовать несколько функций F₁(А, В, С, ...), F₂(A, В, С, ...) от переменных А, В, С, ... к переменным А¢, В¢, С¢, ... . Например, наряду с (6.16) может быть задана функция

(6.18)

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

(6.19)

причем #G₂(A¢,B¢))= 1001 + 0101 = 1101.

Замена переменных (6.13) в функциях F₁(А, В, С, ...), F₂(A, B С,...) эквивалентна переходу от #F₁{А, В, С, ...), #F₂(A, В, С, ...), вычисленных относительно b[А, В, С, ...], к #G₁(А¢, В¢, С¢, ...), #G₂(A¢, В¢, С¢, ...), ..., вычисленных относительно b[А¢, В¢, С¢, ...]. Этот переход в случае независимых функций (6.13) сводится к перестановке столбцов в наборе

(6.20)

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

(6.21)

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

(6.22)

где ||F_ki||—матрица, составленная из набора (6.20); ||G_kj||— матрица, составленная из набора (6.21), причем индекс k относится к номеру преобразуемой строки (номер функций F_k, G_k), а индексы i и j — номера разрядов в # F_k и # G_k, соответственно.

В частном случае, когда F₁ = A,F₂=B,F₃ = C, ..., должны быть, согласно (6.13), G_l = A(A¢, В¢, С¢, ...), G₂=B{A¢, В¢, С¢, ...), G₃ = C(A¢, В¢, С¢, ...), ..., где функции А (A¢, В¢, С¢, ....), В(A¢, В¢, С¢, ...), С(A¢, В¢, С¢, ...), ..., считаются известными. Это условие определяет перестановочную матрицу ||R_ij||, когда замена переменных (6.13) задана. Например, в случае преобразования (6.13а) матрица ||R_ij|| должна переводить набор #A = 0101; #B=0011, представляющий собой просто базис b [А, В], в набор изображающих чисел #A(A¢, В¢) и #B(А¢, В¢), вычисленных относительно базиса b [А¢, В¢], т. е. в набор (6.14). Таким образом, матрица ||R_ij|| должна удовлетворять уравнению

(6.23)

В (6.23) столбец с номером i=0 переводится в столбец с номером j= 1, столбец с номером i= 1 переводится в столбец с номером j=3, столбец с номером i=2 ставится на место столбца с номером j=2 и столбец с номером i=3 смещается на место столбца с номером j = 0. Если в матрице ||R_ij|| элементы с указанными значениями индексов i и j положить равными 1, а остальные — равными 0, т. е. взять

(6.24)

то (6.23) удовлетворится. При этом преобразование функций F₁ и F₂, заданных (6.16) и (6.18), получится из соотношения (6.22):

таким образом, G₁ =В¢, G₂=A¢ +В¢.

В общем случае перестановочная матрица ||R_ij||, соответствующая заданному преобразованию переменных (6.13), строится аналогично: если столбец с номером i=k базиса b[А, В, С, ...] переводится в столбец с номером j=h набора изображающих чисел #А(А¢, В¢, С¢, ...), #В(А¢, В¢, С¢,...), #С(А¢, В¢, С¢,...), ..., вычисленных относительно базиса b[А¢, В¢, С¢,...], то матричный элемент R_kh= 1, а все другие элементы R_ij=0.

Перестановочная квадратная булева матрица ||R_ij||, содержащая только одну единицу в каждом столбце и в каждой строке, допускает обратную матрицу ||R_ij||^-1, равную транспонированной матрице ||R_ij|^T, т. е. ||R_ij||^-1 = ||R_ij||^T=||R_ij||, и, таким образом, ||R_ij||´ ||R_ij||= ||d_ij|| где ||d_ij|| — единичная матрица. Например, для матрицы (6.24) обратная матрица

(6.25)

Умножая (6.22) справа на матрицу ||R_ij||, получим

(6.26)

В частном случае, когда G_ij= #A¢; G₂_j= #B; С₃_j= #С¢, ..., т. е. когда матрица ||G_kj||совпадает с базисом b[А¢, В¢, С¢, ...], (6.26) определяет преобразование переменных, обратное по отношению к (6.13): F₁_i=#A¢(A, В, С, ...); F₂_j=#B¢(A, В, С, ...); F₃_j=#C(A, В, С,...); где изображающие числа функций А¢ (А, В, С,...), В¢(А, В, С, ...); С¢(А, В, С, ...), ... записаны в базисе b [А, В, С, ...].

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

или

причем если функции G₁{А¢, В¢) и G₂ (А¢, В¢) заданы выражениями (6.17) и (6.19), то в переменных А, В, согласно (6.26), получим

Рассмотрим обратную задачу: найти такое преобразование переменных вида (6.13), которое переводило бы функции F_k в функции G_k, т. е. при всех k= 1, 2, ... F_k[A(A¢, В¢, С¢, ...); В(А¢, В¢, С¢, ...); С(А¢, В¢, С¢, ...); ...] = G_k(A¢, В¢, С¢, ...). В отличие от предыдущего случая решение данной задачи существует не всегда и, кроме того, может быть неоднозначным. Например, для когда изображающие числа отличаются не только порядком расположения разрядов, но и их содержимым, не существует замены переменных А = А{А¢, В¢); В=В {А¢, В¢) с независимыми функциями А(А¢, В¢), В(А¢, В¢), которая переводила бы функцию F в функцию G.

Если наборы изображающих чисел (6.20) и (6.21) отличаются только порядком расположения столбцов, то задача решается с помощью (6.22). При этом перестановочная матрица ||R_ij|| строится так же, как и в прямой задаче. Укажем для каждой колонки набора (6.20), на какое место ее следует перевести с таким расчетом, чтобы в результате получился набор (6.21). Тогда, если колонка i=k переводится в колонку j=h, элемент R_kh=l, а все другие элементы R_ij=0. Например, пусть F(A, В, С) = Тогда так как изображающие числа #F(A, В, С) = 0111 1110 и #G(A¢, В¢, С¢)=0101 1111 отличаются только порядком расположения нулей и единиц, то существует преобразование переменных вида (6.13), переводящее функцию Fb функцию G. Положим в матрице ||R_ij|| элементы R₀₀, R₁₆, R₂₇, R₃₂, R₄₁, R₅₄, R_б5 и R₇₃ равными 1, а все остальные элементы R_ij=0. Это означает, что разряд i=0, переводится в разряд j=0, разряд i=1 — в разряд j= 6; i=2 —в разряд j= 7 и т. д. Таким образом, выбираем

Соответствующее данной перестановочной матрице ||R_ij|| преобразование переменных определится с помощью (6.22), если положить (F₁_i)=#A; (F₂_l)=#B; (F₃_i)=#C. Относительно базиса b[A¢, B¢, С¢]

откуда

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

т. е.

Найденное преобразование переменных — не единственное удовлетворяющее условию F(A, В, C) = G(A¢, B¢, С¢).

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

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

Всего же в данном случае существует 2×6! = 1440 различных перестановочных матриц ||R_ij||. В отдельных случаях к замене переменных может сводиться задача нахождения решения специальных булевых уравнений. Предположим, что разведчик, проводивший в течение какого-либо времени наблюдения за действиями войск противника с целью получить сведения о тактике вооруженных сил, представил своему командованию доклад следующего содержания [23]:

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

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

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

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

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

Чтобы решить эту задачу, выделим прежде всего основные понятия, использованные в донесении разведчика: 1) местность — или плоская, или холмистая, но не одновременно плоская и холмистая; 2) время проведения операции — или день, или ночь; 3) погода — хорошая или плохая; 4) атака пехоты — или локализованная, или наступление на широком фронте. Заметим, здесь же, что все битвы происходили с атаками пехоты; 5) артиллерия — дальнобойная или легкая; 6) танки — тяжелые или легкие, причем легкие танки вообще не участвовали в сражениях.

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

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

Вычислим по отношению к базисам b[А, В, С] и b [А¢, В¢, С¢] соответственно изображающие числа функций в левых и правых частях приведенных соотношений эквивалентности.

Номера разрядов i= 01234567

Номера столбцов 9 0 12 2 4 14 12 10

Номера разрядов i=01 2 3 4567

Номера столбцов 10 2 9 4 14 0 12 12

Один набор изображающих чисел может быть получен из другого набора перестановкой столбцов двумя способами. Это означает, что существуют два различных решения выписанных уравнений как относительно А, В, С, так и относительно А¢, В¢, С¢, которые можно определить, если найти соответствующую замену переменных, переводящую левый набор функций в правый набор и наоборот. Исследуем вначале решение, при котором единичными элементами перестановочной матрицы ||R_ij|| являются R₀₂ = l, R₁₅=1, R₂₆=l, R₃₁ = 1, R₄₃=1, R₅₄=1, R₆₇ = 1, R₇₀=l.

Тогда

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

Отсюда

(6.27)

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

(6.27а)

и имеет вид

или в явной форме:

(6.28)

В другом возможном случае единичными элементами перестановочной матрицы ||R_ij|| будут R₀₂ = l, R₁₅=1, R₂₇=l, R₃₁ = 1, R₄₃=1, R₅₄=1, R₆₆ = 1, R₇₀=l, так что

(6.28а)

Соответствующее данной перестановочной матрице преобразование переменных имеет вид

Отсюда

(6.29)

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

или в явной форме:

(6.30)

Соотношения (6.27) и (6.29) допускают следующую интерпретацию: а) на плоской местности будет применяться легкая артиллерия; б) в ночное время противник будет применять дальнобойную артиллерию и тяжелые танки или же легкую артиллерию без танков); в) при плохой погоде либо будет предпринято наступление пехоты на широком фронте, поддержанное дальнобойной артиллерией, либо будут проводиться локализованные атаки пехоты, сопровождаемые огнем легкой артиллерии, либо локализованные атаки пехоты будут поддерживаться тяжелыми танками, либо еще может быть предпринято наступление пехоты на широком фронте с дальнобойной артиллерией без поддержки танков.

Соотношения (6.28) и (6.30) допускают следующую интерпретацию: 1) наступление на широком фронте будет предпринято или на плоской местности при хорошей погоде, или на холмистой местности при плохой погоде (в дневное время), или при хорошей погоде ночью; д) дальнобойная артиллерия будет применяться на холмистой местности; е) тяжелые танки будут применяться на плоской местности в дневное время или на холмистой местности ночью.

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

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

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

Таким образом, результат не отличается от первого варианта.