СДНФ и булевы функции

[MestnyBomzh]

Задача Записать булеву функцию $f(x,y,z)=xy \oplus xz \oplus yz$ в базисе из отрицания, дизъюнкции и конъюнкции
а) произвольным способом
б) с наименьшей возможной сложностью
Решение Я просто записал таблицу истинности и дальше записал СДНФ

$$ \bar{x}yz \vee x \bar{y}z \vee xy \bar{z} \vee xyz $$

Дальше сделал одно упрощение и получил

$$ \bar{x} yz \vee x \bar{y}z \vee xy $$

Пункт а) я выполнил, теперь вопрос является ли последняя форма наименьшей возможной сложность? можно ли тут ещё как-то упростить?

[waxtep]

MestnyBomzh в сообщении #1552727 писал(а):

просто записал таблицу истинности

"не менее двух из $x,y,z$ истинны" - кажется, есть напрашивающийся более краткий способ записать это даже без отрицания

[svv]

В точности эта функция в полном одноразрядном сумматоре по двум операндам $x,y$ и переносу $z$ вычисляет следующий перенос. Сейчас Вы используете 9 операций, среди которых есть конъюнкции, дизъюнкции и отрицания. Т.е. если в схеме разрешено использовать логические элементы "И", "ИЛИ", "НЕ", Вы обойдётесь девятью элементами.

Наверное, это звучит невероятно, но можно обойтись четырьмя. Попробуйте! Подсказку Вам уже дали.

[MestnyBomzh]

Пока что я придумал из головы вот такой вариант

$$ xy \vee yz \vee zx $$

Если вынести за скобку то будет 4 операции

$$ y(x \vee z) \vee zx $$

Видимо, на этот раз это наименьшая сложность? У меня такой вопрос, эта форма эквивалентна формуле которую я писал в первом сообщении

$$ \bar{x} yz \vee x \bar{y}z \vee xy $$

То есть преобразованиями из этого можно получить ту кратчайшую форму. Подскажите как тут надо преобразовывать?

[mihaild]

Заметьте, что $a \vee \bar{a}b$ эквивалентно $a \vee b$, и что-нибудь погруппируйте.

[waxtep]

MestnyBomzh в сообщении #1552761 писал(а):

Если вынести за скобку то будет 4 операции

$$ y(x \vee z) \vee zx $$

Видимо, на этот раз это наименьшая сложность? У меня такой вопрос, эта форма эквивалентна формуле которую я писал в первом сообщении

$$ \bar{x} yz \vee x \bar{y}z \vee xy $$

Да и да

MestnyBomzh в сообщении #1552761 писал(а):

Подскажите как тут надо преобразовывать?

Наверное, разные варианты возможны, мне показалось проще всего заменить xor на or исходя из таблицы истинности, а затем поколдовать над сокращением количества операций

[MestnyBomzh]

mihaild в сообщении #1552762 писал(а):

$a \vee \bar{a}b$ эквивалентно $a \vee b$

с помощью этого свойства:

$$ \bar{x} yz \vee x \bar{y}z \vee xy = \bar{x}yz \vee x(\bar{y}z \vee y) = \bar{x}yz \vee xz \vee xy = z(\bar{x}y \vee x) \vee xy = zy \vee zx \vee xy $$