авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 | 5 |

«УДК 002; 004.3(075.8) МИНОБРНАУКИ РОССИИ ББК 32.81; 32.97я73 ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ ...»

-- [ Страница 3 ] --

заключительная часть обеспечивает переход автомата из со стояния q3 в «хорошее» состояние q8. Отметим, что, следуя указанному принципу при по строении диаграммы конечного автомата для языка Labcbca,асb, мы встретимся с осложнением:

из состояния q3 по букве а следует идти в q4, если этой буквой начинается очередное подсло во, и в q6, если этой буквой начинается заключительное подслово.

Рис. 3.22. Диаграмма конечного автомата, распознающего регулярный язык Примеры.

В нижеперечисленных примерах 3.1–3.19 требуется построить конечный автомат, рас познающий язык L. В примерах 3.1–3.8 алфавит А = {a,b,c}. В примерах 3.9–3.19 алфавит А = {0, 1, 2, …9} Пример 3.1. L тогда и только тогда, когда в слове встречается не более трех букв а подряд.

Пример 3.2. L тогда и только тогда, когда в слове сочетание ab встречается не бо лее двух раз.

Пример 3.3. L тогда и только тогда, когда в слове содержится подслово bbсс.

Пример 3.4. L тогда и только тогда, когда слово имеет длину не более 8 и содер жащит одинаковое число букв a и b.

Пример 3.5. L тогда и только тогда, когда слово содержит четное число букв.

Пример 3.6. L тогда и только тогда, когда слово содержит нечетное число букв а.

Пример 3.7. L тогда и только тогда, когда при наличии в слове буквы a там встре чается также и буква b.

Пример 3.8. L тогда и только тогда, когда каждая буква алфавита встречается в сло ве не более двух раз.

Пример 3.9. L = L(4).

Пример 3.10. L = L(6).

Пример 3.11. L = L(7).

Пример 3.12. L = L(8).

Пример 3.13. L = L(10).

Пример 3.14. L = L(15).

Пример 3.15. L = L(20).

Пример 3.16. L = L(25).

Пример 3.17. L = L(30).

Пример 3.18. L = L(50).

Пример 3.19. L = L(125).

Пример 3.20.

Построить конечные автоматы, распознающие объединение, пересечение и разность языков, заданных конечными автоматами, диаграммы которых представлены на рис. 3.22.

Рис. 3.22. Конечные автоматы, распознающие объединение, пересечение и разность языков, заданных другими конечными автоматами Пример 3.21.

Построить конечные автоматы, распознающие объединение, пересечение и разность языков, заданных конечными автоматами, диаграммы которых представлены на рис. 3.23.

Рис. 3.23. Конечные автоматы, распознающие объединение, пересечение и разность языков, заданных другими конечными автоматами Пример 3.22.

Построить конечные автоматы, распознающие объединение, пересечение и разность языков, заданных конечными автоматами, диаграммы которых представлены на рис. 3.24.

Рис. 3.24. Конечные автоматы, распознающие объединение, пересечение и разность языков, заданных другими конечными автоматами Пример 3.23.

Построить конечные автоматы, распознающие объединение, пересечение и разность языков, заданных конечными автоматами, диаграммы которых представлены на рис.3.25.

Рис. 3.25. Конечные автоматы, распознающие объединение, пересечение и разность языков, заданных другими конечными автоматами 2.1.3.4. Недетерминированные конечные автоматы и определяемые ими языки.

Недетерминированный конечный автомат определяем как совокупность K* = {Q, A, q0, g*, F}, где Q, A, q0 и F имеют тот же смысл, что в п. 2.1.3.3, а функция переходов g* явля ется отображением типа QxА [2Q\ ]. Напомним, что для любого множества М через 2М обозначается множество всех подмножеств из М;

символ обозначает пустое множество.

Совокупность g*(qi,аj) – это всегда непустое подмножество состояний автомата, в лю бое из которых он может перейти из состояния qi под воздействием буквы аj, здесь qi Q, аj А.

В отличие от недетерминированных автоматов, конечные автоматы, введенные в пре дыдущем пункте, именуем детерминированными. Детерминированный конечный автомат является частным случаем недетерминированного, он получается из последнего в предполо жении, что все множества g*(qi,аj) являются одноэлементными.

Будучи запущен в работу над произвольным словом из своего начального состояния, недетерминированный конечный автомат может функционировать по-разному. Язык L(K*), распознаваемый недетерминированным конечным автоматом K*, определяем следующим образом: слово принадлежит языку L(K*) тогда и только тогда, когда имеется последова тельность состояний автомата такая, что qr0 = q0 ;

qr1 g * (qr0, ai1 );

qr2 g * (qr1, ai2 );

...

qrp g (qrp1, ai p );

* при этом q rp F.

Иными словами, слово принадлежит языку L(K*) тогда и только тогда, когда сущест вует способ работы данного автомата над данным словом такой, что после завершения обра ботки автомат оказывается в состоянии, принадлежащем множеству F.

На рис. 3.26 дан пример недетерминированного конечного автомата K1* (причина неде терминированности заключается в том, что под воздействием буквы а автомат из состояния q0 может либо перейти в состояние q1, либо остаться в состоянии q0). Легко видеть, что язык L(K1*) совпадает с ранее введенным регулярным языком L4.

Рис. 3.26. Недетерминированный конечный автомат Теорема 3.4. Языки, определяемые недетерминированными конечными автоматами, являются регулярными языками.

По произвольному недетерминированному конечному автомату K* = {Q, A, q0, g*, F}, распознающему язык L(K*), детерминированный автомат K = {Q, A, q0, g, F} такой, что L(K) = L(K*), строим следующим образом. Полагаем Q = 2Q\, т. е. состояниями автомата K считаем непустые подмножества состояний автомата K*, при этом определяем q0 = {q0}.

Функцию переходов автомата K строим таким образом, чтобы, обработав из q0 произволь ное слово, этот автомат приходил в состояние, представляющее собой подмножество со стояний исходного автомата K*, в каждое из которых K* может перейти из своего начально го состояния в результате обработки некоторым способом данного слова. Достижение ука занной цели обеспечивается следующим определением функции g: qu g(qi,aj) ( qv qi) такое, что {qu g*(qv,аj)}.

Так как слово принадлежит L(K*) тогда и только тогда, когда существует способ ра боты автомата K* над данным словом такой, что после завершения обработки автомат ока зывается в одном из состояний множества F, совокупность F определяем следующим обра зом: произвольное состояние qi F тогда и только тогда, когда q iF.

Построенный изложенным способом детерминированный конечный автомат распозна ет тот же язык, что и исходный автомат K*. Теорема доказана.

Далее в данном пособии недетерминированность рассматриваемых автоматов будет оговариваться дополнительно, под термином «конечный автомат» всегда понимается детер минированный конечный автомат.

Два автомата называем эквивалентными, если они распознают один и тот же язык. Со гласно изложенному в доказательстве теоремы 3.4 алгоритму, для недетерминированного конечного автомата с N состояниями всегда можно построить эквивалентный ему детерми нированный конечный автомат, имеющий 2N–1 состояние. В действительности число тре буемых состояний может оказаться меньшим. На рис. 3.27 представлен недетерминирован ный автомат K*, имеющий 3 состояния. Диаграмму переходов эквивалентного ему детерми нированный конечного автомата K (см. рис. 3.28) строим следующим образом. Вводим вер шину – состояние {q0}. Из своего начального состояния q0 автомат K* по букве а либо пере ходит в q1, либо остается в q0;

по букве b автомат переходит в q2. Поэтому автомат K по бук ве а из {q0} переходит в состояние {q0,q1}, а по букве b переходит в состояние {q2}. Из со стояний совокупности {q0,q1} по букве а автомат K* переходит в состояния той же совокуп ности, а по букве b как из состояния q0, так и из состояния q1 реализуется переход в q2. По этому автомат K по букве а из {q0,q1} переходит в то же состояние {q0,q1}, а по букве b пе реходит в состояние {q2}. Из состояния q2 автомат K* по букве а переходит в q0, а по букве b – остается в q2. Поэтому автомат K по букве а из {q2} переходит в {q0}, а по букве b – оста ется в {q2}.

Построение автомата K закончено. Другие мыслимые состояния-подмножества оказы ваются излишними, они недостижимы;

начав работу из своего начального состояния, авто мат может оказываться только в трех введенных состояниях (включая начальное).

Рис. 3.27. Рис. 3.28.

Концепция недетерминированного конечного автомата легко применяется для по строения автомата, распознающего объединение двух регулярных языков. Пусть L1 и L2 – ре гулярные языки, распознаваемые конечными автоматами K1 = {Q1, A, q10, g1, F1} и K2 = {Q2, A, q20, g2, F2} соответственно. Пусть D1 и D2 – диаграммы переходов, определяющие эти ко нечные автоматы. Для построения диаграммы переходов D автомата, распознающего объе динение языков L1 и L2, объединяем эти диаграммы следующим образом. Вводим новую вершину – состояние q0. По каждой букве х входного алфавита А из q0 проводим две дуги с надписанной буквой х;

верхняя дуга имеет своим концом вершину g1(q10,х), т.е. состояние, в которое переходит из своего начального состояния под воздействием буквы х первый авто мат, а нижняя – вершину g2(q20, х), т.е. состояние, в которое переходит из своего начального состояния под воздействием буквы х второй автомат. Начальным состоянием построенного автомата считаем q0;

множество F его «хороших» состояний определяем как объединение множеств F1 и F2. Специально отметим, что в случае, когда хотя бы в одном из автоматов K1, K2 начальное состояние является «хорошим», в F следует включить состояние q0. На первом такте обработки любого непустого входного слова = х автомат имеет возможность пере хода из q0 либо по верхней, либо по нижней дуге с надписанной буквой х.

Если реализован переход по верхней дуге, то далее фактически работает автомат K1 и проверяется принадлежность слова языку L1;

если реализован переход по нижней дуге, да лее работает автомат K2 и проверяется принадлежность слова языку L2;

построенный авто мат в результате обработки произвольного входного слова может оказаться в состоянии, принадлежащем подмножеству F, тогда и только тогда, когда принадлежит объединению языков L1 и L2. На рис. 3.29 представлена диаграмма переходов построенного по изложенной схеме недетерминированного конечного автомата, распознающего множество чисел, каждое из которых кратно 2 или 5.

В заключение отметим, что для любых слов, и в произвольном алфавите А опре деляемый ими язык L, (см. п.2) является регулярным.

Диаграмма (вообще говоря, недетерминированного) конечного автомата, определяю щего этот язык, строится аналогично представленной на рис. 3.13 диаграмме автомата, опре деляющего язык Labcbca,cab.

Рис. 3.29. Диаграмма переходов недетерминированного конечного автомата, распознающе го множество чисел, каждое из которых кратно 2 или Примеры.

Пример 3.24.

По недетерминированному конечному автомату, диаграмма которого представлена на рис. 3.30, построить детерминированный конечный автомат, распознающий тот же язык.

Рис. 3.30. Недетерминированный конечный автомат Пример 3.25.

По недетерминированному конечному автомату, диаграмма которого представлена на рис. 3.31, построить детерминированный конечный автомат, распознающий тот же язык.

Рис. 3.31. Недетерминированный конечный автомат Пример 3.26.

По недетерминированному конечному автомату, диаграмма которого представлена на рис. 3.32, построить детерминированный конечный автомат, распознающий тот же язык.

Рис. 3.32. Недетерминированный конечный автомат Пример 3.27.

Построить конечный автомат, распознающий дополнение к языку, заданному недетер минированным конечным автоматом, диаграмма которого представлена на рис. 3.33.

Рис. 3.33. Недетерминированный конечный автомат Пример 3.28.

Построить недетерминированный конечный автомат, распознающий объединение язы ков, заданных конечными автоматами, диаграммы которых представлены на рис. 3.34.

Рис. 3.34. Заданные конечные автоматы Пример 3.29.

Построить недетерминированный конечный автомат, распознающий множество чисел, делящихся на 25.

2.1.3.5. Размещения, перестановки, сочетания, сочетания с повторениями.

Бином Ньютона.

А. Перестановки, размещения, сочетания Пусть A = {a1,..., an} – конечное множество. Совокупность из k элементов множества A (не обязательно различных) называется k-выборкой множества A. Выборка называется упо рядоченной, если каждому ее элементу поставлен в соответствие номер – натуральное число, не превосходящее k так, что разным элементам соответствуют разные числа. Упорядоченные выборки будем называть также наборами. Элементы упорядоченных выборок будем заклю чать в круглые скобки, а элементы неупорядоченных выборок – в фигурные скобки. Напри мер, (a1, a2, a2) и (a2, a1, a2) – две различных упорядоченных выборки, а {a1, a2, a2} и {a2, a1, a2} – одна и та же неупорядоченная выборка.

Перестановкой n-элементного множества A = {a1,..., an} называется любой набор (ai1,..., ain), состоящий из элементов A, в котором каждый элемент из A встречается ровно один раз. Например, у трех элементного множества {a1, a2, a3} существует ровно шесть раз личных перестановок:

(a1, a2, a3), (a1, a3, a2), (a2, a1, a3), (a2, a3, a1), (a3, a1, a2), (a3, a2, a1).

