Основные принципы построения карт Карно

1) Карты Карно – это такие таблицы задания ФАЛ (плоская развертка n-мерных кубов), что склеивающиеся между собой конституенты единицы или нуля расположены в соседних клетках: по горизонтали и по вертикали клетки таблицы отличаются лишь значением одной переменной.

 

2) Клетки, расположенные по краям таблицы считаем соседними и обладают этим же свойством.

 

Например:

1) n=2

карты Карно диаграммы Вейча

 

 

2) n=3

 

 

3) n=4

 

4) n=5

Для построения используют две карты Карно четырех переменных.

Например:

Минимизировать на картах Карно функцию f(x₁,x₂,x₃,x₄), которая равна единице на наборах с номерами – 0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 15 (предыдущий пример).

Построим двоичные наборы, на которых задана функция.

№ набора	Наборы	f (x 1, x 2, x 3, x4)

 

Построим Карты Карно для заданной функции.

 

00

Таким образом,

 

Задание к лабораторной работе

1. Минимизировать функцию трех переменных F(x,y,z) c использованием куба, карт Карно, методом Квайна – Мак-Класки. Функция F(x,y,z) задана в лабораторной работе № 3.

2. Сгенерировать по указанному ниже алгоритму функцию Q(x₁, x₂, x₃, x₄).

3. Минимизировать функцию четырех переменных Q(x₁,x₂,x₃,x₄) c использованием куба, карт Карно и метода Квайна – Мак-Класки.

Алгоритм генерации варианта

1. Записать строку S = <ФИО >.

2. Удалить в строке S все повторные вхождения букв.

3. Пронумеровать все буквы получившейся строки таким образом, что n(S_i) - номер буквы в русском алфавите.

4. Для генерации функции Q(x₁,x₂,x₃,x₄) оставить первые 7 неповторяющихся чисел, полученных после преобразования . Полученные значения определяют единичные наборы функции Q(x₁,x₂,x₃,x₄).

Контрольные вопросы

1. Определение логической переменной и буквы.

2. Определение элементарной конъюнкции.

3. Нормальная и совершенная дизъюнктивные формы.

4. Ранг конъюнкции. Длина ДНФ.

5. Кратчайшая и минимальная ДНФ.

6. Сокращенная ДНФ.

7. Максимальные интервалы.

8. Карты Карно и диаграммы Вейча.

9. Метод Квайна: минитермы, импликанты (простые и существенные).

 

ЛИТЕРАТУРА

 

1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. – М.: Мир, 1980.

2. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990.

3. Столл Р. Множества.Логика.Аксиоматические теории. – М.: Просвещение, 1968.

4. Поспелов Д.А. Логические методы анализа и синтеза схем. – М.: Энергия,1974. – 268с.

5. Шоломов Л.А. Основы теории дискретных логических вычислительных устройств. – М.: Наука,1980.

6. Андерсон Дж. Дискретная математика и комбинаторика.– М.: Мир, 2001. – 960с.

7. Міхайленко В.М., Федоренко Н.Д., Демченко В.В. Дискретна математика: Підручник. – Київ: Вид-во Європ. ун-ту, 2003. – 318с.

 

СОДЕРЖАНИЕ

 

Лабораторная работа № 1

Способы задания множеств. Операции над множествами.

Основные соотношения алгебры множеств………………………..................2

Лабораторная работа № 2

Отношения на множествах………… …………………………………….…..8

Лабораторная работа № 3

Булевы функции. Законы алгебры логики. Аналитические способы описания. Полные системы функций………………………………………..17

Лабораторная работа № 4

Методы минимизации функций алгебры логики …………………………...32