Примеры минимизации булевой функции с большим числом переменных

[Mishel 825]

Доброго времени суток!

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

[mike-y-k]

А поиск? Есть даже онлайн ресурсы. "минимизация булевых функций онлайн"

[Mishel 825]

От 9 переменных поиск результатов не даёт. На 8 переменных есть примеры функций для минимизации, очевидно штучно подобраны, для карти Карно.

Минимизация функций онлайн только до 6 переменных, включительно.

[Mishel 825]

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

[mike-y-k]

Mishel 825, тут уже от реализации алгоритма сильно зависит. Встречаемые варианты работали до 6 переменных. Дальше был тихий ужас.
Алгоритмы на методах Куайна и Куайна-МакКласки тут эффективнее.
И алогоритм Espresso в его реализациях кушает до 40 переменных. Кстати вроде на его основе работают оптимизаторы и валидаторы для программируемой логики. И оптимизаторы в системах проектирования микросхем. Хотя чаще там сразу несколько методов задействованы с выбором оптимума из результатов.

PS По ссылкам на статьи внизу есть ссылки на реализации в разных вариантах. Можно их проверить и выбрать оптимальный(е)/лучший(е)/…

PPS Тут сильная зависимость от Ваших задач и критериев оценки результата. В такой ситуации только показать векторы движения получится…

[ProtAS-13]

Необходимо исходное выражение булевой функции и её минимальная форма.

Делал как-то для себя по Квайн+Петрик (см. екзешник во вложении).
Программу ограничил 8 переменными, хотя, как я помню, реализация позволяет и большее число переменных, но сейчас исходники искать надо, да и заново все вспоминать
Програмка, конечно сыровата - нет прогресс-бара (для малого количества переменных, было не нужно), очистка результатов отдельно не выведена (делается через смену количества переменных), может быть еще какие неудобства, сейчас уже и не вспомню.
Главное считает правильно, а когда получил результат, то и забил на всякие рюшечки.
Попробуйте, может пригодиться.
Кстати, делал по книжице: "Шевелев Ю.П. Дискретная математика. Ч.1. Теория множеств. Булева алгебра (2003)".
Если будете тестировать, то отпишитесь - чисто для статистики - не ошибся ли где в реализации алгоритма.

[mike-y-k]

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

[Mishel 825]

Спасибо поддерживающим тему.
mike-y-k, хорошая информация, ищу примеры для тестирования.

ProtAS-13, протестировал на 4, 5, 6 и 8 переменных. Програма выдала правильный результат. Приложил функции для тестирования и результаты тестирования. Не везде отображается инверсия, что затрудняет ориентацию.

[Bill]

Доброго времени суток!

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

Цель какая?

[mike-y-k]

Bill, а цель из названия и первого топика? Очень востребованно в семействе разнообразных программируемых логических… Оптимизация, однако. Руками написанное/нарисованное не всегда минимально получается и не лезет в имеющееся железо. Собственные средства в пакетах разработки тоже не всегда устраивают или отсутствуют из-за стоимости.