Квантор означает что существует хотя бы один экземпляр определенного типа вещей

Квантор существования

Дата добавления: 2014-11-28 ; просмотров: 799 ; Нарушение авторских прав

Квантор существования – это выражение реляционного исчисления, означающее существование хотя бы одной строки, удовлетворяющей условию.

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

Рассмотрим пример запроса:

Перечислить названия фирм-клиентов, покупавших товар 3333.

Эта таблица состоит из одного столбца и целевым списком является

Данные о продажах хранятся в таблице Sale, где код товара ProdId = 3333. Таким образом, условие таково: существует хотя бы одна строка таблицы Sale, содержащая Id (идентификатор клиента) и код товара 3333. Это формулируется следующим образом:

Существует s IN Sale

(s.CustId = r.CustId and s.ProdId = 3333)

Такое выражение читается: «Существует строка s в таблице Sale такая, что s.CustId = r.CustId и s.ProdId = 3333».

Полное решение в реляционном исчислении выглядит так:

(r.CustName : r IN Customer AND exists s IN Sale

(s.CustId = r.CustId and s.ProdId = 3333))

Оно описывает таблицу, состоящую из одного столбца и содержащую названия клиентов, взятых из строк таблицы Customer. Данное название помещается в таблицу решения, если его строка r удовлетворяет условию после двоеточия. В реляционной алгебре для выполнения этого запроса требуется соединение. Рассмотрим более сложный запрос, требующий двух соединений.

Запрос: Кто покупал настольные лампы?

Рассмотрим три таблицы.

Customer (Клиент) Sale (Продажи) Product (Товары)

Этот запрос используется для иллюстрации соединения при описании реляционной алгебры. Решение в реляционном исчислении выглядит так:

Источник

Реляционное исчисление

Большинство работающих языков запросов основано на
реляционном исчислении. Реляционные исчисления — непроцедурные
системы. Исчисления выражают только то, каким должен быть результат
вычисления, но не то, каким образом проводить вычисления. Эта
обязанность возлагается на процессор языка запросов данной СУБД.

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

Реляционное исчисление кортежей является, по сути, формализацией
системы обозначений, предназначенной для образования множеств. В
реляционном исчислении используются булевы операции (И, ИЛИ, НЕ)
над условиями, которые могут быть истинными или ложными. В нем
также используются кванторы существования и всеобщности, означающие, соответственно, что элемент определенного типа существует
или что условие истинно для каждого элемента определенного типа.

В реляционной алгебре для выполнения этого запроса необходимо
использовать алгебраическое выражение, которое должно содержать
следующие операции:
ƒ

· операцию Выбор над отношением r, результатом ее применения к
отношению r является другое отношение, которое представляет
собой подмножество кортежей отношения r со значением, равным 2
в атрибуте Вес:

· проецирование результата предыдущей операции на атрибут
Назв_дет.Окончательный результат запроса будет выглядеть
следующим образом:

В реляционном же исчислении формулировка этого запроса должна
иметь следующий вид:
< t.Назв_дет ⎟ t in r and t.Bec = 2>,
где t — это переменная, обозначающая произвольную строку.
Отношение, из которого берется t, определяется выражением “ in r”которое
означает, что t— строка отношения.
t.Назв_дет — значение атрибута Назв_детв строке r; символ (|) —
разделяет целевой список и определяющее выражение. В данном случае:
t.Назв_дет — целевой список;
t in r and t.Bec = 2 — определяющее выражение;
t.Bec = 2 означает, что значение атрибута Весв строке t равно 2.

Фигурные скобки «<>«, в которые заключено выражение, определяют
результат запроса, как множество значений данных. Что именно входит в
это множество, описывает выражение в скобках. Приведенное здесь решение иллюстрирует почти все элементы реляционного исчисления.

8.2.1. Целевой список и определяющее выражение
Решением каждого запроса в реляционном исчислении является
отношение, которое задается целевым списком и определяющим
выражением. Целевой список определяет атрибуты отношения решения.
Определяющее выражение — это условие, на основании которого
отбираются значения из базы данных, которые войдут в отношение
решения.

В предыдущем примере Назв_детберется из строки и помешается в
строку решения, если строка t удовлетворяет условию
t in r and t. Вес = 2.

