функции. Функции многозначной логики. Функции многозначной логики

• Название: Функции многозначной логики
• Анкор: функции
• Дата: 23.09.2022
• Размер: 44.11 Kb.
• Имя файла: Функции многозначной логики.docx
• Тип: Документы; #691702

Функции многозначной логики

Обозначим E_k= {0,1,2,...,k-1}, k > 2. Пусть (n раз). Рассмотрим отображение , где аргумент .

Определение. Функцией k-значной логики называется функция произвольного фиксированного числа переменных, у которой как переменные, так и сама функция принимают значения из .

Таким образом, функция k-значной логики отображает . Функцию , как и булеву функцию, можно задать в виде таблицы:

0 0 … 0 0 0 … 1 . . . . . . . k-1 k-1 … k-1	. . . . . . .

Обозначим через множество всех k-значных функций (или – k-значная логика), через – множество всех функций из , зависящих от n переменных.

Утверждение 1. | |= (очевидно из табличного задания).

Понятия существенных и фиктивных переменных, понятие равенства функций, формула и реализация функций формулами, эквивалентность формул – всё как в .

Рассмотрим важнейшие функции k-значной логики:

1. Константы 0, 1, 2,..., k-1

2. x+1 (по модулю k)

3. N(x)=k–1–x (отрицание Лукашевича)

4.

5.

6. Максимум , т.е.

7.

8.

9.

Замечание. Функции 6. – 9. коммутативны и ассоциативны. , .

Утверждение 2. Для любой функции из имеет место представление:

, где

.

Доказательство. Пусть . Рассмотрим . Надо показать, что слева и справа стоят одинаковые значения. Вычислим

.

1-й случай. , тогда . Поэтому



.

2-й случай. . Тогда существует i-й разряд такой, что , поэтому . Следовательно,

В итоге получаем

max(0,...,0, . ЧТД

Определение. Система функций называется полной, если её замыкание совпадает с .

Следствие 1. Система {0,1,...,k-1,I₀(x),...,I_k-1(x), max(x,y), min(x,y)} полна в .

Утверждение 3. Система {0,1,...,k-1,I₀(x),...,I_k-1(x), max(x,y), x+1} полна в .

Утверждение 4. Система {max(x,y), x+1} полна в .

Определение. Функция Вебба V_k(x,y)=max(x,y)+1.

Утверждение 5. Система {V_k(x,y)} полна в .

Доказательство. 1) Подставим вместо x,y просто x, тогда

V_k(x,x)=max(x,x)+1=x+1.

2) V_k(x,y)+1+1...+1 (k-1 раз) = max(x,y)+1+...+1 (k раз)=max(x,y).ЧТД

Теорема 1. Существует алгоритм для распознавания полноты конечных систем функций в .

Замечание. Число предполных классов в

.

Теорема 2. Система полиномов полна в , если и только если k –простое.

Теорема 3. Для любого в существует замкнутый класс, не имеющий базиса.

Замечание. Понятие базиса в совпадает с соответствующим понятием в .

Теорема 4. Для любого в существует замкнутый класс со счётным базисом.

Теорема 5. Для любого в существует континуум замкнутых классов.

ОТЛИЧИЯ от

1) В существует счётное множество замкнутых классов.

2) В каждый замкнутый класс имеет конечный базис.

3) В каждая функция представима единственным образом в виде полинома по mod 2.

А как в ?

1) В существует континуум замкнутых классов.

2) В существует замкнутый класс, не имеющий базиса.

3) В существует замкнутый класс, который имеет счётный базис.

4) Система полиномов полна в iff k – простое число.