Лекции, шпаргалки, информация по предметам, статьи, лабораторные, тех.задания


Кафедра ИС(АВТ)

Основы дискретной математики - Вопрос 23

Лекции(шпаргалка) по основам дискретной математики для кафедры Информационных систем (ИС), факультет Автоматики и вычислительной техники (АВТ).

Вопрос 23
Понятие квантора, двойственность квантора.
Исчисление предикатов кроме алгебры предикатов содержит новые, дополнительные логические операции квантификации, которые делают его значительно богаче по содержанию. При этом, как и в случае простейших операций, предикаты рассматриваются только с точки зрения их значений, т.е. равносильные предикаты не различаются. Основными операциями квантификации являются применение квантора общности и квантора существования. Определим эти понятия. Пусть А(х) есть одноместный предикат, определенный на множестве М. Запись А(х) означает: "верно, что х удовлетворяет предикату А(х)". Универсальным высказыванием, соответствующим предикату А(x), называется высказывание "каждый элемент множества М удовлетворяет предикату А(х)". Это высказывание обозначается символом (!A)А(х) или !AхА(ж) и считается истинным, если данный предикат тождественно истинный, и ложным в противном случае, (!A - перевернутая первая буква английского слова All - "все"). Знак общности ! заменяет в словесных формулировках слова: "все", "всякий", "каждый", "любой".

Пусть А(х) - одноместный предикат, определенный на множестве М. Экзи-стенциональным высказыванием, соответствующим предикату А(х), называется высказывание "существует элемент множества М, удовлетворяющий предикату А(х)", которое обозначается символом (Эх)А(х) или ЭхА.(х) и считается истинным, если предикат А(х) выполнимый, и ложным в противном случае. (Э - перевернутая первая буква английского слова Exists - "существует" ). Знак существования Э употребляется вместо слов "хотя бы один", "найдется", "существует".

Заметим, что выражения !AxА(х) и ЭхА(х) суть высказывания, а не предикаты, хотя в них присутствует предметная переменная х множества М. Присутствие х здесь связано с принятым способом обозначений. Переменная х, входящая в выражения !АxA(x) и ЭхА(х), является связанной, тогда как переменная х, входящая в предикат А(х), является свободной. Указанные знаки !А и Э в математике носят название кванторов: !А - квантор общности (или всеобщности), Э - квантор существования.

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

Приписывание спереди к предикатной формуле какого-либо квантора называется операцией навешивания квантора (или связывания квантором).

Введенные кванторы не являются независимыми друг от друга. Имеют место соотношения:

|(!Ax)A(x)=(Эx)|A(x), |(Эx)A(x)=(!Ax)|A(x).

Первая формула утверждает: А(х) истинно не для всех х тогда и только тогда, когда существует х, для которого А(х) ложно. Вторая формула утверждает; не существует х, дня которого А(х) истинно, тогда и только тогда, когда А(х) ложно для всех x. Иногда указанные формулы записывают как !AxA(x)=ЭxA(x), ЭхА(х) = !АxA(x).

В силу указанных соотношений кванторы !А и Э называют двойственными друг другу.

Обсудить вопрос в студенческом форуме

 

Сайт содержит информацию о учебном заведении и студенческой общине и не является официальным