Математическая логика и теория алгоритмов

Рассмотрим множество высказываний (переменных), каждое из которых может принимать одно из значений - 1 . На множестве введенных Л-значных высказываний вводятся операции: 1) x=x+l(mod к) - циклическое отрицание или отрицание Поста, здесь + - сложение по модулю к; 2) Nx-k-l-x - отрицание Лукасевича; если хФт , Функция 1т{х) называется иногда характеристической функцией и обозначается как х"'; 4) х& у=т1п(д:, у )~ конъюнкция; 5)x v j^max(x, jh) - дизъюнкция; 6) хху= лху (mod к) ~ произведение по модулю к; 7) х-+у~х-+у (mod к) — сумма по модулю к; \ к - \ , если 8) х=> v=^ [(А:-1)-х +J', если О < 3; :< х ^ й:- 1 . Вводятся и другие операции. Используя введенные операции, можно строить суперпозиции этих функций, исследовать их свойства. Также определяют нормаль­ ные формы и можно доказать следующее соотношение: где дизъюнкция берется по всевозможным наборам значений (аьйг, переменных (хьхз, Легко доказать теорему: Теорема 5.1. ЧиcJЮ различных функций А:-значной логики, 1гп зависящих ОТ « переменных, равно А: , если X = т, 4 , (^1) & а„), 192