Основные положения дискретной математики (стр. 9 из 11)

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 – количество мест;

- операции;

- кванторы;

· ( ) – скобки.

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

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

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

Пример:

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

Пример: формула

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

тождественно истинна.

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

F₂, - тождественно истинна.

Пример (Задание №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

Смежные вершины	Несмежные вершины	Смежные ребра	Несмежные ребра
v₁и v₂	v₁и v₃	e₁и е₂	e₁и е₃
v₂и v₃	e₂и е₃	e₄и е₂
v₃и v₄	e₃и е₄
v₄и v₁	e₄и е₁
v₄и v₂	e₄и е₅
e₃и е₅
e₁и е₅
e₂и е₅

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

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

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

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

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

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

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