А. Кофман и Р. Фор. Займемся исследованием операций (стр. 24 )

.

Таким образом, «или» исключительное обозначается через (есть перо и нет карандаша или нет пера и есть карандаш).

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

a∙a = a (1)

и

a + a = a. (2)

Рассмотрим некоторые обозначения и свойства:

если а справедливо, полагают а = 1;

если а ложно, записывают а = 0.

Следовательно, здесь используют переменную, которая может принимать только два значения, 0 или 1. Пусть а и b — две переменные такого типа (бинарные переменные):

если а = 0, b = 0, то a∙b = 0, а+b = 0;

если а = 0, b = 1, то a∙b = 0, а+b = 1;

если а = 1, b = 0 , то a∙b = 0, а+b = 1;

если а = 1, b = 1, то a∙b = 1, а+b = 1.

Отсюда получаются таблицы логических произведений и сумм:

0∙0 = 0, 0∙1=0, 1∙0=0, 1∙1=1,

0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1=1.

Точка здесь обозначает не знак умножения, а представляет собой «и», а знак плюс с точкой обозначает не сложение, а союз «и/или». Можно было бы также применить символы ∩ и È, употребляемые в теории множеств, но в бинарной алгебре это не представляет интереса.

Вернемся к вашей задаче и найдем, какой тип приемника нужно производить, чтобы получить наибольшую прибыль. Вы отметили четыре условия, которые мы обозначим С1, С2, С3, С4.

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

,

где T1 означает, что серия T1 применяется, a , что она не применяется; аналогично для остальных Ti.

Прежде чем перейти к другим условиям, заметим, что бесполезно сохранять семь переменных T1, Т2, Т3, Е, P, А и F. Достаточно лишь пяти из них, так как E и P взаимно исключаются, аналогично A и F. Таким образом, мы имеем

или , с одной стороны,

или , с другой стороны.

Перейдем к условию С2.

С2. Если используют корпус P, то из этого следует, что нельзя использовать серию Т2 и трансформатор F.

Как записать отношение следования? Это нетрудно; если из а следует b, то должно быть

.

Это означает, что «иметь a и не иметь b» ложно. Но это соотношение эквивалентно следующему:

,

которое является дополнительным предложением[57].

Условие С2 тогда запишется как

,

или же

.

С3. Использование серии T1 влечет за собой применение трансформатора F. Это еще одно отношение следования

,

или же

.

C4. Из применения Т2 или Т3 следует использование питания A

,

или же

.

Но ; при этом условии предыдущее равенство можно
переписать в виде

.

Для того чтобы были выполнены все условия С1, С2, C3 и С4 , необходимо, чтобы

С1 ∙ С2 ∙ С3 ∙ С4 = 1,

т. е.

. (3)

Это выражение легко упростить, если учесть свойства (1) и (2), а также следующие:

которые вам покажутся очевидными.

Умножения (в смысле алгебры Буля), содержащиеся в выражении (3), могут выполняться в любом порядке.

Выполним последнее:

;

затем, логически умножая результат на выражение из С2, получим

Остается умножить логически последний результат на выражение из С1:

Для того чтобы окончательный результат равнялся единице, необходимо, чтобы хотя бы одно из слагаемых равнялось 1, так:

означает одно возможное решение, совместное со всеми условиями, — это монтаж T1FE;

означает возможное решение — это T2АE;

означает возможный монтаж — это Т3А.

В этом случае безразлично, применять E или P; нужно рассмотреть Т3АЕ и Т3АР.

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

Т1FЕ: 110 — (28 + 25 + 9+ 27) = 21 франк,

Т2АЕ: 110 — (30 + 23 + 9 + 28) = 20 франков,

Т3АЕ: 110 — (31 + 23 + 9 + 25) = 22 франка,

Т3АР: 105 — (31 + 23 + 6 + 25) = 20 франков.

Наибольшую прибыль, 22 франка, даст вам модель в корпусе из дерева с сериями Т3 и питанием А.

(Наконец, партнеры могут вставить слово.)

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

Луи. В этом частном случае ты прав. Взгляните на рис. 11.1. Всего здесь можно указать двенадцать комбинаций, из которых возможны только четыре. Но я хотел воспользоваться этой маленькой задачей, чтобы вы смогли составить представление о булевой алгебре и услугах, которые она может оказать. Действительно, условия реального производства гораздо более сложны, и варианты решений столь же многочисленны, сколь и разнообразны. В этих случаях задача принимает сугубо комбинаторный характер, а это привело бы к перебору астрономического количества решений. С помощью же алгебры Буля достаточно проверить гораздо меньшее число возможностей. Замечу еще, что в некоторых задачах становится почти невозможным анализировать спецификации узлов, начиная со спецификаций по отдельным деталям: тогда эта алгебра становится практически незаменимой.

