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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
59
4. Пусть y,y,x,x
′
′
означают соответственно «7 — простое число», « 7 —
составное число», « 8 — простое число», « 8 — составное число» :
a) какие из предложений y&x,y&x,y&x,y&x
′
′
′
истинны и
какие ложны ?;
b) то же с заменой конъюнкций на дизъюнкцию ;
c) то же для предложений y,x,y,x
′′
.
5. Проверить, не составляя таблиц истинности, являются ли следующие
формулы тождественно истинными:
a)
p
p
→
; b)
p
p
∨
;
c)
pp ∧
;
d)
p
p
↔
;
e)
p
p
→
; f)
p
p
↔
;
g)
(
)
ppp
→
∨
;
h)
(
)
pp&p ↔ ;
i)
(
)
ppp
∨
→
; j)
(
)
p&pp&pp
→
↔
;
k)
(
)
ppp
↔
∨
;
l) pp → ;
m) pp ↔ ;
n)
(
)
(
)
pppp
∧
→
∨
.
6. Составить таблицы истинности для формул:
a)
x
∨
;
b)
(
)
(
)
yxyxyx
→
∨
∧
→
∨
;
c)
(
)
zyx
∨
∧
; d)
(
)
zxyyx
→
∨
→
∧
;
e)
(
)
(
)
zyxyx ∧∨→→ ;
f)
(
)
(
)
xyzx ↓↔→ ;
g)
(
)
(
)
xyzx
⊕
∨
→
;
h)
(
)
(
)
(
)
y&xzy|z →→ ;
i)
(
)
zyx|xyz →∨ ;
j)
(
)
(
)
(
)
yxzyx ⊕↔↓↓ ;
k)
(
)
(
)
(
)
y|zyxxyz ↓∨∨
l)
nn
y...yyx...xx
∧
∧
∧
→
∨
∨
∨
2121
.
7. Установить, какие из следующих формул являются тождественно ис-
тинными, тождественно ложными:
a)
y&xyx →∨
;
b)
(
)
(
)
xyyx
→
→
→
;
c)
(
)
(
)
xyyx
→
∨
→
; d)
(
)
yxx
∨
→
;
e)
(
)
y|xxy ↔
;
f)
(
)
(
)
yxyx
∨
↔
→
;
g)
(
)
(
)
yxyx ↔↔⊕ ; h)
(
)
yxyx ↓↔∨ ;
i)
(
)
(
)
(
)
(
)
(
)
zyxyzyx
→
∨
→
→
→
→
j)
(
)
(
)
zxyx
→
⊕
→
.
8. a) Известно, что импликация
x
→
истинна, а эквивалентность
x
↔
ложна. Что можно сказать о значении импликации
x
→
? 
                                           59
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
4. Пусть x , x ′ , y , y ′ означают соответственно «7 — простое число», «7 —
   составное число», «8 — простое число», «8 — составное число»:
       a) какие из предложений x & y , x & y′ , x ′ & y , x & y′ истинны и
           какие ложны ?;
       b) то же с заменой конъюнкций на дизъюнкцию;
       c) то же для предложений x , y , x ′ , y ′ .

5. Проверить, не составляя таблиц истинности, являются ли следующие
   формулы тождественно истинными:

            a) p → p ;                           b) p ∨ p ;
            c) p ∧ p ;                           d) p ↔ p ;
            e) p → p ;                           f) p ↔ p ;
            g)   ( p ∨ p) → p ;                  h) p & ( p ↔ p ) ;
            i)   ( p → p) ∨ p ;                  j) p ↔ p & ( p → p & p ) ;
            k)   p ∨ ( p ↔ p );                  l) p → p ;
            m) p ↔ p ;                           n) ( p ∨ p ) → ( p ∧ p ) .

6. Составить таблицы истинности для формул:
a) x ∨ y ;                           b) ( x ∨ y ) → ( x ∧ y ∨ x → y ) ;
c) ( x ∧ y ) ∨ z ;                   d) x ∧ y → ( y ∨ x → z ) ;
e)   ( x → y ) → (x ∨ y ∧ z );                   f)    ((x → z ) ↔ � y )↓ x ;
g)   ( x → (z ∨ y )) ⊕ x ;                       h)    (z |(� y )→ z ) → (x & y );
i)   xyz | (x ∨ y ) → z ;                        j)    ((x ↓ y )↓ z ) ↔ (x ⊕ y );
k)   ((xyz ) ∨ x ∨ y ) ↓(z | y )                 l) x1 ∨ x 2 ∨ ... ∨ x n → y1 ∧ y2 ∧ ... ∧ yn .

7. Установить, какие из следующих формул являются тождественно ис-
   тинными, тождественно ложными:
a) x ∨ y → x & y ;                   b) ( x → y ) → ( y → x ) ;
c)   (x → y ) ∨ ( y → x );                            d) x → ( x ∨ y );
e)   xy ↔ ( x | y ) ;                                 f) ( x → y ) ↔ ( x ∨ y );
g)   ( x ⊕ y ) ↔ ( x ↔ y );                           h) x ∨ y ↔ (x ↓ y );
i)   ( x → y ) → ((z → y ) → (( x ∨ y ) → z ))        j) ( x → y ) ⊕ ( x → z ) .

8. a) Известно, что импликация x → y истинна, а эквивалентность x ↔ y
      ложна. Что можно сказать о значении импликации y → x ?

Страницы