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) «Брат Марини».

Розв’язок.

1) Речення «Студенти здають сесію» може приймати значення «Істина» або «Хибність», тому його можна представити у вигляді предиката. У внутрішній структурі даного речення можна виділити присудок «здають», підмет «студенти» і доповнення «сесію». Останні можна розглядати як предметні константи. Таким чином, отримали двомісний предикат ЗДАВАТИ (студенти, сесію).

2) Присудком у даному реченні є слово «більше». Представимо підмет «» і доповнення у вигляді термів. Причому терм«» має внутрішню структуру, оскільки його можна представити за допомогою функціонального символу плюс. Тоді вихідне речення прийме вид двомісного предиката: БІЛЬШЕ (плюс, ). Тут− предметна змінна, а 1 константа.

3) Речення «Брат Марини» не можна представити у вигляді предиката, оскільки його значенням є не «Істина» або «Хибність», а деякий елемент предметної області, що відповідає великій кількості людей.

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

Розв’язок.

1) ; 2); 3); 4); 5) Ждон любить Сью більше, ніж Мері.

Завдання 3. Розглянути як предметну область множину дійсних чисел. Записати у вигляді виразів логіки предикатів математичні твердження:

а) «Для всіх вірно, що»;

б) «Існує число, квадрат якого дорівнює 4».

Розв’язок.

Введемо предикат ДОРІВНЮЄ (), який істинний у тому випадку, якщо значення змінноїдорівнює значенню. Тоді, використовуючи квантори, можна записати:ДОРІВНЮЄ;ДОРІВНЮЄ.

Завдання 4. Визначити, які змінні є зв’язаними, а які – вільними, в наступних формулах: а) ; б); в).

Розв’язок. Обидві змінні у формулі а) є вільними. У формулі б) змінна є зв’язаною, а змінна− і зв’язаною, і вільною (зміннавільна в предикатіі зв’язана в предикаті. У формулі в) зміннає зв’язаною, а змінна− вільною.

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

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

Розв’язок.

а) «Існують ітакі, що»;

б) «Існує таке, що»;

в) «Для кожного існуєтаке, що»;

г) «Існує таке, що для всіхвиконується»;

д) «Джон любить Сью більше, ніж кого-небудь».

Завдання 6. Нехай заданий предикат . Що можна сказати про істинність формули, якщо предметною областю є: а) множина дійсних чисел; б) предметна область містить комплексне число?

Розв’язок.

Формула істинна, якщо універсом (предметною областю) є множина цілих чисел., однак вона помилкова, якщо предметна область містить комплексне число.

Завдання 7.Нехай, тоді твердженняхибне.

Якщо універс − множина додатних цілих чисел, то що можна сказати про істинність: а) ; б)?

Розв’язок.

а) істинно; б) істинно.

Завдання 8. Отримати випереджену нормальну форму для формули .

Розв’язок.

.

ПЕРЕЛІК ПОСИЛАНЬ

1. Бондаренко, М. Ф. Компьютерная дискретная математика [Текст] : учебник для вузов / М. Ф. Бондаренко, Н. В. Белоус, А. Г. Руткас. – Харьков: «Компания СМИТ», 2004. – 480 с.

2. Тевяшев, А. Д. Основы дискретной математики в примерах и задачах [Текст] : учеб. пособие для вузов / А. Д. Тевяшев, И. Г. Гусарова. – Харьков: ХНУРЭ, 2003. – 272 с.

3. Бардачев, Ю. Н. Основы дискретной математики [Текст] : учебное пособие / Ю. Н. Бардачев, Н. А. Соколова, В. Е. Ходаков; под редакцией В. Е. Ходакова – Херсон: ХГТУ, 2000. – 356 с.

4. Сигорский, В. П. Математический аппарат инженера [Текст] / В. П. Сигорский. – Киев: Техніка, 1977. – 768 с.

5. Капитонова, Ю. В. Лекции по дискретной математике [Текст] / Ю. В. Капитонова, С. Л. Кривой, А. А. Летичевский, Г. М. Луцкий. – СПб.: БХВ-Петербург, 2004. – 624 с.

6. Андерсон, Дж. А Дискретная математика и комбинаторика [Текст] / Джеймс А Андерсон. – М.: Издательский дом «Вильямс», 2003. – 960 с.

7. Кузнецов, О. П. Дискретная математика для инженера [Текст] / О. П. Кузнецов, Г. М. Адельсон-Вельский. – М.: Энергоатомиздат, 1988. – 480 с.

8. Яблонский, С. В. Введение в дискретную математику [Текст] / С. В. Яблонский. – М.: Наука, 1986. – 384 с.

9. Бондаренко, М. Ф. Збірник тестових завдань з дискретної математики [Текст] / М. Ф. Бондаренко, Н. В. Білоус, І. Ю. Шубін. – Харків: ХТУРЕ, 2000. – 156 с.

10. Новиков, Ф. А. Дискретная математика для программистов [Текст] / Ф. А. Новиков. – СПб: Питер, 2001. – 304 с.

Навчальне видання

МЕТОДИЧНІ ВКАЗІВКИ

до практичних занять з дисципліни

«ДИСКРЕТНА МАТЕМАТИКА»

(Частина 1)

для студентів усіх форм навчання напряму 6.050101 – Комп’ютерні науки

Упорядники: ВАСИЛЬЦОВА Наталія Володимирівна

ЧАЛА Лариса Ернестівна

Відповідальний випусковий В.М. Левикін

Редактор Б.П. Косіковська

Комп’ютерна верстка Л.Д. Медведєва

План 2012 (перше півріччя), поз.6

Підп. до друку 05.01.12 Формат 60х84 1/16 Спосіб друку – ризографія

Умов.друк.арк. 3,9. Облік.вид.арк. 3,6. Тираж 30 прим.

Зам. №1-6 Ціна договірна

ХНУРЕ. Україна, 61166, Харків просп.. Леніна, 14

Віддруковано в навчально-науковому

Видавничо-поліграфічному центрі ХНУРЕ