ЛР_Информатика

81

выводы по проделанной работе.

5. ЗАДАНИЕ НА РАБОТУ

Перевести число из одной позиционной системы счисления в другую в соответствии с полученным.

6. КОНТРОЛЬНЫЕ ВОПРОСЫ

1.Какая система называется позиционной? Приведите примеры таких

систем.

2.Какая система называется непозиционной? Приведите примеры таких систем.

3.Правила какой арифметики используются при переводе числа из одной системы счисления в другую делением на основание новой системы?

81

82

ЛАБОРАТОРНАЯ РАБОТА №8 ПРЕОБРАЗОВАНИЕ ВЫРАЖЕНИЙ БУЛЕВОЙ АЛГЕБРЫ

1. ЦЕЛЬ РАБОТЫ

Изучить методы преобразования выражений булевой алгебры.

2. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

Булевой алгеброй называется непустое множество A с двумя бинарными операциями или (аналог конъюнкции), (аналог

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

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

6.Дополнительность:

7.Идемпотентность:

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

9.Аннулирующее свойство единицы:

10.Свойство нуля:

11.Свойства инверсии (инволютивность):

12. Правило вычеркивания: a b a b a

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

Шаг 1. Если в функции имеются операции, отличные от И, ИЛИ, НЕ,

82

83

то используем следующие свойства для их устранения:

x1 x2 x1 x2 x1 x2 (x1 x2 ) (x1 x2 ) x1 x2 x1 x2

x1 / x2 x1 x2

x1 x2 x1 x2 x1 x2

Шаг 2. Используем свойства инверсии и законы де Моргана чтобы каждая операция отрицания относилась только к одной переменной.

Шаг 3. Используем свойства дистрибутивности и другие свойства, чтобы получить нормальную форму.

Например, преобразовать в нормальную дизъюнктивную форму функцию f (a,b,c) (a b) c .

f (a,b,c) (a b) c (a b) c (a b) c (a b) c (a b) c

ac bc abc

Способы преобразования НФ в СНФ. Совершенная нормальная форма отличается от нормальной формы (НФ) тем, что всегда содержит термы только максимального ранга и дает однозначное представление функции.

Произвольная нормальная дизъюнктивная форма (НДФ) переводится в СНДФ следующим образом.

Пусть f ДНФ Fj . Тогда:

fСДНФ F j xi F j xi

где xi – переменная, которая не входит в данный терм Fj .

Произвольная НКФ переводится в СКНФ путем следующего преобразования:

Пусть fНКФ j . Тогда:

fСКНФ j xi xi ( j xi ) ( j xi )

Переведем в СДНФ функцию из предыдущего примера: f (a,b,c) ac bc abc acb acb bca bca abc

abc abc abc abc abc

Если выражение задано в произвольном виде и его необходимо представить в виде СКНФ, то проще всего воспользоваться следующим правилом:

Преобразование в СКНФ выражения произвольного вида. Процесс преобразования функции осуществляется для исходной функции, представленной таблицей истинности в соответствии с выражением:

83

84

x,если 1

где x

x,если 0

Например, представить функцию f (a,b,c) ab c в виде СКНФ. Таблица истинности для данной функции имеет вид:

нулевые значения на наборах 0, 4, 6. Тогда в соответствии с (1) получим: f (a,b,c) (a b c) (a b c) (a b c) .

Способы преобразования НФ в СНФ. Совершенная нормальная форма отличается от нормальной формы (НФ) тем, что всегда содержит термы только максимального ранга и дает однозначное представление функции.

Отчет по лабораторной работе должен содержать следующие разделы:

титульный лист;

цель работы:

задание на лабораторную работу;

ход работы;

ответы на контрольные вопросы;

выводы по проделанной работе.

84

85

5. ЗАДАНИЕ НА РАБОТУ

Приведенные логические выражения:

преобразовать в СДНФ;

преобразовать в СКНФ;

преобразовать в базис «И-ИЛИ-НЕ» и минимизировать.

1ac b cd ad

2abc abcd ac a cd

3ad ac abd ac / d

4a ad abd ac / abd

5abc abcd ac ac

6(a b) cd

6.КОНТРОЛЬНЫЕ ВОПРОСЫ

1.В чем отличие булевой алгебры от алгебры логики?

2.Чем отличаются совершенная нормальная и нормальная формы представления функций?

3.Перечислите способы представления функций булевой алгебры.

85

86

ЛАБОРАТОРНАЯ РАБОТА №9 МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ С ПОМОЩЬЮ КАРТ КАРНО

1. ЦЕЛЬ РАБОТЫ

Изучить методы преобразования выражений булевой алгебры.

2. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ Карта Карно – это двумерная табличная форма представления булевой

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

таблица истинности булевой функции. Карта содержит 2n клеток, где n – число аргументов функции. Таким образом, каждому из наборов значений аргументов (СДНФ) соответствует одна клетка карты, и в эти клетки вписываются нули или единицы, представляющие значения функции на данном наборе.

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

Правила минимизации следующие:

1.Две соседние клетки (два 0-куба) образуют один 1-куб. При этом клетки, лежащие на границах карты, также являются соседними по отношению друг к другу.

2.Четыре вершины могут объединяться, образуя 2-куб, содержащий две независимые координаты.

3.Восемь вершин могут объединяться, образуя один 3-куб.

4.Шестнадцать вершин, объединяясь, образуют один 4-куб и т.д.

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

Рисунок 1 – Минимизация функции пяти переменных с помощью карты Карно

86

87

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

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

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

Рисунок 2 – Построение карты Карно с помощью шестнадцатиклеточных карт

Особенную роль в процессе минимизации логических формул играют

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

87

88

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

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

Отчет по лабораторной работе должен содержать следующие разделы:

титульный лист;

цель работы:

задание на лабораторную работу;

ход работы;

ответы на контрольные вопросы;

выводы по проделанной работе.

88

89

5. ЗАДАНИЕ НА РАБОТУ

Доопределить оптимальным образом и минимизировать с помощью карты Карно частичные логические функции.

6. КОНТРОЛЬНЫЕ ВОПРОСЫ

1.Какая логическая функция называется частичной?

2.Сколько ячеек содержит карта Карно для функции семи переменных?

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

89

90

ЛАБОРАТОРНАЯ РАБОТА №10 МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ МЕТОДОМ КВАЙНА-МАК-КЛАСКИ

1. ЦЕЛЬ РАБОТЫ

Изучить метод Квайна-Мак-Класки минимизации логических функций.

2. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ Метод Квайна-Мак-Класки является одним из формальных методов

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

Перед началом вычислений производится упорядочение этого комплекса по нормам векторов (весам наборов), при этом 0-кубы разбиваются на классы по количеству единиц в них.

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

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

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

На первом этапе первого цикла выполняются все возможные склеивания между 0-кубами. Результаты помещаются в продолжение таблицы. Затем производятся все поглощения 0-кубов 1-кубами. Если останутся 0-кубы, не поглощенные в результате второго этапа, им присваивается метка «первичная импликанта». На этом первый цикл склеивания и поглощения заканчивается.

Второй цикл выполняется аналогично, но уже над комплексом С1 ,

составленным из 1-кубов. Циклы продолжаются до тех пор, пока это возможно.

Как только все циклы склеивания окончены, составляется таблица, строками которой являются первичные импликанты, а столбцами — исходные термы. Если в некоторый минитерм СДНФ входит какая-либо из первичных импликант, то на пересечении соответствующего столбца и строки ставится метка. Для полученной таблицы производится выбор минимального покрытия – такой совокупности первичных импликант, которая включает метки во всех столбцах, по крайней мере, по одной метке в каждом столбце. При нескольких возможных вариантах такого выбора

90