Булевы функции. ДН- формы и КН-формы

1.

Булевы функции.
ДН- формы и
КН-формы.

2.

3.

Алгебра логики (булева алгебра) — это
раздел математики, изучающий
высказывания, рассматриваемые со стороны
их логических значений (истинности или
ложности) и логических операций над ними.

4.

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

5.

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

6.

Значениям переменной в булевой алгебре
соответствуют состояниям элементов микросхем
компьютера или любого другого электронного
устройства: сигнал присутствует (логическая "1")
или сигнал отсутствует (логический "0").
На логических элементах, реализующих булевы
функции, строятся логические схемы
электронных устройств

7.

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

8.

Нормальные формы для формул
алгебры высказываний
Для каждой формулы алгебры
высказываний можно указать
равносильную ей формулу,
содержащую из логических связок
лишь (конъюнкцию и дизъюнкцию)

9.

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

10.

Понятие дизъюнктивной нормальной
формы.
Дизъюнктивным одночленом от переменных
X1,X2,...,Xn называется дизъюнкция этих
переменных или их отрицаний .
Примеры дизъюнктивных одночленов:
Х1 ˅ Х1, Х2˅ ¬Х2 ¬Х3, Х2 ˅ ¬Х3 ˅¬ Х2 ˅X5,

11.

Понятие конъюнктивной
нормальной формы.
Конъюнктивным одночленом от переменных Х1, Х2, Хn
называется конъюнкция этих переменных или их отрицаний.
Примеры конъюнктивных одночленов:
Х1 ˄ Х1, Х2 ˄ ¬Х2 ¬Х3, Х2 ˄ ¬Х3 ˄¬ Х2 ˄X5,

12.

Дизъюнктивной нормальной формой
называется дизъюнкция конъюнктивных
одночленов, т.е. выражение вида К1 V К2 V... V
Кр, где все Ki, i = 1,2, ...,р, являются
конъюнктивными одночленами (не
обязательно различными).

13.

Конъюктивной нормальной формой
называется конъюнкция дизъюнктивных
одночленов D1 ˄ D2 ˄... ˄ Dp, где все Dj, j =
1,2,...q, являются дизъюнктивными
одночленами (не обязательно
различными).

14.

Всякая формула обладает как
дизъюнктивной, так и
конъюнктивной нормальными
формами.

15.

Дизъюнктивная нормальная форма
.
X1 X2
f
0
0
1
0
1
1
1
0
1
1
1
0

16.

Конъюнктивная нормальная форма
.
X1 X2
f
0
0
0
0
1
0
1
0
1
1
1
0

17.

18.

ПРАВИЛО ОТЫСКАНИЯ СОВЕРШЕННОЙ ДИЗЪЮНКТИВНОЙ
НОРМАЛЬНОЙ ФОРМЫ ДЛЯ ДАННОЙ ФОРМУЛЫ:
-нужно выбрать все те наборы значений её переменных, на
которых формула принимает значение 1;
-для каждого такого набора выписать совершенный
конъюнктивный одночлен, принимающий значение 1 на этом
наборе и только на нём;
-полученные совершенные конъюнктивные одночлены
соединить знаками дизъюнкции.

19.

ОТЫСКАНИЯ СОВЕРШЕННОЙ КОНЪЮНКТИВНОЙ
НОРМАЛЬНОЙ ФОРМЫ ДЛЯ ДАННОЙ ФОРМУЛЫ:
-нужно выбрать все те наборы значений её переменных,
на которых формула принимает значение 0;
-для каждого такого набора выписать совершенный
дизъюнктивный одночлен, принимающий значение 0 на
этом наборе и только на нём.
- полученные совершенные дизъюнктивные одночлены
соединить знаками конъюнкции.

20.

Для приведения формулы к совершенной
нормальной форме нужно сначала привести
её к дизъюнктивной (или конъюнктивной)
нормальной форме.
Затем нужно продолжить равносильные
преобразования полученных нормальных
форм с тем, чтобы довести их до наиболее
краткого.

21.

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

22.

Молодцы!