И теория алгоритмов

МАТЕМАТИЧЕСКАЯ ЛОГИКА

И ТЕОРИЯ АЛГОРИТМОВ

Учебное пособие

Воронеж 2007

ГОУВПО «Воронежский государственный

технический университет»

Н.А. Ююкин С.И. Моисеев Г.Ф. Федотенко

МАТЕМАТИЧЕСКАЯ ЛОГИКА

И ТЕОРИЯ АЛГОРИТМОВ

Утверждено Редакционно-издательским советом

университета в качестве учебного пособия

Воронеж 2007

УДК 510(075)

Ююкмн Н.А. Математическая логика и теория алгоритмов: учеб. пособие/ Н.А. Ююкин, С.И. Моисеев, Г.Ф. Федотенко. Воронеж: ГОУВПО «Воронежский государственный технический университет», 2007. 90 с.

В учебном пособии рассматриваются краткие теоретические сведения по теории множеств, бинарным отношениям, алгебраическим системам, булевым функциям, k – значной логике, формальным системам, формализации понятия алгоритма и оценки его сложности.

Учебное пособие соответствует требованиям государственного образовательного стандарта высшего профессионального образования по направлению 090100 «Информационная безопасность», специальностям 090102 «Компьютерная безопасность», специальности 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем», дисциплине «Математическая логика и теория алгоритмов»

Библиогр.: 8 назв.

Научный редактор д-р физ.-мат. наук, проф. И.Л. Батаронов

Рецензенты: кафедра высшей математике Воронежского ин-

ститута МВД России (зав. кафедрой д-р физ.-

мат. наук, проф. В.В. Меньших);

д-р физ.-мат. наук, проф. В.Н. Нечаев

© Ююкин Н.А., Моисеев С.И., Федотенко Г.Ф., 2007

© Оформление. ГОУВПО «Воронежский

государственный технический университет», 200 7

ВВЕДЕНИЕ

Данное пособие предназначено для студентов ВГТУ, обучающихся по специальностям:

090102 – Компьютерная безопасность;

090105 – Комплексное обеспечение информационной безопасности автоматизированных систем.

Дисциплина “Математическая логика и теория алгоритмов” обеспечивает приобретение знаний и умений в соответствии с Государственным общеобразовательным стандартом и при этом содействует фундаментализации образования, формированию мировоззрения и развитию логического мышления.

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

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

Достижению данной цели служат следующие задачи:

изучить максимально широкий круг понятий математической логики и теории алгоритмов;

получить навыки решения учебных и практических задач;

овладеть методами алгоритмизации;

ознакомиться с основами формальных математических систем (теорий) и автоматическим доказательством теорем;

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

Дисциплина “Математическая логика и теория алгоритмов” относится к числу прикладных математических дисциплин. Она основывается на знаниях, приобретенных студентами при изучении дисциплины “Алгебра”. Знания и навыки, полученные при изучении дисциплины “Математическая логика и теория алгоритмов”, используются при изучении общепрофессиональных и специальных дисциплин.

1. КРАТКИЕ СВЕДЕНИЯ О МНОЖЕСТВАХ,

ОТНОШЕНИЯХ И АЛГЕБРАИЧЕСКИХ СИСТЕМАХ

1.1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ

1.1.1. Основные понятия

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

Множеством называется любая совокупность определенных и различимых между собой объектов нашей интуиции и интеллекта, мыслимая, как единое целое. Эти объекты называются элементами множества. Множества обозначаются большими буквами латинского алфавита, а их элементы – малыми. Запись xÎX означает, что элемент x принадлежит множеству X, в противном случае пишут xÏX.

В этом “определении” совокупность предметов рассматривается, как один общий объект и при этом предметы как бы собираются в один мешок, а дальше работают с этим мешком, как с единым целым, не задумываясь о его содержании. Такой подход известен в биологии, где растения и животные, классифицируются по видам, классам, отрядам и т. д. При этом внимание переносится с отдельных представителей на общие свойства группы, как совокупности. В языке это отражается в словах “компания”, “стая”, “стадо” и т.д.

В “определении” множества нет никаких ограничений на природу элементов. Это может быть множество студентов второго курса, множество пятен на солнце, множество зелёных яблок, множество звёзд на небе и так далее. Заметим, что в качестве элементов множеств могут быть также множества. Например: с одной стороны, группа студентов – это множество, состоящее из людей, а с другой стороны, эта группа является элементом множества всех групп в институте.

В математике часто используют числовые множества, элементами которого являются числа. Из школьной алгебры известны числовые множества N – натуральных, Z – целых, Q – рациональных, I – иррациональных, R – действительных чисел.

Геометрически множество действительных чисел изображается точками числовой оси, то есть прямой на которой выбрано: 1) начало отсчёта, 2) положительное направление и 3) единица масштаба.

Между множеством действительных чисел и точками числовой оси существует взаимно однозначное соответствие.

Множества точек X числовой оси называются:

a ≤ x ≤ b – отрезком,

a < x < b – интервалом,

a < x ≤ b, a ≤ x < b – полуинтервалом,

Все указанные множества называются промежутками.

Всякий интервал, содержащий точку a, называется окрестностью точки a.

Если множество содержит конечное число элементов, то оно называется конечным, а в противном случае – бесконечным.

Конечное множество обычно задаётся перечислением его элементов с заключением их в фигурные скобки, то есть

X= {x₁,x₂,,…,x_n}.

Однако перечисление элементов громоздко для описания больших множеств и не применимо для бесконечных множеств. Такие множества задаются с помощью характеристических свойств. Пусть P(x) некоторое предложение, зависящее от x, которое может быть истинным или ложным в зависимости от x, тогда запись X={x|P(x)}, означает, что xÎX тогда и только тогда, когда P(x) истинное утверждение.

Например: A= {1,2}={xÎN | x<3}.

Подмножеством A множества B (AÍB) или (A содержится в B) называется множество A, каждый элемент которого принадлежит B. Графически это изображается с помощью кругов Эйлера, как показано на рисунке.

Множества A и B называются равными (A=B), если AÍB и BÍA.

Множество, не содержащее ни одного элемента, называется пустым и обозначается Ø. Совокупность всех допустимых объектов в рамках решаемой задачи называется универсальным множеством и обозначается U.

Совокупность всех подмножеств множества А называется множеством-степенью и обозначается P(А), то есть P(А) ={ В ç В Í А }.

1.1.2. Операции над множествами

Объединение AÈB есть множество всех элементов принадлежащих A или B. Следует иметь ввиду, что существуют два значения союза или:

1) «исключающее или» - либо то, либо другое и третьего не дано;

2) «не исключающее или» - то или другое, или то и другое вместе.

В определении объединения множеств подразумевается второе “не исключающее или”, то есть элемент может принадлежать только A, только B, а также одновременно этим

множествам

Пересечение множеств С=A ÇB, есть множество элементов принадлежащих A и B.

Разность A\B, есть множество, состоящее из элементов A, не входящих в множество В.

Симметричная разность

Прямым (декартовым) произведением двух множеств АхВ называется множество всех упорядоченных пар (а,b), в которых первый элемент аÎА, а второй bÎВ.

Степенью множества А называется его прямое произведение самого на себя, то есть .

Дополнением множества A называется множество Ā, состоящее из элементов универсального множества, не являющихся элементами множеством A.