Задачи по дискретной математике для контрольных и самостоятельных работ. Булевы функции. Васильев А.В - 27 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

A Приложение. Задачи повышенной трудности
1. Доказать, что формула, содержащая только связку ∼, тождественно ис-
тинна
1
тогда и только тогда, когда любая переменная входит в нее четное
число раз.
2. Доказать, что если F – тождественно истинная формула, то после заме-
ны в ней каждой переменной на ее отрицание, получится тождественно
истинная формула.
3. Доказать, что F тождественно истинна тогда и только тогда, когда F
x
y
1
→y
2
тождественно истинна, где y
1
, y
2
– переменные, не входящие в F , а F
x
y
1
→y
2
– результат замены в F переменной x на формулу y
1
→ y
2
.
4. Найти длину СДНФ заданной функции
4.1. x
1
⊕ . . . ⊕ x
n
4.2. (x
1
∨ . . . ∨ x
n
)(x
1
∨ . . . ∨ x
n
)
4.3.
W
(i
1
...i
k
)
x
i
1
· · · x
i
k
4.4.
&
(i
1
...i
k
)
(x
i
1
∨ · · · ∨ x
i
k
)
4.5. (x
1
∼ x
2
)(x
2
∼ x
3
) . . . (x
n−1
∼ x
n
)
4.6. (x
1
⊕ x
2
)(x
2
⊕ x
3
) . . . (x
n−1
⊕ x
n
)
4.7. (x
1
⊕ x
2
)(x
2
⊕ x
3
) . . . (x
n−1
⊕ x
n
)(x
n
⊕ x
1
)
4.8. (x
1
⊕ x
2
) ∨ (x
2
⊕ x
3
) ∨ . . . ∨ (x
n−1
⊕ x
n
)
4.9. (x
1
⊕ x
2
) ∨ (x
2
⊕ x
3
) ∨ . . . ∨ (x
n−1
⊕ x
n
) ∨ (x
n
⊕ x
1
)
4.10. (x
1
∼ x
2
) ∨ (x
2
∼ x
3
) ∨ . . . ∨ (x
n−1
∼ x
n
)
4.11. (x
1
→ x
2
)(x
2
→ x
3
) . . . (x
n−1
→ x
n
)
4.12. (x
1
→ x
2
)(x
2
→ x
3
) . . . (x
n−1
→ x
n
)(x
n
→ x
1
)
4.13. (x
1
→ x
2
)(x
2
→ x
1
)(x
2
→ x
3
)(x
3
→ x
2
) . . . (x
n−1
→ x
n
)(x
n
→ x
n−1
)
4.14.
n
X
i=1
x
1
. . . x
i−1
x
i+1
. . . x
n
⊕ x
1
. . . x
n
4.15. (x
1
∨
x
2
)(x
2
∨ x
3
) . . . (x
n−1
∨ x
n
)
4.16. (x
1
∨ x
2
)(x
2
∨ x
3
) . . . (x
n−1
∨ x
n
)(x
n
∨ x
1
)
4.17. (x
1
| x
2
) ∨ (x
2
| x
3
) ∨ . . . ∨ (x
n−1
| x
n
)
4.18. (x
1
↓ x
2
)(x
2
↓ x
3
) . . . (x
n−1
↓ x
n
)
4.19. (x
1
| x
2
)(x
2
| x
3
) . . . (x
n−1
| x
n
)
1
Формула называется тождественно истинной, если она равна 1 при любых значениях аргументов.
27
A     Приложение. Задачи повышенной трудности

1. Доказать, что формула, содержащая только связку ∼, тождественно ис-
   тинна1 тогда и только тогда, когда любая переменная входит в нее четное
   число раз.
2. Доказать, что если F – тождественно истинная формула, то после заме-
   ны в ней каждой переменной на ее отрицание, получится тождественно
   истинная формула.
3. Доказать, что F тождественно истинна тогда и только тогда, когда Fyx1 →y2
   тождественно истинна, где y1 , y2 – переменные, не входящие в F , а Fyx1 →y2
   – результат замены в F переменной x на формулу y1 → y2 .
4. Найти длину СДНФ заданной функции
     4.1. x1 ⊕ . . . ⊕ xn
     4.2. (x1 ∨ . . . ∨ xn )(x1 ∨ . . . ∨ xn )
            W
     4.3.       xi1 · · · xik
            (i1 ...ik )
     4.4.      & (xi1 ∨ · · · ∨ xik )
            (i1 ...ik )
     4.5. (x1 ∼ x2 )(x2 ∼ x3 ) . . . (xn−1 ∼ xn )
     4.6. (x1 ⊕ x2 )(x2 ⊕ x3 ) . . . (xn−1 ⊕ xn )
     4.7. (x1 ⊕ x2 )(x2 ⊕ x3 ) . . . (xn−1 ⊕ xn )(xn ⊕ x1 )
     4.8. (x1 ⊕ x2 ) ∨ (x2 ⊕ x3 ) ∨ . . . ∨ (xn−1 ⊕ xn )
     4.9. (x1 ⊕ x2 ) ∨ (x2 ⊕ x3 ) ∨ . . . ∨ (xn−1 ⊕ xn ) ∨ (xn ⊕ x1 )
    4.10. (x1 ∼ x2 ) ∨ (x2 ∼ x3 ) ∨ . . . ∨ (xn−1 ∼ xn )
    4.11. (x1 → x2 )(x2 → x3 ) . . . (xn−1 → xn )
    4.12. (x1 → x2 )(x2 → x3 ) . . . (xn−1 → xn )(xn → x1 )
    4.13. (x1 → x2 )(x2 → x1 )(x2 → x3 )(x3 → x2 ) . . . (xn−1 → xn )(xn → xn−1 )
          Xn
    4.14.     x1 . . . xi−1 xi+1 . . . xn ⊕ x1 . . . xn
            i=1
    4.15. (x1 ∨ x2 )(x2 ∨ x3 ) . . . (xn−1 ∨ xn )
    4.16. (x1 ∨ x2 )(x2 ∨ x3 ) . . . (xn−1 ∨ xn )(xn ∨ x1 )
    4.17. (x1 | x2 ) ∨ (x2 | x3 ) ∨ . . . ∨ (xn−1 | xn )
    4.18. (x1 ↓ x2 )(x2 ↓ x3 ) . . . (xn−1 ↓ xn )
    4.19. (x1 | x2 )(x2 | x3 ) . . . (xn−1 | xn )
1 Формула    называется тождественно истинной, если она равна 1 при любых значениях аргументов.


                                                        27

Страницы