Алгебра в коммутации или минимизация.

Булева алгебра

Булева алгебра — это непустое множество A с бинарными операциями ∧ (И), ∨ (ИЛИ), унарной операцией ¬ (НЕ) и двумя выделенными элементами: 0 (Ложь) и 1 (Истина). Она используется для анализа и упрощения логических выражений.

Карта Карно

Карта Карно — графический метод минимизации булевых функций. Это таблица, где соседние ячейки отличаются значением только одной переменной, что позволяет визуально группировать их, применяя законы булевой алгебры, например, поглощения: a ∧ (a ∨ b) = a.
Пример упрощения, используя законы булевой алгебры:
(a ∨ ¬b) ∧ (a ∨ b) =
=(a ∧ a) ∨ (a ∧ b) ∨ (¬b ∧ a) ∨ (¬b ∧ b)=
= a ∨ ab ∨ a¬b ∨ 0=
= a(1 ∨ b ∨ ¬b) = a ∨ ab = a

Отличие от таблицы истинности: Карта Карно представляет значения функции в двумерном виде, что облегчает поиск групп для упрощения.

Таб.1 Таблица Истинности (а): Карта Карно (б).

Таблица истинности – это табличное представление логической функции, где перечислены все возможные комбинации входных переменных и соответствующие им значения выходной переменной. В таблице истинности, как правило, пишется по порядку (вертикально) от Нуля (0) до 2^n-1, где n число переменных.

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

• Дизъюнктивная нормальная форма (ДНФ) — дизъюнкция (ИЛИ) конъюнкций (И) литералов.
  Пример: (X1 ∧ ¬X2 ∧ ¬X3) ∨ (¬X1 ∧ X2 ∧ ¬X3) ∨ (¬X1 ∧ X2 ∧ X3).
  Минтерм – это конъюнкция (И) всех входных переменных (каждая переменная либо в прямом, либо в инверсном виде), дающая значение "ИСТИНА" только для одной комбинации входных значений.

Схему 1. Дизъюнктивная нормальная форма

Схема 1 может быть представлена как:

(X1 ∧ ¬X2 ∧ ¬X3) ∨ (¬X1 ∧ X2 ∧ ¬X3) ∨ (¬X1 ∧ X2 ∧ X3)

(X1׬X2׬X3)+(¬X1×X2׬X3)+(¬X1×X2×X3)

• Конъюнктивная нормальная форма (КНФ) — конъюнкция (И) дизъюнкций (ИЛИ) литералов.
  Пример: (X1 ∨ ¬X2 ∨ ¬X3) ∧ (¬X1 ∨ X2 ∨ X3) ∧ (¬X1 ∨ ¬X2 ∨ X3).
  Макстерм – это дизъюнкция (ИЛИ) всех входных переменных (каждая переменная либо в прямом, либо в инверсном виде), дающая значение "ЛОЖЬ" только для одной комбинации входных значений.

Схема 2. Конъюнктивная нормальная форма

Схема 2 может быть представлена как:

(X1 ∨ ¬X2 ∨ ¬X3) ∧ (¬X1 ∨ X2 ∨ X3) ∧ (¬X1 ∨ ¬X2 ∨ X3)

(X1+¬X2+¬X3)×(¬X1+X2+X3)×(¬X1+¬X2+X3)

Построение Карты Карно.
Для правильного расположения переменных используется код Грея (Gray code), где соседние комбинации отличаются только одним битом.

Ключевая черта кода Грея: расстояние Хэмминга (dH)​ между любыми двумя соседними комбинациями равно единице: dH​(Gi​,Gi+1​)=1, где Gi​ — i-я кодовая комбинация в коде Грея.
Это свойство делает его циклическим кодом с единичным расстоянием. Частный случай, где первая и последняя комбинации также отличаются на один бит, называется циклическим кодом Грея.

Таб. 2. Код Грея и запись его для Карты Карно.

Код Грея заполняется, для примера см. Таб. 2. а). :
для одной переменной
первый ряд заполняется как X1 = 0,1(см. Таб. 2. б, в);
для двух переменных
первый ряд заполняется как X1 = 0,1,1,0 (зеркально отображение первого ряда для одной переменной (0,1→1,0). Второй ряд (X2) - первая половина заполняется -0, а вторая -1
для трех переменных
первой и второй ряд (X1, X2) заполняется зеркально. Третий ряд (X3) первая половина заполняется -0, а вторая половина -1
Смотрите Таб. 2. б), в), г) - расположения переменных Xn не имеет значения.

Таб.3. Таблица истенности (а) и Карта Карно (б, в, г).

В табличном расположении переменных Xn, не важно (См. Таб. 3. б) Карта Карно - X1_X2X3; в) Карта Карно - X1X2_X3; г) Карта Карно - X1X2X3.)

Поглощение переменной

Закон поглощения переменной — закон алгебры логики (булевой алгебры), который упрощает логические выражения за счёт устранения избыточности. Существует два фундаментальных тождества, которые упрощают выражения с использованием «поглощающих» терминов:
Закон поглощения 1:
Формула:
a+(ab) = a.
a ∨ (a ∧ b) = a

Схема 3. Поглощение контакта a+(ab)

Закон поглощения 2:
Формула:
a×(a+c) = a.
a ∧ (a ∨ c) = a

Схема 4. Поглощение контакта a×(a+c)

Любая другая комбинация положение контактов сводится к одному из двух этих законов

Закон поглощения 3:
Формула:
(a+b)×(¬a+b) = b.
(a ∨ b) ∧ (¬a ∨ b) = b

Схема 5. Поглощение контакта (a+b)×(¬a+b)

Закон поглощение 4:
Формула:
(a×d)+(¬a×d) = d
a ∧ d) ∨ (¬a ∧ d) = d

Схема 6. Поглощение контакта (a×d)+(¬a×d)

Минимизация с помощью Карты Карно

Процесс минимизации:

Минимизация с помощью карты Карно:

1. Постройте карту по таблице истинности.
2. Сгруппируйте прямоугольные области из соседних ячеек, содержащих 1 (для ДНФ) или 0 (для КНФ). Размер группы должен быть степенью двойки (1, 2, 4, 8...).
3. Для ДНФ (по единицам): каждая группа даёт конъюнкцию переменных, не меняющих своё значение в группе. Конъюнкции объединяются дизъюнкцией.
4. Для КНФ (по нулям): каждая группа даёт дизъюнкцию переменных, не меняющих своё значение в группе. Дизъюнкции объединяются конъюнкцией.

Пример минимизации (см. ниже Рис. 2, 3):

Внимание:

Ниже рассматривается внешнее воздействие на контакты. В Таблице Истинности записаны внешние команды, а не их состояние контактов. Контакты на чертеже чертятся в состоянии нормального положения (нет никакого воздействия на контакт).

Рис. 1. Состояние механизма управления на примерах а) Кнопка, б) Реле. Где "0" - нет воздвействия; "1" - подана "команда".

Минимизация по ДНФ (См. Рис. 2). Группируем единицы. Если в группе переменная принимает и 0, и 1, она исключается.

Осуществляется по единицам (для получения дизъюнктивной нормальной формы-ДНФ (См. Рис. 2. б)). Объединяем в прямоугольную форму единицы и получим терму - клетку -"00" А-1 и клетку "10" Б-1.
Тут видно, что X1 пропадает ( клетка А-X1 имеет значение ноль (0), а клетка Б-X1 значение единица (1)) и останется только переменная X2 - клетка X2-1 равная ноль (0) - см. Рис. 2.б), в). В соответствии таблицы Рис. 2. в) можем нарисовать минимизированную схему - Рис. 2. е) . Состояние контакта смотреть на рис. 1. (Когда нет никого воздействие на контакт - состояние контакта нормально замкнут (1))

Рис. 2. а) Таблица истинности; б) Карта Карно; в) Минимизация; г) Электрическая схема по таблице истиности ДНФ; д) Электрическая схема по таблице истиности КНФ; е) Электрическая схема по таблице минимизации.

Минимизация по КНФ (См. Рис. 3). Группируем нули. Если в группе переменная принимает и 0, и 1, она исключается.

Осуществляется по нулям (для получения конъюнктивная нормальная форма-КНФ (См. Рис. 3. б)). Объединяем в прямоугольную форму нули и получим терму - клетку -"01" А-2 и клетку "11" Б-2.
Тут видно, что X1 склеится ( клетка А-X1 имеет значение ноль (0), а клетка Б-X1 значение единица (1)) и останется только переменная X2 - клетка X2-2 равная единица (1) - см. Рис. 3.б), в). В соответствии таблицы Рис. 3. в) можем нарисовать минимизированную схему - Рис. 4. е) . Состояние контакта смотреть на рис. 1. (когда нет никого воздействие на контакт - состояние контакта нормально замкнут (1) про воздействии на контакт - разрыв).

Рис. 3 а) Таблица истинности; б) Карта Карно; в) Минимизация; г) Электрическая схема по таблице истинности ДНФ; д) Электрическая схема по таблице истинности КНФ; е) Электрическая схема по таблице минимизации.

Изменим значения в Таблице Истинности согласно Рис.4.1 и Рис.4.2 и заполним Карту Карно.
ДНФ.
Выделяем две прямоугольный области для дизъюнктивной нормальной формы (Рис.4.1).
Столбец 1 - склейка X1 (А-X1 = 0; Б-X1 = 1) и сохранить переменную X2=0;
Стока А - склейка X2 (1-X2 = 0; 2-X2 = 1) и сохранить переменную X1=0.
или X1+X2

Рис. 4.1 а) Таблица истинности; б) Карта Карно; в) Минимизация; г) Электрическая схема по таблице истинности ДНФ; д) Электрическая схема после минимизации.

КНФ.
Выделяем одну прямоугольную область для конъюнктивной нормальной формы (Рис.4.2).
сохраняется переменная X1=1 (Б-1)
сохраняется переменная X2=1 (А-2)

Рис. 4.2 а) Таблица истинности; б) Карта Карно; в) Минимизация; г) Электрическая схема по таблице истинности КНФ; д) Электрическая схема после минимизации

Схемы сборки контактов (ДНФ и КНФ)

Для построение схемы необходимо определить как будет собрана схема по ДНФ или по КНФ. Допустим есть некая таблица из четырех переменных (см. Таблицу на Схеме 7. а).).
Схема контактов по сборке ДНФ.
Контакты в каждой конъюнкции соединяются последовательно, группы конъюнкций — параллельно. Отсутствующая переменная — перемычка. (см. Схема 7. б). X2-2).
Схема контактов по сборке КНФ.
Контакты в каждой дизъюнкции соединяются параллельно, группы дизъюнкций — последовательно. Отсутствующая переменная — разрыв. (см. Схема 7. в). X2-2).

Схема. 7. а) Таблица положения систем управления; б) Схема сборки контактов по ДНФ; в)Схема сборки по КНФ. Примечание: - обратите внимание на положение контактов при одной и тоже таблицы.

При больших переменных Xn необходимо рассматривать оси симметрия. Рассмотрим Карту Карно шести переменных и составим матрицу значений функций 8х8 и разделим по вертикали на оси - юля:
а, б ,в, г, д, е, ж, з.
и по горизонтали оси - таня:
0, I, II, III, IV, V, VI, VII, VIII.
Вертикальные оси контролирует поля колонок (Рис. 5):
Ось "б" контролирует колонки "А" - "Б" (Смотреть строку 0);
Ось "в" контролирует колонки "Б" - "В" и "А" - "Г" (Смотреть строку 1);
Ось "г" контролирует колонки "В" - "Г" (Смотреть строку 2);
Ось "д" контролирует колонки "А" - "З", "Б" - "Ж", "В" - "Е" и "Г" - "Д" (Смотреть строку 3);
Ось "е" контролирует колонки "Д" - "Е" (Смотреть строку 4);
Ось "ж" контролирует колонки "Д" - "З" и "Е" - "Ж"(Смотреть строку 5);
Ось "з" контролирует колонки "Ж" - "З"(Смотреть строку 6).

Рис. 5. Контроль столбцов отностельно линий осей юли. Коптроль соблюдается четко по середине относительно юли (смотрет штрифовку) и по всей колонке.

Приведем пример и сгруппируем единици только по горизонтали Рис. 6.

Рис. 6. Пример контроля столдцов отностельно линий вертикальных осей юли.

