Методом невизначених коефіцієнтів побудувати поліном Жегалкіна для наступних функцій: а) ; б) ; в) , г) .
Завдання 8. Провести дослідження на лінійність булевих функцій: а) ; б) ; в) .
Завдання 9. Довести повноту таких систем функцій шляхом зведення їх до відомих повних класів: а) ; б) ; в) .
Завдання 10. Перевірити на повноту такі класи функцій: а) ; б) ; в) .
Завдання 11. За допомогою теореми Поста перевірити на повноту набори булевих функцій: а) , б) , в) , г) .
7.4 Приклади аудиторних і домашніх завдань
Завдання 1. Визначити, чи зберігає 0 і 1 функція .
Розв’язок.Перевіримо значення даної булевої функції на нульовому й одиничному двійкових наборах: ; .
Отже, дана функція зберігає 1 і не зберігає 0.
Завдання 2. Визначити відношення порядку для інтерпретацій функції і функції .
Розв’язок.Для функції однієї змінної маємо два набори змінних: (0) і (1). Відношення часткового порядку встановлюється таким чином: . Тут усі пари порівнянні.
Для функції двох змінних маємо чотири набори змінних: , для яких відношення часткового порядку встановлюється так: . Розглянуті набори є порівнянними, а набори і не є порівнянними.
Завдання 3. Провести дослідження на монотонність функції .
Розв’язок.Для функції запишемо всі набори значень змінних, для яких виконується відношення порядку, визначимо значення функції на даних наборах і порівняємо їх:
Функція є монотонною.
Завдання 4. Провести дослідження на монотонність функції .
Розв’язок.Для функції запишемо всі набори значень змінних, для яких виконується відношення порядку, визначимо значення функції на даних наборах і порівняємо їх:
.
.
.
.
Функція не є монотонної, тому що при не виконується умова .
Завдання 5. Побудувати поліном Жегалкіна для функції .
Розв’язок.Побудуємо поліном Жегалкіна, скориставшись наступним методом: 1) побудуємо еквівалентну формулу, використовуючи операцію кон’юнкції і заперечення; 2) замінимо на і розкриємо дужки у формулі, користуючись законом дистрибутивності . Дійсно виконуються такі рівності , , звідки
,
Оскільки , то .
Завдання 6. Використовуючи метод невизначених коефіцієнтів побудувати поліном Жегалкіна для булевої функції трьох змінних, яка задається таким чином: .
Розв’язок.Поліном Жегалкіна для функції будемо шукати у вигляді:
, де .
Коефіцієнти визначаються із рівності для довільного припустимого набору :
;
;
;
, тому ; ;
, тому ;
, отже ;
Отже, і .
Звідси поліном буде мати вигляд .
Завдання 7. Провести дослідження на лінійність функції .
Розв’язок.Побудуємо поліном Жегалкіна функції , використовуючи такі тотожності: , .
.
Функція не є лінійною, оскільки її поліном Жегалкіна містить кон’юнкції змінних.
Завдання 8. Системи (штрих Шеффера) і (стрілка Пірса) функціонально повні. Довести повноту систем і .
Розв’язок.Проведемо такі перетворення: ,
; . Тому зводиться до , а зводиться до .
Завдання 9. Перевірити на слабку функціональну повноту систему , що складається з однієї функції , яка задана таблицею істинності (табл. 7.1).
Таблиця 7.1 − Таблиця істинності функції
Розв’язок.Функція немонотонна, тому що .
Побудуємо її поліном Жегалкіна:
.
Поліном Жегалкіна містить кон’юнкцію змінних, отже, функція нелінійна і система є функціонально повною в слабкому розумінні.
Завдання 10. Довести функціональну повноту системи .
Розв’язок.Операцію заперечення можна представити поліномом Жегалкіна у вигляді , отже, функція заперечення лінійна. Функція заперечення є самодвоїстою, не зберігає 0, не зберігає 1 (це визначається з використанням таблиці істинності), немонотонна. Імплікація є нелінійною функцією, тому що її поліном Жегалкіна має вигляд , вона несамодвоїста, не зберігає 0, зберігає 1 (можна визначити з таблиці істинності функції), немонотонна. Отже, для кожного класу Поста в даній системі є хоча б одна функція, що цьому класу Поста не належить. За теоремою Поста така система булевих функцій є функціонально повною.
8 ЛОГІКА ТА ОБЧИСЛЕННЯ ВИСЛОВЛЕНЬ
8.1 Мета заняття
Ознайомлення c основними поняттями логіки та обчислення висловлень. Вивчення на практичних прикладах способів побудови та інтерпретації висловлень, методів перевірки правильності міркувань.
8.2 Методичні вказівки з організації самостійної роботи студентів
Під час підготовки до практичного заняття необхідно повторити лекційний матеріал, розділи літератури [1-10] з таких питань: елементарні висловлення (атоми); логічні зв’язки і формули логіки висловлень; логіка висловлень та її закони, ізоморфність алгебри логіки і логіки висловлень; пріоритет операцій алгебри висловлень; інтерпретація формул логіки висловлень, правильні міркування; логічна еквівалентність і логічний наслідок; обчислення висловлень (мова, система аксіом і правила висновку); повнота і несуперечність обчислення висловлень; вивідність в обчисленні висловлень (дедуктивний висновок, правила підстановки і відділення); різні аксіоматизації обчислення висловлень; деякі прийоми доведення в обчисленні висловлень.
Підготовка і виконання практичного заняття проводиться в два етапи.
Перший етап пов’язаний з вивченням на практичних прикладах таких основних понять і визначень: висловлення; атом; висловлювальна змінна; істиннісне значення; множина істиннісних значень; логічні зв’язки; формула логіки висловлень (молекула); заперечення висловлення; кон’юнкція, диз’юнкція, імплікація висловлень; засновок (умова, антецедент); логічний наслідок (висновок, консеквент); правильно побудована формула; логіка висловлень; інтерпретація висловлення; тотожно істинна формула; тотожно хибна формула; незагальнозначуща (несуперечлива) формула; правильне міркування; логічна еквівалентність; обчислення висловлень; мова обчислення висловлень; аксіоми обчислення висловлень; висновок в обчисленні висловлень; теорема дедукції; правила висновку; дедуктивний висновок; правило відділення; правило підстановки; несуперечливе логічне обчислення; незалежна система аксіом.
Під час виконання першого етапу практичного заняття студент, повинен запропонувати і записати індивідуальний приклад для кожного з розглянутих вище понять і визначень логіки і обчислення висловлень.
Другий етап виконання практичного заняття пов’язаний з розв’язанням практичних завдань, які надаються у підрозділі 8.3, на основі запропонованих типових прикладів (див. підрозділ 8.4).
8.3 Контрольні запитання і завдання
8.3.1 Контрольні запитання
1. Який вид речень моделює формальна логіка?
2. Дайте визначення поняття «висловлення».
3. Дайте визначення поняття «алгебра логіки висловлень».
4. Які висловлення називаються атомами?
5. Що в логіці висловлень називають логічними зв’язками?
; б) 
; в) 
, г) 
.
; б) 
; в) 
.
; б) 
; в) 
.
; б) 
; в) 
.
, б) 
, в) 
, г) 
.
.
; 
. 
і функції 
.
. Тут усі пари порівнянні.
, для яких відношення часткового порядку встановлюється так: 
. Розглянуті набори є порівнянними, а набори 
і 
не є порівнянними.
.
запишемо всі набори значень змінних, для яких виконується відношення порядку, визначимо значення функції на даних наборах і порівняємо їх:
.
запишемо всі набори значень змінних, для яких виконується відношення порядку, визначимо значення функції на даних наборах і порівняємо їх:
.
.
.
.
не виконується умова 
.
.
на 
і розкриємо дужки у формулі, користуючись законом дистрибутивності 
. Дійсно виконуються такі рівності 
, 
, звідки
,
, то 
.
.
, де 
.
визначаються із рівності 
для довільного припустимого набору 
:
;
;
;
, тому 
; 
;
, тому 
;
, отже 
;
Отже, 
і 
.
.
.
, 
.
.
(штрих Шеффера) і 
(стрілка Пірса) функціонально повні. Довести повноту систем 
і 
.
,
; 
. Тому 
, що складається з однієї функції 
, яка задана таблицею істинності (табл. 7.1).
немонотонна, тому що 
.
.
.
, отже, функція заперечення лінійна. Функція заперечення є самодвоїстою, не зберігає 0, не зберігає 1 (це визначається з використанням таблиці істинності), немонотонна. Імплікація є нелінійною функцією, тому що її поліном Жегалкіна має вигляд 
, вона несамодвоїста, не зберігає 0, зберігає 1 (можна визначити з таблиці істинності функції), немонотонна. Отже, для кожного класу Поста в даній системі є хоча б одна функція, що цьому класу Поста не належить. За теоремою Поста така система булевих функцій є функціонально повною.