Программирование на языке Паскаль

q := q^.Next; ссылку - на следующий элемент

End;

WriteLn;

End;

Begin головная программа

ClrScr;

WriteLn(`Создание списка');

WriteLn;

Formir_spisok; обращение к процедуре создания списка

WriteLn(`Введено чисел: ', head^.Inf);

WriteLn(`Введенные числа:');

Vyvod_spisok; обращение к процедуре вывода списка

WriteLn;

WriteLn(`Удаление элементов из списка');

WriteLn;

New(r);

Repeat

WriteLn;

Write(`Удаляемый элемент: ');

ReadLn(poisk);

If (poisk = 0) если он равен нулю,

Then Break; то выходим из цикла удаления

flag := 0; флаг поиска равен нулю - удаляемый элемент пока не найден

q := head^.Next; поисковый указатель q - на первый элемент списка,

r := head; тормозной r - на голову списка

While (q <> Nil) Do пока не конец списка

If (q^.Inf = poisk) ищем нужный элемент

Then

Begin

flag := 1; если элемент найден:

Break; выходим из цикла поиска

End

Else

Begin

r := q; иначе подтягиваем r к q

q := q^.Next; и делаем шаг по списку

End;

If (flag = 0) Then если элемент не найден:

Begin

WriteLn(`Такого элемента в списке нет');

WriteLn(`Список:');

Vyvod_spisok; выводим список

Continue; и продолжаем цикл удаления

End;

r^.Next := q^.Next; если элемент найден,

Dispose(q); то удаляем его из списка и освобождаем память

head^.Inf := head^.Inf - 1; уменьшаем счетчик элементов на единицу

q := head^.Next; возвращаем указатели в голову списка

r := head;

If (head^.Inf = 0) Then если в списке не осталось элементов

Begin

WriteLn(`Список пуст');

Break;

End;

WriteLn;

WriteLn(`Новый список:');

Vyvod_spisok; выводим новый список

Until (poisk = 0); окончание цикла удаления элементов

WriteLn(`Список:');

Vyvod_spisok; выводим окончательный список

ReadLn;

End.

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



Сортированные списки

Широкое применение связные списки получили при решении задач сортировки последовательностей данных.

Пусть имеется связный список из трех чисел, расположенных по возрастанию от головы к хвосту списка: 3, 5, 12.

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

Var head, q, r, v: TPoint;

Остальные ссылки выполняют следующие функции:

head - ссылка на первый элемент списка,

r - поисковая ссылка,

v - всегда отстает от нее на шаг, используется для переадресации элементов списка.

Список сформирован, и значениями переменных head и r является ссылка на первый элемент списка, а переменная q отстает на шаг от r и ссылается на head:

Необходимо вставить элемент 7 на свое место в списке, то есть перед 12.

Для включения нового элемента в готовый список выполняются следующие действия:

1. создается новый элемент и заполняется его информационное поле:

New(v);

v^.Inf := 7;

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

While (r <> Nil) Do пока не дошли до конца списка

If (r^.Inf <= v^.Inf) Then если текущий еще меньше вставляемого,

Begin

q := r; то подтягиваем q к r

r := r^.Next; и делаем шаг по списку указателем r

End;

сейчас ссылка r указывает на элемент 12 , то есть r^.Inf = 12, q^.Inf = 5, и q указывает на элемент, после которого нужно вставить новый:



3. в ссылочное поле нового элемента помещается адрес, стоящий в ссылочном поле найденного элемента q (т.е. адрес следующего за ним элемента, в данном случае элемента 12):

v^.Next := q^.Next;

сейчас оба элемента (7 и 5) будут соединены с элементом 12,

4. в ссылочное поле найденного элемента 5 помещается адрес нового элемента 7:

q^.Next := v;

Пример: сформировать сортированный список из элементов 5, 3, 12, 7 и вывести его на экран (конец ввода - число 0).

Интерфейс:

Создание сортированного списка

Первое число: 5

Следующее число: 3

Следующее число: 12

Следующее число: 7

Следующее число: 0

Введено чисел: 4

Список:

3 5 7 12

Программа:

Program Sort_spisok;

Uses CRT;

Type TPoint = ^TElement;

TElement = Record

Inf: Integer;

Next: TPoint;

End;

Var head, q, r, v : TPoint;

Procedure Formir_sort_spisok;

Begin

New(head); head - указатель на голову списка

head^.Inf := 0; количество элементов в списке

head^.Next := Nil; списка еще нет

New(v); формируем первый элемент

Write(`Первое число: ');

ReadLn(v^.Inf); вводим его информационную часть

If (v^.Inf=0) если ввели 0,

Then Exit; то выходим из процедуры

head^.Inf := 1; в списке один элемент

v^.Next := head^.Next; вставляем его в голову списка

head^.Next := v; в head^.Next адрес первого элемента списка

New(r); r - поисковая ссылка

Repeat

New(v); формируем очередной элемент

Write(`Очередное число: ');

ReadLn(v^.Inf); вводим его информационную часть

If (v^.Inf=0) если ввели 0,

Then Break; то выходим из цикла ввода

head^.Inf := head^.Inf + 1; увеличиваем счетчик элементов на 1

r := head^.Next; поисковик r - на первый элемент списка

q := head; q - отстает на шаг

While (r <> Nil) Do пока не дошли до конца списка

If (r^.Inf <= v^.Inf) Then если текущий еще меньше

Begin вставляемого,

q := r; то подтягиваем q к r

r := r^.Next; и делаем шаг по списку

End

Else Break; иначе выходим из цикла поиска - место найдено

v^.Next := q^.Next; ставим новый элемент на место

q^.Next := v;

Until (v^.Inf = 0);

End;

Procedure Vyvod_spisok; процедура вывода списка

Begin

q := head^.Next; текущую ссылку - на первый элемент

While (q <> Nil) Do пока не конец списка

Begin

Write(q^.Inf:5); выводим очередной элемент

q := q^.Next; ссылку - на следующий элемент

End;

WriteLn;

End;

Begin головная программа

ClrScr;

WriteLn(`Создание сортированного списка');

WriteLn;

Formir_sort_spisok; обращение к процедуре создания списка

WriteLn(`Введено чисел: ', head^.Inf);

WriteLn(`Список:');

Vyvod_spisok; обращение к процедуре вывода списка

ReadLn;

End.

Бинарные деревья

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

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

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

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

Вершины графа обычно нумеруются или обозначаются прописными латинскими буквами: A. B, C, … Любой граф можно описать или задать перечислением вершин и ребер. Наиболее удобный способ такого задания - с помощью матрицы смежности, в которой строки и столбцы соответствуют вершинам графа, а значения элементов - длине ребер, соединяющих эти вершины. Если длина ребер не задается, то наличие ребра обозначается единицей, а его отсутствие - нулем.

Например, граф:

задается матрицей смежности:

Как видно, это симметричная матрица.

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



Для этого ориентированного графа матрица смежности имеет вид:

Говорят, что две вершины соединены путем, если из первой вершины можно пройти по ребрам во вторую вершину. Путей между вершинами может быть несколько, поэтому они обозначаются перечислением вершин, которые встречаются на данном пути. Например, вершины A и C графа:



соединены путями ABC, AC, ADC, AEDC, ABDC, AEDBC.

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

Связный граф, в котором нет циклов, называется деревом:

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

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

Из вершины A выходят три ребра - AB, AC и AЕ, в вершину D входит одно ребро - ED. Этот же граф можно описать следующей матрицей смежности:

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

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

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

Бинарное дерево - это такое ориентированное дерево, в котором:

из каждой вершины исходит не более двух ребер,

имеется только одна вершина - корень дерева, в которую не входит ни одного ребра,

в каждую вершину, кроме корня, входит только одно ребро.

Бинарные деревья обычно изображаются корнем вверх:



В этом бинарном дереве вершина A является корнем.

Для ребер бинарного дерева, выходящих из одной вершины, имеются две возможности - быть направленными влево-вниз или вправо-вниз: ребро BD направлено влево-вниз, а ребро DH - вправо-вниз.

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

Узел, не являющийся корнем ни одного поддерева, называется листом. В вышеприведенном дереве листьями являются узлы G, H, K. Характеристикой каждого узла является его уровень, определяемый следующим образом: корень дерева имеет нулевой уровень, уровень любого другого узла на единицу больше уровня узла-предшественника: узлы B,C имеют уровень 1, узлы D, E, F - уровень 2, узлы G,H,K (узлы) - уровень 3.

Глубина бинарного дерева - это максимальный уровень листа дерева, что равно длине самого длинного пути от корня к листу дерева.

Среди узлов различают предков и потомков: узел A является предком для узлов B и C, узлы G и H - потомками узла D. Поэтому корень дерева - это узел, не имеющий предков, а листья - это узлы, не имеющие потомков.

Бинарные деревья - это полезная структура данных в тех случаях, когда в каждой точке вычислительного процесса должно быть принято одно решение из двух возможных (альтернатива), например, в алгоритмах сортировки, когда требуется сравнение каждого очередного элемента (числа, слова) со всеми предшествующими. Использование бинарных деревьев позволяет уменьшить количество таких сравнений: берется первый элемент и помещается в исходный узел бинарного дерева, который становится его корнем с пока пустыми левым и правым поддеревьями. Каждый последующий элемент сравнивается с элементом, стоящим в корне дерева: если новый элемент меньше его, то он образует левый узел следующего уровня, а если больше или равен - то правый. Так продолжается до тех пор, пока сортируемая последовательность элементов не закончится. При этом получается, что самый левый лист будет содержать минимальный элемент из введенной последовательности, а самый правый - максимальный. Любой левый узел будет содержать элемент, меньший, чем элемент в предшествующем узле, а правый - больший или равный элементу в предшествующем узле.

Например, следующая последовательность чисел:

14 15 4 9 7 18 3 5 16 4 20 17 9 14 5

образует бинарное дерево:

В этом дереве самый левый лист содержит наименьшее число 4, а самый правый - наибольшее 20.

Если сейчас просмотреть это дерево в так называемом симметричном порядке - слева направо: левое поддерево - его корень - правое поддерево, то получим отсортированную последовательность:

3 4 4 5 5 7 9 9 14 14 15 16 17 18 20

Бинарное дерево можно представить связным списком, в котором каждое ссылочное поле каждого элемента (узла) должно содержать значения двух ссылок - на элемент (узел) слева внизу и элемент (узел) справа внизу. Если один из узлов отсутствует, то ссылка на него равна Nil. Самые нижние элементы списка (листья) имеют ссылки со значениями Nil:

Если информационные поля элементов дерева являются данными целого типа, то дерево можно описать, например, следующим образом:

Type TRebro = ^TUzel;

TUzel = Record

Data: Integer; информационное поле

Left, Right: TRebro; ссылочные поля

End;

Var root, q, v: TRebro;

Здесь объектами типа TUzel являются записи, в которых каждое ссылочное поле Left или Right равно либо Nil, либо ссылке на конкретную ячейку памяти компьютера, отведенную для объекта типа TUzel.

Дерево можно представить в виде множества объектов типа TUzel, связанных ссылками. Сами эти объекты соответствуют узлам дерева, а ссылки - его ребрам. Если при этом поле Left (Right) некоторого узла равно Nil, то это значит, что в дереве из этого узла не исходит ребро, направленное влево-вниз (вправо-вниз). Переход от вышестоящего к нижестоящему узлу совершается, как и в связных списках, присваиванием ссылочной переменной значения ее ссылочного поля, левого или правого. Этим способом можно просмотреть все узлы дерева сверху вниз. Включение нового узла в дерево осуществляется, как и включение нового элемента в связный список, изменением значений ссылочных полей соответствующих узлов. Вместе с каждым деревом рассматривается переменная, значением которой является ссылка на корень дерева (в нашем примере это root). Если в дереве нет ни одного узла, то значение этой переменной равно Nil.

Корень дерева можно создать, например, так:

New(root);

Write(`Первое число: ');

ReadLn(root^.Data);

root^.Left := Nil;

root^.Right := Nil;

После этого можно вводить сортируемую последовательность: очередное введенное число сравнивается с числом, стоящим в корне, и образует левый или правый узел следующего уровня. Ссылку v будем использовать для ввода нового элемента, ссылку q (поисковик) - для поиска места в дереве для нового элемента.

Пример: создать бинарное дерево для сортировки последовательности целых чисел. Ввести несколько чисел (см. выше) - конец ввода - число 0. Вывести введенную последовательность на экран.

Интерфейс:

Первое число: 14

Очередное число: 15

Очередное число: 4

Очередное число: 9……..

Очередное число: 0

Отсортированная последовательность:

3 4 4 5 5 7 9 9 14 14 15 16 17 18 20

Программа:

Program Bi_Tree;

Uses WinCRT;

Type TRebro = ^TUzel;

TUzel = Record

Data : Integer;

Left, Right : Rebro;

End;

Var root, q, v : TRebro;

Procedure Order(base: TRebro); процедура просмотра дерева

Begin

If (base <> Nil) Then

Begin

Order(base^.Left);

Write(base^.Data:5);

Order(base^.Right);

End;

End;

Begin

ClrScr;

New(root);

Write('Первое число: ');

ReadLn(root^.Data); первое число - в корень дерева

root^.Left:=Nil;

root^.Right:=Nil;

Repeat

Write('Очередное число: ');

New(v);

ReadLn(v^.Data);

If (v^.Data = 0) если очередное число - ноль,

Then Break; то выходим из цикла ввода

v^.Left:=Nil;

v^.Right:=Nil;

q:=Root; поисковик - в корень дерева

While (q <> Nil) Do пока не добрались до листа:

Begin

If (v^.Data < q^.Data) если введенное число меньше числа в очередном узле

Then If (q^.Left <> Nil) и левая ссылка узла не пуста,

Then q:=q^.Left то делаем шаг влево,

Else иначе

Begin если левая ссылка узла пуста,

q^.Left:=v; то подвешиваем туда очередное число

Break; и выходим из цикла поиска

End;

If (v^.Data >= q^.Data) если введенное число больше или равно числу в очередном узле

Then If (q^.Right <> Nil) и правая ссылка узла не пуста,

Then q:=q^.Right то делаем шаг вправо,

Else иначе

Begin если правая ссылка узла пуста,

q^.Right:=v; то подвешиваем туда очередное число

Break; и выходим из цикла поиска

End;

End; {While}

Until (False);

WriteLn;

Writeln('Отсортированная последовательность: ');

Order(root);

WriteLn;

ReadLn;

End.

Поиск заданного узла в дереве

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

Var poisk: Integer; искомое число

flag: 0..1; флаг поиска; flag=1 - число найдено

n: Word; количество найденных одинаковых чисел

Искомые числа вводить циклом до ввода 0 - конец поиска:

Что искать: 20

Такое число есть

Найдено чисел: 1

Что искать: 50

Такого числа нет.........

Что искать: 0

Конец поиска

Программа:

Program Bi_Tree;

Uses WinCRT;

Type TRebro = ^TUzel;

TUzel = Record

Data : Integer;

Left, Right : Rebro;

End;

Var root, q, v : TRebro;

poisk: Integer; искомое число

flag: 0..1; флаг поиска

n: Word; количество найденных одинаковых чисел

Procedure Formir_Tree; процедура формирования бинарного дерева

Begin

New(root);

Write('Первое число: ');

ReadLn(root^.Data); первое число - в корень дерева

root^.Left:=Nil;

root^.Right:=Nil;

Repeat

Write('Очередное число: ');

New(v);

ReadLn(v^.Data);

If (v^.Data = 0) если очередное число - ноль,

Then Break; то выходим из цикла ввода

v^.Left:=Nil;

v^.Right:=Nil;

q:=Root; поисковик - в корень дерева

While (q <> Nil) Do пока не добрались до листа:

Begin

If (v^.Data < q^.Data) если введенное число меньше числа в очередном узле

Then If (q^.Left <> Nil) и левая ссылка узла не пуста,

Then q:=q^.Left то делаем шаг влево,

Else иначе

Begin если левая ссылка узла пуста,

q^.Left:=v; то подвешиваем туда очередное число

Break; и выходим из цикла поиска

End;

If (v^.Data >= q^.Data) если введенное число больше или равно числу в очередном узле

Then If (q^.Right <> Nil) и правая ссылка узла не пуста,

Then q:=q^.Right то делаем шаг вправо,

Else иначе

Begin если правая ссылка узла пуста,

q^.Right:=v; то подвешиваем туда очередное число

Break; и выходим из цикла поиска

End;

End; {While}

Until (False);

End; конец процедуры формирования дерева

Procedure Order(base: TRebro); процедура просмотра дерева

Begin

If (base <> Nil) Then

Begin

Order(base^.Left);

Write(base^.Data:5);

Order(base^.Right);

End;

End; конец процедуры просмотра дерева

Begin основная программа

ClrScr;

Formir_Tree; обращение к процедуре формирования дерева

WriteLn;

Writeln('Отсортированная последовательность: ');

Order(root); обращение к процедуре просмотра дерева

WriteLn;

Repeat начало цикла поиска

Write(`Что искать: ');

ReadLn(poisk); ввод искомого числа

If (poisk = 0) если ввели 0,

Then Break; то выходим из цикла поиска

q:=root; поисковик - в корень дерева

flag:=0; еще ничего не найдено

n:=0; ни одного значения не найдено

While (q <> Nil) Do пока не добрались до листа:

Begin

If (q^.Data = poisk) Then если значение найдено:

Begin

flag:=1;

n:=n+1; количество найденных одинаковых значений

End;

If (poisk < q^.Data) спускаемся на следующий узел

Then q:=q^.Left

Else q:=q^.Right;

End; {While} дошли до листа

If (flag = 1)

Then

Begin

WriteLn(`Такое число есть');

WriteLn(`Найдено чисел: ', n);

End

Else WriteLn(`Такого числа нет');

Until (False); конец цикла поиска

ReadLn;

End.

Удаление узла из дерева

Задача удаления узла в сформированном дереве решается в следующем порядке:

поиск удаляемого узла

анализ найденного узла

Поиск удаляемого узла осуществим с помощью двух переменных-указателей: q - поискового, указывающего на найденный узел, и v, отстающего от него на уровень и всегда указывающего на корень удаляемого узла:

Var root, q, v, r : TRebro;

poisk: Integer; искомое число (узел)

flag: 0..1; флаг поиска: 1 - узел найден, 0 - не найден

Методика удаления узла будет зависеть от того, какого типа этот узел:

лист

узел с одним поддеревом,

узел с двумя поддеревьями.

Добавим в нашу программу процедуру удаления заданного узла. Сначала найдем заданный узел - на него будет указывать ссылка q:

Write(`Что удалить: ');

ReadLn(poisk); ввод удаляемого узла

If (poisk = 0) если это 0,

Then Break; то выходим из цикла удаления

q := root; поисковик q - в корень дерева

v := q; v отстает на шаг

flag := 0; еще ничего не найдено

While (q <> nil) Do пока не дошли до листа:

Begin

If (q^.Data = poisk) Then если нашли удаляемый узел:

Begin

flag:= 1; флаг поиска - на 1

Break; и выходим из цикла поиска

End; {If}

v:=q; если еще не нашли: подтянули ссылку v к поисковику q

If (poisk < q^.Data) и сделали шаг по дереву на уровень ниже

Then q:=q^.Left

Else q:=q^.Right;

End; {While}

Если удаляемый узел найден (flag=1), то начинается его анализ:

если это лист - то безболезненно его удаляем (q - указатель на удаляемый узел, v - указатель на его предка):

If (q^.Left = Nil) And (q^.Right = Nil) Then это лист

Begin

If (v^.Left = q) если он подвешен слева от предка,

Then v^.Left:=Nil то вместо него Nil,

Else v^.Right:=Nil; иначе Nil - справа от предка

Dispose(q); освобождаем от него память

{на продолжение}

End;

если у него слева - ничего нет, а справа - поддерево:



If (q^.Left = Nil) And (q^.Right <> Nil) Then

Begin

If (v^.Left = q) если он подвешен слева от предка,

Then v^.Left:=q^.Right то слева вместо него - правое поддерево узла q,

Else v^.Right:=q^.Right; иначе справа вместо него - правое поддерево узла q

Dispose(q); освобождаем от него память

{на продолжение}

End;

если у него справа - ничего нет, а слева - поддерево:

If (q^.Right = Nil) And (q^.Left <> Nil) Then

Begin

If (v^.Left = q) если он подвешен слева от предка,

Then v^.Left:=q^.Left то слева вместо него -левое поддерево узла q,

Else v^.Right:=q^.Left; иначе справа вместо него - левое поддерево узла q

Dispose(q); освобождаем от него память

{на продолжение}

End;

если у него и слева и справа - поддеревья. В этом случае нужно:

сделать шаг влево и идти до конца все время направо или

сделать шаг вправо и идти до конца все время налево.

q - ссылка на удаляемый узел,

r - ссылка на узел, который поставим на место удаляемого,

v - ссылка на предка узла r.

Найденным узлом r заменим удаляемый узел q :

If (q^.Right <> Nil) And (q^.Left <> Nil) Then

Begin

v:=q; подтягиваем указатель v к q

r:=q^.Right; ссылкой r делаем шаг вправо

от удаляемого узла

While (r^.Left <> Nil) Do идем все время налево до конца

Begin

v:=r; подтягиваем указатель v к r

r:=r^.Left; и делаем по дереву шаг влево

End; {While}

q^.Data:=r^.Data; помещаем вместо удаляемого узла q найденный самый левый на этом пути,

If (r^.Right = Nil)

Then v^.Left:=Nil а вместо него подвешиваем Nil

Else v^.Left:=r^.Right; или его правое поддерево

Dispose(r); освобождаем память от найденного узла

End;

Объектно-ориентированное программирование

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

Паскаль позволяет обрабатывать сложные структуры данных: числа, символы, массивы, строки, множества, файлы и записи. Это обеспечивается таким свойством языка, как возможность описания комплексных совокупностей различных базовых типов. Запись, например, позволила создавать программы по формированию и обработке файлов записей различной структуры - баз данных. Алгоритмы обработки информационных полей записей формируются в виде процедур и функций, что позволяет создавать достаточно эффективные программы. Однако зачастую, обрабатывая файлы записей, не удавалось реализовать алгоритмы обработки информационных полей небольшим количеством процедур, а сами процедуры сделать более наглядными. Это привело к необходимости появления таких конструкций, которые бы характеризовались не только информационным составом, но и методами обработки информационных полей. Была создана высшая абстракция данных - объекты и новая технология программирования - объектно-ориентированное программирование.

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

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

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

В основе объектно-ориентированного программирования лежат понятия объекта, инкапсуляции, наследования и полиморфизма.

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

Инкапсуляция - это соединение данных и подпрограмм их обработки в единой структурной единице, защищающее эти данные от некорректного использования. Эта структурная единица, как уже было сказано, является сложным описанием, задающим тип (он называется классом). Она позволяет использовать переменные данного класса - объекты. Представление данных скрывается внутри объектов, и они напрямую (непосредственно) недоступны пользователю. Доступ к ним (инициализация, изменение) возможен только с помощью специальных подпрограмм, образующих интерфейс класса. Это позволяет отделить использование операций от их реализации и упрощает программирование. Мы сталкивались с такой ситуацией в модулях, когда интерфейс и реализация подпрограмм модуля разъединены - интерфейс (Interface) открыт пользователям, а реализация подпрограмм - их текст (Implementation) - закрыт. Подпрограммы обработки данных объекта (методы) становятся такими же компонентами объекта, как и сами данные (поля). Это позволяет наделять объекты собственным поведением, реализуя их взаимодействие путем вызова интерфейсных подпрограмм.

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

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

Пример: создать программу, рисующую на экране точку (используется модуль Graph) и перемещающую ее на некоторое расстояние.

Program Tochka;

Uses CRT, Graph;

Var x, y, dx, dy: Word;

driver, regim: Integer;

Begin

driver:=detect; автоопределение графического драйвера

InitGraph(Driver,Regim,'C:\BP\BGI'); инициализация графического режима

SetBkColor(1); цвет фона - синий

ClearDevice; очистка экрана

SetColor(14); цвет фигур - желтый

x:=100; x и y - координаты точки

y:=150;

dx:=50; dx и dy - шаги по координатам

dy:=100;

PutPixel(x,y,14); рисуем точку желтым цветом

Delay(1000); задержка 1 сек

PutPixel(x,y,1); там же рисуем точку цветом фона

x:=x + dx; делаем шаг по координатам

y:=y + dy;

PutPixel(x,y,14); рисуем желтую точку на новом месте

Delay(1000);

ReadLn;

CloseGraph; закрываем графический режим

End.

Эта программа создана классическими методами с использованием переменных и процедур для работы с графическими объектами.

Создадим объект, включающий:

поля x и y - его координаты,

методы Init - инициализация - задание начальных значений координат,

Show - появление объекта на экране,

Hide - скрытие объекта,

Move - перемещение объекта на один шаг по координатам.

Поля объекта называются его свойствами. Для описания объектов в Паскале используется специальный тип Object:

Program Tochka;

Uses CRT, Graph;

Type TPix = Object

x, y: Word; координаты точки

Procedure Init(a, b: Word); инициализация объекта: a и b - его начальные координаты

Procedure Show; появление объекта

Procedure Hide; скрытие объекта

Procedure Move(da, db: Word); перемещение объекта: da и db - шаги по координатам

End;

Procedure TPix.Init; инициализация

Begin

x:=a; x и y - глобальные переменные

y:=b; a и b - входные переменные (формальные параметры) - начальные координаты объекта

End;

Procedure TPix.Show; появление

Begin

PutPixel(x,y,14); помещаем желтую точку по координатам x и y

End;

Procedure TPix.Hide; скрытие

Begin

PutPixel(x,y,1); помещаем синюю (цвет фона) точку по координатам x и y

End;

Procedure TPix.Move; перемещение

Begin

Hide; скрытие

x:=x + da; изменение координат

y:=y + db; x и y - глобальные переменные

da и db - входные переменные (формальные параметры) - шаги по координатам

Show; появление

End;

Var x0, y0, dx, dy: Word;

driver, regim: Integer;

pixel: TPix; создаем экземпляр объекта - переменную pixel

Begin

driver:=detect; автоопределение графического драйвера

InitGraph(Driver,Regim,'C:\BP\BGI'); инициализация графического режима

SetBkColor(1); цвет фона - синий

ClearDevice; очистка экрана

SetColor(14); цвет фигур - желтый

x0:=100; x0 и y0 - начальные координаты точки

y0:=150;

dx:=50; dx и dy - шаги по координатам

dy:=40;

pixel.Init(x0, y0); инициализация точки: задаем начальные координаты точки

pixel.Show; выводим точку на экран по заданным координатам

Delay(1000); пауза в 1 сек

Pixel.Move(dx, dy); перемещаем точку на dx,dy

Delay(1000); пауза в 1 сек

ReadLn;

CloseGraph; закрываем графический режим

End.

Таким образом:

1. в объекте TPix объединены описания его полей (свойств) и методов - инкапсуляция,

2. доступ к свойствам объекта возможен только через его методы; непосредственное обращение к полям противоречит принципам объектно-ориентированного программирования!

3. поведение объекта полностью определяется его методами Init, Show, Hide, Move,

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

5. перед началом работы с экземпляром объекта (точкой) необходима его инициализация - задание начальных координат точки.

Рассмотрим понятие наследования: используя объект TPix, создадим объект TRing для рисования и перемещения окружности, добавив в новый объект поле rad - радиус окружности и переопределив для нее методы Init, Show, Hide, доставшиеся от родительского типа. Это означает, что в обоих типах будут использованы методы с одними и теми же именами, но с различной реализацией. Поля x и y новый объект унаследует от старого - это будут координаты центра окружности:

Type TRing = Object (TPix) объект TRing - потомок объекта TPix

rad: Word; радиус окружности

Procedure Init(a, b, r: Word); инициализация объекта: a и b - координаты его центра, r - его радиус

Procedure Show; появление объекта

Procedure Hide; скрытие объекта

End;

Procedure TRing.Init; переопределенная инициализация

Begin

x:=a; x, y, rad - глобальные переменные

y:=b; a, b, r - входные переменные (формальные параметры) -координаты центра объекта и его радиус

rad:=r;

End;

Procedure TRing.Show; переопределенное появление

Begin

SetColor(14); цвет фигуры - желтый

Circle(x,y,rad); помещаем желтую окружность по координатам x и y

End;

Procedure TRing.Hide; переопределенное скрытие

Begin

SetColor(1); цвет фигуры - синий (цвет фона)

Circle(x,y,rad); помещаем синюю окружность по координатам x и y

End;

Далее поместим головную программу:

Var x0, y0, dx, dy, radius: Word;

driver, regim: Integer;

ring: TRing; создаем экземпляр объекта - переменную ring

Begin

driver:=detect; автоопределение графического драйвера

InitGraph(Driver,Regim,'C:\BP\BGI'); инициализация графического режима

SetBkColor(1); цвет фона - синий

ClearDevice; очистка экрана

SetColor(14); цвет фигур - желтый

x0:=100; x0 и y0 - начальные координаты центра окружности

y0:=150;

dx:=50; dx и dy - шаги по координатам

dy:=40;

radius:=10; радиус окружности

ring.Init(x0, y0, radius); инициализация окружности: задаем начальные координаты ее центра и радиус

ring.Show; выводим окружность на экран по заданным координатам

Delay(1000); пауза в 1 сек

ring.Move(dx, dy); перемещаем окружность на dx,dy

Метод ring.Move не был определен при описании объекта TRing, поэтому будет вызван метод родительского объекта pixel.Move - на экране переместится точка, а не окружность.

Таким образом, если метод объекта-предка не переопределен в объекте-потомке, то будет работать метод объекта-предка.

Вспомним описание этого метода:

Procedure TPix.Move; перемещение

Begin

Hide; скрытие

x:=x + da; изменение координат

y:=y + db;

Show; появление

End;

Можно заметить, что метод Move обращается к методам Show и Hide. Смысл этих обращений очевиден: сначала объект делается невидимым на экране (вызывается метод Hide), задаются его новые координаты, и он снова делается видимым (вызывается метод Show). Что произойдет, если метод Move использовать в программе одновременно с двумя экземплярами различных объектов: pixel и ring?

Метод Move наследуется объектом TRing от объекта TPix, а методы Hide и Show, поскольку сокрытие и показ окружности на экране осуществляются не так, как точки, в объекте TRing переопределяются с добавлением новой глобальной переменной rad и заданием цвета фигуры. Для точки при этом никаких осложнений не возникнет, поскольку все вызываемые методы Init, Show и Hide являются для нее родными.

Что касается окружности, то при вызове метода Ring.Move система пытается обнаружить метод с таким же именем в описании объекта TRing, и, не найдя его, продолжает поиски в объекте-предке TPix. В результате имеет место обращение к методу предка pixel.Move. После этого из метода Move вроде бы должны быть вызваны переопределенные методы ring.Hide и ring.Show. Однако этого не происходит: из унаследованного метода pixel.Move экземпляр объекта ring вместо ring.Hide и ring.Show вызывает одноименные методы объекта TPix: pixel.Hide и pixel.Show.

Это объясняется тем, что методы pixel.Move, pixel.Hide и pixel.Show жестко связаны, поскольку они были откомпилированы в едином контексте - объектном типе TPix. Другими словами, связь между этими методами, которая была установлена при компиляции, имеет статический характер. Поэтому в этом случае будет перемещаться точка, а не окружность.

Как сделать так, чтобы методы Hide и Show вызывались в зависимости от того, экземпляр какого объекта обращался к методу Move?

В этом случае используется механизм динамического (позднего) связывания - в отличие от статического (раннего) связывания. Указанный механизм реализуется с помощью виртуальных методов: заголовок виртуального метода в описании объекта-предка дополняется словом Virtual:

Procedure TPix.Show; Virtual;

Procedure TPix.Hide; Virtual;

Если в потомках этого объектного типа имеются переопределенные методы (методы с тем же именем), то они тоже должны быть объявлены в описании этих потомков как виртуальные и при этом иметь тот же набор формальных параметров, что и метод объекта-предка:

Procedure TRing.Show; Virtual;

Procedure TRing.Hide; Virtual;

В данном случае методы инициализации и перемещения объектов виртуальными не объявляются! В методах же инициализации экземпляров объектов Init вместо слова Procedure используется слово Constructor:

a) для объекта Tpix :

Constructor Init(a, b: Word); . . . . . . . . . . .

Constructor TPix.Init;

Begin

x:=a;

y:=b;

End;

b) для объекта Tring :

Constructor Init(a, b, r: Word); . . . . . . . . . . .

Constructor TRing.Init;

Begin

x:=a;

y:=b;

rad:=r;

End;

Теперь при использовании динамического связывания один и тот же метод Move будет работать по-разному (перемещает точку или окружность) - в зависимости от того, какой объект его вызывает. Именно это свойство объектов называется полиморфизмом.

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

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

Итак, для каждого типа объекта (класса объектов) создается только одна таблиц виртуальных методов, а отдельные экземпляры объекта содержат только адрес этой таблицы. Значение этого адреса и устанавливается процедурой, называемой конструктором. В ней вместо слова Procedure используется слово Constructor.

Таким образом:

конструктор определяется в каждом объектном типе, имеющем виртуальные методы,

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

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

сам конструктор виртуальным быть не может.

Доступ к полям объекта рекомендуется осуществлять не напрямую, а только с помощью методов. Такой подход гарантирует корректное использование данных объекта и их защиту от нежелательного доступа, который может повлечь непредсказуемые последствия. Поэтому поля и методы в описании объектного типа могут быть объявлены как скрытыми, так и общедоступными. Соответствующие разделы в описании объекта открываются директивами Private и Public:

Type TRing = Object (TPix) объект TRing - потомок объекта TPix

Private скрытые

rad: Word; радиус окружности

Public общедоступные

Constructor Init(a, b, r: Word); инициализация объекта: a и b - координаты его центра, r - его радиус

Private скрытые

Procedure Show; появление объекта

Procedure Hide; скрытие объекта

End;

Скрытыми объявлены: поле rad, процедуры Show и Hide. Общедоступен конструктор Init. Каждая очередная директива Private и Public отменяет действие предыдущей. Если в описании типа указанных директив вообще нет, то все поля и методы считаются общедоступными.

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

Полная программа, использующая два объектных типа TPix и TRing, свойства инкапсуляции, наследования, полиморфизма, виртуальные методы и конструкторы, может выглядеть так:

Program Pix_And_Ring;

Uses CRT, Graph;

Type TPix = Object

Private

x, y: Word; координаты точки

Public

Constructor Init(a, b: Word); инициализация объекта: a и b - его начальные координаты

Private

Procedure Show; Virtual; появление объекта

Procedure Hide; Virtual; скрытие объекта

Public

Procedure Move(da, db: Word); перемещение объекта: da и db - шаги по координатам

End;

Constructor TPix.Init; инициализация

Begin

x:=a; x и y - глобальные переменные

y:=b; a и b - входные переменные (формальные параметры) - начальные координаты объекта

End;

Procedure TPix.Show; появление

Begin

PutPixel(x,y,14); помещаем желтую точку по координатам x и y

End;

Procedure TPix.Hide; скрытие

Begin

PutPixel(x,y,1); помещаем синюю (цвет фона) точку по координатам x и y

End;

Procedure TPix.Move; перемещение

Begin

Hide; скрытие

x:=x + da; изменение координат

y:=y + db; x и y - глобальные переменные

da и db - входные переменные (формальные параметры) - шаги по координатам

Show; появление

End;

Type TRing = Object (TPix) объект TRing - потомок объекта TPix

Private

rad: Word; радиус окружности

Public

Constructor Init(a, b, r: Word); инициализация объекта: a и b - координаты его центра, r - его радиус

Private

Procedure Show; Virtual; появление объекта

Procedure Hide; Virtual; скрытие объекта

End;

Constructor TRing.Init; переопределенная инициализация

Begin

x:=a; x, y, rad - глобальные переменные

y:=b; a, b, r - входные переменные (формальные параметры) -координаты центра объекта и его радиус

rad:=r;

End;

Procedure TRing.Show; переопределенное появление

Begin

SetColor(14); цвет фигуры - желтый

Circle(x,y,rad); помещаем желтую окружность по координатам x и y

End;

Procedure TRing.Hide; переопределенное скрытие

Begin

SetColor(1); цвет фигуры - синий (цвет фона)

Circle(x,y,rad); помещаем синюю окружность по координатам x и y

End;

Var x0, y0, dx, dy, radius: Word;

driver, regim: Integer;

pixel: TPix; создаем экземпляр объекта TPix - переменную pixel

ring: TRing; создаем экземпляр объекта TRing - переменную ring

Begin

driver:=detect; автоопределение графического драйвера

InitGraph(Driver,Regim,'C:\BP\BGI'); инициализация графического режима

SetBkColor(1); цвет фона - синий

ClearDevice; очистка экрана

SetColor(14); цвет фигур - желтый

x0:=100; x0 и y0 - начальные координаты центра окружности

y0:=150;

dx:=50; dx и dy - шаги по координатам

dy:=40;

radius:=10; радиус окружности

ring.Init(x0, y0, radius); инициализация окружности: задаем начальные координаты ее центра и радиус

ring.Show; выводим окружность на экран по заданным координатам

Delay(1000); пауза в 1 сек

ring.Move(dx, dy); перемещаем окружность на dx,dy

x0:=200; x0 и y0 - начальные координаты точки

y0:=250;

dx:=80; dx и dy - шаги по координатам

dy:=50;

pixel.Init(x0, y0); инициализация точки: задаем начальные координаты точки

pixel.Show; выводим точку на экран по заданным координатам

Delay(1000); пауза в 1 сек

Pixel.Move(dx, dy); перемещаем точку на dx,dy

Delay(1000); пауза в 1 сек

ReadLn;

CloseGraph; закрываем графический режим

End.



Приложение 1

Основы алгебры логики

Логика как искусство рассуждений зародилась в глубокой древности. Начало науки о законах и формах мышления связывают с именем Аристотеля - величайшего древнегреческого философа, жившего в эпоху Александра Македонского около 2400 лет назад.

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

Прошло два тысячелетия, прежде чем Лейбниц предложил ввести в логику математическую символику и использовать ее для логических построений. Эту идею последовательно реализовал в XIX веке английский ученый Джордж Буль, положив тем самым основы математической логики (алгебры логики, булевой алгебры).

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

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

“Джордж Буль - создатель математической логики” - истинное,

“2>5” - ложное,

“Я легко выполню все тесты по Паскалю” - тоже ложное.

Высказывания обозначаются прописными латинскими буквами: A, B, C,…

Различают простые и сложные высказывания. Примеры простых высказываний приведены выше. Сложные высказывания представляют собой определенные сочетания простых. Истинность или ложность сложного высказывания зависит от истинности и ложности составляющих его простых высказываний.

Итак, высказывания могут принимать одно из двух значений:

истина

ложь

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

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

К основным логическим операциям относятся:

отрицание (инверсия)

конъюнкция

дизъюнкция

импликация (следование)

эквивалентность.

Логическая функция НЕ (отрицание)

Эта функция означает отрицание высказывания А и читается “НЕ А”.

В литературе она обозначается как или ¬А.

Отрицанием высказывания А называется сложное высказывание НЕ А, которое истинно, когда А ложно, и ложно, когда А истинно.

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

А
0	1
1	0

Пример: высказывание А=”сегодня среда”,

его отрицание =”сегодня Не среда”,

или =”неверно, что сегодня среда”.

Логическая функция И (конъюнкция - логическое умножение)

Соединение двух простых высказываний А и В в одно сложное с помощью союза И называется конъюнкцией или логическим умножением.

В литературе операция конъюнкции обозначается как & или ^.

Конъюнкцией двух высказываний А и В (A&B) называется сложное высказывание, которое истинно, если оба составляющих его высказывания истинны, и ложно, если хотя бы одно из них ложно:

A	B	A&B
0	0	0
0	1	0
1	0	0
1	1	1

Пример: высказывание А=”число Х делится без остатка на 2”,

высказывание В=”число Х делится без остатка на 3”,

конъюнкция этих высказываний A&B=” число Х делится без остатка на 2 И число Х делится без остатка на 3” - это признак делимости числа на 6.

Логическая функция ИЛИ (дизъюнкция - логическое сложение)

Соединение двух простых высказываний А и В в одно сложное с помощью союза ИЛИ называется дизъюнкцией или логическим сложением.

В литературе операция дизъюнкции обозначается как + или \/.

Дизъюнкцией двух высказываний А и В (A+B) называется сложное высказывание, которое истинно, если хотя бы одно из составляющих его высказываний истинно, и ложно, когда оба высказывания ложны:

A	B	A+B
0	0	0
0	1	1
1	0	1
1	1	1

Пример: высказывание А=”сегодня среда”,

высказывание В=”сегодня НЕ среда”,

дизъюнкция этих высказываний A+B=” сегодня среда ИЛИ сегодня НЕ среда” - это любой день недели.

Логическое следование (импликация)

Соединение двух простых высказываний А и В в одно сложное с использованием оборота “если…, то…” называется логическим следованием или импликацией.

В литературе операция импликации обозначается как =>.

Пример: высказывание А=”завтра будет хорошая погода”,

высказывание В=”завтра поедем загорать”,

импликация A=>B = “ЕСЛИ завтра будет хорошая погода, ТО завтра поедем загорать ”.

Будем считать это сложное высказывание договором. Этот договор не будет выполнен только в одном случае: если завтра будет хорошая погода, а мы не поедем отдыхать. В остальных случаях этот договор выполняется:

Импликацией двух высказываний “если А, то В” (A=>B) называется сложное высказывание, которое ложно тогда, когда первое высказывание истинно, а второе ложно:

A	B	A=>B
0	0	1
0	1	1
1	0	0
1	1	1

Импликацию можно представить через операции НЕ, И, ИЛИ:

A=>B ? + В

Логическое совпадение(эквивалентность)

Соединение двух простых высказываний А и В в одно сложное с использованием оборота “…тогда и только тогда, когда …” называется эквивалентностью.

В литературе операция импликации обозначается как - или ~.

Пример: высказывание А=”Х - четное число”,

высказывание В=”Х делится без остатка на два”,

эквивалентность A- B = “ Х - четное число тогда и только тогда, когда Х делится без остатка на два ”.

Эквивалентность A- B будет истинна только тогда, когда истинны или ложны оба составляющие ее высказывания одновременно:

A	B	A- B
0	0	1
0	1	0
1	0	0
1	1	1

Эквивалентность можно представить через операции НЕ, И, ИЛИ:



A- B ? & + A&В

Логические функции И, ИЛИ, НЕ образуют полную систему функций или базис - систему логических функций, позволяющую строить логические функции любой сложности.

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

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

закон исключенного третьего

закон противоречия

закон двойного отрицания

закон де Моргана

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

закон расширенной контрапозиции

закон перестановки посылок

закон силлогизма

Закон исключенного третьего

Этот закон выражается тавтологией:

А + ? 1

логическая сумма высказывания и его отрицания всегда истинна.

Закон исключенного третьего можно проверить таблицей истинности:



А		А+
0	1	1
1	0	1

Известна и латинская формулировка этого закона: “Tertium non datur”, что в переводе означает “Третьего не дано”.

Пример: высказывание А=”Сегодня пятница”,

высказывание =”Сегодня НЕ пятница”,

дизъюнкция этих высказываний А+ = “ Сегодня пятница ИЛИ сегодня НЕ пятница ”.

“НЕ пятница” означает любой другой день недели, кроме пятницы. Значит, сложное высказывание А+ говорит о том, что сегодня пятница ИЛИ любой другой день недели - оно всегда истинно. День недели - это или пятница, или НЕ пятница - третьего варианта не будет. Поэтому этот закон называется законом исключенного третьего.

...