Рекуррентные соотношения. Возвратные последовательности

Рекуррентным соотношением называется соотношение вида , которое позволяет вычислить все члены последовательности , если заданы ее первые k членов.

Пример 2.11. Формула задает арифметическую прогрессию.

Последовательность называется возвратной, если для всех n и некоторого k выполняется где p_i = const.

Пример 2.12. Геометрическая прогрессия – это возвратная последовательность, так как . Следовательно, выполняется

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

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

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

1. если l_i – корень кратности 1 (i =1,…, k), то общее решение имеет вид где c_i = const (i =1,…, k).

2. если l_i – корень кратности r_i (i =1,…, k), то общее решение имеет вид , где – произвольные константы (i =1,…, n, j =1,…, r_i).

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

Пример 2.13. Найти последовательность { a_n }, удовлетворяющую рекуррентному соотношению

Составим характеристический многочлен

Для нахождения корней сгруппируем слагаемые .

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

решая которую находим с₁ =1, с₂ = 1, с₃ =1. Таким образом, .

Алгебра логики

Булевы функции

Функцией алгебры логики или булевой функцией называется функция n переменных если аргументы функции являются булевыми переменными (т.е. ), и функция может принимать только два значения: 0 или 1. Таким образом, булева функция Булевы функции называются также переключательными функциями. Каждая комбинация значений аргументов булевой функции называется набором. Для функции n переменных количество разных наборов равно 2 ⁿ.

Булева функция задается таблицей истинности:

x 1	x 2	x 3	…	xn- 1	xn	f (x 1, x 2 ,…,xn)
			…			f (0,0,…,0,0)
			…			f (0,0,…,0,1)
…	…	…	…	…	…	…
			…			f (1,1,…,1,0)
			…			f (1,1,…,1,1)

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

x			f 1	f 2

Функции 0 и 1 называются соответственно тождественным нулем и тождественной единицей. Функция f ₁ называется тождественной функцией и обозначается через x. Функция f ₂ называется отрицанием x и обозначается .

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

 

x 1	x 2	f 3	f 4	f 5	f 6	f 7	f 8

Приведем обозначения и названия этих функций. Функция f ₃ называется конъюнкцией x ₁ и x ₂ и обозначается x ₁× x ₂. Функция f ₄ называется дизъюнкцией x ₁ и x ₂ и обозначается . Функция f ₅ называется суммой по модулю 2 и обозначается . Функция f ₆ называется импликацией и обозначается (читается x ₁ влечет x ₂). Функция f ₇ называется эквивалентностью и обозначается x ₁ ~ x ₂ (читается x ₁ эквивалентно x ₂). Функция f ₈ называется штрихом Шеффера и обозначается x ₁ |x ₂ (читается не x ₁ и x ₂).

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

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

Булева алгебра

Множество булевых функций с операциями (дизъюнкция), ×(конъюнкция), (отрицание) называется булевой алгеброй. Операция отрицание имеет самый высокий приоритет, затем идет конъюнкция, а затем дизъюнкция. Рассмотрим основные аксиомы булевой алгебры (в аксиомах x, y, z могут быть булевыми переменными или функциями).

1.

коммутативность

2.

ассоциативность

3.

идемпотентность

4.

свойства констант

5.

`0=1

аксиомы отрицания

6.

дистрибутивность

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

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

9.

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

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

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

1. поглощение

2. склеивание

Нормальные формы

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

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

Пример 3.1. , x ₁

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

Пример 3.2. ,

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

Пример 3.3. ,

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

Пример 3.4. ,

В примере видно, что является одновременно днф и кнф.

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

Пример 3.5. Найти днф, кнф для функции

– Днф.

– кнф.

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

Конституентой единицы k¹ набора называется конъюнкция всех переменных, образующих этот набор. Причем, переменная входит в конъюнкцию с отрицанием, если она на данном наборе равна 0 и без отрицания, если она равна 1. Конституентой нуля k⁰ данного набора называется дизъюнкция всех переменных, образующих этот набор. Переменная входит в дизъюнкцию без отрицания, если она на этом наборе равна 0 и с отрицанием, если она равна 1. Совершенная дизъюнктивная нормальная форма функции f – дизъюнкция k¹ тех наборов, на которых функция принимает значение 1. Совершенная конъюнктивная нормальная форма функции f – конъюнкция k⁰ тех наборов, на которых функция принимает значение 0. Представление функции в СДНФ или СКНФ единственно. Совершенные формы легко строить по таблице истинности.

Пример 3.6. Построим СДНФ и СКНФ для функции f, для которой задана таблица истинности.

x 1	x 2	x 3	f

Для построения СДНФ рассмотрим все наборы, на которых функция принимает значение 1, и выпишем для этих наборов все k¹:

, , , .

Тогда СДНФ имеет вид:

Для построения СКНФ рассмотрим все наборы, на которых функция принимает значения 0, и выпишем для этих наборов k⁰:

, , , .

Тогда СКНФ имеет вид:

Для построения СДНФ из ДНФ можно домножить элементарную конъюнкцию на (если переменная x_i отсутствует в элементарной конъюнкции) и применить закон дистрибутивности.

Пример 3.7. Найти СДНФ для функции

– СДНФ.

Для построения СКНФ из КНФ в элементарную дизъюнкцию, не содержащую переменную x_i, добавляем и применяем закон дистрибутивности.

Пример 3.8. Найти СКНФ для функции – СКНФ.

В дальнейшем для представления СДНФ функции f будем указывать номера k¹, на которых функция равна 1. Для определения набора необходимо перевести номер k¹ в двоичное число.

Пример 3.9. Пусть СДНФ функция f определяется следующим образом.

=

Переведем номера k¹ в двоичные числа

Таким образом, f обращается в 1 на наборах

(0,0,0,1), (0,1,0,1), (1,0,0,0), (1,0,1,1), (1,1,1,0).

Аналогично, для представления функции в СКНФ будем использовать запись с указанием номеров k⁰, на которых функция равна 0.

Пример 3.10. = .

Переведем номера k⁰ в двоичные числа

Функция f обращается в 0 на наборах

(0,0,1,0), (0,0,1,1), (0,1,1,1), (1,0,1,1).