Математическая логика и теория алгоритмов. Сергиевская И.М. - 30 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

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

Рубрика: 

35
5) ),,(),( zy
x
z
P
x
y
x
yR ∀∃→∀ .
6)
),( y
x
y
P
x
∃∀ ),( y
x
yQ
x
∃∃∧ .
7) →∀ ),( y
x
xP
),( z
x
zQ
x
∀∃ .
8) ),(),( y
x
yQ
x
y
x
y
P
x
∃
¬∀∨∀∃ .
9)
()
),(),,(),,( yxQzyxzRzyxzPx ∨
∀
→∀∃
.
10) ),,(),,( zy
x
zQ
x
zy
x
xP
∀
∃→∀ .
5.
Найти предикат, не содержащий кванторов, логически эквивалентный
данному предикату. Предикаты
A
и
B
определены на множестве
{}
cba ,,.
1)
),(),( z
x
zB
x
y
x
yA ∃∀→∀ .
2)
),(),( z
x
zBy
x
yA
x
∀∧∃∀ .
3)
),(),( z
x
zB
x
y
x
A ∃∀∨∀ .
4)
),(),( z
x
zB
x
y
x
Ay
∀
∃→∃∀ .
5)
),(),( z
x
zBy
x
Ay ∀∨∀∃ .
6)
),(),( z
x
zB
x
y
x
A ∀∀∨∀ .
7)
),(),( z
x
Bzy
x
A ∀∃∧∃ .
8)
),(),( y
x
yB
x
z
x
A ∃∃→∀ .
9)
),(),( z
x
zBy
x
yA
x
∀∧∃∀ .
10)
),(),( z
x
zB
x
y
x
yA
∀
∃∨∀ .
6. Записать с помощью кванторов следующие утверждения и их отрицания.
1)
Функция )(
x
f
возрастает на интервале
(
)
ba,.
2)
Функция )(
x
f
непрерывна на интервале
(
)
ba,.
3)
Множество
A
является собственным подмножеством множества
B
.
4)
Точка
0
x является точкой экстремума функции )(
x
f
.
5)
Функция )(
x
f
достигает наибольшего значения на отрезке
[]
ba, в точке
0
x .
6)
Функция )(
x
f
дифференцируема в точке
0
x .
7)
Бинарное отношение
ρ
является симметричным.
8)
Функция )(
x
f
ограничена на множестве
R
.
9)
Булева функция ),...,,(
21 k
xxxf самодвойственна.
10)
Множества
A
и
B
не пересекаются.
7. Доказать эквивалентность
()
)()()()( xxQxxPxQxPx ∃∨∃=∨∃
.
8. Доказать, что не эквивалентны формулы
(
)
)()( xQxPx
∧
∃
и )()(
x
x
Q
x
xP
∃
∧
∃ .
В
Ответы и указания.
В
Содержание. 
5) ∀yR( x, y ) → ∃x∀zP( x, y, z ) .
6) ∀x∃yP( x, y ) ∧ ∃x∃yQ( x, y ) .
7) ∀xP( x, y ) → ∃x∀zQ( x, z ) .
8) ∃x∀yP( x, y ) ∨ ¬∀x∃yQ( x, y ) .
9) ∃x∀zP( x, y, z ) → (∀zR( x, y, z ) ∨ Q( x, y ) ) .
10) ∀xP( x, y, z ) → ∃x∀zQ( x, y, z ) .

     5. Найти предикат, не содержащий кванторов, логически эквивалентный
данному предикату. Предикаты A и B определены на множестве {a, b, c} .
1) ∀yA( x, y ) → ∀x∃zB ( x, z ) .
2) ∀x∃yA( x, y ) ∧ ∀zB( x, z ) .
3) ∀xA( x, y ) ∨ ∀x∃zB( x, z ) .
4) ∀y∃xA( x, y ) → ∃x∀zB( x, z ) .
5) ∃y∀xA( x, y ) ∨ ∀zB( x, z ) .
6) ∀xA( x, y ) ∨ ∀x∀zB ( x, z ) .
7) ∃xA( x, y ) ∧ ∃z∀xB( x, z ) .
8) ∀xA( x, z ) → ∃x∃yB( x, y ) .
9) ∀x∃yA( x, y ) ∧ ∀zB( x, z ) .
10) ∀yA( x, y ) ∨ ∃x∀zB ( x, z ) .

     6. Записать с помощью кванторов следующие утверждения и их отрицания.
1) Функция f (x) возрастает на интервале (a, b ) .
2) Функция f (x) непрерывна на интервале (a, b ) .
3) Множество A является собственным подмножеством множества B .
4) Точка x0 является точкой экстремума функции f (x) .
5) Функция f (x) достигает наибольшего значения на отрезке [a, b] в точке x0 .
6) Функция f (x) дифференцируема в точке x0 .
7) Бинарное отношение ρ является симметричным.
8) Функция f (x) ограничена на множестве R .
9) Булева функция f ( x1 , x2 ,..., xk ) самодвойственна.
10) Множества A и B не пересекаются.

      7. Доказать эквивалентность
∃x(P( x) ∨ Q( x) ) = ∃xP( x) ∨ ∃xQ( x) .

       8. Доказать, что не эквивалентны формулы ∃x(P( x) ∧ Q( x) ) и ∃xP( x) ∧ ∃xQ( x) .

В Ответы и указания.
В Содержание.



                                                        35

Страницы