Построение совершенной дизъюнктивной и конъюнктивной нормальных форм

           

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное  бюджетное образовательное учреждение

высшего профессионального  образования

«тюменский государственный  нефтегазовый  университет»

ФИЛИАЛ  « ТОБОЛЬСКИЙ ИНДУСТРИАЛЬНЫЙ ИНСТИТУТ »

Кафедра математики и информатики

 

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

по дисциплине «Дискретная  математика» 

на тему Построение совершенной дизъюнктивной и конъюнктивной нормальных форм.

 

 

 

 

 

 

 

 

 

Выполнила студентка  группы ИВТ(б)-11

____________Сердученко Ю.В

      (подпись)

 

 

Руководитель  курсового проекта:

к.п.н., доцент ___________ Татьяненко С.А.

       (подпись) 

 

 

 

 

 

 

 

 

Тобольск, 2012г.

 

Содержание

 

Введение……………………………………………………………………………..3 Глава 1. Булева алгебра. 4

1.1 Булевы функции одной переменной 5

1.2 Булевы функции двух переменных 5

1.3  Реализация функций формулами. 6

1.4 Равносильные формулы 7

1.5 Законы булевой алгебры 7

1.6 Полнота системы булевых функций 9

Глава 2. Двойственность функций 10

2.1 Принцип двойственности 10

Глава 3. Совершенная дизъюнктивная нормальная форма, совершенная конъюнктивная нормальная форма, дизъюнктивная нормальная форма и конъюнктивная нормальная форма 12

3.1 СДНФ И СКНФ 12

3.2 ДНФ И КНФ 16

Глава 4. Примеры приведения формул  Алгебры Высказываний к  КНФ,ДНФ,СКНФ И СДНФ 20

Заключение………………………………………………………………………...23

Список литературы 24

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

Середина XIX века – Логическая алгебра (Булева алгебра)-Универсальный логический язык, который создал в 1847 году английский математик Джордж Буль(1815–1864). Он разработал исчисление высказываний, впоследствии названное в его честь булевой алгеброй. Пользуясь ею, можно закодировать любые утверждения, истинность или ложность которых нужно доказать, а затем манипулировать ими подобно обычным числам в математике.

Алгебра Буля широко применяется при проектировании и проверке электрических схем, в которых используются реле, работающие по принципу "да - нет", при программировании и проектировании ЭВМ, в операциях с переключателями, сигналами, схемами. В современной математической логике этот раздел значительно усовершенствован и разрабатывается как теория булевых алгебр, в том числе как алгебра множеств, алгебра высказываний и т. п. В области традиционной логики соотношения Алгебры Буля часто используются для иллюстрации и прояснения отношений между объемами понятий.

 

 

 

Данная курсовая работа состоит из следующих разделов:

1)введение

2)теоретическая часть

3)практическая часть

4)Заключение

5)Список используемой литературы

 

 

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

 

Перечень подлежащих разработке вопросов:

а) по теоретической части: булевы функции одной и двух переменных, формулы булевой алгебры, двойственные и самодвойственные функции, нормальные формы формул, полнота системы функций и др.

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

 

 

 

 

 

Глава 1. Булева алгебра

 

БУЛЕВА АЛГЕБРА (Алгебра логики) - область математики, содержащая правила обращения с множествами, а также с логическими утверждениями типа «и», «или». 
Создателем алгебры логики является живший в ХIХ веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний.

Логической (булевой) функцией (или просто функцией) n переменных y = f(x1, x2, …, xn)- называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1.

