Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 17
Текст из файла (страница 17)
Если вспомнить классификацию способов задания множеств (й 1 1), то первая проблема — это проблема построения порождающей процедуры, а вторая — проблема разрешающей процедуры для множества истинных формул. Те же проблемы встают и в логике высказываний. Однако там есть стандартная разрешающая процедура: вычисление формул на наборах значений переменных, С ее помощью порождающую процедуру для множества М~ тождественно истинных высказываний можно организовать следующим образом: строим последовательно все формулы, вычисляем каждую из них на всех наборах и включаем в М только те, которые истинны на всех наборах.
Аналогичная процедура в логике предикатов сталкивается с большими трудностями, связанными с тем, что предметные и предикатные переменные имеют в общем случае бесконечные области определения. Поэтому прямой перебор всех значений невозможен, и приходится использовать различные косвенные приемы. Покажем их на примере некоторых эквивалентных со. отношений 3хР (х) — ухР (х).
(3.31) Пусть для некоторого предиката Р и области М левая часть истинна. Тогда не сущесъвует аыМ, для которого Р(а) истинно; следовательно, для всех а Р(а) ложно, т.е. гг(о) истинно, и правая часть истинна, Если же левая часть ложна, то существует ае-=М, для которого Р(а) истинно, и, следовательно, правая часть ложна Аналогично доказывается ухР (х) — нх Р (х). (3.32) Докажем теперь дистрибутивность Чх относителщю конъюнкции и Вх относительно дизъюнкции ух (Р (х) й Р, (х)) — т1хР, (х) й ухР, (х).
(3.33) Пусть левая часть соотношения истинна для некоторых Р~ и Рь Тогда для любого а~М истинно Р,(а)йР,(а), поэтому Р,(а) и Р,(а) одновременно истинны для любых а, и, следовательно, тгхР,(х)йухР,(х) истинно. Если. же левая часть ложна, то для некоторого аеиМ ложно либо Р,(а), либо Р»(а), а следовательно, ложно либо цхР,(х), либо ~хР»(х), и правая часть ложна, Аналогично доказывается дх (Рг (х) ~/ Р«(х)) — ВхР, (х)',/ВхР, (х). (3.34) Если же )ух и Вх в этих соотношениях поменять местами, то получатся соотношения, верные лишь в одну сторону: Вх (Рг (х) й Р, (х)) — »ВхР, (х) 6 ВхР, (х); (3,36) ЦхР»(х) ~/ ухР»(х)) — «~~х(Р,(х) ~/ Р,(х)). (3,36) В таких случаях говорят, что левая часть — более сильное утверждение, чем правая, поскольку она требует для своей истинности выполнения более жестких условий, чем правая.
Так, в (3.35) в левой части требуется, чтобы Р,(а) и Р,(а) были истинны для одного и того же а, тогда как в правой части Р~ и Рз могут быть истинны при различных а, и а,. В (3.36) левая часть требует, чтобы хотя бы один предикат выполнялся для всех а~М; в правой части достаточно, чтобы один предикат был истинен там, где ложен другой. В этих рассуждениях по существу уже содержатся доказательства; окончательное их уточнение предоставляем читателю. Пример, когда (3.35) и (3.36) в обратную сторону неверны: Р,(х): «х — четное число», Р,(х): «х — нечетное число». Приведем без доказательства еще несколько соотношений: Т(хт/уР (х, у) — цуцхР (х, у); (3.37) ВхдуР(х, у) — ВуВхР (х, д). (3.38) Пример 3.12, в показывает, что перестановка различных кванторов не является эквивалентностью. Пусть У вЂ” переменное высказывание или формула, не содержащая х.
Тогда ух (Р (х) й У) — тухР (х) Ь)'; (3.39) (3.40) (3.41) (3. 42) ух (Р (х) ~У У) — Т~хР (х) Ч У; 'лх (Р (х) й )') — дхР(х) 8с )г; дх(Р(х) '/ )') — ~хР(х) ~„г )г, Эти соотношения означают, что формулу, не содержащую х, можно выносить за область действия квантора, связывающего х. О методах доказательства в логике предикатов, Метод доказатель. ства формул, содержащих переменные, путем непосредственной подстановки в ннх нонстант называется методом интерпретаций нли методом моделей '. Подстановка констаат позволяет интерпретировать формулу кан осмысленное утверждение об элементах конкретного множества М.
Поэтому такой метод, выясняющий истинность формул путем обращения к ее возможному смыслу, называется также семантическим (т.е. смысловым). Метод интерпретаций удобен для доказательства выполнимости формул илн их неэквивалентности, поснольку и в том, и в другом случае достаточно найти одну подходящую подстановку (именно так мы поступили ранее„сославшись на пример 3.12, в). Он удобен также для исследования истинности формул на конечных областях. Дело в том, что если область М конечна, М=(аь ..,, а„), то кван- торы переходят в конечные формулы логини высказываний: ухР(х) Р(а ) ЙР(аа) сг ... МР(а„); пхР(х) Р(а,)'уР(аз)Ч ...
т/ Р(а„). ' Точные понятия интерпретации и модели вводятся в гл. б, $6.3. Заменив все кванторы в формуле по этим соотношениям, любую формулу логики предикатов можно перевеств в формулу, состоящую из предикатов, соединенных знаками логических операций. Истинность такой формулы иа конечной области проверяется конечным числом под. стаиовок и вычислений. Для бесконечных же областей в общем случае и прежде всего при доказательстве тождественной истинности формул метод интерпретаций, как уже отмечалось, связан с большими трудностями. Поэтому для построения множества истинных формул в логике предикатов выбирается другой путь. Это множество порождается из исходных фор. мул (аксиом) с помощью формальных процедур — правил вывода. Слово «формальный» (которое часто противопоставляется слову «содержательный») подчернивает здесь то обстоятельство, что при переходе от одних выводимых формул к другим ие происходит какого-либо обращения к содержанию, смыслу формул, Используются лишь формальные, внешние свойства последовательностей символов, образующих формулы, причем эти свойства полностью описываются правиламн вы- вода.
Важность формального подхода в том, что благодаря ему удается избежать обращения к бесконечной области (что иенабежно при методе интерпретаций) и на каждом шаге вывода оперировать только с конечным множеством символов. Методы рассуждений, использующие только конечные мионгества конечных обьектов, называются финит- ными. Множества, порожденные такими формальными методами, называются формальиымн системами (см. гл. 6).
ГЛАВА ЧЕТВЕРТАЯ ГРАФЫ 4Л. ОСНОВНЫЕ ПОНЯТИЯ И ОПЕРАЦИИ Графы, их вершины, ребра и дуги, Теорию графов начали разрабатывать для решения некоторых задач о геометрических конфигурациях, состоящих из точек и линий, В этих задачах несущественно, соединены ли точки конфигурации отрезками прямых или криволинейными дугами, какова длина линий и другие геометрические характеристики конфигурации, Важно лишь то, что каждая линия соединяет какие-либо две из заданных точек.
Таким образом, можно дать определение графа как совокупности двух множеств )г (точек) и Е (линий), между элементами которых определено отношение инцидентности, причем каждый элемент еенЕ инцидентен ровно двум элементам о', овен)г. Элементы множества и' называются вергиинами графа 6, элементы множества Š— его ребрами. Вершины и ребра графа 6 называют еще его элементами и вместо ия)г, еенЕ пишут соответственно иееб и еевб, В некоторых задачах инцидентные ребру вершины неравноправны, они рассматриваются в определенном порядке. Тогда каждому ребру можно приписать направление от первой из инцидентных вершин ко второй, Направленные ребра часто называют дугами (однако в этой книге они будут называться ребрами), а содержащий их граф — ориентированным (граф, определенный ранее, называется неориентированным).
Первая по порядку вершина, инцидентная ребру ориентированного графа, называется его начилом, вторая — его концом. Говорят еще, что ребро ориентированного графа выходит из начала и входит в конец. 88 В дальнейшем оказалось, что понятие графа можно применить не только при исследовании геометрических конфигураций. Особенно часто определяют графы при анализе функционирования систем, С отдельными компонентами изучаемой системы удобно связывать вершины графа, а с парами взаимодействующих компонент — его ребра. Построенный таким образом граф называют структурным графом системы.
Изображение графов. На рис. 4.1, а — з изображены некоторые неориентированные графы. Множество ребер Е моа1 б1 3 3 О е1 зк) Рча 4.1 жет быть пустым (рис. 4.1, г), Если же множество вершин У пусто, то пусто и Е. Такой граф называется пустым. Линии, изображающие ребра графа, могут пересекаться, по точки пересечения не являются вершинами (рис. 4.1, д); различные ребра могут быть инцидентны одной и той же паре вершин (рис. 4.1, е), в этом случае они называются кратными; граф, содержащий кратные ребра, часто называют мульти- графом. Ребро может соединять некоторую вершину саму с собой (рис.
4,1,ж), такое ребро называется петлей. На рис. 4.1,з изображен фрагмент бесконечного графа. Его вершины — это точки плоскости с целыми координатами (х, у), а ребра — соединяющие их горизонтальные и вертикальные отрезки длины 1. Обычно рассматриваемые графы конечны, т. е. конечны множества их элементов (вершин и ребер). Поэтому конечность этих графов не будет специально оговариваться.'Од- нако некоторые понятия и результаты, о которых будет идти речь, относятся к произвольным графам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