Ряд "0"
- Объединение столбцов "А" и "Б" (симметрия по оси "б");
Ряд "1"
- Объединение столбцов "А" и "Г" (симметрия по оси "в");
Ряд "2"
- Нет объединения (нет осей симметрии);
Ряд "3"
- Объединение столбцов "В" и "Г" (симметрия по оси "г") Внимательно - Ось г на контролирует колонки "А" и "Е";
- Объединение столбцов "А" и "Г" (симметрия по оси "в");
- Объединение столбцов "В" и "Е" (симметрия по оси "д");
Ряд "4"
- Объединение столбцов "В" и "Е" (симметрия по оси "д");
- Единица ячейка 4-А не имеет симметрии с другими единицами ряда 4 (Ось "г" не контролирует колонки "А" и "Е");
Ряд "5"
- Объединение столбцов "А" и "З" (симметрия по оси "д");
Ряд "6"
- Объединение столбцов "А" и "Д" (симметрия по оси "б");
- Объединение столбцов "А" и "Г" (симметрия по оси "в");
- Объединение столбцов "А" и "З" (симметрия по оси "д");

Горизонтальные оси контролируют поля строк:
Ось "I" контролирует колонки "0" - "1";
Ось "II" контролирует колонки "0" - "3" и "1" - "2";
Ось "III" контролирует колонки "2" - "3";
Ось "IV" контролирует колонки "0" - "7", "1" - "6", "2" - "5" и "3" - "4"
Ось "V" контролирует колонки "4" - "5";
Ось "VI" контролирует колонки "4" - "7" и "5" - "6";
Ось "VII" контролирует колонки "6" - "7".

Рис. 7. Контроль столбцов отностельно линий горезонтальних осей тани. Коптроль соблюдается четко по середине относительно тани (смотрет штрифовку) и по всем строкам.

Приведем пример и сгруппируем только по вертикали (Набор единиц аналог Рис 6.)

Рис. 8. Пример контроля столдцов отностельно линий вертикальных осей тани.

Столбец "А"
- Объединение строк "0" и "1" (симметрия по оси "I");
- Объединение строк "0" и "3" (симметрия по оси "II");
- Объединение строк "1" и "5" (симметрия по оси "IV");
- Объединение строк "5" и "6" (симметрия по оси "VI");
Столбец "Б"
- Нет не одного объединения
Столбец "В"
- Объединение строк "3" и "4" (симметрия по оси "IV");
Столбец "Г"
- Объединение строк "1" и "2" (симметрия по оси "II");
- Объединение строк "2" и "3" (симметрия по оси "III");
Столбец "Е"
- Объединение строк "3" и "4" (симметрия по оси "IV");
Столбец "З"
- Объединение строк "5" и "6" (симметрия по оси "VI").

Выше писалось

Склеивать можно только прямоугольные области с числом единиц (нулей), являющимся целой степенью двойки (1, 2, 4, 8, 16, 32… клетки).

Но это не так (См. Рис 9), при объединении единиц или нулей необходимо следить за осями юля и таня.

Рис. 9. Попытка объеденить число едениц в прямоугольник 2х4.

В действительности, матрицу на Рис. 9 следует разбить на три отдельные группы (как показано на Рис. 10), чтобы правильно учесть структуру Карты Карно и прилегающие области.

Рис. 10. Объеденить число едениц.

Таблица Истинности и Карта Карно.

При сравнении таблицы истинности и карты Карно становится очевидно, что это взаимосвязанные представления. Таблица истинности, при знании правил склейки и булевой алгебры, может быть использована для минимизации логических выражений напрямую, без обязательного перехода к карте Карно. (См. Рис 11 и 12)

Рис. 11. а) Контроль ячеек для склейки в Карте Карно; б) Контроль ячеек для склейки в Таблице Истинности.

Рис. 11 показывает, как процесс склейки (объединения) может быть визуализирован как в карте Карно (а), так и в таблице истинности (б), при этом используются одни и те же логические принципы (Сравните с Рис 7).

Рис. 12 демонстрирует, что можно выполнить минимизацию, используя Таблицу Истинности напрямую (а, д, е), без обязательного преобразования в карту Карно (б, в, г). Перестановка строк в таблице истинности (д) может помочь визуально идентифицировать группы для склейки (е).

Рис. 12. Минимизация: а) Таблица Истинности; б) Карта Карно X1-X2X3; в) Карта Карно X1X2-X3; г) Карта Карно X1X2X3. д) Таблица Истинности а) записанной в ином порядке; е) Склейка через Таблицу Истинности.