Processing math: 100%


21:59
СКНФ и СДНФ булевой функции

Пример. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 00101110.

Решение.

Строим таблицу значений функции (табл.):

Таблица

x1

x2

x3

f(x1, x2, x3)

0

0

0

0

0

1

0

0

1

0

2

0

1

0

1

3

0

1

1

0

4

1

0

0

1

5

1

0

1

1

6

1

1

0

1

7

1

1

1

0

 
Алгоритм построения СКНФ и СКНФ см. на странице правила построения СДНФ и СКНФ по таблице истинности

СКНФ (0): № 0, 1, 3, 7

f(x1,x2,x3)=(x1x2x3)(x1x2¯x3)(x1¯x2¯x3)(¯x1¯x2¯x3)

СДНФ (1): № 2, 4, 5, 6

f(x1,x2,x3)=¯x1x2¯x3x1¯x2¯x3x1¯x2x3x1x2¯x3

 

  1. Теорема. Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно нулю, то существует такая формула F, зависящая от списка переменных x1, x2, …, xn и находящаяся в СДНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки дизъюнктивных членов.
  2. Теорема . Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно единице, то существует такая формула F, зависящая от списка переменных x1, x2, …, xk и находящаяся в СКНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки конъюнктивных членов.
Категория: Дискретная математика | Просмотров: 2993 | Добавил: Admin | Теги: булева алгебра | Рейтинг: 0.0/0
Всего комментариев: 0
avatar
close