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

Система функций А:-значной логики {ф1,ф2,.-.,<рот} называется функционально полной, если любую функцию / А:-значной логики можно выразить через функции из {фьф2,"->фт}. Существует и критерий полноты системы функций. Теорема 5.2 (о функциональной полноте, теорема! А. В. Кузнецова). Для каждой А:-значной логики существует конечное число замкнутых классов К\, Кг, К ф таких, что для полноты сис­ темы функций А:-ЗНаЧНОЙ логики {фьф25-"=фт} необходимо и доста­ точно, чтобы {ф1,ф2,...,ф„} не содержалась целиком ни в одном из классов К),Къ Kr(k)- ' | Отметим, что в А:-значных логиках сохраняются многие свойства и результаты, которые имели место в двузначной логике, но есть и существенные отличия от двузначной логики. Многозначная логика Лутсевича. В отличие от А:-значной ло­ гики Поста в А;-значной логике Лукасевича считается, что истинност­ ные значения переменных образуют следующее множество; ^ О I 2 к - 2к - \ 1 " \ к-1' к - 1 ' к-1 J Эти истинностные значения можно интерпретировать как степень (уровень) истинности. Операции определяются следующим образом: Nx=\-x; х&, >^min(x, у); (5.2) xv;y=max(x, у ) . Операции импликации и эквивалентности вводятся по форму­ лам: A-=>>^min(l, - х) и xs j=l - l х-у 1. Отметим, что Лукасевич вводил только отрицание и импликацию, а остальные записывал через них, 193