57. Понятие квантора. Квантор существования. Квантор всеобщности.
Пусть Р(х) – предикат, определенный на множестве М. Высказывание для всех х из М Р(х) – истинна обозначается так: х Р(х)
Значок называется квантором всеобщности.
Высказывание "Существует х из М такой, что Р(х) – истина", записывается: х Р(х)
Значок называется квантором существования.
Переменная, на которую наложен квантер называется связанной переменной, а процесс употребления кванторы называется навешиванием квантора.
Свободная переменная – обычная переменная, которая принимает различные значения из множества М.
Выражение Р(х) – переменная высказывания, зависящая от значения х.
Выражение х Р(х) не зависит от переменной х и при фиксированном Р или М имеет строго определенное значение.
Связанные переменные могут встречаться не только в логике, но и в математике:
Навешивать кванторы можно на многоместные предикаты и на выражения.
Если Р(х) – четное число, тогда высказывание х Р(х) истинно на множестве М, содержащее четные числа и ложно, если М содержит хотя бы одно нечетное число.
х Р(х) – истинно на любом множестве М, содержащем хотя бы одно четное число, и ложно на множестве нечетных чисел.
Пример4:
Теорема Ферма:
x,y,z,n P(x,y,z): xn+yn=zn
58. Исчисление предикатов.
Исчисление предикатов производится в соответствии со следующими правилами:
1. аксиомой исчисления высказываний
2. предикатными аксиомами
3. х F(х)F(y)
F(x)y F(y)
Правило логического вывода
1. Правило modus poneus
2. Правило обобщения
3. Правило существования
59. Аксиомы исчисления предикатов. Правила логического вывода.
Пусть ,
,
— произвольные формулы, а х
и у
— предметные переменные. Тогда формулы
следующих видов принимаются в качестве
аксиом классического исчисления
предикатов:
1. ((
)),
2. (((
))((
)())),
3. ((&
)),
4. ((&
)
),
4. ((&
)
),
5. ((
(&
))),
6. (()((
)((
)))),
7. ((
)),
8. (
(
)),
9. ()(
)),
10. ((
)((
)))
,
11. (
),
12. (x(x/y)),
13. ((x/y)
x).
В исчислении
предикатов употребляются след. три
правила вывода. 1) Правило вывода
заключений: из формул
и (
)
выводится формула
.
Два кванторных правила вывода: 2) из
формулы (
),
где
не
содержит свободно х,
можно вывести (x
);
3) из формулы (
),
где
не
содержит свободно х,
можно вывести (x
).
60. Графы. Типы задач теории графов.
Графом G(V,E) называется совокупность двух множеств непустого множества вершин V и множества E неупорядоченных пар различных элементов множества V.
E – множество ребер.
V – множество вершин.
Число вершин – р
Число ребер – q
Среди дисциплин и методов дискретной математики теория графов, а особенно алгоритмы наиболее часто используются в программировании.
Язык графов позволяет компактно представлять условие задачи и облегчает понимание на интуитивном уровне.
Задачи, на которых основывается теория графов
1. Задача о Кенигсбергских мостах
4 участка суши соединяются 7 мостами.
Необходимо обойти все 4 участка суши пройдя по каждому мосту 1 раз и вернуться в исходную точку.
Решение невозможно, так как кол-во мостов, соединяющих сушу должно быть четным числом.
2. Задача о 3 домах и 3 колодцах
Построить тропинки от каждого дома к каждому колодцу, чтобы они не пересекались.
3. Задача о 4 красках
Любую карту на плоскости раскрасить 4 красками так, чтобы никакие 2 соседние области не были раскрашены одним цветом.