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

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

2. Що розуміють під істиннісним значенням висловлювання?

3. Які висловлювання називаються атомами?

4. Які існують логічні зв'язки?

5. У чому відмінність дедуктивних висновків від недедуктивних?

6. Дайте визначення логічного наслідку одного (декількох) висловлювань.

7. У чому полягає метод доведення від противного?

8. Наведіть можливі галузі застосування математичної логіки.

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

1. Чи є дані формули загальнозначущими, суперечливими або несуперечливими:

а) ;

б) (AB)(BA);

в) (A(BA))A;

г) (A¬B)(¬AB)?

2. Розставити різними способами дужки у таких формулах:

а) ¬А¬BC;

б) ABCD.

3. Зменшити якомога більшу кількість дужок у формулі:

а) (¬((A) (C)))(B);

б) (((A)(B))(C))((A)((B)(C)));

в) ((B)~(¬(C)))(((A)(A))((B)(D))).

4. Доведіть, що заперечення висловлювання "А є достатня та необхідна умова для В" еквівалентно висловлюванню "А є достатня та необхідна умова для В".

5. Використовуючи тотожності, спростіть формули логіки висловлювань:

а) (АВС)(А(ВС))В;

б) (АВ)САСВА.

6. Перевірте правильність даних висновків:

а) ;

б) ;

в) .

7. Запишіть формулами дані висловлювання:

a) обчислення виконані точно, або конструкція недосконала;

б) якщо погода буде добра, ми підемо гуляти і не будемо готуватися до КДМ;

в) якщо я поїду на автобусі, то спізнюся на екзамен з КДМ, або я скористаюся таксі;

г) тиск спадає, і система не працює;

д) А допомагає П, або П допомагає А, або вони допомагають один одному;

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

ж) невірно, що якщо я не знаю математичну логіку, то я складу екзамен з КДМ.

13 Практичне заняття № 11. Логіка першого порядку (лпп)

13.1 Мета заняття

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

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

Під час підготовки до практичного заняття крім конспекту лекцій рекомендується використовувати [1, c. 207-231; 2, c. 207-231; 3, c. 78-81; 4, c.74-82, 9, c. 82-99; 15, c. 68-89; 17, c. 23-63].

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

• терм, предикат;

• зміст вільних і зв'язаних змінних в алгебрі предикатів;

• правильно побудовані формули, інтерпретація формул у ЛПП;

• логічні висновки в ЛПП;

• квантори;

• випереджені нормальні форми (ВНФ);

• перетворення будь-якої формули до ВНФ;

• закони логіки першого порядку.

13.3 Приклади розв’язання типових завдань

1. Записати природною мову дані висловлювання логіки предикатів.

а) ДОРІВНЮВАТИ (х,5);

б) ЗНАТИ(тато(Вася), математика).

Проаналізуємо кожен предикат окремо.

а) Предикат ДОРІВНЮВАТИ(х,5) відповідає твердженню «x дорівнює 5» природної мови. Тут 5 – константа, х – предметна змінна;

б) У висловлюванні ЗНАТИ(тато(Вася), математика) функціональний символ «тато(х)» приймає значення з множини людей, що відповідає відношенню «бути батьком х». Тому вираз тато(Вася) слід інтерпретувати як «Васин тато». Таким чином, предикат ЗНАТЬ(тато(Вася), математика) відповідає реченню «тато у Васі знає математику» природної мови. У предикаті «Вася» та «математика» є константами.

2. Одержати ПНФ для формули x)yz)P(x,y)P(y,z)z)Q(x,y,z)).

Скористаємося алгоритмом.

xyz)P(x,y)P(y,z)z)Q(x,y,z))=

x)y)(z)P(x,z)P(y,z))z)Q(x,y,z))=

=xy)(z)(P(x,yP(y,z))u)Q(x,y,u))=

xy)z)u)(P(x,y)P(y,z)Q(x,y,u)).

3. Довести тотожну істинність формули

x)(А(х)В(х(х)А(х)x)В(х)).

Доводитимемо від противного. Припустимо, що є така інтерпретація предикатних і предметного символів, а також така предметна галузь М, у якій наведена формула помилкова. У цьому випадку x)(А(х)В(х))=1, х)А(х)=1, x)В(х)=1. Існує рішення в області М таке, що А(р)=1. Маємо А(р)=1, тобто В(р)=0, а це суперечить тому, що x)В(х)=1. Це протиріччя доводить неможливість випадку, коли вихідна формула помилкова.

4. Розглянемо формулу G: x)(P(x)Q(f(x),a)).

У G є одна константа а, один одномісний функціональний символ f, один одномісний предикатний символ Р та один двомісний предикатний символ Q. Нижче наводиться інтерпретація I формули G.

Область:	D={1,2}.
Оцінки для а:	.
Оцінки для f:	f(1) f(2) 2 1
Оцінки для Р й Q:	P(l) P(2) Q(l, 1) Q(l, 2) Q(2, 1) Q(2, 2) Х І І І Х І

Якщо х=1, то (P(x)Q(f(x),a))=P(1)Q(f(1),a)=P(1)Q(2,1)=ХХ=І.

Якщо х=2, то (P(x)Q(f(x),a))=P(2)Q(f(2),a)=P(2)Q(1,1)=ІІ=І.

Оскільки (P(x)Q(f(x),a)) істинно для всіх елементів x з області D, то формула x)(P(x)Q(f(x),a)) істинна в інтерпретації I.

5. Запишемо такі твердження:

(a) Кожне раціональне число є дійсним числом.

(б) Існує число, яке є простим.

(в) Для кожного числа х існує таке число у, що х<у.

Позначимо «х є просте число» через Р(х)_, «х є раціональне число» через Q(x), «x є дійсне число» через R(х) та «х менше у» через МЕНШЕ(х,у). Тоді подані вище ствердження можуть бути записані відповідно виразами:

(a')x)(Q(x)R(x));

(б')x) P(x);

(в')х)у) МЕНШЕ(x, у).