Булевы функции: полнота и базис системы

[ИСН]

Значит, и все их комбинации сохраняют единицу. Значит...

[Sverest]

а нужно суперпозицию из этих функций представлять?

[ИСН]

не понял смысл последнего слова

[Sverest]

в методичке написано: система булевых функций называется полной, если любая логическая функция может быть представлена в виде суперпозиции указанных функций

[ИСН]

А, понял. И что? Вы собираетесь представлять любую логическую функцию в виде суперпозиции указанных функций?
Предупреждаю: их (любых) довольно много.

[Sverest]

По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:
Хотя бы одна функция, не сохраняющая 0.
Хотя бы одна функция, не сохраняющая 1.
Хотя бы одна нелинейная функция.
Хотя бы одна немонотонная функция.
Хотя бы одна несамодвойственная функция.

Вот, еще что то нашел, это то?

-- Чт июн 02, 2011 17:03:19 --

Раз в этой системе существует одна функция, не сохраняющая 0, значит система полная

[ИСН]

Все эти "Хотя бы" связаны между собой каким условием?

[Sverest]

Цитата:

Все эти "Хотя бы" связаны между собой каким условием?

Вот этого я не понял, толи все вместе должно выполняться, толи любое из них


Полная система функций называется базисом, если она перестаёт быть полной при исключении из неё любого элемента.

То есть надо исключить, $x$, потом $y$ ?

[ИСН]

Sverest в сообщении #453093 писал(а):

Вот этого я не понял, толи все вместе должно выполняться, толи любое из них

Дак поймите!

[caxap]

Sverest в сообщении #453084 писал(а):

значит система полная

Сделайте функцию, которая тождественно равна нулю. Если этого нельзя сделать, то почему? Надо вспомнить, чем вы занимались на прошлой странице. К чему там все эти единицы были?

Забудьте про критерий Поста.

-- 02 июн 2011, 18:11 --

Вообще, как получать новые функции из имеющихся?

[ИСН]

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

[Sverest]

ИСН в сообщении #453094 писал(а):

Sverest в сообщении #453093 писал(а):

Вот этого я не понял, толи все вместе должно выполняться, толи любое из них

Дак поймите!

Вроде, это все вместе должно выполниться

-- Чт июн 02, 2011 17:25:06 --

caxap в сообщении #453096 писал(а):

Sverest в сообщении #453084 писал(а):

значит система полная

Сделайте функцию, которая тождественно равна нулю. Если этого нельзя сделать, то почему? Надо вспомнить, чем вы занимались на прошлой странице. К чему там все эти единицы были?

Забудьте про критерий Поста.

-- 02 июн 2011, 18:11 --

Вообще, как получать новые функции из имеющихся?

я вот ищу в методичке и учебнике, и найти не могу

[ИСН]

То-то и оно: должны все вместе. И что же?

[caxap]

(ИСН)

ИСН в сообщении #453098 писал(а):

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

ОК, не буду на кухне толпиться, пойду в зал. Критерия Поста я избегал потому, что понимания от этого не прибавится. Причину того, почему набор не полный, желательно осознать. Форум вроде как преследует образовательную цель (а не чтоб зачёт сдать).

[Sverest]

caxap в сообщении #453096 писал(а):

Sverest в сообщении #453084 писал(а):

значит система полная

Сделайте функцию, которая тождественно равна нулю. Если этого нельзя сделать, то почему? Надо вспомнить, чем вы занимались на прошлой странице. К чему там все эти единицы были?

Забудьте про критерий Поста.

-- 02 июн 2011, 18:11 --

Вообще, как получать новые функции из имеющихся?

$x \cdot 0$ тождественно равна нулю