кр гаряев. Чарльз Петцольд - Код_ тайный язык информатики-Манн, Иванов и Фе. Книга принадлежит Контакты владельца Культовая книга талантливого преподавателя стала для многих первым уверенным шагом в программировании
 Скачать 6.11 Mb.
|
|
Количество битов Количество кодов 1 2 1 = 2 2 2 2 = 4 3 2 3 = 8 4 2 4 = 16 5 2 5 = 32 6 2 6 = 64 7 2 7 = 128 8 2 8 = 256 9 2 9 = 512 10 2 10 = 1024 Каждый дополнительный бит удваивает количество кодов. Если известно, сколько нужно кодов, можно ли рассчитать, сколько для этого потребуется битов? Иными словами, как считать в противоположном направлении по вышеприведенной таблице? Используемый при этом метод иногда называется «логарифм по основанию два». Логарифм — феномен, противоположный возведению в степень. Извест- но, что 2 в седьмой степени равно 128. Логарифм 128 по основанию 2 равен 7. В более строгой математической нотации получается, что выражение 2 7 = 128 эквивалентно выражению log 2 128 = 7. Итак, если логарифм 128 по основанию 2 равен 7, а логарифм 256 по ос- нованию 2 равен 8, то каков логарифм 200 по основанию 2? На самом деле он равен примерно 7,64, но нам этого знать и не требуется. Как правило, биты скрыты от поверхностного взгляда в глубинах элект- ронных устройств. Вы не увидите их на компакт-диске, в электронных часах или внутри компьютера. Лишь иногда биты различимы вполне отчетливо. Приведу пример. Если у вас есть обычный фотоаппарат с 35-миллимет- ровой пленкой, возьмите кассету и поверните ее, как показано на рисунке. Глава 9. За битом бит 89 1 2 3 4 5 6 7 8 9 10 11 12 Перед вами предстанет набор серебристых и черных квадратов, отдаленно напоминающий шахматную доску. На рисунке я пронумеровал их от 1 до 12. Этот набор называется DX-кодировкой. Эти 12 квадратов в действительности представляют собой 12 бит. Серебристый квадрат соответствует 1, черный — 0. Квадраты 1 и 7 всегда серебристые (1). Что значат эти биты? Вы, возможно, знаете, что пленки различаются по светочувствительности. Пленка высокой чувствительности считается «бы- строй», поскольку на ней можно производить съемку с очень короткими экс- позициями. Чувствительность пленки измеряется в единицах ASA (American Standards Association, Американская ассоциация по стандартам), причем наи- более популярны пленки с чувствительностью 100, 200 и 400 единиц*. Чув- ствительность в единицах ASA не только напечатана на упаковке, но и зако- дирована на кассете. Различают 24 стандартные степени светочувствительности для фотопленки. 25 32 40 50 64 80 100 125 160 200 250 320 400 500 640 800 1000 1250 1600 2000 2500 3200 4000 5000 * Сегодня в большинстве стран мира используется система ISO (International Organization for Standartization, Международная организация по стандартизации). Обозначения светочувствительности пленки по системам ASA и ISO совпадают. Прим. науч. ред. 90 Код Сколько битов нужно, чтобы закодировать чувствительность пленки? Ответ прост: пять. Мы знаем, что 2 4 = 16, а это слишком мало. А вот 2 5 = 32 — больше чем достаточно. Соответствие между квадратами на кассете и чувствительностью пленки показано в таблице. Квадрат 2 Квадрат 3 Квадрат 4 Квадрат 5 Квадрат 6 Светочувствительность пленки 0 0 0 1 0 25 0 0 0 0 1 32 1 0 0 1 0 50 1 0 0 0 1 64 1 0 0 1 1 80 0 1 0 1 0 100 0 1 0 0 1 125 0 1 0 1 1 160 1 1 0 1 0 200 1 1 0 0 1 250 1 1 0 1 1 320 0 0 1 1 0 400 0 0 1 0 1 500 0 0 1 1 1 640 1 0 1 1 0 800 1 0 1 0 1 1000 1 0 1 1 1 1250 0 1 1 1 0 1600 0 1 1 0 1 2000 0 1 1 1 1 2500 1 1 1 1 0 3200 1 1 1 0 1 4000 1 1 1 1 1 5000 Эти коды используются в большинстве современных 35-миллиметровых фотоаппаратов. Если на вашем фотоаппарате выдержка или тип пленки уста- навливаются вручную, эти коды в нем не применяются. Если же коды все-таки считываются, присмотритесь к фотоаппарату, когда будете вставлять плен- ку. Вы увидите шесть металлических контактов, соответствующих квадратам с первого по шестой на кассете. Серебристые квадраты — это просто открытая металлическая поверхность кассеты, которая является проводником. Черные квадраты покрыты краской, которая не проводит электричество. Электрическая схема фотоаппарата построена так, что ток подводится к первому квадрату на кассете (он всегда серебристый). Этот ток будет (или не будет) проведен пятью контактами на квадратах со второго по шестой в за- висимости от того, окрашены они изолирующей краской или нет. Так, если ток Глава 9. За битом бит 91 присутствует на контактах 4 и 5, но отсутствует на контактах 2, 3 и 6, в фото- аппарат вставлена пленка 400 ASA. При съемке выдержка будет установлена автоматически. В бюджетных фотоаппаратах считываются только квадраты 0 и 3, а чув- ствительность пленки считается равной 50, 100, 200 или 400 единицам ASA. Квадраты с восьмого по двенадцатый в большинстве аппаратов также не ис- пользуются. В квадратах 8, 9 и 10 зашифровано число кадров на пленке, а квадра- ты 11 и 12 содержат сведения о том, черно-белая или цветная пленка, позитивная или негативная. Вероятно, чаще всего вам приходилось сталкиваться с двоичными чис- лами в коде UPC (Universal Product Code, универсальный код продукта), или прос то штрихкоде, — наборе черных полос, который сегодня присутствует практически на любой упаковке. Штрихкод — наглядный символ повсемест- ного проникновения компьютеров в нашу жизнь. Хотя у некоторых людей штрихкод вызывает приступы паранойи, это со- вершенно безобидная вещь, изобретенная для автоматизации розничной тор- говли и учета товаров. Со своей задачей он справляется вполне успешно. Бла- годаря ему, например, современные кассовые аппараты выдают покупателю чек, в котором подробно расписаны все его покупки, чего без штрихкода сде- лать нельзя. Нас же в первую очередь интересует, что код UPC является двоичным, хотя на первый взгляд этого не скажешь. Давайте разберемся, как устроен штрихкод и как он работает. Чаще всего встречается штрихкод, состоящий из нескольких цифр и 30 вертикальных полосок различной толщины, разделенных пустыми ин- тервалами переменной толщины. В качестве примера рассмотрим штрихкод, нанесенный на банку куриного супа с вермишелью фирмы Campbell. 0 7 000 01251 1 5 Сразу хочется разделить код UPC на тонкие и жирные полоски, узкие и широкие промежутки, и это действительно помогло бы разобраться в его структуре. Черные полоски и пустые промежутки штрихкода бывают различ- ной ширины (всего четыре полоски). 92 Код Конечно, удобнее трактовать UPC как набор битов. Имейте в виду, что сканирующему устройству нет нужды просматривать штрихкод целиком, тем более прибор не может интерпретировать цифры в его основании, поскольку это потребовало бы применения сложной компьютерной технологии распо- знавания символов (Optical Character Recognition, OCR). Сканеру достаточно «увидеть» тонкий срез штрих-кода. Код UPC делают таким большим просто для того, чтобы кассиру легче было нацелить на него сканер. Срез, попадаю- щий в сканер, выглядит следующим образом. Почти как азбука Морзе, правда? Сканируя эту информацию слева направо, компьютер присваивает бит 1 первой встреченной черной полоске и бит 0 первому промежутку. Следующие промежутки и штрихи считываются как последовательности одного, двух, трех или четырех битов в зависимости от ширины штриха или промежутка. В би- товом представлении этот штрихкод выглядит так. 10100011010110001001100100011010001101000110101010111001011001101101100100111011001101000100101 Итак, весь UPC — просто последовательность из 95 бит. В данном случае их можно сгруппировать. Биты Значение 101 Левый шаблон-ограничитель 0001101 Цифры слева 0110001 0011001 0001101 0011001 01010 Центральный шаблон-разделитель 1110010 Цифры справа 1100110 1101100 1001110 1100110 1000100 101 Правый шаблон-ограничитель Глава 9. За битом бит 93 Первые три бита — всегда 101. Они называются левым шаблоном-ограни- чителем и нужны для того, чтобы настроить сканирующее устройство. По ша- блону-ограничителю сканер определяет ширину штриха и промежутка, соот- ветствующую одному биту. Иначе на всех упаковках код UPC пришлось бы делать одинакового размера. За левым шаблоном-ограничителем следует шесть групп по семь бит в каж- дой. В них закодированы десятичные цифры от 0 до 9, в чем мы убедимся чуть позже. Затем идет 5-битовый центральный шаблон-разделитель — фиксиро- ванная группа битов (всегда 01010), используемая как встроенная контрольная система. Не найдя центрального шаблона-разделителя в нужном месте, сканер считает штрихкод неверным. В частности, так выявляют плохо пропечатанные или поддельные штрихкоды. За центральным шаблоном-разделителем всегда идут еще шесть групп по семь бит каждая, а за ними — правый шаблон-ограничитель, всегда равный 101. Позже я расскажу, почему благодаря наличию правого шаблона-ограничителя штрихкод можно сканировать и в обратном направлении, то есть справа налево. Всего в коде UPC зашифровано 12 десятичных цифр. Шесть из них зако- дированы с его левой стороны, по семь бит в каждой. Для их расшифровки применяется таблица. Левосторонние коды 0001101 = 0 0110001 = 5 0011001 = 1 0101111 = 6 0010011 = 2 0111011 = 7 0111101 = 3 0110111 = 8 0100011 = 4 0001011 = 9 Обратите внимание: каждый 7-битовый код начинается с 0 и заканчивается 1. Встретив 7-битовый код, который начинается с 1, а заканчивается 0, сканер «пони- мает», что код UPC либо неверно прочитан, либо подделан. Кроме того, в каждом коде группы единиц встречаются лишь дважды. Это значит, что каждая десятич- ная цифра в коде UPC зашифрована двумя вертикальными штрихами. Еще одна особенность кодов в этой таблице — нечетное количество еди- ниц в каждом из них. Она также позволяет проверить корректность штрих- кода — так называемый контроль четности (parity). Группа битов обладает четным паритетом, если в ней четное количество битов-единиц, и нечетным паритетом, если в ней нечетное количество битов-единиц. Для расшифровки битов в правой части штрихкода применяется таблица. 94 Код Правосторонние коды 1110010 = 0 1001110 = 5 1100110 = 1 1010000 = 6 1101100 = 2 1000100 = 7 1000010 = 3 1001000 = 8 1011100 = 4 1110100 = 9 Эти коды дополняют коды из предыдущей таблицы. Там, где в левосто- ронних кодах был 0, теперь стоит 1, и наоборот. Правосторонние коды всегда начинаются с 1 и заканчиваются 0. Кроме того, число битов 1 в них всегда чет- ное, что можно применять для контроля четности. Вот мы и готовы к расшиф- ровке UPC. С помощью двух приведенных выше таблиц можно определить 11 цифр, зашифрованных на банке Campbell Soup. 0 51000 01251 7 Какая досада! Да, это те самые цифры, что напечатаны под штрихкодом. На самом деле это очень удобно: если сканер по каким-то причинам не смог прочитать код, кассир может ввести его вручную. Вы наверняка видели, как это бывает. Конечно, получается, что весь наш труд по расшифровке штрихкода был напрасным, к тому же никакой секретной информации мы так и не полу- чили: просто 30 вертикальных штрихов превратились в 12 цифр. Первая цифра (в данном случае 0) характеризует тип кода. 0 означает, что перед нами обычный код UPC. Если код нанесен на упа- ковку с товаром переменного веса, например с мясом или овощами, он начи- нается с 2. Товары со скидкой обозначаются цифрой 5. Следующие пять цифр — код производителя. В нашем примере код 51000 соответствует компании Campbell Soup. Он есть на всех продуктах марки Campbell. За ними следует пятизначный (01251) код конкретного продукта этой компа- нии, в нашем случае код банки с куриным супом. Код продукта информати- вен лишь в сочетании с кодом производителя. У куриного супа с вермишелью, выпущенного другой компанией, будет другой код продукта, в свою очередь код 01251 может значить нечто совершенно иное у другого производителя. Вопреки распространенному мнению, в код UPC не включается цена то- вара. Информация о ней извлекается из компьютерной базы данных, исполь- зуемой в кассовых аппаратах наряду со сканерами. Последняя цифра (здесь — 7) называется символом проверки остатка и тоже используется для исключения ошибок. Чтобы проверить его на прак- тике, присвоим букву каждой из первых 11 цифр (наш пример 0 51000 01251). Глава 9. За битом бит 95 A BCDEF GHIJK Теперь вычислим: 3 × (A + C + E + G + I + K) + (B + D + F + H + J). Вычтем результат из ближайшего большего числа, кратного десяти. По- лученное число и будет символом проверки остатка для куриного супа с вер- мишелью Campbell: 3 × (0 + 1 + 0 + 0 + 2 + 1) + (5 + 0 + 0 + 1 + 5) = 3 × 4 + 11 = 23. Ближайшее большее число, кратное десяти, — 30. Значит, 30 – 23 = 7. Это число — результат проверки остатка — напечатано под штрихкодом и зашифровано в нем. Такая проверка — одна из форм избыточности. Если остаток, вычисленный по штрихкоду, не совпадет с остатком, явно указанным в нем, штрихкод будет сочтен недействительным. Как правило, для представления десятичной цифры от 0 до 9 достаточ- но четырех бит. В штрихкодах используется по семь бит на цифру. Целыми 95 бит закодировано всего 11 значимых десятичных цифр. Если учесть, что UPC с обеих сторон ограничен пустым пространством, эквивалентным девяти нуле- вым битам, получается, что во всем штрихкоде 11 цифр закодировано 113 бит, по 10 бит на цифру! Такая избыточная надежность отчасти требуется для защиты от ошибок. Код товара был бы не слишком полезен, если бы покупатель мог в два счета подправить его фломастером. Кроме того, UPC удобен, поскольку его можно считывать в обоих направ- лениях. Если в первых считанных цифрах количество единиц четно, сканер распознает, что код читается справа налево. Для расшифровки правосторон- них цифр компьютер использует следующую таблицу. Правосторонние коды в обратном направлении 0100111 = 0 0111001 = 5 0110011 = 1 0000101 = 6 0011011 = 2 0010001 = 7 0100001 = 3 0001001 = 8 0011101 = 4 0010111 = 9 Вот таблица левосторонних кодов. 96 Код Левосторонние коды в обратном направлении 1011000 = 0 1000110 = 5 1001100 = 1 1111010 = 6 1100100 = 2 1101110 = 7 1011110 = 3 1110110 = 8 1100010 = 4 1101000 = 9 Эти 7-битовые коды отличаются от кодов, считываемых слева направо. Никакой путаницы не возникает. Наше знакомство с кодами началось с азбуки Морзе, состоящей из точек, тире и промежутков между ними. Азбука Морзе, на первый взгляд, имеет мало общего с нулями и единицами, на деле же сводится именно к ним. Вспомните устройство азбуки Морзе. Тире втрое длиннее точки. Точки и тире в пределах одной буквы разделены паузами продолжительностью в одну точку. Промежутки между буквами по длительности равны одному тире. Сло- ва разделяются паузами в два тире. Чтобы немного упростить анализ, допустим, что длина тире превышает длину точки не в три, а в два раза. Это означает, что точка соответствует од- ному единичному биту, а тире — двум единичным битам. Паузы состоят из нулевых битов. Вот простейшая таблица с азбукой Морзе из главы 1. A • — B — • • • C — • — • D — • • E • F • • — • G — — • H • • • • I • • J • — — — K — • — L • — • • M — — N — • O — — — P • — — • Q — — • — R • — • S • • • T — U • • — V • • • — W • — — X — • • — Y — • — — Z — — • • А вот та же таблица, преобразованная в биты. A 101100 B 1101010100 C 11010110100 D 11010100 E 100 F 1010110100 G 110110100 H 101010100 I 10100 J 101101101100 K 110101100 L 1011010100 M 1101100 N 110100 O 1101101100 P 10110110100 Q 110110101100 R 10110100 S 1010100 T 1100 U 10101100 V 1010101100 W 101101100 X 11010101100 Y 110101101100 Z 11011010100 Глава 9. За битом бит Обратите внимание: все коды начинаются с 1 и кончаются парой 0, пред- ставляющей паузу между буквами в пределах одного слова. Кодом пробела меж- ду словами является дополнительная пара 0. Таким образом, на азбуке Морзе фраза Hi there выглядит так. • • • • • • — • • • • • • — • • Представив ее в битах, мы получим нечто очень похожее на срез штрихкода. 101010100101000011001010101001001011010010000 В битовом выражении азбука Брайля гораздо проще азбуки Морзе. Шрифт Брайля является 6-битовым кодом. Каждый символ — набор из шести точек, каждая из которых может быть выпуклой или плоской. Как говорилось в гла- ве 3, обычно точки нумеруются от 1 до 6. 1 2 3 4 5 6 Например, вот как записывается шрифтом Брайля слово code, где край- ний левый бит соответствует первой позиции, а крайний правый — шестой. Позже мы узнаем, что с помощью битов можно зашифровать не только коды товаров, чувствительность пленки, художественную ценность фильма, способ наступления британской армии или послание любимой женщине, но и любые слова, изображения, звуки, музыку и кино. В своей основе биты — это числа. Для представления информации в форме битов достаточно пересчитать коли- чество доступных возможностей. Это количество определяет, сколько битов по- надобится для того, чтобы присвоить каждой возможности уникальный номер. Биты также играют важную роль в логике, находящейся на стыке фило- софии и математики; ее главная цель — определение истинности или ложнос- ти некоего утверждения. Истину и ложь также можно обозначить через 1 и 0. 98 Глава 10 Логика и переключатели Что есть истина? Аристотель полагал, что она как-то связана с логикой. Сбор- ник его сочинений под названием «Органон» (датируемый IV веком до н. э.) — самое раннее произведение, где подробно освещается эта тема. Для древних греков логика — средство анализа языка c целью нахождения истины, поэто- му она считалась формой философии. Основа логики Аристотеля — силло- гизм. Самый известный силлогизм (который фактически отсутствует в рабо- тах Арис тотеля) формулируется так: Все люди смертны; Сократ — человек; следовательно, Сократ смертен. В силлогизме из двух считающихся истинными предпосылок выводится заключение. Смертность Сократа может показаться достаточно очевидной, однако су- ществует множество разнообразных силлогизмов. Рассмотрим следующие две предпосылки, которые предложил математик XIX века Чарльз Доджсон, из- вестный как Льюис Кэрролл: Все философы логичны; нелогичный человек всегда упрям. В данном случае вывод не очевиден. Он формулируется так: «Некоторые упрямые люди не являются философами». Обратите внимание на неожидан- ное и привносящее неопределенность слово «некоторые». На протяжении более двух тысяч лет математики боролись с логикой Арис тотеля, пытаясь укротить ее с помощью математических символов и опе- раторов. До XIX века ближе всех к решению этой задачи удалось подойти только Готфриду Вильгельму фон Лейбницу (1646–1716), который занимался Глава 10. Логика и переключатели 99 логикой в молодости, а затем заинтересовался иными вещами, например од- новременно с Исааком Ньютоном разработал дифференциальное исчисление (независимо от него) *. Затем на сцену вышел Джордж Буль. Джордж Буль родился в 1815 году в Англии в социуме, где его шансы на успех были очень малы. Поскольку он был сыном башмачника и бывшей горничной, его перспективы не сильно отличались от перспектив его предков по причине жесткой классовой иерархии британского общества. Однако бла- годаря своему пытливому уму и отцу, который интересовался наукой, мате- матикой и литературой, молодой Джордж получил образование, как правило являющееся привилегией мальчиков из высших классов общества. Он изучал латынь, греческий язык и математику. Ранние работы Буля по математике по- зволили ему в 1849 году стать первым профессором математики в Королев- ском колледже Корка. Несколько математиков в середине 1800-х годов работали над формаль- ным определением логики (среди них особо выделялся Огастес де Морган). Однако именно Буль совершил настоящий концептуальный прорыв: сначала в короткой книге «Математический анализ логики, или Очерк исчисления де- дуктивных умозаключений» (1847), затем в гораздо более объемном и амбици- озном произведении «Исследование законов мышления, на которых основаны математические теории логики и вероятностей» (1854), которое кратко также называется «Исследование законов мышления». Буль умер в 1864 году в воз- расте 49 лет от пневмонии, которую он подхватил, попав под дождь по доро- ге на лекцию. Название книги Буля 1854 года говорит о постановке амбициозной зада- чи: поскольку мозг разумного человека мыслит, используя логику, то, найдя способ математического представления логики, мы получим математическое описание того, как работает мозг. Разумеется, в наше время такое ви´дение ка- жется весьма наивным (или просто оно значительно опережает свое время). Изобретенная Булем алгебра очень похожа на обычную. В обычной ал- гебре операнды (обычно буквы) обозначают цифры, а операторы (например, «+» и «×») указывают, как эти числа должны объединяться. Как правило, мы используем обычную алгебру для решения таких задач: у Ани есть три ябло- ка. У Бетти в два раза больше яблок, чем у Ани. У Кармен на пять яблок боль- ше, чем у Бетти. У Дейрдре в три раза больше яблок, чем у Кармен. Сколько яблок у Дейрдре? * Лейбниц и Ньютон предложили разный терминологический аппарат и различные формы записи дифференциального исчисления. В итоге победил вариант Лейбница. Прим. науч. ред. 100 Код Чтобы решить эту задачу, сначала преобразуем ее в арифметические вы- ражения, используя четыре буквы, соответствующие количеству яблок, имею- щихся у каждой из четырех женщин: A = 3; Б = 2 × A; К = Б + 5; Д = 3 × К. Мы можем объединить эти четыре выражения в одно путем подстановки, а затем уже выполнить операции сложения и умножения: Д = 3 × К; Д = 3 × (Б + 5); Д = 3 × ((2 × А) + 5); Д = 3 × ((2 × 3) + 5); Д = 33. Имея дело с обычной алгеброй, мы следуем определенным правилам. Эти правила настолько укоренились в практике, что мы больше не думаем о них как о правилах и даже иногда забываем их названия. Однако любая форма ма- тематики подчиняется им. Первое правило заключается в том, что сложение и умножение являют- ся коммутативными операциями. Это означает, что можно менять операнды местами в обеих частях выражения, не влияя на результат: A + B = B + A; A × B = B × A. Напротив, операции вычитания и деления не являются коммутативными. Сложение и умножение — ассоциативные операции, то есть: A + (B + C) = (A + B) + C; A × (B × C) = (A × B) × C. Наконец, умножение дистрибутивно по отношению к сложению: A × (B + C) = (A × B) + (A × C). Глава 10. Логика и переключатели 101 Другой характеристикой обычной алгебры является то, что она всегда оперирует числами, например килограммами сыра, количеством уток, расстоя- нием, которое прошел поезд, или возрастом членов семьи. Гений Буля сделал алгебру более абстрактной, отделив ее от концепции числа. В булевой алгебре (именно такое название получила алгебра Буля) операнды относятся не к чис- лам, а к классам. Класс — это просто набор предметов, который в дальнейшем стал множеством. Поговорим о кошках. Кошки могут быть мужского и женского пола. Для удобства множество котов будем обозначать буквой M, а множество кошек — Ж. Имейте в виду, что эти два символа не соответствуют количеству кошек. Ко- личество котов и кошек может меняться с течением времени по мере того, как новые особи рождаются, а старые, к сожалению, уходят в мир иной. Эти бук- вы обозначают классы кошек со специфическими характеристиками. Говоря о котах, мы можем просто сказать «М». Мы также можем использовать другие буквы для обозначения окраса кошек: буквой Р описать множество рыжих, буквой Ч — множество черных, буквой Б — множество белых, а буквой Д — множество кошек всех «других» цветов, то есть кошек, не входящих в классы Р, Ч или Б. Наконец (по крайней мере, в нашем примере) кошки могут быть либо сте- рилизованными, либо нет. Давайте обозначим буквой С множество стерили- зованных кошек, а буквой Н — множество нестерилизованных. В обычной (числовой) алгебре операторы «+» и «×» используются для обозначения операций сложения и умножения. В булевой алгебре применя- ются те же символы «+» и «×», что может вызвать путаницу. Всем известно, как складывать и умножать числа в обычной алгебре, но как можно склады- вать и умножать классы? Дело в том, что в булевой алгебре мы фактически ничего не складываем и не умножаем. Вместо этого символы «+» и «×» означают нечто совершенно иное. В булевой алгебре символ «+» — это объединение двух классов, которое предполагает объединение всего, относящегося к первому классу, со всем, от- носящимся ко второму. Например, выражение Ч + Б означает множество всех кошек черного и белого окраса. Символ «×» — это пересечение двух классов, то есть пересечение множе- ства элементов, принадлежащих как первому, так и второму классу. Например, Ж × Р — класс всех кошек женского пола и рыжего окраса. Как и в обычной ал- гебре, мы можем написать Ж × Р в виде Ж и Р или просто ЖР (именно так пред- почитал писать сам Буль). Вы можете рассматривать эти две буквы в качестве двух прилагательных, описывающих множество «рыжие кошки женского пола». 102 Код Чтобы не спутать обычную алгебру с булевой, вместо символов «+» и «×» для обозначения объединения и пересечения классов иногда используются символы U и ∩. Однако освобождающее влияние Буля на математику отчасти заключалось в том, чтобы сделать использование знакомых операторов более абстрактным, поэтому, следуя его примеру, я решил не вводить новые символы. Коммутативные, ассоциативные и дистрибутивные правила остаются справедливыми в булевой алгебре. Более того, здесь оператор «+» является дистрибутивным по отношению к оператору «×», чего нельзя сказать об обыч- ной алгебре: Б + (Ч × Ж) = (Б + Ч) × (Б + Ж). Объединение белых и черных кошек-самок равнозначно пересечению двух объединений: белых и черных кошек, а также белых кошек и кошек-самок. Это сложно понять, но все именно так и устроено. Булевой алгебре необходимы еще два символа. Они смахивают на числа, но ими не являются, поскольку иногда с ними обращаются не так, как с числа- ми. Символ 1 означает множество всех вещей, о которых мы говорим. В дан- ном примере 1 — это множество всех кошек: М + Ж = 1. Значит, множество всех кошек содержит самцов и самок. Точно так же оно включает всех кошек рыжего, черного, белого и других окрасов: Р + Ч + Б + Д = 1. Кроме того, множество всех кошек можно получить и так: С + Н = 1. Символ 1 может использоваться со знаком минус, чтобы указать на мно- жество всех вещей, исключающее некое подмножество, например: 1 − М. Как видите, это множество всех кошек, кроме самцов. Множество всех ко- шек, исключающее всех самцов, соответствует множеству кошек женского пола: Глава 10. Логика и переключатели 103 1 − М = Ж. Другой необходимый символ — 0, а в булевой алгебре 0 означает пустое множество, которое ничего не содержит. Пустое множество — результат пере- сечения двух взаимоисключающих множеств, например множество кошек- гермафродитов: Ж × М = 0. Обратите внимание: символы 1 и 0 иногда работают одинаково в булевой и в обычной алгебре. Например, пересечение множества всех кошек и кошек женского пола соответствует множеству кошек-самок: 1 × Ж = Ж. Пересечение пустого множества и множества кошек-самок представляет пустое множество: 0 × Ж = 0. Объединение пустого множества и множества всех кошек-самок — это множество кошек-самок: 0 + Ж = Ж. Однако иногда результаты в булевой и в обычной алгебре отличаются. Напри- мер, объединение всех кошек и кошек-самок соответствует множеству всех кошек: 1 + Ж = 1. Это не имеет смысла в обычной алгебре. Поскольку Ж — множество всех кошек-самок, а 1 − Ж — множество всех кошек, которые не являются самками, объединение этих двух множеств соот- ветствует 1: Ж + (1 − Ж) = Ж + М = 1. Пересечение двух множеств соответствует 0: Ж × (1 − Ж) = 0. 104 Код С исторической точки зрения эта формулировка — важная веха в логике, называемая законом противоречия, который гласит, что нечто не может одно- временно являться собой и своей противоположностью. Где булева алгебра действительно отличается от обычной, так это в сле- дующем выражении: Ж × Ж = Ж. Пересечение множества кошек-самок и множества кошек-самок по-преж- нему множество кошек-самок. Это выражение имеет смысл в булевой алгебре. Однако оно неверное, если бы буква Ж означала число. Буль считал, что вы- ражение X 2 = X является единственным выражением, отличающим его алге- бру от обычной. Вот еще одно булево выражение, которое выглядит странно с точки зрения обычной алгебры: Ж + Ж = Ж. Объединение множества кошек-самок и множества кошек-самок по-преж- нему является множеством кошек-самок. Булева алгебра предоставляет математический метод для решения силло- гизма Аристотеля. Давайте рассмотрим первые две его части: Все люди смертны; Сократ — человек. Буквой Л мы обозначим множество всех людей, буквой Х — множество всех смертных существ, а буквой С — множество Сократов. Что означает вы- ражение «все люди смертны»? Пересечение множества всех людей и множества всех смертных существ — это множество всех людей: Л × Х = Л. Выражение Л × Х = Х было бы неправильным, поскольку множество всех смертных существ включает кошек, собак и деревья. Выражение «Сократ — человек» означает, что пересечение множества Сократов (очень небольшого множества) и множества всех людей (гораздо бо- лее крупного множества) представляет множество Сократов: С × Л = С. Глава 10. Логика и переключатели 105 Поскольку из первого уравнения известно, что Л равно Л × Х, можем под- ставить это выражение во второе: С × (Л × Х) = С. Согласно ассоциативному закону это равнозначно выражению: (С × Л) × Х = С. Однако мы уже знаем, что С × Л равно С, поэтому можем упростить вы- ражение, используя эту подстановку: С × Х = С. Теперь мы закончили. Эта формула указывает, что пересечение множества Сократов и множества всех смертных существ есть С, а это значит, что Сократ смертен. Если бы вместо этого оказалось, что С × Х равно 0, мы бы пришли к выводу, что Сократ не был смертным. Если бы мы обнаружили, что С × Х равно Х, то вывод заключался бы в том, что Сократ является единственным смертным существом, а все остальные бессмертны. Использование булевой алгебры может показаться излишним для дока- зательства очевидного факта (особенно учитывая то, что Сократ доказал соб- ственную смертность 2400 лет назад), однако ее можно использовать для того, чтобы определить, удовлетворяет ли что-то определенному набору критериев. Возможно, однажды вы зайдете в зоомагазин и скажете продавцу: «Мне ну- жен стерилизованный кот белого или рыжего окраса, или стерилизованная кошка любого окраса, кроме белого, или я возьму любую из имеющихся у вас черных кошек». И продавец скажет, что вам нужна кошка из множества, опи- сываемого следующим выражением: (М × С × (Б + Р)) + (Ж × С × (1 − Б)) + Ч. Верно? И вы ответите: «Да! Точно!» Проверяя, правильно ли продавец вас понял, можно отказаться от по- нятий объединения и пересечения, вместо них использовать слова ИЛИ и И. Я пишу эти слова заглавными буквами, потому что они не только соответ- ствуют понятиям в обычном языке, но и могут представлять собой опера- ции в булевой алгебре. Когда вы формируете объединение двух множеств, вы фактически берете элементы из первого ИЛИ второго множества. А когда вы 106 Код формируете пересечение, то берете только те элементы, которые одновремен- но принадлежат первому И второму множествам. Кроме того, вы можете ис- пользовать слово НЕ везде, где встречается символ 1, за которым следует знак «минус». Таким образом: ȣ символ «+» (ранее обозначавший объединение) теперь означает ИЛИ; ȣ символ «×» (ранее обозначавший пересечение) теперь означает И; ȣ выражение «1 –» (ранее обозначавшее множество всех элементов, за ис- ключением чего-то) теперь означает НЕ. Именно поэтому приведенное выше выражение также может быть записано: (М И С И (Б ИЛИ Р)) ИЛИ (Ж И С И (НЕ Б)) ИЛИ Ч. Как видите, это соответствует тому, что вы сказали. Обратите внимание, как скобки уточняют ваши пожелания. Вам нужна кошка, принадлежащая од- ному из трех множеств. (М И С И (Б ИЛИ Р)) |