Табличный способ задания фал

ПУТЕЙ СООБЩЕНИЯ»

(МИИТ)

УТВЕРЖДАЮ:

Директор РОАТ

________ Апатцев В.И._

(название института, подпись, Ф.И.О.)

«_____»______________ 20 г.

Кафедра____Железнодорожная автоматика, телемеханика и связь__________

(название кафедры)

Автор____________Орлов А.В., Боровков Ю.Г.________________________

(ф.и.о.)

Электронные лекции

Теория дискретных устройств автоматики и телемеханики

(название)

_______________Комбинационные устройства______________________________

Специальность/направление 220201.65 Управление и информатика (код, наименование специальности / направления)

_________в технических системах (зУИ)/Автоматизация_и управление______

Утверждено на заседании Учебно-методической комиссии РОАТ Протокол №_________ «____» _____________ 2015 г. Председатель УМК _______________ (подпись, Ф.И.О.)

Утверждено на заседании кафедры   Протокол №_______ «___» _____________ 2015 г.   Зав. кафедрой ___________________ (подпись, Ф.И.О.)

Москва 2011 г.

Лекция 1

Понятие функции алгебры логики

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

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

Способы задания функций алгебры логики

Существует ряд способов задания (описания) ФАЛ. На рис. 2 приведены основные из них.

Табличный способ задания ФАЛ

При табличном способе задания ФАЛ, она представляется таблицей, в которой каждой совокупности значений переменных приведено соответствующее единственное значение функции . Совокупность значений переменных называется набором, а таблица при условии, что значения функции определены для всех возможных наборов из n переменных, носит название Таблица истинности.

Поскольку каждая из входных переменных может принимать только два значения – 0 и 1, то максимальное количество уникальных наборов входных переменных, а, следовательно, и количество строк в таблице истинности, может быть определено по формуле вида:

, (1)

где – основание системы счисления (все переменные могут принимать только одно из двух возможных значений);

– количество переменных, входящих в ФАЛ.

Так, например, для ФАЛ трёх переменных , таблица истинности, не считая строки заголовка, должна содержать строк, для ФАЛ пяти переменных – и т.д.

Таблица истинности функции y трёх переменных может иметь, например, такой вид:

Таблица 1

№ набора

Так как на каждом наборе значений входных переменных функция может принимать одно из двух возможных значений, то, следовательно, при входных переменных возможны различных ФАЛ. Иными словами для переменных можно построить различных таблиц истинности. Например, при одной переменной ( ) возможно задать четыре различных ФАЛ (см. табл.), для – 16, для – 256 и т.д.

Обозначение

Таблица истинности является конечным результатом абстрактного синтеза дискретного устройства и служит исходным документом для различного рода преобразований ФАЛ на последующих этапах синтеза.

Графический способ задания ФАЛ

При графическом способе каждому набору значений переменных ФАЛ соответствует определенная точка -мерного пространства. Координатам вершин -мерного куба соответствуют наборы значений переменных, а их обозначениям – приписаны значения функции на этих наборах. Поскольку каждая из переменных ФАЛ может принимать только два значения: 0 и 1, то каждое ребро, соединяющее две соседние вершины, наборы которых отличаются одной переменной, имеет единичную длину. Поэтому -мерный куб называют единичным.

Количество вершин -мерного куба равно количеству строк в таблице истинности, а количество координатных осей равно количеству переменных. При количестве переменных более 3-х графическое представление ФАЛ затруднительно.

Единичный 3-x мерный куб, соответствующий ФАЛ, заданной ранее таблицей истинности (табл. 1), приведен на рис. 3. Для примера вершина куба на рис. 3 и ячейка табл. 1, содержимое которых описывает один и тот же набор переменных (№6), выделены пунктиром. Аналогичным образом можно сопоставить вершинам куба остальные ячейки таблицы истинности.

Координатный способ задания ФАЛ

При координатном способе ФАЛ задают в виде координатной карты состояний, называемой картой Карно. Карта Карно представляет собой прямоугольную или квадратную таблицу, разделенную горизонтальными и вертикальными линиями на клетки. Общее количество клеток в карте Карно соответствует количеству наборов ФАЛ, следовательно, оно может быть вычислено по формуле (1). Следует отметить, что общее количество клеток карты Карно совпадает с количеством вершин -мерного куба, и количеством ячеек в столбце таблицы истинности. При построении карты Карно для ФАЛ, содержащей не более четырёх переменных, все переменные разбиваются на две группы. Одна из групп переменных определяет выбор строки в карте Карно, а другая – выбор столбца. На пересечении строки и столбца находится клетка, в которую записывается значение функции при соответствующем наборе переменных. Переменные разбиваются на группы таким образом, чтобы в соседних клетках наборы различались только значением одной переменной. В качестве примера на рис. 4 представлена карта Карно для ФАЛ, заданной в табл. 1. В ней ячейка, соответствующая набору переменных № 6 из табл. 1, выделена пунктиром. Содержимое остальных ячеек также однозначно соответствует содержимому ячеек столбца из табл. 1.

