Вопрос по дискре

olga1507

Кто-нибудь где-нибудь встречал в литературе подобную задачу?
Дана функция g : E_k^m --> Е_k (k-значная лоника, от m переменных)
Необходимо описать класс функций U(g) \subset {f:E_k^n --> Е_k }, обладающих следующим свойством. Для любой функции f_1 \in U(g существует функция f_2 \in U(g такая что,
справедливо равенство:
g(f_1(x_{1,1},...x_{n,1} ... , f_1(x_{1,m},...x_{n,m} = f_2 (g(x_{1,1}, ... , x_{1,m} ...,g(x_{n,1}, ... , x_{n,m}
Другими словами, описать класс функций, с которыми g можно было бы переставлять.
Класс U(g) всегда содержит все селекторы. Но меня интересуют такие функции g, для которых класс U(g) не тривиален.
Напимер, если n = 1, и g - самодвойственная, то U(g) сожержит функцию (не x).

iri3955

Что такое m,n и k?
У тебя всё ж перепутано.
upd. Понял... Видимо, x_i,j - это x_{i,j}...
А во второй части равенства первый индекс таки пробегает от 1 до n, а не всегда 1

olga1507

значит так.
k - это значность логики.
m - арность функции g
n - арность функции f. Для всего класса U(g) число n одно и тоже.
x_i,j это x_{i,j} (не стал так писать сразу, чтоб не сбивать тех, кто не знает ТеХа
Ну в формуле малость опечетался ... спасибо =) Исправил.

iri3955

Странная задача. Хочется найти максимальный по включению класс? Тогда ещё константы включаются.

olga1507

Да константы нам тоже есть.
Задачка на самом деле возникла из одной проблемы связанной с клетачными автоматами.
Там еще вот какое условие важно. Хотелось бы, чтобы среди функций U(g) была бы функция F, обладающая следующим свойством:
должны существовать x_1, ... , x_r \in E_k r < k, такие что подставляя в F эти значения мы сможем получить любое значение из E_k. В каком-то смысле x_1, ... , x_r - это базис, а F - это так функция через которую мы все выражаем.
в P_2 это условие изменится r = k. (т.к. при r = 1 очевидно ничего не получится)
полюс наложится еще одно хитрое условие.
На самом деле, я не смог в P_2 найти ни одной функции g, отличной от линейной, конъюнкции и дизъюнкции, для которой класс U(g) небыл бы триыиальным (тобишь содержал бы вышеуказанную функцию F). И собственно вопрос то у меня в том и состоит - это условие хоть для какой-нибудь функции g выполняется, кроме как для линейной, конъюнкции и дизъюнкции.
Просто тут на лицо некоторое обобщение понятия двойственности - если в качестве g взять не(x то любая свмодвойственная функйия f_1 будет лежать, т.к. для нее f_2 просто можно взять равной f_1. А тут обобщение - f_2 можно менять, а сопрягаем мы функцией не не(x а некоторой произвольной функцией g.
Оставить комментарий
Имя или ник:
Комментарий: