misle.ru страница 1
скачать файл
КОНЕЧНАЯ -ПОЛНАЯ СИСТЕМА ФУНКЦИЙ

ЧЕТЫРЕХЗНАЧНОЙ ЛОГИКИ
А.Л. Шабунин
Чувашский государственный университет им. И.Н. Ульянова

математический факультет

кафедра прикладной и дискретной математики

Россия, 425015, г. Чебоксары, пр. Московский, 15

тел.: (8352) 497965, e-mail: alsh@chuvsu.ru

Пусть Pk — множество всех функций k-значной логики, X — множество символов переменных со значениями из Ek=.

Следуя М.М. Глухову [1], определим индуктивно понятие -формулы над непустым классом как выражения вида f(), где f(x1,…,xs+1) — обозначение функции из F, — символ переменной или -формула над F, а . Множество всех функций из Pk, реализуемых -формулами над F, называется -пополнением множества F и обозначается через . При построении -формул используется ограниченная суперпозиция: -формула может подставляться в f(x1,…,xs+1) только вместо x1. Если =Pk, то F называется -полной системой. В [1] найдены конечные -полные системы при k. В [2] для k5 построены -полные системы из двух бинарных операций, а для k=2 доказано отсутствие конечных -полных систем.

Пусть S4 — множество всех подстановок множества E4, — операция сложения по модулю 4, определенная на E4. Определим на множестве E4 бинарные операции i (i=0,1,2,3): 10 2=3, 30 2=1, 11 3=3, 31 3=1, 12 0=3, 32 0=1, 13 1=3, 33 1=1 и a i b=a в остальных случаях.



Теорема. Система функций S4  {+,0, 1, 2, 3} -полна.

Симметрическая группа S4 порождается двумя подстановками и .



Следствие. Система функций1, σ2, +, 0, 1, 2, 3} -полна.
Литература
1. Глухов М.М. Об -замкнутых классах и -полных системах функций k-значной логики // Дискретная математика, 1989. Т. 1, вып. 1. С. 16–21.

2. Чернышов А.Л. Условия -полноты систем функций многозначной логики  // Дискретная математика, 1992. Т. 4, вып. 4. С. 117–130.





скачать файл



Смотрите также: