ТОП 10:

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



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

Функцией алгебры логики от переменных называется функция, принимающая значения 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. Введем обозначение:

Проверкой легко установить, что xG = 1, тогда и только тогда, когда
x = G. Отсюда следует, конъюнкция равна 1 (здесь G равен 0 или 1) тогда и только тогда, когда . Например, конъюнкция (в которой G2 = G1 = 0, G3 = G4 = 1) равна 1 только в случае, когда x1 = x2 = 0, x3 = x4 = 1.

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

, (3.1)

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

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

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

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

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

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

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

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

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

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

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


Метод Блейка

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

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

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

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

.

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

Пример: .

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 


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

 

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

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

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

1) qi aj →qk ae;

2) qi aj →qk ae R;

3) qi aj →qk ae L.

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

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

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

где А, qk 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(x1, x2,…, xn) – функция от n переменных. Обозначим D(y) – область определения функции y = f(x1, x2,…, xn), E(y) – область значений функции y = f(x1, x2,…, xn).

Функция y = f(x1, x2,…, xn) называется числовой функцией, если:

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

2) E(y) N

Функция y = f(x1, x2,…, xn) называется частично числовой функцией, если:

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

2) E(y) N.

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

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

2) (x1, x2,…, xn) = xm , 1 ≤ m ≤ n – функция повторяющая значение своих аргументов;

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

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

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

Будем говорить, что n – местная функция φ получается из m – местной функции ψ и n – местныхфункций f1,f2,…,fm с помощью операции суперпозиции, если для всех x1,x2,…,xn справедливо равенство:

φ (x1,x2,…,xn) = ψ( f1(x1, x2,…, xn),…, fm(x1, x2,…, xn))

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

Функцией алгебры логики от переменных называется функция, принимающая значения 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 введением фиктивной переменной, причем эти функции являются равными.







Последнее изменение этой страницы: 2017-01-19; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.206.194.83 (0.021 с.)