Задания для самостоятельного выполнения

9. Упростите формулы алгебры логики:

0)	(X→Y ) & (X Ú Y );
1)	X Ú Y → X & ;
2)	( X Ú Y ) &( →Z)
3)	X Ú (X & Y→ );
4)	Y Ú Z → Y & ;
5)	& X → ;
6)	→ X & Z ;
7)	Z & X →Y Ú ;
8)	→ X Ú Y;
9)	Ú Y → ;

Тема 3. Формы представления логических функций

Виды форм логических функций:

- нормальная форма, если булева функция выражена через дизъюнкцию, конъюнкцию и отрицание переменных.

- совершенная форма, если функция записывается единственным образом.

Дизъюнктивной нормальной формой (ДНФ) логической функции называется ее представление в виде дизъюнкции некоторых элементарных конъюнкций.

Конъюнктивной нормальной формой (КНФ) логической функции называется ее представление в виде конъюнкции некоторых элементарных дизъюнкций.

Существуют два класса совершенных форм: совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ).

Механизм построения ДНФ:

1. постройте таблицу истинности логической функции;

2. отметьте наборы переменных, на которых логическая функция истинна;

3. выпишите отмеченные наборы переменных, соединяя между собой операцией конъюнкции, а между наборами – дизъюнкцией. Причем, если переменная имеет ложное значение, то она берется с отрицанием, а если истинное значение, то без отрицания.

Упростив полученную ДНФ, получите СДНФ.

Механизм построения КНФ:

1. постройте таблицу истинности логической функции;

2. отметьте наборы переменных, на которых логическая функция ложна;

3. выпишите отмеченные наборы переменных, соединяя между собой операцией дизъюнкции, а между наборами – конъюнкцией. Причем, если переменная имеет ложное значение, то она берется без отрицания, а если истинное значение, то с отрицанием;

Упростив полученную КНФ, получите СКНФ.

Полиномом Жегалкина логической функции F(x₁,x₂,…x_n) называется ее представление в виде суммы по модулю два (строгой дизъюнкции) некоторых элементарных конъюнкций и константы 1.

Полином Жегалкина единственным образом представляет логическую функцию и может быть найден:

- с помощью эквивалентных преобразований ДНФ,
выразив операции ИЛИ и НЕ через операции сложение по модулю два, и константу 1. Для этого применяются следующие соотношения:

a Ú b = a Å b Å a b , Ø а = 1 Å а; a Å a =0; ( a Å b ) c = a c Å b c

- с помощью эквивалентных преобразований СДНФ достаточно заменить все дизъюнкции на операции сложение по модулю два и избавиться от инверсий при помощи эквивалентного преобразования: Øа = 1 Å а;

- с помощью методов (неопределенных коэффициентов, карт Карно и метода треугольника).

Примеры выполнения заданий

1. Постройте совершенные формы для функции & b Å .

a b	& b	& b Å .
0 0	1 0 0	0 1 1
0 1	1 1 1	1 1 0
1 0	0 0 0	0 1 1
1 1	0 0 1	0 0 0

СДНФ = & Ú & b Ú a & º & ( Ú b) Ú a & º & 1Ú a & º
º Ú a & º ( Ú a) & ( Ú ) º 1 & ( Ú ) º Ú .

СКНФ = Ú .

2. Логическая функция f ( x , y , z )= x Å ( z ® Ø x ) & y задана аналитически. Переведите ее в другие виды представления:

Решение : построим таблицу истинности.

xyz	z ® Ø x	(z ® Ø x) & y	x Å (z ® Ø x) & y
000	0 1 1	1 0 0	0 0 0
001	1 1 1	1 0 0	0 0 0
010	0 1 1	1 1 1	0 1 1
011	1 1 1	1 1 1	0 1 1
100	0 1 0	1 0 0	1 1 0
101	1 0 0	0 0 0	1 1 0
110	0 1 0	1 1 1	1 0 1
111	1 0 0	0 0 1	1 1 0

Для представления функции в графическом виде, удобнее найти СКНФ:

СКНФ = ( x Ú y Ú z ) & ( x Ú y Ú ) & ( Ú Ú z ) =

= ( x Ú y Ú (z & )) & ( Ú Ú z) = ( x Ú y Ú 0) & ( Ú Ú z)=

=( x Ú y) & ( Ú Ú z)= ( x Ú y) & Ú ( x Ú y) & Ú ( x Ú y) & z=

= x & Ú y & Ú x & Ú y & Ú ( x Ú y) & z=

=0 Ú y & Ú x & Ú 0 Ú ( x Ú y) & z= y & Ú x & Ú ( x Ú y) & z.

Построим функциональную схему для f(x, y, z) = y & Ú x & Ú ( x Ú y )& z

x y z

3. Выясните, верно ли равенство, отыскав полином Жегалкина для логической функций в обеих частях этого равенства: x ~ y = xy Ú

Решение : x ~ y = = x Å y Å 1

xy Ú = xy Å xy Å = 0 Å xy Å ( x Å 1)( y Å 1)=

= xy Å xy Å x Å y Å 1 = x Å y Å 1.

Итак, равенство верно.

4. Выясните, равносильны ли данные ДНФ функций:

f ₁ = Ú x Ú y z , f ₂ = x Ú x z , f ₃ = Ú z , получив их СДНФ.

Решение : преобразуем данные функции к СДНФ.

f₁= & Ú x & Ú y & z = &( Ú x) Ú y & z= & 1 Ú y & z = Ú z

f₂ = x & Ú x & z = x &( Ú z)

Итак, f ₁ = f ₃ ¹ f ₂ . Следовательно, не равносильны.

5. Найдите полином Жегалкина для функции f(x, y, z) = ( ® x) & z & a) c помощью эквивалентных преобразований ДНФ; b) с помощью эквивалентных преобразований СДНФ

Решение: a) найдем ДНФ функции, построив таблицу истинности.

xyz	® x	( ® x) & z	( ® x) & z &
000	1 0 0	0 0 0	0 0 1
001	0 1 0	1 1 1	1 1 1
010	1 0 0	0 0 0	0 0 1
011	0 1 0	1 1 1	1 1 1
100	1 1 1	1 0 0	0 0 0
101	0 1 1	1 1 1	1 0 0
110	1 1 1	1 0 0	0 0 0
111	0 1 1	1 1 1	1 0 0

ДНФ = & & z Ú & y & z

Выразим операции ИЛИ и НЕ через операции строгой дизъюнкции и константу 1 по формулам: a Ú b= a Å b Å ab, Øа = 1 Å а;

z Ú y z = z Å y z Å z y z = (1 Å x ) (1 Å y ) z Å (1 Å x ) yz = = (1 Å y Å x Å xy ) z Å yz Å xyz = z Å zy Å xz Å xyz Å yz Å xyz = z Å xz

b ) Преобразуем ДНФ в СДНФ:

ДНФ = & & z Ú & y & z . СДНФ = z & & ( Ú y ) = z & & 1 = z &

Заменим все дизъюнкции на операции строгой дизъюнкции и избавимся от инверсий при помощи формулы: Øа = 1 Å а.

z & = z & (1 Å x ) = z Å zx.

Получили одинаковые полиномы Жегалкина, следовательно, вычисления сделаны верно.

Дата добавления: 2020-04-08; просмотров: 132; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 3 456 7 Следующая ⇒

Мы поможем в написании ваших работ!