Розв’язок. Введемо атомарні висловлення: − « ділиться на 9»; − «

Введемо атомарні висловлення: − « ділиться на 9»; − « ділиться на 3». Висловлення «Якщо ділиться на 9, то ділиться на 3» можна представити у вигляді формули . З одночасного виконання посилань і можемо зробити висновок за правилом відділення: « ділиться на 3».

9 ЛОГІКА ТА ОБЧИСЛЕННЯ ПРЕДИКАТІВ

 

9.1 Мета заняття

 

Ознайомлення c основними поняттями логіки та обчислення предикатів. Вивчення на практичних прикладах способів побудови та інтерпретації предикатів, методів перевірки правильності міркувань, правил для проведення дедуктивних умовиводів.

 

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

 

Під час підготовки до практичного заняття необхідно повторити лекційний матеріал, розділи літератури [1-10] з таких питань: основні поняття і визначення логіки предикатів; операції логіки предикатів, кванторні операції; формули і їхня інтерпретація в логіці предикатів; закони і тотожності логіки предикатів; випереджені нормальні форми; вивідність у логіці предикатів; обчислення предикатів (мова, аксіоми, правила висновку).

Підготовка і виконання практичного заняття проводиться в два етапи.

Перший етап пов’язаний з вивченням на практичних прикладах таких основних понять і визначень: предикат; універс (предметна область); область визначення предиката; область значень предиката; -місцевий предикат (одномісний, двомісний, нульмісний предикат); терм; індивідуальний символ; символ предметних змінних; функціональний символ; квантор загальності; квантор існування; елементарна формула логіки предикатів (атом); область дії квантора; зв’язана змінна; вільна змінна; замкнута формула; інтерпретація формули логіки предикатів; загальнозначуща, суперечлива, здійсненна, незагальнозначуща формула; логічний наслідок; випереджена нормальна форма; обчислення предикатів; правило видалення квантора загальності; правило введення квантора загальності; правило видалення квантора; правило введення квантора існування; правило відділення; правило зв’язування квантором загальності; правило зв’язування квантором існування; правило перейменування зв’язаної змінної.

При виконанні першого етапу практичного заняття студент повинен запропонувати і записати індивідуальний приклад для кожного з розглянутих вище понять і визначень.

Другий етап виконання практичного заняття пов’язаний з розв’язанням практичних завдань, представлених у підрозділі 9.3, на основі запропонованих типових прикладів (див. підрозділ 9.4).

 

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

9.3.1 Контрольні запитання

 

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

2. Що називається порядком предиката? Наведіть приклади -місцевих предикатів.

3. Які типи символів дозволяється використовувати для побудови атомів логіки предикатів?

4. Дайте визначення поняття «терм».

5. Що розуміють під предметною областю?

6. Що розуміють під квантором загальності?

7. Дайте визначення поняття «квантор існування».

8. Які змінні називаються зв’язаними, а які - вільними?

9. З чого складається інтерпретація формули логіки предикатів?

10. Поясніть, як здійснюється заміна зв’язаної змінної.

11. Сформулюйте комутативні властивості кванторів.

12. Запишіть формули закону де Моргана для кванторів.

13. Дайте визначення випередженої нормальної форми.

14. За допомогою яких законів можна опустити знаки операцій заперечення безпосередньо на предикати?

15. Яким чином можна перетворити довільну формулу логіки предикатів у випереджену нормальну форму?

16. Перелічите правила висновку, які можна використовувати для проведення дедуктивних умовиводів з висловленнями логіки предикатів.

17. Сформулюйте призначення вирахування предикатів.

18. Запишіть формули аксіом вирахування предикатів.

19. Перелічить правила висновку обчислення предикатів.

 

9.3.2 Контрольні завдання

 

Завдання 1. З наведених нижче речень виписати окремо висловлення, окремо предикати: а) ; б) 2+3=6; в) про нього щось говорять; г) брат ; д) протилежні сторони і паралелограма рівні; е) кожне явище має свою причину .

Завдання 2. У наведених одномісних предикатах зробити можливі підстановки змінної так, щоб отримати істинні висловлення: а) – найвища гірська вершина у світі; б) – представник діалектичної логіки; в) ; г) – логічний зв’язок; д) – видатний античний логік.

Які з них допускають одну, а які - багато підстановок?

Завдання 3. Задано предикати: а) ; б) ; в) ; г) . Записати висловлення: 1) ; 2) ; 3) ; 4) .

Завдання 4. Записати наведені нижче твердження в символічній формі, використовуючи предикати. Якщо буде потреба, то вказати предметну область.

а) на кожній вулиці буде свято;

б) деякі машини розумніші за людей;

в) кожний грає в теніс краще, ніж Фред;

г) для кожної дії існує рівна і протилежно спрямована протидія;

д) кожний гравець у гольф, зрештою, буде обіграний більш сильнішим гравцем.

Завдання 5. Задано предикати: а) ; б) ; в) ; г) .

Записати висловлення: 1) ; 2) ; 3) ; 4) .

Завдання 6. Довести хибність формули , де .

Завдання 7. Записати наступні висловлення, використовуючи знаки кванторів: а) існує число таке, що ; б) будь-яке число або позитивне, або негативне, або дорівнює нулю.

Завдання 8. Указати вільні й зв’язані змінні входження кожної зі змінних у наступних формулах: а) ; б) ; в) ; г) .

Завдання 9. Нехай − « − натуральне число», − « − ціле число», − « − просте число», − « − парне число», − « − непарне число», − « ділиться на ».

Сформулюйте природною мовою наступні висловлення, встановивши їхні значення істинності: а) ; б) ; в) ; г) ; д) .

Завдання 10. Вказати вільні й зв’язані входження змінних у наступні формули, що містять предикати й :

а) ;

б) ;

в) ;

г) .

Завдання 11. Привести до випередженої нормальної форми наступні формули:

а) ;

б) ;

в) .

Завдання 12. Визначити, чи є формула логічним наслідком формул і .

Завдання 13. Застосовуючи дедуктивні правила логіки предикатів, вивести висновок з наступних засновок:

а) якщо один з нас піде завтра на перше заняття, то він повинен буде встати рано, а якщо ми підемо сьогодні ввечері в театр, то він ляже спати пізно. Якщо кожний з нас ляже пізно спати, а встане рано, то будемо задовольнятися п’ятьома годинами сну. Але ми не можемо задовольнятися п’ятьома годинами сну;

б) якщо всі ціни одночасно підвищуються, то підвищується і заробітна плата. Всі ціни високі або застосовується регулювання цін. Якщо застосовується регулювання цін, то немає інфляції. Спостерігається інфляція.

 

9.4 Приклади аудиторних і домашніх завдань

 

Завдання 1. Представити у вигляді предикатів наступні речення:

1) «Студенти здають сесію»; 2) «Число більше, ніж число »; 3) «Брат Марини».