Файл: микры и вмсс вместе.doc

Логические операции и элементарные логические функции.

ДИЗЪЮНКЦИЯ (логическое сложение)

Таблица сложения: Выполняет логическую операцию ИЛИ.

0 v 0 = 0 Обозначается X=AvB.

0 v 1 = 1

1 v 0 = 1 На выходе появится сигнал 1, когда

1 v 1 = 1 ИЛИ на первом ИЛИ на втором входе

Обозначение на схемах: есть сигнал 1.

Эту схему в электронике называют

A 1 X=AvB схемой сборки.

B Технический пример: сигнал о пожаре.

КОНЪЮНКЦИЯ (логическое умножение)

Таблица умножения: Выполняет логическую операцию И.

0  0 = 0 Обозначается X=A^B.

0  1 = 0

1  0 = 0 На выходе появится сигнал 1, когда

1  1 = 1 И на первом И на втором входе

Обозначение на схемах: есть сигнал 1.

Эту схему в электронике называют схемой совпадений

A & X=AB.

B Технический пример: сигнал "готовность".

ИНВЕРСИЯ (логическое отрицание)

Таблица сложения: Выполняет логическую операцию НЕ.

1 = 0 Обозначается чертой сверху.

0 = 1

Обозначение на схемах:

Эту схему в электронике называют инвертором.

A 1 X=A

Технический пример: сигнал о пожаре.

ОТРИЦАНИЕ ОТ КОНЪЮКЦИИ (И-НЕ)

0 & 0 = 1

0& 1 = 1 ___

1& 0 = 1A & F=A&B

1 & 1 = 0 B

функция Шеффера

ОТРИЦАНИЕ ОТ ДИЗЪЮНКЦИИ (ИЛИ-НЕ)

00 1 Стрелка Пирса

0 1 0 __ X1 1 F

1 0 0 F=Xn; F=1, если Xn=0 X2

1 1 0

РАВНОЗНАЧНОСТЬ

__ __

X1 F=X1&X2 V X1&X2

X2 = F

НЕРАВНОЗНАЧНОСТЬ

F=X1+X2 __ __

F=X1&X2 V X1&X2

XOr

X1 == F

X2

ИМПЛИКАЦИЯ

F=X1->X2

ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

1. Законы одинарных элементов

A v 1 = 1

A  1 = A Эти соотношения доказываются путем подстановки

A v 0 = A A=1 и A=0

A  0 = 0

2. Законы отрицания

­_

A= A Закон двойного отрицания

AA = 0 Законы дополнительности

A vA = 1

_ _ _____

A v B = A  B Правило де Моргана Следствия из правила де Моргана:

_ _ ____ ___ ____

A  B = A v B A v B =AB A vB =A v B

____ _____

AB =A vB AB =A v B

3. Комбинационные законы

A v A = A Законы тавтологии

A  A = A

A v B = B v A Коммутативные законы

A  B = B  A

(A v B) v C = A v (B v C) Ассоциативные законы

(A  B)  C = A  (B  C)

A(B v C) = AB v AC Дистрибутивные законы

A v (BC) = (A v B)(A v C) Второй дистрибутивный закон можно доказать на основе первого:

(AvB)(AvC) = AAvACvBAvBC = AvACvABvBC = =A(1vCvB)vBC = A v BC

A v AB = A Законы поглощения Законы поглощения можно доказать:

A(A v B) = A AvAB = A(1vB) = A

A(AvB) = AAvAB = AvAB = A(1vB) = A

A B v AB = A Законы склеивания

(A v B)(A vB) = A Доказательство:

A B v AB = A(B vB) = A

(A v B)(A vB) = A A v AB v A B v BB = A v AB v AB = =A(1 vB v B) = A

ПОСТРОЕНИЕ ЛОГИЧЕСКИХ СХЕМ

Каждое логическое выражение можно реализовать в виде конкретной логической схемы:

a 1 a ab 1 D=a vab

&

b

Можно попытаться преобразовать это выражение:

___ ________ __________ ___

D = a vab =aab =a(a vb)= a a vab =ab = a v b

Следовательно D=a v b a 1 D=a v b

b

Эта схема намного проще, поэтому всегда следует стараться упростить выражение.

Это же преобразование можно сделать с помощью второго дистрибутивного закона, а затем закона склеивания:

D = a vab = (a va)(a v b)= a v b

3.Способы представления логических функций. Минимизация функций алгебры логики методом Вейча-Карно.

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

Элементами являются конъюнкция или дизъюнкция.

Элементарной называется конъюнкция (дизъюнкция) в которую входит только переменные или их отрицания.

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

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

Используют совершенные ДНФИ КНФ

Их особенности: 1.Все элементы члены формы им одинаковый ранг. 2.Элементные члены содержат все логические переменные (имеют полный ранг).

Пример:

СКНФ

X3X2X1F

X1vX2vX3 0 0 0 0 __ __

0 0 1 1 X1&X2 &X3

0 1 0 1 X1 &X2 &X3

0 1 1 1 X1 &X2 &X3

X1vX2vX3 1 0 0 0

X1vX2vX31 0 1 0

X1vX2vX3 1 1 0 0

1 1 1 1 X1 &X2 &X3

Минтермом называется логическая функция которая принимает значение 1 на первом наборе логической переменной.

Макстеры логическая функция которая принимает значение 0 на первом наборе.

Правило записи СДНФ

1. Отмечаем наборы логических переменных на которых функция принимает единичные значения (функция истина).

2. Составляем элементарные конъюнкции для этих наборов по правилу:

Если логическая переменная на этом наборе = 1, то она входит в конъюнкцию так, как она есть.

Если логическая переменная = 0, то она входит с отрицанием.

3. Полученные конъюнкции объединяются операцией дезъюнкции:

В результате получим СДНФ

___ ___ __ __ ___

F=X1 &X2 &X3vX1 &X2 &X3vX1 &X2 &X3vX1 &X2 &X3

Правило записи СКНФ

1. Отмечаем макстерами логические функции.

2. Составление элементов дизъюнкций для каждого отмеченного набора по правилу:

Если переменная =0, то записывается так как есть.

Если переменная =1, то записывается с инверсией.

3. Полученные элементы дизъюнкции объединяют операцией конъюнкции.

___ __ __ ___ ___

F=X1 v X2 v X3 & X1 v X2 v X3 & X1 v X2 v X3 & X1 v X2 v X3

Минимизация логических функций

Цель – получение minформы логической функции.Метод Вейна – Корно

Целесообразно использовать при количестве логических переменных не более четырех.

Используем диаграмму Вейга и Карты Карто.

_ _ _

b b a a a a _

a b 1 1 0 1 1 1 d

ab 1 1 b 1 1

c c _ 1 _ d

c b 1 d

c c

c

Составляется так, что соседние клетки соответствуют состоянию ментермом.

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

При определение контура необходимо соблюдать следующие правила.

1. Контур должен быть прямоугольным.

2. Внутри контура должны быть клетки с записанными только 1.

3. Число клеток в контуре должно быть целой степенью двойки.

4. Одни и те же клетки могут входить в различные контуры.

5. При определение контура самая нижняя и верхняя строки а также первый и последний столбец считать соседними.