Решение. Таблица основных конъюнкций для трех аргументов

Таблица основных конъюнкций для трех аргументов

p	q	r	Осн. конъюнкции	Строка ист.
			p /\ q /\r
			p /\ q /\~r
			p /\ ~q /\r
			p /\ ~q /\~r
			~p /\ q /\r
			~p /\ q /\~r
			~p /\ ~q /\r
			~p /\ ~q /\~r

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

Пример: Построить составное высказывание, которое истинно в строках 2 и 6 (т.е. с таблицей истинности 01000100).

A = (p /\ q /\ ~r) \/ (~p /\ q /\~r) – выбираем из таблицы основные конъюнкции из строк 2 и 6 и связываем их дизъюнкцией.

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

2.5 Отношения между высказываниями

Как было сказано выше, высказывание (простое или составное) полностью характеризуется таблицей истинности (число строк в этой таблице определяется по формуле 2ⁿ, где n – количество простых высказываний в составном высказывании). Значение в каждой строке – "0" или "1". Если возникает необходимость сравнить между собой два составных высказывания, то, естественно, сравниваются между собой таблицы истинности. Результатом этого сравнения будет установление вида бинарного отношения, которое связывает эти высказывания.

Так как в таблицах истинности только 0 и 1, то при построковом сравнении двух таких таблиц возможны следующие варианты:

Номер варианта	Вариант
	1 – 1
	1 – 0
	0 – 1
	0 – 0

Отсутствие всех вариантов просто невозможно. Отсутствие трех любых вариантов возможно, если сравниваются логические законы (частный случай). Из всех шести комбинаций отсутствия двух вариантов рассмотрим два: отсутствие вариантов 1 и 4; отсутствие вариантов 2 и 3. Общее название этих отношений – "2-отношения"; в первом случае название отношения "противоположность", во втором – "эквивалентность". Оставшиеся четыре комбинации будем называть "другие 2-отношения".

При отсутствии одного варианта (четыре случая) – общее название "простые отношения":

отсутствие варианта 1 – "Т-несовместимость";

отсутствие варианта 2 – "из А следует В";

отсутствие варианта 3 – "из В следует А";

отсутствие варианта 4 – "F-несовместимость",

где А – первое сравниваемое высказывание, В – второе.

Если при сравнении двух высказываний присутствуют все четыре варианта, то такие высказывания независимы (отношение – "независимы").

2.6 Аргументы

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

Одной из задач логики является проверка правильности аргументов.

Аргумент называется правильным, если конъюнкция посылок связана с заключением отношением "следует".

А /\ В /\ С "следует" D,

где А,В,С – посылки (составные высказывания);

D – заключение (составное высказывание).

Практически проверка правильности аргумента выполняется следующим образом: построить таблицы истинности для каждой посылки и заключения; для правильного аргумента каждой строке истинности посылок (строка, в которой каждая посылка имеет значение "1") должна соответствовать истинность заключения.

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

2.7 Задачи на построение таблиц истинности

