Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Кванторы


Функциональная природа предиката влечет за собой введение ещё одного понятия – квантора. (quantum – от лат. «сколько») Кванторные операции можно рассматривать как обобщение операций конъюнкции и дизъюнкции в случае конечных и бесконечных областей.

Квантор общности (все, всякий, каждый, любой (all – «всякий»)). Соответствующие ему словесное выражение звучит так:

«Для всякого x Р(x) истинно». Вхождение переменной в формулу может быть связанным, если переменная расположена либо непосредственно после знака квантора, либо в области действия квантора, после которого стоит переменная. Все прочие вхождения – свободные, переход от P(x) к x(Px) или (Px) называется связыванием переменной x или навешиванием квантора на переменную x (или на предикат P) или квантификацией переменной х. Переменная, на которую навешивается квантор, называется связанной, несвязанная квантования переменная называется свободной.

Например, переменная x в предикате Р(x) называется свободной ( x – любое из М), в высказывании Р(x) переменную x называют связанной переменной.

Справедлива равносильность P(x1)P(x2)P(xn),

P(x) – предикат, определенный на множестве М={х12...х4}

Квантор существования (exist – «существовать»). Словесное выражение, соответствующее ему, звучит так: “Существует x, при котором Р(x) истинно”. Высказывание xР(x) уже не зависит от x, переменная x связана квантором .

Справедлива равносильность:

xP(x) = P(x1)P(x2)P(xn), где

P(x) - предикат, определенный на множестве М={x1,x2…xn}.

Квантор общности и квантор существования называют двойственными, иногда используется обозначение квантора ! – «существует, и притом, только один».

Ясно, что высказывание xP(x) истинно только в том единственном случае, когда Р(x) - тождественно истинный предикат, а высказывание ложно только тогда, когда Р(x) - тождественно ложный предикат.

Кванторные операции применяются и к многоместным предикатам. Применение кванторной операции к предикату P(x,y) по переменной x ставит в соответствие двухместному предикату P(x,y) одноместный предикат xP(x,y) или xP(x,y), зависящий от у и не зависящий от х.

К двухместному предикату можно применить кванторные операции по обеим переменным. Тогда получим восемь высказываний:

1. P(x,y); 2. P(x,y);

3. P(x,y); 4. P(x,y);

5. P(x,y); 6. P(x,y);

7. P(x,y); 8. P(x,y)

Пример 3. Рассмотреть возможные варианты навешивания кванторов на предикат P(x,y) – “x делится на y”, определенный на множестве натуральных чисел (без нуля) N. Дать словесные формулировки полученных высказываний и определить их истинность.

Операция навешивания кванторов приводит к следующим формулам:



- высказывания “для любых двух натуральных чисел имеет место делимость одного на другое” (или 1) все натуральные числа делятся на любое натуральное число; 2) любое натуральное число является делителем для любого натурального числа) ложные;

- высказывания “существуют такие два натуральных числа, что первое делится на второе” (1. «существует такое натуральное число x, которое делится на какое-то число y»; 2. «существует такое натуральное число y, которое является делителем какого-то натурального числа x») истинны;

- высказывание “существует натуральное число, которое делится на любое натуральное”, ложное;

- высказывание “для всякого натурального числа найдется такое натуральное, которое делится на первое” (или для всякого натурального числа найдется свое делимое), истинное;

- высказывание “для всякого натурального x существует такое натуральное число y, на которое оно делится” (или «для всякого натурального числа найдется свой делитель»), истинное;

- высказывание “существует натуральное число, которое является делителем всякого натурального числа”, истинное (таким делителем является единица).

В общем случае изменение порядка следования кванторов изменяет смысл высказывания и его логическое значение, т.е. например, высказывания P(x,y) и P(x,y) различны.

Пусть предикат P(x,y) означает, что x является матерью для y, тогда P(x,y) означает, что у каждого человека есть мать – истинное утверждение. P(x,y) означает, что существует мать всех людей. Истинность этого утверждения зависит от множества значений, которые могут принимать y: если это множество братьев и сестер, то оно истинно, в противном случае оно ложно. Таким образом, перестановка кванторов всеобщности и существования может изменить сам смысл и значение выражения.

Квантор существования можно выразить через квантор всеобщности применительно к предикату P(x), xP(x) =

Квантор общности можно выразить с помощью квантора существования.

Пусть F1(x)=yP(x,y), тогда yP(x,y)=.

 

Операции над предикатами.Все формулы логики высказываний являются частным случаем логики предикатов. Все операции логики высказываний переносятся в логику предикатов.

Отрицание предиката. Чтобы образовать отрицание предиката, начинающегося одним из знаков или , можно:

1) либо поставить знак перед всем высказыванием

2) либо

а) заменить начальный знак (или ) на противоположный

б) поставить знак перед остальной частью предиката

 

<== предыдущая лекция | следующая лекция ==>
Предикаты. Операции над предикатами | Пример 4

Дата добавления: 2014-01-03; Просмотров: 1576; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.003 сек.