Контрольные вопросы

Задание для лабораторной работы.

1. Для неориентированного графа варианта, заданного файлом вида «таблица рёбер», определить, является ли данный граф эйлеровым (ответ обосновать). Если да, то построить эйлеров цикл в соответствии с алгоритмом (записи в списках инцидентности вершин полагать упорядоченными по возрастанию номеров вершин). Отчёт должен содержать:

1. текст входного файла и графическое представление графа;

2. результирующий и вспомогательный стеки построения эйлерова цикла;

3. порядок обхода вершин эйлерова цикла (если он существует).

2. Для неориентированного графа варианта, заданного файлом вида «таблица рёбер», определить, является ли данный граф гамильтоновым, используя алгоритм с возвратом. Если да, то достаточно ограничиться одним вариантом гамильтонова цикла (записи в списках инцидентности вершин полагать упорядоченными по возрастанию номеров вершин). Отчёт должен содержать:

1. текст входного файла и графическое представление графа;

2. дерево построения гамильтонова цикла;

3. порядок обхода вершин гамильтонова цикла (если он существует).

Лабораторная работа №8 совершенные нормальные формы булевых функций

Цель работы:

Теоретические сведения

Введем следующие обозначения .

Легко проверить, что ,.

Теорема 1. (о разложении булевых функций). Любую булеву функцию можно представить в виде

(5.1)

где дизъюнкции берутся по всем возможным наборам ().

Теорема 2. Всякая булева функция (кроме 0) имеет единственную СДН-форму

.

С помощью принципа двойственности легко доказать представление функции СКН-формой.

Теорема 3. Всякая булева функция (кроме 1) имеет единственную СКН-форму

.

С помощью совершенных нормальных форм можно решить проблему выполнимости или опровержимости формулы.

Для того чтобы найти, при каких значениях высказывательных переменных формула является выполнимой, необходимо построить ее СДН-форму. Количество таких наборов равно числу полных элементарных конъюнкций, так как, если одна из них истинна, то истинна и вся формула. Элементарная конъюнкция истинна, когда истинны все её составляющие, следовательно, если переменная входит в неё без отрицания, то она принимает значение 1, а если с отрицанием, то – 0. Аналогично, для решения задачи опровержимости строится СКН-форма.

Совершенные нормальные формы используются также для решения задачи, обратной задаче разрешимости – построение реализации булевой функции, заданной таблицей. Нули функции определяют полные элементарные дизъюнкции, входящие в СКН-форму функции. Такая дизъюнкция строится так, чтобы все составляющие ее переменные или их отрицания обращались в нуль, т.е. если значение переменной 0, то переменная входит в дизъюнкцию без отрицания, если – 1, то – с отрицанием. Соответственно, по единицам булевой функции можно построить ее СДН-форму.

Для вычисления значений булевых функций в общем случае надо использовать сложную рекурсивную процедуру (см. [3], п. 3.2.1.), т.к. надо определить все подформулы вплоть до Х_i или . При использовании совершенных форм алгоритм вычисления будет намного проще и эффективнее.

В ЭВМ совершенные формы представляются в виде матрицы размера kn, состоящей из нулей и единиц, где k – число членов разложения (элементарных конъюнкций или дизъюнкций); n – число пропозиционных переменных. Матрица F представляет собой часть общей таблицы истинности, определяющей булеву функцию f. Для представления СДНФ берутся строки, соответствующие единицам f, а для СКНФ – строки, соответствующие нулям f.

Пусть х – массив пропозиционных переменных. Предположим, х_i получили некоторые значения и необходимо вычислить значение нормальной формы f. Предлагаются следующие правила:

Эффективность данного алгоритма проявляется также в том, что цикл можно прервать, как только будет найдено необходимое значение i или j.

Например, вычислим значение функции f(x₁, x₂) = x₁  x₂ при x₁ = 0; x₂ = 1. Запишем таблицу истинности функции f:

x1	x2	f
0	0	1
0	1	0
1	0	0
1	1	1

Тогда F_СДНФ = ;F_СКНФ = . Поскольку ни одна из строкF_СДНФ, которая определяет наборы значений переменных, соответствующие 1 функции, не совпала с заданными значениями х_j, то f (0, 1) = 0.

Тоже самое можно определить и по СКНФ, так как первая строка F_СКНФ совпадает со значениями х_j, то f (0, 1) = 0.

Сформулируем законы булевой алгебры и производные от них формулы в терминах булевых функций.

1. X Y  Y X, X Y  YX.

2. (X Y)Z  X (YZ), (XY)Z  X(YZ).

3. XX  X, XX  X.

4. X(XY)  X, X(XY)  X.

5. X (YZ)  (X Y)(X Z), X (YZ)  (XY)(XZ).

6. X0  Л, X1  X,

X0  X, X1  1.

7. , .

8. .

9. 0.

10. 1.

11. .

12. .

13. ,

14. ,

Для преобразования одной совершенной нормальной формы в другую нужно вначале максимально упростить исходную форму, воспользовавшись законами 4, 5, 13, 14. Затем преобразовать упрощенную формулу по свойству взаимной дистрибутивности 5, получив нормальную форму, и развернуть её в требуемую совершенную форму по законам склеивания 13.