2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Булевы функции: полнота и базис системы
Сообщение01.06.2011, 21:03 
Аватара пользователя


17/12/10
538
Является ли полной система функций $\{x \vee y, \overline{x} \oplus y\}$
Образует ли она базис?

С чего надо начинать?

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


07/01/10
2015
Обе функции сохраняют единицу.

 Профиль  
                  
 
 Re: Булевы функции
Сообщение02.06.2011, 00:07 


27/01/10
260
Россия
Если взять класс $T_0$ функций, сохраняющих нуль, то любая функция в нем представима полиномом, в котором свободный член равен 0. Поэтому базис класса $T_0$ есть $\{xy, x\oplus y\}.$ А теперь можно заметить, что класс $T_1$ состоит из двойственных (к функциям из $T_0$) функций и воспользоваться принципом двойственности.

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


07/01/10
2015
cyb12
Зачем так сложно?

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


28/07/09
1238
Sverest, это задача на критерий Поста. Исходя из формулировки, нужно проверить принадлежность функций к 5 классам. Если обе функции лежат хотя бы в одном из этих пяти классов, то система не является полной.

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


17/12/10
538
caxap в сообщении #452755 писал(а):
Обе функции сохраняют единицу.

то есть надо просто подставить единицу?

-- Чт июн 02, 2011 10:32:12 --

caxap в сообщении #452755 писал(а):
Обе функции сохраняют единицу.

то есть надо просто подставить единицу?

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


07/01/10
2015
Sverest в сообщении #452888 писал(а):
то есть надо просто подставить единицу?

Надо проверить моё высказывание из 2-го сообщения. И из этого сделать вывод, что не все функции можно получить из данных функций, а значит это не полная система.

(Оффтоп)

Legioner93 в сообщении #452869 писал(а):
это задача на критерий Поста.

Не надо пугать человека. Из критерия Поста тут нужна только маленькая часть (часть необходимого условия критерия), с очевидным доказательством.

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


17/12/10
538
$1 \vee 1=1; 1 \vee 0=1; 0 \vee 1=1; 0 \vee 0 =0$ единицу сохраняет

$\overline{1} \oplus 1=1; \overline{0} \oplus 1= 0; \overline{1} \oplus {0}=0; \overline{0} \oplus 0=1$ единицу не сохраняет

так?

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


09/09/10
3729
Извините, а как вы ухитрились из $f(1)=1$ сделать вывод "$f$ сохраняет единицу", а из $g(1)=1$ сделать "$g$ не сохраняет единицу"?

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


17/12/10
538
Joker_vD в сообщении #452954 писал(а):
Извините, а как вы ухитрились из $f(1)=1$ сделать вывод "$f$ сохраняет единицу", а из $g(1)=1$ сделать "$g$ не сохраняет единицу"?


я подставил единицу, а получил ноль, вывод единица не сохранилась

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


09/09/10
3729
Sverest в сообщении #452964 писал(а):
я подставил единицу, а получил ноль

Это вы про $\overline 1 \oplus 1 = 1$? Подставленную единицу я вижу, а где ноль?

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


17/12/10
538
Joker_vD в сообщении #452967 писал(а):
Sverest в сообщении #452964 писал(а):
я подставил единицу, а получил ноль

Это вы про $\overline 1 \oplus 1 = 1$? Подставленную единицу я вижу, а где ноль?


Я про $ \overline{1} \oplus {0}=0$

-- Чт июн 02, 2011 13:30:58 --

Или надо было, чтоб в и там и там еденица была

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


07/01/10
2015
Sverest в сообщении #452970 писал(а):
Или надо было, чтоб в и там и там еденица была

Конечно. Повторяю свой совет.

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


09/09/10
3729
Говорят, что булева функция $f(x,y)$ сохраняет единицу, если $f(1,1)=1$. Берем функцию $f(x,y) = \overline x \oplus y$. $f(1,1) = \overline 1 \oplus 1 = 1$. Вывод?

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


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

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

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



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

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


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

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