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

Тема в разделе "WASM.CRYPTO", создана пользователем _blackfox_, 9 окт 2006.

  1. Black_mirror

    Black_mirror Active Member

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

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    _blackfox_
    Ага, я действительно понял так, что совсем любые. Но тогда почему не подходит {0,1,AND,XOR} в качестве базиса? Вроде четыре элемента и полная система, а любые три будут неполными. Или я обсчитался?
     
  3. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Stiver
    Здесь 0 лишний, его можно получить как X xor X.
     
  4. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Black_mirror

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

    _blackfox_

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

    _blackfox_ New Member

    Публикаций:
    0
    Регистрация:
    17 дек 2005
    Сообщения:
    17
    Так, уже что-то проясняется :)
    Почему четвертая функция лишняя? ведь система из этих четырхе функций также будет полной. Или это из определения? Если да, дай его пожалуйста.
     
  6. _blackfox_

    _blackfox_ New Member

    Публикаций:
    0
    Регистрация:
    17 дек 2005
    Сообщения:
    17
    Да, действительно :) Это хорошо, что получилось отсечь ненужные функции
     
  7. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Добавлю для интересующихся темой: теоретическое обоснование всего этого хозяйства (т.е. аргументации на основании свойств функций) проходит под названием "Теорема Поста" и изучается похоже в курсе дискретной математики (российских) ВУЗов.
     
  8. _blackfox_

    _blackfox_ New Member

    Публикаций:
    0
    Регистрация:
    17 дек 2005
    Сообщения:
    17
    У нас почему-то не изучается :dntknw:
     
  9. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    _blackfox_
    Точного определения я не знаю, но если некоторую функцию базиса можно выразить через остальные функции базиса, то зачем нам в базисе лишняя функция?
     
  10. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Stiver
    Значит действительно нужно тупо перебирать все комбинации из четырех функций, одна из которых имеет два из приведенных выше пяти свойств и остальные три по одному

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

    _blackfox_ New Member

    Публикаций:
    0
    Регистрация:
    17 дек 2005
    Сообщения:
    17
    Необходимо теоретически обосновать вот это:
    А конкретнее про то, почему мы можем выкинуть лишнюю функцию... и лишняя ли она?
    Отмазки типа "если некоторую функцию базиса можно выразить через остальные функции базиса, то зачем нам в базисе лишняя функция" не катят :dntknw:

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

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    _blackfox_
    Посмотри здесь: http://pgap.chat.ru/zap/zap125.htm#0

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

    _blackfox_ New Member

    Публикаций:
    0
    Регистрация:
    17 дек 2005
    Сообщения:
    17
    Всем большое спасибо, тема закрыта :)))