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

           

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

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

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

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

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

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

 

 

 

 

 

 

 

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

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

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

 

 

 

 

 

 

 

 

 

Выполнила студентка  группы ИВТ(б)-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(x₁, x₂, …, x_n)- называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 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 аргументов является суперпозицией  элементарных функций, заданных табл.

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

 

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

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

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