Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Соликамский государственный педагогический институт (филиал)
федеральное государственное образовательное учреждение высшего профессионального образования «Пермский государственный национальный исследовательский университет»
Кафедра математики и физики
Отчет
по дисциплине
Дискретная математика
Тема реферата: Фундаментальные понятия дискретной математики как основа формальных методов применяемых в информатике и икт
Выполнила:
Студент 2 курса
321 группы
Канзапарова А.А.
Соликамск, 2013
Содержание
Введение
Дискретная математика — область математики, изучающий свойства дискретных структур. К таким структурам могут быть отнесены конечные группы, конечные графы, а также некоторые математические модели преобразователей информации, конечные автоматы, машины Тьюринга и так далее. Это примеры структур конечного характера. Раздел дискретной математики, изучающий их, называется конечной математикой. Иногда само это понятие расширяют до дискретной математики. Кроме указанных конечных структур, дискретная математика изучает некоторые системы алгебры, бесконечные графы, вычислительные схемы определенного вида, клеточные автоматы и т. д. Как синоним иногда употребляется термин "дискретный анализ".
1.1. Понятие формальной системы
Формальная система (ФС) считается заданной, если определены
следующие ее компоненты:
1. Алфавит;
2. Совокупность правильно построенных формул;
3. Множество аксиом;
4. Множество правил вывода.
Алфавит ФС включает конечное или бесконечное число символов. Эти символы делятся на три группы — буквы, символы операций и связок, вспомогательные символы (скобки различных видов, запятые и т.д.). Количество символов связок, символов операций и вспомогательных символов конечно, число букв может быть бесконечно за счет индексов, принимающих натуральные значения. Любую конечную последовательность символов алфавита именуем формулой ФС.
В совокупности формул ФС выделено множество правильно построенных формул (ППФ). Для ППФ задаются правила их конструирования и эффективная процедура, позволяющая по каждой формуле ФС определить, является ли она ППФ.
Множество аксиом — это выделенное подмножество ППФ. Если множество аксиом бесконечно, то предполагается наличие процедуры проверки по ППФ, является ли она аксиомой.
Правила вывода позволяют из имеющегося множества ППФ (утверждений) получать новые ППФ — непосредственные следствия этих утверждений.
Последовательность ППФ А1, А2, ..., Аn называется выводом в ФС, если для любого i=1,…,n ППA Аi является либо аксиомой AС, либо непосредственным следствием некоторых ППФ множества (A1, A2, …,Ai - 1), получаемым применением к этим ППФ некоторого правила вывода;
ППФ A называется теоремой ФС, если в данной ФС имеется вывод, в котором последней ППФ является A.
1.2. Разрешимая и неразрешимая формальная система
Формальная система называется разрешимой, если существует алгоритм определения по произвольной ППФ, является ли она теоремой.
Если такого алгоритме не существует, то рассматриваемая ФС именуется неразрешимой.
Правильно построенная формула B выводима из совокупности ППФ (А 1, А2, ..., Аn), если существует последовательность ППФ В1, В2, ..., Вk такая, что Вk=В и для любого i=1,..,k формула Вi является либо аксиомой ФС, либо формулой множества (А1, А2, ..., Аn), либо непосредственным следствием некоторых ППФ множества (В1, В2, ..., Вk), получаемых применением к этим ППФ одного из правил посылками или гипотезами.
Формулы, выводимые из пустого множества посылок, являются теоремами. Запись А1, А2, ..., Аn |— В означает выводимость формулы В из множества посылок (А1, А2, ..., Аn ) |— В означает, что В является теоремой ФС.
Если М={А1, А2, ..., Аn}, то запись А1, А2, ..., Аn |— В можно представить записью М |— В.
Очевидны следующие утверждения:
— если M1 ⊆ M и M1 |− B, то M |− B;
— M| −B тогда и только тогда, когда в М имеется конечное подмножество M1 такое, что M1 |−B;
—если M1 |− A и M2 |− B для любой формулы В из множества M1, M2 |− A.
Приведем простейший пример формальной системы.
Считаем:
алфавит состоящим из символов |, =, +.
Правила конструкции ППФ следующие:
1) | есть ППФ;
2) если а – ППФ, то а| также ППФ;
3) если а и b – ППФ, то а + b и а = b также ППФ;
4) других ППФ нет.
Система аксиом включает единственную аксиому: | = |.
Единственное правило вывода следующее: из ППФ a = b выводится, а + | = b |.
Очевидно, что теоремой в введенной ФС будет любая формула вида:
|+|+|+…+|=|…|,
где слева и справа от знака = стоит одинаковое число символов |; других теорем в ФС нет.
1.3 Исчисление высказываний как формальная система
Исчисление высказываний (ИВ) представляем в виде формальной системы. Алфавит ИВ образуют буквы латинского алфавита с числовыми индексами или без них (эти буквы называются высказывательными переменными или атомами), символы логических связок ¬ (отрицание), & (конъюнкция), ∨ (дизъюнкция), → (импликация), а также левая и правая скобки.
1.3.1. Правила образования ППФ
1) все атомы являются ППФ;
2) если А и В – ППФ, то ¬ (A), (А&В), (А ∨ В), (А → В)– также ППФ.
3) других ППФ не существует.
Скобки, расположение которых в ППФ определяется однозначно, мы иногда будем опускать.
Система аксиом ИВ (введена П. С. Новиковым):
1) A → (B → A),
2) (A → B) → (A → (B → C) → (A → C)),
3) (A & B) → A,
4) (A & B) → B,
5) A → (B → (A & B)),
6) A → (A ∨ B),
7) B → (A ∨ B),
8) (A → C) → ((B → C) → ((A ∨ B) → C)),
9)(A → B) → ((A → ¬B) → A),
10) ¬¬A → A,
11) A → ¬¬A.
1.4. Свойства дедуктивных теорий
Непротиворечивость
Теория, в которой множество теорем покрывает всё множество формул (все формулы являются теоремами, «истинными высказываниями»), называется противоречивой. В противном случае теория называется непротиворечивой. Выяснение противоречивости теории — одна из важнейших и иногда сложнейших задач формальной логики. После выяснения противоречивости теория, как правило, не имеет дальнейшего ни теоретического, ни практического применения.
Полнота
Теория называется полной, если в ней для любой формулы выводима либо сама, либо ее отрицание. В противном случае, теория содержит недоказуемые утверждения (утверждения, которые нельзя ни доказать, ни опровергнуть средствами самой теории), и называется неполной.
Независимость аксиом
Отдельная аксиома теории считается независимой, если эту аксиому нельзя вывести из остальных аксиом. Зависимая аксиома, по сути, избыточна, и ее удаление из системы аксиом никак не отразится на теории. Вся система аксиом теории называется независимой, если каждая аксиома в ней независима.
Разрешимость
Теория называется разрешимой, если в ней понятие теоремы эффективно, то есть существует эффективный процесс (алгоритм), позволяющий для любой формулы за конечное число шагов определить, является она теоремой или нет.
В ИВ имеются два правила вывода - подстановка и modus ропепs (дедуктивного вывода). Правило подстановки применяется к имеющейся ППФ А, содержащей некоторый атом X. Одновременной заменой всех вхождений этого атома в А(X) на произвольную ППФ В мы получим формулу A(В), которую именуем результатом подстановки в ППФ А(X) формулы В. Если А(X) — теорема ИВ, то A(В) — тоже теорема ИВ.
1.4.1. Приведем пример
Подставив в аксиому 8 ИВ формулу (С&D) вместо атома С, получаем следующую теорему ИВ:
(A → (С & D)) → ((B → (С & D)) → ((A ∨ B) → (С & D))).
Правило дедуктивного вывода (modus ponens) применяется к имеющейся паре ППФ А и А → В; результатом применения данного правила является ППФ В. Если A и А → В являются теоремами ИВ, то В — также теорема ИВ. Будем трактовать символы ¬, &, ∨, → как функции алгебры логики. Тогда каждая ППФ, сконструированная из атомов X1, X2, …, Xn, на любых наборах их логических значений (0 или 1, ложь или истина) обращается в ложь или истину. Правильно построенная формула, которая является истинной на всех наборах логических значений ее переменных, именуется общезначимой. Правильно построенную формулу А именуем невыполнимой (противоречивой), если ППФ ¬ А является общезначимой. Можно проверить, что все аксиомы ИВ являются общезначимыми ИПФ. Оба правила вывода сохраняют обще значимость.
Получаем справедливость следующего утверждения:
"Каждая теорема ИВ является общезначимой ППФ".
Полноту приведенной системы аксиом утверждает следующий факт:
"Каждая общезначимая ППФ является теоремой ИВ".
Система аксиом П.С.Новикова обладает также свойствами непротиворечивости и независимости. Далее под термином "формула" понимаем ППФ. Две формулы ИВ называются эквивалентными, если на любом наборе логических значений составляющих их атомов они одновременно обращаются в истину или одновременно обращаются в ложь. Эквивалентность обозначаем символом =. Легко убедиться, что
(А→В)=(¬А∨В);
данный факт далее будет играть, принципиальное значение. Литерами будем называть атомы и их отрицания. Таким образом, формула (¬А∨В) составлена из двух литер, ¬ А и B. Формула В есть конъюнктивная нормальная форма (КНФ), если В имеет вид
В1&В2&...&Вm,
где каждая из формул Bi, i=1,…,m, есть дизъюнкция литер. В качестве примера КНФ приведем формулу:
(¬X1∨X3∨¬X4)&(X1∨X2)&(X2∨¬X3∨X5).
Аналогично, формула В есть дизъюнктивная нормальная форма (ДНФ), если В имеет вид
В1∨В2∨...∨Вm,
где каждая из формул Bi, i=1,…,m, есть конъюнкция литер. В качестве примера ДНФ приведем формулу:
(¬X1&X3&¬X4)∨(X1&X2)∨(X2&¬X3&X5).
В дальнейшем дизъюнкцию литер будем называть дизъюнктом, а конъюнкцию — конъюнктом.
Любая формула ИВ может быть преобразована в эквивалентную ей ДНФ или КНФ с помощью следующего алгоритма.
Шаг 1. А→В = ¬ А∨В,
А~В = (А∨¬В)& (¬А∨В)
выражение операций импликации и эквиваленции через операции конъюнкции и дизъюнкции.
Шаг 2. ¬ А=A,
¬ (А ∨ В) = ¬ А& ¬ В,
¬ (А&В) = ¬ А ∨ ¬ В
продвижение отрицания до атома.
Шаг 3. А ∨ (В&C) = (А ∨ В)& (А ∨ C) (для КНФ),
А& (В ∨ C) = (А&В) ∨ (А&C) (для ДНФ).
Пример 1. Требуется преобразовать в КНФ формулу
Ф=[(А → В)& ¬ (C&(D → А))].
Решение. Ф=[(А → В)& ¬ (C&(D → А))]=(А ∨ В)& (C ∨ ¬ (D ∨ А))=
=(А ∨ В)& (C ∨ D)& (C ∨ А)
Заключение
Классификация ИС по признаку структурированности решаемых задач
Список литературы
1. А.И. Белоусов, С.Б. Ткачев Дискретная математика. М.,МГТУ им. Н.Э. Баумана, 2004. — 742 с.— Математика в техническом университете
2. Акимов О.Е.Дискретная математика. Логика, группы, графы. — 2—е изд.— М, Лаборатория базовых знаний, 2001. — 376 с. — "Технический университет "
модельные
кспертные
Создающие управленческие отчеты
Разрабатывающие альтернативы решений
Для частично структурированных или неструктурированных задач
Для структурированных задач (автоматизация решения)
Информационные системы