ЛАФ толық системасы

Кез келген ЛАФ, суперпозиция операциясның көмегімен бір функция классынан алынсы, онда ол міндетті түрде сол классқа тиісті болады.

ЛАФ жүйесінің функцияларын кез келген f функциясының суперпозициясы, R классқа тиісті. Бұл жағдайда функция жүйесі R классында толық функциональды және R калассында базис деп аталады. Егерде базис құраушылардың бір ғана функциясын алып тастайтын болсақ және жүйе функциясы толық емеске айналса, онда базис минимальды болып табылады.

Барлық n айнымалылары мен функциялары, R классының ішінде екені белгілі болады.

ЛАФ системасының бірнеше толық түрін көрсетуге болады: дизъюнкция, конъюнкция функция системасы және қарсылық; дизъюнкция, функция системасы және қарсылық; конъюнкция функция системасы және қарсылық; Шеффер функциясы; Вебба (Пирс) функциясы және т.б. Соңғы төрт система минимальді базиса болып саналады. Толқтық түсінігі мен минимальді базис алгебры логикасының фундаментальды түсінігі болып саналады, үлкен теориялық және қолданбалы мағынаға ие.

Пост-Яблонский теоремасы: функция ситемасы толық болу үшін келесі функциялар жеткілікті және қажет:

1) константа «0» сақтамайтын;

2) константа «1» сақтамайтын;

3) өздік екілік емес;

4) сызықты емес;

5) монотонды емес.

Мысалы: Функция жүйесінің барлық функциясы мен құралы түзу сызықты, ал қисық сызықты функцияны қабылдамайды. Барлық түзу сызықты функцияның жиыны тұйық, не әрбір осы функцияның суперпзициясы да түзу сызықты функция болып табылады. Осыған байланысты осы функция жүйесінің көмегімен барлық логиклық функцияларды көрсетуге болады. Бұл талқылаулар орынды және басқа да теоремаларға қажетті.

Негізгі әдебиеттер: 2[76-105], 3[174-183], 4[123-150]

Қосымша әдебиеттер: 5[95-108],8[9-38, 60-87]

Бақылау сұрақтары:

1. Логикалық функция мен айнымалыларға анықтама беріңіз.

2. Шағын ЛАФ атаңыз және олардың жазылуы.

3. Жегалкин полиномы дегеніміз не?

4. Базис дегеніміз не?

5. ЛАФ функционалді толық системасына анықтам беріңіз.

Дата добавления: 2013-12-14