Найдем число Pn различных перестановок n-элементного множества. Для этого из n элементного множества будем последовательно выбирать элементы и формировать из них упорядоченную выборку: первый выбранный элемент станет первым элементом упорядо ченной выборки, второй – вторым и т. д. Нетрудно видеть, что первый элемент можно вы брать n способами. Второй элемент будет выбираться из (n 1) оставшихся элементов, по этомуего можно выбрать (n 1) способом. Продолжая выбор, заметим, что после выбора первых k элементов останется (n k) невыбранных элементов. Следовательно, (k + 1)-й эле мент можно выбрать (n k) способами. Перемножив числа способов, которыми можно вы брать первый, второй,..., (n 1)-й и n-й элементы, получим величину, равную числу спосо бов, которыми можно упорядочить n-элементное множество. Таким образом, Pn = n · (n 1) ·... · 2 · 1 = n! (3.1) Размещением из n элементов по k называется произвольная перестановка k элементного подмножества n-элементного множества. Для обозначения числа размещений из nэлементов по k используется символ Akn. Рассуждениями аналогичными приведенным выше при определении величины Pn, нетрудно показать, что Akn = n(n 1) ·... · (n k + 1) = n! / (n k)!. (3.2) Сочетанием из n элементов по k называется произвольное k-элементное подмножество n n элементного множества. Число сочетаний из n элементов по k обозначается через k k (иногда также используется символ C n. Так как у одного k-элементного подмножества су ществует ровно k! различных перестановок, то из (1.2) легко следует, что n n(n 1)... (n k + 1) n!

= k (n k )!k! =. (3.3) k (k 1)... 2 Из равенства (1.3) легко вытекают следующие часто используемые свойства сочетаний:

n n 1 n n n = k n k, k = k 1 + k. (3.4) Второе из этих равенств докажем также при помощи комбинаторных рассуждений.

Пусть A – множество всех k-элементных подмножеств множества {1, 2,..., n}. Это множество разобъем на два класса A1 и A2 так, что в первый класс отнесем все подмножества, содержа щие n, а во второй класс – подмножества без этого элемента. Нетрудно видеть, что A1 состо n n подмножеств, а A2 – из ит из k. Так как каждое k-элементное подмножество по k 1 падает либо в класс A1, либо в класс A2, то |A| = |A1| + |A2|, и, следовательно, n n 1 n k k + k 1.

= Сочетанием с повторениями из n элементов по k называется неупорядоченная k выборка n-элементного множества. Например, из трех элементов a1, a2 и a3 можно составить шесть сочетаний с повторениями по два элемента:

a1a1, a1a2, a1a3, a2a2, a2a3, a3a3.

Каждое сочетание с повторениями из n элементов по k однозначно определяется тем, сколько раз каждый элемент множества входит в рассматриваемое сочетание. Пусть в неко торое такое сочетание элемент ai входит mi раз, где i = 1, 2,..., n. Этому сочетанию поставим в соответствие набор 1...101...10......01...1 (3.5) {{ { m1 m2 mn из k единиц, сгруппированных в n блоков, и n 1 нулей, разделяющих эти блоки. В этом на боре первый блок из m1 единиц соответствует элементу 1, второй блок из m2 единиц — эле менту a2, и т. д. Приведенным выше двухэлементным сочетаниям соответствуют следующие шесть наборов:

1100, 1010, 1001, 0110, 0101, 0011.

Очевидно, что набор вида (1.5) однозначно определяет соответствующее ему сочетание с повторениями. Поэтому число Hk n сочетаний с повторениями из n элементов по k равно числу наборов из k единиц и n 1 нулей.

Каждый такой набор можно рассматривать как набор значений характеристической функции k-элементного подмножества (n + k 1)-элементного множества. Следовательно, n + k 1 (n + k 1)!

Hn = k = (n 1)!k!.

k Б. Бином Ньютона Числа сочетаний и сочетаний с повторениями появляются в известной формуле бинома Ньютона y ( y 1)...( y k + 1) k (1 + x) y = 1 + x (3.6) k!

k = в случаях, когда y принимает целые положительные и целые отрицательные значения, соот ветственно. Поэтому эти числа называются также биномиальными коэффициентами. Пока жем, что их появление в (3.6) не случайно. Для этого установим справедливость формулы бинома Ньютона при целых значениях y при помощи комбинаторных рассуждений.

Если показатель степени бинома – целое неотрицательное число, то равенство (3.6) за писывается в виде n n (1 + x) n = x k. (3.7) k =0 k Справедливость равенства (3.7) следует из того, что после раскрытия скобок в выраже нии (1 + x)n коэффициент при k-й степени переменной x будет равен числу способов, кото рыми можно выбрать k раз переменную x из n двучленов (1 + x).

Если показатель степени бинома – целое отрицательное число, то после изменения зна ка перед переменной x равенство (3.6) превращается в равенство n + k 1 k (1 x) n = k x, (3.8) k = которое справедливо при |x| 1. Для доказательства (1.8) воспользуемся хорошо известным частным случаем формулы (3.8) – формулой суммы убывающей геометрической прогрессии (1 x) 1 = x k. Тогда k = n (1 x) = (1 + x + x 2 +...)(1 + x + x 2 +...)...(1 + x + x 2 +...). (3.9) 144444444 44444444 2 n раз Нетрудно видеть, что после раскрытия скобок в правой части (3.9) коэффициент при k й степени переменной x будет равен числу способов, которыми можно выбрать n степеней переменной x из n рядов 1 + x + x2 +... так, чтобы сумма этих степеней была равна k. Рас сматривая выбор xp из q-го ряда 1 + x + x2 +... в (3.9) как выбор p элементов q-го вида из n возможных видов, заключаем, что коэффициент при xk равен числу сочетаний с повторения n + k k.

ми их n элементов по k, т.е. Рассмотрим несколько примеров использования формулы бинома Ньютона. Подстав ляя в (1.7) вместо x единицу и минус единицу по лучим тождества n n n n k = 2n, (1) k = 0.

k k =0 k = Вычисляя сумму и разность этих тождеств и деля результаты пополам, получаем, что n n [ n / 2] [ n / 2] 2k = 2n 1, n 2k + 1 = 2.

k =0 k = Дифференцирование (3.7) с подстановкой единицы вместо x и интегрирование (3.7) по x от нуля до единицы дают следующие тождества n 1 n 2n n n k k = n2n 1, k + 1 k = n + 1.

k =0 k = Раскроем скобки в равенстве (1 + x)n(1 + x)m = (1+x)n+m. Так как коэффициенты при xp в правой и левой частях равны, то из (1.7) и правила умножения многочленов следует равенст во n m n + m p k p k = p, (3.10) k = называемое сверткой Вандермонда. Следующее тождество n + k n + m m n = n +1 (3.11) k = нетрудно доказать индукцией по m. Действительно, при m = 1 рассматриваемое тождество n n + n n + 1. Предположим, что оно верно при m 1. Тогда тривиально: = n + k n + m 1 n + m 1 n + m 1 n + m n + k m 1 m n = n + n = n + 1 + n = n + 1. k = k = Тождество (3.11) доказано.

Далее будем использовать обозначения n!! для произведения всех тех натуральных чи сел, которые не превосходят n и имеют такую же четность как и n, т. е.

2n!! = 2n(2n 2) ·... · 2, (2n + 1)!! = (2n + 1)(2n 1) ·... · 1.

Рассмотрим пример использования формулы (3.6) с нецелым показателем степени. Раз ложим в ряд функцию ( 1 4 x ) 1. Нетрудно видеть, что 1 1 1 1... k + 1 2 2 2 (4) k x k = =1+ 1 4x k!

k = 1 3 2k... 2k (2k 1)!! k 2 2 =1+ (4) k x k = 1 + x= k! k!

k =1 k = 2k k 2k k!(2k 1)!! k (2k )!!(2k 1)!! k (2k )! k =1+ x =1+ x = 1+ x = x.

k k !k ! k!k ! k !k! k =1 k =1 k =1 k = Поэтому k 2k 2m 2m k 2k = xk = x.

1 4 x k =0 k k =0 m=0 k m m разложение (1 4 x) 1 = m = 0 4 k x k, приходим к тождеству Таким образом, учитывая 2k 2m 2m k k m m = 4.

k m=0 Использование равенства (3.6) является сильным средством получения различных со отношений с биномиальными коэффициентами. Однако в ряде случаев более действенными оказываются методы, использующие комбинаторную природу биномиальных коэффициен тов. В качестве примера таких методов рассмотрим комбинаторные доказательства тождеств (3.10) и (3.11). Сначала докажем равенство (3.10):

n m n + m p k p k = p.

k =0 Для этого множество всех p-элементных подмножеств (n + m)-элементного множества A = {1, 2,..., n + m} разобъем на p классов A1,..., Ap так, что класс Ak будет состоять из всех тех подмножеств множества A, в которые входит ровно k чисел, каждое из которых не пре n восходит n, и p k чисел, каждое из которых больше n. Первые k чисел можно выбрать k m способами, а оставшиеся p k чисел – p k способами (если k n или p k m, то тако n m го подмножества не существует и, соответственно, = 0 или p k = 0). Следовательно, k n m каждый класс Ak состоит из k p k подмножеств. Наконец заметим, что каждое p элементное подмножество множества A принадлежит одному из классов Ak, т.е.

| A |= k = 0 | Ak |. Тождество (3.10) доказано.

p Теперь приведем комбинаторное доказательство тождества (3.11):

n + k n + m m n = n + 1.

k =0 Множество всех (n + 1)-элементных подмножеств (n + m)-элементного множества {1, 2,..., n + m} разобъем на m классов A1,...,Am так, что в j-й класс Aj попадут все те подмножест n + m j ва, у которых минимальный элемент равен j. Нетрудно видеть, что Aj состоит из n подмножеств. Поэтому, полагая k = m j, имеем n + m m n + m n + m n + k j 1 j m m = | A j |= = = n.

n +1 n n j =1 j =m j =1 j = 2.1.4. Теория графов 2.1.4.1. Граф и его разновидности Простым графом (кратко – графом) G называется пара множеств: непустое конечное множество V и множество E V V неупорядоченных пар элементов из множества V G = (V, E ), V, E V V, E = E (то есть E симметричное отношение на V).

Множество V называется множеством вершин, а множество E – множеством ребер.

Число вершин графа называется его порядком и обозначается |V|. Обычно граф изображают диаграммой: вершины – точками, ребра – линиями.

Если вершины 1, 2 соединены ребром = 1, 2, то говорят, что вершины 1, смежные, а ребро инцидентно вершинам 1, 2. Множество всех вершин графа G смеж ных с некоторой вершиной, называется окружением вершины и обозначается через U ( ). Два ребра называются смежными, если они имеют общую вершину. На рис. 4.1 изо бражен граф с четырьмя вершинами и пятью ребрами. Вершины 1, 2 ;

1, 3 ;

2, 4 ;

2, 3 смежные;

вершины 1,4 не смежные, ребра 1, 2, смежные;

1, 3 не смежные.

Рис. 4.1. Граф с четырьмя вершинами и пятью ребрами Часто рассматриваются следующие разновидности графов.

1. Если E – множество упорядоченных пар элементов из V, то граф G = (V, E ) называ ется ориентированным графом (орграфом). В этом случае элементы множества E называ ются дугами. При этом дуга 1, 2 E называется исходящей из вершины 1 и заходящей в 2. На диаграмме графа дуга изображается линией со стрелкой из вершины 1 в вершину вершину 2.

2. Если в графе (в орграфе) хотя бы одна пара вершин соединена более чем одной дугой (ребром), то такой граф (орграф) называется мультиграфом (рис. 4.2), а ребра (дуги) назы ваются кратными.

3. Если, кроме того, элементами множества E могут быть пары,, V, то они называются петлями, а граф G называется графом с петлями или псевдографом. Обычно петля считается неориентированной. На рис. 4.3 3, 3 – петля.

Рис. 4.2. Рис. 4.3.

4. Граф G = (V, E ) называется подграфом графа G = (V, E ) (обозначается G G ), если V V и E E.

5. Если множество вершин подграфа G есть V, а множество его ребер совпадает с множеством всех ребер графа G, оба конца которых принадлежат V, то G называется под графом, порожденным множеством V, и обозначается через G (V ).

2.1.4.2. Морфизмы графов Пусть G1 = (V1, E1 ) и G2 = (V2, E2 ) – графы. Отображение (функция) f : V1 V2 назы 1, 2 E1 следует вается гомоморфизмом, если для любых вершин 1, 2 V из условия f (1 ), f (2 ) E2.

Два графа G1 = (V1, E1 ) и G2 = (V2, E2 ) называются изоморфными (обозначается G1 G2 ), если существует биекция f : V1 V2, сохраняющая смежность вершин:

1, 2 E1 f (1 ), f (2 ) E2.

Изоморфизм графа G = (V, E ) на себя называется автоморфизмом.

Пример 4.1. Рассмотрим граф G1 = (V1, E1 ) рис. 4.4 (a), состоящий из множества вер V1 = {1, 2, 3, 4} шин и множества дуг и ребер (смешанный граф) E1 = { 1, 2, 2, 1, 3, 4, 4, 3, 1, 3, 2, 4, 3, 2, 4, 1 }. G2 = ({a, b, c} ;

Граф { a, b }), b, a, b, c, c, b, a, c, b, b (рис. 4.4 (б)) является гомеоморфным обра (1) = a, G1 = (V1, E1 ), зом графа при гомоморфизме в котором ( 2 ) = b, ( 3) = c, ( 4 ) = b. Граф G3, изображенный на рис. 4.4 (в), изоморфен графу G1 = (V1, E1 ). Изоморфизм задается так: (1) = a, ( 2 ) = b, ( 3) = c, ( 4 ) = d. Ото бражение : {1, 2, 3, 4} {1, 2, 3, 4}, при котором (1) = 2, ( 2 ) = 1, ( 3) = 4, ( 4 ) = 3, является автоморфизмом графа G1 = (V1, E1 ).

Пример 4.2. Следующие три внешне различные диаграммы на рис. 4.5 являются диа граммами одного и того же графа K33.

1 u1 w1, 2 u3 w 3, Изоморфизм задается следующим образом:

3 u5 w 6, 4 u6 w 2, 5 u4 w 4, 6 u2 w 5.

Рис. 4.4. Смешанный граф Рис. 4.5. Внешние диаграммы одного из графов Числовые характеристики графа, одинаковые для всех изоморфных графов, называются инвариантами графа. Например, число вершин и ребер (дуг) является инвариантами графа.

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

Рис. 4.6. Неизоморфные графы Отношение изоморфизма графов является отношением эквивалентности. Следователь но, множество всех графов разбивается на классы эквивалентности, так что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфны. Изоморфные графы естественно отождествлять и их можно изображать одинаковым рисунком.

В некоторых ситуациях все же приходится различать изоморфные графы, и тогда по лезно понятие «помеченный граф». Граф порядка n называется помеченным, если его верши нам присвоены некоторые метки, например номера 1, 2, K, n. Отождествив каждую из вершин графа с ее номером (и, следовательно, множество вершин – с множеством чисел 1, 2, K, n ), определим равенство помеченных графов G и H одного и того же порядка:

G = H тогда, когда EG = EH. На рис. 4.7 изображены три разных помеченных графа.

Рис. 4.7. Примеры помеченных графов 2.1.4.3. Степени вершин Число ребер, инцидентных вершине, называется степенью вершины и обозначает ся deg или d ( ). Последовательность {d1, d 2,K, d n } степеней вершин графа называется степенной последовательностью. На рис. 4.8 приведена диаграмма графа K 4, степень каж дой вершины которого равна трем.

Если степень вершины равна нулю, то такая вершина графа называется изолированной.

Если степень вершины равна единице, то вершина графа называется висячей. Для графа, изо браженного на рис. 4.9: d (1) = d ( 2 ) = 2, d ( 3) = 3, вершина 5 – висячая, вершина 4 – изоли рованная.

Рис. 4.8. Рис. 4.9.

Для ориентированного графа число дуг, исходящих из вершины, называется полу степенью исхода и обозначается через d ( ), а число дуг, входящих в вершину, – полу степенью захода и обозначается d + ( ).

Теорема 4.1. Пусть G – мультиграф с n вершинами и m ребрами, di = d (i ) – степень i, тогда n di = 2m : сумма степеней вершин графа равна удвоенному коли i-й вершины i = честву ребер.

Доказательство. Пересчитаем число ребер в каждой вершине и сложим эти числа. То гда каждое ребро будет подсчитано два раза. Поэтому общее число ребер мультиграфа равно 1n половине этой суммы m = i =1 di.

Этот результат, известный еще более двухсот лет назад Эйлеру, часто называют леммой о рукопожатиях. Из нее следует, что если несколько человек обменялись рукопожатиями, то общее число рукопожатий обязательно четно, так как в каждом рукопожатии участвуют две руки (при этом каждая рука считается столько раз, сколько она участвует в рукопожатиях).

Следствие 4.1. В каждом мультиграфе число вершин нечетной степени четно.

Действительно, пусть 1, 2, K, p – вершины с нечетной степенью, а p +1, p + 2,K, n – вершины с четной степенью. Тогда число p n n n di = di d di = 2ki + 1, i = 1, 2,K, p, – четное. Так как то d i = 2m i i =1 i =1 i = p +1 i = p + ( ) p p 2ki + p – четное число. Следовательно, число p вершин нечетной степени – d= i =1 i i = четно.

2.1.4.4. Маршруты, цепи, циклы, связность Маршрутом в графе G = (V, E ) называется чередующаяся последовательность вершин и ребер {1, 1, 2, 2, K, n 1, n }, в которой любые два соседних элемента инцидентны.

Число ребер в маршруте (с повторениями) называется длиной маршрута. Это определение подходит также для псевдо-, мульти- и орграфов. Для «обычного» графа достаточно указать только последовательность вершин или только последовательность ребер.

• Маршрут называется цепью, если все его ребра различные. Цепь, соединяющая вер шины u и, обозначается [u, ], и тогда вершина называется достижимой из вершины u.

• Маршрут называется замкнутым, если 1 = n.

• Замкнутая цепь называется циклом.

• Цепь называется простой, если все вершины (а значит, и ребра) различны.

• Простая замкнутая цепь называется простым циклом.

• Наименьшая длина цикла в графе называется обхватом.

• Граф без циклов называется ациклическим.

• Для ориентированных графов цепь называется путем, а цикл – контуром.

Пример 4.3. Рассмотрим граф, изображенный на рис. 4.10. В нем {1, 3, 1, 4 } – мар шрут длины 3, но не цепь;

{1, 3, 5, 2, 3, 4 } – цепь (все ребра различные), но не простая {1, 4, 3, 2, 5} цепь (вершина встречается дважды);

– простая цепь;

{1, 3, 5, 2, 3, 4, 1} 3 встречается дважды);

– цикл, но не простой (вершина {1, 3, 4, 1} – простой цикл.

Теорема 4.2. Пусть в графе G = (V, E ) степень каждой вершины не меньше 2. Тогда граф G содержит цикл.

1 – произвольная вершина из V. Построим последователь Доказательство. Пусть ность ребер 1, 2, 2, 3, K, выбирая 2 смежной с 1 и отличной от 1 ;

3 смежной с 2 и отличной от 2 и т. д. По условию теоремы на каждом шаге очередная вершина су ществует. В силу конечности множества вершин V в последовательности 1, 2, 3,K встретится вершина k, которая встречалась раньше. Выбирая k минимальным с этим свой ством, получим цикл.

Рис. 4.10. Рис. 4.11.

существует со Граф G называется связным, если для любых двух его вершин u и единяющая их простая цепь [u, ].

Отношение связности на множестве вершин является отношением эквивалентности.

Рефлексивность следует из того факта, что каждая вершина связана сама с собой тривиаль ной цепью. Симметричность следует из того, что, взяв вершины цепи [u, ] в обратном по рядке, получим цепь из в u. Транзитивность также очевидна: объединив цепи из u в и из в w, получим цепь из u в w. Классы эквивалентности по отношению связности называ ются компонентами связности графа. Число компонент связности графа G обозначается k ( G ). Граф G является связным тогда и только тогда, когда k ( G ) = 1. Если k ( G ) 1, то G – несвязный граф. Граф, состоящий только из изолированных вершин, называется вполне не связным. Очевидно, что всякий несвязный граф G можно представить в виде объединения связных графов (компонент связности). На рис. 4.11 изображен граф с четырьмя компонен тами связности. Ребро графа, после удаления которого увеличивается число компонент связ ности, называется мостом. На рис. 4.12 слева ребро 1, 4 – мост.

2.1.4.5. Представления графов В большинстве случаев граф в памяти компьютера задается матрицей. Существуют различные виды матриц, ассоциированные с графами. Выбор наилучшего представления оп ределяется требованиями конкретной задачи. Ниже приведены несколько наиболее часто ис пользуемых представлений с указанием динамической меры сложности алгоритма N ( n, m ) – объема памяти для каждого представления. Здесь п – число вершин, т – число ребер графа.

Эти представления пригодны и для ориентированных графов, а также после некоторой мо дификации и для псевдографов. Представления иллюстрируются на примерах графа G и орг рафа Г, диаграммы которых представлены на рис. 4.11 и 4.12.

Рис. 4.11. Граф G Рис. 4.12. Граф Г 1. Матрица смежности вершин графа: матрица A = ai j с элементами 1, если вершина i смежна с вершиной j ;

ai j = 0, если вершины i и j несмежные.

Для мультиграфа ai j = (число ребер, соединяющих вершины i и j ).

Пример 4.4. Матрицы смежности вершин графа G и орграфа Г имеют вид:

0 1 0 1 0 1 0 1 0 1 1, A = 0 0 1 1.

AG = 0 1 0 1 0 0 0 Г 1 1 1 0 1 0 1 () Для матрицы смежности N = O n 2.

Теорема 4.3. Два графа изоморфны тогда и только тогда, когда их матрицы смежности вершин получаются друг из друга одновременными перестановками строк и столбцов (т. е.

одновременно с перестановкой i-ой и j-ой строк переставляются в i-ый и j-ый столбцы).

Доказательство. Пусть два графа G1 и G2 порядка n изоморфны. Тогда существует биекция, заданная на множестве {1, 2,K, n} вершин графа G1 и сохраняющая смежность () () вершин. Если A = ai j – матрица смежности графа G1, а B = bi j – матрица смежности графа G2, то, очевидно, в силу изоморфизма, b (i ), ( j ) = ai j, i = 1, 2,K, n, j = 1, 2,K, n.

() () матрица ai j Следовательно, из матрицы bi j получается перестановкой строк и nn nn столбцов согласно соответствию :

1 n 2 K 1 2 K n.

() () ( ) В силу симметричности отношения изоморфизма, аналогично из матрицы ( ai j ) мо nn жет быть получена матрица ( bi j ). Обратно, если в результате динаковой перестановки nn () получается матрица, равная матрице ( bi j ), то указана строк и столбцов из матрицы ai j nn nn биекция, сохраняющая смежность, т.е. изоморфизм графов G1 и G2.

Пример 4.5. Матрицы смежности вершин первого G1 и второго G2 графов, изображен ных на рис. 2.2, имеют вид:

0 0 0 1 1 1 0 1 0 1 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 1 0 1 0 1 0 AG1 =, AG2 =.

1 1 1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 0 1 Матрица AG1 получается из матрицы AG2 одновременной перестановкой второй и третьей, а затем третьей и пятой строк и столбцов. Следовательно, эти графы изоморфны.

( ) с элементами 2. Матрица инцидентности графа: матрица B = bi j 1, если вершина i инцидентна ребру j ;

bij = 0, если вершина i не инцидентна ребру j, строки, которой соответствуют вершинам, а столбцы – ребрам.

Понятно, что такая матрица имеет ровно по две единицы в каждом столбце (ведь всякое ребро имеет два конца – две инцидентные данному ребру вершины). Число единиц в каждой строке матрицы инцидентности равно степени соответствующей вершины. Мат рицы инцидентности изоморфных графов получаются друг из друга путём обычных (непар ных, в отличие от матрицы смежности и матрицы Кирхгофа) перестановок строчек и столбцов.

Для ориентированного графа 1, если ребро j выходит из вершины i ;

bij = 1, если ребро j входит в вершину i ;

0, если вершина i и ребро j не инцидентны.

Пример 4.6. Матрицы инцидентности графа G и орграфа Г имеют вид:

1 2 3 4 5 1 2 3 4 1 0 0 1 0 1 0 0 1 1 1 2 1 1 0 0 1, BГ = 2 1 1 0 0 1.

BG = 3 0 1 1 0 0 3 0 1 1 0 4 0 0 1 1 4 0 0 1 1 Динамическая мера сложности алгоритма для матрицы инцидентности N = O ( n m ).

Аналогично теореме 4.3 справедлива следующая теорема.

Теорема 4.4. Два графа (орграфа) изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга некоторыми перестановками строк и столбцов.

Рис. 4.13. Рис. 4.14.

Пример 4.7. Матрицы инцидентности графа G, изображенного на рис. 4.13, и графа Г (рис. 4.14) имеют вид:

1 2 3 4 5 1 0 1 1 0 1 AG = 2 1 1 0 0 1 0, 3 0 1 1 0 0 4 0 0 0 1 1 1 2 3 4 5 1 0 0 1 1 1 AГ = 2 1 1 0 0 0 1.

3 0 1 1 0 1 4 0 0 1 1 0 Матрица AG получается из матрицы AГ перестановкой 3-го и 5-го, а затем 5-го и 6-го столбцов. Следовательно, эти графы изоморфны.

3. Списки смежности вершин графа (орграфа). Ориентированный или неориентиро ванный граф может быть однозначно представлен списком смежности своих вершин. Для каждой вершины ее список смежности Ad [ ] (adjacency – смежность) состоит из вершин, смежных с ней. Списки смежности составляются для каждой вершины.

Для неориентированного графа N = O ( n + 2m ), для орграфа N = O ( n + m ).

Пример 4.8. Списки смежности вершин графа G и орграфа Г, изображенных на рис.

4.11 и рис. 4.12, имеют вид:

1 2 3 G:

{1, 3,4} {1, 2, 3 } {2, 4 } {2, 4 } 1 2 3 Г:

{3,4 } {1, 3 } {2 } 4. Массивы ребер (дуг). При описании графа списком его ребер каждое ребро представ ляется парой инцидентных ему вершин. Это представление реализовывается двумя массива ми: r = r1, r2, K, rm, t = t1, t2,..., tm, где т – число ребер. Каждый элемент в массиве яв ляется меткой вершины, а i-ое ребро выходит из вершины ri и входит в вершину ti.

Пример 4.9. Массивы ребер графа G и массивы дуг орграфа Г, изображенные на рис.

4.11. и рис. 4.12, имеют соответственно вид:

r 1 1 2 2 4 r 1 2 2 4,.

t 2 4 3 4 3 t 2 3 4 1 Для массива ребер (дуг) N = O ( 2m ).

5. Матрица весов графа: матрица W = ci j с элементами ci j, где ci j – вес ребра (ду ги), соединяющего вершину i с вершиной j. Веса несуществующих ребер (дуг) полагают равными 0 или в зависимости от приложений. Матрица весов графа является обобщением матрицы смежности.

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

2.1.5. Логика предикатов. Методы доказательств 2.1.5.1. Общие сведения и определения В алгебре логики высказывания рассматриваются как нераздельные целые и только с точки зрения их истинности или ложности.

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

Например, в рассуждении “Всякий ромб – параллелограм;

АВСD – ромб;

следовательно, АВСD – параллелограм” посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

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

Такой логической системой является логика предикатов, содержащая всю логику высказываний в качестве своей части.

Логика предикатов, как и традиционная формальная логика, расчленяет элементарное высказывание на субъект (буквально – подлежащее, хотя оно может играть и роль дополнения) и предикат (буквально – сказуемое, хотя оно может играть и роль определения).

Субъект – это то, о чем что-то утверждается в высказывании;

предикат – это то, что утверждается о субъекте.

Например, в высказывании «7 – простое число», «7» – субъект, «простое число» – предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом».

Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х – простое число».

При одних значения х (например, х = 13, х = 17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18) эта форма дает ложные высказывания.

Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1;

0}. Здесь предикат становится функцией субъекта и выражает свойство субъекта.

Дадим несколько определений, относящихся к предикатам.

Определение 5.1.

Одноместным предикатом Р(x) называется произвольная функция переменного x, определенная на множестве M и принимающая значение из множества {1;

0}.

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

Множество всех элементов x M, при которых предикат принимает значения “истина” (1), называется множеством (областью) истинности предиката Р(x), т.е. множество истинности предиката Р(х) – это множество I p = {x : x M, P( x) = 1}, или иначе: M [P ] или x так: M [P(x)]. Так, например, предикат Р(x) – “x – простое число” определен на множестве N, x а множество истинности IP для него есть множество всех простых чисел.

Предикат Q(x) – “sinx = 0” определен на множестве R, а его множеством истинности является I Q = {k, k Z }.

Предикат F(x) – “диагонали параллелограма x взаимно перпендикулярны” определен на множестве всех параллелограмов, а его множеством истинности является множество всех ромбов.

Из приведенных примеров видим, что одноместные предикаты выражают свойства предметов (субъектов).

Определение 5.2.

Предикат Р(х), определенный на множестве М, называется тождественно истинным, если его множество истинности совпадает с областью определения, т. е. Ip = M.

Определение 5.3.

Предикат Р(х), определенный на множестве М, называется тождественно ложным, если его множество истинности является пустым множеством, т. е. Ip = 0.

Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью которого выражаются отношения между предметами.

Примером бинарного отношения, т. е. отношения между двумя предметами, является отношение “меньше”. Пусть это отношение введено на множестве Z целых чисел. Оно может быть охарактеризовано высказывательной формой “х y”, где x, y Z, то-есть является функцией двух переменных Р(х, y), определенной на множестве упорядоченных пар целых чисел Z х Z = Z2 c множеством значений {1;

0}.

Определение 5.4.

Двухместным предикатом Р(x, y) называется функция двух переменных x и y, определенная на множестве М = М1 х М2 и принимающая значения из множества {1;

0}.

В числе примеров двухместных предикатов можно назвать такие предикаты: Q(x, y) – “x = y” – предикат равенства, определенный на множестве R х R = R2;

F(x, y) – “х параллелен y”, “прямая х параллельна прямой y”, определенный на множестве прямых, лежащих на данной плоскости.

Совершенно аналогично вводится понятие трехместного предиката. Приведем пример трехместного предиката (функции трех переменных): S(x, y, z) – “x + y = z”. Подстановка в него х = 3 превращает его в двухместный предикат: S(y, z) – “3 + y = z”, а подстановка х = 3, z = 2 – в одноместный предикат S(y) – “3 + y = 2”.Подстановка же S(2, 3, 5) превращает его в истинное высказывание, а S(1, 7, 4) – в ложное.

Аналогично определяется и n-местный предикат (функция n переменных). Пример п местного предиката:

R(x1, x2,…, xn): a1 x1 +…+ anxn = 0, который, как видим, представляет собой алгебраическое уравнение с n неизвестными.

При n = 0 будем иметь нульместный предикат – это логическая (пропозициональная) переменная, принимающая значения из множества {1;

0}.

2.1.5.2. Логические операции над предикатами Предикаты так же, как высказывания, могут принимать два значения: “истина” (1) и “ложь” (0), поэтому к ним применимы все операции логики высказываний, в результате чего из элементарных предикатов формируются сложные предикаты (как и в логике высказываний, где из элементарных высказываний формировались сложные, составные).

Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов сохраняют тот же смысл, который был им присвоен в логике высказываний.

Пусть на некотором множестве M определены два предиката P(x) и Q(x).

Определение 5.5.

Конъюнкцией двух предикатов P(x) и Q(x) называется новый (сложный) предикат P ( x) Q( x), который принимает значение “истина” при тех и только тех значениях x M, при которых каждый из предикатов принимает значение “истина”, и принимает значение “ложь” во всех остальных случаях.

Очевидно, что областью истинности предиката P ( x) Q( x) является общая часть области истинности предикатов P(x) и Q(x), т.е. пересечение I P I Q.

Так, например, для предикатов P(x): “x – четное число” и Q(x): “x кратно 3” конъюнкцией P ( x) Q( x) является предикат “x – четное число и x кратно трем”, т.е.

предикат “x делится на 6”.

Определение 5.6.

Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат P( x) Q( x), который принимает значение “ложь” при тех и только тех значениях x M, при которых каждый из предикатов принимает значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Ясно, что областью истинности предиката P( x) Q( x) является объединение области истинности предикатов P(x) и Q(x), т.е. I P I Q.

Определение 5.7.

Отрицанием предиката P(x) называется новый предикат P(x) или P(x), который принимает значение “истина” при всех значениях x M, при которых предикат P(x) принимает значение “ложь”, и принимает значение “ложь” при тех значениях x M, при которых предикат P(x) принимает значение “истина”.

I P = I P, т.е. множество истинности предиката Очевидно, что P(x) является дополнением к множеству IP.

Определение 5.8.

Импликацией предикатов P(x) и Q(x) называется новый предикат P( x) Q( x), который является ложным при тех и только тех значениях x M, при которых одновременно P(x) принимает значение “истина”, а Q(x) – значение “ложь”, и принимает значение “истина” во всех остальных случаях.

xM Поскольку при каждом фиксированном справедлива равносильность P( x) Q( x) P( x) Q( x), то I P Q = I P I Q.

Определение 5.9.

Эквиваленцией предикатов P(x) и Q(x) называется новый предикат P( x) Q( x), который обращается в “истину” при всех тех и только тех x M, при которых P(x) и Q(x) обращаются оба в истинные или оба в ложные высказывания.

Для его множества истинности имеем: I P Q = I P I Q I P I Q 2.1.5.3. Кванторные операции Рассмотрим операции, преобразующие предикаты в высказывания.

Пусть имеется предикат Р(х) определенный на множестве М. Если “а” – некоторый элемент из множества М, то подстановка его вместо х в предикат Р(х) превращает этот предикат в высказывание Р(а). Такое высказывание называют единичным. Например, r(x): “х – четное число” – предикат, а r (6) – истинное высказывание, r (3) – ложное высказывание.

Это же относится и к n – местным предикатам: если вместо всех предметных переменных хi, i = 1, n подставить их значения, то получим высказывание.

Наряду с образованием из предикатов высказываний в результате таких подстановок в логике предикатов рассматриваются еще две операции, которые превращают одноместный предикат в высказывание. Эти операции называются операциями квантификации (или просто квантификацией, или связыванием кванторами, или навешиванием кванторов). При этом рассматриваются, соответственно, два типа так называемых кванторов.

А. Квантор всеобщности.

Пусть Р(х) – предикат, определенный на множестве М. Под выражением xP(x) понимают высказывание, истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение звучит так: “Для всякого х Р(х) истинно ”.

Символ называют квантором всеобщности (общности). Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), в высказывании же xP(x) х называют связанной квантором всеобщности.

Б. Квантор существования.

Пусть P(x) – предикат определенный на множестве М. Под выражением xP(x) понимают высказывание, которое является истинным, если существует элемент x M, для которого P(x) истинно, и ложным – в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение звучит так: “Существует x, при котором P(x) истинно.” Символ называют квантором существования. В высказывании xP(x) переменная x связана этим квантором (на нее навешен квантор).

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


yxP( x, y ), yxP( x, y ), yxP( x, y ), yxP( x, y ).

Рассмотрим предикат P(x) определенный на множестве M = {a1,…, an}, содержащем конечное число элементов. Если предикат P(x) является тождественно – истинным, то истинными будут высказывания P(a1), P(a2),…, P(an). При этом истинными будут высказывания xP(x) и конъюнкция P (a1 ) P(a 2 )... P(a n ).

Если же хотя бы для одного элемента a k M P(ak)окажется ложным, то ложными n xP(x) P(ai ). Следовательно, справедлива будут высказывание и конъюнкция i = n равносильность xP( x) P (a1 ) P(a 2 )... P (a n ) = P(a i ).

i = Численные кванторы.

В математике часто встречаются выражения вида “по меньшей мере n” (“хотя бы n”), “не более чем n”, “n и только n” (“ровно n”), где n – натуральное число.

Эти выражения, называемые численными кванторами, имеют чисто логический смысл;

они могут быть заменены равнозначными выражениями, не содержащими числительных и состоящими только из логических терминов и знака или ~, означающего тождество (совпадение) объектов.

Пусть n = 1. Предложение “По меньшей мере один объект обладает свойством P” имеет тот же смысл, что и предложение “Существует объект, обладающий свойством P”, т.е.

x( P( x)). (*) Предложение “не более чем один объект обладает свойством P” равнозначно предложению “Если есть объекты, обладающие свойством P, то они совпадают”, т.е.

xy ( P( x) P( y ) x y ). (**) Предложение “один и только один объект обладает свойством P” равнозначно конъюнкции вышеуказанных предложений (*) и (**).

Отрицание предложений с кванторами.

Известно, что часто для отрицания некоторого предложения достаточно предпослать сказуемому этого предложения отрицательную частицу “не”. Например, отрицанием пред ложения “Река х впадает в Черное море” является предложение “Река х не впадает в Черное море”. Годится ли этот прием для построения отрицаний предложений с кванторами? Рас смотрим пример.

Предложения “Все птицы летают” и “Все птицы не летают” не являются отрицаниями друг друга, т. к. они оба ложны. Предложения “Некоторые птицы летают” и “Некоторые птицы не летают” не являются отрицанием друг друга, т. к. они оба истинны. Таким образом, предложения, полученные добавлением частицы “не” к сказуемому предложений “Все х суть Р” и “Некоторые х суть Р” не являются отрицаниями этих предложений. Универсаль ным способом построения отрицания данного предложения является добавление словосоче тания “наверно, что” в начале предложения. Таким образом, отрицанием предложения “Все птицы летают” является предложение “Неверно, что все птицы летают”;

но это предложение имеет тот же смысл, что и предложение “Некоторые птицы не летают”. Отрицанием предло жения “Некоторые птицы летают” является предложение “Неверно, что некоторые птицы летают”, которое имеет тот же смысл, что и предложение “Все птицы не летают”.

Условимся отрицание предложения x( P( x)) записывать как x( P( x)), а отрицание предложения x( P( x)) – как x( P ( x)). Очевидно, что предложение x( P( x)) имеет тот же смысл, а следовательно, то же значение истинности, что и предложение x( P( x)), а предло жение x( P ( x)) – тот же смысл, что x( P( x)). Иначе говоря, x( P( x)) равносильно x( P( x)) ;

x( P ( x)) равносильно x( P( x)).

Кванторы общности и существования называют двойственными относительно друг друга. Выясним теперь, как строить отрицание предложения, начинающегося с нескольких кванторов, например, такого: xyz ( P( x, y, z )).

Последовательно применяя сформулированное выше правило, получим:

xyz ( P ( x, y, z )) равносильно x(yz ( P( x, y, z )), что равносильно xy (z ( P( x, y, z ))), что равносильно xyz ( P( x, y, z )).

2.1.5.4. Понятие формулы логики предикатов В логике предикатов будем пользоваться следующей символикой:

1. Символы p, q, r, … – переменные высказывания, принимающие два значения: 1 – истина, 0 – ложь.

2. Предметные переменные – x, y, z, …, которые пробегают значения из некоторого множества М;

x0, y0, z0 – предметные константы, т. е. значения предметных переменных.

3. P(·), Q(·), F(·), … – одноместные предикатные переменные;

Q(·,·,…,·), R(·,·, …,·) – n-местные предикатные переменные.

P0(·), Q0(·,·, …,·) – символы постоянных предикатов.

Символы логических операций:,,,.

4.

Символы кванторных операций: x, x.

5.

6. Вспомогательные символы: скобки, запятые.

Определение формулы логики предикатов.

1. Каждое высказывание как переменное, так и постоянное, является формулой (элементарной).

2. Если F(·,·, …,·) – n-местная предикатная переменная или постоянный предикат, а x1, x2,…, xn – предметные переменные или предметные постоянные (не обязательно все различные), то F(x1, x2,…, xn) есть формула. Такая формула называется элементарной, в ней предметные переменные являются свободными, не связанными кванторами.

3. Если А и В – формулы, причем, такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой – свободной, то слова A B, A B, A B есть формулы. В этих формулах те переменные, которые в исходных формулах были свободны, являются свободными, а те, которые были связанными, являются связанными.

4. Если А – формула, то A – формула, и характер предметных переменных при переходе от формулы А к формуле A не меняется.

5. Если А(х) – формула, в которую предметная переменная х входит свободно, то слова xA(x) и xA(x) являются формулами, причем, предметная переменная входит в них связанно.

6. Всякое слово, отличное от тех, которые названы формулами в пунктах 1 – 5, не является формулой.

Например, если Р(х) и Q(x, y) – одноместный и двухместный предикаты, а q, r – переменные высказывания, то формулами будут, например, слова (выражения):

q, P ( x), P ( x) Q( x 0, y ), xP( x) xQ( x, y ), (Q( x, y ) q) r.

Не является формулой, например, слово: xQ( x, y ) P( x). Здесь нарушено условие п.3, так как формулу xQ( x, y ) переменная х входит связанно, а в формулу Р(х) переменная х входит свободно.

Из определения формулы логики предикатов ясно, что всякая формула алгебры высказываний является формулой логики предикатов.

2.1.5.5. Значение формулы логики предикатов О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество M, на котором определены входящие в эту формулу предикаты.

Логическое значение формулы логики предикатов зависит от значений трех видов переменных: 1) значений входящих в формулу переменных высказываний, 2) значений свободных предметных переменных из множества М, 3) значений предикатных переменных.

