X₂ F(X₁, X₂)= X₁X₂

_____

F₁₅= X₁/ X₂= X₁ X₂ -штрих Шеффера, реализуется на элементе «И-НЕ»

Элемент «И-НЕ».

&

X₁

F(X₁, X₂)= X₁/X₂

X₂

_____

F₉= X₁ X₂= X₁ X₂ -стрелка Пирса, реализуется на элементе «ИЛИ-НЕ»

Элемент «ИЛИ-НЕ».

1

X₁

F (X₁, X₂)= X₁ X₂

X₂

__________

F7=X1

ς

X2= X1 mod2 X2

-функция сложения по модулю два, функция «исключающее ИЛИ»,

функция отрицания равнозначности, реализуется на элементе «исключающее ИЛИ»

Элемент «исключающее ИЛИ».

=1

X₁

F(X₁, X₂)= X₁ mod2 X₂

X₂

________

F10=X1

ς

X2= X1 mod2 X2

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

F₁₄=X₁  X₂ -функция импликации, прямая импликация, «ЕСЛИ…ТО…»

______

F₃=X₁  X₂ -отрицание прямой импликации;

F₁₂=X₂  X₁ -обратная импликация;

______

F₅=X₂  X₁ -отрицание обратной импликации.

Для функций F₁₀, F₁₄, F₁₂, F₅, F₃ не существует отдельных логических элементов, но они могут быть реализованы на других элементах.

2.3 Функции многих переменных.

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

Примеры (2.2.) базисов:

1. ¬,  -дизъюнктивный базис;

2. ¬,  -конъюнктивный;

3. ¬, ,  -Булевский базис (смешанный);

4. / -штрих Шеффера;

5. ↓ -стрелка Пирса;

6. /, «1»;

7. ↓, «0»;

8. →, «0»;

9. →, «1»;

10. →, mod2;

11. &, mod2 –базис Жегалкина.

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

Основные законы Булевского базиса:

1) закон идемпотентности

аа=а; аа=а;

2) коммутативный (переместительный) закон

ав=ва; ав= ва;

3) ассоциативный (сочетательный) закон

а(вс)=(ав)с; а(вс)=(ав) с;

4) дистрибутивный (распределительный) закон

а(вс)= (ав) (ас); а (вс)= (ав)  (ас);

5) закон двойного отрицания

_

ā =а;

6) законы двойственности (правила де Моргана)

_ _ __ _ _ ____

а + в= ав; а в = а + в;

Его можно распространить на любое число переменных n:

7) закон склеивания

_

а в + а в =а; (склейка по в)

_

(a + в) (a + в) =а;

8) закон поглощения

а + а в= а; а(а + в)=а.

Действия с константами «0» и «1»:

_

а + 0=а; а + 1=1; а + а =1;

_

а 0 =0; а 1=а; а а =0.

Правило введения и исключения лишних связок:

_ _

F₁X+ F₂X= F₁X+ F₂X+ F₁ F₂;

_ _

(F₁+X) (F₂+X)= (F₁+X) (F₂+X) (F₁+ F₂).

2.4. Задание функции комбинационных логических схем.

Функция может быть задана:

1) таблицей истинности.

Таблица истинности (рис 2.1.) перечисляет все наборы значений двоичных переменных и содержит строк, где n – число переменных. Для каждого набора указывается значение функции.

Если функция на наборе не определена, то в столбце значений функции используется “-“ (прочерк).

Если определить старшинство переменных, то каждому набору можно присвоить номер указываемый в столбце номеров N.

2
) номерами наборов, например, F=1 на наборах {2,3,6}.

3) задание в виде формулы алгебры логики.

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

Выражение вычисляется слева на право в соответствии со старшинством операций .

4) топологические способы задания функции в виде графов или диаграмм (карт) Карно, в виде n - мерных кубов.

2.4.1. Нормальные формы записи булевых функций.

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

ДНФ – дизъюнкция элементарных конъюнкций.

Элементарная конъюнкция – это конъюнкция переменных функций и их отрицаний. Она не может включать переменную и её отрицание одновременно.

Пример 2.3.

Следующие выражения являются элементарными конъюнкциями.

Дизъюнкция элементарных конъюнкций: - ДНФ.

КНФ – конъюнкция элементарных дизъюнкций.

Элементарная дизъюнкция – это дизъюнкция переменных функций и их отрицаний. Она не может включать переменную и её отрицание одновременно.

Пример 2.4.

Следующие выражения являются элементарными дизъюнкциями.

Конъюнкция элементарных дизъюнкций: - КНФ.

Одна и та же функция может иметь несколько ДНФ или КНФ.

2.4.2. Совершенные нормальные формы.

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

Конституентой нуля называют элементарную дизъюнкцию всех переменных функций, иначе её называют дизъюнктивной конституентой, или макситермом.

Конституента единицы принимает единственное значение тогда и только тогда, когда все буквы принимают единичное значение (буква – сама переменная или её отрицание ).

abc=1 только на том наборе, где a=1, b=1, c=1, N=7 (см. рис. 1)

только на том наборе, где , N=5.

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

Конституента нуля равна 0 на наборе , а конституента нуля равна 0 на наборе

На основе конституент 1(0) строятся совершенные нормальные формы (СНФ)

Дизъюнкция конституент 1 носит название совершенной дизъюнктивной нормальной формой (СДНФ).

Пример 2.5.

Конъюнкция конституент 0 носит название совершенной конъюнктивной нормальной формой (СКНФ).

Пример 2.6.

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

Пример 2.7.

Ф
ункции, заданной таблицей истинности (рис. 2.2), соответствует СДНФ.

Функции, заданной этой же таблицей истинности, соответствует СКНФ.

Представление в виде СДНФ или СКНФ для функции является единственным.

Свойства СНФ.

I. 1. Дизъюнкция всех конституент 1 равна единице

.

2. Конъюнкция всех конституент 0 равна нулю

.

II. 1. Дизъюнкция каких-то k конституент единицы равна отрицанию дизъюнкций оставшихся конституент единицы.

2. Конъюнкция каких-то k конституент нуля равна отрицанию конъюнкций оставшихся конституент нуля

Пример 2.8.

Для функции двух переменных a и b имеем следующее множество конституент 1: . Отрицание функции легко может быть найдено путём использования свойства II.1. Действительно, , и следовательно, .

2.5. Задача минимизации булевых функций.

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

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

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

Канонический метод синтеза логических схем заключается в следующем.

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

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

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