Кванторы в математике и логике сообщение
Обновлено: 19.05.2024
Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.
Предикаторы могут быть:
Логические операции над предикатами
Представим, что в неком множестве N определены два предиката P(x) и Q(x). Рассмотрим все операции с ними по-отдельности.
Область истины в этом случае — объединение областей истинности обоих утверждений.
Область истины здесь — дополнение множества истинности утверждения P(x) до множества N, иначе говоря \(I_overline=N\I_P=CI_P.\)
Импликация — предикат \(P(x)\rightarrow Q(x)\) , который остается ложным исключительно при тех значениях \(x\in N\) , в которых одновременно P(x) — истинно, а Q(x) — ложно, во всех остальных значениях истинно.
При каждом x справедливо равенство \(P(x)\rightarrow Q(x)=\overline\vee Q(x)\) , а это значит, что область истинности \(P(x)\rightarrow Q(x)\) — объединение дополнения области истинности P(x) до множества N и области истинности предиката Q(x). Обозначается выражением: \(I_=I_\overline P\cup I_Q.\)
Эквиваленция утверждений \(P(x) и Q(x) — P(x)\leftrightarrow Q(x)\) , который делает истинным высказывание при всех \(x\in N\) , где одновременно \(P(x)\) и \(Q(x)\) принимают одинаковые значения истинности.
При каждом фиксированном x справедливо равенство \(P(x)\leftrightarrow Q(x)=(\overline P\vee Q)\wedge(P\vee\overline
Кванторные операции над предикатами
Прежде чем изучить квантовые операции, нужно разобраться, что из себя представляет сам квантор.
Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих высказывание.
Обозначение кванторов
Символическое обозначение кванторов придумал итальянский математик Дж. Пеано в 90-е годы XIX века. Выглядят эти символы так:
Виды кванторов
Квантор общности \(\forall\)
Оно истинно только в том случае, когда \(P(x)\) — тождественно истинен. В ином случае данное высказывание ложно.
Операция связывания квантором общности по переменной \(x_1\) — это правило, в соответствии с которым каждому n-местному \((n\geqslant2)\) предикату \(P(x, x_2, …, x_n)\) , на множествах \(N_1, N_2, …, N_n\) , в соответствие ставится новый \((n-1)\) - местный предикат. Он обозначается как \((\forall x)(P(x, x_2, …, x_n)).\)
Оно истинно только в том случае, когда одноместный предикат \(P(x, a_2, …, a_n)\) на множестве \(N_1\) тождественно истинен. В противном случае оно ложно.
Квантор существования \( \exists\)
Это высказывание ложно только, когда \(P(x)\) , тождественно ложен. В противном случае оно истинно.
Операция связывания квантором существования по переменной \(x_1\) — это правило, в соответствие с которым каждому n-местному \((n\geqslant2)\) высказыванию \(P(x_1, x_2, …, x_n)\) на множествах \(N_1, N_2, …, N_n\) соответствует новый (n-1-местный предикат. Он обозначается как \((\exists)(P(x_1, x_2, …, x_n)\) . Это высказывание ложно только в том случае, если одноместный предикат \((P(x_1, a_2, …, a_n)\) на множестве \(N_1\) тождественно ложен. В противном случае данное высказывание истинно.
Примеры применения
Использование предикатов
Использование кванторов
- любое натуральное число делится на 5;
- каждое натурально число делится на 5;
- все натуральные числа делятся на 5.
В этом случае решение будет выглядеть так:
Чтобы обозначить истинные высказывания, используем квантор существования:
- существуют натуральные числа, которые делятся на 5;
- найдется натуральное число, которое делится на 5;
- хотя бы одно натуральное число делится на 5.
В записи оно будет выглядеть так:
Так, предикат можно превратить в высказывание, если поставить перед ним квантор.
Понятие кванторов
Введем новые логические знаки, обозначаемые %%\forall%%, %%\exists%% и %%\exists!%%. Знак %%\forall%% называется квантором всеобщности, знак %%\exists%% — квантором существования, а %%\exists!%% — квантором существования и единственности.
Пусть %%P(x)%% — одноместный предикат, определенный на множестве %%D%%.
Квантор всеобщности
Используя квантор всеобщности, можно составить следующее высказывание
$$ \forall x~P(x), $$ которое является истинным тогда и только тогда, когда предикат %%P(x)%% является истинным при любом значении пременной %%x%% из множества %%D%%.
Пусть %%P(x)%% предикат %%x^2 \geq 0%%, определенный на множестве действительных чисел %%D = \mathbb R %%. Тогда высказывание %%\forall x~P(x)%% имеет вид %%\forall x~x^2 \geq 0%%. Это истинное высказывание, так как для любого значения пременной %%x = a \in \mathbb R %% получаем истинное высказывание %%a^2 \geq 0%%. Однако, высказывание %%\forall x~ x^2 > 0%% ложно, например, как при %%x = 0%% получаем ложное высказывание %%0 > 0%%.
Квантор существования
Используя квантор существования, можно составить следующее высказывание
$$ \exists x~P(x), $$ которое является истинным тогда и только тогда, когда предикат %%P(x)%% является истинным хотя бы при одном значении пременной %%x%% из множества %%D%%.
Квантор существования и единственности
Используя квантор существования и единственности, можно составить следующее высказывание
$$ \exists! x~P(x), $$ которое является истинным тогда и только тогда, когда предикат %%P(x)%% является истинным только при одном значении пременной %%x%% из множества %%D%%.
Пусть %%P(x)%% — одноместный предикат, тогда выполняются следующие тождества: $$ \begin \overline \equiv \exists x~ \overline,\\ \overline \equiv \forall x~\overline \end $$
Докажем первое из них. Пусть высказываине %%\overline%% истинно. Тогда высказывание %%\forall x~P(x)%% ложно. Поэтому для некоторого %%x = a%% имеем %%P(a)%% ложно. Тогда %%\overline%% истинно. Итак, для некоторого значения %%x = a~\overline%% истинно. Поэтому высказывание %%\exists x~\overline%% истинно.
Аналогично доказывается второе утверждение.
Правила перестановки кванторов
Справедливы следующие тождества $$ \begin \exists x~\exists y~P(x,y) \equiv \exists y~\exists x~P(x,y), \\ \forall x~\forall y~P(x,y) \equiv \forall y~\forall x~P(x,y). \end $$
Для записи одноименных кванторов существуют следующие сокращения:
$$ \begin \forall x~\forall y \equiv \forall x, y~~~ \text\\ \exists x~\exists y \equiv \exists x, y. \end $$
ГОСТ
Понятие предиката
Предикат - утверждение, которое содержит переменные, принимающие значение $1$ или $0$ (истинно или ложно) в зависимости от значений переменных.
Например, выражение $x=x^5$ является предикатом, т.к. оно является истинным при $x=0$ или $x=1$ и ложным при всех остальных значениях $x$.
Множество, на котором предикат принимает только истинные значения, называется множеством истинности предиката $I_p$.
Предикатом в программировании является функция, которая принимает один или более аргументов и возвращает значения булева типа.
Предикат называется тождественно-истинным, если на любом наборе аргументов он принимает истинное значение:
$P (x_1, \dots, x_n)=1$
Предикат называется тождественно-ложным, если на любом наборе аргументов он принимает ложное значение:
$P (x_1, \dots, x_0)=0$
Предикат называется выполнимым, если хотя бы на одном наборе аргументов он принимает истинное значение.
Т.к. предикаты могут принимать только два значения (истинно/ложно или $0/1$), то к ним можно применять все операции алгебры логики: отрицание, конъюнкция, дизъюнкция и т.д.
Примеры предикатов
Таким образом, предикатом является все то, что утверждается или отрицается о субъекте суждения.
Готовые работы на аналогичную тему
Операции над предикатами
Рассмотрим применение операций алгебры логики к предикатам.
Логические операции:
Дизъюнкция двух предикатов $A(x)$ и $B(x)$ -- предикат , который принимает ложное значение при тех и только тех значениях $x$ из $T$, при которых каждый из предикатов принимает ложное значение и принимает истинное значение во всех остальных случаях. Множество истинности предиката -- объединение областей истинности предикатов $A(x)$ и $B(x)$.
Отрицание предиката $A(x)$ -- предикат, который принимает истинное значение при всех значениях $x$ из $T$, при которых предикат $A(x)$ принимает ложное значение и наоборот. Множество истинности предиката $A(x)$ -- дополнение $T'$ к множеству $T$ в множестве $x$.
Множество истинности предиката -- объединение множества истинности предиката $B(x)$ и дополнения к множеству истинности предиката $A(x)$.
Над предикатами помимо логических операций можно выполнять квантовые операции: применение квантора всеобщности, квантора существования и т.д.
Кванторы
Кванторы -- логические операторы, применение которых к предикатам превращает их в ложные или истинные высказывания.
Квантор -- логические операции, которые ограничивают область истинности предиката и создают высказывание.
Чаще всего используют кванторы:
В математической логике существует понятие связывание или квантификация, которые обозначают приписывание квантора к формуле.
Примеры применения кванторов
С помощью квантора всеобщности можно записать следующие ложные высказывания:
любое натуральное число делится на $7$;
каждое натуральное число делится на $7$;
все натуральные числа делятся на $7$;
который будет иметь вид:
Для записи истинных высказываний используем квантор существования:
существуют натуральные числа, которые делятся на $7$;
найдётся натуральное число, которое делится на $7$;
хотя бы одно натуральное число делится на $7$.
Запись будет иметь вид:
Таким образом, предикат можно превратить в высказывание, если поставить перед предикатом квантор.
Операции над кванторами
Для построения отрицания высказываний, которые содержат кванторы, применяется правило отрицания кванторов:
Рассмотрим предложения и выделим среди них предикаты, указав область истинности каждого из них:
Символы математической логики. Кванторы.
Строгость и стройность построения математической теории держится на законах математической логики. Для понимания курса высшей математики необходимо владеть, по крайней мере, некоторыми ее понятиями и правилами. Кроме то, использование кратких и, в то же время, емких символов математической логики помогает восприятию и запоминанию некоторых, порой громоздких, математических определений и теорем.
Рассмотрим теперь утверждение . Истина это или ложь, зависит от того, каков . для одних это утверждение истинно, для других - ложно.
Утверждения, истинность которых зависит от некоторых переменных, называются предикатами. С предикатами тесно связаны кванторы - символы, позволяющие строить из предикатов конкретные математические утверждения.
Мы будем использовать кванторы для сокращения записи и повышения наглядности некоторых математических формулировок.
Кванторов всего два:
- квантор всеобщности.
Читается "для каждого", или "для любого", или "любой" в зависимости от контекста. Обозначение - перевернутая буква А - первая буква английского All - все.
Например, - " для любого действительного выполняется .
- квантор существования.
Читается "существует", "найдется". Обозначение - перевернутая буква Е - первая буква английского Exists - существует. Например, .
Ква́нтор — общее название для логических операций, ограничивающих область истинности какого-либо предиката и создающих выcказывание. Чаще всего упоминают:
В математической логике приписывание квантора к формуле называется связыванием или квантификацией.
Содержание
Примеры
- любое натуральное число кратно 5;
- каждое натуральное число кратно 5;
- все натуральные числа кратны 5;
.
Следующие (уже истинные) высказывания используют квантор существования:
- существуют натуральные числа, кратные 5;
- найдётся натуральное число, кратное 5;
- хотя бы одно натуральное число кратно 5.
Их формальная запись:
.
Введение в понятие
Кванторы в математической логике
Свободные и связанные переменные
Множество свободных переменных* формулы F определяется рекурсивно, следующим образом:
- Все переменные, входящие в атомарную формулу, являются свободными переменными этой формулы,
- свободные переменные формулы F являются свободными переменными формулы ¬F,
- переменные, являющиеся свободными для хотя бы одной из формул F или G, являются свободными переменными формулы (F Д G),
- все свободные переменные формулы F кроме v являются свободными переменными формулы Kv F.
- Формула без свободных переменных называется замкнутой формулой, или предложением.
- Переменная v связана в формуле F, если F содержит вхождение Kv, где K — квантор.
Связанное переименование, свободное переименование
Операции над кванторами
Правило отрицания кванторов — применяется для построения отрицаний высказываний, содержащих кванторы, и имеет вид:
История появления
Философы давно обращали внимание на логические операции, ограничивающие область истинности предиката, однако не выделяли их в отдельный класс операций. Так, Томас Гоббс считал, что они являются частями имен. [1]
Литература
- Клини С. К. Введение в метаматематику, пер. с англ., М., 1957, с. 72—80, 130—138
- Колмогоров А. Н., Драгалин А. Г. Математическая логика. Изд. 3-е, стереотипное. — М.: КомКнига, 2006. 240 с.
- Новиков П. С. Элементы математической логики. — М.: Наука, 1973, 400 с.
- Чёрч А. Введение в математическую логику, пер. с англ., т. 1, М., 1960, с. 42—48.
Ссылки
Примечания
Wikimedia Foundation . 2010 .
Полезное
Смотреть что такое "Квантор" в других словарях:
квантор — сущ., кол во синонимов: 1 • оператор (24) Словарь синонимов ASIS. В.Н. Тришин. 2013 … Словарь синонимов
КВАНТОР — общее название для логических операций, к рые по предикату Р(х)строят высказывание, характеризующее область истинности предиката Р(х). В математич. логике наиболее употребительны квантор всеобщности и квантор существования Высказывание означает,… … Математическая энциклопедия
Квантор — (от лат. quantum сколько) символ, используемый для обозначения некоторых операций математической логики, одновременно логическая операция, дающая количественную характеристику области предметов, к которым относится выражение, получаемое в… … Начала современного естествознания
квантор — (лат. quantum сколько) символ математической логики; логическая операция, дающая количественную характеристику области предметов, к которым относится выражение, получаемое в результате её применения. Новый словарь иностранных слов. by EdwART, ,… … Словарь иностранных слов русского языка
квантор — а, ч., лог. Логічний оператор, який переводить одну висловлювальну форму в іншу. Квантор існування … Український тлумачний словник
квантор — kvantorius statusas T sritis automatika atitikmenys: angl. quantifier vok. Quantor, m rus. квантор, m pranc. quantifier, m … Automatikos terminų žodynas
Квантор — (от лат. quantum сколько) логическая операция, дающая количественную характеристику области предметов, к которой относится выражение, получаемое в результате её применения. В обычном языке носителями таких характеристик служат слова типа… … Большая советская энциклопедия
Читайте также: