Файл: Федеральное агентство Российской Федерации по образованию гоу впо Тульский государственный университет кафедра электронных вычислительных машин.pdf

36
Таблица 3. Перевод числа из одной позиционной системы счисления в другую
Ответ: 1020304 10
=11446435 7
В ряде случае при переводе чисел из одной системы счисления в другую используют промежуточную систему счисления. Например, такой подход можно использовать при переводе числа из 17-ричной в троичную систему счисления. Вместо операции деления по правилам 17-ричной арифметики можно сначала перевести это число в десятеричную систему счисления в соответствии с выражением
0 0
1 1
17 17 17
⋅
+
⋅
+
+
⋅
=
a
a
a
A
n
n
q
K
, а затем число в десятичной системе перевести в троичную, используя деление в десятичной арифметике.
3. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
1.
Ознакомиться с теоретическими сведениями.
2.
Получить вариант задания у преподавателя.
3.
Выполнить задание.
4.
Продемонстрировать выполнение работы преподавателю.
5.
Оформить отчет.
6.
Защитить лабораторную работу.
4. ТРЕБОВАНИЯ К ОФОРМЛЕНИЮ ОТЧЕТА
Отчет по лабораторной работе должен содержать следующие разделы:
•
титульный лист;
•
цель работы:
•
задание на лабораторную работу;
•
ход работы;
•
ответы на контрольные вопросы;
•
выводы по проделанной работе.
5. ЗАДАНИЕ НА РАБОТУ
Перевести число из одной позиционной системы счисления в другую в соответствии с полученным вариантом (таблица 4).
Делимое
Делитель
Частное
Остаток
1020304
/
7 145757 5
145757
/
7 20822 3
20822
/
7 2974 4
2974
/
7 424 6
424
/
7 60 4
60
/
7 8
4 8
/
7 1
1 1
/
7 0
1

37
Таблица 4. Варианты заданий на работу
Вариант
Число
Исходная система счисления
Система счисления
Система счисления
Система счисления
1 1C2 16 12 9
2 2
316 12 2
3 15 3
550 9
3 8
7 4
111000010 2
15 8
18 5
1212 7
3 5
6 6
121200 3
8 13 12
6. КОНТРОЛЬНЫЕ ВОПРОСЫ
1.
Какая система называется позиционной? Приведите примеры таких систем.
2.
Какая система называется непозиционной? Приведите примеры таких систем.
3.
Правила какой арифметики используются при переводе числа из одной системы счисления в другую делением на основание новой системы?
4.
Какое максимально возможное число можно записать с помощью шестнадцатеричной системы счисления?
5.
Перечислите цифры, используемые для записи числа в восьмеричной системе.
6.
Возможен ли перевод дробных чисел из одной системы счисления в другую? Поясните ответ.
7. ЛИТЕРАТУРА
1. Фомин С. В. Системы счисления. 5-е изд. — М.: Наука. Гл. ред. физ.-мат, лит., 1987.— 48 с.
2. Савельев А.Я. Основы информатики. — М.: Издательство МГТУ имени Н.Э.Баумана, 2001. — 328 с.

