Простое высказывание это логическая переменная, а сложное высказывание это логическая функция (ЛФ).

 

Логические связки - объединяют простые высказывания, т.е. логические переменные, в сложные высказывания, т.е. в логические функции. Например, знаками логических связок являются следующие символы: + или, & или,, и т.д.

 

Логическая переменная - логическая (булева) переменная, или простое высказывание, эта такая величина, которая может принимать только два значения: 0 или 1. Например, когда логическая переменная А истинна, то

А = 1, если же ложна, то А = 0.

 

Инверсия или отрицание некоторой логической переменной, например переменной А, это фактически также логическая переменная, принимающая значение обратное значению переменной А, и обозначаемая как А. Если

А =1, то А = 0, если же А =0, то А = 1.

 

Литерал - логическая переменная или ее инверсия (отрицание). Например, переменная А и ее инверсия А - это одна переменная с разными значениями, но два литерала.

 

Набор - совокупность значений аргументов логической функции. Любая логическая функция n аргументов может иметь 2n наборов. Каждому набору значений аргументов приписывается номер, равный двоичному числу, соответствующему значению данного набора.

 

Логическая функция (ЛФ). - Функция f (x 1, x 2,..., x n) называется логической (переключательной), или булевой, если она, так же как и ее аргументы x i, может принимать только два значения: 0 или 1.

Число различных ЛФ n аргументов конечно и равно 2 или 2m, где m = 2n - число наборов n аргументов. Это объясняется тем, что на каждом наборе у ЛФ может быть два значения: 1 или 0. Поэтому каждой ЛФ можно поставить в соответствие m -разрядное двоичное число, а количество различных двоичных m -разрядных чисел равно 2m, следовательно, количество различных ЛФ равно 2m.

Каждой логической функции данного набора аргументов, принято приписывать номер: 0, 1, 2,...

 

Неполность. определенная ЛФ n переменных, это функция, заданная на числе наборов меньшем 2n.

 

Временная булева функция (ВБФ) - это логическая функция

y = (x 1, x 2,..., x n, t), принимающая значение {0,1} при 0 t s -1, где s -количество интервалов автоматного времени. Число различных ВБФ равно .

 

Элементарные функции одной и двух переменных: NOT, AND, OR, XOR,

AND-NOT, OR-NOT, IF...THEN и т.д.

 

Логическое отрицание, или функция НЕ (NOT): f3(x) = x = x. В данном случае функция является инверсией или отрицанием аргумента.

 

Дизъюнкция - логическое сложение, или функция ИЛИ (OR) - это функция, которая истинна тогда, когда истинна хотя бы одна из ее переменных:

f7(x1, x2) = x1 + x2 = x1 x2 = x1! x2.

 

Конъюнкция - логическое умножение или функция И (AND) - это функция, которая истинна тогда, когда все ее переменные одновременно истинны:

f1(x1, x2) = x1 x2 = x1 x2 = x1 & x2\

 

Функция (штрих) Шеффера или функция И-НЕ - это функция, которая ложна тогда, когда все переменные одновременно истины: f14(x1, x2) = x1/x2.

 

Функция (стрелка) Пирса (Вебба) или функция ИЛИ-НЕ - это функция, которая истинна только тогда, когда все переменные ложны: f8(x1, x2) = x1 x2 = x1 O x2.

 

Импликация или функция ЕСЛИ-ТО (IF-THEN) - это функция, которая ложна тогда и только тогда, когда x1 истинно и x2 ложно. Аргумент x1 называется посылкой, а x2 - следствием: f13(x1, x2) = x1 x2.

 

Исключающее ИЛИ (XOR) - это функция неравнозначности, которая фактически реализует процедуру суммирования по модул. 2:f6(x1, x2) = x1 x2 = x1 x2.

 

Суперпозиция - подстановка в логическую функцию вместо ее аргументов других логических функций.

 

Функционально полная система логических функций - система, с помощью логических функций которой, применяя операции суперпозиции и подстановки, можно получить любую сколь угодно сложную логическую функцию.

 

