Основные положения дискретной математики

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

2. «Прямая Р проходит через точки А и В» – трехместный п

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

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

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

Примеры:

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

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

Р1(х) Q1(х):

Р1(х) Q1(х):

Р1(х) Q1(х): или на 2 и на 3 или ни на 2 и ни на 3

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

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

6.2 Кванторы

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

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

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

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

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

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

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

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

6.3 Формулы

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

· х1,х2,…хn – предметные переменные;

· Pt1, Pt2,…, Ptn – предикаты, где t – количество мест;

· - операции;

· - кванторы;

· ( ) – скобки.

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

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

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

Пример: .

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

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

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

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

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

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

Решение:

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

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

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

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

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

.

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

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

 Скачать реферат