Приведение
подобных членов

[предыдущая глава]  [оглавление]  [следующая глава]

В булевой алгебре есть прием, который по сути своей похож на приведение подобных членов в обычной алгебре. Роль сложения играет операция дизъюнкции, роль умножения - операция конъюнкции. Соответственно, формулы, соединенные символом "" будем называть "слагаемыми", а соединенные символом "&" - "множителями". Вместо числовых коэффициентов перед переменными будет стоять или отсутствовать значок отрицания ~. Что-нибудь вроде:

(x & ~y & z & false) (w) (~v) (~x & ~y & ~z) (z) (x & x)

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

Удаление лишних отрицаний

1. Многократные отрицания сводятся к однократным или к переменным без отрицаний по простому принципу: два идущих подряд отрицания можно стереть, благодаря закону ~~X = X. Таким образом, от нечетного числа отрицаний остается одно, а от четного - ни одного.

После упрощения отрицаний применяем законы поглощения. Сначала перечислим применение законов поглощениея для множителей, а потом - для слагаемых.

Законы поглощения для множителей

2.1. Если среди множителей есть true, и этот множитель не последний в слагаемом, то его можно убрать вовсе, благодаря закону поглощения X&true = X.

Например: x y&true = x y.

2.2. Если среди множителей есть false, то все слагаемое превращается в false, благодаря закону поглощения X&false = false.

Например: x t&y&false = x false.

2.3. Если среди множителей есть два (или более) одинаковых в одном слагаемом, то можно просто вычеркнуть все, кроме одного, благодаря закону поглощения X&X = X.

Например: x ~t&~t&y&~t = x ~t&y.

2.4. Если среди множителей есть два (или более) множителей, где одна и та же переменная есть со знаком "~" и без него, то все слагаемое превращается в false, благодаря закону поглощения X&~X = false.

Например: x t&y&~t = x false.

Законы поглощения для слагаемых

3.1. Если среди слагаемый есть true, то вся формула превращается в true, благодаря закону поглощения X true = true.

Например: x&z&t true = true.

3.2. Если среди слагаемых есть false, то это слагаемое просто стирается (конечно, если оно не последнее), благодаря закону поглощения X false = X.

Например: x false y = x y.

Благодаря этому закону поглощения и закону X&false = false, который мы уже рассмотрели выше, можно дать более общее правило: все слагаемые, где встречается false, должны быть стерты, а если false встречается во всех слагаемых, то от формулы останется просто false.

Например: x t&y&false = x.

3.3. Если среди слагаемых есть два (или более) одинаковых, то можно просто вычеркнуть все, кроме одного, благодаря закону поглощения X X = X.

Например: x x y = x y.

3.4. Если среди слагаемых есть два слагаемых вида "x" и "~x", где x - некоторая одиночная переменная, то вся формула превращается в true, благодаря закону поглощения X ~X = true.

Например: z ~z y = true.

Приведение подобных членов

Теперь собственно о приведении подобных членов. Есть несколько видов "подобия", которое позволяет упростить формулы.

4.1. Пусть есть два слагаемых; в первом присутствуют все множители второго и еще несколько дополнительных множителей. В таком случае первое, более длинное слагаемое можно убрать вовсе, благодаря закону X&Y Y = Y.

Например: x&y&~z x&y = x&y

4.2. В частном случае, когда есть слагаемое, в котором присутствует только одна переменная (без отрицания), то все слагаемые, где присутствует эта переменная (без отрицания), можно вычеркнуть. Кроме того, из всех слагаемых, где эта переменная с отрицанием, можно убрать этот множитель. Аналогично, если есть слагаемое состоящее из одной переменной с отрицанием, то вычеркиваем все слагаемые, где она с отрицанием, и все множители, где она без отрицания. Это следует из законов X ~X&Y = X Y и ~X X&Y = ~X Y.

Пример: x x&y ~x&y = x ~x&y = x&y

Пример: ~z z&y ~z&y = ~z y ~z&y = ~z&y

4.3. Если есть два слагаемых, отличающиеся только одним значком "~" перед какой-нибудь переменной, то вычеркивается одно из слагаемых и эта переменная из оставшегося слагаемого. Это упрощение допускается, благодаря закону X&Y ~X&Y = Y

Например: x&y&z x&y&~z = x&y

1. Упростите формулу a&d b a&a&b&b&~c&d ~d
   Посмотреть ответ

   a&d b a&a&b&b&~c&d ~d = ...

   - применяем 2.3., убирая лишнее "a":

   ... = a&d b a&b&~c&d ~d = ...

   - применяем 4.2. к слагаемому "~d", убираем "d" из всех слагаемых:

   ... = a b a&b&~c ~d = ...

   - применяем 4.1. к слагаемому "a", убираем все слагаемые, содержащие "a": ... = a b ~d

2. Упростите формулу a b a&~a ~q
   Посмотреть ответ

   a b a&~a ~q = ...

   применяем 2.4.:

   ... = a b false ~q = ...

   применяем 3.2.:

   ... = a b ~q

   Тот же результат можно было получить за 1 шаг, применив правило 4.1. к слагаемому "a".

3. Упростите формулу ~a b a ~q&c
   Посмотреть ответ

   Результат - просто true, благодаря правилу 3.4.