Кафедра информационных систем

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

By 29.11.2007 No Comments

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

Вопрос 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).

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

Leave a Reply