Как правильно минимизировать булеву функцию?

Question

[qooke]

С помощью карты карно я минимизировал функцию.

Введённая функция: A∧(B∨C∨D)∨B∧(C∨D)∨C∧D
Вектор функции: 0001011101111111

И получил результат:

Минимизированная ДНФ:
AB∨AC∨AD∨BC∨BD∨CD

Но в этом варианте функции 11 операций вместо моих 8!

Вопрос - почему именно второй вариант называется "минимизированным" , и какая функция будет быстрее выполнятся?

Comments

[SagePtr]

Второй вариант - это не минимизация, это нормальная форма

[qooke]

SagePtr, тогда мне нужен алгоритм для минимизации :с

[SagePtr]

qooke, если вам нужно, чтобы быстрее выполнялось, я бы посмотрел в сторону ветвления (получится 1 операция ветвления и максимум 4 булевых операции):

if (D) {
  return A | B | C;
} else {
  return (A^B^C) | (A&B);
}

Или разветвить сильнее (1 ветвление и 2 логические операции или 2 ветвления и 1 логическая операция):

if (D) {
  return A | B | C;
} else {
  if (A) {
    return B | C;
  } else {
    return B & C;
  }
}

Если булевы переменные равны 1 и можно их суммировать, то вторую часть можно ещё упростить (1 ветвление и 2 логических операции или 1 ветвление и 2 сложения и 1 сравнение):

if (D) {
  return A | B | C;
} else {
  return A + B + C > 1;
}

Примеры писал на человекочитаемом псевдокоде (на основе C), в реальности - возможно, ради ускорения лучше использовать ассемблер. Ветвление можно считать двумя операциями, это тест и джамп обычно в большинстве архитектур процессора.

[qooke]

SagePtr, ветвление в с++ это
cmp ...
je FALSE
<блок для true>
jmp END
.FALSE
<блок для FALSE>
.END (а это всегда выполняется в конце условия)
pop rbp
ret

[qooke]

SagePtr, поэтому вместо ветвлений лучше использовать and / or, которые компилируются так:
https://sun9-63.userapi.com/c855724/v855724555/139...

[qooke]

SagePtr, но всё-таки мне интересны не ветвления, а алгоритм нахождения наиболее эффективной линейной логической функции

[SagePtr]

qooke, оптимизатор в конечном итоге и преобразовует всё в ветвления

[qooke]

SagePtr, ну у меня не преобразуется((
and / or по сути те же ветвления, но они компактнее
и это не оптимизация вроде, а логика работы.
x or y
если х истинна, то у проверяться не будет,
или я хз о чем вы..

[profesor08]

Про скобочки не надо забывать, с их учетом у тебя 12 операций, так что считай на одну операцию минимизировалось.

[qooke]

profesor08, а разве скобки это логическая операция?
ИМХО:
это способ задания операций.
Можно аналогично задать и без скобок,
B or C or D and A or C or D and B or C and D == 8 операций
, количество операций больше не станет,
т.к скобки это как пояснение для компилятора, а сами операции передаются процессору

[profesor08]

qooke, скобки это не логическая опрерация, но тоже операция.

[qooke]

profesor08, эта операция не относится к алгоритму, она его определяет

Answer 1

[Rsa97]

Исходная функция у вас не в одной из нормальных форм. Минимальная форма же определена именно для ДНФ и КНФ.
ДНФ - значит, что выражение записано в виде множественной дизъюнкции, каждый член которой - конъюнкция переменных или их инверсий.
МДНФ - это такая запись ДНФ, в которой количество членов в дизъюнкции минимально.
Для КНФ всё аналогично.
Об минимальном количестве общего числа операций тут речи не идёт.
А для программы надо составлять выражение таким образом, чтобы при вычислении получать результат как можно раньше. Например, если у вас A = false, то (B∨C∨D) вообще не будет вычисляться.

Comments

[qooke]

и всё таки хочется найти какой-то общий алгоритм для нахождения мин. количества операций, а еще лучше - способ расставить логические операции в таком порядке, что зная статистическую вероятность появления какого-то значения исходя из этого строилась функция.
например если шанс появления A = 99%, то NOT(A) AND ... стоит на 1 месте.
Звучит просто и вроде можно расписать на бумажке, но предположим в моем алгоритме 27 переменных и шанс появления каждой немного отличается, просто представьте как сложно найти САМЫЙ эффективный алгоритм, а скорость вычисления стоит на первом месте.