Алгебра логики

Для закрепления материала настоятельно советуется ресурс NAND Game, который демонстрирует способ построения нетривиальной ЭВМ на основе одной логической операции (штриха Шеффера, о котором кратко повествуют следующие разделы).

Основные операции и законы

Основные операции

Общепринятым для цифровой электроники стандартом является использование двух элементарных сигналов: условно \(0\) и \(1\). В связи с этим наиболее простой моделью такой электроники является отображение \(\mathbf{2}^m\to \mathbf{2}^n\), имеющее, грубо говоря, \(m\) двоичных входов и \(n\) двоичных выходов (символом \(\mathbf{2}\) здесь обозначено множество \({0,1}\)).

Отображения \(\mathbf{2}^n\to \mathbf{2}\) мы будем называть логическими операциями арности \(n\) или \(n\)-арными операциями. Элементарные величины \(0\) и \(1\) можно считать операциями арности \(0\). Всего \(n\)-арных операций, как нетрудно вычислить, \(2^{2^n}\). В частности, есть четыре унарных операции и шестнадцать бинарных. Наиболее интересны следующие:

Отрицание: \(\lnot 0 = 1\) и \(\lnot 1 = 0\).

Альтернативные обозначения: \(\lnot x = \overline{x} = \,!x\).

Конъюнкция: \(x\land y = 1\) тогда и только тогда, когда \(x=1\) и \(y=1\).

Альтернативные обозначения: \(x\land y = x\cdot y = x\times y = xy = x \& y\).

Дизъюнкция: \(x\lor y = 1\) тогда и только тогда, когда хотя бы кто-то из \(x\) или \(y\) равен \(1\).

Альтернативные обозначения: \(x\lor y = x\,|\,y = x+y\).

Сложение (или XOR от eXclusive OR): \(x\oplus y = (x+y)\bmod 2\).

Альтернативные обозначения: \(x\oplus y = x+y\).

Импликация: \(x\Rightarrow y = \overline{x} \lor y\).

Штрих Шеффера (или NAND от Not AND): \(x\,|\,y = \lnot(xy)\).

Стрелка Пирса (или NOR от Not OR): \(x\downarrow y = \lnot(x\lor y)\).

Как можно заметить, некоторые обозначения используются сразу для нескольких операций. Поэтому мы остановимся на некоторой единой системе обозначений: \(\lnot x\) и \(\overline{x}\) — для отрицания, \(xy\) и \(x\land y\) — для конъюнкции, \(x\lor y\) — для дизъюнкции, \(x + y\) — для сложения.

Алгебраические свойства

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

Законы де Моргана: \(\overline{x\land y} = \overline{x}\lor\overline{y}\) и \(\overline{x\lor y} = \overline{x}\land\overline{y}\).

Снятие двойного отрицания: \(\lnot\lnot x = x\).

Третьего не дано: \(x\lor\overline{x} = 1\).

Коммутативность: \(xy=yx\) (выполняется также для \(\lor\) и \(+\)).

Ассоциативность: \(x(yz)=x(yz)\) (выполняется также для \(\lor\) и \(+\)).

Дистрибутивность: \(x(y+z)=xy+xz\) (выполняется также для \(\lor,\land\) и \(\land,\lor\)).

Идемпотентность: если \(n\geqslant 1\), то \(x^n=x\).

СДНФ и СКНФ

Нормальные формы

Начнём с пары терминов. Предположим, что есть некий набор правил преобразования формул. Например:

  • \(\lnot\lnot x\) разрешается заменить на \(x\)
  • \(\lnot(x\land y)\) разрешается заменить на \(x\lor y\)
  • \(\lnot(x\lor y)\) разрешается заменить на \(x\land y\)

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

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

Например, формула \(x\land\lnot y\) является нормальной формой относительно вышеприведённого набора правил.

А вот формула \(\lnot(x\land\lnot y)\) не является. При этом её можно нормализовать, получив нормальную форму \(\lnot x\lor y\).

Отметим несколько важных моментов:

  • поскольку процесс нормализации зачастую определён неоднозначно, потенциально из одной и той же формулы можно получить несколько разных нормальных форм
  • конкретно вышеприведённая тройка правил гарантирует завершение процесса нормализации и единственность результирующей нормальной формы

Совершенная дизъюнктивная нормальная форма

Рассмотрим следующую задачу: имея некий набор операций, научиться выражать произвольную операцию в виде комбинации имеющихся. Оказывается, для набора \(\land,\lor,\lnot\) эта задача решается особенно легко: если \(f(x) = 1\) только для \(x=(x_1,x_2,\ldots,x_n)=(a_1,a_2,\ldots,a_n)\), то

\[ f(x_1,x_2,\ldots,x_n)= (\lnot^{\lnot a_1} x_1)(\lnot^{\lnot a_2} x_2)\ldots (\lnot^{\lnot a_n} x_n) \]

В общем случае достаточно взять дизъюнкцию таких выражений для всех \(a\), для которых \(f(a)=1\).

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

Результатом такой манипуляции является штуковина (дизъюнкция конъюнкций), называемая совершенной дизъюнктивной нормальной формой (коротко СДНФ) операции \(f\). Например, импликация имеет СДНФ

\[ x\Rightarrow y = \overline{x}\,\overline{y}\lor \overline{x}y\lor xy \]

Нетрудно заметить, что СДНФ определена с точностью до перестановки конъюнктов внутри дизъюнктов и перестановки самих дизъюнктов.

Совершенная конъюнктивная нормальная форма

Аналогичным образом можно построить «двойственный» объект — СКНФ.

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

Написанные дизъюнкции следует соединить операциями конъюнкции.

Например, для XOR СКНФ имеет вид

\[ x\oplus y = (\overline{x}\lor\overline{y})\land (x\lor y) \]

А для импликации СКНФ следует запомнить наизусть:

\[ x\Rightarrow y = \overline{x}\lor y \]

И опять NAND

Наличие СДНФ и СКНФ у произвольной зависимости показывает, что любую зависимость можно реализовать лишь комбинируя дизъюнкции с отрицаниями (или конъюнкции с отрицаниями).

Тем не менее, при некотором желании можно обойтись и одной операцией. К таким универсальным операциям относятся, например, NAND (и заодно его двойственная операция — NOR).

Это следует из (тривиально проверяемых) соотношений

  • \(\lnot x = x\,|\,x\)
  • \(x\land y = \lnot(x\,|\,y) = (x\,|\,y)\,|\,(x\,|\,y)\)

Многочлены

В заключение рассмотрим ещё один полный (т.е. такой, при помощи которого можно выразить любую зависимость) набор операций: единица, XOR, конъюнкция (далее: \(1,+,\cdot\)).

С этим набором операций ситуация не сильно сложнее: интерполяционная формула Лагранжа для вершин \(n\)-мерного куба даёт выражение

\[ f(x) = \sum_a f(a) (x_1+\overline{a_1}) (x_2+\overline{a_2})\ldots (x_n+\overline{a_n}) \]

Верность равенства тривиально проверяется подстановкой \(a\) или же замечанием о том, что эта формула получена путём формальной замены в СДНФ дизъюнкции на XOR. Поскольку для любого значения \(x\) не более чем один из дизъюнктов равен 1, XOR дизъюнктов СДНФ равен их дизъюнкции.

После раскрытия скобок и приведения подобных получается сумма одночленов, каждый из которых любую из переменных содержит в не более чем первой степени. Такая сумма называется многочленом Жегалкина функции \(f\).

Различных одночленов \(2^n\), поэтому различных многочленов Жегалкина \(2^{2^n}\) — ровно столько же, сколько и \(n\)-арных операций. Поскольку любая операция имеет хотя бы один многочлен Жегалкина, то, согласно принципу Дирихле, любая операция имеет ровно один многочлен Жегалкина.

