Пустое и полное (универсальное) множества в логике

1. Я говорил о  полноте системы функций k-значной логики.  В случае k=2 ---  это теорема Поста о полноте системы булевых  функций.  Формулировку вспомните?  Для  k>2 это теорема Яблонского и теорема Слупецкого.

2.  ПЛИСы обычно работают не с битами,  с 8-битовыми словами.  Другими словами, это автоматы-преобразователи над алфавитом из 256 символов.  

3.   Польский логик Сушко в свое время выдвинул тезис (а не доказал теорему!) о том, что, грубо говоря, любая многозначная логика сводима в некотором смысле к двузначной.    В такой "расплывчатой" формулировке тезис, как позднее оказалось, вообще говоря, неверен.  Ситуация значительно сложнее. В общем, вот Вам статья (Вы же логик?), разбирайтесь, если хотите.   https://www.researchgate.net/publication/221107739_Two_Many_Values_An_Algorithmic_Outlook_on_Suszko's_Thesis

Там и про функциональную полноту есть, зачем и почему она появляется в логике.  В общем, для логика там должно быть все понятно, раз уж понятно даже мне, математику.  Обратите внимание,  что сам факт сводимости чего-то к чему-то еще ни о чем не говорит,  в смысле, не дает как правило инструмента для решения конкретной задачи. Например,   теорема Колмогорова-Арнольда говорит, что любую непрерывную функцию можно выразить как композицию функций одной переменной и операции сложения (т.е. функции от двух переменных).  И что, это как-то отменяет математический анализ  функций многих переменных?  Теорема Александрова о том, что топологическое Т_0-пространство гомеоморфно подпространству  счетной степени связного двоеточия, что,  отменяет топологию?  Ведь аксиома  T_0  ---   это самая слабая аксиома отделимости.

4.  При том, что операции над 2^n-значными числами современный компьютер выполняет как над единым блоком, а не побитово.. Т.е. для него входные символы --- это блоки длины n над алфавитом из 2 символов (обычно n=8, 16, 32, 64, ...)  Точнее, ассемблеры современных процессоров "заточены"  на работу с такими блоками, а не с отдельными битами.  В итоге побитовые операции  требуют больше вычислительных ресурсов  чем "побайтовые".  

3.  Докажите, что детерминированная  (т.е. автоматная) функция f(x)=3^x+3x  над 2-символьным алфавитом  транзитивна на словах любой длины.  Т.е. если взять произвольное слово w длины  n  над 2-символьным алфавитом и начать его итерировать с помощью функции  f(x), то получатся  ВСЕ слова длины  n над 2-символьным алфавитом (в каком-то порядке), каково бы ни было n=1,2,3, ..., 10000000, ...  Эту задачу можно (теоретически) свести напрямую к задаче в двоичной логике, вот и попробуйте свести и решить.