Булеві функції. суперпозиції

МЕТОДИЧНІ МАТЕРІАЛИ ДЛЯ ЗАБЕЗПЕЧЕННЯ

САМОСТІЙНОЇ РОБОТИ СТУДЕНТІВ

ОПЕРАЦІЇ НАД МНОЖИНАМИ

1.(1.1.2) Для універсальної множини , множини , заданої списком, та для множини :

1.знайдіть множини: ;

2.з’ясуйте, яка з п’яти можливостей виконується для множин та : , , , Ø або та просто перетинаються;

3.знайдіть та .

2.(1.1.3) Нехай – множини точок площини, координати яких задовольняють умовам відповідно. Зобразіть в системі координат множину , отриману з множин за формулою .

3.(1.1.4) 1) Чи існують множини такі, що виконується набір умов ? Чи існують множини такі, що виконується набір умов ? 2) Чи існують множини такі, що виконується набір умов ?

4.(1.1.5) З’ясуйте взаємне розміщення множин , якщо – довільні підмножини універсальної множини .

5.(1.1.6) Перевірте, що для довільних множин з виконання включення випливає включення .

6.(1.1.7) Перевірте, що для довільних множин виконання включення є необхідним і достатнім для виконання рівності .

7.(1.1.8) Розв’яжіть систему співвідношень відносно множини та укажіть умови сумісності системи.

8.(1.1.9) Розв’яжіть систему рівнянь відносно множини та укажіть умови сумісності системи або доведіть її несумісність.

ГРАФІКИ

9.(1.2.1) Перевірте справедливість рівності для множин . З’ясуйте, чи вірна рівність для довільних .

10.(1.2.2) Для даного графіка знайдіть: .

11.(1.2.3) Для даних графіків та розв’яжіть відносно графіка рівняння за умови, що . Для кожного знайденого укажіть .

ВІДПОВІДНОСТІ

12.(1.3.1) Дано відповідність .

1.Зобразіть відповідність у вигляді графа.

2.З’ясуйте, які властивості (всюди визначеність, сюр’єктивність, функціональність, ін’єктивність) їй притаманні.

3.Знайдіть образ множини та прообраз множини при даній відповідності.

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

5.Побудуйте відповідність між скінченими множинами, якій притаманні властивості, протилежні даній відповідності .

ВІДНОШЕННЯ

13.(1.4.2) Дано відношення .

1.З’ясуйте, які властивості притаманні даному відношенню: рефлексивність, антирефлексивність, симетричність, антисиметричність, транзитивність, зв’язність.

2.Опишіть, що представляє з себе відношення .

3.Побудуйте на скінченій множині відношення, якому притаманний набір властивостей, що і . Зобразіть його графом та аналітично.

4.Побудуйте на нескінченій множині відношення, якому притаманний набір властивостей, протилежних даному. У випадку неможливості побудови доведіть суперечливість набору вимог.

14.(1.4.4) Дано відношення .

1.Зобразіть графом.

2.Добудуйте до відношення еквівалентності, укажіть фактор-множину.

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

4.Добудуйте до відношення лінійного порядку, укажіть найбільший та найменший елементи.

5.Добудуйте до відношення строгого порядку.

6.Добудуйте до відношення строгого лінійного порядку.

Зауваження. Відношення добудовується за допомогою введення мінімально необхідної кількості додаткових ребер.

БУЛЕВІ ФУНКЦІЇ. СУПЕРПОЗИЦІЇ

15.(2.1.1) Дано булеву функцію .

1.Побудуйте її таблицю істинності.

2.Спростіть, використовуючи основні формули.

3.Знайдіть функцію , двоїсту до функції :

а) за допомогою таблиці істинності;

б) за означенням .

16.(2.1.2) Напишіть таблицю функції , що є суперпозицією функцій і , якщо , , , , , , , , , .

17.(2.1.3) Дано булеву функцію .

1.З’ясуйте, які її змінні є істотними, а які фіктивними.

2.Запишіть у вигляді формули, що містить лише істотні змінні.

18.(2.1.4) Булеву функцію задано формулою.

1.Напишіть її таблицю істинності.

2.Знайдіть фіктивні змінні даної функції.

3.Перетворіть дану формулу в еквівалентну їй, але таку, що не містить фіктивних змінних.