Проблема разрешимости тождественной истинности

Ввиду особой роли ТИФ, возникает вопрос о существовании общего метода (разрешающего метода), позволяющего относительно любой конкретной формулы логики высказываний ответить, является ли она тождественно истинной или нет.

Укажем несколько методов разрешения этого вопроса.

1. Составление таблицы истинности, соответствующей данной формуле. Если последний столбец таблицы (столбец значений данной формулы) состоит из одни И, данная формула – ТИФ, если же в столбце содержится хотя бы одна Л, она не является ТИФ. Разумеется, составление таблицы истинности ‑ не всегда удобный метод (при числе n переменных таблица содержит 2n строк). Но она всегда состоит из конечного числа шагов и всегда дает ответ на поставленный вопрос.

2. Преобразование формулы (приведение ее к КНФ). Все операции, знаки, которые содержатся в формуле, выражаются через конъюнкцию, дизъюнкцию и отрицание. Знаки отрицания сводятся к отдельным переменным (использование законов де Моргана). Для этого используются законы двойного отрицания, коммутативности, ассоциативности конъюнкции и дизъюнкции, дистрибутивности дизъюнкции относительно конъюнкции.

В результате этих преобразований формула приводится к КНФ. Если в каждой дизъюнкции содержится какая-либо переменная вместе с ее отрицанием, то данная формула – ТИФ. Если существует хотя бы одна дизъюнкция, не содержащая ни одной переменной вместе с ее отрицанием, данная формула не является ТИФ.

Пример. Применим этот метод к формуле (pÞq)(qÞr) Þ (pÞr)

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

Пример. Применим этот метод к формуле (pÞq)(qÞr) Þ (pÞr).

Допустим, что эта формула не является ТИФ. Тогда существует хотя бы один набор значений переменных (p, q, r), при котором она ложна, то есть основание истинно

(pÞq)(qÞr)ºИ; (1)

а следствие ложно (pÞr)ºЛ. (2)

Из (2) следует р=И, (3)

а r=Л (4)

Из (1) следует, что (pÞq)ºИ; (5)

(qÞr)ºИ; (6)

Из (6) и (4) следует q=Л, (7)

а из (7) и (5) р=Л. (8)

Получили противоречие (3) и (8). Следовательно, наше допущение неверно и формула (1) ТИФ.

На основе этих примеров можно сделать ряд выводов о тождественной истинности формул.

Теорема 1. Чтобы элементарная логическая сумма была тождественно-истинной, необходимо и достаточно, чтобы в ней содержалась хотя бы одна пара слагаемых, из которых одно есть некоторая переменна, а другое – ее отрицание.

В самом деле, если такая пара слагаемых найдется, то сумма имеет вид Поскольку , поэтому и истинна вся рассматриваемая сумма, каковы бы ни были остальные слагаемые y, z,…

Это условие достаточное. Теперь об условии необходимом. Допустим, что такой пары слагаемых, из которых одно является отрицанием другого, в сумме нет. В таком случае можно каждой переменной, не стоящей под знаком отрицания, дать значение Л, а каждой переменной, стоящей под знаком отрицание дать значение И. Это можно сделать, поскольку ни одна переменная не входит в сумму одновременно с отрицанием и без отрицания. После указанной подстановки каждое слагаемое примет значение Л, и, следовательно, формула не является ТИФ, что и требовалось доказать.

Аналогично доказывается

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


 

Элементы теории графов

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

 

Основные понятия и определения

 

Граф — это система некоторых объектов вместе с парами этих объектов, изображаются отношения связи между ними.

Графом G называется система (V,U,j), где V={n} — множество вершин; U={u} — множество ребер; j — функция инциденции, ста­вящая в соответствие каждому ребру uÎU упорядоченную (или не­упорядоченную) пару вершин (n1,n2), называемых концами ребра u.

Множество vUu образует множество элементов графа. По количеству элементов графы делятся на конечные и бесконечные.

Если j(u)= (n1,n2) — упорядоченная пара, (т.е. (n1 ¹n2)Ù(n1,n2)¹ (n2,n1)), то ребро n называется ориентированным ребром или дугой, исходящей из вершины n1 (начало), и входящей в вершину n2 (конец дуги).

Если j(u)=(n1,n2) — неориентированная пара, то соответствую­щее ей ребро — неориентированное.

Граф с неориентированными ребрами называют неориентиро­ванным, а с ориентированными ребрами — неориентированным графом (орграфом).

