Способы задания булевых функций: 12.1. Способы задания булевой функции

Лекция 03. Определение и способ задания булевых функций

Булевой функцией от n аргументов называется однозначное отображение n – мерного булева куба на одномерный булев куб.

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

1. Табличный

X1 X2 X3 … XN	F(X)
0 0 0 0 0 0 0 0 0	G1
…	Gi
1 1 1 1 1 1 1 1 1	Gn

Gi — значение функции от данных аргументов.

Порядок возрастания векторов по мере возрастания их номеров называют лексикографическим.

2. Векторный

F = (g1…gn)

3. Геометрический

Единичным вектором для данной функции называется тот вектор, значение функции на котором равно 1.

Носителем данной функции – совокупность всех единичных векторов этой функции (Nf – носитель функции f)

На векторах, помеченных звездочкой, функция обращается в 1.

Nf = {001, 011, 100, 110} = [1,3,4,6] [] – указаны номера векторов.

3. В виде формулы.

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

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

Фиктивные переменные у функции можно добавлять и исключать.

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

Строим таблицу функций при n = 1.

X	0	X	_ X	1
0	0	0	1	1
1	0	1	0	1

Таблица всех элементарных булевых функций, применяемых в записи формул

X	Y	0	&	_____ Y®X	X	___ X®Y	Y	+	V	¯	~	_ Y	X ®Y	_X	Y®X	/	1
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Все эти функции от двух аргументов мы и будем называть элементарными булевыми функциями.

Основными элементарными функциями являются конъюнкция, дизъюнкция и отрицание.

Элементарные булевы функции удовлетворяют всем аксиомам булевой алгебры.

Суперпозиции булевых функций

Ф = {ф1…фk}

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

1. Переименование какого-нибудь аргумента в одной из функций системы (возможно отождествление аргумента).

2. В одну из функций системы вместо любого аргумента ставится значение любой функции из этой системы.

Ф1 = {Y…xn}

Фi = (x1 … фj(x1…xn) … xn)

Ф(1) – множество всех элементарных суперпозиций из системы Ф.

Ф(k+1) – множество всех элементарных суперпозиций из систему Фk.

Функция g называется суперпозицией функций из системы, если

$ N : g Î Фn

Это означает, что g можно получить из функции системы Ф, применяя конечное число раз операцию элементарной суперпозиции.

Конкретное выражение суперпозиции будем называть формулой над системой Ф.

G = Fф

Суперпозиция элементарных булевых функций – формула.

Для удобства записи договоримся, что отрицание – самая сильная операция. Следующая – конъюнкция, а остальные – равносильны.

_ _

X+Y = XY V XY

_ _

X ~ Y = XY V XY

__

X ® Y = X V Y

_ _

X ¯ Y = X Y

< Предыдущая		Следующая >

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

Похожие презентации:

Элементы комбинаторики ( 9-11 классы)

Применение производной в науке и в жизни

Проект по математике «Математика вокруг нас. Узоры и орнаменты на посуде»

Знакомство детей с математическими знаками и монетами

Тренажёр по математике «Собираем урожай». Счет в пределах 10

Методы обработки экспериментальных данных

Лекция 6. Корреляционный и регрессионный анализ

Решение задач обязательной части ОГЭ по геометрии

Дифференциальные уравнения

Подготовка к ЕГЭ по математике. Базовый уровень Сложные задачи

Способы задания логических функций
1. Табличный
2. Алгебраический, например дизъюнктивная
нормальная форма (ДНФ) — логическая сумма
элементарных логических произведений:
F (A, B, C) = AB + AC
3. Числовой (под знаком суммы перечисляются
номера наборов, на которых функция равна «1»)
F = Σ (1,2)
Правило перехода от таблицы к
совершенной ДНФ
• Для каждого набора, на котором функция равна
единице, записывается элементарное
произведение всех аргументов.
Причём если аргумент в этом наборе принимает
значение 0, то пишется его отрицание.
Затем производится логическое сложение
полученных элементарных произведений.
Примечание: совершенная ДНФ (СДНФ)
содержит все переменные или их отрицания,

например:
_
_
_
• F (A, B, C) = АВС + АВС +АВС
Пример перехода от таблицы к СДНФ
• Переход от табличного представления булевой
функции к алгебраическому.
_
_
F (A, B) = АВ + АВ = А
В
Построение комбинационной схемы
• На основе полученной структурной формулы
построим комбинационную схему, состоящую из
логических элементов И, ИЛИ, НЕ.
Логический элемент «НЕ»
Отрицание
(Операция «НЕ»)
Х-ка передачи и быстродействие
• 6 элементов «НЕ»
• (К155ЛН1)
http://myrepititor.ru/electronics/82-Osnovnye_xarakteristiki_i_parametry_logicheskix_eleme.html
Логические элементы «2И» и «2ИЛИ»
Схема на логических элементах
• DD1 — К155ЛН1
• DD2 — К155ЛИ1
• DD3 — К155ЛЛ1
• Выводы 7 DD1-DD3 – общ.
• Выводы 14 DD1-DD3 – +5В.
Карты Карно
• Карта Карно четырех переменных.
____
ABCD
__ _
ABCD
___
ABCD
_ _
ABCD
__
ABCD
___
ABCD
_
ABCD
__
ABCD
__
ABCD
_
ABCD
ABCD
_
ABCD
_ __
ABCD
_ _
ABCD
_
ABCD
_ _
ABCD
Правила применения закона склеивания
• 1. Если единицами заполнены две соседние
строки или два соседних столбца, либо две
строки или два столбца, расположенные по
краям карты, то соответствующие восемь
слагаемых четвертого ранга можно заменить
слагаемым первого ранга (ранг — число
переменных, входящих в слагаемое).
Правила применения закона склеивания
• 2. Если единицами заполнена одна строка или
один столбец, или четыре угловых квадрата,
или четыре квадрата, которые, в свою очередь,
составляют квадрат, то соответствующие четыре
слагаемых четвертого ранга заменяются одним
слагаемым второго ранга.
Правила применения закона склеивания
• 3. Если единицы расположены в двух соседних
квадратах, в том числе и находящихся на
концах строки или столбца, то соответствующие
два слагаемых четвертого ранга склеиваются,
превращаясь в одно слагаемое третьего ранга.
Пример применения карты Карно
• Дана функция
F (A, B, C, D) = S (0, 3, 4, 5, 7, 8, 10, 11, 14, 15).
В виде структурной формулы она выглядит
следующим образом:
____
__ __ _
_ _
_ ___
• F = ABCD + ABCD + ABCD + ABCD + ABCD + ABCD +
_ _
_
_
• + ABCD + ABCD + ABCD + ABCD.
Пример применения карты Карно
• Нанесем
эту функцию на карту Карно и,
произведя все возможные склеивания, получим
функцию
___ _ _
• F = AC + CD + BCD + ABC,
Задача
Построить схему на логических элементах
• Задана булева функция
• Задание:
• 1. Построить схему на логических элементах
НЕ, И, ИЛИ.
2. Выбрать серию ИС ТТЛ.
3. Проставить цоколевку.
4. Определить таблицу состояний.
5. Представить функцию числовым способом.
6*. Минимизировать функцию с помощью карты Карно.
Список использованных источников и
литературы
1. Нарышкин А.К. Цифровые устройства и
микропроцессоры: учеб. пособие для радиотехн.
специальностей вузов / А. К. Нарышкин. — М. :
Академия, 2006. — 317 с.
2. Пухальский Г.И., Новосильцева Т.Я.
Проектирование дискретных устройств для
интегральных микросхем: Справочник. — М.: Радио и
связь, 1990. — 304 с.
3. Пухальский Г.И., Новосельцева Т.Я.
Проектирование цифровых устройств: Учеб.
пособие. – СПб.: Изд-во «Лань», 2012. – 896 с.
4. Одинец А.И. Цифровые устройства. Конспект
лекций. – Омск: ОмГТУ, 2009.-64 с.
5. Открытые источники Internet

English     Русский Правила

п\) возможные комбинации переменных. Эти функции будут принимать на выходе только 0 или 1. Вот пример булевой функции: f(a,b,c) = a X b + c. Эти функции реализованы с помощью логических вентилей.

Цифровая схема f(a,b,c)

Таблица истинности функции

	б	с	ф(а,б,в)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Существует способ реализации функций в канонической форме, минимальной форме функции. Например, если бы нам пришлось реализовать функцию с таблицей истинности функции f. Сначала мы бы сформировали термы, в которых функция имеет значение 1, с единственной возможной комбинацией для каждого терма. Термин будет равен 1 для одной комбинации записи и 0 для других. Для этого мы будем использовать вентиль И и сделать эту комбинацию со всеми входами, равными 1 в вентиле И. Тогда функция будет суммой всех членов. Таким образом, условия таблицы истинности будут:

Условия ∑

a	б	в	ф(а,б,в)	Условия ∑
0	0	0	0	0
0	0	1	1	!а Х !б Х в
0	1	0	0	0
0	1	1	1	!а Х б Х в
1	0	0	0	0
1	0	1	1	а Х !б Х в
1	1	0	1	а Х б Х !с
1	1	1	1	а Х б Х в

\[\begin{split}f (a,b,c) &= (!a X !b X c) + (!a X b X c) + (a X !b X c) + (a X b X !c) + (a X b X c) \\ &= !b X c X ( a + !a) + b X c X ( a + !a ) + a X b X !c \\ &= !b X c + b X c + a X b X !c \\ &= с + а Х б Х !с \\ &= (c + a X b) X ( c + !c) = a X b + c\end{split}\]

