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.


 

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

47952. Мотивация и стимулирование персонала 135.93 KB
  Стимулирование труда предполагает создание условий (хозяйственного механизма), при которых активная трудовая деятельность, дающая определенные, заранее зафиксированные результаты, становится необходимым и достаточным условием удовлетворения значимых и социально обусловленных потребностей работника
47953. Економічна статистика. Впровадження економічної статистики на підприємства різних типів господарювання 953.5 KB
  Предмет і метод статистичної науки та її завдання в умовах формування ринкової економіки. Статистичне спостереження. Зведення і групування матеріалів статистичного спостереження. Абсолютні та відносні величини. Середні величини. Ряди динаміки. Графічні зображення. Статистика засобів виробництва
47954. Страхування. Конспект лекцій 2.22 MB
  Конспект лекцій Страхування для студентів спеціальностей Банківська справа Фінанси та Облік і аудит Харків: ХБІ УАБС 2005. Конспект лекцій підготовлений відповідно до програми з нормативної навчальної дисципліни Страхування . Складається із вступу мета і завдання дисципліни її місце у навчальному процесі; навчальнометодичного забезпечення яке розкриває сутність та зміст основних питань курсу âСтрахування â з кожної теми; рекомендованої літератури.
47955. Сучасні технології в рекламі та ПР-діяльності 59 KB
  Соціальний ПР може допомогти створити і підтримати позитивний імідж компанії використовуючи спеціальні технології у тому числі благодійність довгострокові соціальні програми. Вони дозволяють підвищити рейтинг компанії і організацій сприяють формуванню позитивної оцінки її діяльності в цілому появи зацікавленості суспільства а також влада в стабільності і процвітанні. У результаті втрачали не тільки громадяни але і компанії чий авторитет поступово знижувався. Щоб відповідати цим очікуванням потрібно планомірний комплексний підхід до...
47956. Сучасні технології в рекламі та ПР-діяльності 955 KB
  Несвоєчасне подання інформації заперечення факту знищення фінансових документів клієнтів і через кілька днів його визнання наполегливі спроби заперечувати свою провину коли ФБР не тільки вже зібрало всі докази але частина з них оприлюднило завдали такого удару по репутації nderson що від нього почали йти клієнти. Ними можуть бути представники виконавчої та законодавчої влади аналітики ринку інвестори й акціонери засоби масової інформації споживачі продукції. Процеси обміну тобто купівлі та продажу товарів характеризуються...
47957. Словотвір як учення про творення слів і загальні принципи їх мотивації 337.5 KB
  Творення відведення це розділ мовознавства який вивчає слова за способами і засобами їх творення та словотвірною структурою. Словотворення зароджується одночасно зі словами базується на них і є засобом їх формування. Розділ мовознавчої науки який вивчає процес творення слів його механізм правила способи моделі словотвірну структуру слова і словотвірну систему мови називається словотвором. Зв'язок словотворення із синтаксисом виявляється в тому що: 1 синтаксична одиниця словосполучення становить для деривації...
47958. ІСТОРІЯ УКРАЇНИ 96.5 KB
  Вступ до курсу Історія України Історія України як наука та навчальна дисципліна Історія України як галузь історичної науки і як навчальна дисципліна. Періодизація історії України. Міжпредметний зв'язок у вивченні історії України.