L_5_БФ1 (2)

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

Булевы функции названы в честь английского математика ХIХ века Дж. Буля, который впервые
применил алгебраические методы для решения логических задач. Они образуют самый простой
нетривиальный класс дискретных функций - их аргументы и значения могут принимать всего два
значения. С другой стороны, этот класс достаточно богат и его функции имеют много интересных
свойств. Булевы функции находят применение в логике, электротехнике, многих разделах
информатики.
Обозначим через В двухэлементное множество
. Тогда
- это множество всех двоичных последовательностей (наборов, векторов) длины - n

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

Каждый из ее аргументов Xi может принимать одно из двух значений 0 или 1 и
значением функции на любом наборе из также может быть 0 или 1. Обозначим
через
множество всех булевых функций от переменных. Их число:
Булевы функции могут быть представлены в аналитическом виде (например: ДНФ и КНФ) или в
табличной форме

3. Фиктивные и существенные переменные

Наборы булевых переменных u и v называются
соседними по i-й переменной,
если они отличаются только значением i-й переменной:
u=(a1, a2, …, ai-1, 0, ai+1, …, an)
v=(a1, a2, …, ai-1, 1, ai+1, …, an)
Переменная xi называется
фиктивной переменной функции f,
если для любых наборов u и v, соседних по i-й переменной,
выполняется равенство f(u)=f(v)
Переменная xi называется
существенной переменной функции f,
если существуют наборы u и v, соседние по i-й переменной,
такие, что f(u)≠f(v)

4. Булевы функции двух аргументов.

x1 x2 f1(x1,x2)=0
0
0
1
1
0
1
0
1
f2(x1,x2)=
x1&x2
противоречие
конъюнкция
0
0
0
0
0
0
0
1
Обе переменные
являются фиктивными
f3(x1,x2)= f4(x1,x2)=x1 f5(x1,x2)=
⌐(x1→x2)
⌐(x2→x1)
запрет
0
0
1
0
запрет
0
0
1
1
0
1
0
0
Переменная x2
является фиктивной

5. Булевы функции двух аргументов.

f6(x1,x2)=x2
x1 x2
f7(x1,x2)=
f8(x1,x2)=
f9(x1,x2)=
тождество
x1 x2
сложение по
модулю 2
x1 x2
дизъюнкция
x1↓x2
стрелка
Пирса
0
0
1
0
1
0
0
1
0
0
1
1
0
1
1
1
0
0
1
1
1
0
1
0
Переменная x1
является фиктивной

6. Булевы функции двух аргументов.

x1 x2
0
0
1
1
0
1
0
1
f10(x1,x2)=
f11(x1,x2)=
¬ x2
1
0
0
1
1
0
1
0
x1↔x2
эквиваленция
Переменная x1
является фиктивной
f12(x1,x2)=
f13(x1,x2)=
¬ x1
1
0
1
1
1
1
0
0
x2→x1
импликация
Переменная x2
является фиктивной

7. Булевы функции двух аргументов.

f14(x1,x2)=
x1 x2
0
0
1
1
0
1
0
1
x1→x2
импликация
1
1
0
1
f15(x1,x2)=
f16(x1,x2)=
x1|x2
штрих
Шеффера
1
тавтология
1
1
1
0
1
1
1
1
Обе переменные
являются фиктивными

8. Выявление фиктивных переменных

Задана функция f(x1,x2,x3).
Выяснить, какие ее аргументы являются фиктивными.
x1
x2
x3
f
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
1
1
0
1
0
1
1
0
1
1
1
1
0
1. Наборы (000) и (100) являются
соседними по x1, f(000) ≠ f(100).
х1 является существенной.
2. Наборы (000) и (001) являются
соседними по x3, f(000) ≠ f(001).
х3 является существенной.
3. Рассмотрим наборы, соседние
по х2:
f(000)=f(010)=0
f(001)=f(011)=1
f(100)=f(110)=1
f(101)=f(111)=0
х2 является фиктивной.

9. Суперпозиция

Суперпозицией функций называется функция,
полученная с помощью
• подстановок этих функций вместо их аргументов,
• переименования аргументов.
Выражение, описывающее суперпозицию, называется
формулой.
Пример
Заданы функции f2(x1,x2) и f1(x1,x2). Построить таблицу
функции h(x1,x2)=f2(x2,f1(x1,x2))
x1
x2 f1
f2
0
0
0
1
0
1
1
1
1
0
1
1
1
1
0
0
1. Построить таблицу
y = f1(x1,x2)
2. Построить таблицу
h = f2(x2,y)
x 1 x2
y
h
0
0
0
1
0
1
1
0
1
0
1
1
1
1
0
1

10. Формулы

11. Построение таблицы по формуле

Порядок действий:
• задать все возможные комбинации аргументов,
• установить порядок выполнения операций,
• для
каждой
комбинации
значений
аргументов
последовательно установить значения функции.
Порядок выполнения логических операций
• Отрицание
• Конъюнкция
• Дизъюнкция
• Импликация, эквиваленция
• Все остальные
Пример:
x1|x2 x3&¬x1 = (x1|(x2 (x3&(¬x1))))
порядок выполнения:
4 3 2 1

12. Пример построения таблицы по формуле

f(x1,x2,x3) = ¬x1 x2 & x3
3 аргумента, 23=8 комбинаций.
Порядок выполнения операций:
1. y1 = ¬x1
2. y2 = x2 & x3
3. y3 = y1 y2
x1
x2
x3
y1
y2
y3
0
0
0
1
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
1
1
1
1
1
1
0
0
0
0
1
1
0
1
0
0
1
1
1
0
0
0
1
1
1
1
0
1
1

