67607

Полнота и замкнутость

Лекция

Математика и математический анализ

Система функций из P2 (множества всех булевых функций) называется функционально полной, если любая булева функция может быть записана в виде формулы через функции этой системы

Русский

2014-09-12

131.5 KB

1 чел.

Лекция № 16  (11.04.00)

Полнота и замкнутость

Опр || система функций  из P2 (множества всех булевых функций) называется функционально полной, если любая булева функция может быть записана в виде формулы через функции этой системы.

Пример: 1) Само множество ;

2);

3) - не полна.

Теорема || Пусть даны две системы функций из

, (I)

. (II)

Известно, что система I полная и каждая функция системы I выражается через функции системы II. Тогда система II является полной.

Доказательство || Пусть . В силу полноты сист. I функцию h можно выразить в виде формулы . По условию теоремы

Поэтому

ч. и т.д.

Примеры ||

1)  - полная.

2)  - тоже полная, так как .

3)  - тоже полная.

4)  - тоже полная, так как

,

,

. ((2) – I)

5)  - неполная. Докажем это от противного.

Предположим, что .

Но . Противоречие.

6)  - неполная (сохраняет константу 0 – см. след лекц.).

7)  - неполная (сохраняет константу 1 – см. след лекц.).

6)  -  полная

8)  

тогда взяв в качестве сист. I сист. 2) можно заключить, сист. функций 8) – полная. Тем самым, справедлива

Теорема Жегалкина || Каждая функция из  может быть выражена при помощи полинома по модулю 2 – (полинома Жегалкина):

.

Имеем: число разных сочетаний  равно числу подмн-в мн-ва из n элементов. Каждое aik может принимать одно из 2-х значений {0,1}. Тогда число разных пол. Жег. равно , т.е. равно числу различных булевых функций.

Т. о. получаем единственность представления функций через пол. Жег.

Примеры

Следовательно,

Пока опустим

2 способ T-преобразов. вектора функции

X1

x2

x3

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

3 способ – алгебраических преобразований

Опр. Пусть M – некоторое подмножество функций из P2. Замыканием M называется мн-во всех булевых функций, представимых в виде формул через функции мн-ва M. Обозначается [M].

Замечание. Замыкание инвариантно относ. операций введения и удаления фиктивных перем.

Примеры.

1) M=P2, [M]=P2.

2) M={1,x1x2}, [M] – мн-во L всех линейных ф-й вида

,   (ci{0,1}).

Свойства замыкания:

  1.  [M]=M;
  2.  [[M]]=[M];
  3.  M1M2  [M1][M2];
  4.  [M1M2][M1][M1].

Опр. Класс (мн-во) M называется (функционально) замкнутым, если [M]=M.

Примеры.

  1.  Класс M=P2 функционально замкнут;
  2.  Класс {1,x1x2} не замкнут;
  3.  Класс L замкнут (линейное выражение, составленное из линейных выражений линейно).

Новое определение полноты. M – полная система, если [M]=P2.


 

А также другие работы, которые могут Вас заинтересовать

17521. Розрахунок і побудова цифрових СІХ фільтрів з частотною вибіркою. Фільтрація складених сигналів 338 KB
  Лабораторна робота №5 На тему: Розрахунок і побудова цифрових СІХ фільтрів з частотною вибіркою. Фільтрація складених сигналів Мета роботи Ознайомитись з різними типами цифрових фільтрів навчитись розраховувати різні типи фільтрів і застосовувати їх на практи...
17522. Модуляція та демодуляція сигналів. Амплітудна модуляція складених сигналів 149 KB
  Лабораторна робота №6 На тему: Модуляція та демодуляція сигналів. Амплітудна модуляція складених сигналів Мета роботи Розглянути принципи модуляції сигналів. Проаналізувати особливості різних типів модуляції. Ознайомитись з алгоритмом отримання амплітудної ...
17523. Формування аналогового сигналу з заданими параметрами з допомогою широтно-імпульсного модулятора 416.35 KB
  Тема: Формування аналогового сигналу з заданими параметрами з допомогою широтноімпульсного модулятора. Мета: Ознайомлення з роботою широтноімпульсного модулятора. Завдання:Сформувати вихідний сигнал ШІМ з частотою та формою заданими згідно варіанту: Варіант:...
17524. Безопасность жизнедеятельности, конспект лекций 619 KB
  Конспект содержит основные сведения о взаимодействии человека и среды обитания, человека и технических систем, охране труда. Рассмотрены правовые, организационные вопросы безопасности жизнедеятельности. Дано представление о чрезвычайных ситуациях, мероприятиях и средствах защиты населения при ЧС.
17525. Реалізація аналого-цифрового перетворювача 537.99 KB
  Тема: Реалізація аналогоцифрового перетворювача. Мета: Ознайомлення з принципом роботи аналогоцифрових перетворювачів порозрядного зрівноваження. Завдання: Виміряти значення напруги на виході потенціометра з допомогою АЦП реалізованого на базі ЦАП згідно ва...
17526. Реалізація системи автоматичного регулювання 123.51 KB
  Тема: Реалізація системи автоматичного регулювання. Мета: Ознайомлення з роботою систем автоматичного регулювання зі зворотнім звязком. Завдання:Реалізувати систему регулювання вихідної напруги активного аналогового фільтра нижніх частот другого порядку з ча
17527. Робота з базами даних в Java з використанням OR/M Hibernate 76.5 KB
  Лабораторна робота №1 Тема: Робота з базами даних в Java з використанням OR/M Hibernate. Мета: Навчитись виконувати основні операції при роботі з базами даних в Java використовуючи OR/M Hibernate. Ознайомитись з середовищем програмування Eclipse. Хід роботи: Теоретичні відомості: O/RM ...
17528. Java Servlet та JSP 86 KB
  Лабораторна робота №2 Тема: Java Servlet та JSP. Мета: Навчитись створювати та виконувати Java Servlet та JSPсторінки всередині серверу Tomcat. Хід роботи: Теоретичні відомості: Сервлет Javaобєкт що працює всередині спеціальної програми сервлетконтейнера і застосовується
17529. Розробка Java-програм з Web-інтерфейсом, що працюють з базами даних, на основі фреймворка Spring та Java Persistence API (JPA) 305.5 KB
  Лабораторна робота №3 Тема: Розробка Javaпрограм з Webінтерфейсом що працюють з базами даних на основі фреймворка Spring та Java Persistence API JPA. Мета: Навчитись використовувати шаблон проектування MVC та фреймворк Spring при створенні Javaпрограм з Webінтерфейсом. Навчитись вико...