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.Формулы. Реализация функций формулами. /* Булевы формулы строятся исходя из более простых (элементарных) формул. Р2 - множество всех булевых функций.

Р2(n) — множество всех булевых функций от n переменных DР2

1)Для любой fD f(x1,...xn)- формула над множеством D.

2)Если f0D и f0=f0(x1,...xn), A1,...An – то или формулы над множеством D содержат переменные (x1,...xn, не обязательно все или каждая из них является одной из этих переменных, то результат подстановки A1,...An в f0 так же не будет формулой над D.

Каждой формуле U в множестве D будем сопоставлять булеву функцию, о которой будем говорить, что она реализуется данной формулой. При этом будем полагать, что если формула U реализует функцию f, то она так же реализует и любую равную ей функцию.

Тождественные функции являются формулами над любым множеством функций.*/

Зображення булевих функцій у вигляді формул

Булева функція представляється формулою у вигляді слова в певному алфавіті, а саме до цього алфавіту входять всі символи убльвих змінних, а також &, V, =>, <=>, Г, а також технычны символи: (, )

Означення: Формулою називають:

1) кожну х1, х2, ... , хn

2) (xi & xj), (xi V xj), (xi => xj), (xi <=> xj), Г xi, Г xj

3) Якщо А та В – вже формули, то (А & B), (А V B), (А => B), (А <=> B), Г А, Г В

4) Інші формули ми не визнаємо

Теорема1: Кожна булева функція від n змінних може бути представлена у вигляді формули

y3 = f(x1, x2) = x1

y3 = f(u1, u2) = u1

y12 = f(u1, u2) = Г u1

y14 = f(u1, u2) = Г (u1 & u2)

f(u1, u2, u3) = u1 & u2 & u3

Теорема2: Кожна булева функція від n змінних може бути представлена у вигляді формули, в якій фігурують лише символи &, V, Г, (, )

Кожну лог. схему можна сконструювати, використовуючи лише диз’юнктори, кон’юнктори і інвектори в достатьній кількості (з точку зору фізики)

Доведення теореми 2:

x1	x2	x1 => x2	Гx1 V x2
0	0	1	1 1 0
0	1	1	1 1 1
1	0	0	0 0 0
1	1	1	0 1 1

x1<=>x2 = (x1 => x2) & (x2 => x1)

1 1 1 1

0 1 0 0

0 0 0 1

1 1 1 1

Тобто (x1 => x2) = (Гx1 V x2 ) або (x1<=>x2) = (x1 => x2) & (x2 => x1)

Якщо Т1 має місце, то і Т2 теж має місце

Функция f называется суперпозицией функций f1,f2…fn, если она получается некоторой подстановкой подстановкой функций друг в друга.

Формулой над F называется выражение F[F]=f(t1,t2..tn)

Правило подстановки: если в равносильных формулах вместо всех вхождений некоторой переменной х подставить 1 и ту же формулу, то получаться равносильные формулы.

Правило замены: если в формуле заменить некоторую подформулу на равносильную., то получиться формула равносильная исходной.

.

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 можно представить в виде СКНФ.

9.11Эквивалентность формул. Свойства элементарных булевых функций.

Формулы U,V называются эквивалентными ( U=V), если они реализуют равные функции.

Свойства:

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

2. Свойство двойного отрицания:

 

 (4.2)

3. Идемпотентность (отсутствие степеней и множителей):

 

а) х & х = х; б) х u х = х. (4.3)

4. Закон противоречия:

х &`х = 0. (4.4)

5. Закон «исключенного третьего»:

х u х = 1. (4.5)

6. Ассоциативность:

а) х₁ & (х₂ & х₃) = (х₁ & х₂) & х₃; б) х₁ u(х₂ u х₃) = (х₁ u х₂) u х₃. (4.6)

7. Коммутативность:

а) х₁ & х₂ = х₂ & х₁; б) х₁ u х₂ = х₂ u х₁. (4.7)

8. Дистрибутивность конъюнкции относительно дизъюнкции:

х₁ & (х₂ u х₃) = (х₁ & х₂) u (х₁ & х₃). (4.8)

9. Дистрибутивность дизъюнкции относительно конъюнкции:

 х₁ u (х₂ & х₃) = (х₁ u х₂) & (х₁ u х₃). (4.9)

10. Правила де Моргана:

а) б) (4.10)

 

13 Замкнутые классы. Св-ва замыкания.

.14 Класс ф-ций сохраняющих 0 .

1)Т0 – класс бул. ф-ций сохраняющих 0: Т0 = {f| f(0,0...0)=0}

fT0 <=> f(0,…,0)=0.

входят: 0, x, x&y, xy.

невходят: 1, x, xy, , , .

Число ф-ций входящих в класс Т0 равно 2(2ⁿ)-1

Теорема: Класс Т0 – замкнут: [T0]=T0.

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

пусть f0, f1, f2 …. fk e T0. Пострим суперпозицию этих функций:

Ф(x1,x2,…xn)=f0(f1(…),…fk(…))T0, т.е.

Ф(0,…,0)=f0(0,…,0)=0, что верно.

Поэтому [T0]=T0.

-----------------------------------------------

Позначимо через Т0 клас всіх булевських функцій f(x1, …, xn), що зберігають константу 0, тобто функцій, для яких f(0, …, 0)=0. Доведемо, що Т0 – замкнений клас. Оскільки він містить тотожню функцію, то достатньо показати, що функція ф=f(f1, …, fn) належить Т0, якщо f, f1, …, fn належать Т0. Останнє випливає з того, що:

Ф(0, …, 0)=f(f1(0, …, 0), …, fm(0, …, 0))=f(0, …, 0)=0.

15.Класс ф-ций сохраняющих 1 .

Т1 – класс бул. ф-ций сохраняющих 1: Т1 = {f| f(1,1...1)=1}

fT1 <=> f(1,…,1)=1.

входят: 1, x, x&y, xy, xy, xy.

Не входят: x, xy, xy, xy.

Теорема: Класс Т1 – замклут: [T1]=T1.

Для док-ва этого достаточно показать, что элементарная суперпозиция ф-ций из Т1 также принадлежит Т1. пусть f0, f1, f2 …. fk e T1. Пострим суперпозицию этих функций:

Ф(x1,x2,…xn)=f0(f1(…),…fk(…)), f0, f1,…,fkT1.

Ф(1,…,1)=f0(f1(1),…,fk(1))=f0(1,…,1)=1, т.е. ФТ1.

------------------------------------------------

Позначимо через Т1 клас всіх булевських функцій f(x1, …, xn), що зберігають константу 1, тобто функцій, для яких f(1, …, 1)=1. Доведемо, що Т1 – замкнений клас. Оскільки він містить тотожню функцію, то достатньо показати, що функція ф=f(f1, …, fn) належить Т1, якщо f, f1, …, fn належать Т1. Останнє випливає з того, що:

Ф(1, …, 1)=f(f1(1, …, 1), …, fm(1, …, 1))=f(1, …, 1)=1