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

Теорема 6.1. Число различных функций ^-значной логики, зависящих от 7 п переменных, равно к Система функций ^-значной логики (cpi, (р2,..., (рт} называется функциональ­ но полной, если любую функцию / ^-значной логики можно выразить через функции из {(р1, (р2,...,(рт}- Существует и критерий полноты системы функций. Теорема 6.2 (о функциональной полноте, теорема А. В. Кузнецова). Для каждой ^-значной логики существует конечное число замкнутых классов Ki, К2, Кф) таких, что для полноты системы функций ^-значной логики {(Ph(P2,- -,(Pm} необходимо и достаточно, чтобы {(ph(p2,- -,(pm} не содержалась целиком ни в одном из классов Ki, К2, ..., Kr(k). Отметим, что в ^-значных логиках сохраняются многие свойства и резуль­ таты, которые имели место в двузначной логике, но есть и существенные отли­ чия от двузначной логики. Многозначная логика Лукасееича. В отличие от ^-значной логики Поста в ^-значной логике Лукасевича считается, что истинностные значения перемен­ ных образуют следующее множество: Т = \о = -^ j _ ^ ^ ^ \ к-Г к-Г к-Г"''к-1' к-1 }' (6.1) Эти истинностные значения можно интерпретировать как степень (уровень) ис­ тинности. Операции определяются следующим образом: Nx=\-x; x&y=min(x, у); (6-2) xvy=max(x, у). Операции импликации и эквивалентности вводятся по формулам: х^у=тт(\, \+у - х) и хщ>=\- \ х-у | . Отметим, что Лукасевич вводил только отрицание и импликацию, а остальные записывал через них. Для каждого к, к >2, ^-значная логика Лукасевича обозначается как Lk. В последовательности L2, L3, L4, ... этих логик L2 является классической двузнач­ ной логикой, логика L3 совпадает с трёхзначной логикой Лукасевича, рассмот­ ренной в предыдущем параграфе. Предельный случай - логика Lo - является бесконечнозначной логикой, для которой истинностными значениями являются все рациональные числа единичного отрезка [0,1], а операции вводятся по (6.2). Рассматриваются также и другие многозначные логики, для которых ис­ тинностными значениями являются числа отрезка [0,1], но определяемые по 191