Переменные, которые могут принимать  только два значения 0 и 1 называются логическими переменными (или просто переменными). Заметим, что логическая переменная х может подразумевать под числом 0 некоторое высказывание, которое ложно, и под числом 1 высказывание, которое истинно. Например, высказывание “Волга впадает в Каспийское море” является истинным и, значит, с точки зрения дискретной математики принимает значение 1, а высказывание “в неделе 8 дней” является ложным, и переменная, которая заменяет это высказывание, принимает значение 0. Имеется много высказываний, которые либо истинны, либо ложны, но о которых мы не знаем, что имеет место на самом деле. Например, высказывание “студент Петров (имеется в виду конкретный человек) имеет дома компьютер”. Такого рода высказывания требуют проверки (конечно, если нам важен этот факт). Поэтому считаем, что переменная, заменяющая это высказывание, может принимать значение 0 или 1.

 

Обозначим множество {0;1} через  , т. е. .

Функция  f  из множества   называется булевой функцией переменных.  Напомним, что

 

Переменные булевых функций  могут принимать только значения 0 или 1 и называются булевыми переменными.

Множества всех булевых функции n переменных обозначается  , т.е.

Количество  всех булевых функции n переменных находится по формуле

 

Например, булевых функции 1 переменной

,

   булевых функции 2 переменных

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

1.1Булевы функции одной переменной

   

Значения

переменной   х

0

1

 

Название функции

Обозначение функции

Значения  функции

f1

Тождественный нуль

0

0

0

f2

Тождественная

х

0

1

f3

Отрицание

1

0

f4

Тождественная единица

1

1

1


                                       Таблица 1.Булевы функции одной переменной

 

1.2 Булевы  функции двух переменных

   

Значения   переменных                            

x1

0

0

0

1

1

0

1

1

x2

 

Название функции

Обозначение функции

Значения  функции

f1

Тождественный нуль

0

0

0

0

0

f2

Конъюнкция

&, 

, ·

0

0

0

1

f3

Отрицание импликации

0

0

1

0

f4

Тождественная первой переменной

0

0

1

1

f5

Отрицание импликации

0

1

0

0

f6

Тождественная второй переменной

0

1

0

1

f7

Сумма по модулю два, строгая дизъюнкция

0

1

1

0

f8

Дизъюнкция

0

1

1

1

f9

Стрелка Пирса

1

0

0

0

f10

Эквиваленция

1

0

0

1

f11

Инверсия второй переменной

1

0

1

0

f12

Импликация

1

0

1

1

f13

Инверсия первой переменной

1

1

0

0

f14

Импликация

1

1

0

1

F15

Штрих Шеффера

1

1

1

0

F16

Тождественная единица

1

1

1

1

1


                                                    Таблица 2. Булевы функции двух переменных

 

1.3  Реализация функций формулами.

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

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

ПРИМЕР

Построить таблицу истинности для  формулы  

x1

x2

0

0

0

1

0

1

0

1

1

0

0

1

1

1

1

1


 

                               Таблица 3.Таблица истинности формулы

Таким образом, формула    реализует функцию   (тождественная единица).

ПРИМЕР

Построить таблицу истинности для  формулы   .

x1

x2

0

0

0

0

0

0

1

0

0

1

1

0

0

1

1

1

1

1

0

1


                               Таблица 4. Таблица истинности  формулы

Таким образом, формула   реализует функцию   (дизъюнкция).

 

1.4 Равносильные формулы.

Формулы называются равносильными, если реализуют одну и ту же функцию.

Формула называется тождественно-истинной или тавтологией, если она реализует тождественную единицу.

Формула называется тождественно-ложной, если она реализует тождественный ноль.

1.5 Законы булевой алгебры.

Законами булевой алгебры называются следующие равносильности:

1.          Идемпотентность  

  

2.          Коммутативность  

 

3.         Ассоциативность  

 

4.         Дистрибутивность 

 

5.         Закон поглощения  

6.         Закон склеивания 

            

7.        Закон нуля

8.        Закон единицы      

                                                    

9.       Закон дополнения 

                                       

10.      Инволютивность    

                                                       

11.      Законы де Моргана 

         

  

 

 

 

1.6 Полнота системы булевых функций.

 

