пользователей: 24204
предметов: 10946
вопросов: 190752
Конспект-online
оставь конспект в интернете, это поможет тебе в учебе и подготовке к сессии.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

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

про классы: вопрос 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
хиты: 221
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2017. All Rights Reserved. помощь