Дискретная математика. Шефферова функция

[usmanovamir]

Помогите пожалуйста, дискретную математику прошел на 1-ом семестре, а теперь начались задачи по программированию на дискретную математику.
Не могу разобраться с $k$-значной логикой.
Задача такая: Во входном файле задана функция от 2-х переменных. Является ли она шефферовой?
Объясните пожалуйста, что такое шефферова функция в $P_k$, не в $P_2$?
Ну и каким образом можно проверить, является ли она шефферовой?
Алгоритмы писать не надо, просто подскажите идею, с программирование сам разберусь. Спасибо!

Deggial: формулы поправил. Все формулы и термы оформляйте $\TeX$ом, инструкция тут

[iifat]

Поглядел вот сюда. Ничего почти не понял, но такое чувство, что вопрос в общей постановке не решён, нет?

[usmanovamir]

iifat в сообщении #831423 писал(а):

Поглядел вот сюда. Ничего почти не понял, но такое чувство, что вопрос в общей постановке не решён, нет?

Тоже, почти ничего не понял, но согласен, в этой диссертации толком этом вопрос не решён.

-- 28.02.2014, 21:12 --

Надо было хорошо слушать лекции, и все записывать. И как на зло, нет в ташкентском филиале преподов по дискретке

[Xaositect]

Шефферова функция - это функция, которая в замыкании порождает все $P_k$.

Нужно просто порождать все возможные функции от 2 переменных, если удастся получить все, то функция Шефферова, если нет - то нет. Подробнее см. Яблонский, Введение в дискретную математику, глава 2, §3 (Распознавание полноты. Теорема о полноте)

iifat в сообщении #831423 писал(а):

Поглядел вот сюда. Ничего почти не понял, но такое чувство, что вопрос в общей постановке не решён, нет?

Не имеет отношения к вопросу, там рассматривается более сильное понятие замыкания.

[usmanovamir]

Xaositect в сообщении #831480 писал(а):

Шефферова функция - это функция, которая в замыкании порождает все $P_k$.

Нужно просто порождать все возможные функции от 2 переменных, если удастся получить все, то функция Шефферова, если нет - то нет. Подробнее см. Яблонский, Введение в дискретную математику, глава 2, §3 (Распознавание полноты. Теорема о полноте)

iifat в сообщении #831423 писал(а):

Поглядел вот сюда. Ничего почти не понял, но такое чувство, что вопрос в общей постановке не решён, нет?

Не имеет отношения к вопросу, там рассматривается более сильное понятие замыкания.

Спасибо! Но всё равно, не совсем понятно. Можете поподробнее про порождение всевозможных функций от 2-ух перемнных.

-- 02.03.2014, 16:28 --

И, поподробнее про задачу: во входном файле даны $k^n$ чисел, являющихся значениями функции на всех наборах. По этим значениям и надо определить, является эта функция шефферова.