13.4 Контрольні запитання та завдання

1. Дайте визначення поняттю предикат.

2. Що називається порядком предиката?

3. Наведіть приклади n-місних предикатів.

4. Як здійснюється складання матриці предиката?

5. Дайте визначення терму.

6. Коли предикат хА(х,у) набуває значення "Істина"?

7. Що називається формулою в логіці першого порядку?

8. Сформулюйте поняття інтерпретації формули логіки першого порядку.

9. Дайте визначення поняттю логічного наслідку в логіці предикатів.

13.5 Приклади аудиторних і домашніх задач

1. З наведених нижче речень випишіть окремо висловлювання, окремо – предикати:

a) х>0;

б) 2+3=6;

в) про нього щось говорять;

г) x брат y;

д) протилежні сторони A s B паралелограма рівні;

е) кожне явище x має свою причину y.

2. Визначіть, чи еквівалентні дані предикати:

a) х²=1 й х=1;

б) х²=х й х=1.

3. Визначіть вільні і зв'язані входження кожної зі змінних у таких формулах:

a)х)P(x,y)y)Q(y);

б)х)(P(x)P(y));

в)х)(P(x)Q(y))y)R(x,y);

г)х)[(P(x)Q(y))y)R(x,y)].

4. Нехай х та y – деякі люди, Q(x,y) означає «x батько y». Сформулюйте природною мовою дані висловлювання, визначивши їх значення істинності:

a)х)y)Q(x, y);

б)х)y)Q(x, y);

в)y)х)Q(x, y);

г)y)х)Q(x, y);

д) х)y)Q(x, y);

е) х)y)Q(x, y).

5. Опустіть знаки заперечення безпосередньо на предикати або булеві змінні:

a) x)((y)(B(y)z)C(z))A(x)));

б) y)(x)(A(y,z)B(x))C(z));

в) x)((y)(A(x)B))C(x,y));

г) u)v)(P(u)Q(v)A(z)).

6. Наведіть до ПНФ такі висловлювання:

a)y)(P₁(y)x)P₂(x, y));

б) x)((y)A(x,y)y)z)(C(z)B(x,y));

в)xy)B(x,y)~x)A(x);

г) y)x)(A(x)B(y));

д)x)P₁(x)x)(P₂(y)y)P₃(x,y)).

7. Визначіть, чи є формула G логічним наслідком множини формул K:

a)	G=x)(P(x)Q(x)), K={x)P(x),x)Q(x)};
б)	G=x)¬R(x), K={(x)R(x)x)Q(x),¬Q(a)};
в)	G=x)R(x,x), K={xy)(R(x,y)R(y,x)), xyz)(R(x,y)R(y,z)R(x,z))};
г)	G=x)(P(x)¬R(x)), K={x)[P(x)y)(Q(y)S(x,y))], x)[R(x)y)(Q(y) ¬S(x,y))]x)P(x)}.

14 Практичне заняття № 12. Основні поняття теорії графів

14.1 Мета заняття

Ознайомитися з основними поняттями теорії графів. Набути навичок задання графів різними способами, а також виконання основних операцій над графами.

14.2 Методичні рекомендації до самостійної роботи студентів

Під час підготовки до практичного заняття необхідно вивчити відповідний розділ конспекту лекцій та ознайомитися з матеріалом підручників [1, c. 239-246, c. 248-260; 2, c. 239-246, c. 248-260; 3, c. 89-102; 6, c. 21-41, c. 178-189; 9, c. 156-181; 12, c. 297-309; 14, c. 11-53; 17, c. 64-128].

При повторенні матеріалу слід звернути увагу на такі питання:

• походження графів;

• визначення графів;

• види графів;

• способи задання графів;

• орієнтовані та неорієнтовані графи;

• маршрут, ланцюг, цикл, шлях, контур;

• зв'язність графів, компонента зв’язності, сильнозв'язані графи;

• ступінь вершини, сума ступенів вершин графа;

• досяжність;

• визначення ізоморфізму графів, приклади ізоморфних графів;

• ізоморфізм як відношення еквівалентності на множині графів.