Обход дерева. Понятие списка. Деревья и списки

 

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

1. Прямой (КЛП – корень, лево, право). Сначала мы учитываем корень, затем левое поддерево и правое поддерево. Это правило выполняется для каждой вершины, начиная с корня.

2. Обратный (ЛКП – лево, корень, право). Сначала мы учитываем левое поддерево, затем корень и правое поддерево. Это правило выполняется для всех вершин, начиная с корня.

3. Концевой (ЛПК – лево, право, корень). Сначала мы учитываем левое поддерево, затем правое и корень.

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

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

 

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

 

Задача 1. Обойти тремя способами бинарное дерево

 

 

Решение. 1. Прямой (КЛП). 1 2 4 5 8 3 6 9 7 10 11.

2. Обратный (ЛКП) 4 2 8 5 1 6 9 3 1 0 7 1 1.

3. Концевой (ЛКП) 4 8 5 2 9 6 1 0 1 1 7 3 1.

Задача 2. Нарисовать дерево, соответствующее списку:

а) (а); б) (а,b,с); в) (а,(b,с), (е,(f,k))).

 

 

Решение.

 

а) б) с)

k

f

е

с

b

а

а

 

 

 

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

 

Задача 1. Обойти тремя способами бинарное ордерево.

a

e

а) б)

l

m

k

d

q

f

c

b

а

n

p

m

l

b

e

f

d

c

k

 

 

Задача 2. Нарисовать дерево, соответствующее списку

а) (а,(b,(c,d)), (e,f),k);

б) (а,(b,(c,(d,e))), (k(l,m)),p);

в) ((a,b), (c,(d,e),(f,k))).

Задача 3. Написать список висячих вершин данного ордерева

а) б)

t

l

m

k

s

p

m

b

e

f

d

c

a

 

 

Задача 4. Найти глубину списка.

а) ((a,(b,(c,d))), (f,e),k); б) (a,(b,(c,(d,k))), (e,(f,((q,m),h)))).

 

ТЕМА 3. БУЛЕВЫ ФУНКЦИИ

Булевой функцией y=f(x ₁, x ₂,…, x _n) от n переменных x ₁, x ₂,…, x _n называется любая функция, в которой аргументы и функция могут принимать значение либо 0, либо 1, т.е. булева функция это правило, по которому по произвольному набору нулей и единиц (x ₁, x ₂,…, x _n) ставится в соответствие значение 0 или 1.

Вектором значений булевой функции у = f(x ₁, x ₂,…, x _n) называется упорядоченный набор всех значений функции f, при котором значения упорядочены по лексикографическому порядку.

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

1. Булева функция f(x ₁, x ₂,…, x _n), принимающая значение 1 на всех наборах нулей и единиц, называется константой 1, или тождественной единицей. Обозначение: 1.

2. Булева функция f(x ₁, x ₂,…, x _n), принимающая значение 0 на всех наборах нулей и единиц, называется константой 0, или тождественным нулем. Обозначение: 0.

3. Отрицанием называется булева функция одной переменной, которая определяется следующей таблицей истинности

х
f(x)

Обозначения: Ø х, . Запись Ø х читается «не икс» или «отрицание икс».

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

x
y
f(x,y)

Другие названия: логическое умножение (произведение); логическое «и».

Обозначения: х × у, х Ù у, min(x,y). Запись может читаться так: «икс и игрек» или «икс умножить на игрек».

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

x
y
f(x,y)

Другие названия: логическое сложение (сумма); логическое «или». Обозначение: хÚу, max(x,y).

Запись хÚу может читаться так: «икс или игрек» или «сумма икс и игрек».

6. Импликацией называется булева функция двух переменных, которая определяется следующей таблицей истинности

x
y
f(x,y)

Другое название: логическое следование.

Обозначения: х®у, хÞу, хÉу. Запись х®у может читаться так: из икс следует игрек».

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

 

x
y
f(x,y)

Обозначения: х ~ у, х «у, х º у.

Запись х ~ у может читаться так: «икс эквивалентно игрек» или «икс равносильно игрек».

8. Суммой по модулю_2 называется булева функция двух переменных, которая определяется следующей таблицей истинности

x
y
f(x,y)

