Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

10. Указать, какая из перечисленных проблем является алгоритмически разре­ шимой: 1) проблема диофантовых корней, 2) проблема эквивалентности слов, 3) проблема остановки, 4) проблема разрешимости логики предикатов, 5) проблема нахождения решения задачи коммивояжёра. Тест по неклассическим логикам и сложности вычислений (тест Ж» 6) 1. Конъюнкция и дизъюнкция в трехзначной логике Лукасевича вводятся сле­ дующим образом: 1) х&у=тах(х,у), xvy=min(x,y); 2) х&у= min(x,y), xvy= тах(х,у); 3) х&у= xxy(mod 3), xvy= x+y(mod 3); 4) x&y=(xvy) + l(mod3), xvy= max(x,y); 5) x&y= min(l, max(x,y)), xvy= max(l, min(x,y)). 2. Число различных функций к - значной логики, зависяш,их от п переменных равно: 1) п><к 2) п" 3) Г 4) к^ 5) 3. Рассмотрим к - значную (к>2) логику Поста, где циклическое отрицание вве­ дено как —1 х=х+1 (mod к), а отрицание Лукасевича кшМх=к-1-х. Указать, какое утверждение истинно: \)N(Nx) = X и —if —iXy) = x; 2) N(Nx) ^x и —if —iXy) = x; 3)N(Nx) =x и —i(—x) ^x; 4) N(Nx) ^x и —if —iXy) 5) N(Nx) = -n(-^). 4. Рассмотрим к - значную логику Поста, где переменные принимают значения О, 1, ... к-1. Импликация в этой логике вводится следуюш,им образом: (к -1, если О < X < у <к -1, х^у=< [(к -1 )-х + у, если О < у < X <тп- 1. Пусть к=3. Обозначим значения О, 1,и 2 через О, Уг и 1 соответственно. Укажи­ те, какое из следуюш,их утверждений истинно: 1) эта импликация совпадает с дизъюнкцией логики Рейхенбаха; 2) эта импликация совпадает с импликацией логики Бочвара; 3) эта импликация совпадает с импликацией логики Клини; 4) эта импликация совпадает с импликацией логики Гейтинга; 5) эта импликация совпадает с импликацией логики Лукасевича. 5. Пусть задана лингвистическая переменная, описываемая набором: