Функции алгебры логики. Булевы функции.

Функции алгебры логики. Булевы функции.

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

Теорема 1 Имеется точно булевых функций от переменных.

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

1) – константа 0;

2) – константа 1;

3) – тождественная функция;

4) – отрицание х;

5) – конъюнкция x и y;

6) – дизъюнкция х и у;

7) – импликация х и у;

8) – эквивалентность х и у;

9) – сложение х и у по mod2;

10) – функция Шеффера;

11) – стрелка Пирса.

Переменная xi в функции называется фиктивной, если = при любых значениях остальных переменных. В этом случае функция, по существу, зависит от (n-1) – переменной, т.е. представляет собой функцию от (n-1) переменной. Говорят, что функция g получается из функции f удалением фиктивной переменной, а функция f получается из g введением фиктивной переменной, причем эти функции являются равными.

Равносильные формулы. Формулы алг логики

Приведем определение формулы алгебры логики.

1) каждая «элементарная» булева функция – формула;

2) если некоторое выражение N есть формула, то тоже формула;

3) если некоторые выражения M и N есть формулы, то выражения , , , тоже формулы;

4) других формул, кроме построенных по п.п.1), 2), 3), нет.

Две формулы N и M называются равносильными, если они определяют одну и ту же булеву функцию (запись N = M будет означать, что формулы N и M равносильны)

Очевидно, что отношение равносильности формул алгебры логики является:

1) рефлексивным, т.е. N = N для любой формулы N;

2) симметричным, т.е. если N = M, то M = N для любых формул N и M;

3) транзитивным, т.е. если N = M и M = J, то N = J для любых формул N,M,J.

Законы алгебры логики

1) – закон тождества; – закон противоречия; – закон исключительного третьего; – закон двойного отрицания; , – законы идемпотентности; , – законы коммутативности; , – законы дистрибутивности; , – законы ассоциативности;

2) , – законы де Моргана; , , , , – законы поглощения; , – законы склеивания.

Назовем формулу алгебры логики двойственной к формуле , если = .

 

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

Теорема 1 Если формулы алгебры логики N и M равносильны, то и двойственные им формулы N^* и M^* равносильны.

НОРМАЛЬНЫЕ ФОРМЫ

Пусть G – параметр, равный 0 или 1. Введем обозначение:

Проверкой легко установить, что x ^G = 1, тогда и только тогда, когда
x = G. Отсюда следует, конъюнкция равна 1 (здесь G равен 0 или 1) тогда и только тогда, когда . Например, конъюнкция (в которой G₂ = G₁ = 0, G₃ = G₄ = 1) равна 1 только в случае, когда x ₁ = x ₂ = 0, x ₃ = x ₄ = 1.

Теорема 1 Всякая булева функция f(x₁,x₂,…,x_n) может быть представлена в следующей форме:

, (3.1)

где 1 ≤ k ≤ n, в дизъюнкции берется по всем наборам значений переменных.

Разложением функции по всем переменным называется совершенной дизъюнктивной нормальной формой (сокращенная запись СДНФ) функции.

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

Формула вида (краткая запись ), где – конъюнкции называется дизъюнктивной нормальной формой (ДНФ).

Теорема 3 Для любой формулы алгебры логики существует равносильная ей дизъюнктивная нормальная форма.

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

Теорема 4 Для любой формулы алгебры логики существует равносильная ей конъюнктивная нормальная форма.

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

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

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

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

Метод Блейка

Метод Блейка для построения сокращенной ДНФ из произвольной ДНФ состоит в применении правил обобщенного склеивания и поглощения. Подразумевается, что правила применяются слева направо. На первом этапе производится операция обобщенного склеивания до тех пор, пока это возможно. На втором производится операция поглощения.

1. Метод Блейка состоит в применении двух правил:

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

б) поглощение – второе правило. Оно основано на равенстве

.

Находим в Д.Н.Ф. конъюнкции с минимальным числом сомножителей и все конъюнкции, их содержащие, вычеркиваем.

Пример: .

Разумно в Д.Н.Ф. сначала применить метод группировки (как более простой), а затем метод Блейка.

Построение минимального ДНФ

ДНФ назыв минимальной, если она включает минимальное число символов по сравнению со всеми другими эквивалентами ей ДНФ

Теорема 3 Минимальная ДНФ булевой функции получается из сокращенной ДНФ данной функции путем удаления некоторых элементарных конъюнкций.

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

В сокращенной ДНФ

элементарная конъюнкция поглощается дизъюнкцией остальных элементарных конъюнкций, т.е. .

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

Теорема 5 Всякая минимальная ДНФ является тупиковой.

1 Выделяются все максимальные интервалы, и строится сокращенная ДНФ.

2 Строятся все тупиковые ДНФ.

3 Среди всех тупиковых ДНФ выделяются все минимальные ДНФ.

Дальнейший алгоритм удобно реализовать методом импликантных матриц.

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

Для каждой находим набор такой, что .

Клетку импликантной матрицы, образованную пересечением i -строки и j -столбца отметим крестиком.

Чтобы получить минимальную ДНФ заданной функции, достаточно найти минимальное число , которое совместно накрывают крестиками все столбцы импликантной матрицы.

 

Машина Тьюринга

 

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

Лента разбита на ячейки. Во всякой ячейке в каждый момент времени находится в точности один символ из внешнего алфавита А={а₀,а₁,…а_n-1 }, n 2. Некоторый символ алфавита А называется пустым, любая ячейка, содержащая в данный момент пустой символ, называется пустой ячейкой.

Управляющее устройство в каждый момент времени находит в некотором состоянии q_i, принадлежащее множеству Q{q₀,q₁,…,q_r-1}, r 1. Множество Q называется внутренним алфавитом. Работа машины Тьюринга определяется программой. Программа состоит из команд. Каждая команда представляет собой выражение одного из следующего вида:

1) q_i a_j →q_k a_e;

2) q_i a_j →q_k a_e R;

3) q_i a_j →q_k a_e L.

Команда 1 заключается в том, что содержимое a_j обозреваемой на ленте ячейки стирается, а на его место дописывается символ a_e (который может совпадать с a_j), машина переходит в новое состояние q_k (оно может совпадать с предыдущим состоянием q_i). Команда 2 работает аналогично команде 1, и дополнительно сдвигает считывающую головку в соседнюю справа ячейку.Команда 3 работает аналогично команде 1, и дополнительно сдвигает считывающую головку в соседнюю слева ячейку.

Если считывающая головка находится в крайней справа (слева) ячейки ленты и происходит ее сдвиг вправо (влево), то к ленте пристраивается новая ячейка в пустом состоянии.

Машинным словом или конфигурацией называется слово вида

где А, q_k Q.

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

 

Функция называется вычислимой по Тьюрингу, если существует ма-шина Тьюринга, вычисляющая её.

 

Композиция машины Тьюринга

Поскольку машина Тьюринга—алгоритм, то операции композиции применимы и к машинам Тьюринга. Рассмотрим основные из них, а именно: произведение, возве-дение в степень, итерацию.

Тезис Тьюринга. Для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой нибудь алгоритм, когда функция явл вычислимой по Тьюрингу то есть когда она может вычисляться на подходящей машине Тьюрингаю.
Пусть заданы машины Тьюринга Т1 и Т2, имеющие какой-то общий внешний алфавит А = {а0, а1,..., аm} и внутренние алфавиты Q1 = {q0, q1,..., qn} и cоответственно Q2 = {q0,q1,…,qt}. Композитом, или произведением, машины Т1 на машину T2 будем называть машину Т с тем же внешним алфавитом А= {а0, а1,..., аm}, внутренним алфавитом Q = {q0, q1,...,qn, qn+1,...,qn+t} и программой, получающейся следующим образом. Во всех командах Т1 содержащих заключитель-ный символ q0, заменяем его на символ qn+1. Все остальные символы в командах T1 оставляем неизменными. В командах Т2, напротив, символ q0 оставляем неизменным, но зато каждый из остальных символов заменяем символом qn+j. Совокупность всех команд Т1 и Т2, измененных указанным способом, и будет программой композита или произведения машин T1 и T2.
Произведение машины T1 на машину Т2 обозначается через Т = T1 • T2, или
Т = T1 * Т2.
Таким образом, машина Т есть произведение машин Т1 и T2, если последовательная работа этих двух машин эквивалентна работе одной машины Т

Классы рекурсивных функций

В дальнейшем под множеством натуральных чисел N будем понимать множество N = {0,1,2,…,k,…}

Пусть y = f(x₁, x₂,…, x_n) – функция от n переменных. Обозначим D(y) – область определения функции y = f(x₁, x₂,…, x_n), E(y) – область значений функции y = f(x₁, x₂,…, x_n).

Функция y = f(x₁, x₂,…, x_n) называется числовой функцией, если:

1) D(y)=N ×∙ N ∙× …×∙ N = ;

2) E(y) N

Функция y = f(x₁, x₂,…, x_n) называется частично числовой функцией, если:

1) D(y) N ×∙ N∙×…×∙N = ;

2) E(y) N.

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

1) O(x) = 0 – нуль-функция

2) (x₁, x₂,…, x_n) = x_m, 1 ≤ m ≤ n – функция повторяющая значение своих аргументов;

3) S(x) = x+1 – функция следования.

Определим следующие три операции: суперпозиции, примитивной рекурсии и минимизации.

Операция суперпозиции

Будем говорить, что n – местная функция φ получается из m – местной функции ψ и n – местныхфункций f₁,f₂,…,f_m с помощью операции суперпозиции, если для всех x₁,x₂,…,x_n справедливо равенство:

φ (x₁,x₂,…,x_n) = ψ(f₁(x₁, x₂,…, x_n),…, f_m(x₁, x₂,…, x_n))

Функции алгебры логики. Булевы функции.

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

Теорема 1 Имеется точно булевых функций от переменных.

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

1) – константа 0;

2) – константа 1;

3) – тождественная функция;

4) – отрицание х;

5) – конъюнкция x и y;

6) – дизъюнкция х и у;

7) – импликация х и у;

8) – эквивалентность х и у;

9) – сложение х и у по mod2;

10) – функция Шеффера;

11) – стрелка Пирса.

Переменная xi в функции называется фиктивной, если = при любых значениях остальных переменных. В этом случае функция, по существу, зависит от (n-1) – переменной, т.е. представляет собой функцию от (n-1) переменной. Говорят, что функция g получается из функции f удалением фиктивной переменной, а функция f получается из g введением фиктивной переменной, причем эти функции являются равными.