Например, импликация имеет многочлен Жегалкина

\[ x\Rightarrow y = (x+1)y+(x+1)(y+1)+xy = xy + x + 1 \]

Измерение информации

Количество информации

Передача информации

Вообще говоря, очень трудно дать определение термину «информация». Один из возможных подходов — формализовать не само понятие информации, а понятие передачи информации.

Передачей информации мы назовём пару конечных вложенных множеств \(A\subset B\). Это можно интерпретировать так:

  • Вася знает, что мир вокруг него находится в одном из состояний, принадлежащих множеству \(B\), но не знает, в каком конкретно
  • Петя что-то Васе сообщает
  • теперь Вася знает, что некоторые из рассматриваемых им до этого возможных состояний мира не совместимы с собщением Пети; остаётся некоторое подмножество \(A\) допустимых теперь Васей состояний мира

Обратим внимание, что ситуация \(A=B\) вполне соответствует житейско-бытовой фразе «Петя не сообщил Васе никакой новой для него информации».

Измерение количества информации

Иногда хочется как-то количественно выражать информативность Петиного сообщения с точки зрения Васи.

Совсем наивный способ

Назвать количеством информации разность размеров соответствующих множеств: \(|B|-|A|\).

У такого способа есть очень серьёзный недостаток: зависимость от масштаба. А именно, рассмотрим две ситуации.

Ситуация первая

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

Вася спрашивает у Пети, находящегося на улице, идёт ли там дождь. Петя отвечает, что не идёт. Множество Васи уменьшилось до размера 1. Значит, Петя сообщил Васе одну единицу информации.

Ситуация вторая

Вася знает, что на улице либо идёт дождь, либо не идёт, но не видит эту улицу, поскольку сейчас находится на видеоконференции. Также Вася знает, что его кот находится либо на кухне, либо в ванной. Его знания моделируются четырёхэлементным множеством.

Вася спрашивает у Пети, находящегося на улице, идёт ли там дождь. Петя отвечает, что не идёт. Множество Васи уменьшилось до размера 2. Значит, Петя сообщил Васе две единицы информации.

А ситуации-то совершенно одинаковы с точки зрения внешнего наблюдателя!

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

Менее наивный способ

Назвать количеством информации отношение размеров множеств \(|B|/|A|\).

Такой способ масштабоинвариантен: это хорошо.

Также этот способ позволяет вообще не строить явные модели множеств знаний. Вместо этого можно:

  • рассмотреть множество всевозможных сообщений, которые Петя может сообщить Васе
  • сделать гипотезу о том, что все они несут одинаковое количество информации
  • вычислить количество информации одного сообщения как размер множества всевозможных сообщений

Например, если Вася спросил Петю, какого цвета у Пети автомобиль, Вася ожидает получить какой-то цвет в качестве ответа: любой ответ Пети (если, конечно, предположить, что Петя назовёт конкретный цвет) уменьшит размер множества неопределённости знаний Васи во столько раз, сколько цветов Петя может потенциально Васе сообщить.

Основной недостаток такого способа измерения информации: он мультипликативен. Если первое сообщение несёт \(x\) единиц информации, а второе — несёт \(y\) единиц информации, то оба сообщения вместе несут \(x\cdot y\) единиц информации. Большинство же способов измерения чего-либо (длины, площади, объёма, массы) аддитивны: мера целого есть сумма мер частей.

Реально используемый способ

Количеством информации называется двоичный логарифм отношения размеров множеств \(B\) и \(A\).

Логарифм:

  • инъективен (по значению логарифма однозначно восстанавливается его вход)
  • преобразует произведения в суммы

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

Единицы измерения информации

При измерении информации последним из вышеописанных способов единица информации называется битом (сокращение от Binary digIT — если сообщения состоят из двоичных разрядов и несут одинаковое количество информации, то один двоичный разряд как раз несёт единицу информации).