При конкретных значениях каждого из трех видов переменных формула логики предикатов становится высказыванием, имеющим истинное или ложное значение.

В качестве примера рассмотрим формулу yz ( P( x, y ) P( y, z )), (1) в которой двухместный предикат Р(x, y) определен на множестве M х M, где M = {0, 1, 2,…, n,…}, т.е.

M х M = N х N.

В формулу (1) входит переменный предикат P(x, y), предметные переменные x, y, z, две из которых y и z – связанные кванторами, а x – свободная.

Возьмем за конкретное значение предиката P(x, y) фиксированный предикат P0(x, y): “x y”, а свободной переменной х придадим значение x 0 = 5 M. Тогда при значениях y, меньших x0 = 5, предикат P0(x0, y) принимает значение “ложь”, а импликация P ( x, y ) P( y, z ) при всех z M принимает значение “истина”, т.е. высказывание yz ( P 0 ( x, y ) P 0 ( y, z )) имеет значение “истина”.

2.1.5.6. Равносильные формулы логики предикатов Определение 5.10.

Две формулы логики предикатов А и В называются равносильными на области М, если они принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесенных к области М.

Определение 5.11.

Две формулы логики предикатов А и В называются равносильными, если они равносильны на всякой области.

Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Рассмотрим основные из этих равносильностей.