Система булевых функций называется полной в классе , если любая функция в классе является суперпозицией этих функций. Под классом подразумеваются все возможные булевы функции от n переменных.

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

Функцию, полученную из элементарных путем перенумерации аргументов и подстановки вместо аргументов в некоторых других булевых функций, называют суперпозицией функций. Нетрудно убедиться, что любая булева функция  от n аргументов является суперпозицией  элементарных функций, заданных табл.

Например: функция является суперпозицией  элементарных функций: отрицания, дизъюнкции, конъюнкции и импликации.

 

Теорема: Отрицание, дизъюнкция и конъюнкция образуют полную систему булевых функций

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

Полная система булевых функций  называется базисом, если она перестает быть полной при удалении, хотя бы одной из этих функций.

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

Для проверки полноты заданной системы  булевых функций может быть использовано следующее очевидное утверждение:

Если система - полная и любая  из функций f1, f2,...,fm может быть выражена с помощью суперпозиций через  функции g1, g2,…, gk, то система также  полная.

 

 

 

 

 

 

Глава 2. Двойственность функций

2.1 Принцип двойственности.

Двойственной для булевой функции   называется  булева функция:

.

ПРИМЕР

Функция  f  называется самодвойственной если  

Утверждение 1. Если функция f(x1, x2, …, xn) самодвойственная, то функция   тоже самодвойственная.

Утверждение 2. Чтобы функция была самодвойственной необходимо и достаточно, чтобы на всяких двух противоположных наборах она принимала разные значения.

Противоположными называются те наборы, которые в сумме дают         двоичный код числа (2n-1).

ПРИМЕР

Функция   является самодвойственной, т.к.    

 

ТЕОРЕМА (Закон двойственности)

Если формула равносильна формуле  ,  то формула  равносильна формуле 

(Если две равносильные формулы  заменить двойственными, то равносильность  сохранится). 

 

ТЕОРЕМА  (Принцип двойственности)

Двойственная к булевой  формуле может быть получена заменой  констант 0 на 1,1 на 0, Ù на Ú, Ú на Ù и сохранением структуры формулы (т.е. соответствующего порядка действий).

Примеры самодвойственных функций.

f(x)=(01) 
f(x,y)=(0101) 
f(x,y)=(1010) 
f(x,y)=(0011) 
f(x,y)=(1100) 
f(x,y,z)=(01010101) 
f(x,y,z)=(10101010) 
f(x,y,z)=(00001111) 
f(x,y,z)=(11110000) 
f(x,y,z)=(00110011) 
f(x,y,z) =(11001100)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 3. Совершенная дизъюнктивная нормальная форма, совершенная конъюнктивная нормальная форма, дизъюнктивная нормальная форма и конъюнктивная нормальная форма

 3.1 СДНФ и СКНФ.

 Определим степень следующим образом:

 , т.е.    

Выражение вида:  - называется полной совершенной элементарной конъюнкцией.

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

Выражение вида:  - называется полной совершенной элементарной дизъюнкцией.

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

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

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

ПРИМЕР

Составим  СДНФ и СКНФ для функции .

Формула:

 ,

таким образом, получили СКНФ для функции, состоящую из одной элементарной дизъюнкции.

Продолжим преобразования, получим:

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

 

На этом примере покажем связь  между таблицей истинности функции  и ее совершенными нормальными формами:

х1

х2

0

0

1

0

1

1

1

0

0

1

1

1





 

  

 

 

  

 

                                                Таблица 5.Таблица истинности  формулы

СДНФ:

СКНФ:

Инверсия  в логике (от лат. inversio — переворачивание, перестановка) 

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

 

х1

х2

элементарные конъюнкции

0

0

1

0

1

1

1

0

0

1

1

1


 

                                                        Таблица 6.Таблица нахождения СДНФ

