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

Стр 1 из 2Следующая ⇒

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ

ЧЕРНИГОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА ИНФОРМАЦИОННЫХ И КОМПЬЮТЕРНЫХ СИСТЕМ

ПРОЕКТИРОВАНИЕ ЭЛЕКТРОННЫХ УСТРОЙСТВ

Методические указания к расчетно-графическим работам

по дисциплине

Компьютерная логика»

для студентов направлений подготовки
6.050102 «Компьютерные инженерия» и
6.050103 «Программная инженерия»

Обсуждено и рекомендовано

на заседании кафедры

информационных и компьютерных систем.

Протокол №13

від 05.06.2012 р.

Чернигов ЧГТУ 2012

Проектування електронних пристроїв. Методичні вказівки до розрахунково-графічних робіт з дисципліни “Комп’ютерна логіка” для студентів напрямів підготовки 6.050102 «Комп’ютерна інженерія» та 6.050103 «Програмна інженерія» / Укладачі: Соломаха В.В., Гора Н.О. – Чернігів: ЧДТУ, 2012. - 97 с. Рос. мовою.

Составители: Соломаха Валерий Владимирович, старший преподаватель,

Гора Наталья Олеговна, старший преподаватель

Ответственный за выпуск:	Казимир В.В., зав. кафедрой информационных и компьютерных систем, доктор техн. наук, профессор
Рецензент:	Нестеренко С.О., канд. техн. наук, доцент

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ............................................................................................... 5

1 РГР №2. РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ НА ЛОГИЧЕСКИХ ЭЛЕМЕНТАХ............................................................................................ 6

1.1 Цель работы..................................................................................... 6

1.2 Теоретические сведения................................................................... 6

1.3 Способы представления булевых функций.................................... 7

1.3.1 Табличный способ представления.......................................................... 7

1.3.2 Матричный способ представления......................................................... 7

1.3.3 Графический способ представления....................................................... 8

1.3.4 Аналитический способ представления................................................... 9

1.4 Логические функции........................................................................ 9

1.4.1 Логические функции одной переменной................................................ 9

1.4.2 Логические функции двух переменных.................................................. 9

1.5 Алгебра Буля................................................................................. 10

1.6 Законы алгебры логики................................................................. 11

1.7 Переход от табличной формы представления.............................. 12

1.8 Импликанты и имплициенты булевых функций........................... 13

1.9 Сокращенные, минимальные и тупиковые формы....................... 14

1.10 Метод карт Карно (диаграммы Вейча).................................. 15

1.10.1 Минимизация функции трех переменных......................................... 15

1.10.2 Минимизация функции четырех переменных................................... 16

1.10.3 Минимизация функции пяти переменных......................................... 17

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

1.10 Алгебра Жегалкина................................................................. 19

1.11.1 Определение алгебры Жегалкина..................................................... 19

1.11.2 Преобразование функций в алгебре Жегалкина.............................. 19

1.11.3 Переход от булевой алгебры к алгебре Жегалкина......................... 20

1.11 Задания, выполняемые в расчетно-графической работе....... 21

1.12 Пример выполнения работы № 2........................................... 23

1.13.1 Выполнение задания 1....................................................................... 23

1.13.2 Выполнение задания 2....................................................................... 27

1.13.3 Выполнение задания 3....................................................................... 33

1.13 Выводы.................................................................................... 34

1.14 Содержание отчета.................................................................. 34

2 РГР№3. ПРОЕКТИРОВАНИЕ И ИССЛЕДОВАНИЕ ТРИГГЕРОВ 35

2.1 Цель работы................................................................................... 35

2.2 Теоретические сведения................................................................. 35

2.3 Запоминающие элементы триггеров............................................. 38

3.3.1 Запоминающие элементы триггеров, управляемые уровнем тактирующего сигнала................................................................................................................ 38

3.3.2 Запоминающие элементы триггеров, управляемые перепадом тактирующего сигнала................................................................................................................ 43

- ЗЭЗЭ триггеров, собранные по MS схеме...................................................... 43

- ЗЭЗЭ по схеме трёх триггеров................................................................... 44

2.4 Задания, выполняемые в расчетно-графической работе.............. 46

2.5 Пример выполнения работы № 3.................................................. 47

3.5.1 Пример построения DV-триггеров по MS схеме на элементах И-НЕ 47

3.5.2 Пример реализации Т-триггера по MS схеме на элементах ИЛИ-НЕ 49

3.5.3 Пример реализации JK-триггера по схеме трех триггеров на И-НЕ 51

2.6 Выводы........................................................................................... 53

2.7 Содержание отчета........................................................................ 53

3 РГР №4. ПРОЕКТИРОВАНИЕ И ИССЛЕДОВАНИЕ СИНХРОННЫХ АВТОМАТОВ......................................................................................... 54

3.1 Цель работы................................................................................... 54

3.2 Теоретические сведения................................................................. 54

3.3 Абстрактный синтез автомата....................................................... 55

4.3.1 Минимизация числа состояний автомата 56

4.3.2 Кодирование состояний автомата....................................... 59

4.3.3 Получение функций возбуждения блока памяти и функций выхода.. 61

3.4 Задания выполняемые в расчетно-графической работе............... 61

3.5 Пример выполнения работы № 4.................................................. 63

3.6 Выводы........................................................................................... 65

3.7 Содержание отчета........................................................................ 66

4 РЕКОМЕНДОВАННАЯ ЛИТЕРАТУРА......................................... 67

ВВЕДЕНИЕ

Методические указания разработаны помощь в помощь для выполнения расчетно-графических работ по дисциплине «Компьютерная логика».

При изучении дисциплины выполняется три лабораторные работы

2.Реализация комбинационных схем на логических элементах.

3.Проектирование и исследование триггеров.

4.Проектирование синхронных цифровых автоматов.

При выполнении данных работ необходимо производить определенные расчеты, производить построение схем.

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

РГР №2. РЕАЛИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ НА ЛОГИЧЕСКИХ ЭЛЕМЕНТАХ

Цель работы

Изучить методы проектирования комбинационных схем на логических элементах типа И - НЕ, ИЛИ - НЕ, исключающее ИЛИ

Теоретические сведения

Функция F (x₁,x₂,…,x_n) называется логической или

булевой, если она принимает два значения: ложь или истина (0 или 1).

Аргументы x₁,x₂,…,x_n принимают так же значения ложь или истина (0 или 1) и называются также булевыми или логическими переменными.

ДЖОРДЖ БУЛЬ (George Boole)

2 ноября 1815 (Линкольн, Англия) –

8 декабря 1864 (Баллинтемпл,

Ирландия)

Научная сфера:

Математика, Логика, Философия математики.

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

Место работы:

Королевский колледж в Корке (Ирландия).

Упорядоченная совокупность переменных (x₁,x₂,…,x_n) называется булевым набором длины n.

Наборы, на которых функция F(x₁,x₂,…,x_n) = 0, называются нулевыми наборами, а на которых функция F(x₁,x₂,…,x_n) = 1, называются единичными наборами переменных.

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

Множество значений функции на всех наборах называется областью значения логической функции

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

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

1.3.1 Табличный способ представления

Таблица 1.1 – Функция четырех переменных

х₁	х₂	х₃	х₄	F
0	0	0	0	0
0	0	0	1	1
0	0	1	0	0
0	0	1	1	1
0	1	0	0	1
0	1	0	1	0
0	1	1	0	0
0	1	1	1	0
1	0	0	0	1
1	0	0	1	0
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	0
1	1	1	0	0
1	1	1	1	1

Такая таблица называется таблицей истинности.

Число двоичных наборов равно 2ⁿ , где n – число переменных.

Наборы обозначаются десятичными или шестнадцатиричными числами: 2,4,7,8,9,10,15 или 2,4,7,8,9,A,F.

Недостаток: при увеличении числа переменных размер таблицы резко возрастает.

1.3.2 Матричный способ представления

Это - частный способ табличного представления логических функций. В частности – карты Карно.

Изобретены в 1952 Эдвардом В. Вейчем (диаграммы Вейча) и усовершенствованы в 1953 Морисом Карно(карты Карно).

Таблица 1.2 – Карта Карно четырех переменных

х₃х₄ х₁х₂	00	01	11	10
00	0	1	1	0
01	1	0	0	0
11	0	0	1	0
10	1	0	1	0