Построить таблицы истинности для следующих составных высказываний:

	(p /\ q \/ ~r)		~(p /\ q /\ r)
	~(p \/ q /\ r)		r /\ p \/ ~r
	(~p \/ r) /\ ~q)		~p /\ ~q \/ ~r)
	~(p /\ ~q) \/ r)		(p /\ r) \/ (q \/~p)
	p /\ ~(q \/ r)		(q /\ ~(r /\ ~p)

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

3.1 Общие понятия и определения

Граф G как математический объект – это совокупность двух множеств: непустого множества вершин V и множества ребер E, элементы которого представляет собой неупорядоченные (для ориентированного графа – упорядоченные) пары элементов из множества V.

G (V,E) = áV; Eñ, n(V) > 0, E Ì V ´ V,

где для неориентированного графа E = E^–1 (бинарное отношение E симметрично).

Минимальный граф состоит из одной вершины.

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

Пусть v₁ и v₂ – вершины, e₁ = (v₁, v₂) – соединяющее их ребро.

Тогда вершина v₁ и ребро e₁ инцидентны, вершина v₂ и ребро e₁ также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными.

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

3.2 Способы задания графов

Множество вершин и множество рёбер для конечных графов задаются, как правило, перечислением. Возможно задание графа описанием отношения инцидентности.

1 Отношение инцидентности задано матрицей смежности:

– столбцы и строки матрицы – вершины графа;

– для смежных вершин элемент матрицы равен1, для остальных – 0;

– для неориентированного графа эта матрица всегда симметрична;

– число рёбер равно числу единиц выше или ниже главной диагонали матрицы (включая элементы на диагонали).

2 Отношение инцидентности задано матрицей инцидентности:

– столбцы матрицы соответствуют вершинам графа, а строки – рёбрам;

– если ребро e_i инцидентно вершине v_j, то элемент матрицы e_ij=1, в противном случае – e_ij = 0.

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

Для ориентированного графа при заполнении матрицы:

e_ij = –1,если v_j – начало ребра;

e_ij =1,если v_j –конец ребра;

e_ij = a (где a – любое число, кроме –1,1,0),если ребро – петля в вершине v_j_;

в остальных случаях e_ij= 0.

3 Граф задан списком ребер.

e_i	v_i,v_j
	a, b
	b, d
…	…

Примечание. Здесь e_i –ребро, v_i_,v_j – пара вершин, соединяемых этим ребром.

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

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

Граф H называют частью графа G, если множество вершин графа H принадлежит множеству вершин графа G и множество рёбер графа H принадлежит множеству рёбер графа G, т.е.:

V(H) Ì V(G); E(H) Ì E(G).

Часть графа H называется суграфом, если она содержит все вершины графа G.

Суграф H для неориентированного графа G называется покрывающим суграфом, если любая вершина последнего инцидентна хотя бы одному ребру из H.

Подграф G(U) графа G на множестве вершин U (U Ì V) – это часть графа, которой принадлежат все ребра с обоими концами из U.

Звёздный граф для вершины v (v Î G) состоит из всех рёбер с началом и концом в вершине v. Множество вершин звёздного графа состоит из вершины v и других смежных с ней вершин.

3.4 Операции с частями графа

1 Дополнение

Если задан граф G и его часть H, то дополнение части H

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

2 Объединение

H1 È H2 = H;

V(H) = V(H1) È V(H2), E(H) = E(H1) È E(H2),

где V(H), V(H1), V(H2), – множества вершин соответствующих графов;

E(H), E(H1), E(H2), – множества рёбер этих же графов.

H È H = G (объединение части графа и его дополнения).

3 Пересечение

H1 Ç H2 = H;

V(H) = V(H1) Ç V(H2), E(H) = E(H1) Ç E(H2) (если H1 и H2 не имеют общих вершин, то эта операция не определена).

Маршрутом в единичном связном графе G называется такая конечная последовательность ребер (e_1,e_2….e_n), в которой каждые два соседних ребра имеют общую инцидентную вершину.

Вершина v_о, инцидентная ребру e₁ и не инцидентная ребру e₂, называется началом маршрута в графе G.

Вершина v_n, инцидентная ребру e_n и не инцидентная ребру e_n_-1, называется концом маршрута.

Число ребер маршрута называется его длиной.

Если вершины v_о и v_n совпадают, то маршрут называется циклическим (или просто циклом).

Отрезок конечного или бесконечного маршрута сам является маршрутом.

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

Другими словами, в цепи ребро может встретиться не более одного раза, а в простой цепи вершина – не более одного раза.

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

Расстоянием между двумя вершинами графа называется минимальная длина простой цепи, связывающей эти вершины (обозначение d(v¢,v²)).

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

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

3.5 Диаметр, радиус и центр графа

Рассмотрим единичный связный неориентированный граф G.

Минимальная длина простой цепи с началом в v¢, и концом в v²называется расстоянием между этими вершинами.

Диаметр графа – максимальное из расстояний между любыми парами вершин графа: D(G) = max d(v¢,v²).

v',v" Î G

Если принять за точку отсчёта расстояний одну из вершин графа G (например v_i),то максимальное из расстояний от v_i до любой из вершин графа G называется удалением от этой вершины:

r( v_i ) = max d(v_j).

v_j Î G

Вершина v_i называется центром графа, если удаление от неё принимает минимальное значение(таких вершин в графе может быть несколько). Удаление от центра называется радиусом графа:

r(G) = min r(v_i).

v_i Î G

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

Рассмотрим на примере определение этих параметров графа (анализ графа на минимум).

Пример: Задан единичный неориентированный граф G:

V = {a, b, c, d, e, f}; E = {ab, ac, bc, cd, ce, de, ef}.

Определить диаметр, центр (центры) и радиус этого графа.

Для определения этих параметров изобразим граф и составим матрицу расстояний: (на пересечении столбца и строки (вершины графа) матрицы указывается расстояние между этими вершинами; такая матрица (выделена на рисунке) симметрична относительно главной диагонали).

В столбце с заголовком r( v_i ) укажем удаления от соответствующих вершин (максимальное значение расстояния каждой строки).

Вершины	a	b	c	d	e	f	r(v_i)	Центр
a								Нет
b								Нет
c								Да
d								Да
e								Да
f								Нет

Максимальное из удалений и будет диаметром графа (т.е. максимально возможным расстоянием между вершинами в исследуемом графе): D(G)= 3.

Вершины, для которых удаление r( v_i ) принимает минимальное значение (помечены в последнем столбце «Да»), являются центрами графа G, а значение удаления – радиусом графа:

r(G ) = 2.

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

3.6 Диаметр протяженности, радиус протяженности и центр протяженности графа

Рассмотрим единичный связный неориентированный граф G. Максимальная длина простой цепи с началом в v¢, и концом в v² называется протяженностью между этими вершинами (обозначается g(v¢,v²)).

Диаметр протяженности графа – максимальная из протяженностей между любыми парами вершин:

L(G) = max g(v¢,v²).

v',v" Î G

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

l ( v_i ) = max g(v_j).

v_j Î G

Центр(центры) протяженности – вершина с минимальным числом протяженности. Самые длинные простые цепи с началом в центре протяженности называются радиальными, а их длина – радиусом протяжённости графа.

l(G) = min l(v_i).

v_i Î G

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

Пример. Для анализа на максимум используем граф G из предыдущего примера: V={a, b, c, d, e, f}; E={ab, ac, bc, cd, ce, de, ef}. Определить диаметр протяженности, центр(центры) протяженности и радиус протяженности этого графа.

Для определения этих параметров изобразим граф G и составим матрицу протяженностей: (на пересечении столбца и строки(вершины графа) матрицы указывается протяженность между этими вершинами; такая матрица(выделена на рисунке) симметрична относительно главной диагонали).

В столбце с заголовком l(v_i) приводятся числа протяженностей для вершин, указанных в начале каждой строки (максимальное из значений протяженностей каждой строки). Максимальное из чисел протяженностей и будет диаметром протяженности графа (т.е. максимально возможной протяженностью между вершинами в исследуемом графе): L(G) = 5.

Вершины	a	b	c	d	e	f	l(v_i)	Центр
a								Нет
b								Нет
c								Да
d								Нет
e								Нет
f								Нет

Вершина с, для которой число протяженности принимает минимальное значение, является центром протяженности графа G, а значение числа протяженности вершины с – радиусом протяженности графа: l(G) = 3.

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

3.7 Задачи к главе 3

1 Задан граф G: V ={A, B, C, D, E, F}; E ={AB, AD, BC, DЕ, CE, EF}.

Привести графическое изображение этого графа, привести примеры суграфа, покрывающего суграфа, подграфа G(U) для вершин U={C,D,E} (с пояснениями) и звездного графа для вершины D. Определить диаметр, центр и радиус графа G.

2 Задан граф G: V ={A, B, C, D, E, F}; E ={ AB, CB, BE, BD, EF, FD}.

Привести графическое изображение этого графа, привести примеры для него суграфа, покрывающего суграфа, подграфа G(U) для вершин U={А,D,E} (с пояснениями) и звездного графа для вершины В. Определить параметры протяженности (диаметр, центр и радиус) этого графа.

3 Задан граф G: V ={ A, B, C, D, E, F}; E ={ AB, CB, BE, BD, EF, DЕ}.

Привести графическое изображение этого графа, привести примеры для него суграфа, покрывающего суграфа, подграфа G(U) для вершин U={А,B,E} (с пояснениями) и звездного графа для вершины F. Определить параметры протяженности (диаметр, центр и радиус) этого графа.

4 Задан граф G: V ={A, B, C, D, E, F}; E ={AB, AF, BE, BD, BC, FC, EF}.

Привести графическое изображение этого графа, привести примеры суграфа, покрывающего суграфа, подграфа G(U) для вершин U={F,D,E} (с пояснениями) и звездного графа для вершины A. Определить диаметр, центр и радиус графа G.

4 Теория конечных автоматов

4.1 Конечные автоматы – распознаватели

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

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

а) входной алфавит V конечного автомата (конечное множество входных символов, которые будет распознавать КА);

б) конечное множество состояний S;

в) начальное состояние КА – s ₀ (состояние, с которого начинает работу КА при обработке новой цепочки);

г) множество допускающих состояний – S _доп (подмножество состояний, с элементами которого сравнивается достигнутое КА состояние после прихода символа "конец цепочки");

д) таблица переходов (управляющая таблица), которая паре "текущее состояние – входной символ" ставит в соответствие новое состояние КА из множества состояний S).

Примечания:

1 В множество входных символов обязательно включают особый символ "конец цепочки", который сообщает КА о том, что достигнутое состояние s_i нужно сравнить с элементами множества S _доп и, если s_i Î S _доп, пропустить цепочку; в противном случае цепочка отвергается. В тексте этот символ будет иметь вид –|.

2 Часто при распознании цепочек возникает ситуация, когда невозможно текущей паре "состояние – входной символ" поставить в соответствие новое состояние. По сути это означает, что цепочка не принадлежит распознаваемому множеству, хотя она и не просмотрена до символа "конец цепочки". Такие ситуации в таблице переходов помечаются символом " Е " ("error"); попав в такое состояние, КА отвергает проверяемую цепочку и переходит в начальное состояние. В конкретных программных реализациях может вызываться обработчик ошибок, выдаваться сообщение о характере ошибки и т.п.