Всякому графу G(v,u,j) можно сопоставить соотнесенный не­ориентированный граф , где — сопоставляет ребрам те же пары вершин, что и j, но неупорядоченные.

Граф, имеющий как ориентированные, так и неориентирован­ные ребра, называется смешанным.

Граф G=(v,u,j), ребрами которого являются всевозможными пары j(u)=(ni,nj) для двух возможных вершин ni,njÎV, называется полным неориентированным графом. Такие графы для трех, четырех и пяти вершин приведены:

Граф G=(v,u,j), в котором пара вершин соединяется несколькими (кратными) ребрамиб называется мультиграфом, а содержащий изолированные вершины — нуль-графом.

Дополнением графа G=(v,u,j) является граф Gк=(v,u,j), ребра которого совместно с графом G образуют полный граф.

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

Число ребер, связанных с вершиной ni (петля учитывается два­жды), называют степенью вершины.

 

Цепи и циклы графов

Цепь — конечная или бесконечная последовательность ребер S=(…n1,n2,…), в которой у каждого ребра nк одна из вершин явля­ется вершиной ребра nк-1, при этом ребро и одна из вершин могут встречаться несколько раз. Каждая цепь имеет начальную и конеч­ную вершину, остальные вершины называются внутренними (про­межуточными).

Цепь называется простой, если любое реьро не повторяется в цепи дважды. Составной (сложной) в противном случае; элементар­ной, если в ней ни одна из вершин не повторяется дважды.

Цикл — конечная цепь, начинающаяся и заканчивающаяся на той же вершине.

Цикл называется простым, если все его ребра различны, в ином случае — составным (сложным), и элементарным — если при об­ходе его ни одна из вершин не встречается дважды.

Цикл, не содержащий вершины, кроме той, на которой он начи­нается и заканчивается, называется петлей.

Цикл, у которого начальная и конечная вершины различны, на­зывается путем.

Он также может быть простым (никакая дуга не встречается дважды), составным или элементарным (никакая вершина не встре­чается дважды).

Длина пути — число ребер (дуг) в нем.

Цикл, начинающаяся и заканчивающаяся в начальной вершине, называется контуром.

Граф называется конечным, если число вершин его конечно, и бесконечным — в ином случае.

Граф Н(v,u,j) называется частичным для графа G(v,u,j), если все ребра и вершины графа Н, являются соответственно ребрами и вершинами графа G, т.е. если НÌG, то для всех n ÎV.

Нуль-граф считается частичным графом любого графа. Все частичные графы Нi для G(v,u,j) можно получить, выбирая в качестве ребер всевозможные подмножества ребер графа 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)ÇА для всех vÎV.

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

1 - Граф G(v).

2 - Подграф GА(А) графа G(v).

3 - Частичный подграф НА(А) графа G(v).

4 - Дополнительный частичный подграф НА(А) графа G(v).

 

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

Две вершины ni и nj неорганизованного графа G(v) называются связными, если существуюет цепь S с концами ni и nj. При прохож­дении пути через некоторую вершину nк более одного раза цикл в вершине nк можно удалять из цепи S.

Неориентированный граф называется связным, если любая пара его вершин связана. Отношение связности для вершин графа явля­ется отношением эквивалентности. Оно разбивает множество вер­шин графа на классы.

Подграфы, ''натянутые'' на эти классы вершин, называются компонентами связности графа. Другими словами, компонентами связности неориентированного графа G(v) называется подграф НА(А) с множеством вершин АÌv и множеством ребер в G(v), инцидентных только вершинам из А, причем ни одна из viÎA не смежна с верши­нами из множества vÇА.

Несвязный граф состоит из нескольких отдельных частичных подграфов:

В сильно связанном ориентированном графе для любой пары вершин обязательно существует соединяющий их путь. Компонентой сильной связности ориентированного графа G(v) называется сильно связанный подграф НА(А) с множеством вершин АÌv и множеством дуг, имеющих начало и конец в множестве А, причем ни одна из вершин viÎA и ни одна из вершин vjÎ vÇА не смежны между собой. Очевидно, что сильно связанный ориентированный граф имеет только одну компоненту сильной связности. Пример ориентированного графа, состоящего из 2-х компонент сильной связности, приведен ниже

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

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

Такой граф не имееи кратных ребер:

Ветвями дерева называются ребра графа, входящие в дерево.

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