Розділ “Алгебричні структури”
I. Виконайте завдання.
1) Задано множину 
цілих чисел, які при діленні на 3 дають остачу 2, і операцію звичайного віднімання (–). Дослідіть, чи утворюють множина 
і операція (–) алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
2) Нехай 
— множина всіх квадратних невироджених матриць порядку n, елементами яких є дійсні числа, 
— операція множення матриць. Дослідіть, чи утворюють множина і операція алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
3) Задано множину комплексних чисел 
і операцію звичайного множення (
). Дослідіть, чи утворюють множина А і операція () алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
4) Задано множину раціональних чисел без нуля 
і операцію звичайного множення (). Дослідіть, чи утворюють множина А і операція () алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
5) Дослідіть, чи утворюють множина ірраціональних чисел 
і операція звичайного додавання (
) алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
6) Задано множину Z цілих чисел і операцію , яка визначається так: 
. Дослідіть, чи утворюють множина Z і операція алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
7) Задано множину N натуральних чисел і операцію , яка визначається так: 
. Дослідіть, чи утворюють множина N і операція алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
8) Задано множину додатних раціональних чисел 
, де 
— нескоротний дріб, і операцію звичайного множення (). Дослідіть, чи утворюють множина 
і операція () алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
9) Нехай 
— множина n -вимірних векторів з дійсними координатами, (+) — операція покоординатного додавання векторів. Дослідіть, чи утворюють множина 
і операція (+) алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
10) Нехай 
— множина раціональних чисел з проміжку 
, у яких дробова частина містить n цифр (наприклад, при 
такими числами є: 
, 
), (+) — операція звичайного додавання. Дослідіть, за якої умови алгебрична структура 
є абелевою (комутативною) групою.
11) Нехай 
— множина всіх парних цілих чисел, () — операція звичайного множення. Дослідіть, чи утворюють множина і операція () алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
12) Задано множину комплексних чисел 
і операцію звичайного додавання (+). Дослідіть, чи утворюють множина А і операція (+) алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
13) Дослідіть, чи утворюють множина натуральних чисел N і операція звичайного додавання (+) алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
14) Задано множину 
визначників квадратних матриць порядку n і операцію множення матриць (). Дослідіть, чи утворюють множина і операція () алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
15) Дослідіть, чи утворюють множина цілих чисел Z і операція звичайного віднімання (–) алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
16) Дослідіть, чи утворюють множина раціональних чисел Q і операція звичайного ділення (
) алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
17) Задано множину натуральних чисел N і для будь-яких елементів 
визначено бінарну операцію 
як модуль різниці цих елементів 
. Дослідіть, чи утворюють множина N і операція алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
18) Дослідіть, чи утворюють множина натуральних чисел N і операція звичайного множення () алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
19) Задано множину натуральних чисел N і для будь-яких елементів визначено бінарну операцію як менший із цих елементів 
. Дослідіть, чи утворюють множина N і операція алгебру. Якщо так, то класифікуйте алгебричну структуру , дослідивши її основні властивості й існування одиничного та оберненого елементів.
20) Задано множину комплексних чисел 
(де Q — множина раціональних чисел) і операцію ділення (). Класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
21) Дослідіть, чи утворюють множина ірраціональних чисел і операція звичайного множення () алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
22) Задано множину ненульових комплексних чисел 
і операцію множення (). Дослідіть, чи утворюють множина А і операція () алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
23) Задано множину 
визначників невироджених квадратних матриць порядку n і операцію множення матриць (). Дослідіть, чи утворюють множина і операція () алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
24) Задано множину Z цілих чисел і операцію , яка визначається так: 
. Дослідіть, чи утворюють множина Z і операція алгебру. Якщо так, то класифікуйте алгебричну структуру , дослідивши її основні властивості й існування одиничного та оберненого елементів.
25) Задано множину 
натуральних чисел, які при діленні на 3 дають остачу 1, і операцію звичайного множення (
). Дослідіть, чи утворюють множина 
і операція () алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
26) Задано множину 
і операцію додавання за модулем 4 (
; при цьому операція додавання за модулем m 
визначається так: 
, де 
, 
, 
, 
). Дослідіть, чи утворюють множина 
і операція () алгебру. Якщо так, то класифікуйте алгебричну структуру 
, дослідивши її основні властивості й існування одиничного та оберненого елементів.
Розділ “Алгебра логіки”
II. Використовуючи таблицю істинності, доведіть чи спростуйте тотожність.
1) 
; 2) 
;
3) 
; 4) 
;
5) 
; 6) 
;
7) 
; 8) 
;
9) 
; 10) 
;
11) ; 12) 
;
13) 
; 14) 
;
15) 
; 16) 
;
17) 
; 18) 
;
19) 
; 20) ;
21) 
; 22) 
;
23) 
; 24) 
;
25) 
; 26) 
.
III. Запишіть формулу функції, двоїстої до заданої функції 
, використовуючи а) означення двоїстої функції; б) принцип двоїстості.
1) 
; 2) 
;
3) 
; 4) 
;
5) 
; 6) 
;
7) 
; 8) 
;
9) ; 10) 
;
11) 
; 12) ;
13) 
; 14) 
;
15) 
; 16) 
;
17) 
; 18) ;
19) 
; 20) ;
21) ; 22) 
;
23) 
; 24) 
;
25) 
; 26) .
IV. Для заданої функції 
запишіть: а) ДДНФ; б) ДКНФ; в) поліном Жегалкіна; в) дослідіть, чи є функція самодвоїстою.
1) 
; 2) 
;
3) 
; 4) 
;
5) 
; 6) 
;
7) 
; 8) 
;
9) 
; 10) 
;
11) 
; 12) 
;
13) 
; 14) 
;
15) 
; 16) 
;
17) 
; 18) 
;
19) 
; 20) 
;
21) 
; 22) 
;
23) 
; 24) 
;
25) 
; 26) 
.
V. Обґрунтовуючи належність кожної функції поданої системи до певного класу Поста і використовуючи критерій Поста, дослідіть, чи є повною система функцій.
1) 
; 2) 
;
3) 
; 4) 
;
5) 
; 6) 
;
7) 
; 8) 
;
9) 
; 10) 
;
11) 
; 12) 
;
13) 
; 14) 
;
15) 
; 16) 
;
17) 
; 18) 
;
19) 
; 20) 
;
21) 
; 22) 
;
23) 
; 24) 
;
25) 
; 26) 
.
VI. Для заданої функції знайдіть скорочену ДНФ: а) методом Квайна; б) за допомогою діаграм Хассе.
1) 
; 2) 
;
3) 
; 4) 
;
5) 
; 6) 
;
7) 
; 8) 
;
9) 
; 10) 
;
11) 
; 12) 
;
13) 
; 14) ;
15) 
; 16) 
;
17) 
; 18) 
;
19) 
; 20) 
;
21) 
; 22) 
;
23) 
; 24) 
;
25) 
; 26) 
;
VII. Для функції 
знайдіть мінімальну ДНФ за допомогою карт Карно.
1) 
;
2) 
;
3) 
;
4) 
;
5) 
;
6) 
;
7) 
;
8) 
;
9) 
;
10) 
;
11) 
;
12) 
;
13) 
;
14) 
;
15) 
;
16) 
;
17) 
;
18) 
;
19) 
;
20) 
;
21) 
;
22) 
;
23) 
;
24) 
;
25) 
;
26) 
.
Розділ “Математична логіка”
VIII. У відповідність складному висловлюванню поставте формулу, виділивши перед цим прості висловлювання і заміняючи зв’язки логічними операціями. Перевірте, чи є одержана формула тавтологією.
1) “Якщо число ділиться на 6, то воно ділиться на 2 і на 3”;
2) “Буде чи не буде дощ, я піду на заняття або в бібліотеку”;
3) “Я роздрукую завдання тоді і тільки тоді, коли матиму папір і заправлю картридж”;
4) “Зображення буде чітким, якщо при скануванні задати велику роздільну здатність, а при збереженні використати алгоритм стискання без втрати якості”;
5) “Я добре засвою матеріал, якщо розберу теорію і виконаю практичні завдання”;
6) “Якщо дощ буде лити як з відра, то я не піду ні на заняття, ні в бібліотеку”;
7) “Сьогодні ми склали іспит, тому завтра будемо відпочивати і милуватися природою”;
8) “Якщо я проснуся і буде лити дощ, то я на заняття не піду”;
9) “Ноутбук буде працювати, якщо буде напруга в мережі або буде заряджений акумулятор”;
10) “Якщо буде бажання, то влітку ми поїдемо в гори або на море”;
11) “Я підготуюся до складного іспиту, якщо буде хороший конспект і багато книжок”;
12) “Я піду на прогулянку тоді і тільки тоді, коли закінчаться заняття і буде хороша погода”;
13) “Якщо в картриджі буде тонер, то я роздрукую реферат і розв’язки задач”;
14) “Коли настане літо і закінчиться сесія, студенти будуть мати великі канікули”;
15) “Ми зможемо скласти залік тоді і тільки тоді, коли виконаємо всі лабораторні роботи і успішно їх захистимо;
16) “Вночі студент писав програму і робив завдання з дискретної математики і тому вранці пізно прокинувся”;
17) “Якщо я буду мати час, то напишу програму, але не буду виконувати завдання з дискретної математики”;
18) “Я напишу хорошу програму тоді і тільки тоді, коли буде натхнення або матиму багато часу”;
19) “Якщо в комп’ютері малий обсяг оперативної пам’яті або слабка відеокарта, то комп’ютер буде працювати повільно”;
20) “Розклад занять буде оптимальний тоді і тільки тоді, коли в ньому не буде “вікон” і щодня буде однакова кількість пар”;
21) “Якщо процесор перегріється, то комп’ютер буде працювати некоректно або навіть зависне”;
22) “Подання інформації буде структурованим, якщо використати списки або таблиці”;
23) “Якщо число закінчується на 0, то воно ділиться на 2 і на 5”;
24) “Програмний код зрозумілий тоді і тільки тоді, коли він поданий структуровано і в ньому є коментарі”;
25) “Якщо в чотирикутнику всі кути рівні, то він є прямокутником або квадратом”;
26) “Студент правильно виконає домашнє завдання тоді і тільки тоді, коли він розбере теорію і зрозуміє подані на занятті приклади”.
IX. Визначте, за допомогою якого правила виведення системи природного виведення можна довести подану нижче теорему. Якщо при цьому є засновок, який не використовується для одержання висновку, то вкажіть його.
1) “Із А, В, 
одержати 
”; (
)
2) “Із 
, 
одержати 
”; (
)
3) “Із 
, 
одержати 
”; (
)
4) “Із 
, одержати 
”; (
)
5) “Із 
, 
, 
одержати 
”; (
)
6) “Із 
, 
, одержати ”; (
)
7) “Із 
, 
, 
одержати 
”; (
)
8) “Із , одержати 
”; (
)
9) “Із 
, А одержати 
”; ()
10) “Із , 
, одержати 
”; ()
11) “Із , , одержати 
”; ()
12) “Із , 
, С одержати 
”; ()
13) “Із , , одержати ”; ()
14) “Із , 
, 
одержати ”; ()
15) “Із 
, , одержати 
”; ()
16) “Із , одержати 
”; ()
17) “Із , 
, одержати 
”; ()
18) “Із 
, , 
, 
одержати 
”; ()
19) “Із 
, одержати 
”; ()
20) “Із , , 
одержати 
”; ()
21) “Із 
, , одержати ”; ()
22) “Із 
, 
, 
, 
одержати 
”; ()
23) “Із , одержати ”; ()
24) “Із 
, одержати 
”; ()
25) “Із 
, одержати ”; ()
26) “Із , , 
одержати ”. ()
X. Виконайте завдання.
1) Нехай 
. Визначте множини істинності для кон’юнкцій поданих нижче предикатних формул: а) “ 
” і “ 
”; б) “ 
” і “ 
”.
2) Використовуючи символи кванторів, запишіть у вигляді формул подані нижче предикати: а) “Існує таке число 
, що 
”; б) “Для всіх , таких, що 
, виконується нерівність 
”.
3) Дано предикати: 
“ n — ціле число”, 
“ n — просте число”, 
“ n — число, кратне 5”. Встановіть значення істинності наведених нижче формулі подайте їх звичайною мовою: а) 
; б) 
; в) 
.
4) Предикат 
задано на множині 
матрицею виду:
Яка з наведених нижче формул і чому визначає цей предикат: а) 
; б) 
; в) 
?
5) Запишіть подану нижче формулу у вигляді нормальної форми ВНФ: 
.
6) Нехай . Побудуйте множини істинності для кожного з поданих нижче предикатів: а) 
; б) 
; в) 
; г) 
.
7) Нехай , а також задано предикати 
“ х — просте число” і 
“ х — раціональне число” Використовуючи квантори, запишіть у вигляді формул подані нижче твердження: а) “Будь-яке просте число є раціональним числом”; б) “Існує раціональне число, яке є простим числом”.
8) У поданих нижче формулах визначте, які змінні і чому є зв’язаними, а які — вільними: а) 
; б) 
.
9) Нехай є комірки з номерами 1, 2, 3, 4. Використовуючи квантори, подайте у вигляді формули твердження: “Збільшити номер кожної комірки на 2”.
10) На множині парних натуральних чисел 
задано два предикати “число n кратне 5”, 
“ 
”. Побудуйте множини істинності для поданих нижче предикатів: а) 
; б) 
; в) 
; г) 
.
11) Запишіть подану нижче формулу у вигляді нормальної форми ВНФ: 
.
12) Нехай 
. Побудуйте множини істинності для кожного з поданих нижче предикатів: а) 
; б) 
2; в) 
.
13) Нехай 
, а також задано предикат 
“ y є функцією від х ”. Встановіть значення істинності наведених нижче формул і подайте їх звичайною мовою: а) 
; б) 
; в) 
.
14) За столом сидить шестеро осіб. Використовуючи квантори, подайте увигляді формули твердження: “Серед шести присутніх є один програміст”.
15) Предикат задано на множині 
матрицею виду:
Яка з наведених нижче формул і чому визначає цей предикат: а) 
; б) 
; в) 
?
16) Дано предикати: “ n — просте число”, “ n — число, кратне 3”. Встановіть значення істинності наведених нижче формулі подайте їх звичайною мовою: а) 
; б) 
; в) 
.
17) Вкажіть вільні й зв’язані змінні в поданих нижче формулах: а) 
; б) 
.
18) Запишіть подану нижче формулу у вигляді нормальної форми ВНФ: 
.
19) Нехай . Визначте множини істинності для диз’юнкцій поданих нижче предикатів: а) “ 
” і “ 
”; б) “ 
” і “ 
”.
20) На множині парних натуральних чисел 
задано два предикати “число n кратне 3”, “ 
”. Побудуйте множини істинності для поданих нижче предикатів: а) 
; б) 
; в) 
; г) 
.
21) Визначте, чи еквівалентні подані нижче предикати: а) “ 
” і “ 
”; б) “ 
” і “ 
”.
22) Використовуючи квантори, запишіть у вигляді формули твердження: “Для того, щоб у точці 
функція 
мала екстремум, необхідно, щоб похідна функції в цій точці дорівнювала нулю”, якщо: а) 
, 
; б) 
, .
23) Дано предикати: 
“ n — натуральне число”, “ n — ціле число”, “ n — просте число”. Встановіть значення істинності наведених нижче формулі подайте їх звичайною мовою: а) 
; б) 
; в) 
.
24) Дано предикати: 
“ х — ціле число”, “ х — просте число”. 
“ х — раціональне число”. Використовуючи квантори, запишіть формули для поданих нижче тверджень: а) “Будь-яке раціональне число є дробом виду 
, де х — ціле число, у — натуральне число”; б) “Існують раціональні числа виду , де х і у — прості числа”.
25) Нехай 
, 
, 
, де І — істина, Х — хибність. При 
знайдіть значення формул: а) 
; б) 
.
26) На множині однозначних і двозначних парних натуральних чисел задано два предикати: “Число х кратне 3”, “ 
”. Побудуйте множини істинності для поданих нижче предикатів: а) 
; б) 
; в) 
; г) 
.
