Часть 2: Логика и теория графов
1: Что такое предложение? Говоря о том, что такое предложение, предложение - это утверждение, которое может судить об истинности или ложности. Как правило, заглавная буква может использоваться для представления предложения. Например:
Ответ: 3 — нечетное число.
В: Медь — это металл.
C:1+4=2
Результат очевиден и легко виден, истинностное значение высказывания А и высказывания В является истинным высказыванием, истинностное значение высказывания С является ложным высказыванием.
2: Что такое соединение?
Союз используется для образования одного предложения в составное предложение.Союз включает «не», «и», «или», «импликация», обычно символ «┐» означает «не», а символ «∧» означает «и», символ «∨» означает «или», а символ «→» означает «импликация».
Ниже приведена таблица истинности, вы можете посмотреть на приведенные определения этих связок:
Обобщите приведенные выше символы на языке:
1: При истинности предложений P и Q тогда и только тогда, когда составное предложениеP∧QИстинностное значение истинно, иначеP∧Qистинное значение ложно
2: Когда истинностные значения предложений P и Q оба ложны, тогда и только тогда, когда составное предложениеP∨Qистинное значение равно ложному, иначеP∨Qоба верны
3:когда предложениеPистинный и предполагаемыйQложно тогда и только тогда, когда составное предложениеP→QИстинное значение ложно. Другие случаиP→QОба верны.
4: Что касается союза «не», то предложение может быть отрицательным, когда предложениеPверно, то есть ┐Pявляется ложным.
3: Исчисление предложений
В соответствии с приведенными выше правилами докажите его исчисление высказываний следующим образом:
(1) ┐┐P =P
(2)P∨P P
P∧P P
(3)P∨Q Q∨P
P∧Q Q∧P
(4)P∨(Q∧R) (P∨Q)∧(P∨R)
P∧(Q∨R) (P∧Q)∨(P∧R) (5)P∨(P∧Q)P
P∧(P∨Q)P
(6)┐(P∨Q) ┐P∧┐Q
┐(P∧Q) ┐P∨┐Q
(7)P∨F P
P∧T P
(8)P∨T T
P∧F F
Два: картина
В этой части будут представлены некоторые основные понятия следующей теории графов, прежде всего, что такое граф, определение графа выглядит следующим образом:
1: Что такое изображение?
Граф состоит из тройки (V,E, ф), гдеVнепустое множество узлов,E— множество ребер, ψ — множество ребер изEк функции на узле, неупорядоченном четном или упорядоченном наборе четных.
Ниже приведен пример для иллюстрации:
Мы обнаружили, что ребра в графе всегда связаны с двумя вершинами, поэтому граф обычно представляется как двукратный, то есть G = (V, E), если реброekНет последовательного повышенияvi,vj> связано, то ребро называется неориентированным ребром. Рубианekи узел заказал пару vi,vj> связано, то ребро называется направленным ребром, гдеviдля стороныekначальный узел ,vjявляется конечным узлом.
И если каждое ребро в графе не имеет направления, граф можно назвать неориентированным графом, как в примере 1, если каждое ребро в графе является ориентированным ребром, граф называется ориентированным.Рисунок, как показано ниже:
На втором рисунке это действительно может быть представлено как G = (V, E):
V= {a,b,c,d}
E= {a,b>, a,d>, b,d>, b,c>, c,c〉}
В графе, если два узла связаны направленным ребром или ненаправленным ребром, эти два узла называются соседними узлами. Два ребра, связанные с одним и тем же узлом, вместе называются смежными ребрами. Ребро называется самозамыкающейся схемой, такой как (c, c) на приведенном выше рисунке является самозамыкающейся цепью.
Кроме того, при изучении свойств графов и локальной структуры графов очень важно понятие подграфов, об определении подграфов я хочу рассказать ниже:
РисованиеG=(V,E) и рисунокG1=(V1,E1), еслиV1 еVиE1∈E, это называетсяG1 естьGподграф ; еслиV1 =VиE1=E, это называетсяG1 естьGИстинный подграф ; еслиV1=VиE1∈E, это называетсяG1 естьGсгенерированный подграф.
В приведенном ниже примере (b) и (c) оба являются подграфами (a), а (b) является сгенерированным подграфом (a).
2: Реконструкция карты
Обычно геометрию графа можно изобразить несколькими различными способами, то есть геометрия графа не уникальна, но они описывают один и тот же граф. Если есть два графа с одинаковым количеством узлов и ребер, и отношения между узлами и ребрами также одинаковы, то эти два графа должны быть одинаковыми или изоморфными.
Определяется следующим образом:
рисунокG1 =(V1,E1) и рисунокG2 =(V2,E2), если существует биективная функцияf:V1→V2, иe=vi,vj>ДаGребро 1 тогда и только тогда, когдаe'=f(vi),f(vj)>ДаG2 называется ребромG1 иG2 изоморфизм, обозначаемый какG1 DG2.
Например:
Следующие два графа являются изоморфными графами, и \ используется для представления соответствующего
Соответствие узлу:
v1 \a
v2 \b
v3 \c
v4 \d
v2,v1>\b,a>
v4 ,v1>\ d,a>
v3 ,v4>\c,d>
v3 ,v2>\ c,b>
2: Пути и петли
Определение пути:
ориентированный графG=(V,E) представляет собой последовательность конечных реберe1,e2,…,en, где любая сторонаeiКонечный узел является ребромei+ 1 начальный узел, то такое ребро называется
последовательность - это графикGмаршрут из. Когда все ребра пути отличны друг от друга, он называется простым путем, когда все ребра пути различны, он называется простым путем;
Когда все узлы отличаются друг от друга, это называется базовым путем.
Например, на изображении ниже:
P4 = (v1 ,v2>,v2 ,v4>,v4 ,v2>,v2 ,v3>,v3 ,v4>,v4 ,v2>,
v2 ,v5>,v5 ,v1>) — цепь;P5 = (v1 ,v2>,v2 ,v3>,v3 ,v4>,v4 ,v2>,v2 ,v5>,v5 ,v1>)
простая схема;P6 = (v1 ,v2>,v2 ,v3>,v3 ,v4>,v4 ,v5>,v5 ,v1>) является основой
эта схема.
Длина пути:
В пути количество содержащихся ребер называется длиной пути.
В ориентированном графе, если есть подчиненный узелviк узлуvjпуть, вызывается изviприбытьvjдоступен. будетviМножество всех достижимых узлов называетсяviмножество достижимых узлов.
В ориентированном графе, если каждая пара узлов различнаviиvjвзаимно достижимы, то такой граф называется сильно связным графом.
3: Матричное представление графика:
определение:
ПредполагатьG= (V,E) — ориентированный граф,V= {v1 ,v2,…,vn}, определитеn×nматрицаA,AЭлементыaij, и имеет
называется матрицейAэто картинаGматрица смежности .
4. Степень узла
В ориентированном графе количество ребер, введенных в узел, называется входной степенью узла, а количество ребер, испущенных узлом, называется исходящей степенью узла. Сумма степени входа и степени выхода узла называется степенью узла. В неориентированном графе количество ребер, связанных с узлом, называется степенью узла.
5: дерево
Дерево — это ориентированный граф без петель.Ориентированный граф без петель означает, что в ориентированном графе нет петель. Среди них узел, степень входа которого равна 0, называется корневым узлом, а узел, степень исхода которого равна 0, называется листом. Следовательно, узлы в графеaи узелfявляется корневым узлом, а узелb,dиgЭто листья.
Определяется следующим образом:
Если ориентированный графT, есть только один узелvимеет степень входа 0, все остальные узлы имеют степень входа 1, а подчиненный узел имеет степень входа 0.vВыезд, чтобы добратьсяTКаждый узел в называетсяTЭто направленное дерево или корневое дерево.TУзел со степенью вхождения 0vэто корень дерева,TУзел, степень входа которого равна 0, является листом дерева, а другие узлы, степень входа которых равна 1, называются узлом ветви (или внутренним узлом) дерева.
Например, все деревья, показанные на рисунке ниже, являются деревьями с корнями. Изолированный узел также является ориентированным деревом.
Поскольку в ориентированном дереве нет петель, все пути в дереве являются элементарными путями. Длина пути от корневого узла до узла дерева называется уровнем узла.
В дереве, показанном на рисунке (а) выше, уровень корневого узла 1 равен 0, количество уровней узлов 2, 5 и 6 равно 1, а количество уровней узлов 3, 4 и 7 равно 3. . При этом длину самого длинного пути в дереве называют высотой дерева.
В то же время для удобства можно использовать термины семейства для выражения отношений между узлами в дереве.vКаждый узел, достижимый из начальной точки, называетсяvПотомки , узлы, достижимые только одним ребром, называютсяvпрямые потомки (или сыновья).
Как видно из структуры направленного дерева, каждый узел дерева является также корнем поддерева данного дерева. Если вы удалите корень дерева и связанные с ним ребра, вы получите несколько поддеревьев, а корнями этих поддеревьев являются узлы на первом уровне.
В ориентированном дереве, если исходящая степень каждого узла меньше или равнаm, скажем, деревоmмета-дерево; если исходящая степень каждого узла равнаmили 0, говорят, что дерево полноеmмета-дерево
когдаm= 2,mмета-дерево и завершитьmМета-деревья называются соответственно бинарными деревьями и полными бинарными деревьями. Для каждого узла ветви или корневого узла бинарного дерева существует не более двух поддеревьев, а именно левое поддерево и правое поддерево.
Например:
Используйте двоичное дерево для представления арифметического выражения ((a-c)/(b1+b2))+b3 *b4
Для компьютеров удобнее иметь дело с бинарными деревьями, поэтому упорядоченное дерево часто преобразуют в бинарное. Способ представления упорядоченного дерева с помощью двоичного дерева:
(1) За исключением сохранения самого левого узла ответвления, удалите все ответвления, которые растут из каждого узла, и соедините узлы в один слой с направленными ребрами слева направо.
(2) Для любого заданного узла его левый и правый потомки выбираются следующим образом: узел непосредственно под данным узлом, как левый потомок, для узла, примыкающего к данному узлу на той же горизонтальной линии, Как правый сын и так далее.
Что ж, приведенный выше контент охватил большую часть базовых знаний, необходимых для формальных языков и автоматов, а затем мы официально приступим к изучению формальных языков и автоматов.