Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Функциональная полнота






Как видно из табл.2.1, все функции попарно связаны между собой посредством отрицания, т.е. (і=0, 1, …15). Отсюда следуют зависимости для констант и , для функций одной переменной (двойное отрицание) и для функций двух переменных:

х1х212; х1< х21> х2 ; х1Ä х212 ; х1212;

х121х2; х1> х21< х2 ; х121Ä х2; х1212.

Из этих зависимостей следует, что любую функцию двух переменных, включая константы, можно выразить в аналитической форме через совокупность шести функций, содержащей отрицание и любую из каждой пары (у0, у15), (у1, у14), (у2, у13), (у6, у9), (у7, у8).

Приняв во внимание, что хх=0 и х+х=1, можно сократить комплект элементарных функций до трех: отрицания `х, конъюнкции х1х2 и дизъюнкции х12. Совокупность этих функций положена в основу булевой алгебры, которая преимущественно используется при математическом моделировании цифровых систем.

Система функций, суперпозицией которых может быть представлена любая функция из некоторого множества логических функций, называется функционально полной. Система функций является минимально полной, если удаление из нее любой функции превращает эту систему в неполную. Необходимое и достаточное условие функциональной полноты состоит в том, что выбранные функции должны в совокупности обладать всеми свойствами, приведенными в табл. 2.2 (звездочкой * отмечены свойства, которыми обладает данная функция).

 

Таблица 2.2

 

Функция Обозна-чение Свойства
    Несохра-нение 0 Несохра-нение 1 Несамо-двойст-венность Нелиней-ность Немоно-тонность
Константа 0 Константа 1 Отрицание Конъюнкция Дизъюнкция Импликация Эквиваленция Отрицание импликации Сумма по модулю 2 Штрих Шеффера Стрелка Пирса х х1х2 х12 х1> х2 х12 х1< х2   х1Ä х2 х12 х12     * *     * *   * *   *   *     *   * * * * * * * * * *   * * *   * * *   *     * *     *   * *     * *  

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал