Требуется привести к с.д.н.ф. произвольное логическое выражение. Допустим, такое:
a | c & a => !!b <=> b & a | !b <=> c
( что эквивалентно (((a | (c & a)) => !!b) <=> c) & (((b & a) | !b) <=> c) )
Столкнулся с 2-мя проблемами: во-первых, некоторые выражения упрощаются
( a & b | a & !b равносильно a ),
другие, хоть и очень похожие — нет
( a & b | c & a & !b),
т. е. нужен алгоритм распознавания. Во-вторых, формула может быть очень длинной и неплохо было бы иметь алгоритм побыстрее. Как выгоднее хранить конъюнкты — в алфавитном или лексикографическом порядке?
Посоветуйте какой-нибудь источник на эту тему. Просто учебник логики не предлагайте — алгоритмическая сторона там не рассматривается.
Программировать сложно. Но не программировать еще сложнее.
Здравствуйте, DSblizzard, Вы писали:
DS>Требуется привести к с.д.н.ф. произвольное логическое выражение.
С.д.н.ф. определена однозначно, для ее вычисления нужно подставить все 2^n комбинаций значений в функцию.
DS>Столкнулся с 2-мя проблемами: во-первых, некоторые выражения упрощаются DS>( a & b | a & !b равносильно a ), DS>другие, хоть и очень похожие — нет DS>( a & b | c & a & !b),
После упрощения будут уже не с.д.н.ф., так что не ясно, к чему это.
DS>т. е. нужен алгоритм распознавания. Во-вторых, формула может быть очень длинной и неплохо было бы иметь алгоритм побыстрее. Как выгоднее хранить конъюнкты — в алфавитном или лексикографическом порядке?
В худшем случае без разницы. Например, для функции "сумма по модулю два всех переменных" любая д.н.ф. будет экспоненциального по n размера.
Здравствуйте, DSblizzard, Вы писали:
DS>Требуется привести к с.д.н.ф. произвольное логическое выражение. Допустим, такое:
Приведение булевой функции к СДНФ — это не упрощение, а усложнение — фактически, это получается таблица истинности.
Например, f(x,y,z,t)=True в СДНФ состоит из 16 дизъюнктов.
А вот упрощение, — если ничего не путаю, — это NP-полная задача "SAT"
Здравствуйте, DSblizzard, Вы писали:
DS>Требуется привести к с.д.н.ф. произвольное логическое выражение. Допустим, такое: DS>a | c & a => !!b <=> b & a | !b <=> c DS>( что эквивалентно (((a | (c & a)) => !!b) <=> c) & (((b & a) | !b) <=> c) ) DS>Столкнулся с 2-мя проблемами: во-первых, некоторые выражения упрощаются DS>( a & b | a & !b равносильно a ), DS>другие, хоть и очень похожие — нет DS>( a & b | c & a & !b), DS>т. е. нужен алгоритм распознавания. Во-вторых, формула может быть очень длинной и неплохо было бы иметь алгоритм побыстрее. Как выгоднее хранить конъюнкты — в алфавитном или лексикографическом порядке? DS>Посоветуйте какой-нибудь источник на эту тему. Просто учебник логики не предлагайте — алгоритмическая сторона там не рассматривается.
если переменных больше существуют неплохие эвристические методы позволяющие добиться минимизации формул, правда не всегда дающие минимальные результаты (помню, читал монографию на тему), к сожалению не помню название — давно было. Каталог библиотеки в помощь
Здравствуйте, Mab, Вы писали:
DS>>Столкнулся с 2-мя проблемами: во-первых, некоторые выражения упрощаются DS>>( a & b | a & !b равносильно a ), DS>>другие, хоть и очень похожие — нет DS>>( a & b | c & a & !b), Mab>После упрощения будут уже не с.д.н.ф., так что не ясно, к чему это.
В первом случае — просто a, т.е. с.д.н.ф., во втором случае — дальше не упрощается, я так и написал.
Программировать сложно. Но не программировать еще сложнее.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, DSblizzard, Вы писали:
DS>>Требуется привести к с.д.н.ф. произвольное логическое выражение. Допустим, такое:
К>Приведение булевой функции к СДНФ — это не упрощение, а усложнение
Смотря для кого и в каких ситуациях. В логических языках и алгоритме резолюции обычно используются именно нормальные формы. К>А вот упрощение, — если ничего не путаю, — это NP-полная задача "SAT"
SAT — это выполнимость, т. е. принимает ли данное выражение значение true хоть при одном присваивании значений переменным. К упрощению это не относится.
Программировать сложно. Но не программировать еще сложнее.
— фактически, это получается таблица истинности.
Перекуём баги на фичи!