Пусть А(х) и В(х) – переменные предикаты, а С – переменное высказывание (или формула, не содержащая х). Тогда имеют место равносильности:

1. xA( x) x A( x).

2. xA( x) x A( x).

3. xA( x) x A( x).

4. xA( x) x A( x).

5. xA( x) xB( x) x[ A( x) B ( x)] C xB( x) x[C B( x)].

6.

C xB( x) x[C B( x)] 7.

C xB( x) x[C B( x)] 8.

x[ B ( x) C ] xB( x) C.

9.

x[ A( x) B( x)] xA( x) xB( x).

10.

x[C B ( x)] C xB( x).

11.

x[C B( x)] C xB( x).

12.

xA( x) yB( y ) xy[ A( x) B( y )].

13.

x[C B( x)] C xB( x).

14.

x[ B( x) C ] xB( x) C.

15.

Равносильность 1 означает тот простой факт, что, если не для всех х истинно А(х), то существует х, при котором будет истиной A(x).

Равносильность 2 означает тот простой факт, что, если не существует х, при котором истинно А(х), то для всех х будет истиной A(x).

Равносильности 3 и 4 получаются из равносильностей 1 и 2, соответственно, если от обеих их частей взять отрицания и воспользоваться законом двойного отрицания.

ЗАКОНЫ ЛОГИЧЕСКИХ ОПЕРАЦИЙ.

