Лабораторная работа №3
БУЛЕВЫ ФУНКЦИИ
Цель работы: изучение и реализация алгоритмов работы с булевыми функциями.
Методические указания
Теоретический материал приведен в главе 5. Рассмотрим алгоритмы, связанные с булевыми функциями. В алгоритмах используются следующие обозначения:
Конструкция
For X Î M Do
P(X)
End For
Означает применение процедуры Р Ко всем элементам множества М.
Оператор
Select M Î М
Означает выбор Произвольного Элемента Т Из множества М. Этот оператор часто необходим в «переборных» алгоритмах.
Оператор
Yield X
Означает возврат значения Х, Но при этом выполнение функции не прекращается, а продолжается со следующего оператора.
Совершенные нормальные формы
Алгоритм 1. Построение СДНФ
Вход: Вектор X : Array [l..N] Of String Идентификаторов переменных,
Матрица V : Array [1..2N, l..N] Of 0..1 всех различных наборов значений переменных,
Вектор F : Array [1..2N] Of 0..1 соответствующих значений функции.
Выход: Последовательность символов, образующих запись формулы СДНФ для заданной функции.
F := False { признак присутствия левого операнда дизъюнкции }
For I From 1 To 2N Do
If F[I] = 1 then
If F then
Yield 'Ú' { добавление в формулу знака дизъюнкции }
Else
F : = True
End If
G :=False { признак присутствия левого операнда конъюнкции }
For J From 1 to N do
If G Then
Yield 'Ù' { добавление в формулу знака конъюнкции }
Else
G : =true
End if
If V[I, j] = 0 Then
Yield 'Ø' { добавление в формулу знака отрицания }
End If
Yield X[J] { добавление в формулу идентификатора переменной }
End for
End if
End for
Алгоритм 2. Алгоритм вычисления СНДФ
Вход: Массив, представляющий СДНФ: F : Array [1..K, 1..N] Of 0..1;
Множество значений переменных X : Array [1..N] Of 0..1.
Выход: 0..1 – значение булевой функции.
For I From 1 To K Do
For J From 1 To N Do
If F[I, j] ¹ x[J] Then
Next for I
End if
End for
Return 1
End for
Return 0 {все слагаемые в дизъюнкции = 0}
Алгоритм построения бинарного кода Грея
Данный алгоритм генерирует последовательность всех подмножеств поэлементного множества, причем каждое следующее подмножество получается из предыдущего удалением или добавлением одного элемента.
Алгоритм 3. Алгоритм построения бинарного кода Грея
Вход: N >0 — мощность множества
Выход: последовательность кодов подмножеств В
В : Array [l..n] Of 0..1 { битовая шкала для представления подмножеств }
For i From 1 To n Do
B[I]: = 0 { инициализация }
End For
Yield В { пустое множество }
For I From 1 to 2N-1 Do
P: =Q(I) { определение элемента, подлежащего добавлению или удалению }
В[Р] := 1 - В[Р] { добавление или удаление элемента }
Yield В { очередное подмножество }
End For
Proc Q(I) { количество 2 в разложении I На множители + 1 }
Q: = 1; J : = I
While J Четно Do
J:=j / 2; q :=q + 1
End while
Return Q
End Proc
Пример
Протокол выполнения алгоритма для N = 3.
|
I |
Р |
В | ||
|
0 |
0 |
0 | ||
|
1 |
1 |
0 |
0 |
1 |
|
2 |
2 |
0 |
1 |
1 |
|
3 |
1 |
0 |
1 |
0 |
|
4 |
3 |
1 |
1 |
0 |
|
5 |
1 |
1 |
1 |
1 |
|
6 |
2 |
1 |
0 |
1 |
|
7 |
1 |
1 |
0 |
0 |
Задание
1. Реализовать алгоритм (на любом языке программирования), описанный в теоретическом материале (номер варианта соответствует номеру алгоритма).
2. Получить результаты работы алгоритма для четырех видов различных исходных данных.
| < Предыдущая | Следующая > |
|---|