Рис. 11.1.

Булевы алгебры и их применение

А. Свойства объединения и пересечения

Мы не намереваемся дать на этих нескольких страницах полное изложение булевых алгебр[58], тем не менее попытаемся сначала обосновать примененные выше правила вычислений.

Рассмотрим некоторое множество предметов: например, все шары, содержащиеся в урне. Это множество образует совокупность R, с которой мы будем иметь дело. Разобьем сто шаров на несколько групп. Выделим сначала большие шары, затем обычные; если мы поместим их в два ящика A и B, то в первый мы положим 36 больших шаров, а во второй — 64 обычных (табл. 11.1).

Таблица 11.1.

Таблица 11.2

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

В таблице 11.2 указано число шаров, содержащихся в каждом из десяти ящиков.

а) Понятие объединения

Рис.11.2

Если мы возьмем объединение шаров из ящиков A и B, то получим (рис. 11.2) множество шаров из совокупности R

A È B = R.

Но мы можем также сгруппировать шары по цвету в каждом из классов A и B:

Aк È Aж È Aз È Aс È Aф = A;

Bк ∩ Bж È Bз È Bс È Bф = B,

где через Ак, Вк, Aж, Вж... и т. д. обозначены соответствующие подмножества A и B, содержащие только красные шары, только желтые и т. д.

Естественно, можно переменить порядок, в котором берутся объединения.

Например,

A ÈB = B ÈA = R;

таким образом, операция объединения является коммутативной.

Можно также образовать частичные объединения, например

{[(Aк ÈAж) È Aз] È Aс} ÈAф = A

или

Aк È {[(Aж È Aз) È Aс] È Aф} = A.

Отсюда видно, что операция объединения ассоциативна.

б) Понятие пересечения

Рассмотрим теперь множество красных шаров; оно состоит из 11 обычных шаров и 6 больших. Обозначим его через Ек. Мы имеем

Ек = Ak È Bk.

Множество Ек и множество A имеют общую часть, которая является подмножеством Ак (см. рис. 11.3); запишем

Ек ∩ A = Ak

и обозначим эту операцию термином пересечение.

Имеем также

Ек ∩ B = Bk.

Легко видеть, что пересечение также коммутативно.

Рис. 11.3. Пересечение Ак образовано дважды заштрихованной фигурой.

Предположим теперь, что одни шары сделаны из терракоты T, а другие — из пластмассы Р. Мы проведем соответствующую классификацию при помощи добавочной перегородки в каждом из маленьких ящиков (табл. 11.3).

Таблица 11.3

	Т	P	P	Т
	32	32	21	15
к	5	6	3	3
ж	4	4	2	1
з	9	8	4	5
с	6	8	9	3
ф	8	6	3	3
	64	36

Обозначая через Азт, Азп части ящика А3, содержащие соответственно шары из терракоты и из пластмассы, мы получаем, например, что

Ез = Aз È Bз = Азт ÈАзп ÈВзп ÈВзт.

Рассмотрим операцию

(А ∩ Р) ∩ Ез.

Она состоит во взятии пересечения сначала множеств A и P (рис. 11.4, слева) (пусть это всё шары, содержащиеся в ящике αβγσ), а затем пересечения полученного множества с Е3 (пусть это шары в ящике abсd).

Рис. 11.4. Только квадратик abcd покрыт тройной штриховкой.

Рис. 11.5

Рис. 11.6

Возьмем теперь (рис. 11.4, справа) сначала пересечение P с Е3 (пусть это aβ’γ’d), а затем пересечение aβ’γ’d с A (пусть это abcd). В обоих случаях мы получаем Aзп.

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

А ∩ (P ∩ Ез) = (А ∩ Р) ∩ Ез,

а это означает, что операция пересечения ассоциативна.

в) Вычислим теперь

А È (P ∩ Ез);

покажем, что

А È (P ∩ Ез) = (А ÈР) ∩ (A ÈЕз).

Рисунки 11.5, а и 11.5,б, расположенные рядом, показывают, что объединение дистрибутивно по отношению к пересечению. Это свойство весьма примечательно, так как, например, сложение не дистрибутивно относительно умножения, т. е. равенство

