Материал: Методические указания к выполнению лабораторных работ по дисциплине «Дискретная математика» для студентов направления подготовки бакалавров. Собенина О.В., Пак А.А

Говорят, что ПФ задана в конъюнктивной нормальной форме (КНФ), если она является конъюнкцией элементарных дизъюнкций.

Пример. (X Y Z) (X Y) - КНФ.

На основе равносильных преобразований любая формула может быть приведена к нормальной форме (ДНФ или КНФ).

Совершенной дизъюнктивной нормальной формой (СДНФ) данной ПФ называется ДНФ, в которой каждая элементарная конъюнкция содержит все переменные – без отрицания или с отрицанием, но не вместе.

Совершенной конъюнктивной нормальной формой (СКНФ) данной ПФ называется КНФ, в которой каждая элементарная дизъюнкция содержит все переменные – без отрицания или с отрицанием, но не вместе.

Существует два способа перехода к совершенным формам табличный и аналитический.

Алгоритм 1

(табличный способ приведения к СДНФ)

1.Составить таблицу истинности данной ПФ.

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

3.Образовать дизъюнкцию всех полученных элементарных конъюнкций, которая и составляет СДНФ.

Алгоритм 2

(табличный способ приведения к СКНФ)

1.Составить таблица истинности данной ПФ.

2.Рассмотреть те строки, в которых формула принимает истинностное значение 0. Каждой такой строке поставить в соответствие элементарную дизъюнкцию, причем переменная,

34

принимающая значение 1, входит в нее с отрицанием, а 0 – без отрицания.

4. Образовать конъюнкцию всех полученных элементарных дизъюнкций, которая и составляет СКНФ.

воспользуемся алгоритмами 3 и 4. Построим таблицу истинности и на ее основе составим СДНФ и СКНФ.

( X Y Z ) ( X Y Z ) ( X Y Z ) ( X Y Z )

Построение СДНФ

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

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

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

35

кортежей значений, то алгоритм построения СДНФ дает синтаксически однозначный результат. Переменные всегда перечисляются в лексикографическом порядке, а кортежи булевских значений – в порядке возрастания целых чисел, задаваемых кортежами как двоичными шкалами. Такой порядок считается установленным.

Алгоритм вычисления значения булевой функции

Некоторые классы формул допускают более эффективную интерпретацию по сравнению с алгоритмом Eval. Рассмотрим алгоритм вычисления значения булевой функции, заданной в виде СДНФ, для заданных значений переменных x1, … , xn. В этом алгоритме используется следующее представление данных. СДНФ задана массивом f array [1..k,1..n] of 0..1, где строка f [i,*] содержит набор значений 1,..., n , для кото-

рого f ( 1,..., n) 1, i 1,k, k n.

Быстрое вычисление значения СДНФ имеет не только теоретическое, но и большое практическое значение. Например, во многих современных программах с графическим интерфейсом для составления сложных логических условий используется наглядный бланк в виде таблицы: в клетках записывается условие, причем клетки одного столбца считаются соединенными конъюнкциями, а столбцы – дизъюнкцией, т.е. образуют ДНФ (или наоборот, в таком случае получается КНФ). В частности, так устроен графический интерфейс QBE (Query-by-Example), применяемый для формулировки логических условий при запросе к СУБД.

Алгоритм. Алгоритм вычисления СДНФ

Вход: массив, представляющий СДНФ: f : array [1..k, 1..n] of

0..1;

множество значений переменных x : array [1..n] of

0..1.

37

{ x11 ... xnn 1 ( 1,..., n ) x11 ... xnn 1} end for

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

Замечание. В алгоритме использован оператор next, которому здесь придается следующая семантика: выполнение текущего цикла прерывается, а выполнение программы продолжается со следующего шага цикла, указанного в оператора next. Такого рода операторы называются операторами структурного перехода. Операторы структурного перехода присутствуют в некоторых реальных языках программирования (например оператор continue в языке C), хотя обычно имеют более ограниченную семантику по сравнению с использованным здесь оператором next.

Этот алгоритм в худшем случае выполняет kn сравнений, а в среднем – гораздо меньше, т.е. он существенно эффективнее общего алгоритма интерпретации.

Вопросы для самопроверки

1.Что понимают под высказыванием? Привести пример высказывания.

2.Какое предложение не будет высказыванием? Привести пример такого предложение.

3.Привести пример сложного высказывания.

4.Какие операции над высказываниями существуют?

5.Каков приоритет операций над высказываниями?

38