Система просматривает строки отношения r одну за другой. Первой
строке временно присваивается имя t и проверяется истинность
определяющего выражения. Поскольку в этом случае t.Вес = 1,
определяющее выражение, ложно, поэтому А — значение атрибута t.Hазв_дет в этой строке не помещается в отношение решения. Затем система переходит к следующей строке, дает ей имя t и снова проверяет истинность определяющего выражения. На этот раз выражение истинно, поэтому Д помещается в отношение решения. Процесс повторяется для каждой строки отношения r. В результате получается следующее
отношение, идентичное полученному ранее:

Целевой список может состоять из нескольких атрибутов,
разделенных запятыми.
.
Рассмотрим еще один пример. Пусть даны отношения:

Согласно алгебраическому выражению πНазв_дет(r ∩ s) реляционной
алгебры, содержащему операции пересечения и проецирования, получим
отношение:

Несколько иначе выглядят аналоги только двух операций
реляционной алгебры — операций соединения и деления. Для построения
аналогов этих операций требуются кванторы: квантор существования для соединения и квантор всеобщности для деления.

8.2.2. Квантор существования
Квантор существования означает, что существует хотя бы один
экземпляр определенного типа вещей. В реляционном исчислении квантор
существования используется для задания условия того, что определенный
тип строк в отношении существует.
Рассмотрим отношения:

Оно описывает отношение, состоящее из одного столбца и
содержащее названия деталей, взятых из строк отношения
ПОТРЕБНОСТИ. Данное название помещается в отношение решения, если его строка t удовлетворяет условию после знака «⎟».

Рассмотрим подробнее вышеописанный механизм обработки
нескольких строк отношения ПОТРЕБНОСТИ, чтобы понять, как будет
применяться условие.
Первая строка отношения ПОТРЕБНОСТИ(которая обозначена t)
имеет Назв_дет = А, и оно будет помещено в результирующее отношение,
если в отношении СКЛАДсуществует строка, в которой Код_дет= ‘01’, а
Кол_дет > t.Количество. Такая строка действительно существует, и она
обозначена как s. Итак, t удовлетворяет определяющему условию, поэтому
t.Hазв_дет помещается в отношение решения. Этот процесс должен
повториться для каждой строки отношения ПОТРЕБНОСТИ. Когда
закончена обработка первой строки, вторая строка обозначена t, и теперь
уже для нее ищется соответствующая строка s в отношении СКЛАД.
Такой строки не существует, поэтому Д не помещается в результирующее
отношение. Продолжая дальше обработку строк отношений по указанному алгоритму, получим множество решения, которое составит новое
отношение, и будет выглядеть следующим образом:

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

8.2.3. Квантор всеобщности
Квантор всеобщности означает, что некоторое условие применяется
ко всем строкам или к каждой строке некоторого типа. Он используется в
тех же целях, что и операция деления реляционной алгебры.
Проиллюстрируем его применение тем же запросом, который
рассматривался в разделе, описывающем операцию деления. Пусть даны
два отношения:

Требуется определить фамилии тех студентов, каждый из которых
сдавал все экзамены, перечисленные в отношении RASP. Необходимо
обратить внимание на то, что условие выбора студента содержит
определение каждый. В результирующее отношение нключаются только те
студенты, которые сдавали каждый экзамен. Если взглянуть на
полученный результат, то можно увидеть, что условию запроса
удовлетворяют только два студента.
Полное решение в реляционном исчислении с использованием
квантора всеобщности FORALL таково:
FORALL s,
где t — кортеж отношения VEDOM;
s — кортеж отношения RASP.

Имя студента из строки t таблицы VEDOMпомещается в
результирующее отношение, если определяющее выражение истинно для
строки t, а определяющее выражение истинно, если для каждой строки s
отношения RASPдолжна существовать строка t в отношении VEDOM, удовлетворяющая условию, то есть в данном случае для каждой строки s
отношения RASPдолжна существовать строка t в отношении VEDOMс
одной и то же фамилией:
ƒ

· Иванов присутствует в строках t (1) и t (2): t (1) соответствует s (2) и
t (2) соответствует s (1);
ƒ

· Сидоров присутствует в строках t (3) и t (4): t (3) соответствует s (2)
и t (4) соответствует s (1);
ƒ

· Коровин присутствует только в строке t (5): t (5) соответствует s (1),
а для s (2) нет соответствующей строки t.

Полное соответствие всем строкам отношения RASP есть только у
Иванова и Сидорова. Таким образом, они и вошли в результирующее отношение.

Источник

MT1102: Линейная алгебра (введение в математику)

В алгебре высказываний применяют логические знаки для записи различных утверждений. Однако нам не достаточно этих знаков для выражения мысли типа «Всякий элемент %%x%% из множества %%D%% обладает свойством %%P(x)%%».

