Схемная сложность булевой функции

[dima_1985]

Здравствуйте! Не могу понять что значит схемная сложность булевой функции? Вот есть функция $f(x,y,z)=(0,1,1,0,0,1,0,0)$. Минимизировал ее и получил $z\bar y\vee\bar xy\bar z$.
Почитал, что нашел в интернете и построил .Схемная сложность это количество уровней в дереве? Иногда пишут просто сложность булевой функции. Схемная сложность и сложность это одно и тоже?

[Xaositect]

Схема - это не обязательно дерево. Например, для Вашей функции можно взять такую схему:
\xymatrix{x\ar[ddd] & y\ar[d] & z\ar[ldd]\ar[dd] \\ & \bar{y}\ar[d]\ar[rd] & \\ & \bar{y} \vee z\ar[ld] & \bar{y}z\ar[lddd] \\ x \vee \bar{y} \vee z\ar[d] & & \\ \overline{x \vee \bar{y} \vee z} = \bar{x}y\bar{z}\ar[rd] & & \\ & \bar{x}y\bar{z} \vee \bar{y}z = f(x,y,z) & }

Сложность схемы - это не количество уровней, а количество операций (вершин в графе, кроме исходных переменных). У моей схемы сложность 6, а у Вашей - 7.
А схемная сложность функции - это минимальная сложность схемы, которая вычисляет эту функцию. Если я нигде не ошибся, то схемы из 5 элементов для этой функции существовать не может, и поэтому ее схемная сложность равна 6, но доказать это (по крайней мере, руками, а не полным перебором) нетривиально.

[Sender]

В другом базисе может получиться другая сложность. Например, в Nand-базисе сложность данной функции равна 5. $f1 =y \barwedge z, f2 = \bar x, f3 =y \barwedge f1\barwedge f2, f4 = z\barwedge f1, f = f3\barwedge f4.$
$\xymatrix{ x\ar[d]&y\ar[dd]\ar[rd]&&z\ar[ld]\ar[dd]\\ f2\ar[rd]&&f1\ar[ld]\ar[rd]\\ &f3\ar[rd]&&f4\ar[ld]\\ &&f}$

-- Пт июл 07, 2017 09:37:00 --

Минимальность доказана SAT-солвером.

-- Пт июл 07, 2017 09:40:03 --

А глубина схемы, соответственно, 3.

-- Пт июл 07, 2017 10:08:55 --

Как-то натыкался на лекции А.В. Чашкина по дискретной математике, там в лекции 8 есть все необходимые определения, парочка полезных теорем и примеров оценки сложности и глубины булевых функций.

[Xaositect]

Есть еще лекции Ложкина с ВМК МГУ: Ложкин С.А. "Лекции по основам кибернетики" и Ложкин С.А. "Дополнительные главы кибернетики", скачать можно тут и тут.

[dima_1985]

Xaositect ,Спасибо! Хотел прояснить для себя некоторые вопросы. Если задача стоит в нахождении минимальной ДНФ(КНФ). В литературе рассматриваются несколько подходов, я знаю два карты Карно и метод Квайна. Это два альтернативных алгоритма которые приводят к одинаковому результату ? Трудоемкость алгоритма Квайна гораздо выше, для $4$ переменных не реально посчитать минимальной ДНФ(КНФ). На практике удобней пользоваться картами Карно? Если задача стоит построить минимальную нормальную форму функции $f$? Используя алгоритм Квайна мы должны найти минимальные ДНФ и КНФ из них выбрать минимальную. Если пользоваться картами Карно, то мы должны действовать аналогично строим минимальные ДНФ и КНФ и из них выбираем минимальную? Или можно построить одну из них например минимальную ДНФ и она будет минимальной нормальной формой?

[svv]

(Оффтоп)

Лекции Чашкина и Ложкина.

[Xaositect]

dima_1985 в сообщении #1232005 писал(а):

В литературе рассматриваются несколько подходов, я знаю два карты Карно и метод Квайна. Это два альтернативных алгоритма которые приводят к одинаковому результату ? Трудоемкость алгоритма Квайна гораздо выше, для $4$ переменных не реально посчитать минимальной ДНФ(КНФ). На практике удобней пользоваться картами Карно?

Я не знаю, что Вы имеете в виду, говоря о картах Карно как об алгоритме поиска минимальной ДНФ. Карты Карно - это просто графическое представление импликант для функций от 3 или 4 переменных, все действия с картами Карно можно так же записать как действия с простыми импликантами. Для 4 переменных все реально сделать руками любым методом, не преувеличивайте :)

dima_1985 в сообщении #1232005 писал(а):

На практике удобней пользоваться картами Карно?

На практике удобно пользоваться SAT-солверами и эвристиками, которые дают не обязательно минимальную, но достаточно простую ДНФ.

dima_1985 в сообщении #1232005 писал(а):

Если пользоваться картами Карно, то мы должны действовать аналогично строим минимальные ДНФ и КНФ и из них выбираем минимальную?

Если я правильно понимаю (Вы используете слово "минимальная ДНФ" в двух разных смыслах), то да, все равно для нахождения минимальной ДНФ нужен будет перебор всех неулучшаемых ДНФ.

[dima_1985]

Xaositect в сообщении #1232024 писал(а):

На практике удобно пользоваться SAT-солверами и эвристиками, которые дают не обязательно минимальную, но достаточно простую ДНФ.

Про этот метод я пока не знаю.

Xaositect в сообщении #1232024 писал(а):

Если я правильно понимаю (Вы используете слово "минимальная ДНФ" в двух разных смыслах), то да, все равно для нахождения минимальной ДНФ нужен будет перебор всех неулучшаемых ДНФ.

Я думаю не совсем правильно для моей функции

dima_1985 в сообщении #1231966 писал(а):

$f(x,y,z)=(0,1,1,0,0,1,0,0)$

минимальная ДНФ(может быть несколько?)

dima_1985 в сообщении #1231966 писал(а):

$z\bar y\vee\bar xy\bar z$

минимальная КНФ(может быть несколько?) $(y \vee z)(\bar y \vee \bar z)(\bar x \vee z)$. Для того чтобы найти минимальную в классе нормальных форм мы выбираем минимальную из МКНФ и МДНФ ? Получаем минимальную в классе нормальных $z\bar y\vee\bar xy\bar z$ ( так как $5$ переменных три отрицания).