Таблица истинности - таблица, в которой приведены все возможные наборы аргументов некоторой логической функции и соответствующие им значения самой функции.

 

Терм - группа логических переменных в прямой или инверсной форме, т.е. группа литерал, некоторой логической функции, объединенных одним и тем же знаком логической связки: логического сложения или же логического умножения. В терме каждая переменная или ее отрицание встречается только один раз, т.е. в терм может входить или переменная данной функции, или ее отрицание.

 

Ранг терма - количество переменных и их инверсий, т.е. количество литерал, входящих в данный терм. Терм, в который входят все переменные, или их отрцания, данной ЛФ имеет максимальный ранг.

 

Макстерм (H), т.е. дизъюнктивный терм, - это логическая функция, связывающая все переменные в прямой или инверсной форме, т.е. литералы, знаком дизъюнкции.

 

Минтерм (F), т.е. конъюнктивный терм, - это логическая функция, связывающая переменные в прямой или инверсной форме, т.е. литералы, знаком конъюнкци.

 

Конституента единицы (К1) тождественна минтерму.

 

Конституента нуля (К0) тождественна макстерму.

 

Элементарное произведение - конъюнкция нескольких переменных или их отрицаний, т.е фактически минтерм.

 

Элементарная сумма - дизъюнкция переменных, часть которых может иметь отрицания, т.е. фактически макстерм.

 

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

 

Способы представления логических функций: табличный, аналитический, числовой, геометрический (графический).

 

Числовой способпредставления логической функции: в случае СНДФ под знаком суммы (или) перечисляются, заключенные в скобки, номера наборов, на которых функция равна единице. В случае СНКФ - под знаком произведения (или) перечисляются, заключенные в скобки, номера наборов, на которых функция равна нулю. Например, f1 = (1, 3, 5, 6)=

f2 = (0, 4, 7)

 

Геометрический (графический) способпредставления логической функции: например, функция двух переменных представляется в виде квадрата, вершины которого соответству. n комбинациям переменных; функция трех переменных представляется в виде трехмерного куба; а четырех переменных - в виде четырехмерного куба и т.д.

 

Карты Карно (Вейча) - один из способов графического представления логической функции. Используются в процедурах минимизации ЛФ.

 

Нормальная форма аналитического представления логической функции:

НДФ - Fi, где Fi - минтермы любого ранга, включая единичный, - в данном случае знак логического сложения.

НКФ - Hi, где Hi - макстермы любого ранга, - в данном случае знак логического умножения.

 

Совершенная (стандартная или каноническая) форма аналитического представления ЛФ:

СНДФ - Fi, где Fi - минтермы только максимального ранга.

СНКФ - Hi, где Hi - макстермы только максимального ранга.

 

Минимальные нормальные формы представления ЛФ:

МНДФ - НДФ с минимальным числом минтермов, имеющих минимальные ранги, ни один из которых исключить нельзя, или НДФ содержащая наименьшее количество букв (литерал).

МНКФ - НКФ с минимальным числом макстермов, имеющих минимальные ранги, ни один из которых исключить нельзя, или НКФ содержащая наименьшее количество букв (литерал).

 

Минимизация логической функции - получение ее МНДФ или МНКФ для того, чтобы в дальнейшем получить минимальное количество логических элементов в электронной схеме, предназначенной для реализации данной логической функции.

 

Соседние термы - термы в НДФ или НКФ, которые отличаются только одной переменной: в одном терме переменная без отрицаниия, а в другом - с отрицанием.

 

Вхождение одной ЛФ в другую: если некоторая логическая функция равна нулюна тех же наборах, на которых равняется нулю другая функция f, то считается, что функция входит в функцию f.

 

Импликанта - некоторая логическая функция, входящая в данную ЛФ и обращаемая в ноль при наборе переменных, на котором сама ЛФ также равна нулю.

 

Импликанта дизъюнктивная - любой минтерм, или группа минтермов исходной НДФ.

 

Импликанта конъюнктивная - любой макстерм, или группа макстермов исходной НКФ.

 