Понятие кванторов

Введем новые логические знаки, обозначаемые %%\forall%%, %%\exists%% и %%\exists!%%. Знак %%\forall%% называется квантором всеобщности, знак %%\exists%% — квантором существования, а %%\exists!%% — квантором существования и единственности.

Пусть %%P(x)%% — одноместный предикат, определенный на множестве %%D%%.

Квантор всеобщности

Используя квантор всеобщности, можно составить следующее высказывание

Читается как: «для любого %%x%% выполняется %%P(x)%%»; «для всякого %%x

P(x)%%»; «для всякого %%x%% верно %%P(x)%%» и т.п.

Пусть %%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%%.

Квантор существования

Используя квантор существования, можно составить следующее высказывание

Читается как: «существует %%x%% такой, что %%P(x)%%»; «существует %%x%% с условием %%P(x)%%» и т.п.

Квантор существования и единственности

Используя квантор существования и единственности, можно составить следующее высказывание

Читается как: «существует единственный %%x%% такой, что %%P(x)%%»; «существует единственный %%x%% с условием %%P(x)%%» и т.п.

Отрицание «кванторов»

Докажем первое из них. Пусть высказываине %%\overline<\forall x

P(x)>%% истинно. Тогда высказывание %%\forall x

P(x)%% ложно. Поэтому для некоторого %%x = a%% имеем %%P(a)%% ложно. Тогда %%\overline%% истинно. Итак, для некоторого значения %%x = a

\overline%% истинно. Поэтому высказывание %%\exists x

Аналогично доказывается второе утверждение.

Применение одного из кванторов «понижает» степень предиката на единицу. Из двуместного предиката получается одноместный предикат, а из одноместного — предикат %%0%% степени или высказывание.

Правила перестановки кванторов

P(x,y) \equiv \exists y

P(x,y) \equiv \forall y

Однако, разноименные кванторы переставлять местами нельзя. Рассмотрим двуместный предикат %%P(x, y): x + y = 0%%, определенный на множестве %%\mathbb R%%. Тогда высказывание %%\exists x

x + y = 0%% можно прочитать так: «существует %%x%%, которое в сумме с любым %%y%% равно 0». Это ложно высказывание.

Переставим разноименные кванторы местами и получим высказывание %%\forall y

x+ y = 0%%, которое можно прочитать так: «для любого %%y%% существует %%x%% такой, что их сумма равна 0». Это истинное высказывание. В итоге получили различные истинностные значения высказываний.

Для записи одноименных кванторов существуют следующие сокращения:

\forall y \equiv \forall x, y

\exists y \equiv \exists x, y. \end $$

Источник

КВАНТОР

Полезное

Смотреть что такое «КВАНТОР» в других словарях:

квантор — сущ., кол во синонимов: 1 • оператор (24) Словарь синонимов ASIS. В.Н. Тришин. 2013 … Словарь синонимов

квантор — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN quantifier … Справочник технического переводчика

КВАНТОР — общее название для логических операций, к рые по предикату Р(х)строят высказывание, характеризующее область истинности предиката Р(х). В математич. логике наиболее употребительны квантор всеобщности и квантор существования Высказывание означает,… … Математическая энциклопедия

Квантор — (от лат. quantum сколько) символ, используемый для обозначения некоторых операций математической логики, одновременно логическая операция, дающая количественную характеристику области предметов, к которым относится выражение, получаемое в… … Начала современного естествознания

квантор — а, ч., лог. Логічний оператор, який переводить одну висловлювальну форму в іншу. Квантор існування … Український тлумачний словник

квантор — kvantorius statusas T sritis automatika atitikmenys: angl. quantifier vok. Quantor, m rus. квантор, m pranc. quantifier, m … Automatikos terminų žodynas

Квантор — (от лат. quantum сколько) логическая операция, дающая количественную характеристику области предметов, к которой относится выражение, получаемое в результате её применения. В обычном языке носителями таких характеристик служат слова типа… … Большая советская энциклопедия

квантор — кв антор, а … Русский орфографический словарь

Источник

Логические операции. Кванторы

Логические операции

В любом национальном языке употребляемые в обычной речи связки “и”, “или”, “если …, то …”, “тогда и только тогда, когда …” и т.п. позволяют из уже заданных высказываний строить новые сложные высказывания. Истинность или ложность получаемых таким образом высказываний зависит от истинности и ложности исходных высказываний и соответствующей трактовки связок как операций над высказываниями. Логическая операция полностью может быть описана таблицей истинности, указывающей, какие значения принимает сложное высказывание при всех возможных значениях простых высказываний.

