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

Нужно решить одну задачку.
Необходимо доказать, что базис, состоящий из четырех функций двух переменных не существует.
Перебирать все сочетания по n из 16 функций (а их 969) - слишком долго, можно ли решить эту задачу другим путем?
Буду рад любым советам.

 

Честно признаюсь, вопроса не понял совершенно. Что за функции, базис чего? Если кто-то понял, просьба объяснить и мне.

P.S. Если это задание взято откуда-то (из задачника, домашней работы и т.д.), желательно привести оригинальную формулировку.

 

видимо функции - булевы
а функции базиса видимо не должны выражаться друг через друга?

 

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

 

Спасибо за ответы.
Да, я говорю про булевы функции.
Они могут абсолютно любые - их всего 16

Чтобы система была базисом нужно, чтоб выполнялось 2 условия:
1) система из всех 4 функций должна быть полной
2) системы из любых 3 функций не должны быть полными.

 

дык приведи примеры систем из 3х функций которые полные))))))

 

Это в линейной алгебре. Как применить это в дискретной математике я не знаю не уверен, что базисом здесь тоже самое, что и в линейке.

 

Функции полными быть не могут Полными бывают системы функций.

 

я про полные системы, возможно не хватает знаков припинания
короче приведи контрпример

 

Контрпример - базис из 4-х функций? Его не должно быть, если изначальная формулировка верна.
Пример не-базиса из 4-х функций: (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1).
Система из всех функций полная, но любая система из 3-х функций тоже полная

Полная система должна содержать:
одну функцию, не сохраняющую 0
одну функцию, не сохраняющую 1
одну функцию не самодвойственную
одну функцию нелинейную
одну функцию немонотонную
Т.е. система полная, если ВСЕ эти уловия выполняются.

 

да пожалуй контрпример громко сказанно.
просто пример базиса из 2 или 3 или 1 функции - достаточно.

 

_blackfox_

Теперь понял Вопрос в том, что считать базисом в этом случае. Можно дать два определения:

1) Минимальная полная система
2) Максимальная система, в которой ни один элемент не может быть выражен через комбинацию других

В случае линейных пространств эти определения совпадают (доказательство кстати очень нетривиальное). В общем же случае они совпадать вовсе не обязаны. Если взять первое определение, то, как и посоветовал CrazyFun, просто приведи полную систему с тремя элементами (например AND, OR, NAND). Если второе, то придется садиться медитировать..

 

_blackfox_
Чтобы построить базис из 4х функций, тебе нужно взять функции каждая из которых обладает не более чем двумя требуемыми свойствами (в противном случае для покрытия не достающих свойств хватит еще 2х функций, то есть всего получится не более 3х). Таких функций всего 4: 0,1,X&Y,X|Y. Но базис из них не получить, так как все они монотонные.

 

Это не правильно,чтобы система из N функций была базисом нужно чтобы выполнялись два условия:
1) систеама должна быть полной (это правда)
2) ни одна функция системы не должна выражаться через другие функции этой системы(в алгебре векторов это звучит как ни один вектор не должен быть линейной комбинацией других)

к примеру, в булевых функциях есть два базиса в каждом из которых по одной функции, это, насколько помню, стрелка Пирса и штрих Шеффера, каждая из этих функций выражает все другие(в свое время дажи были попытки построить на них компы, но суперпохиции оказались слишком сложные)

А в этой задаче, на сколько я понял, необходимо показать что ЛЮБАЯ система из трех функций является полной, тогда как следствие базиса из 4-ех не существует.

 

Немного не понял, каким образом существование базиса из трех функций докажет, что из четырех функций базиса не существует?

Можно подробнее в этом месте?

Спасибо за наводку, буду медитировать

 

Немного помедитировал и нашел неполную систему из трех функций: &, v, импликация.
Все эти функции сохраняют единицу - система не может быть полной

 

_blackfox_

По определению Если ты называешь базисом минимальную (по размеру) полную систему и существует полная система с тремя элементами, то никакая четырехэлементная система по определению уже не может быть базисом. Так как условие минимальности не выполняется.

Определись все-таки, что ты понимаешь под базисом, иначе так и дальше будем все в одну кучу валить. Твое описание

соответствует моему определению 1), так что следуя ему, задачу можно считать решенной.

 

Немного не понял. По твоему, если существует базис из двух функций, то из базиса из трех, четырех и т.д. тоже не будет существовать?
Я ошибся в описании, немного неточно его написал. нужно брать не любые 3 функции, а только те, которые входят в изначальные 4.
Пример: система из &,v,|,1, мы проверяем на полноту &,v,| &,v,1 &,|,1 и т.д., а не любые функции

 

_blackfox_
Чтобы 4 функции образовали базис, у каждой из них должно быть по крайней мере одно свойство, которое отсутствует у остальных(нелинейность, немонотонность и т.д.). Если функция обладает сразу тремя свойствами, то чтобы покрыть оставшиеся 2 нужно не более 2х функций. Поэтому функции обладающие более чем двумя свойствами рассматривать смысла нет. Обладают только двумя свойствами: 0,1,И,ИЛИ.
Все они не самодвойственны.
0 не сохряняет 1.
1 не сохряняет 0.
И,ИЛИ нелинейные.
Но все эти функции являются монотонными, поэтому базис из них не построить.

 

Т.е. хотя бы одна нелинейная, остальные линейные - это чтобы система полноы была? я правильно понял?

Объясни тут подробнее, пожалуйста. Никак не пойму
Все что дальше понятно.