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

задан 25 Май '17 23:47

1

При любом k существует функция W_k(x,y)=max(x,y)+1 (функция Вебба), через которую выражается любая функция k-значной логики. Сумма здесь по модулю k.

(25 Май '17 23:53) falcao

@falcao любую ли функцию можно представить в таком виде, чтобы она содержала только операции + и - ?

(26 Май '17 0:06) PavLee

@PavLee: если Вы имеете в виду выразить функцию полиномом по модулю k (через сложение и умножение, то есть), то при простом k это возможно, а при составном невозможно. Контрпримером будет функция, равная 1 в нуле и 0 в остальных точках. Её через арифметические операции не выразить.

(26 Май '17 0:08) falcao

@falcao да, я имею ввиду это, то есть если взять 10ти-значную логику, то не любая функция представима, а если 7ми-значную, то любая?

(26 Май '17 0:12) PavLee

@falcao подскажите пожалуйста где об этом можно почитать, или как прийти к таким выводам

(26 Май '17 0:16) PavLee

@PavLee: приходить к этому не надо, потому что доказательства там достаточно нетривиальные. Но это стандартный материал курсов дискретной математики. В учебнике Яблонского посмотрите главу про k-значную логику -- там всё изложено хорошо и понятно.

(26 Май '17 1:30) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×888

задан
25 Май '17 23:47

показан
242 раза

обновлен
26 Май '17 1:30

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru