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

Функция алгебры логики (ФАЛ), или булева функция, — это отображение \(f: B^n \to B\), где \(B=\{0,1\}\). Множество \(B^n\) всех двоичных наборов длины n называют единичным кубом или n-мерным булевым гиперкубом. Значения переменных задают координаты его вершин, а функция помечает каждую вершину числом 0 или 1.1

Геометрический язык позволяет описывать наборы, слои, соседство, грани и множество единиц \(N_f\). Он особенно удобен потому, что элементарным конъюнкциям соответствуют грани куба, а представления функции через ДНФ затем можно рассматривать как покрытия множества \(N_f\) такими гранями.1

Что важно запомнить
  • \(B^n=\{0,1\}^n\) — множество всех \(2^n\) двоичных наборов длины n.
  • i-й слой куба состоит из наборов с ровно i единицами.
  • Два набора соседние, если отличаются ровно в одной координате.
  • Грань получают фиксацией части координат в 0 или 1. Остальные координаты остаются свободными.
  • \(N_f\) — множество вершин, на которых \(f=1\).1

Функция алгебры логики

Пусть \(B=\{0,1\}\). Функция алгебры логики от n переменных отображает каждый набор \(\alpha = (\alpha_{1},\ldots,\alpha_n)\) из \(B^n\) в одно из двух значений, 0 или 1. Её можно задать таблицей истинности. Эквивалентное представление — характеристическое множество \(N_f\), состоящее из всех наборов \(\alpha\), для которых \(f(\alpha)=1\).1

Единичный куб

Множество \(B^n\) удобно рассматривать как множество вершин n-мерного куба. Вес набора равен числу единиц в нём. Вершины одинакового веса образуют слой \(B_i^n\). Расстояние Хэмминга между двумя наборами — число координат, в которых они различаются. При расстоянии 1 вершины называют соседними.1

На \(B^n\) также используют покоординатный частичный порядок: \(\alpha \le \beta\), если \(\alpha_i \le \beta_i\) для каждой координаты. Он особенно важен при изучении монотонных булевых функций.

Грани куба

Грань можно задать словом \(\gamma\) из символов 0, 1 и 2. Символ 0 или 1 фиксирует соответствующую координату, а 2 означает свободную координату. Если зафиксировано r координат, грань имеет ранг r и размерность \(n-r\). В ней находится \(2^{n-r}\) вершин.1

Элементарная конъюнкция из r литералов является характеристической функцией грани ранга r. Поэтому алгебраические выражения получают наглядный геометрический смысл. Если конъюнкция равна 1 на некоторой грани, то эта грань соответствует множеству наборов, удовлетворяющих конъюнкции. В дальнейшем ДНФ можно понимать как объединение нескольких таких граней, покрывающих \(N_f\).1

Пример простыми словами

В кубе \(B^3\) условие \(x_{1}=1\) задаёт грань из четырёх вершин: (100), (101), (110), (111). Если дополнительно зафиксировать \(x_{3}=0\), получим грань \(x_{1}\cdot \neg x_{3}\) из двух вершин: (100) и (110). Чем больше координат зафиксировано, тем выше ранг грани и тем меньше её размерность.

Частые ошибки
  • Путать слой и грань. Слой задаётся числом единиц, а грань — фиксацией конкретных координат.
  • Путать ранг и размерность грани. В принятой в курсе терминологии их сумма равна n.
  • Считать формулу и ФАЛ одним объектом. Разные формулы могут задавать одну и ту же функцию.

Другие вопросы

Источники

  1. 1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 1, §2, МГУ, факультет ВМК