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

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

Предикатом Р(х₁…х_n), называется функция P:MⁿB, где М- призвольное множество, а В - двоичное множество .

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

М называется предметной областью предиката, а элементы этого множества (х₁…х_n)М, называются предметными переменными.

Если предикат зависит от n аргументов, то это будет n-местный предикат.

Если в предикат поставить конкретное значение аргументов, то предикат становится высказыванием.

Рассмотрим примеры предикатов:

Р⁰: 2²+3²5² - высказывание

Р¹:х²+3²5² - одноместный предикат

Р²:х²+y²5² - двухместный предикат

Иногда используют более простую запись: x>y - это двухместный предикат, предметной областью которого могут служить любые множества действительных чисел. Высказывание 6>6 - истинно, а 7>7 - ложно. Различные подстановки чисел вместо одной предметной переменной дают различные n - местные предикаты: x>5, x>0, 7>y и т. д.

«Прямая Р проходит через точки А и В» - трехместный предикат, у которого предметными областями двух переменных (А и В) являются множества точек, а предметной областью третей переменной Р является множество прямых.

6.1 Операции над предикатами

Над предикатами можно производить те же операции, что и над высказываниями: .

Примеры:

Р¹(х): х делится на 2

Q¹(х): х делится на 3

Р¹(х) Q¹(х):

Р¹(х) Q¹(х):

Р¹(х) Q¹(х): или на 2 и на 3 или ни на 2 и ни на 3

Р¹(х) Q¹(х): : не делиться на 2 или делиться на 3

Р¹(х): х не делится на 2.

6.2 Кванторы

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

Пусть Р(х) - предикат, определенный на М, т. е. . Тогда под высказыванием «для всех х из М Р(х) истинно» мы понимаем высказывание, которое является истинным, если Р(х) истинно для любого х. Высказывание записанное в кавычках обозначается , множество М не входит в обозначение, но должно быть ясно из контекста. Знак , называется квантором общности.

А под высказыванием «существует такой х их М, что Р(х) истинно» мы понимаем высказывание, которое является истинным, если найдется хотя бы один х такой, что Р(х) является истинным. Высказывание в кавычках обозначается . Знак , называется квантором существования.

Переход от Р(х) к или к называется связыванием переменной х (или квантификацией). Переменная, на которую навешан квантор, называется связанной, несвязанная переменная называется свободной.

Квантору общности соответствует связывание словами «для всех», квантору существования - словом «существует».

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

Пример кванторов:

Пусть Р(х) - предикат, х - четное число, тогда высказывание - истинно на любом множестве четных чисел и ложно на множестве, содержащем хотя бы одно нечетное число. Высказывание - истинно на любом множестве, содержащим хотя бы одно четное число и ложно на любом множестве нечетных чисел.

6.3 Формулы

Алфавит исчисления предикатов содержит следующие символы:

х₁,х₂,…х_n - предметные переменные;

P^t_1, P^t_2,…, P^t_n - предикаты, где t - количество мест;

- операции;

- кванторы;

( ) - скобки.

Последовательность перечисленных символов называется формулой.

При логической интерпретации формул логики предикатов возможны две основные ситуации:

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

Пример: .

Если формула f выполнима в М при любых подстановках констант, то она называется тождественно истинной в М. Формула f тождественно истинная в любых М называется тождественно истинной или общезначимой.

Пример: формула тождественно истинна для всех М, состоящих из одного элемента, а формула тождественно истинна.

Две (или более ) формулы называются эквивалентными, если при любых подстановках констант они принимают одинаковые значения. В частности все тождественно истинные (тождественно ложные) формулы эквивалентны. Отметим, что если F₁ и F₂ эквивалентны, то формула F1F₂, - тождественно истинна.

Пример (Задание №8):

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

Всякое натуральное число, делящееся на 12 делиться на 2, 4, 6.

Решение:

Введем на натуральном ряде предикаты:

А(х) - делиться на 12 (т. е. А(х)=1 тогда и только тогда, когда х делиться на 12),

В(х) - делиться на 2 (т. е. В(х)=1 тогда и только тогда, когда х делиться на 2),

С(х) - делиться на 4 (т. е. С(х)=1 тогда и только тогда, когда х делиться на 4),

D(х) - делиться на 6 (т. е. D(х)=1 тогда и только тогда, когда х делиться на 6).

.

7. ТЕОРИЯ ГРАФОВ

Теория графов разработана для решения задач о геометрических конфигурациях, состоящих из точек и линий. При этом не существенно соединены ли точки прямыми отрезками или криволинейными дугами, какова их длина и т. д. Важно лишь то, что каждая линия соединяет какие-либо точки. Исходя из этого граф определяется как совокупность двух множеств V (множество точек) и Е (множество линий).

Записывается граф следующим образом: G(V,E).

Элементы множества V называются вершинами графа G. Элементы множества Е - ребрами графа G. Вершины и ребра графа G называют его элементами и часто записывают и .

7.1 Понятие смежности

