2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Булевы функции
Сообщение02.06.2011, 17:54 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
У Вас нет функции "$\cdot$".

 Профиль  
                  
 
 Re: Булевы функции
Сообщение02.06.2011, 18:02 
Аватара пользователя


17/12/10
538
должно быть две переменных?

 Профиль  
                  
 
 Re: Булевы функции
Сообщение02.06.2011, 18:04 
Заслуженный участник


09/09/10
3729
Sverest в сообщении #453084 писал(а):
По теореме Поста, чтобы система булевых функций была полной, надо, чтобы в ней существовали:
Хотя бы одна функция, не сохраняющая 0.
Хотя бы одна функция, не сохраняющая 1.
Хотя бы одна нелинейная функция.
Хотя бы одна немонотонная функция.
Хотя бы одна несамодвойственная функция.

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

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

 Профиль  
                  
 
 Re: Булевы функции
Сообщение02.06.2011, 18:07 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Булевы функции
Сообщение02.06.2011, 18:19 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Булевы функции
Сообщение02.06.2011, 18:31 
Аватара пользователя


17/12/10
538
Tlalok в сообщении #453132 писал(а):
Sverest
Зачем Вам методичка? Я, например, пользовался сборником задач. Гаврилов, Сапоженко
Глава 2 параграф 6. Но для интереса можете прочесть всю главу.


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

 Профиль  
                  
 
 Re: Булевы функции
Сообщение02.06.2011, 18:36 
Заслуженный участник
Аватара пользователя


14/03/10
595
Одесса, Украина
Как это не разобраны? Вы знакомы с теоремой Поста или еще называют Критерий Поста?

 Профиль  
                  
 
 Re: Булевы функции
Сообщение02.06.2011, 18:37 
Аватара пользователя


17/12/10
538
Tlalok в сообщении #453136 писал(а):
Как это не разобраны? Вы знакомы с теоремой Поста или еще называют Критерий Поста?

да

 Профиль  
                  
 
 Re: Булевы функции
Сообщение02.06.2011, 18:41 
Заслуженный участник
Аватара пользователя


14/03/10
595
Одесса, Украина
Тогда какие у Вас затруднения?
Определите к каким классам принадлежат ваши функции.

 Профиль  
                  
 
 Re: Булевы функции
Сообщение02.06.2011, 18:44 
Аватара пользователя


17/12/10
538
caxap в сообщении #453096 писал(а):
Sverest в сообщении #453084 писал(а):
значит система полная

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

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

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

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


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

 Профиль  
                  
 
 Re: Булевы функции
Сообщение06.06.2011, 19:47 
Аватара пользователя


17/12/10
538
caxap в сообщении #453096 писал(а):
Сделайте функцию, которая тождественно равна нулю. Если этого нельзя сделать, то почему? Надо вспомнить, чем вы занимались на прошлой странице. К чему там все эти единицы были?

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

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


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

 Профиль  
                  
 
 Re: Булевы функции
Сообщение06.06.2011, 20:07 
Заслуженный участник
Аватара пользователя


07/01/10
2015
Sverest в сообщении #453143 писал(а):
Что лучше почитать, чтобы ответить на эти вопросы?

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

Sverest в сообщении #454843 писал(а):
Объясните мне эти вопросы, я их так и не понял

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

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

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

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

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

 Профиль  
                  
 
 Re: Булевы функции
Сообщение06.06.2011, 20:29 
Аватара пользователя


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

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

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


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

 Профиль  
                  
 
 Re: Булевы функции
Сообщение06.06.2011, 20:48 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Булевы функции
Сообщение06.06.2011, 20:50 
Аватара пользователя


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

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

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


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 49 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group