пользователей: 21276
предметов: 10469
вопросов: 178036
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Элементы булевых функций: основные классы булевых функций: определения, примеры, свойства; теорема Поста. Первая и вторая теоремы Шеннона. Функциональная полнота.

про классы: вопрос 25

Теорема Поста

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

 (Post E.L. The two-valued interactive systems of mathematical logic. – Annals of Math. Studies, v. 5, Princeton Univ. Press. Princeton-London, 1941).

Требования : P2класс  - замкнутый, то Базис - конечный.

Теорема (Пост). Каждый замкнутый класс из P2 имеет конечный базис.

Теорема (Пост). Мощность множества замкнутых классов в P2 - счетная.

Хотя вторая теорема следует  из первой, тем не менее, в доказательстве Поста сначала устанавливается второй факт, а затем  - первый.

Теорема (Пост). Система булевых функций F полна тогда и только тогда, когда она содержит

хотя бы одну функцию, не сохраняющую нуль,

хотя бы одну функцию, не сохраняющую единицу,

хотя бы одну несамодвойственную функцию,

хотя бы одну немонотонную  функцию,

хотя бы одну нелинейную функцию:

 

 


10.06.2014; 17:51
хиты: 217
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь