Задачі для самостійного розв’язування. 1. Напишіть, використовуючи мову логіки предикатів, такі речення:
1. Напишіть, використовуючи мову логіки предикатів, такі речення:
а) ” число х більше 2 ”;
б) ” х сестра у ”;
в) ” діагоналі ромба перпендикулярні ”;
г) ”кожне явище має свою причину ”.
2. Перекладіть природною мовою такі висловлювання логіки предикатів:
а) ДОРІВНЮВАТИ ( х , 10 );
б) ЛЮБИТИ (мама (Каті), гімнастика ) ;
в) БІЛЬШЕ ( плюс ( х , 1 ) , 1 ).
3. Змінні функції ” х > у ” набувають значень на множині
{ 2,3,4 }; Р 
, Р 
– предикати, що задаються цією функцією відповідно при алфавітному і зворотному йому порядках. Необхідно встановити:
а) область визначення предикатів Р і Р ;
б) значення істинності Р (3,4) і Р (3,4).
4. Визначте еквівалентність таких предикатів:
а) х 
= х і х = 1;
б) х = 1 і х = 1;
в) х 
= 1 і х = 1.
5. Запишіть такі висловлювання, використовуючи логіку предикатів:
а) будь-яке парне додатне число ;
б) існує таке число х, що х + 1 = 10 ;
в) для будь-якого х завжди х + 0 = х .
6. Вкажіть вільні та пов’язані входження кожної зі змінних у таких формулах:
а) 
х Р ( х,у ) 
х Q ( х,у ) ;
б) 
у Q ( х,у ) 
х Р ( х,у ) ;
в) х [( Р ( х,у ) 
Q ( у )) у Р ( х,у ) ] .
7. Наведені висловлювання для предиката Р(х,у), де "х сестра у”, сформулювати природною мовою, визначивши їх значення істинності:
а) у х Р ( х,у ) ; г) у х Р ( х,у ) ;
б) х у Р ( х,у ) ; д) х у Р ( х,у ) ;
в) х у Р ( х,у ) ; е) х у Р ( х,у ) .
8. Предикат 
задано на предметній області D={а, в} такою матрицею:
| х | а | а | в | в |
| у | а | в | а | в |
| Р(х,у) | Х | І | І | І |
Яка з наведених формул визначає цей предикат?
а) х у Р ( х,у ); г) у х Р ( х,у );
б) у х Р ( х,у ); д) у Р ( а;у );
в) х Р ( х,а ); є) х у Р ( х,у );
9. Визначте вільні та пов’язані входження змінних у такі формули, що містять предикати Р і 
:
а) х Р ( х , х );
б) х ( х 
Р ( х , х ) Р ( х , х )) ;
в) х ( х Р ( х , х ) 
Р ( х , х )) ;
г) х х Р ( х , х ) Q (х ) ;
д) х Р ( х , х ) х Р ( х , х ) .
10. Знайдіть значення істинності таких предикатних виразів:
а) P ( a , f ( a )) P ( b , f ( b ));
б) х y P ( x,y ) P ( f ( x ), f ( y ))
на предикатній області D = { 3,4 } при значенні функціональних символів:
f( a ) = 4 , f( b ) = 3; предикатів P( 3,3, ) = І, P( 3,4, ) =
= І, P( 4,3, ) = І, P( 4,4, ) = Х.
11. Оцінити формулу x P( x ) Q ( f( x ),a ) на інтерпретації при: D = { 1,2 };
a = 1; f ( 1 ) = 2; f ( 2 ) = 1;P ( 1 ) = Х; P ( 2 ) = І; Q ( 1,1 ) = = І; Q ( 1,2 ) = І;
Q ( 2,1 ) = Х; Q ( 2,2 ) = І.
12. Визначити рівносильність формул x P(x ), x P(x ) на двохелементній множині M = { a,b }.
13. Визначити рівносильність формул F=P(x1, x2)Ú P(x1, x3) і G=P(x ,x ) P(x ,x ), які задані на множині M = { a,b } предикатами Q ( x,y ) та Q ( x,y ), наведеними в таблицях
| х | у | 
| х | у | 
| |
|
| Х |
|
| х | |
|
| 
| І |
|
| І | |
|
|
| І |
|
| Х | |
|
|
| Х |
|
| І |
14. Для заданих предикатів х ( Р ( х ) 
Q ( х )) і
z ( Р ( z ) Q ( у )) встановити їх еквівалентність.
15. Винести за дужки квантори:
а) х Р ( х,у ) ( х Q ( х ) у Q ( у ));
б) х у Р ( х,у ) х у (Q (х, z ) у Р ( х,у ));
в) х Р ( х,у ) ( у Р ( у ) Q ).
16. Довести загальнозначущість формули
х Р ( х ) у Р ( у ).
17. Довести суперечливість формули
х Р ( х ) у Р ( у ).
18. Показати , що комутативні властивості для виразу
х у Р ( х,у ) 
у х Р ( х,у )
не виконуються.
19. Довести, що:
а) ├ 
x (А → В) → ( x А → x В);
б) А, x А → В ├ x В;
в) ├ x1 x2 … xm А → А;
г) x ( А → В) 
(А → x В);
д) x (В → А) ( х В → А);
е) x (А D) → ( x А x В).
Коментарі. Основні відомості з логіки предикатів, кванторів і формул логіки предикатів, викладені в цьому розділі, dзяті з [9, 20], рівносильність формул логіки предикатів і логічні висновки ‒ з [1, 7, 21] , а закони, тотожності логіки предикатів і випереджені нормальні форми випливають із [20, 28].