Примеры выполнения заданий. 1.Найдите суперпозицию функций для формулы: B ~ Ø(A Ú B) ® A

1.Найдите суперпозицию функций для формулы: B ~ Ø(A Ú B) ® A

Решение: определим порядок выполнения операций и запишем их с помощью элементарных функций от одной или двух переменных:

g₃(в)=B;

g₃(a)=A;

f₉(а, в)= Ø(A Ú B);

f ₁₂ (a, b)= Ø(A Ú B) ® A

Получаем: f₁₀(g₃( в), f₁₂(f₉(а, в), g₃(a))).

2. Постройте канонические формы для функции & b Å .

a b	& b	& b Å .
0 0	1 0 0	0 1 1
0 1	1 1 1	1 1 0
1 0	0 0 0	0 1 1
1 1	0 0 1	0 0 0

СДНФ = & Ú & b Ú a & º & ( Ú b) Ú a & º & 1Ú a & º
º Ú a & º ( Ú a) & ( Ú ) º 1 & ( Ú ) º Ú .

СКНФ = Ú .

СПНФ = Ú =(1 + а) + (1 + b).

3. С помощью теоремы о полноте установите полноту алгебры Жегалкина {Å, 1, *}:

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

a Å b = a × + × b;

a = 0 + = 0 × a + 1 × = a Å 1;

a + b = = (()(bÅ1))Å1.

Задания для самостоятельного выполнения

1. Найдите суперпозицию функций для формул:

0) A&B ® BÚ A ¯ ØB 1) ØB Å A & B ® A | B 2) Ø(A & B)¯ Ø AÚ B ¯ A 3) Ø(A Ú B & A ~ B ¯ A) 4) B & ØA Ú Ø B Å A | B

5) A ~ B | ØAÅ B ® A 6) B Ú A ¯ B Å ØA & B 7) Ø(B & A Ú Ø B) ® A¯ B 8) A & B Å Ø(A Ú B) ¯ A 9) B ~ A Å B & A | ØB

2. Постройте канонические формы для функций:

0) Å b Å ; 1)(а Ú ) & (b Ú ); 2)(а → ) → с; 3)а & b Ú & ; 4)(а → b) → (a → с);	5) & ; 6) ; 7)а & b Ú → с; 8)(a Å b) & ; 9)( → ) Å с;
	a b с

СДНФ =

СКНФ =

СПНФ=

3. С помощью теоремы о полноте установите полноту системы:

0) {Å, 1}; 1) {Ø®, 1}; 2) {®, Å}; 3) {®, 0}; 4) штрих Шеффера;

5) {®, 1}; 6) стрелка Пирса; 7) {Å, 1}; 8) {®, 0}; 9) {®, Å};

4. Булевская функция f(x, y, z) задана таблично. Представьте эту же функцию формулой логики и функциональной схемой:

Переменные	Варианты задания функции f(x, y, z)
x	y	z	0)	1)	2)	3)	4)	5)	6)	7)	8)	9)

Практическое занятие №9. Применение
алгебры логики

Цель работы:	1.	изучить способы минимизации булевых функций в классе ДНФ;
	2.	получить навыки в применении булевых функций для анализа и синтеза дискретных устройств и релейно-контактных схем. Упрощение и преобразование схем.

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

Методы минимизации булевых функций:

Метод Квайна.

Метод Квайна - МакКласски.

Метод Блейка - Порецкого.

Метод диаграмм Вейча.

Метод минимизирующих карт.

Метод Петрика.

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

Минимизация систем булевых функций.

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

1. Все наборы единицы из СДНФ булевой функции f записываются их двоичными номерами.

2. Все номера разбиваются на непересекающиеся группы. Признак образования i -й группы: i единиц в каждом двоичном номере наборы единицы.

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

4. Производят всевозможные склеивания. Неотмеченные после склеивания номера являются простыми импликантами.

Нахождение минимальных ДНФ далее производится по импликантной матрице.

Примеры выполнения заданий

1. Минимизируйте методом Квайна - МакКласски булеву функцию
f(x₁, x₂,x_3, x₄₎, заданную таблицей истинности:

В СДНФ функции f(x₁, x₂,x_3, x₄₎, заменим все наборы единицы их

двоичными номерами: f = 0001 Ú 0011 Ú 0101 Ú 0111 Ú 1110 Ú 1111.	x4x3x2x1	f
Образуем группы двоичных номеров. Признаком образования i - й группы является i единиц в двоичном номере наборы единицы.	0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111	0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1
Номер группы	Двоичные номера наборов единицы
	-
	0011, 0101
	0111, 1110

Склеим номера из соседних групп таблицы. Склеиваемые номера вычеркнем (прим. - выделено цветом). Результаты склеивания занесем в следующую таблицу.

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

Номер группы	Двоичные номера наборов единицы
	00*1, 0*01
	0*11, 01*1
	*111, 111*

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

Простые импликанты	Наборы единицы
0**1	X	X	X	X
*111				X		X
111*					X	X

0**1 —> x₄; 111* —> x₁x₂x₃. Итак, МДНФ = x₄ Ú x₁x₂x₃

2. Применение булевых функций для анализа и синтеза дискретных устройств. Упрощение и преобразование комбинационных схем

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

Логический элемент И (конъюнктор) реализует операцию логического умножения (см. рис. 1). Логический элемент ИЛИ (дизъюнктор) реализует операцию логического сложения (см. рис. 2). Логический элемент НЕ (инвертор) реализует операцию отрицания
(см. рис. 3). Логический элемент И-НЕ реализует функцию штрих Шеффера (см. рис. 4). Логический элемент ИЛИ-НЕ реализует функцию стрелка Пирса (см. рис. 5).

Рис.1

Рис.2

Рис.3

Рис.4

Рис.5

Примеры выполнения заданий

1. Укажите функцию F(a, b, c, d), реализуемую схемой из функциональных элементов предварительно упростив:

a b c d

  &

  &

Решение: F(a, b, c, d) = a & c Ú Ú с & b º c &(a Ú b) Ú .

Дата добавления: 2014-11-20