Лабораторная работа №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. Получить результаты работы алгоритма для четырех видов различных исходных данных.

© 2011-2024 Контрольные работы по математике и другим предметам!