(общезначимые формулы логики предикатов) P ( y ) xP( x) x[ P( y ) P( x)].

9.

xP( x) x P( x).

1.

C xP( x) x[C P( x)].

xP ( x) x P( x).

2.

C xP( x) x[C P( x)].

10.

xP( x) x P( x).

3.

C xP( x) x[C P( x)].

11.


xP( x) x P( x).

4.

C xP( x) x[C P( x)].

12.

5. x[ P( x) Q( x)] xP( x) xQ( x).

x[C P( x)] C xP( x).

13.

6. x[ P( x) Q( x)] xP( x) xQ( x).

x[C P( x)] C xP( x).

14.

xyP( x, y ) yxP( x, y ).

7.

15. xP( x) yQ( y ) xy[ P( x) Q( y )] xyP( x, y ) yxP( x, y ).

8.

x[ P( x) C ] xP( x) C.

16.

xyP( x, y ) yxP( x, y ).

xP( x) xQ( x) xP( x) yQ xP( x) xQ( x) x[ P( x) Q( x)]. 35.

x[ P( x) yQ( y )] xy[ P( x) x[ P( x) Q( x)] xP( x) xQ( x 31.

xP( x) xQ( x) xP( x) yQ( y ). 54.

x[ P( x) Q( x)] [xP( x) x x[ P( x) yQ( y )] xy[ P( x) Q( y )].

32.

.

xP( x) xP( x).

33.

x[ P( x) P( y )] xP( x) P( y ) 34.

.

x[ P( x) C ] xP( x) C.

2.1.5.7. Нормальные формы формул логики предикатов В логике предикатов, как и в логике высказываний, формулы могут иметь нормальную форму, т.е. существуют эквивалентные нормальные формы представления любых предикатных формул. При этом, используя равносильности алгебры высказываний и логики предикатов, каждую формулу логики предикатов можно привести к нормальной форме. В логике предикатов различают два вида нормальных форм: приведенную и предваренную.

Определение 5.12.

Говорят, что формула логики предикатов имеет приведенную нормальную форму, если она содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отрицания отнесена к элементарным формулам.

Пример 5.1.

1, 18 (xP( x) yQ( y )) R ( z ) xP( x) yQ( y ) R ( z ) xP( x) yQ( y ) R ( z ).

1, xP( x) yQ( y ) R ( z ) Получили приведенную нормальную форму исходной формулы.

Среди нормальных форм формул логики предикатов выделяют так называемую предваренную (префиксную, пренексную) нормальную форму (ПНФ). В ней кванторные операции либо полностью отсутствуют, либо они используются после всех операций алгебры логики, т.е. ПНФ формулы логике предикатов имеет вид ( x1 )( x 2 )...( xn ) A( x1, x 2,..., x m ), n m, где под символом xi понимается один из кванторов x i или x i, а формула А кванторов не содержит.

Процедура получения (приведения) ПНФ. Состоит в следующем:

1. Используя формулы 18, 19 (отнесенные к предикатам), заменить операции и ~ на,.

2. Используя формулы логики предикатов 31, 32, а также формулы логики высказываний 1, 16, 17, представить предикатную формулу таким образом, чтобы символы отрицания относились непосредственно к символам предикатов (и, таким образом, мы приводим исходную формулу к приведенной форме).

3. Для формул, содержащих подформулы вида xP( x) xQ( x), xP( x) xQ( x), вести новые переменные, позволяющие использовать соотношения 46, 47, 49, 50 или 53, 54.

4. С помощью формул 35 – 38, 46, 47, 49, 50, 53, 54 получить формулу в виде ПНФ.

Пример 5.2.

xyP ( x, y ) xyQ ( x, y ) xyP( x, y ) xyQ( x, y ) x[yP( x, y ) yQ ( x, y )] обозначим в предикате Q переменную y через z x[yP( x, y ) z Q( x, z )] xyz ( P( x, y ) Q( x, z )) Пример 5.3.

31, (xyP ( x, y ) xyQ( x, y )) xyP ( x, y ) xyQ ( x, y ) xy P ( x, y ) xyQ ( x, y ) обозначим в предикате Q переменную x через z 53 xy P( x, y ) zyQ( z, y )] xz (y P( x, y ) yQ( z, y )) xzy ( P( x, y ) Q( z, y )) – ПНФ.

Пример 5.4.

18 xy (z ( P( x, z ) Q( y, z )) uR ( x, y, u )) xy (z ( P( x, z ) Q( y, z )) uR ( x, y, u ) xy (z ( P( x, z ) Q( y, z ) uR ( x, y, u ) xy (z ( P( x, z ) Q( y, z )) uR ( x, y, u ) последний предикат не зависит от переменной z xyz ( P( x, z ) Q( y, z ) uR ( x, y, u )) два первых предиката не зависят от xyzu ( P( x, z ) Q( y, z ) R( x, y, u )) – ПНФ.

переменной u Пример 5.5.

18 (uP(u ) yuQ( y, u )) xR( x) (uP(u ) yuQ( y, u )) xR( x) 1 18 uP(u ) yuQ( y, u ) xR( x) uP(u ) yuQ( y, u ) xR( x) 16 1 uP(u ) yuQ( y, u ) xR( x) uP(u ) yuQ( y, u ) xR( x) 32 35 u P(u ) yuQ( y, u ) xR( x) u ( P(u ) yQ( y, u )) xR( x) 46 47 uy ( P(u ) Q( y, u )) xR( x) uyx( P(u ) Q( y, u ) R( x)) xyu ( P(u ) Q( y, u ) R( x)) ПНФ.

2.1.5.8. Общезначимость и выполнимость формул. Проблема разрешимости Определение 5.13.

Формула А логики предикатов называется выполнимой в области М, если существуют значения переменных входящих в эту формулу и отнесенных к области М (иначе – существует модель), при которых формула А принимает истинные значения.

Определение 5.14.

Формула А логики предикатов называется выполнимой, если существует область, на которой эта формула выполнима.

Определение 5.15.

Формула А логики предикатов называется тождественно-истинной в области М (выполнимой), если она принимает истинные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.

Определение 5.16.

Формула А логики предикатов называется общезначимой, если она тождественна истинна на всякой области (на любой модели).

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

Это понятие является обобщением понятия тождественной истинности формулы логики высказываний. Все логические законы, представленный в логике высказываний формулами (1 – 30) являются общезначимыми формулами логики предикатов и выражают, как и другие общезначимые формулы, законы логики на языке логике предикатов.

Наиболее употребительные специфические законы логики предикатов, как было отмечено выше, представлены формулами (31 – 54).

Общезначимость формулы логики предикатов, например, F обозначается –F. Все общезначимые формулы могут быть источниками новых – формул. Например, подставляя в (14) – закон исключенного третьего x x – вместо х предикат Р(х1,…, хn), получаем общезначимую формулу Р(х1,…, хn) P (х1,…, хn). При n = 1 имеем общезначимую формулу P ( x) P( x), и, таким образом, x[ P( x) P( x)] – общезначимая формула логики предикатов.

Из тождественно истинной формулы логики высказываний (2) x y y x подстановкой вместо х предиката Р(х, y), а вместо y – предиката Q(x, y) получаем общезначимую формулу P ( x, y ) Q( x, y ) Q( x, y ) P( x, y ) и т. д.

Определение 5.17.

Формула А логики предикатов называется тождественно ложной в области М, если она принимает ложные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области (иными словами, на данной модели).

Определение 5.18.

Формула А логики предикатов называется тождественно ложной (невыполнимой), если она тождественно ложна на всякой области (на всякой модели).

Например, формула x[ P( x) P( x)] является тождественно ложной (невыполнимой) формулой логики предикатов.

Из приведенных определений с очевидностью следует:

1. Если формула А общезначима, то она и выполнима на всякой области (модели).

2. Если формула А тождественно истинна в области М, то она и выполнима в этой области.

3. Если формула А тождественно ложна в области М, то она не выполнима в этой области.

4. Если формула А не выполнима, то она тождественно ложна на всякой области (на всякой модели).

5. Для того, чтобы формула А логики предикатов была общезначима, необходимо и достаточно, чтобы ее отрицание было не выполнимо.

6. Для того, чтобы формула А логики предикатов была выполнимой, необходимо и достаточно, чтобы формула A была не общезначима.

Рассмотрим пример Пример 5.6.

Доказать равносильность (логическое тождество):

(xy P( x, y ) uvP(v, u )) (vuP(v, u ) yxP( x, y )) xyP( y, x) uvP(u, v) Заметив, что в каждой из кванторных подформул обе предметные переменные связаны и что, таким образом, они являются высказываниями, введем обозначения:

А= xyP( x, y ) = vuP(v, u ) = uvP(u, v), В= uvP(v, u ) = yxP( x, y ) = xyP( y, x), или обозначив первую и вторую предметные переменные через n1 и n2, соответственно:

А= n1 n 2 P (n1, n 2 ), В= n 2 n1 P(n2, n1 ).

В этих обозначениях заданное для рассмотрения тождество будет выглядеть так:

( A B) ( A B) B A.

Произведя равносильные преобразования, можем убедиться в справедливости этого 15, 6 тождества: ( A B) AB AAB BAB ЛB BA BA Если охарактеризовать рассматриваемое выражение в целом, то видим, что это общезначимая формула.

Пример 5.7.

Определить тип формулы xy[ P( x) P( y )] = F..

Пусть Р(х): “Число х – четно –” предикат, определенный в М = N2.

Таким образом, рассматриваемая формула на данной модели представляет собой следующее утверждение: “Среди натуральных чисел существуют как четные, так и нечетные ”. Очевидно, что это высказывание истинно и, таким образом, на данной модели формула F тождественно истинна.

Однако, если этот же предикат задать на множестве M = N х N, где N – множество четных чисел, то формула F на такой модели окажется тождественно ложной.

Учитывая изложенное, заключаем, что рассматриваемая формула F выполнима (но не общезначима).

Пример 5.8.

Для формулы yP( x, y, z ) подобрать модель, на которой она является тождественно истинной (и, таким образом, в целом выполнимой).

Пусть Р(x, x, y): “x·x = y”, или иначе “x2 = y” – предикат, определенный на множестве натуральных чисел, т.е. М = N. Тогда рассматриваемая формула выражает утверждение о существовании натурального квадрата натурального числа, что, очевидно, является истиной, т.е. на данной модели формула тождественно истинна, что и требовалось доказать.

Пример 5.9.

Рассмотрим формулу xP( x, y, x). Это выполнимая формула. Действительно, если Р(х, y, x): “x + y = x” – предикат суммы, то на M = N существует подстановка вместо y соответствующего значения, дающего значение истинности данной формуле. Очевидно, это y = 0, поскольку в этом случае получаем “х = х”.

Если же P(x, y, x): “xy = x” – предикат произведения, то таким значением y является y = 1, так как при нем получаем истинное высказывание x( x 1 = x).

Но это единственные подстановки, приводящие к верным утверждениям, что и говорит именно о выполнимости данной формулы (но не об ее общезначимости).

Пример 5.10.

Является ли общезначимой формула: xP( x, y ) xP( x, y ) ?

Пусть P(x, y) – предикат порядка (бинарного отношения ) “ x y ”, определенный на конечном множестве натуральных чисел M1. Тогда при подстановке в формулу вместо свободной переменной y величины y = a max M 1 мы получим истинное утверждение, а при подстановке любой другой константы из множества М1 – ложное. Таким образом, рассматриваемая формула не является общезначимой.

Пример 5.11.

Рассмотрим формулу A( y ) zA( z ). Покажем, что она невыполнима.

Допустим противное, т.е. что она выполнима. Это означает, что существует такое множество М и такой конкретный предикат A 0 в нем, что когда y, z M, то данная формула превращается в такой конкретный предикат B ( y ) = A 0 ( y ) zA 0 ( z ), который, в свою очередь, превращается в истинное высказывание при всякой подстановке вместо y элементов из множества М. Возьмем любое y 0 M. Тогда высказывание B ( y 0 ) = A 0 ( y 0 ) zA 0 ( z ) истинно, как мы только что установили. Следовательно, истинны высказывания A 0 ( y 0 ) и zA 0 ( z ).

Из истинности второго высказывания заключаем, что высказывание A 0 ( y 0 ) истинно (поскольку “для всех предметных переменных”, как бы они ни обозначались). Но это противоречит истинности первого высказывания A 0 ( y 0 ).

Таким образом, наше предположение о выполнимости формулы неверно.

Проблема разрешимости в логике предикатов ставится так же, как и в алгебре логики:

существуют ли алгоритмы, позволяющие для любой формулы А логики предикатов установить, к какому типу (классу) она относится, т.е. является ли она общезначимой, выполнимой или тождественно ложной (невыполнимой). Если бы такой алгоритм существовал, то, как и в алгебре высказываний, он сводился бы к критерию тождественной истинности любой формулы логики предикатов. Отметим, что, в отличие от алгебры логики, в логике предикатов не применим метод перебора всех вариантов значений переменных, входящих в формулу, так как таких вариантов может быть бесконечное множество.

2.1.5.9. Применение языка логики предикатов для записи математических предложений, определений, построения отрицания предложений.

А. Запись математических предложений и определений в виде формул логики предикатов Язык логики предикатов удобен для записи математических предложений и определений. Он дает возможность выражать логические связи между понятиями, записывать определения, теоремы, доказательства. Приведем несколько примеров таких записей.

Пример 5.12. Определение предела “ b ” функции (х), определенной в области E, в точке x0: b = lim f ( x) 0 0x E (0 x x 0 f ( x) b ). Используя x x трехмесиный предикат P(,, x), запишем: b = lim f ( x) 0 0x E ( P(,, x)), x x где P (,, x) = (0 x x 0 f ( x) b ).

Пример 5.13.

Определение непрерывности функции в точке.

Функция f (x), определенная на множестве E, непрерывна в точке x0 E, если 0 0x E ( P(,, x)), где P (,, x) = (0 x x 0 f ( x) f ( x 0 ) ).

Пример 5.14.

Определение возрастающей функции.

Функция f (x), определенная на множестве E возрастает на этом множестве, если x1 Ex 2 E ( x1 x 2 f ( x1 ) f ( x 2 )).

Здесь использован двуместный предикат W ( x1, x 2 ) : ( x1 x 2 f ( x1 ) f ( x 2 )).

Б. Построение противоположный утверждений Пусть дано некоторое математическое утверждение А. Ему будет противоположным будет утверждение A.

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

Определение неограниченной функции мы получим, беря отрицание этой формулы и проводя равносильные преобразования:

31 M R+ x E ( f ( x) M ) M R+ x E ( f ( x) M ) M R+ x E ( f ( x) M ).

M R+ x E ( f ( x) M ) Последняя формула дает не негативное, а положительное определение неограниченной функции.

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

Особый интерес представляет построение утверждения, отрицающего справедливость некоторой теоремы: x E ( P( x) Q( x)). Это будет утверждение:

31 x E ( P( x) Q( x)) x E ( P( x) Q( x)) x E ( P( x) Q( x)).

В. Прямая, обратная и противоположная теоремы Рассмотрим четыре теоремы:

x E ( P( x) Q( x)), (5.1) x E ( P( x) Q( x)), (5.3) x E (Q( x) P( x)), (5.2) x E (Q( x) P( x)). (5.4) Пара теорем, у которых условие одной является заключением второй, а условие второй является заключением первой, называются взаимно обратными друг другу.

Так, теоремы (5.1) и (5.2), а также (5.3) и (5.4) – взаимно обратные теоремы. При этом, если одну из них называют прямой теоремой, то вторая называется обратной.

Пара теорем, у которых условие и заключение одной являются отрицанием соответственно условия и заключения другой, называются взаимно противоположными.

Так, теоремы (5.1) и (5.3), а также (5.2) и (5.4) являются взаимно противоположными теоремами.

Например, для теоремы “Если в четырехугольнике диагонали равны, то четырехугольник является прямоугольником ” (5.1) обратной является теорема “Если четырехугольник является прямоугольником, то его диагонали равны” (5.2). Для теоремы (5.1) противоположной является теорема “Если в четырехугольнике диагонали не равны, то четырехугольник не является прямоугольником” (5.3), а для теоремы (5.2) противоположной является теорема “Если четырехугольник не является прямоугольником, то его диагонали не равны” (5.4).

В рассмотренном примере теоремы (5.1) и (5.4) являются одновременно ложными, а теоремы (5.2) и (5.3) одновременно истинными. Контрпримером к теореме (5.1) является равнобочная трапеция.

Ясно, что прямая и обратная теоремы, вообще говоря, не равносильны, т. е. одна из них может быть истинной, а другая – ложной. Однако легко показать, что теоремы (5.1) и (5.4), а также (5.2) и (5.3) всегда равносильны.

Действительно:

1, 18 x E ( P( x) Q( x)) x E ( P( x) Q( x)) x E (Q( x) P( x)) x E (Q( x) P( x)).

Из этих равносильностей следует, что, если доказана теорема (5.1), то доказана и теорема (5.4), а если доказана теорема (5.2), то доказана и теорема (5.3).

Г. Необходимые и достаточные условия Рассмотрим теорему x E ( P( x) Q( x)) (5.5) Как отмечалось, множество истинности предиката P ( x) Q( x) есть множество I P I Q. Но тогда множеством ложности этого предиката будет I P IQ = I P IQ.

Последнее множество будет пустым лишь в случае, когда I P I Q.

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

Так, в теореме “Если х – число натуральное, то оно целое” предикат Q(x): “х – число целое” логически следует из предиката Р(х): “х – число натуральное”, а предикат “х – число натуральное” является достаточным условием для предиката “х – целое число”.

Часто встречается ситуация, при которой истинны взаимно обратные теоремы x E ( P( x) Q( x)) (1) x E (Q( x) P( x)).(2) Это, очевидно, возможно при условии, что I P = I Q.

В таком случае из теоремы (5.1) следует, что условия Р(х) являются достаточными для Q(x), а из теоремы (5.2) следует, что условие Р(х) является необходимым для Q(x).

Таким образом, если истинны теоремы (5.1) и (5.2), то условие Р(х) является и необходимым, и достаточным для Q(x). Аналогично в этом случае условие Q(х) является необходимым и достаточным для Р(x).

Иногда вместо логической связки “необходимо и достаточно” употребляют логическую связку “тогда и только тогда”.

Так как здесь истинны высказывания (5.1) и (5.2), то истинно высказывание 35, x E ( P( x) Q( x)) x E (Q( x) P( x)) x E ( P( x) Q( x)).

Д. Доказательство теорем методом от противного Доказательство теорем методом от противного обычно проводится по следующей схеме: предполагается, что теорема x E[ P( x) Q( x)], не верна, т. е., существует такой объект х, что условие Р(х) истинно, а заключение Q(x) – ложно. Если из этих предложений путем логических рассуждений приходят к противоречивому утверждению, то делают вывод о том, что исходное предположение неверно, и верна теорема (5.5).

Покажем, что такой подход дает доказательство истинности теоремы (5.5).

Действительно, предположение о том, что теорема (5.5) не справедлива, означает истинность ее отрицания, т. е. формулы x E[ P( x) Q( x)]. Можно показать, что противоречивое утверждение, которое получается из допущенного предположения, как мы видели из ранее рассмотренных примеров, может быть записано как конъюнкция C C = A, где С – некоторое высказывание.

2.1.6. Множества и отношения 2.1.6.1. Мощность множества Понятие “мощность множества” введено основателем теории множеств Г. Кантором, который установил, что мощность множества действительных чисел больше 0, и тем са мым показал, что бесконечные множества могут быть расклассифицированы по их мощно сти.

Мощность множества в математике есть обобщение на произвольные множества поня тия «число элементов». Мощность множества определяется методом абстракции как то об щее, что есть у всех множеств, эквивалентных (количественно) данному;

при этом два мно жества называемых эквивалентными, если между ними можно установить взаимно одно значное соответствие. Мощности называются часто кардинальными (т. е. количественными) числами.



Pages:     | 1 | 2 || 4 | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.