| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Перебор логических функций |
| Автор: Kvanttt 4.7.2009, 13:40 |
| Подскажите: есть допустим функция Вебба для троичной функции, таблица истинности которой: | - | 0 | +| ---------------- - | 0 | + | - | ---------------- 0 | + | + | - | ---------------- + | - | - | - | Обозначения: - false; 0 unknown; + true Я знаю, что через эту функцию (подобно функции И-НЕ для двоичной логики), можно выразить любую другую троичную функцию: Inc(x) = Webb(x, x); Dec(x) = Inc(Inc(x)); x or y = Dec(Webb(x, y)); и т.д. И есть функция x and y, которую я впринципе знаю как выразить x and y = Not(Not(x) or Not(y)), но хотелось бы ее выразить как-нибудь попроще (Потому что сама функция Not в троичной логике достаточно сложно выражается через функцию Вебба) Подскажите алгоритм для перебора всех комбинаций с этой функцией. Я так подумал по этому поводу, и понял, что это достаточно сложно, потому что надо будет составлять дерево, в котором нужно будет перебирать все возможные комбинации ветвей и листьей этого дерева. Хотелось бы еще почитать какую-нибудь литературу по этому поводу. Также неплохо было бы обощить этот перебор: Если допустим имеюется не одна функция, а сразу несколько (Те же Inc Dec or). |
| Автор: maxdiver 4.7.2009, 20:00 |
| Я бы не сказал, что перебор здесь сложен. Его можно смоделировать, не строя явно никаких деревьев. Например, всевозможные выражения можно генерировать так. Будем строить их последовательно, на i-ой фазе - выражения, содержащие i операций. Тогда базой, т.е. значениями на нулевом шаге, будут выражения без операций: A[0] = { 'a', 'b' } где через A[i] я обозначил ответ для i-ой фазы, т.е. множество всех выражений с i операциями. Тогда элементы A[i+1] будут получаться как всевозможные комбинации (с какой-то операцией) подвыражений из A[k] и A[i-k], k=0..i: A[i+1] = { z, где z = '(x) операция (y)' по всем x \in A[k], y \in A[i-k], k=0..i } Для каждого нового построенного выражения можно вычислять таблицу истинности (её, кстати, можно найти безо всякого разбора выражения, просто взяв таблицы истинности для x и y и операции), и как только обнаружится выражение, таблица которого совпадёт с требуемой, останавливаем процесс - мы нашли кратчайшее выражение. Разумеется, размеры множеств A[i] будут расти экспоненциально, но не думаю, что это имеет хоть какое-то значение. |