Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Полнота и замкнутость. Примеры функционально полных системСтр 1 из 2Следующая ⇒
Система функций из называется функционально полной, если любая булева функция может быть представлена в виде формулы через функции этой системы. Примеры полных систем. 1) Система – множество всех булевых функций. 2) Система Очевидно, что не каждая система является полной, например, система не полная. Следующая теорема позволяет сводить вопрос о полноте одних систем к вопросу о полноте других систем. Теорема. Пусть даны две системы функций из : , , относительно которых известно, что система полна и каждая ее функция выражается в виде формулы через функции системы . Тогда система является полной. Доказательство. Пусть – произвольная функция из . В силу полноты системы можно выразить формулой над , т. е. . По условию теоремы , , …, . Поэтому в формуле можно исключить вхождения функций , заменив их формулами над : , То есть мы выразили в виде формулы над . Теорема доказана. Опираясь на эту теорему, можно установить полноту еще ряда систем и тем самым расширить список примеров полных систем. 3) Система является полной. Для доказательства возьмем за систему систему 2), а за систему – систему 3) и используем тождество . 4) Система является полной. Доказательство аналогично предыдущему, либо через принцип двойственности. 5) Система является полной. Для доказательства возьмем за систему систему 3), а за систему – систему 5). Тогда , . 6) Система является полной. Для доказательства возьмем за систему систему 3), а за систему – систему 6). Имеем . С понятием полноты тесно связано понятие замыкания и замкнутого класса. Пусть – некоторое подмножество функций из . Замыканием называется множество всех булевых функций, представимых в виде формул через функции множества . Замыкание множества обозначается через . Очевидно, что замыкание инвариантно относительно операций введения и удаления фиктивных переменных. Свойства замыкания: 1) ; 2) ; 3) если , то ; 4) . Класс (множество) называется функционально замкнутым, если . Очевидно, что всякий класс будет замкнутым.Это дает возможность получать многочисленные применения замкнутых классов. В терминах замыкания и замкнутого класса можно дать другое определение полноты, эквивалентное исходному: – полная система, если .
|