С помощью законов булевой алгебры делается упрощение для реализации цифровой схемы с меньшим количество ворот. Есть еще один способ реализовать каноническую функцию, заключающийся в реализации инвертированной функции, а затем снова инвертировании и использовании законов Де Моргана для получения произведения термов. Это двойная форма обобщения. Теперь функция будет произведением терминов, и термины теперь будут иметь значение 0 для одной комбинации входных данных и 1 для каждой другой комбинации.

Условия ∏

a	б	с	!ф(а,б,в)	Условия	ф(а,б,в)	Условия ∏
0	0	0	1	!а Х !б Х !с	0	а+б+в
0	0	1	0	0	1	1
0	1	0	1	!а Х б Х !с	0	а + !б + в
0	1	1	0	0	1	1
1	0	0	1	а Х !б Х !с	0	!а + б + в
1	0	1	0	0	1	1
1	1	0	0	0	1	1
1	1	1	0	0	1	1

\[!f (a,b,c) = !a X !b X !c + !a X b X !c + a X !b X !c\]

\[\begin{split }!!f = f &= !( !a X !b X !c + !a X b X !c + a X !b X !c) = !( !a X !b X !c) X !( !a X b X !c) X !( a X !b X !c) \\ &= (a + b + c ) X (a X !b X c) X (!a X b X c) \\\end{split}\]

Работая с терминами, мы получаем основную форму: f = a X b + c.

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

Представление булевых функций — GeeksforGeeks

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

Канонические и стандартные формы –
Любая двоичная переменная может принимать одну из двух форм или . Булева функция может быть выражена в терминах двоичных переменных. Если все бинарные переменные объединяются вместе с помощью операции И, то получается общее количество комбинаций, поскольку каждая переменная может принимать две формы.
Каждая из комбинаций называется minterm или стандартный продукт . Минтерм представлен где — десятичный эквивалент двоичного числа, обозначенного минтермом.
Важное примечание — В minterm двоичная переменная не имеет штриха, если переменная равна 1, и штрихуется, если переменная равна 0, т. е. если minterm равен, то это означает и .
Например, для булевой функции с двумя переменными minterms –

Аналогичным образом, если переменные объединяются вместе с операцией ИЛИ, то полученный терм называется maxterm или стандартной суммой . Максимальный термин представлен где — десятичный эквивалент двоичного числа, обозначаемого максимальным термином.

Важное примечание — В maxterm двоичная переменная не имеет штриха, если переменная равна 0, и штрихуется, если переменная равна 1, т. е. если maxterm равен, то это означает и .
Например, для логической функции с двумя переменными maxterms —

Minterms и Maxterms для функции с 3 переменными —

Связь между Minterms и Maxterms — Каждый minterm является дополнением соответствующего ему maxterm.
Например, для булевой функции с двумя переменными –

В общем или 

Построение логических функций — Теперь, когда мы знаем, что такое minterms и maxterms, мы можем использовать их для построения логических выражений.

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

Например, рассмотрим две функции и следующие таблицы истинности –

x	y	z	f 1	f 2
0	0	0	0	0
0	0	1	1	0
0	1	0	0	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Функция составляет 1 для следующих комбинаций- 001,100,111
. Соответствующие шахты-,.
Следовательно, алгебраическое выражение для is-


Аналогично, алгебраическое выражение для равно

.



Из вышеизложенного мы можем заключить, что булевы функции могут быть выражены как сумма minterms или произведение maxterms .

«Говорят, что логические функции, выраженные в виде суммы minterms или произведения maxterms, находятся в каноническая форма .

• Пример 1 – Выразите следующее логическое выражение в формах SOP и POS –
  
• Решение – Выражение может быть преобразовано в форму SOP путем добавления пропущенных переменных в каждом члене путем умножения на где пропущенная переменная.
  Это следует из того, что –
  
  При перестановке минтермов в порядке возрастания
  
  Если нам нужна форма POS, мы можем дважды инвертировать форму SOP, как указано выше, чтобы получить-
  
  Формы SOP и POS имеют краткое обозначение представления –
  

Стандартные формы –
Канонические формы – это базовые формы, полученные из таблицы истинности функции. Эти формы обычно не используются для представления функции, поскольку они громоздки для написания, и предпочтительно представлять функцию с помощью наименьшего возможного числа литералов.
Существует два типа стандартных форм —

1. Сумма произведений (SOP) — Логическое выражение, включающее термины И с одним или несколькими литералами каждый, объединенные по ИЛИ.
2. Произведение сумм (POS) Логическое выражение, включающее термины ИЛИ с одним или несколькими литералами каждый, объединенные И вместе, например.

   СОП-
   POS- 

   Примечание – Приведенные выше выражения не эквивалентны, это только примеры.

Угловые вопросы GATE CS

Ответы на следующие вопросы помогут вам проверить свои знания. Все вопросы были заданы в GATE в предыдущие годы или в пробных тестах GATE. Настоятельно рекомендуется их практиковать.

1. GATE CS 2010, вопрос 6
2.