Также используются следующие единицы:

  • байт (B) — обычно 8 бит
  • октет — 8 бит
  • килобит (Kbit) — 1000 бит или 1024 бита
  • кибибит (Kibit) — 1024 бита
  • килобайт (KB) — 1000 байт или 1024 байта
  • кибибайт (KiB) — 1024 байта
  • и аналогичные с приставками мега-, меби-, гига-, гиби-, и так далее

Отметим, что у приставки «мега» за историю развития вычислительной техники встречались все три возможных интерпретации:

  • \(1000\cdot 1000\) — наиболее распространена на данный момент
  • \(1024\cdot 1024\) — тоже часто используется
  • \(1024\cdot 1000\) — объём некоторых разновидностей гибких дисков (технология долговременного хранения информации, почти окончательно исчезнувшая в 2000-х годах) измерялся именно в таких мегабайтах

Кодировка чисел в памяти ЭВМ

Целые числа

К настоящему моменту почти любая ЭВМ использует память, подразделяющуюся на байты — восьмёрки бит. Каждый бит может принимать одно из двух значений (будем их обозначать 0 и 1). Соответственно, каждый байт может принимать одно из двухсот пятидесяти шести значений. Для записи этих значений обычно используют пары шестнадцатиричных цифр: 00, 01, 02, … ff.

Соответственно, для записи целых чисел в память ЭВМ обычно используют 256-ричную систему счисления. При этом различают несколько форматов записи. У каждого формата есть:

  • порядок цифр (байт): Little Endian (от младших цифр к старшим) и Big Endian (от старших цифр к младшим)
  • количество байт: обычно 1, 2, 4, 8 или 16
  • диапазон: «без знака» (от \(0\) до \(N-1\)) или «со знаком» (от \(-N/2\) до \(N/2 - 1\)), где \(N\) — общее количество комбинаций используемых байт

При этом для записи чисел диапазона «без знака» используется обычная 256-ричная система счисления, а числа диапазона «со знаком» записываются так же, как их остатки по модулю \(N\) в формате «без знака».

Например, в 2-байтовом LE-формате без знака число \(1234\) имеет вид d2 04.

А в 1-байтовом формате со знаком число \((-123)\) записывается так же, как и \(256-123=133\) без знака: 85.

Числа с плавающей точкой

Для записи рациональных чисел обычно используется формат с плавающей точкой. Устроен он так: все биты кода (который обычно имеет ширину 16 бит, 32 бита или же 64 бита) делятся на три части:

  • самый старший бит называется знаком
  • следующие несколько бит называются экспонентой (или степенью)
  • оставшиеся биты называются мантиссой (или значащей частью)

Для стандартных форматов используются следующие размеры экспонент:

  • 16 бит («половинная» точность) — 5-битная экспонента
  • 32 бита («одинарная» точность) — 8-битная экспонента
  • 64 бита («двойная» точность) — 11-битная экспонента

Знак задаёт луч, на котором находится число. Знак 0 — неотрицательные числа, знак 1 — неположительные.

Луч (будем все его точки обозначать расстоянием до нуля) разбивается на отрезки:

  • нулевой — от \(0\) до \(2^{-N}\) для некоторого \(N\)
  • первый — от \(2^{-N}\) до \(2^{-N+1}\)
  • каждый следующий получается из предыдущего умножением на два

При этом отрезок от \(1\) до \(2\) имеет номер вида \(01\ldots1\) (здесь 4, 7 или 10 единиц).

Экспонента (кроме экспоненты \(1\ldots 1\), которая зарезервирована) — (записанный двоично) номер такого отрезка. Числа с нулевой экспонентой называются денормализованными.

Далее каждый отрезок разбивается на одинаковые части (количеством, равным количеству всевозможных значений мантиссы). Мантисса — порядковый номер левого деления такой части.

Итого, если знак равен \(s\), экспонента равна \(e\) и отлична от крайних значений, мантисса равна \(m\), ширина экспоненты равна \(E\) бит, а ширина мантиссы равна \(M\), то эти данные кодируют число

