Питання для самоконтролю
1. Чи пов’язані між собою логіка висловлювань і логіка предикатів? Що таке предикат? Як позначають предикати? Який предикат називають n-місним? Який предикат називають нульмісним? Які предикати є бінарними відношеннями? Наведіть приклади предикатів різних порядків.
2. Що таке предметні змінні предиката? Що таке предметні константи? Що таке предметна функція? Що таке терм? Наведіть приклади предметних змінних, констант, функцій. Що таке множина істинності предиката? Які предикати називають розв’язними, тотожно істинними й тотожно хибними? Наведіть приклади розв’язних, тотожно істинних і тотожно хибних предикатів і вкажіть їхні множини істинності.
3. Які логічні операції застосовують до предикатів? Вкажіть множини істинностей при застосуванні логічних операцій до предикатів. Дайте визначення і наведіть приклади застосування квантора загальності й квантора істинності до предикатів. Яку предметну змінну називають зв’язаною, а яку — вільною? Чи може та сама змінна бути зв’язаною і вільною в одній формулі? Що означає наявність у предикаті зв’язаної предметної змінної? Наведіть приклади зв’язування змінних.
4. Що таке елементарна формула? Як утворюються складні формули? Яку формулу логіки предикатів називають тавтологією? Яку формулу логіки предикатів називають замкненою? Як визначають порядок операцій у формулі? Наведіть приклади.
5. Які формули називають еквівалентними? Вкажіть еквівалентності, пов’язані з кванторами: сформулюйте правило перенесення квантора через заперечення, запишіть формули щодо винесення квантора за дужки, щодо перестановки однойменних кванторів, перейменування зв’язаних змінних, запишіть дистрибутивні закони для квантора загальності при кон’юнкції і для квантора існування при диз’юнкції. Для чого використовують еквівалентні перетворення? Наведіть приклад застосування еквівалентних перетворень.
6. Які теореми називають взаємно оберненими? Чи рівнозначні в загальному випадку пряма й обернена теореми? Які теореми називають взаємно протилежними? Чи рівнозначні в загальному випадку взаємно протилежні теореми? Чи можуть бути одночасно істинними взаємно обернені теореми?
7. Яку формулу називаються зведеною формою? Яка формулу називають випереджальною нормальною формою? Чи для кожної формули існує еквівалентна їй випереджальна нормальна форма? Наведіть алгоритм побудови випереджальної нормальної форми.
8. Що є аксіомами числення предикатів? Які правила виведення можна використовувати в численні предикатів? Чи використовуються в численні предикатів допоміжні правила виведення? Якщо так, то які? Сформулюйте правило перейменування вільних змінних. Сформулюйте правило перейменування зв’язаних змінних. Сформулюйте теорему Геделя про повноту числення предикатів. Поясніть, що таке розв’язність формальної системи. Чи є розв’язним числення предикатів?
1 Олівер Хевісайд (Oliver Heaviside; 1850–1925) — англійський інженер, фізик, математик.
2 Ми розглядаємо логіку предикатів вузьку (першого порядку), яка відрізняється від логіки предикатів вищих ступенів тим, що квантори вживаються в формулах лише з предметними змінними, а не з предикатними чи функціональними змінними.
3 Курт Гедель (Kurt Gödel; 1906–1978) — австрійський математик.