Простые или э лементарные импликанты - самые короткие произведения или короткие суммы, входящие в данную ЛФ, или импликанта типа элементарного произведения (минтерма) или элементарной суммы (макстерма), никакая собственная часть которого уже не является импликантой данной ЛФ.

 

Собственная часть логического произведения - получается путем исключения из данного произведения одного или нескольких сомножителей.

 

Сокращенная форма аналитического представления ЛФ - дизъюнкция всех ее простых импликант.

 

Тупиковая форма аналитического представления ЛФ - дизъюнкция простых импликант, ни одну из которых исключить нельзя.

 

Накрытие - если на каком-либо наборе аргументов функция f принимает значение а1, а функция на этом же наборе принимает значение а2, то тогда говорят, что функция f на данном наборе накрывает значение а2 функции своим значением а1.

 

Поглощение - A(A + B) = A; A + AB = A.

 

Склеивание - AB +AB = B (A +A) = B; (A + B)(A +B) = A.

 

Неполное склеивание - xy + xy = x + xy + xy.

 

Формула развертывания: x = (x +y)(x +y); (x + y) = (x + y + z)(x + y +z).

 

Теорема (законы) де Моргана - A + B + C = ABC; ABC = A +B +C.

 

Двойственность - если в некоторой ЛФ изменить все знаки операции И на знаки операции ИЛИ, все знаки операции ИЛИ на знаки операции И, все нули на единицы и все единицы на нули, т.е. заменить все переменные на их инверсии, а инверсии переменных на эти же переменные без инверсии, то получается отрицание исходной ЛФ. Законы де Моргана являются одной из иллюстраций свойства двойственности.

 

Логические схемы - это электронные схемы, реализующие определенные логические функции.

 

Комбинационные схемы - это логические схемы, выходной сигнал которых зависит только от состояния входных синалов в каждый момент времени.

 

Последовательностные схемы - (или накапливающие схемы, содержащие элементы с память.) - это логические схемы, выходной сигнал которых зависит как от входных сигналов, так и от состояния схемы в предыдущие моменты времени.

 

Логический элемент (вентиль) - комбинационная логическая схема, реализующая одну из элементарных логических функций: НЕ, И, ИЛИ, И-НЕ и т.д.

 

Логический оператор - элементарная логическая функция, реализуемая соответствующим комбинационным логическим элементом, т.е. вентилем.

 

Положительная логика работы логической схемы - это когда высокому уровню сигнала ставится в соответствие логическая единица, а низкому уровню - логический ноль.

 

Отрицательная логика работы логической схемы - это когда высокому уровню сигнала ставится в соответствие логический ноль, а низкому уровню - логическая единица.

 

Алгоритм - конечная совокупность точно сформулированных правил решения какой-то задачи, или же точно описанная последовательность выполнения некоторых элементарных процедур, необходимая для получения данного результата.

 

Граф-схема алгоритма - алгоритм описанный специальными графическими символами.

 

Цифровой автомат - это дискретный преобразователь информации, способный принимать различные состояния aj(t), переходить под воздействием входных сигналов xk(t), или команд программы решения задачи, из одного состояния в другое и выдавать выходные сигналы yz(t).

Цифровые автоматы могут быть с "жесткой", или схемной, логикой и с логикой, хранимой в памяти. Различают два класса автоматов: асинхронные и синхронные.

 

Синхронный автомат характеризуется тем, что функционирует под управлением тактовых (или синхронизирующих) сигналов (ТС), имеющих постоянну. длительность и постоянну. частоту, если квантование времени выбрано равномерным. Такт времени ti совмещается с фронтом i-того сигнала ТС. Входные сигналы xk(t) могут воздействовать на автомат лишь при наличии сигнала ТС и не изменяются в течение его длительности. Когда рассматривается абстрактный автомат, то считается, что изменение внутренних состояний автомата aj(t) происходит в интервалы времении между смежными ТС, а выходные сигналы yz(t) формируются по фронту очередного ТС.

 

Асинхронный автомат - у этого автомата длительность интервала времени, в течение которого остается неизменным состояние входных сигналов xk(t), является величиной переменной и определяется временем, которое необходимо автомату для установки соответствующих выходных сигналов yz(t) и завершения перехода в новое состояние aj(t). Следовательно, асинхронный автомат должен формировать сигнал о завершении очередного такта, по которому текущие входные сигналы могут быть сняты, после чего может начаться следующий такт, т.е. возможно поступление новых входных сигналов.

 

Функция переходов - определяет состояние автомата a(t + 1) в момент дискретного времени t + 1 в зависимости от состояния автомата a(t) и значения входного сигнала x(t) в момент времени t| a(t + 1) = f[a(t), x(t)].

 

Функция выходов - определяет зависимость выходного сигнала автомата y(t) от состояния автомата a(t) и входного сигнала x(t) в момент времени t:

y(t) = 1 [a(t), x(t)] или y(t) = 2 [a(t)].

 

Граф автомата - графическая схема, состоящая из узлов, соединенных ветвями. Узлы отождествляют внутренние состояния автомата. Каждая ветвь отмечается входным сигналом, вызывающим в автомате соответствующий данной ветви переход, и выходным сигналом, который возникает при этом переходе.

 

Автомат Мили - синхронный автомат, у которого выходные сигналы зависят как от состояния автомата, так и от значения входного сигнала:

y(t) = 1 [a(t), x(t)]; a(t + 1) = f[a(t), x(t)].

 

Автомат Мура - синхронный автомат, выходные сигналы которого в момент времени t однозначно определяются состоянием автомата в этот же момент времени и в явном виде не зависят от значений входных сигналов:

y(t) = 2 [a(t)]; a(t + 1) = f[a(t), x(t)]\

 

Совмещенный автомат (С-автомат) - отличается от автоматов Мили и Мура тем, что он одновременно реализует две функции выходов 1 и 2, каждая из которых характерна для этих автоматов в отдельности.

 

Триггер - элементарный автомат Мура имеющий два внутренних устойчивых состояния, соответствующих логическим 1 и 0, т.е. логический элемент запоминания.

 

ЛИТЕРАТУРА

 

1. А.Я.Савельев. Арифметические и логические основы цифровых автоматов. М.: Высшая школа. 1980.

2. А.Я.Савельев. Прикладная теория цифровых автоматов. М.:Высшая школа. 1987.

3.Е.Н.Вавилов, Г.П.Портной. Синтез схем электронных цифровых машин. М.: Советское радио. 1963.

4. Г.Н.Соловьев. Арифметические устройства ЭВМ. М.: Энергия. 1978.

5. А.Г.Филиппов, О.С.Белкин. Проектирование логических узлов ЭВМ. М.: Советское радио.1974.

6. Я.Будинский. Логические цепи в цифровой технике. М.: Связь. 1977.

7. Ч.Гилмор. Введение в микропроцессорную технику. М.: Мир. 1984.

8. Я.Чу. Организация ЭВМ и микропрограммирование. М.: Мир. 1975.

9. А.М.Шауман. Основы машинной арифметики. Л.: Из-во Ленинградского университета. 1979.

10. В.А.Ильин. Телеуправление и телеизмерение. М.: Энергоиздат. 1982.

11. Б.М.Каган. Электронные вычислительные машины и системы. М.: Энергоатомиздат. 1991.

12. М.А.Карцев. Арифметика цифровых машин. М.: Наука. 1969.

13. С.В.Яблонский. Введение в дискретную математику. М.: Наука. 1986.

14. Ф.Е.Темников, В.А.Афонин, В.И.Дмитриев. Теоретические основы информационной техники. М.: Энергия. 1971.

15. В.Г.Лазарев, Е.И.Пийль. Синтез управляющих автоматов. М.: Энергия. 1978.

16. Д.Кнут. Искусство программирования для ЭВМ т.2. М.: Мир. 1977.

17. Под редакцией А.Уильямса. Применение интегральных микросхем. М.: Мир. 1987.

18. В.В.Гусев, Л.Г.Зеличенко и др. Основы импульсной и цифровой техники. М.: Советское радио. 1975.

19. Под редакцией Г.Хелмса. Компьютеры. М.: Мир. 1986.