Логические операции над предикатами.

Предикаты так же, как высказывания, могут принимать два значения: “истина” (1) и “ложь” (0), поэтому к ним применимы все операции логики высказываний, в результате чего из элементарных предикатов формируются сложные предикаты (как и в логике высказываний, где из элементарных высказываний формировались сложные, составные). Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов сохраняют тот же смысл, который был им присвоен в логике высказываний.

Пусть на некотором множестве M определены два предиката P(x) и Q(x).

Определение 1.

Конъюнкцией двух предикатов P(x) и Q(x) называется новый (сложный) предикат , который принимает значение “истина” при тех и только тех значениях , при которых каждый из предикатов принимает значение “истина”, и принимает значение “ложь” во всех остальных случаях.

Очевидно, что областью истинности предиката является общая часть области истинности предикатов P(x) и Q(x), т.е. пересечение .

Так, например, для предикатов P(x): “x – четное число” и Q(x): “x кратно 3” конъюнкцией является предикат “x – четное число и x кратно трем”, т.е. предикат “x делится на 6”.

Определение 2.

Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат , который принимает значение “ложь” при тех и только тех значениях , при которых каждый из предикатов принимает значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Ясно, что областью истинности предиката является объединение области истинности предикатов P(x) и Q(x), т.е. .

Определение 3.

Отрицанием предиката P(x) называется новый предикат или , который принимает значение “истина” при всех значениях , при которых предикат P(x) принимает значение “ложь”, и принимает значение “ложь” при тех значениях , при которых предикат P(x) принимает значение “истина”.

Очевидно, что , т.е. множество истинности предиката является дополнением к множеству I_P.

Определение 4.

Импликацией предикатов P(x) и Q(x) называется новый предикат , который является ложным при тех и только тех значениях , при которых одновременно P(x) принимает значение “истина”, а Q(x) – значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Поскольку при каждом фиксированном справедлива равносильность , то .

Определение 5.

Эквиваленцией предикатов P(x) и Q(x) называется новый предикат , который обращается в “истину” при всех тех и только тех , при которых P(x) и Q(x) обращаются оба в истинные или оба в ложные высказывания.

Для его множества истинности имеем:

16.

Свободные и связанные переменные. Кванторы всеобщности и существования, их взаимосвязь.

Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих выcказывание. Чаще всего упоминают:
Квантор всеобщности (обозначение: , читается: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»).
Квантор существования (обозначение: , читается: «существует…» или «найдётся…»).
В математической логике приписывание квантора к формуле называется связыванием или квантификацией.
В многозначных логиках также вводятся и другие кванторы, например, квантор плюральности (квантор Решера) (обозначается перевёрнутой M, читается «для большинства …»).
Содержание [убрать]
1 Примеры
2 Введение в понятие
3 Кванторы в математической логике
3.1 Свободные и связанные переменные
3.2 Операции над кванторами
4 История появления
5 Литература
6 Ссылки
7 Примечания
Примеры[править | править исходный текст]

Обозначим предикат «x делится на 5». Используя квантор общности, можно формально записать следующие высказывания (конечно, ложные):
любое натуральное число кратно 5;
каждое натуральное число кратно 5;
все натуральные числа кратны 5;
следующим образом:
.
Следующие (уже истинные) высказывания используют квантор существования:
существуют натуральные числа, кратные 5;
найдётся натуральное число, кратное 5;
хотя бы одно натуральное число кратно 5.
Их формальная запись:
.

Пусть на множестве простых чисел задан предикат : «Простое число нечётно». Подставим перед этим предикатом слово «любое». Получим ложное высказывание «любое простое число нечётно» (это высказывание ложно, так как 2 — простое чётное число).
Подставив перед данным предикатом слово «существует», получим истинное выcказывание «Существует простое число , являющееся нечётным» (например, ).
Таким образом, превратить предикат в высказывание можно, поставив перед предикатом слова («все», «существует» и другие), называемые в логике кванторами.
Кванторы в математической логике[править | править исходный текст]

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

Свободные и связанные переменные[править | править исходный текст]
Множество свободных переменных* формулы F определяется рекурсивно, следующим образом:
Свободные переменные.
Все переменные, входящие в атомарную формулу, являются свободными переменными этой формулы,
свободные переменные формулы F являются свободными переменными формулы F,
переменные, являющиеся свободными для хотя бы одной из формул F или G, являются свободными переменными формулы (F Д G),
все свободные переменные формулы F кроме v являются свободными переменными формулы Kv F.
Замкнутая формула.
Формула без свободных переменных называется замкнутой формулой, или предложением.
Связанная переменная.
Переменная v связана в формуле F, если F содержит вхождение Kv, где K — квантор.
Связанное переименованию
Квантор всеобщности (обозначения: , ) — это условие, которое верно для всех обозначенных элементов, в отличие от квантора существования, где условие верно только для каких-то отдельных элементов из указанного множества. Формально говоря, это квантор, используемый для обозначения того, что множество целиком лежит в области истинности указанного предиката. Читается как: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…».
Квантор всеобщности — это попытка формализации обозначения того, что нечто (логическое выражение) истинно для всего, или для любой относящейся к делу сущности. Применяется в предикатной логике и символической логике.
В предикатной логике, квантор существования (экзистенциальный квантификатор) — это предикат свойства или отношения для, по крайней мере, одного элемента области определения. Он обозначается как символ логического оператора (произносится как «существует» или «для некоторого»). Квантор существования отличается от квантора всеобщности, который утверждает, что свойство или отношение выполняется для всех элементов области.