Основы построения и функционирования интеллектуальных информационных систем. Былкин В.Д - 33 стр.

Вопросы и упражнения
1. Дайте определение предиката.
2. Дайте определение формулы логики предикатов.
3. Какие вхождения переменных являются свободными, а какие связанными в следующих
формулах:
а) x(P(х, у) → y Q(y)),
б) х(Р(х,у) → y R(х,у),
в) ( ┐ƎzQ(z, z) & R (f (у, z)))
4. Пусть f , g , h - функциональные символы; Р , Q -предикатные символы.
Являются ли формулами следующие слова:
a) Q(x, f(y), h(y, y, z)),
б) (P(x) → y (Q (x, y, z) & Р(g (x,y)))),
в) Q(P(x), f(y), f(z)),
г) f(h(x, y, z)).
Выделите из них термы.
5. Дайте определение выполнимой, общезначимой и невыполнимой формул логики предикатов.
6. Пусть предикаты N(x), C(x), P(x), П(x), Ч(x), D(x, y)имеют соответственно следующий смысл: x -
натуральное число; x- целое число; x — простое число; x - положительное число; x - четное число;
x - делитель y. Сформулируйте смысл следующих формул и укажите, какие из них являются
тождественно истинными

а)   x( N ( x)    C ( x)) ,

б)   x(C (e)     Ч ( x)vЧ ( x)) ,

в)   x y((C ( x) & C ( y)          D( x, y)) ,

г)   x( P( x) & Ч ( x) ,

д) x(C ( x) & П ( x) N ( x)) .
7. Докажите тождественную истинность следующих формул:

а)    x( P( x)          P( x)) ,

б) ( P( x) & (Q       R( x)))        ( xP( x)     R( x)    Q)) , где x не свободна в Q,

в) ( P( x)        Q( x))           ( xP( x) & xQ( x))) ,

г) ( P( x)        Q( x))        ( xP( x) & xQ( x))) .

8. Докажите эквивалентность формул:

а)   xF (x) и x F (x)

б) x( F ( x)     A) и      x( F ( x)      A ,



                                                           33