13. Исключение фиктивных переменных

Задана функция f(x1,x2,x3).
Выразить функцию формулой, содержащей только
существенные переменные.
Переменная х2 является фиктивной.
Построим таблицу функции f(x1,x3)
x1
x2
x3
f
0
0
0
0
0
0
1
1
x1
x3
f
0
1
0
0
0
0
0
0
1
1
1
0
1
1
1
0
0
1
1
0
1
1
0
1
0
1
1
0
1
1
0
1
1
1
1
0
f(x1,x3) = x1 x3

14. Равносильность

Две формулы Ф1 и Ф2 называются равносильными
(обозначается Ф1 Ф2),
если они принимают одинаковые значения
при любом наборе переменных.
Отношение равносильности является
отношением эквивалентности
(рефлексивно, симметрично и транзитивно).
Равносильность формул доказывается
построением таблиц.
Пример равносильных формул:
x1↓x2 ¬x1&¬x2 ¬(x1 x2)
x1
x2
x1↓x2
¬x1
¬x2
¬x1&¬x2
x1 x2
¬(x1 x2)
0
0
1
1
1
1
0
1
0
1
0
1
0
0
1
0
1
0
0
0
1
0
1
0
1
1
0
0
0
0
1
0

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

Идемпотентность
x&x x
x x x
Коммутативность
x&y y&x
x y y x
Ассоциативность
x&(y&z) (x&y)&z
x (y z) (x y) z
Существование границ
x&1 x
x 1 1
x&0 0
x 0 x
Противоречие, исключенное третье
x&¬x 0
x ¬x 1
Законы де Моргана
¬(x&y) ¬x ¬y
¬(x y) ¬x&¬y
Дистрибутивность
x (y&z) (x y)&(x z)
x&(y z) (x&y) (x&z)
Двойное отрицание
¬(¬ x) x

16. Законы поглощения

(П1)
Действительно,
(П2)
Действительно,
(П3)
Действительно,

17. Замена эквивалентных формул

Принцип замены эквивалентных подформул:
Если формула является подформулой формулы Φ, формула ' эквивалентна и
формула Φ' получена из Φ посредством замены некоторого вхождения на '. Тогда Φ'
эквивалентна Φ, т.е. Φ' Φ.
Применяя этот принцип и используя основные тождества, можно находить для заданной
формулы другие эквивалентные ей формулы. Часто это может приводить к
существенному упрощению исходной формулы. Например, если в формуле ((X 0) Y)
заменим на основании рассмотренных ранее тождеств подформулу (X 0) на 0, то
получим эквивалентную формулу (0 Y). По закону коммутативности (2) эта формула
эквивалентна формуле (Y 0), которая, в свою очередь, по одному из тождеств группы
эквивалентна формуле Y.

18. ДНФ и КНФ

Дизъюнктивная Нормальная Форма (ДНФ) и Конъюнктивная Нормальная Форма (КНФ) представления произвольной булевой функции посредством формул специального
вида, использующих только операции , и ¬.
Пусть
- это множество пропозициональных переменных. Введем
для каждого i=1,...,n обозначения:
и
. Формула
, в которой
переменные разные, т.е.
(элементарной дизъюнкцией).
при
и все
, называется элементарной конъюнкцией

19. Определение ДНФ и КНФ

Формула называется дизъюнктивной нормальной формой (ДНФ), если она
является дизъюнкцией элементарных конъюнкций, т.е. имеет вид
где каждая формула
- это элементарная
конъюнкция. называется совершенной ДНФ, если в каждую из ее конъюнкций
входят все переменных из Аналогично, формула называется конъюнктивной
нормальной формой (КНФ), если она является конъюнкцией элементарных
дизъюнкций, т.е. C= D1 D2…. Dn где каждая формула
- это
элементарная дизъюнкция. Она является совершенной КНФ, если в каждую
входят все переменных из
Примеры:
x1&x3 x2&¬x3 x1&x3 x2&¬x3 x1&x2 – ДНФ
(x1 x2)&(x2 x3)&(x1 ¬x3) – КНФ

20. Совершенные ДНФ и КНФ

f(X1,…,Xn) – произвольная булева функция , зависящая от переменных из
.
Nf+ - множество наборов значений переменных, на которых f принимает значение 1, а
Nf- множество наборов, на которых f принимает значение 0, т.е.
и
Определим по этим множествам две формулы:
и
Теорема
1. Если функция f не равна тождественно 0, то формула
ДНФ, задающая функцию f.
- это совершенная
2. Если функция f не равна тождественно 1, то формула
КНФ, задающая функцию f.
Следствие
- это совершенная
Каждая булева функция может быть задана формулой, содержащей переменные и
функции конъюнкции, дизъюнкции и отрицания.

21. Пример

Пусть формула
.
На (1)-ом этапе процедуры получаем следующую цепочку эквивалентностей:
На (2)-ом этапе вносим отрицание внутрь первой скобки и получаем формулу
Устранив двойное отрицание, получим
. Удалим на следующем этапе повторное вхождение первой конънкции и получим ДНФ

22. Пример

Эта ДНФ не является совершенной, так как в каждую из ее трех конъюнкций входят не
все переменные. Построим теперь для них эквивалентные совершенные ДНФ
Подставив эти формулы в Φ1 и устранив повторения конъюнкций, получим
совершенную ДНФ, эквивалентную исходной формуле Φ:
Мы видим, что ДНФ Φ1 , выглядит существенно проще, т.е. является более короткой,
чем совершенная ДНФ Φ2 . Однако совершенные ДНФ и КНФ обладают важным
свойством единственности