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

[ИСН]

У Вас нет функции "$\cdot$".

[Sverest]

должно быть две переменных?

[Joker_vD]

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

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

Ох уж мне эти формулировки. Традиция такая, что ли — формулировать через непринадлежность классам...

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

[Sverest]

То есть значки $\wedge \vee \oplus$ означают лишь правила по которым из единиц и нулей, получаются единицы и нули?

[Tlalok]

Sverest
Зачем Вам методичка? Я, например, пользовался сборником задач. Гаврилов, Сапоженко
Глава 2 параграф 6. Но для интереса можете прочесть всю главу.

[Sverest]

Tlalok в сообщении #453132 писал(а):

Sverest
Зачем Вам методичка? Я, например, пользовался сборником задач. Гаврилов, Сапоженко
Глава 2 параграф 6. Но для интереса можете прочесть всю главу.

в этом задачнике, примеры же подробно не разобраны

[Tlalok]

Как это не разобраны? Вы знакомы с теоремой Поста или еще называют Критерий Поста?

[Sverest]

Tlalok в сообщении #453136 писал(а):

Как это не разобраны? Вы знакомы с теоремой Поста или еще называют Критерий Поста?

да

[Tlalok]

Тогда какие у Вас затруднения?
Определите к каким классам принадлежат ваши функции.

[Sverest]

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

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

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

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

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

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

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

Что лучше почитать, чтобы ответить на эти вопросы?

[Sverest]

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

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

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

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

Объясните мне эти вопросы, я их так и не понял

[caxap]

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

Что лучше почитать, чтобы ответить на эти вопросы?

Верещагин, Шень "Языки и исчисления".

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

Объясните мне эти вопросы, я их так и не понял

В школе вам рассказали о функциях возведения в степень, синус, косинус, логарифм... Как потом сочиняют из них новые функции? Вот как вы вообще понимаете, скажем, $(\sin (4\tg x))^7+42$ ? А вы ведь это как-то понимаете (причём правильно), раз успешно поступили в университет.

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

Если вы успешно ответили на последнее "Почему?", то вам не составит труда ответить на исходный вопрос этой темы.

-- 06 июн 2011, 21:13 --

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

[Sverest]

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

$(\sin (4\tg x))^7+42$ здесь использовано сложение функций, то есть как бы написать, переменная, по сложному закону, зависит от другой, но они сохраняют в некоторых промежутках, уже известную закономерность тех младших функций, из которых сделана сложная.

Цитата:

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

То есть какая бы ни была переменная на входе, на выходе будет положительное число, получается это основное свойство такой функции, и оно будет сохранено, что бы мы не делали с ней?

[caxap]

Ладно. А теперь без вопросительных знаков и с объяснением (был вопрос "Почему?"). И сразу же с решением исходной задачи.

[Sverest]

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

-- Пн июн 06, 2011 21:02:59 --

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

Ладно. А теперь без вопросительных знаков и с объяснением (был вопрос "Почему?"). И сразу же с решением исходной задачи.

Потому что функция выглядит примерно так
$\[x\]=\text{положительное число}$ то есть это свойство игрика, а не икса