38
ЛАБОРАТОРНАЯ РАБОТА №6
ПРЕОБРАЗОВАНИЕ ВЫРАЖЕНИЙ БУЛЕВОЙ АЛГЕБРЫ
1. ЦЕЛЬ РАБОТЫ
Изучить методы преобразования выражений булевой алгебры.
2. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Булевой алгеброй называется непустое множество A с двумя бинарными операциями
∧
или
⋅
(аналог конъюнкции),
∨
(аналог дизъюнкции), унарной операцией
¬
(аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:
1.
Ассоциативность (сочетательный закон):
( ) ( )
(
) (
)
c
b
a
c
b
a
c
b
a
c
b
a
∨
∨
=
∨
∨
⋅
⋅
=
⋅
⋅
;
2.
Коммутативность (переместительный закон):
a
b
b
a
a
b
b
a
∨
=
∨
⋅
=
⋅
;
3.
Законы поглощения:
( )
(
)
a
b
a
a
a
b
a
a
=
∨
⋅
=
⋅
∨
;
4.
Законы склеивания:
(
)
( )
a
b
a
b
a
a
b
a
b
a
=
∨
⋅
∨
=
⋅
∨
⋅
;
5.
Дистрибутивность (распределительный закон):
(
)
(
) (
)
c
b
a
c
a
b
a
c
b
a
c
a
b
a
⋅
∨
=
∨
⋅
∨
∨
⋅
=
⋅
∨
⋅
;
6.
Дополнительность:
0
;
1
=
⋅
=
∨
a
a
a
a
7.
Идемпотентность:
a
a
a
a
a
a
=
∨
=
⋅
;
8.
Закон де Моргана:
(
)
b
a
b
a
b
a
b
a
⋅
=
∨
∨
=
⋅
;
9.
Аннулирующее свойство единицы:
a
a
a
=
⋅
=
∨
1
;
1 1
10.
Свойство нуля:
0 0
;
0
=
⋅
=
∨
a
a
a
11.
Свойства инверсии (инволютивность):
a
a
=
=
=
;
0 1
;
1 0
12.
Правило вычеркивания:
a
b
a
b
a
∨
=
∨
⋅
Преобразование в дизъюнктивную нормальную форму. Всякая аналитическая запись функции может быть преобразована в нормальную форму. Систематическая процедура преобразования функции в нормальную

39 форму с использованием свойств двоичных функций может быть описана следующим образом:
Шаг 1. Если в функции имеются операции, отличные от И, ИЛИ, НЕ, то используем следующие свойства для их устранения:
(
)
(
)
2 1
2 1
2 1
2 1
2 1
x
x
x
x
x
x
x
x
x
x
+
⋅
+
=
⋅
+
⋅
=
⊕
,
2 1
2 1
x
x
x
x
+
=
→
,
2 1
2 1
/
x
x
x
x
⋅
=
,
2 1
2 1
2 1
x
x
x
x
x
x
⋅
=
+
=
↓
Шаг 2. Используем свойства инверсии и законы де Моргана чтобы каждая операция отрицания относилась только к одной переменной.
Шаг 3. Используем свойства дистрибутивности и другие свойства, чтобы получить нормальную форму.
Например, преобразовать в нормальную дизъюнктивную форму функцию
( )
c
b
a
c
b
a
f
⊕
∨
=
)
,
,
(
( )
( ) ( ) ( ) ( )
c
b
a
c
b
c
a
c
b
a
c
b
a
c
b
a
c
b
a
c
b
a
c
b
a
f
∨
∨
=
⋅
⋅
∨
⋅
∨
=
⋅
∨
∨
⋅
∨
=
⊕
∨
=
)
,
,
(
Способы преобразования НФ в СНФ. Совершенная нормальная форма отличается от нормальной формы (НФ) тем, что всегда содержит термы только максимального ранга и дает однозначное представление функции.
Произвольная нормальная дизъюнктивная форма (НДФ) переводится в
СНДФ следующим образом.
Пусть f
ДНФ
= F
j
. Тогда
i
j
i
j
СДНФ
x
F
x
F
f
⋅
∨
=
где x
i
— переменная, которая не входит в данный терм F
j
.
Произвольная НКФ переводится в СКНФ путем следующего преобра- зования.
Пусть f
НКФ
=
Φ
j
. Тогда
(
) (
)
i
j
i
j
i
i
j
СКНФ
x
x
x
x
f
∨
Φ
⋅
∨
Φ
=
⋅
∨
Φ
=
Переведем в СДНФ функцию из предыдущего примера:
c
b
a
c
b
a
c
ab
c
b
a
c
b
a
c
b
a
a
c
b
a
c
b
b
c
a
b
c
a
c
b
a
c
b
c
a
c
b
a
f
∨
∨
∨
∨
∨
=
∨
∨
∨
∨
=
∨
∨
=
)
,
,
(
Если выражение задано в произвольном виде и его необходимо представить в виде СКНФ, то проще всего воспользоваться следующим правилом:
Преобразование в СКНФ выражения произвольного вида. Процесс преобразования функции осуществляется для исходной функции, представленной таблицей истинности в соответствии с выражением
(
)




∨
∨
∨
∧
=
n
n
n
x
x
x
x
x
x
f
α
α
α
K
K
2 1
2 1
0 2
1
,
,
,
,
(1)

40 где



=
=
=
,
0
если
,
;
1
если
,
α
α
α
x
x
x
Например, представить функцию
c
b
a
c
b
a
f
∨
=
)
,
,
(
в виде СКНФ.
Таблица истинности для данной функции имеет вид:
a
b
c
f(a, b, c)
0 0
0 0
0 0
1 1
0 1
0 1
0 1
1 1
1 0
0 0
1 0
1 1
1 1
0 0
1 1
1 1
В соответствии с данной таблицей функция
)
,
,
(
c
b
a
f
принимает нулевые значения на наборах 0, 4, 6. Тогда в соответствии с (1) получим:
(
)
(
) (
)
c
b
a
c
b
a
c
b
a
c
b
a
f
∨
∨
⋅
∨
∨
⋅
∨
∨
=
)
,
,
(
3. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
1.
Ознакомиться с теоретическими сведениями.
2.
Получить вариант задания у преподавателя.
3.
Выполнить задание.
4.
Продемонстрировать выполнение работы преподавателю.
5.
Оформить отчет.
6.
Защитить лабораторную работу.
4. ТРЕБОВАНИЯ К ОФОРМЛЕНИЮ ОТЧЕТА
Отчет по лабораторной работе должен содержать следующие разделы:
•
титульный лист;
•
цель работы:
•
задание на лабораторную работу;
•
ход работы;
•
ответы на контрольные вопросы;
•
выводы по проделанной работе.
5. ЗАДАНИЕ НА РАБОТУ
Приведенные логические выражения (таблица 5):
•
преобразовать в СДНФ;
•
преобразовать в СКНФ;
•
преобразовать в базис «И-ИЛИ-НЕ» и минимизировать.

41
Таблица 5. Варианты заданий на работу
Вариант
f(a, b, c, d)
1
(
)
d
a
cd
b
ac
⊕
⋅
∨
2
(
)
cd
a
ac
abcd
c
b
a
↓
∨
∨
∨
3
( )
d
ac
d
b
a
ac
ad
/
∨
∨
∨
4
(
)
a
ad
abcd
cd
b
ac
⊕
∨
∨
⋅
∨
5
c
a
ac
abcd
c
b
a
∨
∨
∨
6
(
)
abd
ac
d
b
a
ad
a
/
∨
∨
∨

42
ЛАБОРАТОРНАЯ РАБОТА №7
МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ С ПОМОЩЬЮ
КАРТ КАРНО
1. ЦЕЛЬ РАБОТЫ
Изучить методы преобразования выражений булевой алгебры.
2. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Карта Карно — это двумерная табличная форма представления булевой функции, позволяющая в графической наглядной форме легко отыскать минимальные ДНФ логических функций. Карта Карно, это преобразованная таблица истинности булевой функции. Карта содержит 2
n
клеток, где n – число аргументов функции. Таким образом, каждому из наборов значений аргументов (СДНФ) соответствует одна клетка карты, и в эти клетки вписываются нули или единицы, представляющие значения функции на данном наборе.
Минимизирующие карты обычно используют для ручной минимизации булевых функций при небольшом числе переменных.
Правила минимизации следующие:
1.
Две соседние клетки (два 0-куба) образуют один 1-куб. При этом клетки, лежащие на границах карты, также являются соседними по отношению друг к другу.
2.
Четыре вершины могут объединяться, образуя
2-куб, содержащий две независимые координаты.
3.
Восемь вершин могут объединяться, образуя один 3-куб.
4.
Шестнадцать вершин, объединяясь, образуют один 4-куб и т.д.
При числе переменных равном или большем пяти строят комбинированную карту, состоящую из совокупности четырехмерных
(шестнадцатиклеточных) карт. Соседними клетками, в этом случае, являются клетки, совпадающие при совмещении карт поворотом вокруг общего ребра.
Пример минимизации функции пяти аргументов приведен на рис. 20.
Рис. 20. Минимизация функции пяти переменных с помощью карты Карно

43
Следует отметить, что целесообразно выделять области максимально возможного размера (даже если эти области перекрываются) для более эффективной минимизации логического выражения.
Карты Карно удобны для минимизации и неполностью определенных функций, которые будут рассмотрены ниже. Неопределенные значения можно заменить любыми — 0 или 1. Покрывая таблицу минимальным числом максимальных квадратов (или прямоугольников) со сторонами, равными степени двойки, так, чтобы они обязательно покрыли все единицы и не покрывали ни одного нуля, получим минимальную ДНФ всех возможных функций.
Схема построения комбинированной карты при большом числе аргументов минимизируемой функции многократным отражением карты с шестнадцатью клетками показана на рис. 21.
Рис. 21. Построение карты Карно с помощью шестнадцатиклеточных карт
Особенную роль в процессе минимизации логических формул играют
не полностью определенные или частичные функции, область определения которых меньше, чем полное множество наборов значений n аргументов.
Главным свойством не полностью определенных функций является то, что, проводя минимизацию, можно произвольно доопределять функцию, подбирая такие ее значения на запрещенных наборах, которые позволяют произвести покрытие наилучшим образом.

44
На рис. 22 показан пример минимизации частичной функции, где х соответствует запрещенному набору. Произведенное доопределение необязательными нулями и необязательными единицами позволило провести дополнительную минимизацию в двух термах.
Рис. 22. Пример минимизации не полностью определенной функции
3. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
1.
Ознакомиться с теоретическими сведениями.
2.
Получить вариант задания у преподавателя.
3.
Выполнить задание.
4.
Продемонстрировать выполнение работы преподавателю.
5.
Оформить отчет.
6.
Защитить лабораторную работу.
4. ТРЕБОВАНИЯ К ОФОРМЛЕНИЮ ОТЧЕТА
Отчет по лабораторной работе должен содержать следующие разделы:
•
титульный лист;
•
цель работы:
•
задание на лабораторную работу;
•
ход работы;
•
ответы на контрольные вопросы;
•
выводы по проделанной работе.
5. ЗАДАНИЕ НА РАБОТУ
Доопределить оптимальным образом и минимизировать с помощью карты Карно частичные логические функции (таблица 6).