2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Сколько функционально полных систем с одной функцией для n п
Сообщение06.06.2008, 08:10 
Сколько функционально полных систем с одной функцией для n переменных, и как это посчитать?
Для двух переменных таких систем две: стрелка Пирса и стрелка Штрихшеффера. Функционально полной системой является система, через которую можно выразить любую другую функцию. Мне необходимо найти сколько существует функционально полных систем с одной функцией для n переменных. Я встречал, что такие функции также называют Шефферовскими.Заранее спасибо за ответы.

 
 
 
 
Сообщение06.06.2008, 09:10 
Аватара пользователя
Что за "стрелка Штрихшеффера"? Наверное, все-таки штрих Шефера?

 
 
 
 
Сообщение06.06.2008, 09:11 
Аватара пользователя
Цитата:
Карл Маркс и Фридрих Энгельс - это не четыре мужика, а два. А Слава КПСС - вообще не мужик!
:lol:
А по сути - вроде любая функция, не входящая ни в один из предполных классов, порождает всё остальное.

 
 
 
 
Сообщение06.06.2008, 09:53 
Аватара пользователя
По-английски такие функции называются sole sufficient operator. В журнале Notre Dame J. Formal Logic была серия статей на их счет:

 
 
 
 
Сообщение06.06.2008, 12:54 
Hillerkhv писал(а):
Сколько функционально полных систем с одной функцией для n переменных, и как это посчитать?

Это задача 6.24 у Гиндикина. Там же имеется ответ и идея решения.

Уважаемый же maxal, кажется, порекомендовал материалы про обобщение штриха Шеффреа на n-значные логики, а не на функции n переменных 2-значной. Впрочем, не уверен, не вчитывался :oops:

 
 
 
 
Сообщение06.06.2008, 16:23 
Аватара пользователя
Вот коротенькая рецензия на первые три статьи:

T. C. Wesselkamper defines a ternary propositional connective $S$ which is asserted to be functionally complete in every finite-valued logic. G. J. Massey remarks that there is an evident error in the proof; it is not $S$, but the set consisting of $S$ and all the constants, that is complete. The correction by Wesselkamper clarifies the original to yield a correct result.

Как я понимаю, every finite-valued здесь в частности включает в себя и обычную двузначную логику. Но к тому же здесь для полноты еще требуются константы.
С четвертой аналогично:

Let $E(k)=\{0,1,\cdots,k-1\}$. T. C. Wesselkamper proved that a particular Markov operator $S$ defined on $E(k)$ is complete with constants (a function is said to be complete with constants if the set consisting of the function and all the constant functions is complete). In this short note we give an alternative proof of the completeness.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group