<<
>>

ПРЕДСТАВЛЕНИЕ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ

Булевой (переключательной, двоичной) функцией называется двоичная переменная у, значение которой зависит от значений других двоичных переменных (х;, х^ ...,хп), именуемых аргументами: у = у(х,, х2............................................
хп). Задание булевой функции означает, что каждому из возможных сочетаний аргументов поставлено в соответствие определенное значение у. При п аргументах общее число сочетаний N = 2" . Так как каждому сочетанию аргументов соответствует два значения функции (О, 1), то общее число функций Р = 22”. Булевая функция может быть задана на словах, таблично, алгебраически или числовым способом. В табл. 4.2 представлена функция одной переменной у = у(х). При п = 1 существует 4 функции, каждая из которых имеет свое название. Табличное задание функции одной переменной — const ноля, или генератор 0; — повторитель; — инвертор; — const 1; или генератор 1.
Для алгебры логики установлено, что если у = у (z;,z2), где z, и z2— двоичные функции, т. е. z, = zjx^xj, z2 = z2(x3,xj, то y^yiX'.XpXyXj. Операцию замены одной функции другими функциями называют суперпозицией. Эта операция дает возможность с помощью функций малых аргументов получить функции большего числа аргументов. Так, при помощи суперпозиции можно получить функцию с требуемым числом аргументов, используя только функцию двух аргументов. Рассмотрим функцию двух аргументов. По определению существует 16 функций двух аргументов (табл. 4.3). При помощи набора булевых функций двух аргументов можно описать любую цифровую систему. На практике используют не все функции, а лишь те из них, которые методом суперпозиции обеспечивают представление любой другой функции.
Набор таких функций называют функционально полным набором (ФПН). Существует несколько ФПН. В качестве ФПН применяются дизъюнкция, конъюнкция и инверсия. Этот набор называют основным ФПН (ОФПН). Кроме ОФПН, широкое применение получили: ■ функционально-полная система, включающая в себя только одну функцию — функцию Пирса (ИЛИ-НЕ); ■ функционально-полная система, включающая в себя только одну функцию — функцию Шеффера (И-НЕ). При помощи этих функций можно построить любую цифровую систему. Синтез логических устройств в базисе ОФПН состоит из представления этих функций в нормальных формах и минимизации. Табличное задание функции двух переменных Нормальной формой считают представление этих функций посредством суперпозиций вспомогательных функций — минтермов и макстермов. Ч___________________________________________________ - Минтермом называют функцию, которая принимает 1 только при одном значении аргументов и 0 — при других (иногда в литературе используется термин «конституэнта единицы»). Например, для функции двух аргументов имеем: Таким образом, для функции двух аргументов имеем четыре минтерма: Макстермом называют функцию, которая принимает 0 только при одном значении аргументов и 1 — при другом (иногда в литературе используется термин «конституэнта ноля»). Например, для функции двух аргументов имеем: Таким образом, для функции двух ар1ументов имеем также четыре макстерма: При этом, минтерм есть инверсия макстерма: Форму представления функций посредством суперпозиции их мин- термов называют формой представления посредством совершенных дизъюнктивных нормальных форм (СДНФ), а посредством суперпозиции макстермов — посредством совершенных конъюнктивных нормальных форм (СКНФ).
В общем случае форма представления функций посредством суперпозиции их минтермов имеет вид: Для функций одной переменной: Для функций двух переменных: ит. д. Аналогично алгебраическая запись СКНФ имеет вид: Любую функцию можно представить путем суперпозиции их минтермов (СДНФ) или макстермов (СКНФ). Пример. Представим функцию Шеффера путем суперпозиции минтермов (СДНФ) и макстермов (СКНФ). Табличное представление функции Шеффера имеет вид (см. табл. 4.3): Тогда совершенная дизъюнктивная нормальная форма функции Шеффера будет иметь вид: Соответственно СКНФ функции Шеффера: Применив закон де Моргана, получим: Из примеров видно, что данная функция посредством СКНФ представляется значительно проще, чем посредством СДНФ и, следовательно, имеет меньшее число схем для реализации,
<< | >>
Источник: О.А. Акулов Н.В. Медведев. Информатика и вычислительная техника. 2005

Еще по теме ПРЕДСТАВЛЕНИЕ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ:

  1. Представления о функциях журналистики
  2. А МОЖНО ЛЬ АЛГЕБРОЙ ГАРМОНИЮ ПОВЕРИТЬ?
  3. Функции журналистики. Понятие функцию Многообразие социальных и информационных потребностей общества – объективная основа функций журналистики.
  4. Несколько строчек книги, начало которой везде, а конец нигде. Алгебра общения в 12 письмах. Дядя Митя с котом Циником.
  5. “Не язык — функция поэта, а поэт — функция языка”
  6. ESTJ и ENTJ Экстраверты-логики
  7. ISTP и INTP Интроверты-логики
  8. Логики
  9. Логики и этики
  10. Развитие логики
  11. Доминантные логики INTP, ISTP, ENTJ, ESTJ
  12. ГЛАВА 1 Логика трансформации
  13. Марсианская и венерианская логика
  14. ЛОГИКА «5». ХАРАКТЕРИСТИКИ
  15. ПРЕДСТАВЛЕНИЕ
  16. ЛОГИКА «55». ХАРАКТЕРИСТИКИ
  17. Шутка логика
  18. (T) Логика — Этика (F)
  19. ПРЕДСТАВЛЕНИЕ ПАМЯТИ
  20. Хаос вопросов со строгой логикой построения