Функциональные полные системы двоичных функций
Подставляя в качестве аргументов одних двоичных функций другие двоичные функции, можно получить новые двоичные функции. Так, например, при подстановке в двоичную функцию z=F(y1,y2) двоичных функций y1=F(x1,x2) и y2=F(x3,x4) получается двоичная функция четырех аргументов z=F(x1,x2,x3,x4). Операция замены аргументов функции другими функциями называется операцией суперпозиции.
Одним из основных положений алгебры логики является следующее: существует такая совокупность простейших двоичных функций, с помощью которой можно синтезировать сколь угодно сложную двоичную функцию.
Такая совокупность двоичных функций, с использованием которых в результате выполнения операций суперпозиции может быть получена сколь угодно сложная двоичная функция любого конечного числа двоичных аргументов, получила название функционально полной системы (ФПС) двоичных функций.
Определим, какие двоичные функции из числа функций, рассмотренных во втором вопросе, образуют в совокупности ФПС двоичных функций. В множестве всех возможных двоичных функций могут быть выделены пять классов двоичных функций. Функции, относящиеся к одному классу, обладают тем свойством, что в результате выполнения с ними любого числа операций суперпозиции могут быть получены только функции, принадлежащие к тому же классу.
К первому классу относят функции, обладающие свойством сохранять нуль. Такие функции принимают нулевое значение, когда все аргументы имеют нулевое значение: F(0,0,...,0)=0. Функции двух аргументов, сохраняющие нуль, отмечены знаком * в соответствующей графе табл. 4.
Ко второму классу относятся функции, обладающие свойствами сохранять единицу. Такие функции принимают единичное значение, когда все аргументы имеют единичное значение: F(1,1,...,1)=1. Функции двух аргументов, сохраняющие единицу, отмечены знаком * в соответствующей графе табл. 4.
К третьему классу относятся монотонные функции. Определение монотонной функции базируется на понятии возрастания набора значений аргументов. Говорят, что происходит возрастание набора значений аргументов, если нулевые значения аргументов заменяются единичными значениями. Для двух аргументов возрастание наборов имеет место при следующих переходах от набора к набору: от 00 к 01, от 00 к 10, от 00 к 11, от 01 к 11, от 10 к 11.
Монотонной называется функция, которая при любом возрастании набора значений аргументов не убывает, т.е. значение функции при возрастании набора значений ее аргументов или сохраняется неизменным (0®0; 1®1), или изменяется из нулевого в единичное (0®1). Монотонные функции двух аргументов отмечены знаком * в соответствующей графе табл. 4.
К четвертому классу относятся самодвойственные двоичные функции. Самодвойственной называется двоичная функция, которая может изменять свое значение всякий раз, когда изменяются значения всех ее аргументов. Для двух аргументов самодвойственная функция изменяет свое значение, если набор значений ее аргументов 00 заменяется набором 11 и набор значений ее аргументов 01 заменяется набором 10. Самодвойственные функции двух аргументов отмечены знаком * в соответствующей графе табл. 4.
Таблица 4
| x1 | x2 | y0 | y1 | y2 | y3 | y4 | y5 | y6 | y7 | y8 | y9 | y10 | y11 | y12 | y13 | y14 | Y15 |
| Сохр. 0 | * | * | * | * | * | * | * | * | |||||||||
| Сохр. 1 | * | * | * | * | * | * | * | * | |||||||||
| Монотон ная | * | * | * | * | * | * | |||||||||||
| Самодвойственная | * | * | * | * | |||||||||||||
| Линейная | * | * | * | * | * | * | * | * | * |
К пятому классу относятся линейные двоичные функции. Двоичная функция n аргументов называется линейной, если она может быть представлена в виде линейного полинома вида:
y=a0 + a1*x1 + a2*x2 + ... +an.*xn,
где a0, a1,…,an - коэффициенты, принимающие значение 0 или 1.
Для двух аргументов полином имеет вид :
y=a0 + a1*x1 + a2*x2.
Все возможные восемь комбинаций значений коэффициентов а0, а1 и а2 образуют восемь линейных функций двух аргументов:
y0=0 + 0*x1 + 0*x2=0; y1=0 + 0*x1 + 1*x2=x2;
y2=0 + 1*x1 + 0*x2=x1; y3=0 + 1*x1 + 1*x2=x1 + x2;
y4=1 + 0*x1 + 0*x2=1; y5=1 + 0*x1 + 1*x2=1 + x2=x2;
y6=1 + 1*x1 + 0*x2=1 + x1=x1; y7=1 + 1*x1 + 1*x2=1 + x1+ x2=x1~x2.
Линейные функции двух аргументов отмечены знаком * в соответствующей графе табл. 4.
В названные пять классов входят не все двоичные функции. Поэтому для образования новой двоичной функции в результате операций суперпозиции нужно, чтобы в ФПС двоичных функций входили :
- хотя бы одна функция, не сохраняющая нуль;
- хотя бы одна функция, не сохраняющая единицу;
- хотя бы одна немонотонная функция;
- хотя бы одна несамодвойственная функция;
- хотя бы одна нелинейная функция.
Из анализа табл. 4 следует, что функции y8 (стрелка Пирса) и y14 (штрих Шеффера) не принадлежат ни к одному из названных пяти классов. Следовательно, каждая из этих функций дает функционально полную систему, состоящую из одной функции.
Функционально полные системы могут быть образованы из двух функций, например: y2 (запрет по х2) и y15 (константа 1); y1 (конъюнкция) и y10 или y12 (инверсия); y7 (дизъюнкция) и y10 или y12 (инверсия).
Функционально полная система функций, состоящая из трех функций - дизъюнкции, конъюнкции и инверсии, называется основной функционально полной системой (ОФПС) двоичных функций. Операции, соответствующие функциям ОФПС, используются в процессе синтеза и анализа схем ЭВМ.
Набор простейших логических функций, позволяющих реализовать любую другую функцию называется логическим базисом (ЛБ). Функции И, ИЛИ, НЕ не являются минимальным ЛБ, т.к. сами могут быть представлены через другие функции, например через ИЛИ -НЕ или И - НЕ.
Следовательно базис "И - НЕ" или "ИЛИ - НЕ" является минимальным логическим базисом.
Таким образом, для понимания работы, анализа и синтеза цифровых устройств, оперируют понятиями алгебры логики - логические переменные, логические функции, логический базис.
Заключение:
1. Автоматом называют любое устройство, осуществляющее преобразование информации.
2. Переменная, которая может принимать два значения (0 и 1), называется двоичной переменной.
3. Двоичная переменная, значение которой зависит от значений других двоичных переменных аргументов, называется двоичной функцией (булевой функцией, переключательной функцией или функцией алгебры логики).
4. Процесс определения значения двоичной функции по значениям ее аргументов называется логической операцией.
5. Совокупность двоичных функций, с использованием которых в результате выполнения операций суперпозиции может быть получена сколь угодно сложная двоичная функция любого конечного числа двоичных аргументов, получила название функционально полной системы (ФПС) двоичных функций.
Замечания и предложения по содержанию лекции
Замечания и предложения по содержанию лекции