7 + (3 ∙ 5) = (7 + 3) ∙ (7 + 5)

не имеет места.

Покажем теперь, что пересечение дистрибутивно относительно объединения, т. е. что если L, М и N — три множества, то

L ∩ (M È N) = (L ∩ M) È(L ∩ N).

В примере, приведенном выше, покажем, что

А ∩ (P È Ез) = (А ∩ Р) È(A ∩ Ез).

На рис. 11.6, а указан результат операций, соответствующих левой части этого равенства. Рисунок 11.6,б дает, наоборот, правую часть. Легко заметить, что получился одинаковый результат.

г) Теорема де Моргана

Введем сначала класс , соответствующий некоторому классу М; по определению, он состоит из всех элементов совокупности, не принадлежащих M. Например, на рис.11.7 мы заштриховали все то, что входит в нашу совокупность, но не принадлежит Е3; таким образом, мы получили . Рассмотрим теперь (рис. 11.8); легко заметить тождественность фигуры, полученной таким образом, с той, которая получена для множества (рис. 11.9 и 11.10). Аналогичным образом видно (рис. 11.11 и 11.12), что

.

Сопоставим полученные тождества:

и ;

легко усматривается симметрия, или, как еще говорят, двойственность между этими двумя соотношениями, которые представляют собой теорему де Моргана.

Рис. 11.7.

В общем виде, если даны два множества L и М, то

Б. Введение универсальных элементов

Можно условиться обозначать совокупность единицей, т. е. R = 1. Все те рассматриваемые объекты, которые не принадлежат совокупности, образуют пустое множество, которому мы можем сопоставить цифру 0. Таким образом, = 0.

Возьмем теперь совокупность 1 и два множества A и B, являющиеся его частями и такие, что B содержится в A (см. рис. 11.13). Это записывается как

В Ì А.

Заметим, что

B ∩ A = B

и

B È A = A.

Это два способа выражения того, что B Ì А.

Рис.11.8 Рис.11.9 Рис.11.10 Рис.11.11 Рис.11.12

Рис.11.13 Рис.11.14

Предположим теперь, что A совпадает со всей совокупностью (рис. 11.14), тогда получим

B ∩ A = B ∩ 1 = B,

B ÈA = B È 1 = 1.

Заменим теперь A пустым множеством:

B ∩ A = B ∩ 0 = 0,

B È A = B È0 = В.

Легко заметить, что

1 É B É0, В È = 1, В ∩ = 0.

Аналогично очевидно, что

B ÈB = B,

BÇB=B.

Рассмотрим, наконец (рис. 11.15), новый способ обозначения включения; действительно, мы имеем

A È = 1 и ∩ B = 0.

Заметим, что эти два выражения двойственны в смысле де Моргана.

В. Бинарная алгебра Буля

Рассмотрим множество A из некоторой совокупности и сопоставим каждому элементу из R характеристическую функцию, которая принимает значение 1, если х — элемент из A, и 0, если х не принадлежит А.

На рис. 11.16 имеем

f(x) = 1.

Пусть теперь A и B — два множества из R, имеющие непустое пересечение. Схема 1 на рис. 11.17 такова, что

fА(x) = 1, fВ(x) = 1

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

FА ∩ B (x) = 1.

Схема 2 дает

fА(x) = 1, fВ(x) = 0 и FА ∩ B (x) = 0.

На схеме 3 мы имеем

fА(x) = 0, fВ(x) = 1 и FА ∩ B (x) = 0.

Наконец, для схемы 4

fА(x) = 0, fВ(x) = 0, FА ∩ B (x) = 0.

Мы обнаруживаем, что

FА ∩ B (x) = fА(x) ∙ fВ(x)

с обычной таблицей произведений

1 ∙ 1 = 1, 0 ∙ 1 = 0,

1 ∙ 0 = 0, 0 ∙ 0 = 0.

Но речь идет здесь о логическом произведении, введенном выше; действительно, элементы пересечения принадлежат и A, и B, т. е. обладают одновременно и свойствами A (обозначим их через р), и свойствами B (обозначим их через q). Иначе говоря, они обладают свойствами и p, и q.

Рис. 11.16.

Рис. 11.15.

Рассмотрим теперь случай объединения (рис. 11.18). При тех же условиях на

значения fА(x) и fВ(x), как и выше, очевидно, получаем

Случай 1: fА(x) = 1, fВ(x) = 1; FА È B (x) = 1;

Случай 2: fА(x) = 1, fВ(x) = 0; FА È B (x) = 1;

Случай 3: fА(x) = 0, fВ(x) = 1; FА È B (x) = 1;

Cлучай 4: fА(x) = 0, fВ(x) = 0; FА È B (x) = 0;

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

Рис. 11.17

Рис. 11.18

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

1 + 1 = 1, 0 + 1 = 1,

1 + 0 = 1, 0 + 0 = 0.

Вспомним, что логическая сумма элементов двух множеств А и В образуется элементами из А «и/или» В, т. е., если А обладает свойством p, а В обладает свойством q, то A È В обладает свойствами р и q в совокупности (р или q, либо р и q, т. е. р и/или q).

Рис. 11.19

Мы полагаем, что не стоит проверять ни другие свойства, являющиеся теперь очевидными:

А ∙ A = A, А + A = A, A + = 1, А ∙ = 0,

А + 1 = 1, А ∙ 1 = A, А +∙ 0 = A, А ∙ 0 = 0,

ни тем более свойства, связанные с отношением включения (которое в логике называется импликацией):

+ В = 1,

А ∙ = 0.

Впрочем, последние два соотношения связаны теоремой де Моргана.

Естественно, свойства коммутативности, ассоциативности, дистрибутивности распространяются и на бинарную алгебру Буля.

Мы надеемся, что эти рассуждения помогут ознакомиться с бинарной алгеброй Буля (или алгеброй логики) достаточно... логическим путем.

Г. Приложения алгебры Буля

Как мы видели, алгебру Буля можно использовать как инструмент бинарной логической символики, в которой принимаются принципы непротиворечивости (А ∙ = 0) и исключенного третьего (А + = 1).

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

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

Глава 12. Переводчики для Теотиуакана (Задача об управлении персоналом)

Теотиуакан (Мексика)... Каждый год пирамиды этого средоточия археологических памятников привлекают толпы туристов, особенно из Соединенных Штатов. К подлинным развалинам доколумбовских времен (пирамида Солнца, пирамида Луны и другие памятники) следует добавить некоторые недавно воссозданные памятники; все это вместе образует ансамбль, являющийся одной из главных археологических ценностей округа Мехико. Уже многие годы компания «Три звездочки» организует для иностранных туристов ежедневные экскурсии, главной целью которых является поездка в Теотиуакан.

Компания «Три звездочки» арендует в одном специализированном бюро автобусы с шоферами, нанимает гидов-переводчиков и предоставляет все это в распоряжение посетителей. Это бюро имеет гидов-переводчиков, работающих помесячно или постоянно, заработная плата которых составляет ежедневно 41 песо. Постоянные гиды работают пять с половиной дней в неделю, так что их ежедневный заработок можно оценить в 52 песо. Переводчики иногда увеличивают свой заработок заключением маленьких соглашений с продавцами «каритас»[59]. Так утверждают туристы; однако доверять им больше, чем гидам, вряд ли уместно.

Названное бюро имеет такое количество постоянных гидов, что ежедневно может выделить S человек. Если спрос на гидов-переводчиков превышает S, то оно тогда нанимает поденно дополнительных гидов-переводчиков, ежедневная себестоимость содержания которых равна 70 песо. Может случиться, что отсутствие дополнительных гидов-переводчиков вызовет срыв экскурсии; бюро это расценивает как убыток в 400 песо из-за нехватки. Каким числом постоянных гидов-переводчиков должна располагать компания ежедневно, чтобы общая себестоимость была минимальной? На количество автобусов с водителями ограничений не налагается.

Анализ подобной задачи требует знания некоторых статистических величин:

ежедневный спрос на гидов-переводчиков,

ежедневное предложение дополнительных гидов.

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

Таблица 12.1

Ежедневный спрос на гидов-переводчиков.

(1)	Спрос	4	5	6	7	8	9	10	11	12	13	14	15	16
(2)	Частота	2	4	4	8	10	12	12	12	10	10	8	6	2
(3)	Вероятность	0,02	0,04	0,04	0,08	0,10	0,12	0,12	0,12	0,10	0,10	0,08	0,06	0,02
(4)	Накопленная вероятность	0,02	0,06	0,10	0,18	0,28	0,40	0,52	0,64	0,74	0,84	0,92	0,98	1
	Частоты найденные при анализе 100 дней туристического сезона; из них получены вероятности, находящиеся в строках (3) и (4). Средний спрос равен 10,32.

Таблица 12.2