Блог пользователя Gerald

Задача Минимизации логического выражения
Автор Gerald, 14 лет назад, По-русски
Как то раз, на одном TCM контестов (или что-то в этом роде), встречалась следующая задача: Дано логическое выражение с переменными, нужно его так преобразовать, чтобы получить минимальное по длине эквивалентное ему выражение. Хотелось бы узнать как решать подобную задачу? Может кто-нибудь знает статьи или классические алгоритмы решения такой задачи?
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Какие ограничения у задачи?
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я в точности уже не помню, но вроде длина выражения до 100-300 символов, а переменные могут быть от 'a' до 'z'.
→ Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
На Яндекс-Опене, если не ошибаюсь, была такая задача:
Дано логическое выражение с А, Б, С, построить минимальное по длине эквивалентное ему. Она решалась любым алгоритмом нахождения кратчайшего пути: Изначально забивалось, что выражения А,Б,С, являющиеся истинными для таких-то наборов А,Б и С, являются минимальными, потом каждый раз из очереи доставалось минимальное по длине выражение, и его надо было скрестить с другим выражением/записать его отрицание.
Таким образом там минимизировались все логические выражения для любой таблицы истинности. Других таких задач ТСМ не помню. Если переменных гораздо больше, то там и как найти, при каких наборах значений выражение истинно нельзя за нормальное время, мне кажется. ( Ведь нужен перебор 2^(2^N) - все подмножества всех возможных наборов значений переменных)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    На SGU подобная задача №182.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    вполне возможно что это та самая задача, просто я не очень хорошо помню ограничения, Спасибо.
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Упомянутая задача с TCM обсуждается здесь.

Задачи минимизации логических выражений можно ставить по-разному (учитывая или не учитывая скобки, знаки операций, в том числе отрицания и т.п.). В теории булевых функций обычно имеют в виду минимизацию количества входящих в выражение букв. Если тебя интересует теория и всякие алгоритмы минимизации, можешь начать, например, вот с этого.
→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Л.А.Шоломов — "Основы теории дискретных логических и вычислительных устройств". Стр. 65 — 84.

→ Ответить