Лекция 2. Основные понятия и определения
Пример. Зададим ПФ трех аргументов f (x1, x2, x3). Так как каждый из аргументов принимает лишь 2 значения, поэтому мы имеем 8 различных комбинаций 3 переменных. Эти комбинации называют набором. Наборы обычно пишут в так называемом естественном порядке, когда наборы принимают значения (000), (001), … Для получения следующего набора прибавляют 1 к правому разряду — применяется как бы сложение… Читать ещё >
Лекция 2. Основные понятия и определения (реферат, курсовая, диплом, контрольная)
В ЭВМ обрабатывается числовая информация, представленная в двоичной системе счисления (0 и 1). Любую схему ЭВМ можно рассматривать как устройство, имеющее n входных сигналов и m выходных. Поступления на входы некоторой последовательности 0 и 1 вызывает появление на выходах вполне определенной последовательности 0 и 1.
В ЭВМ различают два больших класса схем: класс комбинационных (логических) схем и класс конечных автоматов. В комбинационных схемах значение выходных сигналов в момент времени t однозначно определяется входными сигналами в тот же момент времени. В конечных автоматах выходные сигналы определяются не только входными сигналами, но и состоянием схемы (конечные автоматы содержат элементы памяти).
Построение схем ЭВМ решается с помощью аппарата математической логики. При этом используется только самая простая ее часть — алгебра логики. Основным понятием в той части алгебры логики, на которой основывается ее применение к построению схем ЭВМ, является понятие переключательной функции.
Переключательной или булевой функцией называется функция f (x1, , x2, … xn), способная принимать как и ее аргументы x1, …, xn только два значения 0 или 1. Любая переключательная функция (ПФ) может быть задана таблицей ее значений в зависимости от значений ее аргументов. Такая таблица называется таблицей истинности.
Пример. Зададим ПФ трех аргументов f (x1, x2, x3). Так как каждый из аргументов принимает лишь 2 значения, поэтому мы имеем 8 различных комбинаций 3 переменных. Эти комбинации называют набором. Наборы обычно пишут в так называемом естественном порядке, когда наборы принимают значения (000), (001), … Для получения следующего набора прибавляют 1 к правому разряду — применяется как бы сложение чисел. Наборам присваивается номер, равный двоичному числу, соответствующему данному набору. Сопоставляя каждому набору одно из двух значений ПФ, мы и получим таблицу истинности (например, представленную в табл.2.1).
Любая ПФ n аргументов определена на 2n наборах. Число различных ПФ n аргументов равно при n = 1, число различных ПФ равно 4, при n = 2 — 16, при n = 3 — 256, при n =4 — 65 536, при n=5 — примерно 4,3109. Ясно, что прямое изучение ПФ с помощью таблиц истинности возможно для небольшого числа аргументов.
Возьмем какую либо комбинационную схему (КС) (рис. 2.1).
Если значения ПФ отождествить с выходным сигналом КС, а аргументов — с входными сигналами, то ПФ будет описывать процесс преобразования входных сигналов в выходные, т. е.
y1 = f1(x1, x2,…, xn);
y2 = f2 (x1, x2,…, xn);
.
ym = fm (x1, x2,…, xn).
Любые сложные схемы ЭВМ строятся из простых схем, которые называют логическими элементами.
Логическим элементом называется электронная схема, реализующая элементарную ПФ, имеющая количество входов, равное числу аргументов ПФ и только один выход.
При составлении сложных схем используют два приема: последовательное соединение элементов и перестановку входов элементов. Последовательное соединение логических элементов показано на рис. 2.2.
Последовательное соединение двух логических элементов позволяет получить функцию f3 трех аргументов. Подстановка в функцию вместо ее аргументов других функций называется суперпозицией.
Перестановка входов элементов показана на рис. 2.3.
В общем случае функция f4(x1, x2, x3) отличается от функции f3(x1, x2, x3). Замена одних аргументов функции другими или изменение порядка записи аргументов называется подстановкой аргументов.
В алгебре логики доказывается, что из ПФ одного и двух аргументов с помощью операций суперпозиции и подстановки можно получить все ПФ от большого числа аргументов. Практически это означает, что из логических элементов с одним и двумя входами можно построить любую сколь угодно сложную комбинационную схему.
Переключательные функции одного и двух переменных
Рассмотрим некоторые ПФ одного и двух аргументов. В табл. 2.2 представлены все 4 функции одного аргумента.
Таблица 2.2.
x. | f0(x). | f1(x). | f2(x). | f3(x). | |
Функция f0 (x) равно нулю (константа нуля), f3(x) равна единице (константа единицы), функция f1(x) повторяет значение аргумента, т. е. f1(x)=x. Наиболее интересной и имеющей важное значение является функция f2(x), которая принимает значения, обратные значению аргумента- логическое отрицание или функция НЕ и обозначается как:
Все ПФ двух аргументов приведены в табл.2.3.
Таблица 2.3.
х1 | х2 | f0 | f1 | f2 | f3 | f4 | f5 | f6 | f7 | f8 | f9 | f10 | f11 | f12 | f13 | f14 | f15 | |
Функции f0(x1, x2) и f15(x1, x2) не зависят от значений аргументов: f0(x1, x2)=0 и f15(x1, x2)=1. Функции f3(x1, x2), f5(x1, x2), f10(x1, x2) и f12(x1, x2) являются фактически функциями одного аргумента:
f3(x1, x2)=x1, f5(x1, x2)=x2, f10(x1, x2)=x2 и f12(x1, x2)=x1.
Рассмотрим часто встречающиеся ПФ. Функция f1(x1, x2) реализует операцию конъюнкции или логического произведения. Как видим из табл.2.3, функция f1(x1, x2) равна 1, когда и x1 и x2 равны 1. Конъюнкция обозначается как.
f1(x1, x2)=x1 x2 = x1 x2 = x1 x2 (читается x1 и x2).
Функция f7(x1, x2) реализует операцию дизъюнкцию или логического сложения. Функция равна 1, когда или x1 или x2 равны 1. Дизъюнкция обозначается как.
f7(x1, x2)=x1 x2.
Функция f14(x1, x2) реализует операцию отрицания конъюнкции. Из табл.2.3 видно, что когда конъюнкция f1(x1, x1) равна 0, то функция f14(x1, x2) равна 1, а если f1(x1, x2) равна1, то f14(x1, x2) равна 0, т. е. f14(x1, x2)=f1(x1, x2). Эта операция получила название «штрих Шеффера» и обозначается различными способами:
Функция f8(x1, x2) реализует операцию отрицания дизъюнкции. По аналогии с функцией отрицания конъюнкции, из табл.2.3 видно, что f8(x1, x2)=f7(x1, x2). Эта операция также получила отдельное название — «стрелка Пирса» и обозначается следующим образом:
Функция f6(x1, x2) реализует операцию логической неравнозначности или еще ее называют суммой по модулю два. ПФ равна 1, если аргументы x1 и x2 не равны между собой.
Остальные ПФ двух аргументов рассматривать не будем. Вдействительности, для реализации сколь угодно сложной ПФ не обязательно использовать все 16 ПФ двух аргументов. Можно ограничиться некоторым набором, с помощью которого можно строить любые ПФ.
Система ПФ, из которых с помощью операций суперпозиции и подстановки можно получить любую сколь угодно сложную ПФ, называется функционально полной системой переключательных функций (ФПС ПФ). Существует несколько ФПС ПФ:
- — дизъюнкция, конъюнкция и отрицание;
- — отрицание конъюнкции;
- — отрицание дизъюнкции и другие.
Возникает вопрос, какие ФПС ПФ представляют наибольший практический интерес? Выбор ФПС ПФ с технической точки зрения эквивалентен выбору типов логических элементов, из которых может быть построена любая логическая схема. Оказывается, что наиболее удобной для решения задач синтеза схемы является ФПС ПФ, содержащая дизъюнкцию, конъюнкцию и отрицание.