![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Предикатам могут быть приписаны кванторы. Знак называется квантором общности, а знак
называется квантором существования.
Кванторы в явном виде впервые были введены немецким математиком Готлобом Фреге в работе «Begriffsschrift» («Исчисление понятий», 1879). В 1885 г. английский логик Чарльз Пирс ввел термины «квантор», «квантификация», происшедшие соответственно от лат. quantun — «сколько» и лат. quantun +facio — «делать». Это означает, что квантор показывает, о скольких (всех или некоторых) объектах говорится в том или ином предложении. Символику для кванторов в виде перевернутых латинских букв ввел итальянский математик Дж. Пеано в 90-е гг. XIX в. После использования кванторов математиками Пеано, Шредером, Расселом они стали широко использоваться.
Символ интерпретируется как фраза «для всех х», соответственно
- «существует х».
Выражение " x P (x) интерпретируется следующим образом: для любого х предикат Р (х) истинный.
Выражение $ х Р (х) интерпретируют следующим образом: существует такое х, что предикат Р (х) истинный.
Определение1. Операцией связывания квантором общности называется правило, по которому каждому одноместному предикату , определенному на множестве М, сопоставляется высказывание, обозначаемое
, которое истинно в том и только в том случае, когда предикат
тождественно истинен, и ложно в противном случае.
Высказывание называется универсальным высказыванием для предиката
. Символ
происходит от первой буквы англ. all — «все».
Определение 2. Операцией связывания квантором существования называется правило, по которому каждому одноместному предикату , определенному на множестве М, ставится в соответствие высказывание, обозначаемое
которое ложно в том и только в том случае, когда
тождественно ложен, и истинно в противном случае.
Высказывание называется экзистенциальным высказыванием для предиката
. Символ
происходит от первой буквы англ. exist — «существовать».
В качестве примера рассмотрим предикат P (x) = «x – нечетное число».
На множестве он является тождественно истинным, поэтому для него справедливо выражение:
,
. На множестве
выражение
истинным не будет, для него справедливо выражение
,
.
Если одноместный предикат задан на конечном множестве
, то нетрудно понять, что высказывание
эквивалентно (имеет то же логическое значение) конъюнкции
. В самом деле, по определению истинность высказывания
означает, что предикат тождественно истинен, т.е. каждое из высказываний
, в которые этот предикат превращается, истинно. Последнее равносильно истинности конъюнкции
.
Если одноместный предикат задан на конечном множестве
, то высказывание
эквивалентно (имеет то же логическое значение) дизъюнкции
. В самом деле, по определению ложность высказывания
означает, что предикат
тождественно ложен, т.е. каждое из высказываний
, в которые данный предикат может превратиться, ложно. Последнее равносильно ложности дизъюнкции
.
Итак, для предикатов, заданных на конечном множестве, квантор общности обобщает операцию конъюнкции, квантор существования обобщает операцию дизъюнкции. Для предикатов, заданных на бесконечном множестве, такого сделать нельзя.
Теперь рассмотрим вопрос о применении операции связывания квантором общности или существования к предикатам с любым числом предметных переменных.
Определение 3. Операцией связывания квантором общности по переменной называется правило, по которому каждому п -местному
предикату
, определенному на множестве М =
, ставится в соответствие новый
-местный предикат, обозначаемый
, который для любых предметов
,
, …,
превращается в высказывание
, истинное в том и только в том случае, когда одноместный предикат
, определенный на множестве
, тождественно истинен, и ложное в противном случае.
Например, рассмотрим двухместный предикат «», определенный на множестве
. Применим к нему квантор общности по переменной х. Получим одноместный предикат
, зависящий от переменной у. Этот предикат может превратиться как в истинное высказывание (при
), так и в ложное (при подстановке вместо у любых натуральных чисел, кроме 1).
Заметим, что к -местному предикату
, зависящему от переменных
, можно снова применить операцию связывания квантором общности по одной из свободных переменных. В результате получится
-местный предикат и т. д.
Например, применив к одноместному предикату , где
, квантор общности по переменной у, получим нуль-местный предикат, т.е. высказывание
. Ясно, что полученное высказывание ложно, потому что предикат
опровержим.
Определение 4. Операцией связывания квантором существования по переменной называется правило, по которому каждому п -местному
предикату
, определенному на множестве М =
, ставится в соответствие новый
-местный предикат, обозначаемый
, который для любых предметов
,
, …,
превращается в высказывание
, ложное в том и только в том случае, когда одноместный предикат
, определенный на множестве
, тождественно ложен, и истинное в противном случае.
Заметим, что к -местному предикату
, зависящему от переменных
, можно снова применить одну из операций квантификации ‑ квантор общности или квантор существования по одной из свободных переменных. В результате получится
-местные предикаты
и
.
Определение 5. Переменная х, входящая в предикат , называется связанной, если она находится под действием квантора
или
. В противном случае, переменная х в предикате
является свободной.
Например, в предикате
переменные х и z ‑связанные, а переменные у и v ‑свободные.
Пример 1. Пусть A(x, y) – некоторый двухместный предикат, определённый на множестве из пяти элементов: M = {a1, a2, a3, a4, a5}, Предикатная функция задана матрицей:
y x | a1 | a2 | a3 | a4 | a5 |
a1 | |||||
a2 | |||||
a3 | |||||
a4 | |||||
a5 |
В результате применения квантификации можно получить четыре одноместных предиката.
x | " (y) A(x, y) | y | " (x) A(x, y) | |
a1 | a1 | |||
a2 | a2 | |||
a3 | a3 | |||
a4 | a4 | |||
a5 | a5 |
x | $ (y) A(x, y) | y | $ (x) A(x, y) | |
a1 | a1 | |||
a2 | a2 | |||
a3 | a3 | |||
a4 | a4 | |||
a5 | a5 |
Если к оставшейся свободной переменной применить квантор, то одноместные предикаты превратятся в высказывания:
$ (x) " (y) A(x, y)= 1 $ (y) " (x) A(x, y)= 0
" (x) $ (y) A(x, y)= 1 " (y) $ (x) A(x, y)= 1
Порядок применения разноимённых кванторов существенен и может привести к различным высказываниям.
Пример 2.
1. Пусть предикат определен на множестве натуральных чисел.
Предикат означает ‑ «для всякого х существует такое y, что x делит y». Это утверждение истинно. Если кванторы поменять местами, то получим предикат
, значение которого ‑ «существует такое число y, что любое х его делит». Это утверждение ложно.
2. Пусть ‑ предикат, определенный на множестве людей. Тогда
означает, что у каждого человека х есть мать у. Предикат с другим порядком кванторов
означает ложное утверждение, что существует мать всех людей.
Дата публикования: 2015-03-26; Прочитано: 785 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!