Является ли система связок базисом?
Класс функций сохраняющих 0 (
Примеры из
Примеры не из
Индукция по длине формулы:
- формула (над ), - аргументы
Переход: "" - формула по предположению индукции
Класс функций сохраняющих 1 (
Примеры из
Примеры не из
Самодвойственность
Стоит отметить симметрию относительно центра таблицы истинности (xor не самодвойственна, потому-что симметричные элементы не имеют разные значения)
| a | b | |||
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
Примеры:
**Доказательство по индукции аналогично
Монотонность
Пример: лексикографическое сравнение конкатенации аргументов
| a | b | ||
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 |
Примеры:
Пример: Выразим
через - базис,
- базис
Полином Жегалкина
- Нет
- Нет
- Нет
П.Ж (инъекция) - иньекция - биекция
Полиномов -
Пустой П.Ж.
Линейная функция
- если
- не базис - если
- не базис ... - если
- не базис
Теорема Поста
b)
1а)
1b)
2b)