1.Функции алгебры логики. Алгебра образованная на множестве Е2 = { 0,1 } называется алгеброй логики и содержит операции возможные для для обработки логических выражений. Будем считать что это мн-во Е2 состоит из формальных символов 0 и 1, имеющих смысл логических констант и неимеющих арифметического смысла. Для всех 3х видов схем (1 — обеспечивающие обработку двоичных символов, которые есть числами или другой ин-фо; 2 — каналы, сети по которым передается ин-фа логический 0 или 1, информируют о наличии или отсутствии сигнала; 3 — схемы обеспечивающие решение задач управления, в них логическая 1 — наличие воздействия, 0 — отсутствие) характерным явл то что в точках схемы существуют сигналы, которые могут принимать только 0 или 1. эти символы явл константами булевой алгебры, иногда они могут быть заменены на ПРАВДА , ЛОЖЬ. Функция алгебры логики представляет собою отображение f : Е2^п → Е2 на мн-ве Е2., где п — кол-во входов.

2.Задание функций алгебры логики. Любая логическая функция n переменных может быть задана таблицей, в левой части которой перечислены   2 ^п наборов значений переменных; в правой части- значения функции на этих наборах. Наборы переменных располагаются в лекси-кографическом порядке(совпадает с тем как бы они следовали по возрастанию) , который совпадает с порядком возрастания наборов, рассматриваемых как двоичные числа. Наборы, на которых ф-я принимает 1 — единичный, 0 — нулевой. Ф-я полностью определена, если она задана вектором столбцов составленным из 2 ^п наборов значений переменных.

3.Сущ и несущ переменные. Рассмотрим булевую ф-ю зависящую от п переменных: f(х1,х2…хn).

Будем говорить, что переенная Хе явл существенной переменной для функции ф (функция существенно зависит от Хе) если выполняется неравенство:

f(х1,х2…хе-1, 0, хе+1, ...хn) ≠ f(х1,х2…хе-1, 1, хе+1, ...хn)

Будем говорить, что переменная Хе несущ для функции ф если выполняется:

f(х1,х2…хе-1, 0, хе+1, ...хn) = f(х1,х2…хе-1, 1, хе+1, ...хn)

хе еще называется фиктивной переменной. В этом случае функция существенно зависит от Хе-1.: f(х1,х2…хе-1, хе, хе+1, ...хn) ≠ д(х1,х2…хе-1, хе+1, ...хn)

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

ф(Х1, Х2,Х3) = д(Х1,Х3), где Х2 -фиктивная переменная. Такой прием явл весьма эффективным, т. к. позволяет рассматривать любую совокупность произвольных ф-й как совокупность ф-й зависящих от одинакового кол-ва переменных. Удаление фиктивной переменной осуществляется след. образом: из каждой пары соседних наборов оставляем один, а второй удаляем и даляем столбец, соот-щий фиктивной переменной. Операция введения фиктивной переменной осущ. в обратном порядке. Две бул. ф-ции наз. равными, если одна из них получается из другой путем добавления или удаления фиктивной переменной.

4.Примеры логических ф-й.

Среди бул. ф-ций выделяются элементарные бул. ф-ции: 1)константы: 1, 0; 2)тождественная ф-ция: х; 3)отрицание:х; 4)

			\/					
0 0 1 1	0 1 0 1	0 0 0 1	0 1 1 1	0 1 1 0	1 1 0 1	1 0 0 1	1 1 1 0	1 0 0 0

Приоритет операций: отрицание, конъюнкция, дизъюнкция, имплик-я, эвивал-ность.

5. Представления булевых функций формулами:

Формулой называется выражения которое описывает суперпозицию известных функций.

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

f(x1,x2,x3) = (x1↓x3) (x2→x1)

Любое представление функции в виде формулы является суперпозицией. Для записи формул будем использовать знаки операций: •, v, →, ~, ↓, |. Для функции, представленной заданной формулой, всегда можно построить таблицу ее значений.

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

Теорема 1: Любую булевую функцию n-переменных можно представит в виде формулы.

Теорема 2: Любая булевая функция n-переменных может быть представлена в виде формулы, в которой присутствуют дизъюнкцтя, конъюнкция и отрицание.

6. Представления булевых функций формулами. Примеры:

f(x1,x2,x3) = (x1↓x3) (x2→x1)

f(x1,x2) = x1|x2 =

f(x1,x2,x3) = x1 (x2 v x3) → x3

7. Разложение булевых функций по переменным. Теорема:

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

Введем обозначения: x⁰ = , x¹ = x.

Тогда x^α = α – параметр, который принимает значения 0 и 1.

Теорема: Всякая булевая функция n-переменных может быть представлена в виде:

f(x1,x2,…,xN) = .

8.Разложение булевых функций по переменным. СДНФ.

Любую булеву функцию можно представить в вид;

= v

Это Соотношение назывется разложением булевой функции по первым k переменным. Для доказательства достаточно показать, что подстановка любого набора в это соотношение дает тождество. fn

В ведём обозначение:

x, σ=1

<=> x=σ

Функция вида называется элементарной конъюнкцией, где - const

Функция вида называется элементарной дизъюнкцией, где - const

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

Теорема (о разложении булевых функций по переменным)

Сокращенные ДНФ.(минимальные)

Алгоритм построения сокращенных ДНФ.

1)Находим произвольную КНФ, реализующую ф-ю f(можно взять СКНФ)

2)Перемножаем элементы дизъюнкции и переходим в ДНФ

3)упрощаем полученую ДНФ, используя

x*x=x

xVx=x

x*x=0

xVx=1

xVxy=x

Любую булеву функцию, не тождественную 1 можно представить в виде СКНФ.