1.3.3 Графический способ представления

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

Рисунок 1.1 – Графическое представление функции трех переменных

1.3.4 Аналитический способ представления

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

Логические функции

1.4.1 Логические функции одной переменной

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

2 ² , т.к. функция и n аргументов принимают по 2 значения, т.е.

для одной переменной будет 4 функции:

Таблица 1.3 – Функции одной переменной

х	F₀	F₁	F₂	F₃
0	0	0	1	1
1	0	1	0	1

F₀ (х) = 0 - константа нуля;

F₁ (х) = х - тождественная функция;

F₂ (х) = х – инверсия (отрицание);

F₃ (х) = 1 - константа единицы.

1.4.2 Логические функции двух переменных

Таблица 1.4 – Функции двух переменных

х₁	х₂	F₀	F₁	F₂	F₃	F₄	F₅	F₆	F₇	F₈	F₉	F₁₀	F₁₁	F₁₂	F₁₃	F₁₄	F₁₅
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
обознач.		0	Ù	х₁х₂	х₁	х₂х₁	х₂	Å	Ú	¯	~	ù х₂	х₂®х₁	ù х₁	х₁®х₂	½	1

Наименования:

F₀ = 0 – константа нуля;

F₁= х₁Ù х₂конъюнкция (логическое умножение), может обозначаться

х₁х₂;

F₂= х₁ х₂отрицание импликации (следования), может обозначаться

х₁Ì х₂;

F₃= х₁тождественная функция первой переменной;

F₄= х₂ х₁ – отрицание обратной импликации;

F₅= х₂тождественная функция второй переменной;;

F₆= х₁Å х₂– сложение по модулю 2 (неравнозначность);

F₇= х₁Ú х₂– дизъюнкция (логическое сложение);

F₈= х₁¯ х₂ – стрелка Пирса;

F₉= х₁~ х₂– эквиваленция, может обозначаться х₁« х₂, х₁º х₂;

F₁₀= ù х₂– отрицание (инверсия) х₂, может обозначаться ;

F₁₁= х₂® х₁ – обратная импликация;

F₁₂= ù х₁– отрицание х₁,

F₁₃= х₁® х₂– импликация;

F₁₄= х₁½ х₂– штрих Шеффера;

F₁₅= 1 – константа единицы.

Алгебра Буля

Использует операции: дизъюнкцию, конъюнкцию, отрицание.

1. Ú-дизъюнкция - логическое сложение (операция „или”(or)):

Таблица 1.5 – Дизъюнкция

a	b	a Ú b
0	0	0
0	1	1
1	0	1
1	1	1

2. Ù - конъюнкция - логическое умножение (операция „и” (and)):

Таблица 1.6 – Конъюнкция

a	b	a Ù b
0	0	0
0	1	0
1	0	0
1	1	1

3.инверсия – отрицание (операция „не”)

Таблица 1.7 – Операция отрицание

а	ù а
0	1
1	0

Законы алгебры логики

1. Законы коммутативности:

a Ù b = b Ù a,

a Ú b = b Ú a.

2. Законы ассоциативности:

a Ù (b Ù с) = (а Ù b)Ù с,

a Ú (b Ú с) = (а Ú b)Ú с.

3. Законы дистрибутивности:

a Ù (b Ú с) = (а Ù b)Ú(а Ù с),
a Ú (b Ù с) = (а Ú b)Ù(а Ú с).

4. Законы идемпотентности:

а = a Ù а,

a = а Ú a.

5. Законы нуля и единицы:

a Ù ù а = 0,

а Ù1 = а,

a Ú ù а = 1,

а Ú 0 = а.

6. Законы де Моргана:

ù (a Ú b) = ù a Ù ù b,

ù (a Ù b) = ù a Ú ù b.

7. Законы поглощения:

a Ú (а Ù b) = а,

a Ù (a Ú b) = а.

8. Законы склеивания:

(а Ú ù b)Ù (а Ú b) = а,

(а Ù ù b)Ú (а Ù b) = а.

9. Закон двойного отрицания:

ù ù а = а.

Дата добавления: 2018-05-12; просмотров: 1428; Мы поможем в написании вашей работы!
Поделиться с друзьями:

12 Следующая ⇒

Мы поможем в написании ваших работ!