Программированиеи компьютеры /
Министерство образования Р.Ф.
Филиал Орловского государственного технического университета в г. Братске
Кафедра прикладной информатики в экономике
Дисциплина:
Вычислительные системы, сети и телекоммуникации.
Практическая работа №2
ОСНОВЫ БУЛЕВОЙ АЛГЕБРЫ
Вариант 1
Выполнил: студент группы ПИ - 03 - 351400 Н. В. Алексеев
Проверил: старший преподаватель Д. С. Колтыгин
г. Братск 2004
1. ЦЕЛЬ РАБОТЫ
1.1. Познакомиться с основными понятиями алгебры логики; изучить основные операции булевой алгебры; получить практичес¬кие навыки в построении таблиц истинности и булевых выражений.
1.2. Изучить основные законы и соотношения булевой алгеб¬ры; получить практические навыки по преобразованию и упрощению булевых выражений методами непосредственных преобразований и карт Карно.
3. ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ
3.1. Определить значения истинности высказываний, заданных табл.3.1.1
Таблица 3.1.1
Вариант Высказывания
1 АЛУ микропроцессора выполняет операцию сложения или декодирования команд
Пусть X=”АЛУ микропроцессора выполняет операцию сложение или декодирования команд”, тогда A=”АЛУ микропроцессора выполняет операцию сложения”, B=” АЛУ микропроцессора выполняет операцию декодирования команд”. Следовательно:
X=A или B => X=A+B
Выражение A истинно, следовательно, A=1, тогда:
X=1+B=1
Значит выражение X истинно, независимо от истинности выражения B.
3.2. Построить таблицу истинности по заданной в табл. 3.2.1 булевой функции.
Таблица 3.2.1
Вариант Высказывания
1 f(x,y,z) = (x + )∙( + y)
Таблица истинности функции f(x,y,z):
x y z
x +
x∙z
+ y
f(x,y,z)=(x + )∙( + y)
0 0 0 1 1 0 1 1 1
0 0 1 1 1 0 1 1 1
0 1 0 0 0 0 1 1 0
0 1 1 0 0 0 1 1 0
1 0 0 1 1 0 1 1 1
1 0 1 1 1 1 0 0 0
1 1 0 0 1 0 1 1 1
1 1 1 0 1 1 0 1 1
3.3. По заданной таблице истинности (табл. 3.3.1) построить булевы выражения:
- в форме канонической суммы минтермов;
- в форме канонического произведения макстермов.
Таблица 3.3.1
Вариант Входные
переменные x 0 1 0 1 0 1 0 1
y 0 0 1 1 0 0 1 1
z 0 0 0 0 1 1 1 1
1 f1 1 0 0 1 0 0 1 1
1) СДНФ:
f(x,y,z)= ∙ ∙ +x∙y∙ + ∙y∙z+x∙y∙z
2) СКНФ:
f(x,y,z)=( +y+z)∙(x+ +z)∙(x+y+ )∙( +y+ )
3.4. Используя основные законы и соотношения булевой алгебры, выполнить эквивалентные преобразования булевых выражений, заданных в табл. 3.4.1.
Таблица 3.4.1
Вариант Булево выражение Вид эквивалентного преобразования
1 1∙x3 + 1∙ 3 + x1∙x2
упростить
f(x1,x2,x3)= 1∙x3 + 1∙ 3 + x1∙x2= 1(x3+ 3)+ x1∙x2= 1+ x1∙x2= = 1(x2+ 2)+ x1∙x2= 1∙x2+ 1∙ 2+x1∙x2= 1∙x2+ 1∙ 2+ 1∙x2+x1∙x2= =( 1∙x2+ 1∙ 2)+( 1∙x2+x1∙x2)= 1∙( x2+ 2)+ x2∙( 1+x1)= 1+x2
3.5. Минимизировать булевы функции (табл.3.5.1), заданные в форме канонической суммы минтермов, используя метод непосредственных преобразований и метод Вейча-Карно.
Таблица 3.5.1
Вариант Булевы функции
1 1∙ 2∙ 3 + 1∙x2∙x3 + x1∙x2∙ 3 + x1∙x2∙x3
Метод Вейча-Карно:
1) Таблица истинности:
x1 x2 x3 f(x1,x2,x3)= 1∙ 2∙ 3+ 1∙x2∙x3+x1∙x2∙ 3+x1∙x2∙x3
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
2) Карта Карно:
x2∙x3
x1
00
01
11
10
0
1 0
1 0
1 0 0
1 1
f(x1,x2,x3)= 1∙ 2∙ 3+x1∙x2+x2∙x3
Другой метод:
1) Заполняем таблицу: единичками те ячейки, которые находятся на пересечении неизвестных взятого минтерма. Сделать так для всех минтермов, составляющих выражение, которое необходимо минимизировать.
Все остальные ячейки заполнить нулями.
Обвести рядом стоящие единички («склеить» с единичками в смежных ячейках), сумма которых должна быть равна 2n. Если у ячейки с единичкой нет смежной ячейки с единичкой (n=0), то оювести одну единичку.
Данная таблица – это представление шара на плоскости, то есть, так же как и в методе Вейча-Карно, можно объединять единички, стоящие в ячейках, расположенных в разных концах столбца или строки.
x1 1
2
0 0
0 1
x2 1
1 1 0
1 1 1 0
2
0 0 0 1
3
x3 3
2) Объединенные области записываем в виде булева функции: записываем в минтерм только те переменные, на пересечении которых стоит данное объединение. Делаем так для всех объединений, и записываем выражение в виде канонической суммы минтермов.
f(x1,x2,x3)= 1∙ 2∙ 3+x1∙x2+x2∙x3
Полученное выражение равно выражению, полученному с помощью метода Вейча-Карно.