Цикломатическим числом конечного НГ G наз-ся неотрицательное:
V(G)=Vc + Ve – Vv, где
Vc - число связанных компонент графа
Ve - ребер
Vv – вершин
41 Элементы теории автоматов.
42. Правило подстановки F вместо х.
Правило подстановки формулы F вместо переменной х. При подстановке ф-kf вместо пре-й х все вхождения пер-й х в исходное соотн-е д.б. одновременно заменены ф-й F. Правило применяется к эквивал-м соот-м для получения эк-х соот-й.
43. Правило замены подформул.
Правило замены подформул. Если какая-либо ф-ла F, описываюшая ф-ю f, содержит F1 в качестве подформулы, то замена F1 на эквивал-ю F2 (F1=F2) не изменит ф-и f; полученная при такой замене ф-ла F’ эквив-на исходной F. Правило замены подформул позволяет, используя известные эквив-е соотн-я, получать ф-лы, эквив-е данной, в частности, упрощать формулы.
44. Основные экв-е соотн-я
Соотношения:
(*=
или 
)
Ассоциативность конъюнкции и дизъюнкции:
x1*(x2*x3)=(x1*x2)*x3=x1*x2*x3 14
Коммутативность
x1*x2=x2* x1 15
Дистрибутивность К отн-но Д
x1 (x2x3)=x1x2 x1x3 16
Дистрибутивность К отн-но Д
x1 (x2x3)=(x1x2) (x1x3) 17
Идемпотентность
x*x=x 18
Закон 2-го отрицания
=х
19
Св-ва констант 0 и 1 20
х1=х;
х0=0; х1=1; х0=х; 
=1; 
=0
Правило Де Моргана
=
; 
= 21
Закон противоречия х
=0 22
Закон исключенного третьего х=1 23
Поглощение хху=х; х(ху)=х 24
Склеивание хух
=х
25
Обощенное склеивание
xzy
xy=xzy 26
xy=xy 27
45. Процедура приведения к ДНФ.
Приведение к КНФ и ДНФ можно осущ-ть 2 сп:
1) с помощью таблиц
2) с помощью эквивалентных преобразований
Алгоритм:
1) все отрицанияя «спустить» до переменных с помощью 19 и 21.
2) раскрыть скобки с помощью 14,16,17
3) удалить лишние конъюнкции и повторения пер-х в конъюнкциях с помощью 18,22,23
4) удалить константы с помощью 20
ДНФ – СДНФ – расщепление (обратное склеивание: использ-е 25 в обратную сторону) конъюнкций, к-е содержат не все пер-е.
46. Процедура приведения к КНФ.
Приведение к КНФ и ДНФ можно осущ-ть 2 сп:
1) с помощью таблиц
2) с помощью эквивалентных преобразований
Алгоритм:
1.применить к F правило 2 отрицания и привести к ДНФ.
2. С помощью правил де Моргана освободицца от 2 отрицания и преобр-ть отрицания элем-х конъюнкций в элем-е дизъюнкции.
47. Метод Блейка-Порецкого
Метод позволяет получать сокращенную ДНФ булевой функции f из ее произвольной ДНФ. Базируется на применении формулы обобщенного склеивания:
Ax v B = Ax v B v AB, справедливость которой легко доказать.
Действительно,
Ax = Ax v ABx;
B = B v AB.
Следовательно,
Ах
v В =
Ах v АВх v В v АВ =
Ах V В V АВ.
В основу метода положено следующее утверждение: если в произвольной ДНФ булевой функции f произвести все возможные oбобщенные склеивания, а затем выполнить все поглощения, то в результате получится сокращенная ДНФ функции f.
Пример.
Булева функция f задана произвольной ДНФ.
f = /x1/x2 v x1/x2/x3 v x1x2.
Найти методом Блейка - Порецкого сокращенную ДНФ функции f. Проводим обобщенные склеивания. Легко видеть, что первый и второй элемент заданной ДНФ допускают обобщенное склеивание по переменной х1. В результате склеивания имеем:
/x1/x2
v x1/x2/x3
= /x1/x2 v x1/x2/x3 v /x2/x3.
Первый и третий элемент исходной ДНФ допускают обобщенное склеивание как по переменной х1, так и по х2. После склеивания по x1 имеем:
12
v x1x2 = 12
v x1x2 v 2x2 = 12
v x1x2.
После склеивания по x2 имеем:
12
v x1x2 = 12
v x1x2 v 1x1 = 12
v x1x2.
Второй и третий элемент ДНФ допускают обобщенное склеивание по переменной х2. После склеивания получаем:
x123
v x1x2 =
= x123
v x1x2 v x1x3.
Выполнив последнее обобщенное склеивание, приходим к ДНФ:
f = 12 v x123 v 23 v x1x2 v x13.
После выполнения поглощений получаем:
f = 12 v 23 v x1x2 v x13.
Попытки дальнейшего применения операции обобщенного склеивания и поглощения не дают результата. Следовательно, получена сокращенная ДНФ функции f. Далее задача поиска минимальной ДНФ решается с помощью импликантной матрицы точно так же, как в методе Квайна."
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.