Совершенная дизъюнктивная нормальная форма (СДНФ) – такая дизъюнкция конъюнкций, в которой:

  1. Различны все члены конъюнкции ("множители");
  2. Различны все члены каждой дизъюнкции ("слагаемые");
  3. В каждой дизъюнкции нет одновременно переменной и ее отрицания;
  4. Каждая дизъюнкция содержит все переменные, входящие в данную формулу или их отрицания.

 СДНФ:  

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

  1. Привести формулу к нормальному виду (т.е. избавиться от импликации, эквиваленции и отрицания неэлементарных формул).
  2. Из всех одинаковых членов дизъюнкции ("слагаемых") оставить только один.
  3. Если в каком-то члене дизъюнкции ("слагаемом") не хватает переменной Xi, то "домножаем" его с на, т.е. на 1 .
  4. Раскрыть скобки и из всех одинаковых членов дизъюнкции ("слагаемых") оставить только один.

Для построения СДНФ по таблице истинности необходимо:

  1. Выбрать из таблицы истинности те строки, в которых значение формулы - "Истина".
  2. Для каждой выбранной строки составить конъюнкцию переменных или их отрицаний так, чтобы эта конъюнкция была истинной (для этого переменные, которые в соответствующей строке имеют значение "Ложь" нужно взять с отрицанием, а переменные, имеющие значение "Истина" - без отрицания).
  3. Составить дизъюнкцию полученных конъюнкций.

X

Y

Z

F

СДНФ

СКНФ

0

0

0

1

 

0

0

1

1

 

0

1

0

0

  

0

1

1

0

  

1

0

0

0

  

1

0

1

1

 

1

1

0

0

  

1

1

1

0

  




 

 

                                                  

 

 

 

 

                Таблица 7. Таблица истинности для построения СДНФ и СКНФ

CДНФ:

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

Перечислим свойства совершенства для СДНФ:

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

2. Все логические слагаемые различны.

3. Ни одно слагаемое не содержит  одновременно переменную и ее  отрицание.

4. Ни одно слагаемое не содержит  одну и ту же переменную  дважды.

Алгоритм получения СДНФ по таблице истинности:

1. Отметить те строки таблицы  истинности, в последнем столбце  которых стоят 1:

2. Выписать для каждой отмеченной  строки конъюнкцию всех переменных следующим образом: если значение в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно  0, то ее отрицание: для 1-й строки    , для 3-й строки  , для 4-й строки 

3. Все полученные конъюнкции  связать в дизъюнкцию: 

4. Упрощаем формулу, применяем  законы логики.

 

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

Перечислим свойства совершенства для СКНФ:

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

2.Все логические множители различны.

3.Ни один множитель не содержит  одновременно переменную и ее  отрицание.

4.Ни один множитель не содержит  одну и ту же переменную  дважды.

 

Алгоритм получения СКНФ по таблице истинности

1. Отметить те строки таблицы  истинности, в последнем столбце  которых стоят 0:

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

3. Все полученные дизъюнкции  связать в конъюнкцию:  

4. Упрощаем формулу, применяем  законы логики (если это необходимо).

Покажем, что полученные по двум алгоритмам СДНФ и СКНФ эквивалентны. СДНФ       и  СКНФ   

Можем проверить, построив таблицу  истинности по найденной формуле.

 

X

Y

 

0

0

1

1

0

1

0

0

1

0

1

1

1

1

0

1


                                Таблица 8.Таблица эквивалентности СДНФ и СКНФ

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

 

х1

х2

элементарные дизъюнкции

0

0

1

0

1

1

1

0

0

1

1

1


 

                                                                     Таблица 9.Таблица нахождения СКНФ

Литерал в логике высказываний


В логике высказываний литералом называют переменную или ее логическое отрицание.

Соответственно, положительным литералом называют непосредственно переменную, а отрицательным литералом — логическое отрицание переменной.

 

3.2 ДНФ И КНФ

Дизъюнктивная нормальная форма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ. Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.

Построение совершенной дизъюнктивной и конъюнктивной нормальных форм