Общий вид карты Карно ФАЛ четырёх и двух переменных представлен на рис. 5. У карт Карно двух и четырёх переменных всегда число строк равно числу столбцов, у карт Карно трёх переменных число строк отличается в два раза от числа столбцов. Использование карт Карно вызывает определенные сложности, если количество переменных превышает четыре.

Координатный способ задания ФАЛ используется, как правило, для минимизации ее аналитического выражения.

Числовой способ задания ФАЛ

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

…
…

Тогда функцию можно задать простым перечислением десятичных номеров тех наборов значений переменных, на которых она принимает значение «1». При этом номера наборов находятся путем суммирования произведений значений переменных на их вес по формуле:

. (6)

где – индекс переменной.

Например, ФАЛ, заданная ранее таблицей 1, в числовой форме может быть записана следующим образом:

. (7)

При записи ФАЛ в числовой форме приняты следующие обозначения. В фигурных скобках перечислены номера наборов, при которых ФАЛ принимает единичное значение ( ), разделённые между собой запятыми. За скобкой перечислены входящие в ФАЛ переменные. Существенное значение имеет количество перечисленных вне скобок переменных, а также порядок их перечисления.

Например, если вне скобок перечислены три переменных в порядке, приведённом в (7), то это означает, что указанный в скобках десятичный набор № 3, получается так. Переменные имеют веса: – , – , – . Из формулы (6) следует, что равенство имеет место только в одном случае: , т.е. при следующих значениях переменных: , , и т.д.

Если же числовая форма ФАЛ имеет вид: , то переменные в соответствии со своим индексом имеют те же веса: – , – , – . Поэтому, равенство в формуле (6) будет иметь место при тех же значениях переменных: , .

Аналогично, если ФАЛ записана в форме , то это означает, что во все наборы входит четыре переменных, причём веса распределены следующим образом: – , – , – , – . Тогда ФАЛ принимает единичное значение ( ) на наборе с номером 3, который получается при следующих значениях переменных: , . ФАЛ на наборе с номером 7, который получается при , , также истинна, т.е. принимает значение, равное логической «1».

Числовой способ записи ФАЛ используется в тех же целях, что и таблица истинности, но более компактен и удобен при использовании.

Аналитический способ задания ФАЛ

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

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

1) если в аналитическом задании ФАЛ, участвуют только наборы значений аргументов, на которых она принимает значение 1, то записывается дизъюнктивнаясовершенная нормальная форма (ДСНФ);

2) если в аналитическом задании ФАЛ, участвуют только наборы аргументов, на которых она принимает значение 0, то записывается конъюнктивнаясовершенная нормальная форма (КСНФ).

В свою очередь, после ряда преобразований ФАЛ, заданных в канонических формах, можно получить более простую аналитическую запись функций в виде дизъюнктивных (ДНФ) или конъюнктивных (КНФ) нормальных форм. Если для одной и той же ФАЛ совершенных форм каждого вида может быть только одна, то простых дизъюнктивных и конъюнктивных нормальных форм может быть получено множество в зависимости от цели и методов проведения преобразования ФАЛ, заданных в одной из канонических форм.

Прежде чем рассмотреть методы получения канонических нормальных форм ФАЛ следует сделать пояснения.

а) канонические формы ФАЛ обычно получают на основе таблицы истинности или ее числового выражения;

б) в основе методов получения канонических форм лежит один и тот же принцип – принципсуперпозиции функций. Его суть заключается в том, что в качестве аргументов ФАЛ могут выступать не только двоичные переменные, но и другие ФАЛ. Например, принципу суперпозиции удовлетворяет ФАЛ вида , если переменные и сами являются ФАЛ, имеющими аналитическое выражение , ;

в) при получении обеих канонических форм в качестве аргументов (переменных) используют некие вспомогательные функции, называемые конституентами;

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

ДСНФ

ДСНФ представляет собой дизъюнкцию минтермов:

