Q1(х): х делится на 3
Р1(х)
Р1(х)
Р1(х)
Р1(х)
В программировании квантор определяется как логический оператор, с помощью которого по предикату строится высказывание относительно области истинности предиката.
Пусть Р(х) – предикат, определенный на М, т. е.
А под высказыванием «существует такой х их М, что Р(х) истинно» мы понимаем высказывание, которое является истинным, если найдется хотя бы один х такой, что Р(х) является истинным. Высказывание в кавычках обозначается
Переход от Р(х) к
Квантору общности соответствует связывание словами «для всех», квантору существования – словом «существует».
Навешивать кванторы можно и на многоместные предикаты. Выражение, на которое навешивается квантор общности или квантор сущности, называется областью действия квантора. Навешивание квантора на многоместный предикат уменьшает в нем число свободных переменных и превращает его в предикат от меньшего числа переменных. Это обуславливается определением смысла связанных и свободных переменных. Свободная переменная – это обычная переменная, которая может принимать различные значения из М, а выражение Р(х) – переменное высказывание, зависящее от значения х. Выражение
Пример кванторов:
Пусть Р(х) – предикат, х – четное число, тогда высказывание
Алфавит исчисления предикатов содержит следующие символы:
· х1,х2,…хn – предметные переменные;
· Pt1, Pt2,…, Ptn – предикаты, где t – количество мест;
·
·
· ( ) – скобки.
Последовательность перечисленных символов называется формулой.
При логической интерпретации формул логики предикатов возможны две основные ситуации:
1. Если в области М для формулы F существует такая подстановка констант вместо всех переменных, что F становится истинным высказыванием, то формула f называется выполнимой в области М. Если существует область М, где f выполнима, то f называется просто выполнимой.
Пример:
2. Если формула f выполнима в М при любых подстановках констант, то она называется тождественно истинной в М. Формула f тождественно истинная в любых М называется тождественно истинной или общезначимой.
Пример: формула
Две (или более ) формулы называются эквивалентными, если при любых подстановках констант они принимают одинаковые значения. В частности все тождественно истинные (тождественно ложные) формулы эквивалентны. Отметим, что если F1 и F2 эквивалентны, то формула F1 F2, - тождественно истинна.
Пример (Задание №8):
Ввести а) одноместный предикат, б) многоместный предикат на соответствующих областях и записать при их помощи приведенное ниже высказывание в виде формулы логики предикатов.
Всякое натуральное число, делящееся на 12 делиться на 2, 4, 6.
Решение:
Введем на натуральном ряде предикаты:
А(х) – делиться на 12 (т. е. А(х)=1 тогда и только тогда, когда х делиться на 12),
В(х) – делиться на 2 (т. е. В(х)=1 тогда и только тогда, когда х делиться на 2),
С(х) – делиться на 4 (т. е. С(х)=1 тогда и только тогда, когда х делиться на 4),
D(х) – делиться на 6 (т. е. D(х)=1 тогда и только тогда, когда х делиться на 6).
Теория графов разработана для решения задач о геометрических конфигурациях, состоящих из точек и линий. При этом не существенно соединены ли точки прямыми отрезками или криволинейными дугами, какова их длина и т. д. Важно лишь то, что каждая линия соединяет какие-либо точки. Исходя из этого граф определяется как совокупность двух множеств V (множество точек) и Е (множество линий).
Записывается граф следующим образом: G(V,E).
Элементы множества V называются вершинами графа G. Элементы множества Е – ребрами графа G. Вершины и ребра графа G называют его элементами и часто записывают
Пусть v1, v2 – вершины, е1 – соединяющее их ребро. Тогда вершина v1 и ребро е1 – инцидентны, вершина v2 и ребро е1 также инцидентны. Два ребра инцидентные одной вершине (е1,е2 инцидентны v2) называются смежными. А также две вершины инцидентные одному ребру (v1, v2 инцидентны е1 называются смежными.
Пример: обычно граф изображают диаграммой: вершины – точками (или кружками), ребра – линиями. Изобразим граф, имеющий 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 |
До настоящего момента мы рассматривали неориентированный граф. Если каждому ребру графа присвоить направление (в виде стрелочки) от одной вершины к другой, то такие ребра называются дугами, а содержащий их граф называется ориентированным (или орграфом).
Первая по порядку вершина инцидентная дуге ориентированного графа, называется его началом, вторая – его концом.
Вершины в ориентированном графе называются узлами.
Рассмотрим некоторые виды графов:
· Если ребро соединяет вершину саму с собой, то такой элемент графа называется петлей, а содержащий его граф называется графом с петлей (или псевдографом):
· Если различные ребра могут быть инцидентными одной паре вершин, то они называются кратными, а содержащий их граф называется мультиграфом:
· Множество ребер Е может быть пустым: