Справочник от Автор24
Поделись лекцией за скидку на Автор24

Полнота систем булевых функций

  • 👀 375 просмотров
  • 📌 330 загрузок
Выбери формат для чтения
Статья: Полнота систем булевых функций
Найди решение своей задачи среди 1 000 000 ответов
Загружаем конспект в формате pdf
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Конспект лекции по дисциплине «Полнота систем булевых функций» pdf
Полные системы булевых функций. Линейная булева функция f ( x1 , x2 ,...,xn )  c0  c1x1  c2 x2  ...  cn xn c0  c1  f (1,0,...,0) a  0  0, a  0  a с0 , с1,...,сn  0,1 a  1  a, c0  f (0,0,...,0) aa 0 c1  c0  f (1,0,...,0) c0  c2  f (0,1,...,0) … c0  cn  f (0,0,...,1) c2  c0  f (0,1,...,0) … cn  c0  f (0,0,...,1) Метод неопределенных коэффициентов c0  f (0,0,...,0) f ( x, y)  x  y c0  0  0  0, c1  0  (1  0)  0  1  1, c2  0  (0  1)  0  1  1 c0  c1x  c2 y  0  1 x  1 y  x  y Теорема Жегалкина. Всякая булева функция представима в виде полинома Жегалкина: f ( x1, x2 ,..., xn )   (i ,i ,...,i ) xi1 xi2 ...xik c 1 2 k 1. Приводим формулу в СДНФ. 2. Заменяем знаки дизъюнкции на кольцевые суммы. x  y  x  y  xy  3. Избавляемся от отрицаний x  1  x. 4. Используем дистрибутивность конъюнкции относительно кольцевой суммы x( y  z )  xy  xz. 5. Сокращаем парные конъюнкты x  x  0, x  0  x.  ( x, y, z )  x yz  x yz  x y z  x yz  x yz  x y z  ( x  1)( y  1) z  ( x  1) yz  x( y  1)( z  1)=  xyz  xz  yz  z  xyz  yz  xyz  xy  xz  x  z  xyz  xy  x Полная система булевых функций ,,, ,,1 Классы Поста: 1) T0   f ( x1, x2 ,...,xn ) | f (0,...,0)  0 2) T1   f ( x1, x2 ,...,xn ) | f (1,...,1)  1   3) T*  f ( x1, x2 ,..., xn ) | f  f * 4) TM   f ( x1, x2 ,..., xn ) |     f ( )  f ( ) 5) TL   f ( x1, x2 ,..., xn ) | f  c0  c1x1  ...  cn xn Теорема. Классы Поста попарно различны, не пусты и не совпадают с P2 T0 T1 T* TM TL + + + 1 + + + x + + + + x y + Теорема. Классы Поста замкнуты. 1) f ( x1, x2 ,..., xn ), f1( x1, x2 ,..., xn ), f 2 ( x1, x2 ,..., xn ),..., f n ( x1, x2 ,..., xn ) T0 ( x1, x2 ,..., xn )  f ( f1( x1, x2 ,...,xn ), f 2 ( x1, x2 ,..., xn ),..., f n ( x1, x2 ,..., xn )) (0,0,...,0)  f ( f1(0,0,...,0), f 2 (0,0,...,0),..., f n (0,0,...,0))  f (0,0,...,0)  0 Далее самостоятельно.    T0 Теорема (критерий Поста). Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов Поста. , - дизъюнктивный базис Буля. ,,1 - базис Жегалкина Теорема о четырех функциях. Каждый базис содержит не более четырех булевых функций. f0 T0 , f1 T1, f L TL , f M TM , f* T* { f0 , f1, f L , f M , f*} f0 : f (0,0,...,0)  1 f0 (1,1,...,1)  0  f0  T1, f0  TM  { f0 , f L , f*} - полная система f0 (1,1,...,1)  1  f0  T*  { f0 , f1, f L , f M } - полная система
«Полнота систем булевых функций» 👇
Готовые курсовые работы и рефераты
Купить от 250 ₽
Решение задач от ИИ за 2 минуты
Решить задачу
Найди решение своей задачи среди 1 000 000 ответов
Найти

Тебе могут подойти лекции

Смотреть все 938 лекций
Все самое важное и интересное в Telegram

Все сервисы Справочника в твоем телефоне! Просто напиши Боту, что ты ищешь и он быстро найдет нужную статью, лекцию или пособие для тебя!

Перейти в Telegram Bot