Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Хід заняття



Задача 1.Визначити функції , , так, щоб , , . Якщо побудова якої-небудь функції неможлива, доведіть це. З’ясуйте питання належності побудованих функцій до класів , .

, , .

Розв’язування. Покажемо розвернуту таблицю даних функцій: визначимо функцію f, використовуючи визначення монотонної функції. Т. я. , то на всіх наборах, яким передує набір функція f також повинна дорівнювати 0, тобто . Т. я. , то на всіх наборах, яким передує набір функція f повинна приймати значення 1, тобто f . Отримаємо, .

Визначимо функцію g, враховуючи те, що вона лінійна. Загальний вигляд лінійної функції від змінних x, y, z має вигляд: .

Будемо підставляти набори значень аргументів, на яких функція визначена.

xyz f g h
- -
- -
-
- - -
- -
- -

Отримаємо систему відношень:

,

Замінюючи на 1 в 4 рівності системи, маємо: .

Склавши перші 3 рівності і враховуючи, що , отримаємо . Тобто, . Виходячи з цієї формули, знайдемо значення функції g на тих наборах, на яких вона була невизначена:


,

,

,

.


Тобто маємо: .

Визначимо функцію h, використовуючи визначення само двоїстої функції. Т. я. Набори і протилежні і . Протилежними парами наборів значень змінних є також і , і , і . Використовуючи відомі значення функції h, отримаємо: .

Тобто, .

Т. я. , то , , .

Т. я. , , то , , .

 

Задача 2.Для функцій

і

з’ясувати питання про їх належність класам , , L, M, S. Якщо деяка функція є функціонально повний клас, то виразити з неї за допомогою суперпозицій константи 0 ,1, заперечення і кон’юнкцію . Якщо деяка функція є функціонально повною в слабкому сенсі, то виразити з неї за допомогою суперпозицій і фіксованих змінних заперечення і кон’юнкцію . Отримані результати перевірити за допомогою побудови таблиці.

Розв’язування. З’ясуємо питання про належність до класів Поста.

.

Т. я. Набори і протилежні, але .

Маємо, що , але .

Т. я. , за теоремою Поста, не є фіксовано повним класом, але т. я. , то - функціонально повний в слабкому сенсі клас. Виразимо з функції f заперечення за допомогою фіксованих змінних. Візьмемо сусідні набори змінних і , на яких порушується монотонність і розглянемо функцію .Знайдемо всі значення функції :

,

заперечення побудовано, .

Для побудови кон’юнкції зафіксуємо дві змінні та, при необхідності, пере позначимо останні змінні так, щоб вираз прийняв вигляд: .

Наприклад, зафіксувати змінні можна так: .

В цьому випадку введемо функцію .

Знайдемо значення функції h на всіх наборах:

.

Як бачимо, , кон’юнкція побудована, .

Перевіримо g на належність до класів Поста.

.

Т. я. поліном g має кон’юнкцію, то . Т. я. і . Зауважимо, що

.

Т. я. набори і протилежні, а . Функція g не належить ні до одного з класів Поста, тобто, за теоремою Поста, - функціонально повний клас. Побудуємо заперечення. Розглянемо функцію , знайдемо всі значення функції s:

,

тобто, .

Побудуємо константу 0. для цього візьмемо набір з пари протилежних наборів, на яких функція рівна 0, наприклад і розглянемо функцію . Знайдемо значення функції :

Отже, .

Знайдемо пару протилежних наборів, на яких функція дорівнює 1: .

Розглянемо .Знайдемо значення функції m(x):

Отже, .

Для побудови кон’юнкції зафіксуємо 2 змінні так, щоб поліном g прийняв вигляд .

Наприклад, зафіксувати змінні можна так: , тобто в цьому випадку .

Візьмемо функцію

. Знайдемо значення функції на всіх наборах:

,

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

Розв’язування. Позначимо через , і відповідно безлічі лінійних, що зберігають нуль і самодвоїстності функції від n перемінних. Зобразимо безлічі , і схематично: Заштрихована область відповідає функціям шуканого класу. Очевидно, виконана рівність: .

.Кожна функція з має вигляд: . Поставимо у відповідність кожної такої функції вектор її двоїчних коефіцієнтів . Очевидно, що ця відповідність - биєкція, виходить, кількість різних лінійні функції від n перемінних, дорівнює кількості різних двоїчних наборів розмірності , тобто , отже, . Якщо лінійна функція зберігає константу 0, то , і вона має вигляд . Для самодвоїстої функції виконується властивість

.

З огляду на, що , подивимося, як 6буде виглядати ця рівність у випадку лінійної, що зберігає нуль функції:

а1

Розкриємо дужки: Додамо за модулем 2 до обох частин отриманої рівності вираження , врахуємо, що . Тоді після спрощень будемо мати:

(*)

Зкоефіцієнтів довільним образом можна призначати n-1 коефіцієнт, а значення n-го коефіцієнта однозначно визначається з рівності (*). Отже, між безліч булевих функцій класу і безліччю двоїчних векторів розмірності n-1 існує бієкція, виходить, вірна рівність

Тобто одержуємо:

.

 

Задача 4.Підрахувати число різних булевих функцій від п перемінній, приналежній безлічі .

Розв’язування. Позначимо через і відповідно безлічі самодвоїстих і функцій, що зберігають одиницю, від n перемінних. Зобразимо безлічі і схематично:

Очевидно, .

Нехай , , , зобразимо таблиці цих функцій:

f g h
0 0 ... 0 0 0
0 0 ... 0 1
… … ... …
0 1 ... 1 1
1 0 ... 0 0
… … ... … ...
1 1 ... 1 0
1 1 ... 1 1 1 1

 

Як бачимо, f взаємно однозначно визначається вектором двоїчних коефіцієнтів розмірності , g-розмірності , a h-розмірності .

Виходить, потужності безлічей , і рівні відповідно .

Тобто, .