Булевы уравнения

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

Перейдем от элементов Х,А,В,С к их изображающим числам. Относительно базиса b[А,В,С] найдем #АВС=00000001; #(А+В)=01110111 и, следовательно #Х должно быть таким, чтобы выполнялось равенство

(01110111)(#Х)=00000001,

откуда #Х=*000*001, где вместо (*) можно записать как 0 так и 1. Таким образом, рассматриваемое уравнение имеет 4 решения, соответствующие изображающим числам 00000001; 10000001; 00001001; 10001001, т.е. Х1=АВС, Х2=АВС¬А¬ВС, Х3=С(АВ¬А¬В), Х4=¬А¬ВАВС.

4.4.2.4 – замена переменных. Понятие замены переменных в алгебре логики аналогично понятию замены переменных в обычной алгебре.

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

А=А1В1¬А1¬В1; В=¬А1.

Вычислим по отношению к базису b[А1,В1] изображения числа #A и #B

#А1=0 1 0 1, #¬А1=1 0 1 0,

#В1=0 0 1 1, #¬В1=1 1 0 0.

Значения столбцов 0 1 2 3

Тогда

#A =0001+1000=1001

#B = 1010

Значения столбцов 3021

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

|| F_kj |||| R_ij ||=|| G_kj ||, (4.4)

где || F_kj || - матрица, составленная из набора изображающих чисел переменных А1 и В1, || G_kj || - матрица, составленная из набора изображающих чисел переменных А и В в базисе [А1,В1]. Заполняя (4.4) конкретным содержанием в соответствии с вышеприведенным примером

i= 0123 j=3021

= (4.5)

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

R_ij= (4.6)

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

Исследуем решение, при котором единичными элементами перестановочной матрицы || R_ij || являются R₀₂=1, R₁₅=1, R₂₆=1, R₃₁=1, R₄₃=1, R₅₄=1, R₆₇=1, R₇₀=1. Тогда

|| R_ij || =

и искомое преобразование переменных

#А=

#В=

#С=

откуда

#А[А1,В1,С1] = (11001100),

#В[А1,В1,С1] = 11000011, (4.6)

#С[А1,В1,С1] = 10011001

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

а) А =¬В1; в) В = В1С1¬В1¬С1; с) С = А1В1¬А1¬В1.

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

=

И имеет вид

#А1=

#В1=

#С1=
откуда

#А1[А,В,С] = (01011010),

#В1[А,В,С] = (10101010),

#С1[А,В,С] =(01100110), что соответствует следующим соотношениям:

d) А1 = А¬С¬АС; e) В1=¬А; g) C = А¬В¬АВ.

Последние соотношения допускают следующую интерпретацию:

а) на плоской местности будет применяться легкая артиллерия; b) в ночное время противник будет применять дальнобойную артиллерию и тяжелые танки или же легкую артиллерию без танков; c) при плохой погоде либо будет предпринято наступление пехоты на широком фронте, поддержанное дальнобойной артиллерией, либо будут проводиться локализованные атаки пехоты, сопровождаемые огнем легкой артиллерии; d) наступление на широком фронте будет предпринято или на плоской местности при хорошей погоде или на холмистой местности при плохой погоде; e) тяжелые танки будут применяться на плоской местности в дневное время или на холмистой местности ночью.

Используя полученные результаты ответим на вопрос: какова будет тактика противника, если битва будет происходить на равнине в ясный день?

А¬В¬С=¬В1(В1С1) (¬В1¬С1)(А1В1) (¬А1¬В1)=

=¬В1(¬В1С1¬В1¬С1)(¬В1А1¬А1¬В1)=А1¬ В1С1.

В последнем случае использована теорема де Моргана

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

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

Дата добавления: 2014-01-04