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