Лекции по математической логике1. Элементы математической логики
 Скачать 2.19 Mb.
|
|
Тождественно истинные формулы Множество всевозможных формул логики высказываний с точки зрения принимаемых этими формулами значений разбивается на три класса: 1. Формулы, принимающие значения И при всех наборах входящих в них переменных называются тождественно истинными (ТИФ). 2. Формулы, принимающие значения Л на всех наборах значений переменных, входящих в них, называются тождественно ложными (ТЛФ). 3. Формулы, принимающие при некоторых наборах значений переменных значения И, при других – Л, называются выполнимыми. Предложение « - тождественно истинная формула» обозначают | . На практике мы ввели важное понятие равносильности формулы логики высказывания. Две формулы А и В равносильны (АВ) тогда и только тогда, когда они представляют одну и ту же функцию от входящих в нее переменных, то есть для всех наборов значений переменных значения истинности формул А и В совпадают, в противном случае формулы не равносильны. Таким образом, на первый взгляд может показаться, что для установления равносильности формул достаточно сравнить их значения на всевозможных наборах переменных. Однако кажущаяся простота решения проблемы наталкивается на ряд серьезных затруднений. 1. Во-первых, если число переменных не очень мало, то число наборов, которые нужно подставлять, будет очень велико и применение простого принципа сравнения формул А и В может стать практически невозможным. Уже для 30 переменных потребуется проверить 109 наборов (это примерно соответствует 230). При этом для установления равносильности нужно для каждого набора провести вычисление значений обеих формул, а если эти формулы большой длины, то на это, в свою очередь, понадобится большое число операций. 2. Во-вторых, и это соображение, по видимому более важно – в логике высказываний, в логике предикатов и их приложениях речь пойдет о равносильности не двух каких-либо формул, а о равносильности бесконечного множества формул. Таким образом, нужны утверждения, согласно которым все формулы некоторого определенного вида равносильны соответственно формулам некоторого определенного вида, то есть нужны общие соображения, общие правила вывода одних формул из других. Отношение равносильности и эквивалентность Докажем, что если формулы 1 и 2 равносильны, то формула 12 тождественно истинна, то есть если 12, то | 12 и если | 12, то 12. Доказательство. Действительно, если 12, то формулы 1 и 2 принимают обе значение И или обе значение Л при любом наборе значений входящих в них переменных, а в этом случае формула 12, согласно определению эквивалентности, принимает только значение И, то есть | 12. Обратно, если 12, то 1 и 2 принимают при любом наборе значений входящих в них переменных обе значение И или обе значение Л, то есть 12. Таким образом, исходя из доказанного предложения, каждая из перечисленных в таблице равносильностей порождает тождественно истинную формулу (достаточно заменить знак равносильности = или знаком эквивалентности ). Наоборот, если 12, то для некоторого набора x1,…,xn значений переменных одно высказывание будет иметь значение И, другое – Л. Тогда 1(x1,…,xn) 2(x1,…,xn) будет ложным высказыванием, а следовательно, формула 1(x1,…,xn) 2(x1,…,xn) не будет тождественно истинной. Тем самым задача об установлении равносильности двух формул сводится к установлению тождественной истинности формул частного вида. Наряду с отношением равносильности между формулами логики высказываний рассматриваются некоторые другие отношения, представляющие большой интерес для логики и ее приложений. Среди них наиважнейшим является отношение логического следования. Пусть 1(x1,…,xn)1 и 2(x1,…,xn)2 – две формулы логики высказываний от переменных x1,…,xn. Будем говорить, что формула 2(x1,…,xn) является логическим следствием формулы 1(x1,…,xn), если 2 принимает значение И для всех наборов значений переменных, для которых 1 истинна. Это означает также, что если представить обе формулы их таблицами истинности, то множество наборов, для которых 1 истинна содержится в множестве наборов, для которых истинна формула 2. Например, согласно этому определению 2=(xz) является логическим следствием 1=((xy)&z). Это видно их соответствующих таблиц истинности.
Определение. Формула 2(x1,…,xn) является логическим следствием формулы 1(x1,…,xn) тогда и только тогда, когда тождественно истинна формула 1(x1,…,xn)2(x1,…,xn). Из сказанного видно, что формулы 1 и 2 равносильны тогда и только тогда, когда каждая из них является логическим следствием другой. Из определения также следует, что всякая формула является логическим следствием тождественно ложной формулы. Действительно, так как в этом случае формула 1 никогда не принимает значение И, то множество наборов, для которых 1 истинно, пусто и содержится, следовательно, в множестве наборов истинности для любой формулы 2. Отметим, что введенные отношения (тождества и следования) относятся не к единичным высказываниям, как это имело место для понятия импликации, а к целым множествам высказываний, описываемых формулами 1(x1,…,xn) и 2(x1,…,xn). Формулу 1(x1,…,xn) можно рассматривать как условие, которое может быть выполнимо или нет в зависимости от истинности 1. Перечень тождественно истинных формул 1. (pq)(rq)(prq); 2. pqp; 3. (pq)(pr)(pqr); 4. (pq)pq; 5.  ;6.  закон контрапозиции;7.  ? закон расширенной контрапозиции;8. p(qr)pqr; 9.  ;10.  ;11. (pq)(qr)(pr) – .закон силлогизма. Подстановка Разумеется, этот перечень не исчерпывает тождественно истинные формулы, находящие применение в исчислении высказываний. Вместе с тем каждая из перечисленных тождественно истинных формул порождает новые ТИФ в результате подстановки вместо какой-нибудь входящей в нее переменной произвольной формулы. Действительно, если | (…, р,…) содержит переменную р, то, подставив вместо переменной р всюду, где она входит в , произвольную формулу , в результате получим формулу (…, ,…), которая принимает те же значения, что и исходная формула (…, р,…), так как принимает те же значения (И, Л), что и р. Конечно, можно применять подстановку к нескольким или даже ко всем переменным, входящим в ТИФ. Например, тождественно истинной формулой является | (12)(23)( 13), так как эта формула получается из (11) подстановкой вместо p формулы 1, вместо q формулы 2 и вместо r формулы 3. Проблема разрешимости тождественной истинности Ввиду особой роли ТИФ, возникает вопрос о существовании общего метода (разрешающего метода), позволяющего относительно любой конкретной формулы логики высказываний ответить, является ли она тождественно истинной или нет. Укажем несколько методов разрешения этого вопроса. 1. Составление таблицы истинности, соответствующей данной формуле. Если последний столбец таблицы (столбец значений данной формулы) состоит из одни И, данная формула – ТИФ, если же в столбце содержится хотя бы одна Л, она не является ТИФ. Разумеется, составление таблицы истинности не всегда удобный метод (при числе n переменных таблица содержит 2n строк). Но она всегда состоит из конечного числа шагов и всегда дает ответ на поставленный вопрос. 2. Преобразование формулы (приведение ее к КНФ). Все операции, знаки, которые содержатся в формуле, выражаются через конъюнкцию, дизъюнкцию и отрицание. Знаки отрицания сводятся к отдельным переменным (использование законов де Моргана). Для этого используются законы двойного отрицания, коммутативности, ассоциативности конъюнкции и дизъюнкции, дистрибутивности дизъюнкции относительно конъюнкции. В результате этих преобразований формула приводится к КНФ. Если в каждой дизъюнкции содержится какая-либо переменная вместе с ее отрицанием, то данная формула – ТИФ. Если существует хотя бы одна дизъюнкция, не содержащая ни одной переменной вместе с ее отрицанием, данная формула не является ТИФ. Пример. Применим этот метод к формуле (pq)(qr) (pr)  3. Метод косвенного доказательства (способ от противного). Допустим, что данная формула не является ТИФ. Тогда существует хотя бы один набор значений переменных, входящих в эту формулу, при котором она принимает значение Л. Если такой набор переменных удается найти, то данная формула не является ТИФ. Если же допущение о существовании такого набора значений переменных ведет к противоречию, то данная формула – ТИФ. Пример. Применим этот метод к формуле (pq)(qr) (pr). Допустим, что эта формула не является ТИФ. Тогда существует хотя бы один набор значений переменных (p, q, r), при котором она ложна, то есть основание истинно (pq)(qr)И; (1) а следствие ложно (pr)Л. (2) Из (2) следует р=И, (3) а r=Л (4) Из (1) следует, что (pq)И; (5) (qr)И; (6) Из (6) и (4) следует q=Л, (7) а из (7) и (5) р=Л. (8) Получили противоречие (3) и (8). Следовательно, наше допущение неверно и формула (1) ТИФ. На основе этих примеров можно сделать ряд выводов о тождественной истинности формул. Теорема 1. Чтобы элементарная логическая сумма была тождественно-истинной, необходимо и достаточно, чтобы в ней содержалась хотя бы одна пара слагаемых, из которых одно есть некоторая переменна, а другое – ее отрицание. В самом деле, если такая пара слагаемых найдется, то сумма имеет вид  Поскольку  , поэтому и истинна вся рассматриваемая сумма, каковы бы ни были остальные слагаемые y, z,…Это условие достаточное. Теперь об условии необходимом. Допустим, что такой пары слагаемых, из которых одно является отрицанием другого, в сумме нет. В таком случае можно каждой переменной, не стоящей под знаком отрицания, дать значение Л, а каждой переменной, стоящей под знаком отрицание дать значение И. Это можно сделать, поскольку ни одна переменная не входит в сумму одновременно с отрицанием и без отрицания. После указанной подстановки каждое слагаемое примет значение Л, и, следовательно, формула не является ТИФ, что и требовалось доказать. Аналогично доказывается Теорема 2. Чтобы элементарное произведение было тождественно ложным, необходимо и достаточно, чтобы в нем содержалась хотя бы одна пара множителей, из которых один является отрицанием другого. Элементы теории графов Теория графов представляет в распоряжение инженера исключительно удобный аппарат для моделирования структурных свойств систем и отношений между объектами самой разнообразной природы. На основе аналогии между физическими величинами развивается методика построения математических моделей систем в различной форме. Основные понятия и определения Граф — это система некоторых объектов вместе с парами этих объектов, изображаются отношения связи между ними. Графом G называется система (V,U,), где V={} — множество вершин; U={u} — множество ребер; — функция инциденции, ставящая в соответствие каждому ребру uU упорядоченную (или неупорядоченную) пару вершин (1,2), называемых концами ребра u. Множество vUu образует множество элементов графа. По количеству элементов графы делятся на конечные и бесконечные. Если (u)= (1,2) — упорядоченная пара, (т.е. (12)(1,2) (2,1)), то ребро называется ориентированным ребром или дугой, исходящей из вершины 1 (начало), и входящей в вершину 2 (конец дуги). Если (u)=(1,2) — неориентированная пара, то соответствующее ей ребро — неориентированное. Граф с неориентированными ребрами называют неориентированным, а с ориентированными ребрами — неориентированным графом (орграфом). Всякому графу G(v,u,) можно сопоставить соотнесенный неориентированный граф  , где  — сопоставляет ребрам те же пары вершин, что и , но неупорядоченные.Граф, имеющий как ориентированные, так и неориентированные ребра, называется смешанным. Граф G=(v,u,), ребрами которого являются всевозможными пары (u)=(i,j) для двух возможных вершин i,jV, называется полным неориентированным графом. Такие графы для трех, четырех и пяти вершин приведены:  Граф G=(v,u,), в котором пара вершин соединяется несколькими (кратными) ребрамиб называется мультиграфом, а содержащий изолированные вершины — нуль-графом. Дополнением графа G=(v,u,) является граф Gк=(v,u,), ребра которого совместно с графом G образуют полный граф. Ребро, граничными вершинами которого является одна и та же вершина, называется петлей. В общем случае граф может содержать изолированные вершины, которые являются концами ребер и не связаны между собой, ни с другими вершинами.  Число ребер, связанных с вершиной i (петля учитывается дважды), называют степенью вершины. Цепи и циклы графов Цепь — конечная или бесконечная последовательность ребер S=(…1,2,…), в которой у каждого ребра к одна из вершин является вершиной ребра к-1, при этом ребро и одна из вершин могут встречаться несколько раз. Каждая цепь имеет начальную и конечную вершину, остальные вершины называются внутренними (промежуточными). Цепь называется простой, если любое реьро не повторяется в цепи дважды. Составной (сложной) в противном случае; элементарной, если в ней ни одна из вершин не повторяется дважды. Цикл — конечная цепь, начинающаяся и заканчивающаяся на той же вершине. Цикл называется простым, если все его ребра различны, в ином случае — составным (сложным), и элементарным — если при обходе его ни одна из вершин не встречается дважды. Цикл, не содержащий вершины, кроме той, на которой он начинается и заканчивается, называется петлей. Цикл, у которого начальная и конечная вершины различны, называется путем. Он также может быть простым (никакая дуга не встречается дважды), составным или элементарным (никакая вершина не встречается дважды). Длина пути — число ребер (дуг) в нем. Цикл, начинающаяся и заканчивающаяся в начальной вершине, называется контуром. Граф называется конечным, если число вершин его конечно, и бесконечным — в ином случае. Граф Н(v,u,) называется частичным для графа G(v,u,), если все ребра и вершины графа Н, являются соответственно ребрами и вершинами графа G, т.е. если НG, то для всех V. Нуль-граф считается частичным графом любого графа. Все частичные графы Нi для G(v,u,) можно получить, выбирая в качестве ребер всевозможные подмножества ребер графа G. Подграфом GА(А) графа G(v) называется граф, вершинами которого являются вершины Аv, а ребрами — все ребра из G, оба конца которых лежат в А. Иначе,GА(А) подграф графа G(v), если Аv и GА(v)=G(v)А. Если А=v, то GА(А)=G(v); если А={а}, т.е. А состоит из одной вершины, то GА(а) состоит из петель в а; если Аv — подмножество изолированных вершин графа G(v), то подграфом графа G(v) будет нуль-граф. Частичным подграфом НА(А), АХ графа G(v) называется подграф, ребрами которого являются некоторые ребра из G(v), оба конца которых лежат в А. Иначе, НА(А) — частичным подграф графа G(v), если АХ и НА(v)=G(v)А для всех vV. Дополнительным частичным подграфом НА(А) графа G(v) является единственный граф, состоящий из ребер графа G(v), не принадлежащих некоторому частичному подграфу НА(А) графа G(v).  1 - Граф G(v).2 - Подграф GА(А) графа G(v). 3 - Частичный подграф НА(А) графа G(v). 4 - Дополнительный частичный подграф НА(А) графа G(v). Звездным графом, определяемым вершиной v, называется граф, состоящий из ребер G(v), имеющих v концевой вершиной. При этом петли в v могут включаться, либо не включаться в звездный граф. Две вершины iи j неорганизованного графа G(v) называются связными, если существуюет цепь S с концами iи j. При прохождении пути через некоторую вершину к более одного раза цикл в вершине к можно удалять из цепи S. Неориентированный граф называется связным, если любая пара его вершин связана. Отношение связности для вершин графа является отношением эквивалентности. Оно разбивает множество вершин графа на классы. Подграфы, ''натянутые'' на эти классы вершин, называются компонентами связности графа. Другими словами, компонентами связности неориентированного графа G(v) называется подграф НА(А) с множеством вершин Аv и множеством ребер в G(v), инцидентных только вершинам из А, причем ни одна из viAне смежна с вершинами из множества vА. Несвязный граф состоит из нескольких отдельных частичных подграфов:  В сильно связанном ориентированном графе для любой пары вершин обязательно существует соединяющий их путь. Компонентой сильной связности ориентированного графа G(v) называется сильно связанный подграф НА(А) с множеством вершин Аv и множеством дуг, имеющих начало и конец в множестве А, причем ни одна из вершин viAи ни одна из вершин vjvА не смежны между собой. Очевидно, что сильно связанный ориентированный граф имеет только одну компоненту сильной связности. Пример ориентированного графа, состоящего из 2-х компонент сильной связности, приведен ниже  Отдельными, широко используемыми видами графов являются деревья и прадеревья. Деревом называется конечный связный граф, состоящий по крайней мере из двух вершин и не содержащий циклов. Такой граф не имееи кратных ребер:  Ветвями дерева называются ребра графа, входящие в дерево. Хордами дерева называют ребра, взодящие в граф, дополнительный к данному графу. Деревья на множестве вершин Пусть множество v содержит р вершин, которые пронумерованы v1,…vр. Связав эти вершины (р-1) ребрами так, чтобы отсутствовали циклы, получим некоторое дерево, покрывающее данное множество р вершин. При р=2 такое дерево единственное и состоит из одной ветви. С увеличением р число различных деревьев tp быстро возрастает tp=рр-2 многие из них являются изоморфными, т.е. отличаются только нумерацией вершин. Так при р=0 имеем 108 различных деревьев, из которых 106 неизоморфны. На рис. показаны 16 различных деревьев, которые можно построить на множестве четырех вершин.  Символ дерева Любому дереву Т можно поставить во взаимно-однозначное соответствие некоторый символ — упорядоченную последовательность (р-2) номеров вершин (Т)=(1,2,… р-2), среди которых могут быть повторяющиеся, причем 1,2,… р-2. Эта последовательность для данного дерева образуется следующим образом. Вводится последовательность Np=(1,2,…р), далее выбирается концевая вершина с наименьшим номером и записывается номер ,связанной с ней вершиной, а сама концевая вершина удаляется из последовательности Np=(1,2,…р). Затем этот процесс повторяется до тех пор, пока не получим последовательность (Т)=(1,2,… р-2). Каждый такой шаг соответствует удалению из дерева концевой вершины с наименьшим номером и связанного с ней концевого ребра, причем (р-2) шагов от дерева остается единственное ребро, положение которого определяется парой номеров вершин, оставшихся в последовательности Np. Построение дерева по его символу выполняется последовательным восстановлением концевых вершин и ребер. На первом шаге из последовательности Np=(1,2,…р) выбирается наименьший номер min, который отсутствует в (Т)=(1,2,… р-2) и строится ребро (min,1). Далее удаляется номер min из Np и номер 1 из (Т) и процесс продолжается до исчерпывания символа (Т). оставшаяся в последовательности Np пара вершин определяет последнее ребро дерева. Например, исходя из символа (Т2)=(1,3,1,1,3) дерева Т2   . последовательность N7=(1,2,3,4,5,6,7) на первом шаге имеем ребро (2,1). Удаляя ''2'' из N7 и ''1'' из (Т2), получаем последовательность  На втором шаге получаем ребро (4,3) и далее аналогично ребра (5,1),(6,1),(1,3),(3,7). Совокупность всех полученных ребер и образует соответствующее дерево. Произвольное дерево на множестве р вершин можно рассматривать как одно из покрывающих деревьев графа.  Рис. Дерево полного графа. Экстремальное дерево. В ряде практических задач требуется связать р пунктов наиболее экономичным способом с линиями связи р пунктов, автомобильными дорогами таким образом, чтобы суммарная длина была наименьшей. На языке теории графов эта задача формулируется в общем виде следующим образом. Каждому ребру (i,j) полного графа с р вершинами приписывается вес ij, выражающий численно расстояние, стоимость и другую величину, характеризующую любую пару вершин. Требуется построить экстремальное дерево, связывающее все вершины так, чтобы был минимальным суммарный вес i ветвей дерева  .Перебор вариантов при р9 больше 106. Существует алгоритм Прима, который основан на последовательном введении выбора ребер с наименьшим весом. Затем на каждом следующем шаге выбирается min по весу ребро и, если оно не образует цикла с ранее выбранными ветвями, вводится в дерево. Построение заканчивается после отбора дерева (р-1) ребер. Если имеются ребра с одинаковым весом, то решение может быть единственным в том случае, когда не все такие ребра входят в дерево, а отдается определенный приоритет отдельным. Построение экстремального дерева с максимальным суммарным весом аналогично, необходимо лишь последовательно выбирать для него ребра наибольшего веса. Деревья графа. Будем называть деревом связного графа любое покрывающее дерево, связывающее все его вершины и имеющее в качестве ветвей ребра этого графа. Два дерева считаются различными, если они отличаются хотя бы одним ребром. Существует простой способ определения количества различных деревьев графа без петель (мультиграфа) с р вершинами. Для этого необходимо записать квадратичную матрицу р-го порядка, по главной диагонали которой расположена степень вершин, а ij-и ji-элементы равны взятому со знаком ''-'' числу ребер, связывающих вершиныi и j. Вычисляя любой из главных минора этой матрицы, получим исходное число деревьев. Например, для графа имеем дерево (одно из 7в).   22 — один из главных миноров этой матрицы. Это теорема Трента. Типы конечных графов. Число ребер, связанных с вершиной i (петля учитывается дважды), называется степенью вершины и обозначается deg(i).  deg(2)=4 deg(5)=0 Степень изилирования вершины равна 0. Легко показать, что в любом графе сумма степеней всех вершин равна удвоенному числу ребер, а число вершин нечетной степени всегда четно. В орграфе различают положительные +(i) и отрицательные -(i) степени вершин, которые равны соответственно числу исходящих из i и заходящих в i дуг. Очевидно, что суммы положительных……………………………. Примеры и задачи. 1. Даны два множества Х={x1,x2,x3,x4,x5,x6} Y={y1,y2,y3,y4} и определено бинарное отношение А={(x1,y2),(x2,y1),(x2,y2),(x4,y2), (x4,y3),(x5,y1),(x5,y3)}. Для данного отношения А: а) записать область определения и область значений; б) определить сечения по каждому элементу из Х; в) определить сечения по подмножествам Х'={x1,x4} и Х''={x2,x3,x5} множества Х; г) записать матрицу и нарисовать граф; д) определить симметричное отношение А-1. 2. Пусть Х — множество студентов; Y — множество дисциплин и соотношение хАу, где хХ и уY, означает ''студент х изучает дисциплину у''. Дать словесное описание областей определения и значений, сечений и обратного отношения, полученных в задаче №1. 3. По результатам задачи определите множества А(х2) А(х4), А(х2)\ А(х4) и А(х2)+А(х4). Дайте им словесное описание согласно условия задачи №2. Задача. Представьте бинарные отношения, заданные графом как множество упорядоченных пар и запишите его матрицу.  Задача. Записать композицию С=ВА отношений А={(1,2),(1,3), (2,1),(2,4),(3,3)} и В={(1,1),(1,3), (2,2),(3,1),(4,2),(4,3)}. Проверить результат с помощью операций над матрицами и графами заданных отношений.   |