.

Минтерм – это вспомогательная подстановочная функция, имеющая аналитическое выражение, которая обладает следующими свойствами:

1. в неё входит то же количество переменных, что и в ФАЛ, заданную в виде таблицы истинности (карты Карно).

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

3. набор значений аргументов, на котором минтерм принимает своё единственное единичное значение совпадает с набором значений аргументов, на котором ФАЛ, заданная таблицей истинности или числовым методом, принимает одно из своих единичных значений.

Задача получения ДСНФ может быть разделена на три этапа:

– определение количества минтермов;

– определение аналитического выражения для каждого минтерма;

– составление выражения ДСНФ.

Таблица 5

		Основные элементарные функции алгебры логики ФАЛ
Переменные	Дизъюнкция (логическое сложение, логическое ИЛИ)	Конъюнкция (логическое умножение, логическое И)	Инверсия (логическое отрицание, логическое НЕ)	Сумма по модулю 2 (функция неравно-значности)	Эквивалент-ность (функция равнознач-ности)	Штрих Шеффера (логическое И-НЕ)	Функция Вебба (логическое ИЛИ-НЕ, стрелка Пирса)
Обозначение			,	,	(зависит от одной переменной)		,	,	,
Таблица истинности
Как читается	или	и	не	или или	эквива-лентно	и несовместны	ни ни
Комментарий	Функция дизъюнкции ложна (y=0) только в случае, если ложнызначениявсехпеременных одновременно, иначе функция истинна.	Функция конъюнкции истинна (y=1) только в случае, если истиннызначениявсех переменных одновременно, иначе функция ложна	Функция отрицания истинна, если ложно значение переменной и ложна при истинном значении переменной.	Функция неравно-значности истинна, если х1≠x2и ложна при х1=x2	Функция эквиваленции истинна, если х1=x2и ложна при х1≠x2	Функция штрих Шеффера ложна (y=0) только в случае, если истиннызначениявсехпеременных одновременно, иначе функция истинна.	Функция Вебба истинна (y=1) только в случае, если ложнызначениявсех переменных одновременно, иначе функция ложна
Обозначение логического элемента				m2
Эквивалентная контактная схема

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

Фронтовой контакт тройника реле замыкается в случае, когда обмотка реле находится под током и размыкается, если она обесточена.Тыловой контакт тройника реле замыкается в случае, когда обмотка реле обесточена.

Определение количества минтермов.

Поскольку один минтерм позволяет получить только одно из единичных значений заданной ФАЛ, тогда как она может иметь и более одного единичного значения, то в ДСНФ в общем случае входит столько минтермов , сколько единиц содержится в столбце значений функции таблицы истинности или сколько номеров наборов находится в числовом выражении ФАЛ.

Например, для ФАЛ, заданной таблицей истинности (табл.1), при записи ДСНФ необходимо использовать пять минтермов.

(20)

Причём, минтерм будет задаваться таким образом, чтобы единственная единица получалась на наборе № 3, будет задаваться так, чтобы единственная единица получалась только на наборе № 4 и т.д.

Определение аналитического выражения для каждого из минтермов.

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

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

Например, минтерм , единственная единица у которого будет получаться на наборе № 3 табл. 1, имеет вид: (табл.8), минтерм , единственная единица у которого будет формироваться на наборе № 4 – и т.д.

При вычислении значений минтерма в табл. 8 использовались основные законы алгебры логики. Они приведены в табл. 10.

Составление выражения ДСНФ

После подстановки в формулу (20) аналитических выражений минтермов получим ДСНФ ФАЛ.

Для ФАЛ, заданной табл.1 ДСНФ имеет следующий вид:

.

Таблица 8

№ набора					Комментарий (подстановка значений переменных и вычисление функции)

Примечание: В булевой алгебре конъюнкция при выполнении вычислений имеет приоритет перед дизъюнкцией, поэтому скобки могут быть опущены.

Отличительной особенностью дизъюнктивной совершенной нормальной формы от остальных нормальных форм является то, что во всех её конъюнкциях присутствуют все переменные, входящие в ФАЛ.

КСНФ

КСНФ представляет собой конъюнкцию макстермов:

.

Макстерм – это вспомогательная подстановочная функция, имеющая аналитическое выражение, которая обладает следующими свойствами:

1. в неё входит то же количество переменных, что и в ФАЛ, заданную в виде таблицы истинности или числовым методом.

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

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

Лекция 2

Основные законы алгебры логики