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

Легко проверить, что для циклического отрицания не имеет места закон двойного отрицания, а имеет места закон тройного отрицания, т.е. ~(~(~А)) равносильно А. Также для циклического отрицания не имеет место закон ис­ ключённого третьего, а имеет место закон исключённого четвёртого, который означает, что Av(~A)v(~(~A)) всегда истинно. Для диаметрального отрицания, как уже указано, сохраняется закон двой­ ного отрицания, но не имеет места закон исключённого третьего. Имеется и много других как отличий, так и совпадений этой логики и обычной двузнач­ ной логики. § 2. Многозначные логнкн Конечнозначная (к-значная, к^) логика Поста является обобщением двузначной логики, т.е. при к=2 получится двузначная логика. Рассмотрим множество высказываний (переменных), каждое из которых может принимать одно из значений 0,1,2,.. .,^-1. На множестве введённых к - значных высказываний вводятся операции: 1) X =х+\ (mod к) - циклическое отрицание или отрицание Поста, здесь + - сложение по модулю к; 2) Nx=k-\-x - отрицание Лукасевича; [к-1, если х = т, 1>)1т(х) = \ т=0,\,...,к-\. [ О, если хФт, Функция Ifn(x) называется иногда характеристической функцией и обозна­ чается как х™; 4) x&y=min(x, у) - конъюнкция; 5) X vy=max(x, у) - дизъюнкция; 6) х>у= х>у (mod к) - произведение по модулю к\ 7) х+у=х+у (mod к) - сумма по модулю к; \к-1, если О < X < у < к -1, 8)х ^ у (к -1) - X + у, если О < у < X <к-1. Вводятся и другие операции. Используя введённые операции, можно строить суперпозиции этих функ­ ций, исследовать их свойства. Также можно вводить нормальные формы и до­ казать следующее соотношение: f(xi,...,xn)= V I (Xi)&1^2(^2 )-hJ^n)& f(ai,a2,...,an), (clj ,q2 ,.•• jclyi) где дизъюнкция берётся по всевозможным наборам значений (ai,a2,... ,ап) пере­ менных (Xi,X2, ... ,XrJ. Легко доказать теорему: 190