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


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

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

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

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

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

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

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

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

Введенные кванторы не являются независимыми друг от друга. Имеют место соотношения: |(Vx)A(x)=(3x)lA(x), |(Зх)A(x)=(Vx)|A(х).

Первая формула утверждает: А(х) истинно не для всех х тогда и только тогда, когда существует х, для которого А(х) ложно. Вторая формула утверждает: не существует х, для которого А(х) истинно, тогда и только тогда, когда А(х) ложно для всех х. Иногда указанные формулы записывают как VxA(x)==3xA(x),ЗхА(х)=VxA(x). В силу указанных соотношений кванторы V и 3 называют двойственными друг другу. Перейдем к многоместным предикатам.

Пусть А(х1,х2,..., хn) есть п - местный предикат, определенный на множествах M1, M2,..., Мn (n=>2). Предикатом, полученным из А(х1,х2,...,хn) применением квантора общности (или существования) по переменной х1, называется (n-1) -местный предикат, определенный на множествах М2,...,Мn значением универсального (экзистенциокального) высказывания, соответствующего одноместкому предикату А(х1, х02,...,xon), который получается из данного n-местного предиката заменой переменных х2,...,xn соответствующими им аргументами x02,...,xon. Такой предикат обозначается Vx1A(x1, x2,...,хn) или Зх1А(x1, x2,...,хn) соответственно. К этим ( п - 1) -местным предикатам снова можно применить один из кванторов по любой свободной переменной, получая (п -2) - местные предикаты, и т.д. После п - кратного применения кванторов к n-местному предикату все его свободные переменные будут связаны и получится высказывание.

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

Рассмотрим

Пример 3.31. Пусть А(х,у) и В(х) - предикаты примера. 3.30. Множество истинности дизъюнкции этих предикатов F(x, у) = А(х,y)vB(x) изображено защтрихо-ванной фигурой рис.3.24 а. Найдем предикаты, которые получаются из F(д, у) навешивании на него различных кванторов по различным переменным. Решение. Вначале найдем множество истинности предиката F1(x) = 3yF(x у). Так как здесь переменная у связана, то предикат F1(x) зависит только от х. Выясним, каково его значение при различных х.

Пусть х = x1<2. Проведем на рис.3.24б прямую х = x1. Она проходит через точку х=x1 параллельно оси ординат. Выражение F1(x) согласно приведенной формуле читается "при х=х1 существует хотя бы одно значение у, при котором F(X1,у) истинно". Но прямая х = x1 нигде не пересекает заштрихованное множество истинности предиката F(x,у). Следовательно, это высказывание ложно. Возьмем' теперь на рис. 3.246 прямую х = х2. Очевидно, что, прохода внутри окружности, эта прямая пересекает заштрихованную область (т.е. область истинности предиката F(x, у) ), и здесь высказывание F1(x2)=3yF(x2,у) истинно. Самая левая точка, где оно истинно, есть х = -2, а правая х=безконечности. Поэтому предикат F1(x) =(-2
Для точки х1 выражение F(x1) = VyF(x1,у) читается "при х=x1 для всех значений высказывание F(x1,у) истинно". Но из рис.3.246 следует, что это не так ни для точки x1, ни для точки x2, но справедливо для точки x3. Поэтому здесь F2(x) = (1<х
Аналогично, выбирая прямые y=y1 и т.д., можно получить F3(у) = =3xF(x, у)=1,F4(y)=VxF(x,у)=0, т.е. F3(у) есть тождественно истинный предикат (истинное высказывание), a F4,(y) - тождественно ложный предикат (ложное высказывание).

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

 

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