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

UptoLike

ВУЗ: 

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

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

Рубрика: 

42
1)
()
111
xxx =∀ .
2)
()
122121
xxxxxx =→=∀∀ .
3)
()()
313221321
xxxxxxxxx
=
→=→=∀∀∀
.
4)
()
111
xxx ≤∀ .
5)
(
)()
21122121
xxxxxxxx
=
→≤→≤∀∀
.
6)
()()
313221321
xxxxxxxxx
≤
→≤→≤∀∀∀ .
Моделью данной теории является частично упорядоченное множество.
Для теорий первого порядка справедлива следующая теорема.
Теорема Гёделя о неполноте. Во всякой достаточно богатой теории первого
порядка (в частности, во всякой теории, включающей формальную арифметику),
существует такая истинная формула
A
, что ни
A
, ни
A
¬
не являются выводимыми
в данной теории.
В
Содержание.
Задачи.
1.
Укажите, какие из следующих выражений являются формулами
исчисления предикатов. В каждой формуле укажите свободные и связанные
вхождения переменных:
1)
),( y
x
y
P
x
∀∀ .
2)
),( y
x
y
P
x
→∃ .
3)
)(),( zQy
x
y
P
x
→∀∃ .
4)
()
BABA →→→¬ )( .
5)
),( y
x
y
P
a ∀→ .
6)
()
)(),( xQyxPyx →∀∃ .
7)
)()( yy
Q
x
xP
∀→∀ .
8)
()()
),(),( zyPyxPzx →∀∃¬ .
9)
()()
)()()( xxRxxQxP ∀∃∧→
.
10)
()
),()()( yxxQxQxPx ∀→→∀ .
2.
Пусть n – натуральное число. Даны следующие утверждения.
•
)(n
A
– “число n кратно 5”;
•
)(n
B
– “число n кратно 2”;
•
)(n
– “число n кратно 4”; 
1)   ∀x1 ( x1 = x1 ) .
2)   ∀x1∀x2 ( x1 = x2 → x2 = x1 ) .
3)   ∀x1∀x2 ∀x3 ( x1 = x2 → ( x2 = x3 → x1 = x3 )) .
4)   ∀x1 ( x1 ≤ x1 ) .
5)   ∀x1∀x2 ( x1 ≤ x2 → ( x2 ≤ x1 → x1 = x2 )) .
6)   ∀x1∀x2 ∀x3 ( x1 ≤ x2 → ( x2 ≤ x3 → x1 ≤ x3 )) .
       Моделью данной теории является частично упорядоченное множество.

       Для теорий первого порядка справедлива следующая теорема.

      Теорема Гёделя о неполноте. Во всякой достаточно богатой теории первого
порядка (в частности, во всякой теории, включающей формальную арифметику),
существует такая истинная формула A , что ни A , ни ¬A не являются выводимыми
в данной теории.

В Содержание.




       Задачи.

      1. Укажите, какие из следующих выражений являются формулами
исчисления предикатов. В каждой формуле укажите свободные и связанные
вхождения переменных:
1) ∀x∀yP( x, y ) .
2) ∃x → yP( x, y ) .
3) ∃x∀yP( x, y ) → Q( z ) .
4) (¬A → B) → ( A → B ) .
5) a → ∀yP( x, y ) .
6) ∃x∀y (P( x, y ) → Q( x) ) .
7) ∀xP( x) → ∀yQ( y ) .
8) ¬(∃x∀z (P( x, y ) → P( y, z ) )) .
9) (P( x) → Q( x) ) ∧ ∃x(∀xR( x) ) .
10) ∀x(P ( x) → Q( x) ) → ∀xQ( x, y ) .

      2.   Пусть n    – натуральное число. Даны следующие утверждения.
• A(n)     – “число   n кратно 5”;
• B ( n)   – “число   n кратно 2”;
• C ( n)   – “число   n кратно 4”;



                                           42

Страницы