Определить, является ли полной система логических функций {~,ν,0}?

Решение.

Составим таблицу для испытуемых функций по классам: Т0 - сохраняющих 0, Т1 – сохраняющих 1, L – линейных, S – самодвойственных, М – монотонных, проверяя их свойства.

	T0	T1	L	S	M
~	-	-	+	+	-
ν	+	+	-	-	+
0	+	-	+	-	+

Сохранения 0 (Т0):
~ - эквивалентность: 0~0=1→ нуль не сохраняется;
ν – дизъюкция: 0ν0 =0 → нуль сохраняется;
0 – нуль-функция: это тождественный 0 нуль сохраняется.
    
     Сохранение 1 (Т1):
~ : 1?1=1→ единица сохраняется;
ν: 11=1 → единица сохраняется;
0: очевидно, что единица не сохраняется.
    
     Линейность (L):
~ : исходя из изображающего числа #1001, можем записать СДНФ  и преобразовать в многочлен Жегалкина:


функция линейная;
ν:  т.е. функция не линейная.
0: функция линейная.
    
     Самодвойственность (S)
~ :
т.е. функция не самодвойственна:
т.е. функция  не самодвойственна;
0: 0*=1→функция не самодвойственна.
    
     Монотонность (М):
    
                     Не монотонная          Монотонная             Монотонная
    
     Из таблицы видно, что для каждого класса в наборе {~,ν,0}существует хоть одна функция, не принадлежащая ему, следовательно, данная система функций является полной.