Основы синтеза и диагностирования автоматов. Воронин В.В. - 113 стр.

UptoLike

ВУЗ: 

ТОГУ | Хабаровск

Составители: 

Рубрика: 

109
=x
1
x
2
f(1,1)
∨⎯
x
1
x
2
f(0,1)
∨⎯
x
2
x
1
f(1,0)
∨
21
x
x
f(0,0).
Исходя из таблицы истинности f(x
1
,x
2
)=x
1
⊕
x
2
имеем f(1,1)=f(0,0)=0;
f(1,0)=f(0,1)=1.
Подставив эти значения в последнюю формулу и
учитывая аксиомы
3в) и 4в), окончательно получим
f(x
1
,x
2
)=x
1
⊕
x
2
=
⎯
x
1
x
2
∨⎯
x
2
x
1
.
Ниже получим универсальный алгоритм перехода от табличной
записи функции (от таблицы истинности) к «стандартному» анали-
тическому выражению. Введем понятие степени логической пере-
менной. Пусть
х
α
есть степень переменной х, причем
⎩
⎨
⎧
=
=
=
.0,
;1,
α
α
α
x
x
x
Ниже показан процесс вычисления логической степени:
x=0,
α
=0
→
x
α
=
⎯
x=1; x=0,
α
=1
→
x
α
= x=0;
x=1,
α
=0
→
x
α
=
⎯
x=0; x=1,
α
=1
→
x
α
= x=1;
В теории логических функций на основе теоремы о разложении
и понятии логической степени доказывается следующая теорема.
Теорема
Т1. Любая функция алгебры логики представима в сле-
дующей форме:
f(x
1,
x
2
,…,x
n
)=
n
n
xxx
ααα
L
2
2
1
1
1
∨
. (3.4)
Символ
∨
1
означает, что дизъюнкция берется только по таким набо-
рам степеней
<
α
1
,
α
2
,...,
α
n
>, на которых выполняется равенство
f(
α
1
,
α
2
,...,
α
n
)=1. Представление логической функции в виде (3.4) на-
зывают
дизъюнктивной совершенной нормальной формой (ДСНФ).
Теорема
Т1 дает алгоритм перехода от таблицы истинности логиче-
ской функции к ее
ДСНФ. Он формулируется следующим образом.
• Выбрать в таблице истинности данной функции все наборы
аргументов, на которых она обращается в единицу, т.е. вы-
брать такие
(
α
1
,
α
2
,...,
α
n
), на которых f(
α
1
,
α
2
,...,
α
n
)=1.

Страницы