Логической операцией называется способ построения сложного высказывания из элементарных высказываний, при котором истинностное значение сложного высказывания полностью определяется истинностными значениями исходных высказываний (см. статью “Высказывания. Логические значения”).

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

Рассмотрим два высказывания: p = “Колумб был в Индии” и q = “Колумб был в Египте”. Очевидно, что новое высказывание p q = “Колумб был в Индии или был в Египте” истинно как в случае, если Колумб был в Индии, но не был в Египте, так и в случае, если он не был в Индии, но был в Египте, а также в случае, если он был и в Индии, и в Египте. Но это высказывание будет ложно, если Колумб не был ни в Индии, ни в Египте.

Союз “или” может применяться в речи и в другом, “исключающем” смысле. Тогда он соответствует другому высказыванию — разделительной, или строгой, дизъюнкции.

Строгая, или разделительная, дизъюнкция — логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся истинным только тогда, когда только одно из высказываний является истинным. Логическая операция разделительная дизъюнкция определяется следующей таблицей истинности:

Рассмотрим два высказывания: p = “Кошка охотится за мышами” и q = “Кошка спит на диване”. Очевидно, что новое высказывание p q истинно только в двух случаях — когда кошка охотится за мышами либо когда кошка мирно спит. Это высказывание будет ложно, если кошка не делает ни того, ни другого, т.е. когда оба события не происходят. Но это высказывание будет ложным и тогда, когда предполагается, что оба высказывания произойдут одновременно. В силу того, что этого произойти не может, высказывание и является ложным.

В логике связкам “либо” и “или” придается разное значение, однако в русском языке связку “или” иногда употребляют вместо связки “либо”. В этих случаях однозначность определения используемой логической операции связана с анализом содержания высказывания. Например, анализ высказывания “Петя сидит на трибуне А либо на трибуне Б” заменить на “Петя сидит на трибуне А или Б”, то анализ последнего высказывания однозначно укажет на логическую операцию разделительная дизъюнкция, т.к. человек не может находиться в двух разных местах одновременно.

Импликация — логическая операция, ставящая в соответствие каждым двум элементарным высказываниям новое высказывание, являющееся ложным тогда и только тогда, когда условие (посылка) — истинно, а следствие (заключение) — ложно. Подавляющее число зависимостей между событиями можно описать с помощью импликации. Например, высказыванием “Если на каникулах мы поедем в Петербург, то посетим Исаакиевский собор” мы утверждаем, что в случае приезда на каникулах в Петербург Исаакиевский собор мы посетим обязательно.

Логическая операция импликация задается следующей таблицей истинности:

Импликация будет ложной только тогда, когда посылка истинна, а заключение ложно, и она заведомо будет истинна, если ее условие p ложно. Причем для математика это вполне естественно. В самом деле, исходя из ложной посылки, можно путем верных рассуждений получить как истинное, так и ложное утверждение.

Допустим, 1 = 2, тогда и 2 = 1. Складывая эти равенства, мы получим 3 = 3, т.е. из ложной посылки путем тождественных преобразований мы получили истинное высказывание.

Импликация, образованная из высказываний А и В, может быть записана при помощи следующих предложений: “Если А, то В”, “Из А следует В”, “А влечет В”, “Для того чтобы А, необходимо, чтобы В”, “Для того чтобы В, достаточно, чтобы А”.

Эквивалентность — логическая операция, ставящая в соответствие двум элементарным высказываниям новое, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны. Логическая операция эквивалентность задается следующей таблицей истинности:

Рассмотрим возможные значения сложного высказывания, являющегося эквивалентностью: “Учитель поставит ученику 5 в четверти тогда и только тогда, когда ученик получит 5 на зачете”.

1) Ученик получил 5 на зачете и 5 в четверти, т.е. учитель выполнил свое обещание, следовательно, высказывание является истинным.

2) Ученик не получил на зачете 5, и учитель не поставил ему 5 в четверти, т.е. учитель свое обещание сдержал, высказывание является истинным.

3) Ученик не получил на зачете 5, но учитель поставил ему 5 в четверти, т.е. учитель свое обещание не сдержал, высказывание является ложным.

4) Ученик получил на зачете 5, но учитель не поставил ему 5 в четверти, т.е. учитель свое обещание не сдержал, высказывание является ложным.

Отметим, что в математических теоремах эквивалентность выражается связкой “необходимо и достаточно”.

Рассмотренные выше операции были двухместными (бинарными), т.е. выполнялись над двумя операндами (высказываниями). В алгебре логики определена и широко применяется и одноместная (унарная) операция отрицание.

Отрицание — логическая операция, которая каждому элементарному высказыванию ставит в соответствие новое высказывание, значение которого противоположно исходному. Логическая операция отрицание задается следующей таблицей истинности:

В русском языке для построения отрицания используется связка “неверно, что …”. Хотя связка “неверно, что …” и не связывает двух каких-либо высказываний в одно, она трактуется логиками как логическая операция, поскольку, поставленная перед произвольным высказыванием, образует из него новое.

Отрицанием высказывания “У меня дома есть компьютер” будет высказывание “Неверно, что у меня дома есть компьютер” или, что в русском языке то же самое, “У меня дома нет компьютера”. Отрицанием высказывания “Я не знаю китайского языка” будет высказывание “Неверно, что я не знаю китайского языка” или, что в русском языке одно и то же, “Я знаю китайский язык”.

Кванторы

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

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

Квантор общности позволяет из данной высказывательной формы с единственной свободной переменной x получить высказывание с помощью связки “Для всех x …”. Результат применения квантора общности к высказывательной форме A(x) обозначают x A(x). Высказывание x A(x) будет истинным тогда и только тогда, когда при подстановке в A(x) вместо свободной переменной x любого объекта из области возможных значений всегда получается истинное высказывание. Высказывание x A(x) может читаться следующим образом: “Для любого x имеет место A(x)”, “A(x) при произвольном x”, “Для всех x верно A(x)”, “Каждый x обладает свойством A(x)” и т.п.

Квантор существования позволяет из данной высказывательной формы с единственной свободной переменной x получить высказывание с помощью связки “Существует такой x, что …”. Результат применения квантора общности к высказывательной форме A(x) обозначают x A(x). Высказывание
x A(x) истинно тогда и только тогда, когда в области возможных значений переменной x найдется такой объект, что при подстановке его имени вместо вхождения свободной переменной x в A(x) получается истинной высказывание. Высказывание x A(x) может читаться следующим образом: “Для некоторого x имеет место A(x)”, “Для подходящего x верно A(x)”, “Существует x, для которого A(x)”, “Хотя бы для одного x верно A(x)” и т.п.

Кванторы играют для формализованных языков математической логики ту же роль, которую играют для естественного языка так называемые “количественные” (“кванторные”) слова, — определяют область применимости данного высказывания (или высказывательной формы).

При построении отрицания к высказыванию, содержащему квантор, действует следующее правило: частица “не” добавляется к сказуемому, квантор общности заменяется на квантор единственности и наоборот. Рассмотрим пример. Отрицанием высказывания “Все юноши 11-х классов — отличники” является высказывание “Неверно, что все юноши 11-х классов — отличники” или “Некоторые юноши 11-х классов — не отличники”.

В информатике кванторы применяются в логических языках программирования (см. “Языки программирования”) и языках запросов к базам данных.

Методические рекомендации

Умение строить сложные высказывания требуется при работе с базами данных, при конструировании запроса поиска в Интернете, при построении алгоритмов и написании программ на любом алгоритмическом языке. Более того, это умение можно отнести к общешкольным умениям, т.к. оно связано с построением сложных умозаключений (рассуждений, получений выводов). В основе этого умения лежат знание основных логических операций и умение определять истинность сложных высказываний.

С логическими операциями дизъюнкция, конъюнкция и отрицание школьники знакомятся в основной школе. Там же вводится и понятие таблицы истинности. Скорее всего знакомство с данными понятиями возникает в языках программирования, но использовать их можно и в электронных таблицах — там логические операции реализованы через соответствующие функции OR, AND, NOT.

Более сложные логические операции могут быть рассмотрены в старшей школе. Задачи, использующие импликацию, встречаются в каждом из опубликованных вариантов ЕГЭ по информатике. Например: для какого числа X истинно высказывание ((X > 3) (X (X

6 От латинских слов idem — тот же самый и potens — сильный; дословно — равносильный.

7 Это определение легко распространяется на случай n высказываний (n > 2, n — натуральное число).

8 Это определение, как и предыдущее, распространяется на случай n высказываний (n > 2, n — натуральное число).

9 Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. М.: Физматлит, 2002.

Источник