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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
62
c)
(
)
(
)
(
)
zxyxzyx
∨
↔
∨
=
↔
∨
; d)
(
)
(
)
(
)
zxyxzyx
→
↔
→
=
↔
→
;
e)
(
)
(
)
(
)
z&xy&xzy&x
⊕
=
⊕
; f)
(
)
(
)
(
)
z&xy&xzy&x
↔
=
↔
;
g)
(
)
(
)
(
)
zxyxzyx
→
→
=
→
; h)
(
)
(
)
(
)
zxyxzyx
→
=
→
.
2. Используя основные равносильности, доказать равносильность формул
U и B, когда:
a)
z
x
xy
z
x
U
∨
∨
=
;
xy
z
B
→
=
;
b)
(
)
(
)
(
)
yxyxyxU
↔
⊕
→
→
=
;
x
y
y
x
B
∨
=
;
c)
(
)
(
)
(
)
zyyxxyxU
→
→
→
→
=
;
(
)
zxyB
→
→
=
;
d)
(
)
(
)
zxzy|xU
→
∨
→
=
;
(
)
zyxB
∨
→
=
;
e)
(
)
(
)
zxxyzU ↔↓∨= ;
1
=
yz
xyz
B
;
f)
(
)
(
)
xyz|zyxU
↔
∨
=
;
1
⊕
=
xyz
B
.
3. Выразить все основные операции:
a) через дизъюнкцию , конъюнкцию и отрицание;
b) через конъюнкцию и отрицание;
c) через дизъюнкцию и отрицание;
d) через импликацию и отрицание.
4. a) Выразить отрицание импликации через основные операции так,
чтобы отрицания стояли только над простыми высказываниями.
b) Выразить операцию дизъюнкция через импликацию .
5. Доказать, что операция отрицания не может быть выражена через ос-
новные операции (бинарные) над высказываниями.
6. Мальчик решил в воскресенье закончить чтение книги , сходить в музей
или в кино, а если будет хорошая погода — пойти на реку выкупаться.
В каком случае можно сказать, что решение мальчика не выполнено? В
ответе отрицания должны содержаться лишь в простых высказываниях.
4.3 Решение логических задач с помощью алгебры высказываний
Условие логической задачи записываем в виде формулы алгебры вы-
сказываний, вводя соответствующие обозначения для простых высказыва -
ний, сформулированных в задаче. Далее с помощью равносильных преоб-
разований упрощаем формулу (составное высказывание). В результате по -
лучаем более простую словесную формулировку упрощенной формулы, на 
                                            62
 Операция замыкания. Основные замкнутые классы.
 __________________________________________________________________________________________
c) x ∨ ( y ↔ z ) =( x ∨ y ) ↔ ( x ∨ z ) ;      d) x → ( y ↔ z ) =( x → y ) ↔ ( x → z ) ;

e) x & ( y ⊕ z ) =( x & y ) ⊕ ( x & z ) ;      f) x & ( y ↔ z ) =( x & y ) ↔ ( x & z ) ;
g) x → ( y ⊕ z ) =( x → y ) ⊕ ( x → z ) ;      h) x ⊕ ( y → z ) =( x ⊕ y ) → ( x ⊕ z ) .


 2. Используя основные равносильности, доказать равносильность формул
    U и B, когда:
         a) U = x z ∨ xy ∨ xz ;                  B =z → xy ;
         b) U =( x → y ) → ( xy ⊕ ( x ↔ y )) ;   B = xy ∨ yx ;
         c) U = x → ( xy → (( x → y ) → y )z ) ; B = y → ( x → z ) ;
         d) U =( x | y → z ) ∨ ( x → z ) ;       B =( x → y ) ∨ z ;
           e) U =((z ∨ y ) ↓ x ) ↔ xz ;                   B = xyz ⊕ yz ⊕ 1 ;
           f) U =(( x ∨ y ) ↔ z ) | xyz ;                 B =xyz ⊕1 .

 3. Выразить все основные операции:
        a) через дизъюнкцию, конъюнкцию и отрицание;
        b) через конъюнкцию и отрицание;
        c) через дизъюнкцию и отрицание;
        d) через импликацию и отрицание.

 4.    a) Выразить отрицание импликации через основные операции так,
          чтобы отрицания стояли только над простыми высказываниями.
       b) Выразить операцию дизъюнкция через импликацию.

 5. Доказать, что операция отрицания не может быть выражена через ос-
    новные операции (бинарные) над высказываниями.
 6. Мальчик решил в воскресенье закончить чтение книги, сходить в музей
    или в кино, а если будет хорошая погода — пойти на реку выкупаться.
    В каком случае можно сказать, что решение мальчика не выполнено? В
    ответе отрицания должны содержаться лишь в простых высказываниях.




      4.3 Решение логических задач с помощью алгебры высказываний

       Условие логической задачи записываем в виде формулы алгебры вы-
 сказываний, вводя соответствующие обозначения для простых высказыва-
 ний, сформулированных в задаче. Далее с помощью равносильных преоб-
 разований упрощаем формулу (составное высказывание). В результате по-
 лучаем более простую словесную формулировку упрощенной формулы, на

Страницы