Другое название: антиэквивалентность.

Обозначения: х Å у, х+у.

Запись х Å у может читаться так: «икс плюс игрек».

9. Штрих Шерифа это булева функция двух переменных, которая определяется следующей таблицей истинности

x
y
f(x,y)

Другое название: отрицание конъюнкции, логическое «не-и».

Обозначение: х | у.

Запись х | у может читаться так: «не икс или не игрек», «икс и игрек несовместны», «икс штрих Шеффера игрек».

10. Стрелка Пирса это булева функция двух переменных, которая определяется следующей таблицей истинности

x
y
f(x,y)

Другое название: отрицание дизъюнкции, логическое £ не - или ³.

Обозначение: х ¯ у.

Все логические операции можно выразить через три логические операции (конъюнкция, дизъюнкция, отрицание).

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

Определение. Две функции f ₁ (x ₁, …, x _n) и f ₂ (x ₂, …, x _n) называются равносильными, если они принимают одинаковое значение на одних и тех же наборах переменных. Функция от f ₁ (x ₁, …, x _n) называется тождественно-истинной, если она принимает значения 1 на всех наборах своих переменных. Функция f ₁ (x ₁, …, x _n) называется тождественно-ложной если она принимает значение 0 на всех своих наборах переменных.

Рассмотрим 3 основные группы равносильности.

1. Основные равносильности

· ;

· ;

· x* 1º x;

· ;

· x* 0º0;

· ;

· x * ;

· ;

· (закон двойного отрицания);

· (закон поглощения);

· (закон поглощения).

2. Равносильности, выражающие одни логические операции другими

· ;

· ;

· ;

· ;

· ;

· ;

· .

3. Равносильности, выражающие основные законы алгебры и логики

· ;

· ;

· ;

· ;

· ;

· .

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

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

 

Пусть рассматривается булева функция от n переменных x ₁, x ₂,…, x _n. Выражение (отрицание на любых местах) называют элементарной конъюнкцией (ЭК).

Дизъюнкция нескольких ЭК называется дизъюнктивной нормальной формой (ДНФ).

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

Если в ДНФ все ЭК правильны и полны, то ДНФ называют совершенной (СДНФ).

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

Алгоритм преобразования формулы в СДНФ:

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

.

2. Раскроем скобки и получим ДНФ.

3. Сделаем все ЭК правильными ( в последнем случае ЭК пропадает).

4. Сделаем все ЭК полными (если ЭК не содержит переменную х, то умножим ее на 1= х ).

5. Вернемся к шагу 2.

Через конечное число шагов получим СДНФ. В ней могут оказаться несколько одинаковых ЭК. Из таких ЭК составляем одну, согласно тождеству

Для того, чтобы получить СДНФ с помощью таблицы истинности, необходимо:

1. Записать таблицу истинности.

2. В последнем столбце таблицы истинности выбрать 1.

3. В исходном наборе, соответствующем 1 последнего столбца таблицы, запишем 0 отрицанием переменной, а 1 самой переменной.

4. Записываем СДНФ булевой функции.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1. Доказать, что булева функция (x®y)®((y®z)®(( ®z)) является тождественно истиной.

Решение.

 

x	y	z	x®y	y®z			(y®z)®((x y)	(x®y)®((y®z)®(( ®z))

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

Задача 2. Преобразовать в СДНФ булеву функцию, заданную формулой (х Þ у)(z+x).

Решение. Действуем по стандартному алгоритму:

1. Добьемся, чтобы в формуле остались только дизъюнкции, конъюнкции и отрицания аргументов: (х Þ у)(z+x)= .

2. Добьемся, чтобы конъюнкции выполнялись раньше дизъюнкций (раскроем скобки): = .

3. Делаем все элементарные конъюнкции правильными: .

4. Делаем все элементарные конъюнкции полными: =

5. Ликвидируем одинаковые элементарные конъюнкции:

Задача 3. Рассмотрим получение СДНФ с помощью таблицы истинности на предыдущем примере

х	у	z	x ® y	z D x	(x ® y)(z D x)

Решение. В последней колонки таблицы выбираем функции со значение 1.

По исходным наборам, с учетом алгоритма записываем СДНФ: