Дискретная математика. Элементы теории задачи и упражнения. Часть 2. Булгакова И.Н - 30 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
76
Учитывая, что
(
)
(
)
aabbababa =∨=∨=∨∨ 0 , получим другую
КНФ , равносильную КНФ
1
:
(
)
(
)
(
)
(
)
(
)
.КНФyxzyxzzyxzyxf
2
−
∨
∨
∨
=
∨
∨
∨
∨
=
Неоднозначность нормальных форм очевидна.
Таким образом, применяя различные равносильные преобразования,
мы можем прийти к различным нормальным формам, реализующих одну и
ту же функцию. В связи с этим возникает возможность выбора более
предпочтительной реализации.
ЗАДАЧИ И УПРАЖНЕНИЯ
1. По данному набору
(
)
n
α
α
,...,
1
значений переменных
n
xx ,...,
1
построить
элементарную конъюнкцию , истинную только для этого набора значе-
ний переменных.
2. По данному набору
(
)
n
α
α
,....
1
значений переменных
n
xx ,...,
1
построить
элементарную дизъюнкцию , ложную только для этого набора значений
переменных .
3. С помощью эквивалентных преобразований привести к ДНФ формулы:
1)
(
)
(
)
;zxyzx
∨
∨
2)
(
)
(
)
(
)
(
)
;
41431424321
xxxxxxxxxxx
∨
∨
→
∨
∨
3)
(
)
(
)
;~ yxzyzx ∨→↓
4)
(
)
(
)
;|
314321
xxxxxx
→
→
5)
(
)
(
)
.~ yxyxx ∨→∨
4. С помощью эквивалентных преобразований привести к КНФ формулы:
1)
;
y
x
→
2)
(
)
(
)
;xxxxx
→
→
⊕
4321
3)
(
)
(
)
;~|
41321
xxxxx
→
4)
(
)
(
)
(
)
;~ xyzyxyz ↓∨
5)
(
)
(
)
(
)
.~ zyxzyx →⊕→
5. Пусть
nm
UUXX ,...,,,...,
11
- произвольные формулы алгебры логики.
Доказать следующие эквивалентности: 
                                                 76
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
     Учитывая, что (a ∨ b )(a ∨ b ) =a ∨ b b =a ∨ 0 =a , получим другую
КНФ, равносильную КНФ1 :
        f =( x ∨ y ∨ z )(( x ∨ y ) ∨ z z ) =( x ∨ y ∨ z )( x ∨ y ) −КНФ2 .
     Неоднозначность нормальных форм очевидна.

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




                             ЗАДАЧИ И УПРАЖНЕНИЯ

1. По данному набору (α 1 ,...,α n ) значений переменных x1 ,..., x n построить
   элементарную конъюнкцию, истинную только для этого набора значе-
   ний переменных.
2. По данному набору (α1 ,....α n ) значений переменных x1 ,..., x n построить
   элементарную дизъюнкцию, ложную только для этого набора значений
   переменных.
3. С помощью эквивалентных преобразований привести к ДНФ формулы:
        1) ( x ∨ yz )( x ∨ z );
        2) (( x1 ∨ x 2 x 3 x 4 )( x 2 ∨ x 4 ) → x1 x 3 x 4 ) ∨ ( x1 ∨ x 4 );
              (        )
           3) x ↓z ~ ( y → z ) ∨ xy;
           4) ( x 1 x 2 → x 3 x 4 ) | ( x1 → x 3 );
           5) ( x ∨ ( x ~ y )) → x ∨ y.
4. С помощью эквивалентных преобразований привести к КНФ формулы:
           1) x → yz;
           2) (( x1 x 2 ⊕ x 3 ) → x 4 ) → x;
           3) (( x1 | x 2 ) → x 3 ) ~ x1 x 4 ;
           4) (( xyz ~ ( y ∨ z )) y ) ↓ x ;
           5) �( x ~ yz ) → ( x ⊕ ( y → z )).
5. Пусть X 1 ,..., X m , U1 ,..., U n - произвольные формулы алгебры логики.
   Доказать следующие эквивалентности:

Страницы