Пусть v₁, v₂ - вершины, е₁ - соединяющее их ребро. Тогда вершина v₁ и ребро е₁ - инцидентны, вершина v₂ и ребро е₁ также инцидентны. Два ребра инцидентные одной вершине (е₁,е₂ инцидентны v₂) называются смежными. А также две вершины инцидентные одному ребру (v₁, v₂ инцидентны е₁ называются смежными.

Пример: обычно граф изображают диаграммой: вершины - точками (или кружками), ребра - линиями. Изобразим граф, имеющий 4 вершины и 5 ребер.

Пример: Задание: выписать все смежные и несмежные вершины и ребра.

Решение:

Таб.7

Смежные вершины	Несмежные вершины	Смежные ребра	Несмежные ребра
v1и v2	v1 и v3	e1 и е2	e1 и е3
v2 и v3		e2 и е3	e4 и е2
v3 и v4		e3 и е4
v4 и v1		e4 и е1
v4 и v2		e4 и е5
		e3 и е5
		e1 и е5
		e2 и е5

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

Первая по порядку вершина инцидентная дуге ориентированного графа, называется его началом, вторая - его концом.

Вершины в ориентированном графе называются узлами.

Рассмотрим некоторые виды графов:

Если ребро соединяет вершину саму с собой, то такой элемент графа называется петлей, а содержащий его граф называется графом с петлей (или псевдографом):

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

Множество ребер Е может быть пустым:

Линии, изображающие ребра графа могут пересекаться, но точки пересечения не являются вершинами:

Граф может быть бесконечным:

Каждому неориентированному графу можно поставить в соответствие орграф с тем же множеством вершин заменив лишь ребра неориентированного графа на направленные дуги орграфа. Такое соответствие называется каноническим.

7.2 Матрица инцидентности и списки ребер

Задать граф - значит описать множества его вершин и ребер, а также отношение инцидентности. Когда граф конечен для описания его вершин и ребер достаточно их занумеровать. Отношение инцидентности определяют матрицей _ij, имеющей m строк и n столбцов. Столбцы соответствуют вершинам графа, строки - ребрам графа. Если ребро е_i инцидентно вершине v_j, то _ij = 1, в противном случае _ij = 0. Это матрица инцидентности для неориентированного графа.

Пример (Задание №9)

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

	I	II	III	IV	V	VI	VII
1	1	1	0	0	0	0	0
2	1	0	1	0	0	0	0
3	0	1	0	1	0	0	0
4	1	0	0	0	1	0	0
5	0	1	0	0	0	1	0
6	0	0	1	1	0	0	0
7	0	0	1	0	1	0	0
8	0	0	0	1	0	1	0
9	0	0	0	0	1	0	1
10	0	0	0	0	0	1	1

В матрице инцидентности орграфа _ij = -1, если вершина v_j - начало дуги a_i; _ij = 1, если v_j - конец дуги a_i; если a_i - петля, а v_j - инцидентная ей вершина, то _ij = а, где а - любое число отличное от 0, 1, -1. В остальных случаях _ij = 0.

Пример (Задание №10): построим ориентированный граф и матрицу инцидентности для нее:

1

67

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

Составим списки ребер для данных графов:

Таб. 8 Списки ребер неориентированного графа

Таб. 9 Списки ребер орграфа

Ребра	Вершины		Ребра	Вершины
1	I, II		1	I, II
2	I, III		2	I, III
3	II, IV		3	II, IV
4	I, V		4	III, V
5	II, VI		5	III, IV
6	III, IV		6	III, VII
7	III, V		7	VI, VII
8	IV, VI
9	V, VII
10	VI, VII

Каждая строка списка ребер соответствует строке матрицы с тем же номером ребра.

7.3 Матрица смежности графа

Матрица смежности - это квадратная матрица _ij, строкам и столбцам которой соответствуют вершины графа. Для неориентированного графа _ij ровно количеству ребер, инцидентных i-ой и j-ой вершинам. Для орграфа _ij ровно количеству ребер с началом в i-ой вершине и концом j-ой вершине. Таким образом матрица смежности неориентированного графа симметрична, а орграфа - необязательно.

Пример: построим матрицы смежности для графов, рассмотренных ранее.

	I	II	III	IV	V	VI	VII			I	II	III	IV	V	VI	VII
I	0	1	1	0	1	0	0		I	0	1	1	0	0	0	0
II	1	0	0	1	0	1	0		II	0	0	0	1	0	0	0
III	1	0	0	1	1	0	0		III	0	0	0	0	1	1	1
IV	0	1	1	0	0	1	0		IV	0	0	0	0	0	0	0
V	1	0	1	0	0	0	1		V	0	0	0	0	0	0	0
VI	0	1	0	1	0	0	1		VI	0	0	0	0	0	0	0
VII	0	0	0	0	1	1	0		VII	0	0	0	0	0	0	1

Матрица смежности неориентированного графа

Матрица смежности орграфа.

7.4 Операции над членами графов

Дополнение Н части Н определяется множеством всех ребер графа G, не принадлежащих Н.

Объединение Н₁ Н₂ определяется:

;

.

Пересечение Н₁ Н₂ частей Н₁ и Н₂ графа G определяется:

;

.

8 ОСНОВНЫЕ ТРЕБОВАНИЯ К ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ

Контрольная работа в обязательном порядке должна содержать титульный лист (см. приложение I), условие задачи и подробное описание ее решения. Описание решения должно содержать: используемые при решении формулы и свойства; их название (если таковое имеется); методы или способы решения задачи; результаты вычислений; выводы.

9. ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ

Множества и подмножества. Основные понятия. Графическое представление множеств и операций над ними.

Множества и подмножества. Основные понятия. Свойства операций над множествами. Тождества. Порядок доказательства тождеств.

Отношение на множествах. Декартово произведение.

Отношения на множествах. Одноместные, бинарные, n- местные отношения.

Отношения на множествах. Свойства отношений.

Функция как отношение на множествах. Отношение порядка. Отношение эквивалентности.

Математическое моделирование. Понятие модели. Этапы приведения к модели. Способы моделирования.

Алгебраические модели. Общие понятия. Алгебраические модели с одной определяющей операцией.

Алгебраические модели. Общие понятия. Алгебраические модели с двумя определяющими операциями.

Алгебраические модели. Общие понятия. Алгебраические модели, содержащие более одного класса математических объектов.

Теория кодирования. Общие понятия. Показать построение трехзначного двоичного кода на примере куба. Описать все возможные ситуации.

Теория кодирования. Общие понятия. Кодовые расстояния. Методы обнаружения ошибок.

Теория кодирования. Общие понятия. Групповые коды.

Линейная алгебра. Общие понятия. Линейные подпространства.

Реляционная алгебра. Понятия домена, кортежа. Операции выбора, проекции, объединения.

Математическая логика. Общие понятия алгебры логики. Функции алгебры логики и их таблицы истинности.

Булева алгебра. Общие понятия. Свойства операций и элементов булевой алгебры.

Булева алгебра. Дизъюнктивные нормальные формы. Совершенные дизъюнктивные нормальные формы.

Булева алгебра. Алгоритм преобразования формулы в совершенную дизъюнктивную нормальную форму.

Булева алгебра. Конъюнктивные нормальные формы. Совершенные конъюнктивные нормальные формы.

Исчисление высказываний. Общие понятия. Понятие равносильной формулы.

Исчисление высказываний. Равносильности. Способы доказательства равносильностей.

Исчисление высказываний. Правила равносильных преобразований. Тавтологии. Основные понятия.

Исчисление высказываний. Тавтологии. Методы доказательства тождественной истинности. высказываний.

25. Аксиоматическая система в исчислении. Основные понятия. Выводимые формулы. Правила вывода.

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

Булевы функции. Замкнутые классы. Контактные схемы.

Логика предикатов. Основные понятия. Операции над предикатами.

Логика предикатов. Основные понятия. Кванторы. Исчисление предикатов.

Формальные грамматики. Классификация грамматик. Порождающие грамматики.

Языки. Свойства языков. Операции над языками. Анализ грамматик и языков.

Теория алгоритмов. Понятие алгоритмической разрешимости. Рекурсивные функции.

Теория конечных автоматов. Машины Тьюринга. Формы представления алгоритмов.

Теория графов. Основные понятия.

Элементы комбинаторики. Основные понятия.

ЛИТЕРАТУРА

Кузнкцов О.П., Адельсон - Вельский Г.М. Дискретная математика для инженера - 2-е иэдание переработанное и доплненное М.: Энергоатомиздат 1988г.- 480с.

Горбатов В.А. Основы дискретной математики: учебное пособие для студентов вузов - М.: Высшая школа, 1986Г-311с.

Никольская И Л. Математическая логика: Учебник М.: Высшая школа 1981г.-127с.

Ершов Ю.А., Палютин Е.А. Математическая логика: учебное пособие для вузов 2-е издание исправленное и дополненное- М.: Наука 1987г.- 336с.

Клини С.К. Математическая логика М.: Мир 1973г.

Новиков П.С. Элементы математической логики. М.: Наука 1973г.

Оре О. Теория графов М.: Наука 1968г.

Зыков А.А. Теория конечных графов. Новосибирск: Наука 10969г.

Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике М.: Наука 1977г.- 368с.

Гиндикин С.П. Алгебра логики в задачах М.: Наука 1972г.

Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике, теории автоматов М.: Наука 1975г.

ПРИЛОЖЕНИЕ I

Оформление титульного листа

Волжский университет им. В.Н. Татищева Кафедра «Информатика и системы управления» Контрольная работа по дисциплине «Дискретная математика» специальность 071900 «Информационные системы» Выполнил: студент группы ИТЗ-301 Сидоров И. И. Проверил: Воронцова Е. В. Дата сдачи 00.00.00 Дата проверки 00.00.00 Вариант5. Тольятти 2001