Часть 3. Математические модели

Оценка числа правильных семейств функций $ k $-значной логики

А. В. Галатенко

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: Правильные семейства функций являются удобным средством для задания больших параметрических классов квазигрупп и $d$-квазигрупп. К.Д. Царегородцевым было установлено, что в булевом случае правильные семейства находятся в естественном взаимно-однозначном соответствии с одностоковыми ориентациями булева куба. Число таких ориентаций было оценено И.Матоушеком. В работе представлено обобщение нижней оценки Матоушека на случай логики произвольной значности, некоторые следствия из этого обобщения, а также показано, что свойство правильности является редким — доля правильных семейств размера $n$ в классе всех семейств из n $n$-арных функций, для которых одноименная переменная фиктивна, стремится к $0$ при $n \rightarrow \infty $.

Ключевые слова: правильные семейства функций, функции $k$-значной логики, гиперграф, паросочетание