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

1) проблема диофантовых корней; 2) проблема эквивалентности слов; 3) проблема остановки; 4) проблема разрешимости логики предикатов; 5) проблема нахождения решения задачи коммивояжера. Тест № 6. Неклассические логики и сложность вычислений 1. Конъюнкция и дизъюнкция в трехзначной логике Лукасевича вводятся следующим образом; 1) х8су-тах{х,у), д:у>'=т1п(д:,>'); 2) х8су= xwy= тах(д:,_);); 3) x8Ly= j:xj;(mod 3), .wj;= j:+j;(mod 3); 4) x&_);=(j:v_);)+l(mod 3), xyy= тах(д:,_);); 5) x8Ly= min(l,raax(j:,;>;)), j:yy=max(l, _>;). 2. Число различных функций А;-значной логики, зависящих от п переменных равно: 1) n x t , 2) п") 3) Г; 4^ ^ 3. Рассмотрим А;-значную (А>2) логику Поста, где циклическое отрицание введено как 1х=х+7 (mod fc), а отрицание Лукасевича как N x ^ k - \ - x . Укажите, какое утверждение истинно; 1 ) N{Nx) =х и 1 (1 д:) = д:; 2) N{Nx) и 1 (1 д:) = д:; 3) N{Nx) = д: и 1 (1 д:) .х; 4) N{Nx)Фх и 1 (1 д:) д; 5)Н{Мх) =Л(\х). 4. Рассмотримfc-значнуюлогику Поста, где переменные прини­ мают значения О, Импликация в этой логике вводится сле­ дующим образом; { к - \ , если 0<д:<_);^Л:-1, Л'=>>'=< [(А:-1) - д: + ;у, если 0:^ х т - 1 . 327