Задача по дискретной математике

Возьмем в качестве первой функции XOR.
Эта функция не сохраняет 1, не монотонная, не самодвойственная.
То есть одна из оставшихся функций должна быть несохраняющей 0, а вторая нелинейной.
Добавив две такие функции(например 1(не сохраняет 0) и ИЛИ(нелинейная)) мы получим полную системую. То есть четвёртая функции будет уже лишней.
Вывод: не нужно брать функции с более чем 2мя свойствами.

 

_blackfox_

Ага, я действительно понял так, что совсем любые. Но тогда почему не подходит {0,1,AND,XOR} в качестве базиса? Вроде четыре элемента и полная система, а любые три будут неполными. Или я обсчитался?

 

Stiver
Здесь 0 лишний, его можно получить как X xor X.

 

Black_mirror

Точно, это я почему-то вчера решил, что XOR единицу сохраняет.

_blackfox_

Значит действительно нужно тупо перебирать все комбинации из четырех функций, одна из которых имеет два из приведенных выше пяти свойств и остальные три по одному, и смотреть, получится ли из них базис. Как совершенно правильно и написал Black_mirror. Для трех и более переменных такие базисы существуют

 

Так, уже что-то проясняется
Почему четвертая функция лишняя? ведь система из этих четырхе функций также будет полной. Или это из определения? Если да, дай его пожалуйста.

 

Да, действительно Это хорошо, что получилось отсечь ненужные функции

 

Добавлю для интересующихся темой: теоретическое обоснование всего этого хозяйства (т.е. аргументации на основании свойств функций) проходит под названием "Теорема Поста" и изучается похоже в курсе дискретной математики (российских) ВУЗов.

 

У нас почему-то не изучается

 

_blackfox_
Точного определения я не знаю, но если некоторую функцию базиса можно выразить через остальные функции базиса, то зачем нам в базисе лишняя функция?

 

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

Каждая функция может обладать и двумя свойствами, значение имею её уникальные свойства. Например если все 4 функции у нас не самодвойственные и при этом каждой из них досталось по одному из оставшихся свойств, из них можно было бы построить базис. А то что свойств должно быть не более 2х следует из того, что мы хотим включить в базис 4 функции, то есть по одному уникальному свойству мы должны дать каждой функции. И у нас остаётся одно свойство, которое должно достаться одной или нескольким функциям, то есть всего у каждой функции не более двух свойств. Если бы свойств было не 5, а 6, или мы строили бы базис из 3х функций, то у каждой функции должно было бы быть не более 3х свойств.

 

Необходимо теоретически обосновать вот это:

А конкретнее про то, почему мы можем выкинуть лишнюю функцию... и лишняя ли она?
Отмазки типа "если некоторую функцию базиса можно выразить через остальные функции базиса, то зачем нам в базисе лишняя функция" не катят

Оказывается, теорема Поста - это то, о чем я говорил про полноту системы, так что ничего принципиально нового я из нее не узнал...

 

_blackfox_

Посмотри здесь: http://pgap.chat.ru/zap/zap125.htm#0

Это прямое следствие из
Теорема 2.4. Класс булевых функций K является полным тогда и только тогда, когда он не содержится ни в одном из основных замкнутых классов.

 

Всем большое спасибо, тема закрыта ))