Курс для творческих экспериментов (ТДО, 8)

Автомат Мили описывается следующими формулами: внутреннее состояние автомата в следующий момент времени зависит от внутреннего состояния автомата в настоящий момент времени и входного сигнала в настоящий момент времени: x(t + 1) = ф(х(А р(/)); выходной сигнал автомата в настоящий момент времени зависит от входного сигнала в настоящий момент времени и внутреннего состояния автомата в настоящий момент времени: X(t) = цp(t)); понятие состояния автомата в момент времени t определяется внутренним состоянием автомата и состоянием входа автомата в тот же момент времени: M(t) = (x(t), р(0)-

Автомат Мура. Для автомата Мура функции переходов и выходов выглядят следующим образом:

x(t + 1) = ф(х(/), р(0),

Mt + 1) = |/(х(Г + 1)) = |/(ф(х(0, р(0) = V'WO, Р(0)-

Функция выходов для автомата Мура определяется внутренним состоянием автомата.

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

Алгебра А = <М, S> — совокупность множества М с заданными на нем операциями S = {О_ь 0₂,..., О_п}. Множество Мназывается носителем алгебры, S — сигнатурой.

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

Асинхронный автомат — поведение определяется следующим уравнением: x(t + 1) = ф(x(t), p(t + 1)), ?.(t + 1) = V)f(x(t + 1), p(/ + 1)). В асинхронном автомате изменение состояния входа вызывает переход в следующее внутреннее состояние, т.е. внутреннее состояние автомата зависит от состояния входа в этот же момент времени; соответственно, состояние выхода автомата зависит от состояния его входа.

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

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

Бинарным отношением Т(М) на множестве М называется подмножество М² = М х М Т(М) с М².

Верхняя грань. Элемент х е У называется верхней гранью (точной верхней гранью) Xтогда и только тогда, когда он является наименьшим среди мажорант.

Вершинной связностью к («каппа») связного графа (7 называется наименьшее число вершин, которое нужно удалить, чтобы граф перестал быть связным.

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

Виды косвенных доказательств. Доказательство от противного, доказательство через контрпример, внесение противоречия.

Виды математических доказательств. Выделяется два вида доказательств — прямое и косвенное; при прямом доказательстве доказывается тезис, а при косвенном используется антитезис.

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

Вывод формулы (7 из формул Р_х, Б_ъ ..., Б_п — это такая последовательность формул Р_х, Б₂, ..., Б_п, что Р_п = (7, а любая формула Р/ — либо аксиома, либо исходная формула, либо непосредственный вывод из ранее полученных формул.

Выводимость. Пусть Р_х, Р₂, ..., Р„, (7 — формулы теории Т, т.е. Р_{, Р₂, ..., Р_п, СеР. Если существует такое правило вывода Я, что (Р_{, Р₂, ..., Р_п, (7) е Я, то говорят, что формула С непосредственно вы-

р р р

водима из формул Р_х, Р₂, ..., Р_п по правилу вывода Я: ————-Я, где формулы Р_х, Р₂, ..., Р_п называются посылками, а формула С — заключением.

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

Гипотеза. Если в теории Т существует вывод формулы (? из формул Г_и Г₂, ..., Г_п, то записывают Г_ь Г₂, ..., Г_п К (7, где /], Г₂, ..., —

гипотезы.

Графом (7 (в широком понимании) называется любая пара (К, ?/), где К = {у_1? у₂, ...} — множество элементов любой природы, а (7 = = {«(, и₂> •••} ^— семейство пар элементов из К, причем допускаются пары вида (у,-, у,-) и одинаковые пары.

Двудольный граф называется полным, если любые две вершины ИЗ К] И У₂ ЯВЛЯЮТСЯ смежными. Если |К(| = п_{, У₂ = п₂, то полный двудольный граф обозначается К_{п п} . Заметим, что граф К_{п п} имеет ровно п_{ + п₂ вершин и п_{п₂ ребер.

Двудольным называется граф (7(У, и) такой, что множество вершин У разбито на два непересекающихся подмножества У_х и У₂, причем всякое ребро и инцидентно вершине из У_х и вершине из У₂ (т.е. соединяет вершину из У_х с вершиной из У₂). Множества У₁ и У₂ называются «долями» двудольного графа.

Декартовым произведением двух бинарных отношений называется новое бинарное отношение, элементы которого удовлетворяют следующему условию:

я = я, х Я₂ = {((*, а), (у, Ь)) / (х, у) е Я, и (а, Ь) е Я₂}.

Декартовым произведением двух множеств А и В является новое множество С, элементами которого являются все упорядоченные пары (а, Ь),С = Ах В = {(а, Ь) / а е А, Ь е В).

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

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

Диаметром (1 связного графа (7 называется максимально возможное расстояние между любыми двумя его вершинами. Для несвязных графов диаметр полагается равным бесконечности.

Дизъюнкция а V Ь. Дизъюнкция ложна тогда и только тогда, когда ложны оба операнда. Соответствует союзу «ИЛИ».

Дизъюнктивная нормальная форма ДНФ — это сумма произведений, образованных из переменных и их отрицаний. ДНФ не содержит скобок.

Длиной пути называется число дуг (ребер) в этом пути. Расстоянием от у„ до у_ь в ориентированном графе называется длина наикратчайшего пути от у„ до у_ь. Если пути от V" до у_ь не существует, то расстояние от до у_ь называется бесконечным. Расстояние от у_а до у_ь будем обозначать 5(у_й, у_ь).

Доказательство «от противного» в математике — один из самых часто используемых методов доказательства утверждений. Дана последовательность формул б и отрицание А (б, А). Если из этого следует В и его отрицание (б, А, В, В, не-В), то можно сделать вывод, что из последовательности формул б вытекает истинность А. Иначе говоря, из ложности антитезиса следует истинность тезиса. Этот способ доказательства основывается на истинности формулы

((А —> В) & В) —> А в классической логике и законе двойного отрицания А - А.

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

Дополнением бинарного отношения Я(М) до универсума называется новое бинарное отношение /?(М),

я = {(*, у) / (х, у) ? /?}.

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

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

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

Задача полноты. Пусть М — некоторое множество автоматов. Определить, обладает ли совокупность автоматов, составляющих подмножество М' а М, свойством полноты. Иными словами, если ко всем автоматам подмножества М' конечное число раз применить операцию суперпозиции, совпадут ли М' и М?

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

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

Замыкание отношения относительно свойства. Рассмотрим два отношения /?, и R₂ на множестве М, R₂ обладает свойством S, S(R₂). Отношение /?, называется замыканием R₂ относительно свойства S тогда и только тогда: R_} обладает свойством SS(R), /?, является надмножеством R₂, R_} — наименьшее.

Изолированной называется вершина, у которой и полустепень захода, и полустепень исхода равны нулю.

Импликация я —> Ъ. Для операции импликации из лжи следует все что угодно, а из истины — только истина.

Интерпретацией формальной теории Т в область интерпретации М называется функция, h: F —> М, которая каждой формуле F теории Тоднозначно сопоставляет некое содержательное высказывание относительно объектов множества М. Это высказывание может быть истинно или ложно или не иметь истинностного значения. Но если оно истинно, то говорят, что формула выполняется в данной интерпретации.

Истоком называется вершина, полустепень исхода которой положительна, а полустепень захода равна нулю.

Исчисление — это формальная теория, в которой определены следующие компоненты: алфавит, формулы, аксиомы, правила вывода.

Квантор всеобщности. Под выражением /хР(х) понимаем высказывание, истинное тогда и только тогда, когда Р(х) истинен для каждого элементах из М, и ложное в противном случае. Это высказывание не зависит от х, его словесное выражение выглядит так: «Для любого х Р(х) истинно». Символ V называется квантором всеобщности.

Квантор существования. Под выражением ЗхР(х) понимаем высказывание, истинное тогда и только тогда, когда существует элемент х из М, для которого Р(х) истинен, и ложное в противном случае. Это высказывание не зависит от х, его словесное выражение выглядит так: «Существует х, для которого Р(х) истинно». Символ 3 называется квантором существования.

Классом М(монотонных) булевых функций /(х_1} х₂, ..., х„) называется множество функций, для которых выполняется условие, что на всех наборах s_] и s₂ при s_] > s₂ значение функции/(s_t) >fj(s₂).

Классом К₀ (сохраняющих константу 0) булевых функций /(х_ь х₂, ..., х_п) называется множество функций, для которых выполняется условие, что при нулевых значениях переменных функции принимают значение 0,/-(О, 0,..., 0) = 0.

Классом К_] (сохраняющих константу 1) булевых функций /(х_ь х₂, ..., х_п) называется множество функций, для которых выполняется условие, что при единичных значениях переменных функции принимают значение 1/(1, 1,..., 1) = 1.

Классом L (линейных) булевых функций/(х_ь х₂,..., х_п) называется множество функций, которые представимы полиномом Жегалкина первой степени fj(xJ, х₂, ..., х_п) = с₀ © С] &х_{ © с₂ &х₂ © ... © с_п &х_п.

Классом S (самодвойственных) булевых функций/(х_1? х₂, х„)

называется множество функций, для которых выполняется условие, что f* = fj, т.е. на всех противоположных наборах значения функции

противоположны:/(х_ь х₂,..., х_п) = fj(x_h х₂,..., х_п).

Классом эквивалентности К(х) элемента хде М, называется множество всех элементов у, у е М, с которыми х находится в отношении эквивалентности. К(х) = {у /х<=>у}. Отношение эквивалентности разбивает множество М на непересекающиеся классы эквивалентных между собой элементов, объединение которых совпадает с М.

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

Композицией двух отношений /?, и R₂ называется новое бинарное отношение Я(М), элементы которого удовлетворяют следующему условию:

R = R_{[R₂ = {(х, у) / 3z(x, z) е Я) И (г, у) е R₂).

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

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

ных методах создания программного обеспечения, основываясь на математике и компьютинге.

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

Конечный автомат — устройство, определенное конечным множеством состояний входов — Р = {р), р₂, ..., рдл}, конечным множеством состояний выходов — Л = {Л,,, Х₂, А.^}, конечным множе

ством внутренних состояний — 5 = {5|, в₂, ..., в_м}, а также функцией переходов, определяющей порядок смен внутренних СОСТОЯНИЙ (ф), и функцией выходов, задающих выходные состояния в зависимости от Р и 5 (|/): ? = (Р, 5, Л, ф, |/, 5₀).

Конституэнтой называется логическое произведение переменных или их отрицаний в виде

; 5,. а,. к-, если о,- =1,

&*/', где*,.' = к

/=1 [X/, если а,- = 0.

Конъюнктивная нормальная форма КНФ — это произведение сумм, состоящих из переменных и их отрицаний.

Конъюнкция а & Ь. Конъюнкция двух сомножителей истинна тогда и только тогда, когда истинны оба сомножителя. Соответствует союзу «И».

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

Критерий Поста—Яблонского. Для того чтобы система логических функций /’была функционально полна, необходимо и достаточно, чтобы она по совокупности не содержалась ни в одном из замкнутых классов К₀, К_ь М и /.

Левый нейтральный элемент. Элемент е є М называется левым нейтральным элементом, если Ух є М е ° х = х.

Линейный и частичный порядок. Если любые два элемента х, у є Т(М) находятся друг с другом в отношении упорядоченности х<уилиу<х,то это линейный порядок, в противном случае — частичный порядок.

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

Логические функции. В математической логике мы будем использовать только логические переменные, которые принимают значения либо 0 (ложь), либо 1 (истина). Функции, которые определены на этих переменных и принимают значения 0 или 1, также называются логическими или булевыми.

Мажоранта. Элемент х_т._у е У называется мажорантой {верхней границей или верхним конусом) X тогда и только тогда, когда для любого /х, х е X х < х_т..,.

Максимальный элемент. Элемент х_тах е X называется максимальным элементом Xтогда и только тогда, когда среди элементов Xне существует элементов, большихХ_тах, Т.е. -н(3у е X), Х_тах < у ИХ Ф у.

Другими словами, из сравнимости элементов х_тах е X и х е X вытекает, что х < х_тах.

Маршрутом {путем) в данном графе (7 называется конечная последовательность ребер вида {у₀, У}, {у, у₂}, {у_/и_₁, у_/л}, обознача

емая также через у₀ —> V! —> у₂ —>... —> у,„.

Математическая индукция — один из методов прямых доказательств. Обычно используется, когда нужно доказать некое утверждение для всех натуральных чисел. Для этого доказывается «первое утверждение» — база индукции и затем, доказывая, что если любое утверждение в бесконечной последовательности утверждений верно, то верно и следующее — шаг индукции.

Математическая логика — это наука о методах рассуждений, при которых мы отвлекаемся от содержания рассуждений, а используем только их форму и значение. Основным понятием математической логики является «простое высказывание».

Математическое доказательство. В математике доказательством называется цепочка логических умозаключений, показывающая, что при каком-то наборе аксиом и правил вывода верно некоторое утверждение. Таким образом, математическое доказательство представляет рассуждение, имеющее задачей обосновать истинность (конечно, в математическом, т.е. как выводимость, смысле) какого-либо утверждения.

Минимальный элемент. Элемент х_тт е X называется минимальным элементом Xтогда и только тогда, когда среди элементов Xне существует меньшихх_т(_П, т.е. —|(3у е X), у < х_т]п их Ф у.

Миноранта. Элемент х_ту е У называется минорантой {нижней границей или нижним конусом) X тогда и только тогда, когда для любого /х, х е X х_тц < х .

Множество — совокупность объектов, хорошо различимых нашей интуицией или мыслью, обладающих неким сходством и объединенных в одно общее.

Мост. Ребро и графа (7 называется мостом, если его удаление увеличивает число компонент связности графа.

Мощность множества — количество элементов в множестве (кардинальное число).

Мультиграф — граф, в котором имеется несколько парных ребер или однонаправленных дуг: и, = (у,-, у_у); и₂ - (у,-, у_у).

Мультипсевдограф — граф, в котором имеются петли и парные ребра или дуги.

Независимость. Система аксиом формальной теории называется независимой, если ни одна из аксиом не выводится из оставшихся.

Неориентированным графом С называется пара (К((7), ?/((7)), где К(С) — непустое конечное множество элементов, называемых вершинами, а [/(С) — конечное множество неупорядоченных пар элементов из К(С), называемых ребрами. Будем называть К((7) множеством вершин, а 17(0) — множеством ребер графа С. О каждом ребре вида (у₁₅ у₂) говорят, что оно соединяет вершины у_{ и у₂.

Непротиворечивость. Формальная теория семантически непротиворечива, если ни одна из ее теорем не является противоречием. Формальная теория формально непротиворечива, если в ней не являются

выводимыми одновременно формулы РиР.

Нижняя грань. Элемент х_1пГ е У называется нижней гранью (точной верхней гранью) X тогда и только тогда, когда он является наибольшим среди минорант.

Обращением /С¹ бинарного отношения Я(М) называется новое бинарное отношение /С¹ (Л/), удовлетворяющее следующему условию: Я~¹ = {(х, у) / (у, х) <е Я}.

Общезначимость. Формула общезначима (тавтология), если она истинна в любой интерпретации.

Объединением двух отношений Я_х и Я₂ называется новое бинарное отношение Я(М), элементы которого удовлетворяют следующему условию:

Я = Я_{ и Я₂ = {(х, у) / (х, у) е /г, ИЛИ (х, у) е Я₂.

Одноместным предикатом Р(х) называется всякая функция одной переменной, аргумент которой х определен на некотором множестве М, а значения функции определены на множестве {0, 1}. Множество М, на котором задан предикат, называется областью определения предиката. Множество 1_р, на котором предикат принимает только истинные значения, называется областью истинности предиката Р(х).

Ориентированным графом (7 называется пара (К((7), ?У((7)), где К((7) — непустое конечное множество элементов, называемых вершинами, а [/((7) — конечное множество упорядоченных пар элементов из У(0), называемых дугами (или ориентированными ребрами).

Основные результаты исследования исчисления высказываний. Проблема разрешимости для исчисления высказываний разрешима. Исчисление высказываний непротиворечиво. Исчисление высказываний полно в узком смысле, т.е. к системе аксиом нельзя добавить в качестве новой аксиомы недоказуемой в этом исчислении формулы. Исчисление высказываний полно в широком смысле, т.е. всякая тождественно истинная формула алгебры высказываний доказуема в исчислении высказываний. Система аксиом исчисления высказываний независима.

Особенности программной инженерии:

·                  • основанием программной инженерии является информатика, а не естественные науки;

·                  • основной упор делается на дискретную, а не на непрерывную математику;

·                  • управление производится абстрактными/логическими объектами вместо конкретных/физических установок;

·                  • отсутствие «производственной» фазы в традиционном промышленном смысле;

·                  • «Сопровождение» программного обеспечения в основном связано с продолжающейся разработкой или эволюцией, а не с традиционным физическим износом.

Отношение строгой упорядоченности. Если бинарное отношение Т{М) иррефлексивно, антисимметрично и транзитивно, то оно называется отношением строгой упорядоченности <, <{М).

Отношение тождества. Бинарное отношение и(М), заданное на множестве М, называется отношением тождества тогда и только тогда, когда оно состоит только из пар вида (я, а), а е М, т.е. /а е М(а, а) е и(М).

Отношение толерантности. Бинарное отношение ДА/), заданное на множестве М, называется отношением толерантности (схожести) тогда и только тогда, когда оно рефлексивно и симметрично.

Отношение упорядоченности. Бинарное отношение Т{М), заданное на множестве М, называется отношением упорядоченности тогда и только тогда, когда оно рефлексивно, антисимметрично и транзитивно. Обозначается отношение упорядоченности (порядка) как <<(М).

Отношение эквивалентности. Бинарное отношение Т(М), заданное на множестве М, называется отношением эквивалентности тогда и только тогда, когда оно рефлексивно, симметрично и транзитивно. Обозначается отношение эквивалентности как <=>.

Отрицание а. Отрицание лжи есть истина, отрицание истины есть ложь. Соответствует частице «НЕ».

Пересечение. Пересечением двух отношений У?! и Я₂ называется новое бинарное отношение /?(М), элементы которого удовлетворяют следующему условию: /? = /?, п /?₂ = {(х, у) / (х, у) е /?, и (х, у) е /?₂}.

Перестановками называют комбинации, состоящие из одних и тех же п различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок Р_п = п, где п = 1 • 2 • 3 •... • п.

Подграф. Граф = (У_и и_х) называется подграфом графа С = = (V, и), если К] является подмножеством V и и_{ является подмножеством и.

Подмножество. Множество Л называется подмножеством В, если каждый элемент а₁ из А, а₁ е А, принадлежит одновременно и множеству В, а₁ е В, А с В.

Полнота системы булевых функций. Система функций Р =

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

Полнота. Формальная теория называется полной, если каждому истинному высказыванию соответствует теорема теории.

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

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

Полустепеныо захода Б1:⁺(у) вершины у в ориентированном графе называется число дуг, входящих в данную вершину.

Полустепеныо исхода БГ(у) вершины у в ориентированном графе называется число дуг, выходящих из данной вершины.

Понятия математических доказательств. В теории математических доказательств выделяют следующие понятия: теоремы как доказуемые утверждения; гипотезы, если ни утверждение, ни его отрицание еще не доказаны; леммы как менее сложные утверждения, которые доказываются.

Правило подстановки. Пусть А — некая формула, выводимая (доказуемая) в исчислении высказываний, х — переменная, В — любая формула исчисления высказываний. Тогда формула, которая получается из формулы А путем подстановки в нее вместо переменной х формулы В, выводима (доказуема): А( х )(В //х).

Правило произведения. Если объект* можно выбрать из совокупности объектов т способами и после каждого такого выбора объект у можно выбрать п способами, то пара объектов (х, у) в указанном порядке может быть выбрана т ? п способами.

Правило суммы. Если некоторый объект * может быть выбран из совокупности объектов т способами, а другой объекту может быть выбран п способами, то выбрать либо а, либо у можно (т + п) способами.

Принцип двойственности. Отношение, обратное отношению упорядоченности, также является отношением упорядоченности.

Программная инженерия занимается разработкой систематических моделей и надежных методов производства высококачественного программного обеспечения, и данный подход распространяется на все уровни — от теории и принципов до реальной практики создания программного обеспечения, которая лучше всего заметна сторонним наблюдателям. Особое внимание уделяется анализу и оценке, спецификации, проектированию и эволюции программного обеспечения. Кроме того, в рамки данной дисциплины попадают вопросы, связанные с управлением и качеством, новизной и творчеством, стандартами, индивидуальными навыками и командной работой, а также профессиональной деятельностью, которые играют жизненно важную роль в программной инженерии. Программная инженерия является такой формой инженерии, которая применяет принципы информатики (computer science) и математики для получения рентабельных решений в области программного обеспечения.

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

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

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

Противоречие. Формула В, всегда ложная, называется тождественноложной формулой В- 0 или противоречием.

Противоречие. Формула называется противоречием, если она ложна в любой интерпретации.

Псевдограф — граф, содержащий петли. Петлей в неориентированном графе называется ребро вида (у_ь уД, которое соединяет вершину У] саму с собой; в ориентированном графе петлей называется дуга вида (у_1? уД, которая соединяет вершину у_] саму с собой.

Пустым называется граф, у которого множество ребер пусто. Будем обозначать пустой граф с п вершинами через Р_п.

Путем в ориентированном графе (7 от У( до у,„ называется последовательность ориентированных дуг (ребер) {у_ь у₂}, {у₂, у₃}, ..., {У/«-1, Ущ) такая, что конец каждой предыдущей дуги (ребра) совпадает с началом следующей и ни одна дуга (ребро) не встречается более одного раза. Если в ориентированном графе (7 нашелся путь от у_а до у_ь, то обратного пути от у_ь к у_й может и не быть.

Равенство множеств. Множества А и В равны, если являются подмножествами друг друга.

Равномощные множества, если их мощности равны.

Равносильность. Две формулы Ли В называются равносильными, если на одинаковых наборах они принимают одинаковые значения (А = В).

Разбиение множества X из п элементов на к блоков — это формирование множества 0= {/?!,..., В_к}, в котором В_х и В₂ и ... и в_к = х, В_і п В_] = 0, В_і * 0 для 1 < / <у < к. Обозначим множество всех разбиений множества Хнък блоков через ПДЛД, а через П(ЛД — множество все разбиений.

Размещениями называют комбинации, составленные из п различных элементов по т элементов, лежащих в промежутке от 1 до я, которые отличаются либо составом элементов, либо их порядком.

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

Расстоянием г между вершинами у, и у_у называется длина минимального пути между этими вершинами.

Реберной связностью к («лямбда») связного графа (7 называется наименьшее число ребер, которое нужно удалить, чтобы граф перестал быть связным. Для несвязного графа реберная связность равна нулю. Число реберной связности одновершинного графа также полагается равным нулю.

Регулярный граф. Граф, у которого все п вершин имеют одну и ту же степень, называется регулярным. Если степень каждой вершины равна /*, то граф называется регулярным степени г. Заметим, что регулярный граф степени г на п вершинах имеет ровно п ? — ребер.

- О_п+2 + М_п+ 2 - -^+1 + О_п+1,

= ^Рп₊ + ^Ргг

р

Рекуррентное соотношение: "⁺²

Лг+2

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

Свойствами алгоритма являются: дискретность шагов, детерминированность, регулярность, конечность, массовость.

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

Связь между исчислением высказываний и алгеброй высказываний.

Каждая формула, доказуемая в исчислении высказываний, тождественно истинна в алгебре высказываний. Каждая аксиома — тождественно истинная. Правило подстановки, примененное к тождественно истинным формулам, приводит к тождественно истинным формулам. Правило заключения, примененное к тождественно истинным формулам, приводит к тождественно истинным формулам.

Сильная связность. Любой граф можно разбить на непересека-ющиеся связные графы, называемые компонентами или компонентами связности графа (7. Внутри каждой компоненты будет выполняться определение связности графа.

Сложение Жегалкина а © Ь. Операция истинна тогда и только тогда, когда значения переменных различны.

Смешанным называется граф, содержащий как ориентированные, так и неориентированные ребра.

Собственное подмножество. Если во множестве В найдется ХОТЯ бы ОДИН элемент л:,-, который не принадлежит Л, X,- 6 В, XI Л, то Л собственное подмножество В, А а В. Пустое множество 0 всегда является подмножеством любого множества В.

Совершенная дизъюнктивная нормальная форма (СовДНФ).

V Х|°'х°²..,Х°", где Х,°' = Ху при о, = 1 ИХ_;°' = Ху при О у = 0.

/=1

Совершенная конъюнктивная нормальная форма (СовКНФ).

& (хГ¹ + х₂°² +... + х°"), гдех.^0/ /=0

= Ху при О У = 0 и х,°'

= Ху при о у = 1.

Соотношение Уитни. Для любого графа справедливо соотношение Уитни между реберной связностью А, вершинной связностью к и наименьшей из степеней вершин 8: к < А < 8.

Сочетание из п элементов по т — это неупорядоченный набор (множество) из т различных чисел, принадлежащих множеству X.

Степенью вершины у неориентированного графа (7 называется число ребер, инцидентных у, при этом степень вершины будем обозначать через Вершина степени 0 называется изолированной. Вершина степени 1 называется висячей или концевой.

Стоком называется вершина, полустепень захода которой положительна, а полустепень исхода равна нулю.

Таблица истинности представляет собой таблицу, устанавливающую соответствие между возможными значениями наборов переменных и значениями операции.

Тавтология. Формула А, всегда истинная, называется тождественно истинной формулой или тавтологией, Л-.

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

Теорема — формула, выводимая только из аксиом, без гипотез.

Теорема дедукции. Если Г — множество формул, Ли В — формулы из Г высказываний, А Ь В, то, Г Ь А —> В.

Теорема Дирака. Если в простом графе с п вершинами, причем п> 3, выполняется условие 81(у) > п / 2 для любой вершины у, то граф С является гамильтоновым.

Теорема о ДНФ. Всякая логическая функция, отличная от константы 0, может быть сведена к ДНФ.

Теорема о КНФ. Всякая логическая функция, отличная от константы 1, может быть сведена к КНФ.

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

Теорема Оре. Пусть п — количество вершин в данном графе. Если для любой пары несмежных вершин (у,-, у ) выполнено неравенство ЭДу,) + ВДу) > п, то граф является гамильтоновым.

Теорема Черча. Проблема разрешимости исчисления предикатов в общем виде неразрешима.

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

Трансфинитная индукция — метод прямых доказательств, обобщающий математическую индукцию на случай несчетного числа значений параметра. Трансфинитная индукция основана на следующем утверждении: пусть М — упорядоченное множество, Р(х) при х е М — некоторое утверждение. Пусть для любого X Е М из того, что Р{у) истинно для всех у < х, следует, что верно Р(х), и пусть верно утверждение Р(х), если х — минимальный элемент М, тогда утверждение Р(х) верно для любого X.

Формальная теория. Для определения формальной теории необходимо задать: множество А символов, образующих алфавит; множество слов F в алфавите А, которые называются формулами; подмножество В формул В е F, которые называются аксиомами; множество R отношений на множестве формул R е Fⁿ⁺ , которые называются правилами вывода.

Формула включений и исключений. Если Х_х, Х₂,..., Х_п — некоторые множества и их мощность равна |Л^|, Х₂,..., Х_п, тогда

+

I*, и1₂и ... и Х_п = 1^,1 + |Х₂| + ... + Х_п- {|Х, п Х₂ + Х_х п Х₃ + ??? + Х_п- п ^_w|} + {|^i п Х₂ п Х₃ + ... + Х_п_₂ n Х_п__х п Х_п} + + (-1)^Л_1|^, пХ₂п...пХ„.

Функция биекция. Функция F: Х^> Yназывается биекцией или взаимно однозначным соответствием, если она одновременно является инъекцией и сюръекцией (вложением и наложением).

Функция инъекция. Функция F: Х—> Yназывается инъективной, или инъекцией, или вложением, если она переводит разные элементы в разные, т.е. Vx е X и е X, х * z —> F(x) * F(z).

Функция сюръекция. Функция F; Х^> Yназывается сюръективной, или сюръекцией, или наложением, если множество ее значений есть все Y, т.е. Vy е Y Зх е X, у = F(x).

Функция. Бинарное отношение Fдекартова произведения Хх Y называется функцией, если для каждого элемента х е X найдется не более одного элемента у е Y такого, что (х, у) е F(x, у), т.е. выполняется свойство однозначности полученного результата.

Центром графа (7 называется такая вершина у, для которой максимальное расстояние между у и любой другой вершиной является наименьшим из всех возможных. Это расстояние называется радиусом Я. Таким образом, Я = гшп(тахг(У|, у₂)), где г(у_|5 у₂) — рас-

V, V,

стояние между У! И У₂.

Цепь. Маршрут (путь) называется цепью, если все его ребра различны. Маршрут (путь) называется простой незамкнутой цепью, если все вершины у₀, у_1? у₂, ..., У_т различны.

Цикл. Маршрут (путь) называется простой замкнутой цепью, или простым циклом, если все вершины у₀, у_ь у₂, ..., у,„ различны, кроме

П) = V

Цикломатическое число. Число удаленных в этой процедуре ребер называется цикломатическим числом графа С и обозначается через у((7).

Число размещений. Число упорядоченных т-элементных подмно-

и!

жеств множества А),, содержащего п элементов, равно А'" =-^:—.

(п-т)

Число сочетаний. Число неупорядоченных т-элементных подмножеств множества Х_п, содержащего п элементов, равно

С т _ __

т{п - т)

Шифр перестановки — преобразование символов исходного текста, в соответствии с которым происходит только изменение их порядка без изменения самих символов.

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

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

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

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

Эйлеровым циклом в графе называется цикл, содержащий все ребра графа.

Эквивалентность а <=> Ь. Операция истинна тогда и только тогда, когда значения переменных совпадают.

Элементы множества обозначаются маленькими латинскими буквами, сами множества — заглавными. Чтобы показать, что элемент а принадлежит множеству А, мы пишем а е А, в противном случае а

Ядром отношения Я на множестве М называется новое отношение /?[/Г'].