КА всегда начинает работу из начального состояния s ₀. Символы распознаваемой цепочки поступают посимвольно, начиная с первого, и изменяют состояния КА в соответствии с таблицей переходов. После поступления символа "конец цепочки" достигнутое автоматом состояние фиксируется и сравнивается с множеством допускающих состояний. На основании этого сравнения цепочка допускается или отвергается. По сути КА работает как фильтр, который пропускает "правильные" цепочки. Другая трактовка КА – компактный алгоритм распознания регулярных, в том числе и бесконечных множеств, который строит программист перед началом кодирования (реализацией алгоритма на конкретном языке программирования).

Построение КА для распознания заданного множества цепочек – процесс творческий и неоднозначный. Теоретически для распознания одного и того же множества цепочек можно построить бесконечное множество КА. Описанный выше принцип распознания применим далеко не ко всякому регулярному множеству. Он эффективен в следующих случаях:

– распознаваемые цепочки содержат определенные сочетания символов в начале, конце или (и) середине цепочки;

– распознаваемые цепочки содержат ограниченное число повторений определенных символов или их сочетаний (не больше n; точно n; не меньше n, причем n = 1,2,3);

– распознаваемые цепочки содержат запрет на определенные сочетания символов в начале, конце или (и) во всей цепочке;

– распознаваемые цепочки содержат комбинации названных выше ограничений.

4.2 Эквивалентные состояния КА

Состояния s и t двух различных конечных автоматов эквивалентны тогда и только тогда, когда первый КА, начав работу из состояния s, будет допускать те же цепочки, что и второй КА, начав работу из состояния t. Если эти состояния начальные, то эти автоматы эквивалентны (т.е. будут распознавать одни и те же множества).

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

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

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

Приведенное выше определение эквивалентных состояний не дает эффективного алгоритма поиска таких состояний.

Поиск эквивалентных состояний производится в процессе многократного разбиения множества состояний КА в зависимости от характера воздействия входных символов. Эта операция производится пошагово.

Шаг 1: множество состояний КА разбить на две подгруппы по воздействию символа "конец цепочки" (допускающие и отвергающие) и записать их в виде двух подмножеств; в каждом из полученных подмножеств все состояния по воздействию символа "конец цепочки" эквивалентны.

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

Шаг 3: выполнить разбиение подмножеств состояний на новые эквивалентные по входному символу подмножества, руководствуясь правилом – "оснований для разбиения подмножества нет, если все его элементы (состояния) переходят в одно подмножество".

Шаг 4: если в образованных подмножествах больше одного состояния, повторять шаг 2 до полного перебора всех входных символов; после завершения процесса два и больше состояния, входящие в полученные в конце подмножества эквивалентны между собой.

4.3 Недостижимые состояния КА

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

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

Шаг 1: записать одноэлементное множество, в которое входит начальное состояние.

Шаг 2: дополнить это множество состояниями, в которые переходит КА из состояний, уже присутствующих в множестве при воздействии любых входных символов.

Шаг 3: если на шаге 2 множество не пополняется новыми элементами, то получен исчерпывающий список достижимых состояний; остальные состояния КА недостижимы

Конечный автомат, в котором исключены недостижимые и эквивалентные состояния называется минимальным КА.

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

4.4 Недетерминированный конечный автомат

Недетерминированный конечный автомат (в дальнейшем НКА) представляет собой обычный КА с той разницей, что в таблице переходов паре "входной символ – состояние" ставится в соответствие множество состояний (а не единственное, как в КА) и начальных состояний может быть несколько. Такой автомат может получиться при решении конкретной задачи – построении распознавателя для регулярного множества. Единственный недостаток такого НКА, по сравнению с КА, невозможность простой программной реализации.

В процессе построения такого недетерминированного конечного автомата должны быть определены следующие параметры:

а) входной алфавит V (конечное множество входных символов и символ "конец цепочки");

б) конечное множество состояний S;

в) множество начальных состояний S _нач (подмножество состояний, с которых может начинать работу НКА при обработке новой цепочки);

г) множество допускающих состояний S _доп (подмножество множества состояний S, с которым сравнивается достигнутое НКА состояние после прихода символа "конец цепочки");

д) таблица переходов (управляющая таблица), которая паре "текущее состояние – входной символ" ставит в соответствие несколько новых состояний; если паре "текущее состояние – входной символ" нельзя поставить в соответствие ни одно состояние из множества S, то клетку таблицы переходов оставляют пустой.

Работу НКА можно интерпретировать двумя способами:

1 На некоторых шагах при распознании цепочки с помощью НКА есть множество выборов. Если имеется хотя бы одна последовательность состояний, при которой НКА заканчивает работу в допускающем состоянии, то такая цепочка будет допущена этим НКА.

2 При возникновении альтернативы во время работы НКА (в выборе начального состояния или перехода) автомат распадается на конечные автоматы по количеству альтернатив, которые работают параллельно. Если при поступлении символа "конец цепочки" хотя бы один из параллельно работающих КА находится в допускающем состоянии, то такая цепочка будет допущена этим НКА.

Существует процедура эквивалентного преобразования НКА в КА по следующему алгоритму (преобразуется таблица переходов НКА):

1 Для будущей управляющей таблицы эквивалентного КА изобразить столбцы по количеству входных символов и обозначить их входными символами.

2 В первую клетку первой строки занести как множество все начальные состояния НКА.

3 Заполнить остальные клетки этой строки (кроме последней): по таблице переходов НКА выписать в виде множеств все состояния, в которые переходят состояния, записанные в первой клетке через соответствующие входные символы.

4 В первой клетке очередной строки записать одно из новых множеств состояний, которые получены в п.3 при заполнении клеток таблицы переходов, и выполнить п.3.

5 Закончить процесс построения таблицы переходов после того, как будут исчерпаны все варианты множеств, которые появились в таблице.

6 При заполнении столбца с символом "конец цепочки" ставить "допустить", если в множество состояний первой клетки строки входит хотя бы одно допускающее состояние НКА, и "отвергнуть" – в противном случае.

7. Переобозначить множества состояний как новые состояния и заново заполнить таблицу переходов (получена таблица переходов эквивалентного КА).

8. Определить остальные параметры КА по полученной таблице переходов.

Описанную выше процедуру проиллюстрируем на конкретном примере.

Пример. НКА задан таблицей переходов: