- Подробности
- Автор: Super User
- Категория: Алгебра логики
- Просмотров: 6949
Определить, является ли полной система логических функций {~,ν,0}?
Решение.
Составим таблицу для испытуемых функций по классам: Т0 - сохраняющих 0, Т1 – сохраняющих 1, L – линейных, S – самодвойственных, М – монотонных, проверяя их свойства.
Сохранения 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}существует хоть одна функция, не принадлежащая ему, следовательно, данная система функций является полной.
Решение.
Составим таблицу для испытуемых функций по классам: Т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}существует хоть одна функция, не принадлежащая ему, следовательно, данная система функций является полной.