\[ (-1)^s \cdot 2^{1 + e - 2^{E-1}} \cdot (1 + m\cdot 2^{-M}) \]

В конце концов биты разбиваются на байты и записываются в LE- или BE-порядке.

Пример

Чтобы закодировать число \((-23.75\) в LE-формат половинной точности, проведём следующие действия.

Знак равен 1 (т.к. число отрицательное).

Подберём экспоненту:

  • 01111 соответствует отрезку от 1 до 2
  • 10000 соответствует отрезку от 2 до 4
  • 10001 соответствует отрезку от 4 до 8
  • 10010 соответствует отрезку от 8 до 16
  • 10011 соответствует отрезку от 16 до 32

Последний отрезок нам и нужен.

Теперь будем определять мантиссу:

  • мантиссы с началом 0 кодируют числа отрезка от 16 до 24
  • мантиссы с началом 01 кодируют числа отрезка от 20 до 24
  • мантиссы с началом 011 кодируют числа отрезка от 22 до 24
  • мантиссы с началом 0111 кодируют числа отрезка от 23 до 24
  • мантиссы с началом 01111 кодируют числа отрезка от 23.5 до 24
  • мантиссы с началом 011111 кодируют числа отрезка от 23.75 до 24

Нам как раз нужно начальное число последнего отрезка. Поэтому наша мантисса имеет вид 0111110000.

Итого биты нашего числа: 1 10011 0111110000. Их 256-ричная запись: cd f0.

Осталось записать эти два байта в формате LE: f0 cd.

Кодировка текстов в памяти ЭВМ

Договоримся, что текстом называется последовательность букв — элементов некоторого множества \(A\), называемого алфавитом.

Стандарт ASCII

American Standard Code for Information Interchange (коротко ASCII) — стандартизированное соответствие между 128-символьным алфавитом и целыми числами от 0 до 127 (называемыми кодами соответствующих букв).

Полезно знать следующие особенности ASCII:

  • Первые 32 символа — «управляющие»; к ним относятся, например, «переход на новую строчку», «возврат каретки», «колокольчик» и прочее подобное
  • Цифры от 0 до 9 имеют последовательные коды (от 48 до 57)
  • Буквы латинского алфавита имеют последовательные коды; коды заглавных букв на 32 меньше кодов аналогичных маленьких букв

Кодировки ASCII

Вообще для (равномерной) кодировки текста, состоящего из ASCII-символов, достаточно 7 бит на букву. Тем не менее, поскольку сейчас повсеместно в байте 8 бит, то для кодировки одной ASCII-буквы используются все 8 бит. При этом обычно старший бит оставляют равным 0.

Есть два наиболее употребимых способа использовать старший бит:

  • при использовании какого-нибудь расширения кодировки ASCII единичный старший бит означает, что данный символ не из ASCII, а из дополнительной части алфавита
  • как контрольный (например, бит чётности); впрочем, сейчас такое почти не встречается

Ещё с кодировками ASCII связано название кнопки клавиатуры Ctrl: исторически нажатие на эту кнопку обнуляло 4 старших бита кода одновременно нажатой цифро-буквенной клавиши, предоставляя таким образом доступ к «управляющим» (ConTRoL) символам.

Исторические кодировки для русского языка

Сейчас всё ещё можно изредка встретить три 8-битных расширения ASCII, используемых для кодировки русских текстов:

  • CP866 (оно же dos)
  • CP1251 (оно же win)
  • KOI8-R

Первая кодировка (CP866) малопримечательна и устроена весьма непривычно: например, коды заглавных русских букв от кодов маленьких отличаются совсем не на 32, да и идут русские буквы не подряд.

Дополнительная часть второй кодировки (CP1251) устроена аналогично ASCII: русские буквы идут подряд, а коды заглавных и строчных букв отличаются на 32, кроме буквы ё, которая стоит особняком (в русском алфавите 33 бувы, и одной пришлось пожертвовать).

Кодировка KOI8-R наиболее интересно устроена: в ней русские буквы расположены так, что при обнулении старшего бита у всех букв текст сохраняет читаемость (при вычитании 128 из кода русской буквы получается код похожего по написанию символа ASCII).

Стандарт Unicode

Сейчас Unicode — это фактически общепринятый стандарт, определяющий понятие буквы (в терминах самого Unicode буквы именуются кодовыми точками).

Кодовые точки нумеруются числами от \(0\) до \(2^{20}+2^{16}-1\) за исключением диапазона от \(D800_{16}\) до \(DFFF_{16}\), который для нумерации кодовых точек не используется.

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

UTF-32

Семейство UTF-32 состоит из двух кодировок:

  • в кодировке UTF-32-LE каждая кодовая точка записывается 256-ричным представлением своего номера с LE-порядком байт (от младших к старшим)
  • в кодировке UTF-32-BE каждая кодовая точка записывается 256-ричным представлением своего номера с BE-порядком байт (от старших к младшим)

Иногда текстовые данные в одной из этих кодировках сопровождаются меткой порядка байт в качестве первой буквы текста. Метка порядка байт имеет номер \(FEFF_{16}\). То есть, если текст начинается с байт

FF FE 00 00

то это означает, что используется кодировка UTF-32-LE.

Если же текст начинается с байт

00 00 FE FF

то это означает использование UTF-32-BE.

UTF-8

Наиболее распространённой в интернете сейчас является кодировка UTF-8. Она работает так:

  • первым делом определяется наименьшее количество бит, нужное для записи номера кодовой точки
  • далее выбирается самое короткое подходящее представление из списка ниже

Список представлений:

  • 0??????? (1 байт для кодовых слов длины не более 7 бит)
  • 110????? 10?????? (2 байта для кодовых слов длин от 8 бит до 11 бит)
  • 1110???? 10?????? 10?????? (3 байта для кодовых слов длин от 12 бит до 16 бит)
  • 11110??? 10?????? 10?????? 10?????? (4 байта для кодовых слов длин от 17 бит до 21 бита)

Биты кодовой точки дополняются слева нулями до нужно длины, после чего вписываются вместо ?.

Для примера покажем, как закодировать метку порядка байт (хотя в UTF-8 она смысла не имеет). У неё номер равен

\[ FEFF_{16} = 1111\,1110\,1111\,1111_{2} \]

В нём 16 бит, поэтому нужно использовать третье представление:

FEFF -> 1111 1110 1111 1111
       /   / |  | |  |  \  \
      /   /  |  | |   \ |  |
     /   /   /  | /    \|  |
    /   /   /   //     ||  |
    1111    111011    111111
1110????  10??????  10??????

11101111  10111011  10111111
E   F     B   B     B   F

Итого мы получили байты EF BB BF (именно в таком порядке!).

UTF-16

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

Этих кодировок, как и UTF-32, две штуки: с LE и BE порядками байт.

При этом для кодировки кодовой точки используется либо одна двухбайтовая кодовая единица, либо две двухбайтовых кодовых единицы. При этом порядок байт относится только к кодовым единицам. Сами кодовые единицы (если их две штуки) всегда идут в порядке «начальная, а затем — конечная».

Кодовые точки с номерами, не превышающими \(FFFF_{16}\), записываются одной кодовой единицей, совпадающей с номером.

Кодовые точки с номерами, большими \(FFFF_{16}\), записываются так:

  • из номера вычитается \(2^{16}\)
  • оставшиеся не более чем 20 бит номера дополняются слева ведущими нулям и вписываются в нижеприведённую схему
начальная кодовая единица  |  конечная кодовая единица
110110??  ????????         |  110111??  ????????

Далее каждая кодовая единица записывается с нужным порядком байт (но, ещё раз повторим, сами кодовые единицы записываются в порядке от начальной к конечной).

Программирование