2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 СДНФ и булевы функции
Сообщение16.04.2022, 20:21 
Аватара пользователя
Задача Записать булеву функцию $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 $$
Пункт а) я выполнил, теперь вопрос является ли последняя форма наименьшей возможной сложность? можно ли тут ещё как-то упростить?

 
 
 
 Re: СДНФ и булевы функции
Сообщение16.04.2022, 21:12 
Аватара пользователя
MestnyBomzh в сообщении #1552727 писал(а):
просто записал таблицу истинности
"не менее двух из $x,y,z$ истинны" - кажется, есть напрашивающийся более краткий способ записать это даже без отрицания

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

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

 
 
 
 Re: СДНФ и булевы функции
Сообщение17.04.2022, 01:16 
Аватара пользователя
Пока что я придумал из головы вот такой вариант
$$ xy \vee yz \vee zx $$
Если вынести за скобку то будет 4 операции
$$ y(x \vee z) \vee zx $$
Видимо, на этот раз это наименьшая сложность? У меня такой вопрос, эта форма эквивалентна формуле которую я писал в первом сообщении
$$ \bar{x} yz \vee x \bar{y}z \vee xy $$
То есть преобразованиями из этого можно получить ту кратчайшую форму. Подскажите как тут надо преобразовывать?

 
 
 
 Re: СДНФ и булевы функции
Сообщение17.04.2022, 01:20 
Аватара пользователя
Заметьте, что $a \vee \bar{a}b$ эквивалентно $a \vee b$, и что-нибудь погруппируйте.

 
 
 
 Re: СДНФ и булевы функции
Сообщение17.04.2022, 01:27 
Аватара пользователя
MestnyBomzh в сообщении #1552761 писал(а):
Если вынести за скобку то будет 4 операции
$$ y(x \vee z) \vee zx $$
Видимо, на этот раз это наименьшая сложность? У меня такой вопрос, эта форма эквивалентна формуле которую я писал в первом сообщении
$$ \bar{x} yz \vee x \bar{y}z \vee xy $$
Да и да :-)
MestnyBomzh в сообщении #1552761 писал(а):
Подскажите как тут надо преобразовывать?
Наверное, разные варианты возможны, мне показалось проще всего заменить xor на or исходя из таблицы истинности, а затем поколдовать над сокращением количества операций

 
 
 
 Re: СДНФ и булевы функции
Сообщение17.04.2022, 10:20 
Аватара пользователя
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 $$

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group