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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
92
4. Составить несколько РКС для следующих функций:
1)
)
z
y
(
&
)
y
x
(
→
→
2)
)
z
x
(
)
z
y
(
)
y
x
→
→
→
→
3)
y
x
)
z
y
(
←
∨
4)
z
y
xy
↔
5) )yx()xy(&)yx( ∨∨→→
6)
)yx(&)zx( →∨
7)
z
y
)
z
y
(
&
)
y
x
(
x
∨
∨
∨
∨
∨
5. Из контактов
r
,
q
,
p
составить схему так, чтобы она замкнулась тогда и
только тогда, когда замкнуты какие-нибудь два из трех контактов
r
,
q
,
p
.
6. Требуется, чтобы в большом зале можно было включать или выключать
свет при помощи любого из четырех переключателей, расставленных на
четырех стенах.
Указание: это можно осуществить путем конструирования схемы, в
которой свет включается, когда замкнуто четное число выключателей,
и выключается свет , когда разомкнуто нечетное число выключателей.
7. Для группы из трех человек построить электрическую схему для реги -
страции тайного голосования простым большинством голосов. Требует -
ся так построить схему, чтобы каждый человек, голосующий «за», на-
жимал кнопку , и не нажимал, если он голосует «против», и чтобы в
случае, если будет большинство человек голосовать «за», — загоралась
лампочка .
6. ПОЛИНОМ ЖЕГАЛКИНА.
ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ
ФУНКЦИИ
Элементарная конъюнкция называется монотонной, если она не со-
держит отрицательных переменных.
Полиномом Жегалкина или полиномом по модулю 2 называется
формула :
(
)
ln
KKKKxxP
⊕
⊕
⊕
⊕
=
......,,
3211
,
где
(
)
liK
i
...,, 1
=
— попарно различные монотонные элементарные конъ-
юнкции, составленные из переменных
n
x...,,x
1
. 
                                           92
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
4. Составить несколько РКС для следующих функций:
         1) ( x → y ) & ( y → z )
         2) (( x → y ) & ( y → z ) → ( x → z )
         3) ( y ∨ z ) ← xy
         4) xy ↔ yz
           5) ( x → y ) & ( y → x ) ∨ ( x ∨ y )
           6) ( x ∨ z ) & ( x → y )
           7) x ∨ ( x ∨ y ) & ( y ∨ z ) ∨ y ∨ z

5. Из контактов p , q , r составить схему так, чтобы она замкнулась тогда и
   только тогда, когда замкнуты какие-нибудь два из трех контактов
    p, q, r .

6. Требуется, чтобы в большом зале можно было включать или выключать
   свет при помощи любого из четырех переключателей, расставленных на
   четырех стенах.
    Указание: это можно осуществить путем конструирования схемы, в
    которой свет включается, когда замкнуто четное число выключателей,
    и выключается свет, когда разомкнуто нечетное число выключателей.

7. Для группы из трех человек построить электрическую схему для реги-
   страции тайного голосования простым большинством голосов. Требует-
   ся так построить схему, чтобы каждый человек, голосующий «за», на-
   жимал кнопку, и не нажимал, если он голосует «против», и чтобы в
   случае, если будет большинство человек голосовать «за», — загоралась
   лампочка.




                         6. ПОЛИНОМ ЖЕГАЛКИНА.
                        ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ
                                ФУНКЦИИ

     Элементарная конъюнкция называется монотонной, если она не со-
держит отрицательных переменных.
     Полиномом Жегалкина или полиномом по модулю 2 называется
формула:
                         P (x1 , ..., x n ) =K 1 ⊕ K 2 ⊕ K 3 ⊕... ⊕ K l ,
где K i (i =1, ..., l ) — попарно различные монотонные элементарные конъ-
юнкции, составленные из переменных x1 , ..., x n .

Страницы