Суперпозиция функций алгебры логики
Суперпозиция функций - это образование сложных функций, т.е. в аргументы функций подставляются другие функции, некоторые переменные отождествляются и эта процедура повторяется. Определение. Рассмотрим конечную систему функций алгебры логики . Функция называется элементарной суперпозицией(суперпозицией ранга 1) и обозначается ,если она может быть получена одним из следующих способов. Способ 1. Из некоторой функции , ,переименованием некоторой её переменной. Способ 2. Подстановкой некоторой функции , ,вместо некоторого аргумента одной из функций исходного класса. Если описан класс функций, являющихся суперпозициями ранга r функций из системы F, то класс функций состоит из элементарных суперпозиций функций из , т.е. . Суперпозициямифункций из F называются функции, входящие в какой либо из классов .
Полные системы функций. Понятие базиса.
Определения. Система функций F называется полной, если всякая функция алгебры логики представила посредством суперпозиций функций из системы F. Система функций F называется базисом,если удаление из множества F любой функции приводит к нарушению полноты. Утверждение 1. Система функций является полной. Это следует из Теоремы о разложении функций алгебры логики от n переменных по k=n переменным. Утверждение 2. Системы функций являются полными, так как и . Утверждение 3. Системы функций - штрих Шиффера и стрелка Пирса, являются полными, так как . Утверждение 4. Система функций является полной, так как . Замечание. Очевидно, что все приведенные выше системы функций, кроме системы , являются базисами.
Алгебра Жегалкина. Полином Жегалкина. Теорема Жегалкина. Линейные функции. Алгебра над множеством логических функций с двумя бинарными операциями конъюнкции &и сложения по модулю 2 называется алгеброй Жегалкина. В алгебре Жегалкина, очевидно, имеют место следующие соотношения: x y=y x x(y z)=xy xz x x=0 x 0=x x 1= xVy=xy x y Если в произвольной формуле, выраженной в сигнатуре алгебры Жегалкина, раскрыть скобки и провести возможные сокращения, то получится формула, имеющая вид суммы по модулю 2 элементарных конъюнкций, в которых не содержатся отрицаний. Такая формула называется полиномом Жегалкина. Исходя из оценки числа различных функций алгебры логики и числа различных полиномов Жегалкина, следует Теорема Жегалкина. Для всякой логической функции существует соответствующий ей полином Жегалкина и притом только один. Функция алгебры логики, для которой полином Жегалкина имеет вид (здесь знак суммирования означает суммирование по модулю 2, а параметры , называется линейной. Очевидно, что все функции от одной переменной линейны. Линейными являются, например, функции x yи x y 1=x~y. Для построения полинома Жегалкина можно воспользоваться следующими двумя схемами: Схема 1. Перейти в сигнатуру алгебры Жегалкина (это можно сделать всегда, так как система функций {x&y, x y, 1} ,как это было показано ранее, полна), раскрыть скобки и провести возможные сокращения. Схема 2. Воспользоваться приёмом, который называется методом неопределённых коэффициентов. Этот метод применим лишь тогда, когда функция от n переменных задана своей таблицей истинности. Решается система линейных уравнений с ограничениями, которые задаются через значения функции на двоичных n мерных наборах, и неизвестными - коэффициентами полинома Жегалкина.
Популярное: Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (689)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |