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

UptoLike

ВУЗ: 

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

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

Рубрика: 

63
В
Ответы и указания.
В
Содержание.
Ответы и указания.
Глава 1. Высказывания, формулы, тавтологии. 2. 2), 5), 8), 10) – истинные
высказывания. 1), 4), 7) – ложные высказывания. 3), 6) высказываниями не
являются. 3. Обратите внимание, что 7) – составное высказывание. 5. Не являются
тавтологиями: 2), 3), 5). Вернуться в
Задачи.
Глава 3. Исчисление высказываний. 1. 1), 2), 5), 7), 8), 9) – формулы
исчисления высказываний. 3), 4), 6), 10) формулами исчисления высказываний не
являются. 2. 2). 3. 5) Применить лемму. 6), 7), 9) – применить результат 5). 8), 10),
11), 12) – применить результат 9). Вернуться в
Задачи.
Глава 5. Предикаты. 1. 1)
{
}
2
−
. 3)
{
}
2 . 5)
{
}
1),(
2
=−∈ yxRyx
. 7)
R
. 8)
{
}
22
),( yxRyx ≥∈ . 9)
{}
7,5,3,2,1 . 10)
{
}
1
−
. 2. 1), 3), 4), 6), 7), 9), 10). 1. 2), 5), 8). 0. 3.
7) Воспользоваться формулой
A
B
B
A
B
A
∨
¬
¬
=
.
4. 1)
()()()
ytPzyxRztx ,,, ∨¬∀∀∀ .
2)
()
(
)()
yxPztxRtx ,,, ∨¬∀∃ . 3)
(
)
(
)
(
)
sxQytPst ,,
∧
∃
∀ .
4)
() ( )()
yxQtxPtx ,, ∧∀∃ . 5)
(
)
(
)
(
)
zysPtxRzst ,,, ∨
¬
∀
∃∃ .
6)
() ()()
zxQytPzyxt ,, ∧∃∃∃∀ . 7)
(
)
(
)
(
)
zxQyxPzx ,, ∨
¬
∀
∃
.
8)
() ()()
zxQyxPzyx ,,
¬
∨∀∀∃
.
9)
()()
(
)()
yxQtyxRzysPtzs ,,,,, ∨∨¬∀∃∀ .
10)
()()()
tyxQzyxPtx ,,,, ∨¬∀∃ . 8. Можно привести такой пример: "0")(
=
=
x
x
P
,
"1")( ==
x
x
Q . Предикаты рассматриваются на множестве
R
. Вернуться в Задачи.
Глава 8. Рекурсивные функции. 1. 1)
x
. 2) )1(
+
y
x
.
3)
⎪
⎩
⎪
⎨
⎧
+=−
=+
=
.12,1
,2,
2
),(
kyy
ky
y
x
yxf 4)
y
x
2
. 5)
y
x
. 6) )(sgn x . 7) yx
2
.
8)
⎩
⎨
⎧
+=
=
=
.12,
,2,1
),(
kyx
ky
yxf
9)
⎩
⎨
⎧
+=
=
=
.12,
,2,0
),(
kyx
ky
yxf
10)
⎩
⎨
⎧
>−+
=
=
.0,1
,0,0
),(
yyx
y
yxf Вернуться в
Задачи. 
В Ответы и указания.
В Содержание.




Ответы и указания.

      Глава 1. Высказывания, формулы, тавтологии. 2. 2), 5), 8), 10) – истинные
высказывания. 1), 4), 7) – ложные высказывания. 3), 6) высказываниями не
являются. 3. Обратите внимание, что 7) – составное высказывание. 5. Не являются
тавтологиями: 2), 3), 5). Вернуться в Задачи.
      Глава 3. Исчисление высказываний. 1. 1), 2), 5), 7), 8), 9) – формулы
исчисления высказываний. 3), 4), 6), 10) формулами исчисления высказываний не
являются. 2. 2). 3. 5) Применить лемму. 6), 7), 9) – применить результат 5). 8), 10),
11), 12) – применить результат 9). Вернуться в Задачи.
                                                                       {
      Глава 5. Предикаты. 1. 1) {− 2}. 3) {2}. 5) ( x, y ) ∈ R 2 x − y = 1 . 7) R . 8)       }
{( x, y) ∈ R   2
                         }
                   x ≥ y 2 . 9) {1,2,3,5,7}. 10) {− 1}. 2. 1), 3), 4), 6), 7), 9), 10). 1. 2), 5), 8). 0. 3.
7) Воспользоваться формулой A ↔ B = ¬A¬B ∨ AB .
4. 1) ∀x∀t∀z (¬R( x, y, z ) ∨ P(t , y )) .
2) ∃x∀t (¬R( x, t , z ) ∨ P( x, y )) . 3) ∀t∃s(P(t , y ) ∧ Q( x, s )) .
4) ∃x∀t (P( x, t ) ∧ Q( x, y )) . 5) ∃t∃s∀z (¬R( x, t ) ∨ P(s, y, z )).
6) ∀t∃x∃y∃z (P(t , y ) ∧ Q( x, z )) . 7) ∃x∀z (¬P( x, y ) ∨ Q( x, z )) .
8) ∃x∀y∀z (P( x, y ) ∨ ¬Q( x, z )) .
9) ∀s∃z∀t (¬P(s, y, z ) ∨ R( x, y, t ) ∨ Q( x, y )) .
10) ∃x∀t (¬P( x, y, z ) ∨ Q( x, y, t )) . 8. Можно привести такой пример: P( x) =" x = 0" ,
Q( x) =" x = 1" . Предикаты рассматриваются на множестве R . Вернуться в Задачи.
        Глава 8. Рекурсивные функции. 1. 1) x . 2) x( y + 1) .
                 ⎧       y
                 ⎪ x + , y = 2k ,             y
3) f ( x, y ) = ⎨       2               4) x 2 . 5) x y . 6) sgn ( x) . 7) x 2 y .
                 ⎪⎩ y − 1, y = 2k + 1.
                ⎧1, y = 2k ,                       ⎧0, y = 2k ,
8) f ( x, y ) = ⎨                  9) f ( x, y ) = ⎨
                ⎩ x, y = 2k + 1.                   ⎩ x, y = 2k + 1.
                  ⎧0, y = 0,
10) f ( x, y ) = ⎨                     Вернуться в Задачи.
                  ⎩ x + y − 1, y > 0.




                                                       63

Страницы