End for

End for

End for

End for

End if

End for

End if

End for

End if

End if

Else

End if

Else

End for

Методические указания

БУЛЕВЫ ФУНКЦИИ

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

Цель работы: изучение и реализация алгоритмов работы с булевыми функциями.

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

Конструкция

for x Î M do

P(x)

означает применение процедуры Р ко всем элементам множества М.

Оператор

Select m Î М

означает выбор произвольного элемента т из множества М. Этот оператор часто необходим в «переборных» алгоритмах.

Оператор

yield x

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

Совершенные нормальные формы

Алгоритм 1. Построение СДНФ

Вход: вектор X: array [l.. n ] of string идентификаторов переменных,

матрица V: array [1..2 ⁿ, l.. n ] of 0..1 всех различных наборов значений переменных,

вектор F: array [1..2 ⁿ ] of 0..1 соответствующих значений функции.

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

f := false { признак присутствия левого операнда дизъюнкции }

for i from 1 to 2 ⁿ do

if F [ i ] = 1 then

if f then

yield 'Ú' { добавление в формулу знака дизъюнкции }

f: = true

g: = false { признак присутствия левого операнда конъюнкции }

for j from 1 to n do

if g then

yield 'Ù' { добавление в формулу знака конъюнкции }

g: =true

if V [ i, j ] = 0 then

yield ' Ø ' {добавление в формулу знака отрицания }

yield X [ j ]{добавление в формулу идентификатора переменной }

Алгоритм 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

return 1

return 0 {все слагаемые в дизъюнкции = 0}

Алгоритм построения бинарного кода Грея

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

Алгоритм 3. Алгоритм построения бинарного кода Грея

Вход: n > 0 — мощность множества

Выход: последовательность кодов подмножеств В

В: array [l..n] of 0..1 { битовая шкала для представления подмножеств }

for i from 1 to n do

B [ i ]: =0 { инициализация }

yield В {пустое множество }

for i from 1 to 2 ⁿ -1 do

p: =Q (i){ определение элемента, подлежащего добавлению или удалению }

В [ р ]:=1 - В [ р ]{добавление или удаление элемента }

yield В {очередное подмножество }

proc Q (i){количество 2 в разложении i на множители + 1 }

q: = 1; j: = i

while j четно do

j:=j / 2; q:=q + 1

Дата добавления: 2014-12-27