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(x_1,x_2,x_3)=(x_1 \vee x_2 \vee x_3) (x_1 \vee x_2 \vee\bar{x_3}) (x_1 \vee\bar{x_2} \vee\bar{x_3})(\bar{x_1} \vee\bar{x_2} \vee\bar{x_3})$

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

$f(x_1,x_2,x_3)= \bar{x_1} x_2 \bar{x_3} \vee x_1 \bar{x_2} \bar{x_3} \vee x_1 \bar{x_2} x_3 \vee x_1 x_2 \bar{x_3}$

 

  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