алгоритм для упрощения логических выражений

Question

Я хочу, чтобы упростить очень большой булеву функцию вида:

f(a1,a2,....,an)= (a1+a2+a5).(a2+a7+a11+a23+a34)......(a1+a3+an). 

«» означает, ИЛИ

«+» означает, И

может быть 100 таких терминов («» друг с другом) значение п может пойти Шифрование до 30.

Есть ли осуществимо алгоритм, чтобы упростить этот ?

ПРИМЕЧАНИЕ: Это не лабораторное задание, небольшая часть моего проекта по генерации правил по грубому набору, где f - функция несходства.

Answer 1

Типичным методом является использование boolean algebra, чтобы уменьшить утверждение до его простейшей формы.

Если, к примеру, у вас есть что-то вроде:

(A AND B) OR (A AND C)

вы можете преобразовать его в более простой форме:

A AND (B OR C)

Answer 2

Если вы представляете значений а в качестве int или long, где a1 имеет значение 2, a2 ​​имеет значение 4, a3 имеет значение 8 и т. Д .:

int a = (a1? 2^1: 0) + (a2? 2^2: 0) + (a3? 2^3: 0) + ...;

(тратить немного, чтобы сохранить его простым и игнорируя тот факт, что вы бы лучше с а0 = 1)

И вы делаете то же самое для всех условий:

long[] terms = ...; 
terms[0] = 2^0 + 2^3 + 2^5   // a1+a2+a5 
terms[1] = 2^2 + 2^7 + 2^23 + 2^34 // (a2+a7+a11+a23+a34) 

Тогда вы можете найти результат:

foreach(var term in terms) 
{ 
    if (a & term == term) return true; 
} 
return false; 

НО это хорошо работает только до п = 64. Выше, это грязно.

Answer 3

Хорошо известные способы сделать это, являются:

• если число переменных меньше 5, используйте Karnaugh Map Algorithm
• если число переменных равно 5 или больше, используйте Quine McCluskey Algorithm

Второй способ чаще всего используется на компьютере. Это табличное и прямолинейное. Первый способ - это лучший способ сделать это вручную, и это приносит больше удовольствия, но вы не можете использовать его более чем для 4 переменных.