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

Предикаты так же, как высказывания, могут принимать два значения: “истина” (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 — квантор.
Связанное переименованию
Квантор всеобщности (обозначения:, ∀) — это условие, которое верно для всех обозначенных элементов, в отличие от квантора существования, где условие верно только для каких-то отдельных элементов из указанного множества. Формально говоря, это квантор, используемый для обозначения того, что множество целиком лежит в области истинности указанного предиката. Читается как: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…».
Квантор всеобщности — это попытка формализации обозначения того, что нечто (логическое выражение) истинно для всего, или для любой относящейся к делу сущности. Применяется в предикатной логике и символической логике.
В предикатной логике, квантор существования (экзистенциальный квантификатор) — это предикат свойства или отношения для, по крайней мере, одного элемента области определения. Он обозначается как символ логического оператора ∃ (произносится как «существует» или «для некоторого»). Квантор существования отличается от квантора всеобщности, который утверждает, что свойство или отношение выполняется для всех элементов области.