Лекции Математическая логика (стр. 3 )

Теорема 4.

Любая ФАЛ кроме константы 1 может быть представлена в виде

Такое представление функции называется СИНФ-1 (совершенная импликативная нормальная форма 1 рода).

Алгоритм получения СИНФ-1:

1.  Выбираем те наборы, на которых f = 0.

2.  Выписываем импликативные наборы, причём

3.  Объединяем все наборы конъюнкциями.

Пример.

0	0	0	0	ü
0	0	1	1
0	1	0	1
0	1	1	0	ü
1	0	0	0	ü
1	0	1	1
1	1	0	0	ü
1	1	1	1

Теорема 5.

Любая ФАЛ кроме константы 0 может быть представлена в виде

Такое представление функции называется СИНФ-2 (совершенная импликативная нормальная форма 2 рода).

Алгоритм получения СИНФ-2:

1.  Выбираем те наборы, на которых f = 1.

2.  Выписываем импликативные наборы, причём

3.  Объединяем все наборы дизъюнкциями.

Пример.

0	0	0	0
0	0	1	1	ü
0	1	0	1	ü
0	1	1	0
1	0	0	0
1	0	1	1	ü
1	1	0	0
1	1	1	1	ü

Аналитическая запись булевых функций через стрелку Пирса.

0	0		0	0	1	1
0	0		0	1	0	1
1	1		1	0	0	1
1	1		1	1	0	0

– множество номеров наборов аргументов, на которых или .

Теорема 6.

Любая ФАЛ кроме константы 1 может быть представлена в виде

Алгоритм получения совершенной нормальной формы для стрелки Пирса:

1.  Выбираем те наборы, на которых f = 0.

2.  Выписываем наборы со стрелками Пирса, причём

3.  Объединяем все наборы стрелками Пирса.

Пример.

0	0	0	0	ü
0	0	1	1
0	1	0	1
0	1	1	0	ü
1	0	0	0	ü
1	0	1	1
1	1	0	0	ü
1	1	1	1

Замечание.

Если функция принимает значение 0 только на одном наборе, то берём отрицание.

Лекция № 3.

КЛАССЫ БУЛЕВЫХ ФУНКЦИЙ.

1.  Класс булевых функций, сохраняющих константу 0.

Их число – половина от общего числа БФ, т. е. .

2.  Класс булевых функций, сохраняющих константу 1.

3.  Класс самодвойственных функций.

4.  Линейные функции.

5.  Монотонные функции.

Определение 1.

Функция называется двойственной с функцией , если .

Определение 2.

Функция называется самодвойственной, если она двойственна к самой себе.

Определение 3.

Функция называется линейной, если , где . Конъюнкция и дизъюнкция не линейные функции.