Закон контрапозиции

(p ® q) = (~q ® ~p).

2.4 Построение заданных составных высказываний

В ряде практических случаев возникает необходимость построения составных высказываний с заданной таблицей истинности. Один из методов построения дает следующая теорема.

Теорема. Всякая логическая функция, кроме const "0", может быть представлена в виде дизъюнкции основных конъюнкций. Такое представление называется "совершенной дизъюнктивной нормальной формой" представляемой функции (СДHФ); const "0" можно представить как p /\ ~p.

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

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 Граф задан списком ребер.

ei	vi, vj
	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}.

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