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

"такие простыни" Представьте, какая была бы простынь, если бы ТС предложил минимизировать функцию
f = x0 \/ x1 \/ . . . \/ x31, заданную таблицей истинности.

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

"Это - форум программистов". Да, все программисты сталкиваются с условиями ветвления или повторения, а это и есть булевы функции.
Но некоторые программисты могут участвовать в проектах, в которых требуются свои критерии оптимизации.

"В топике нас не будет интересовать человеческое восприятие". Наверно поэтому тема не нашла широкого отклика.

"В своей реализации я хотел уйти от битов. И просто перейти к использованию списков символов".
Хочу список символов - это каприз мальчика в магазине игрушек или слова мужа, понимающего триаду Вирта: структура данных-алгоритм-программа?

"Игры с кубитами или с иммитацией символа asterisk "*" кажутся мне не очень актуальными применительно
к решению задачи которая в пределе двигается к экспоненциальной".

asterisk выглядит так "*" с этой стороны экрана, а с другой стороны этого же экрана он выглядит так "00101010". Что изменится, если с той стороны экрана он будет выглядеть, например, так "11"?

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

"Памяти у нас сегодня достаточно чтоб не обращать внимание на биты". Не только на биты, но и на байты, и на качество программ, и на многое другое.

22411318 . Это применение драчёвого напильника после драчёвого напильника? Что подтверждается вашими последующими сообщениями. Обычно после драчёвого напильника применяют бархатный напильник
(https://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%BF%D0%B8%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA).
Правильный ответ ( 22410649 ): x¬y \/ ¬z или в вашей нотации: X~Y + ~Z.
Как я уже писал, все основные результаты в области представления булевых функций и их минимизации были получены 50-х - 70-х годах прошлого столетия.

Для реализации функций y1, y2, ..., y16, если бы это была реальная задача, я бы сначала применил декомпозицию. "Дешифровал" бы три старших разряда. После этого остались бы минимизировать логические функции от 5 переменных.
Вопросы совместной реализации системы булевых функций хорошо рассмотрены в книгах Баранова С.И., в частности в книге
Баранов С.И., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. — М.: Радио и связь, 1986. — 272 с.

"К чорту Карно". Карно или Квайн? Если ли между ними принципиальное отличие?

Еще раз рассмотрим функцию 1 из предыдущего обсуждения

x y z f1
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

Запишем не меняя порядок следования первые четыре значения этой функции горизонтально, а под ними в следующей строке запишем остальные значения этой функции. Строки и столбцы полученной матрицы отметим черточками там, где независимые переменные равны 1. Полученное приведено на рис.1, которое назовем просто картой.

На рис.2 рассмотрим две единички, которые отмечены красным цветом: ¬x¬yz \/ x¬yz = ¬yz, т.е. отмеченные красным цветом конституенты склеиваются по переменной x.
На рис.3 рассмотрим две единички, которые отмечены красным цветом: x¬y¬z \/ x¬yz = x¬y, т.е. отмеченные красным цветом конституенты склеиваются по переменной z.
Следовательно, для минимизации нужно найти единички, которые образуют прямоугольник и записать независимые переменные, общие для всех единичек в прямоугольнике.
Теперь рассмотрим две единички, отмеченные на рисунке 4 красным цветом. Они не находятся рядом, поэтому их нельзя обвести прямоугольником. Но они склеиваются по переменной y. Вейч, а затем Карно предложили переставить столбцы местами, как показано на рис.5. Теперь, если полученную карту обернуть вокруг цилиндра, то крайние столбцы будут находиться рядом и можно будет выделить прямоугольник. Карту рис.5 называют картой Карно.

Карту на рис.1 легко заполнять, но сложно искать импликанты. Карту на рис.5 сложно заполнять, но легко искать импликанты.

Выводы: 1) карта Карно это та же таблица истинности; 2) и алгоритм Квайна, и карты Карно основаны на использовании операции склеивания 22406820 .

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

Почему я рассматриваю СДНФ, а не СКНФ? СДНФ: x¬yz \/ y¬z, СКНФ: (x \/ ¬y \/ z)(y \/ ¬z). Это не одна и та же функция, просто показал, что запись СКНФ более громоздкая при одном и том же количестве переменных и операций по сравнению с СДНФ.

Я предложил два варианта представления СДНФ для программной реализации алгоритма Квайна ( 22410652 ).

1-й вариант (далее псевдокод, не путать с языком программирования):

Для хранения БулевоЗначение, скорее всего, будет выделен 1 байт. Т.е. один байт будет хранить всего три возможных значения. Всего потребуется (n+1)(2^n) = 16*(2^15) байт

Поэтому был предложен второй вариант с упаковкой булевых переменных в целое число:

type Функция = array 1 .. 2^n of integer;

В этом случае потребуется 4*(2^n) = 4*(2^15) байт, что в четыре раза меньше, чем в первом варианте.

Для представления одной переменной потребуется два бита:
1 0 - биты числа
0 0 - представляют ¬х1
0 1 - представляют х1
1 * - представляют склейку по переменной х1, в этом контексте знак * обозначает, что значение бита может быть любым и не имеет значения.

Я предлагаю следующий способ сравнения двух наборов на предмет склейки.

Доопределим * единицей, т.е. 1* -> 11.
Сопоставим логические значения с числами: 00(ложь) <-> 0, 01(истина) <-> 1, 1*(склейка) = 11 <-> 3.
Введем функцию Lk(Xik, Xjk) = |Xik - Xjk| - 1, где Xik и Xjk значения в "разряде" k i-го и j-го наборов:

Два набора склеиваются, если после сравнения всех "разрядов" встретилось только одно L=0 и не было ни одного L>0.
Если учесть возможности сокращения числа переборов, о которых я написал ранее, то можно получить сумму всех L.
Если она равна -(n-1), то сравниваемые наборы склеиваются.
Использование типа integer для хранения одного набора решает задачу отметки этого набора путем присвоения знака - этому числу.

Т.е. мы свели логические операции к арифметическим. Это применимо к обоим предложенным вариантам представления СДНФ.

В качестве упражнения можно рассмотреть чисто логическое решение для сравнения двух наборов.

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

Если хочется работать с символами, то можно предложить следующие варианты.


В этом случае функция Lk будет такой: Lk(Xik, Xjk) = |ord(Xik) - ord(Xjk)| - 1.


Еще один вариант - это использование массива строк:

type Функция = array 1 .. 2^n of string[n+1];

Для обозначения истинности можно использовать высоту букв, например, ¬xy¬z можно записать строкой xYz.
Тогда таблица, описывающая функцию Lk, будет выглядеть так:


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

На этом программирование алгоритма Квайна считаю законченным, поскольку все основные моменты программной реализации этого алгоритма были рассмотрены.

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


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