logo

Алгоритмы получения формулы по таблице истинности сднф и скнф

СДНФ

|

СКНФ

1. Конструирование логических схем начинается с таблицы истинности

(1)

X

Y

f(X,Y)

0

0

0

0

1

1

1

0

1

1

1

0

2. Отметим те строки таблицы, выходы которых равны

1

X

Y

f(X,Y)

0

0

0

0

1

1*

1

0

1*

1

1

0

0

X

Y

f(X,Y)

0

0

0*

0

1

1

1

0

1

1

1

0*

3.Выписываем для каждой отмеченной строки комбинацию переменных через знак

конъюнкцию ()

дизъюнкцию (V)

знаки операции отрицания расставим следующим образом:

если переменная = 1, то запишем | если переменная = 0, то запишем саму

саму эту переменную, если же она = 0, |эту переменную, если же она = 1,

то запишем ее отрицание. | то запишем ее отрицание.

(X  Y) для 2-й строки

(X V Y) для 1-й строки

(X  Y) для 3-й строки

(X V Y) для 4-й строки

4. Все полученные выражения связываем операцией

дизъюнкция

(X  Y) V (X  Y)

конъюнкция

(X V Y)  (X V Y)

Таблица истинности (1) и полученные СДНФ и СКНФ демонстрируют принцип действия одной и той же логической схемы.

Покажем, что полученные СДНФ и СКНФ эквивалентны. Преобразуем СКНФ по правилам алгебры логики:

(X V Y) (X VY) = XX V XY VXY V YY

Yandex.RTB R-A-252273-3
Yandex.RTB R-A-252273-4