Контрольна робота
Дисципліна: Дискретна математика
1. Многочлен Жегалкина. Знаходження многочлена Жегалкина по СДНФ (з обґрунтуванням)
поліном жегалкіна - сума по модулю 2, в якій кожний доданок являє собою
· Константу
· окрему змінну
· твір декількох змінних.
Алгоритм побудови полінома Жегалкина по СДНФ (заснований на доведенні теореми про існування полінома Жегалкина).
Початок. Задана досконала ДНФ функції f (x 1, ..., xn).
Крок 1. Замінюємо кожен символ диз'юнкції на символ суми по модулю 2.
Крок 2. Замінюємо кожну змінну з інверсією x рівносильній формулою x 1.
Крок 3. Розкриваємо дужки.
Крок 4. Викреслюємо з формули пари однакових доданків.
Кінець. Отримано поліном Жегалкина функції f (x 1, ..., xn).
Сума по модулю два може бути виражена через диз'юнкцію, кон'юнкцію і заперечення: A? B=A? B, звідки A? 1=
многочлен Жегалкина логічний безліч
2. Задані універсальна безліч U і три його підмножини A, B, C.
Перевірити (довести або спростувати) справедливість співвідношення:
Рішення:
Побудуємо діаграму Ейлера-Венна, зобразивши універсальна безліч прямокутником, а підмножини колами. Відзначимо на діаграмі штрихуванням додаток до перетинанню A, B, C.
Тепер зобразимо на діаграмі штрихуванням доповнення до кожного з підмножин:
Побудуємо їх об'єднання і отримаємо:
Остання діаграм збігається з діаграмою безлічі, тому, що потрібно було довести.
. Задано бінарне відношення
,
де.
Визначити, чи виконуються для даного відношення властивості симетричності і рефлексивності. Відповідь обгрунтувати.
100101010101910101010108010101010171010101010601010101015101010101040101010101310101010102010101010111010101010012345678910
Рефлексивність. Це відношення рефлексивно, тому для А виконується x + x парне.
Симетричність. Це відношення симетричне на безлічі А, т.к (x + y) -четно= gt; (y + x) -четно.
. Спростивши логічну функцію двох змінних, перевірити її самодвоїстих, монотонність і лінійність. Відповідь обгрунтувати.
Рішення:
Функція лінійна, тому подана в вигляді лінійного полінома Жегалкина:
Функція не є монотонною, тому є набори (10) lt; (11), при яких f (10) gt; f (11)
Функція самодвоїстих, тому на всіх наборах виконується умова
. На вершину гори ведуть дев`ять доріг. Скількома різними способами можна піднятися на гору і спуститися?
Рішення:
За умовою задачі, нас цікавить вибірка з 9 елементів 2 елементів, при якій вибирані елементи повертаються у вихідне безліч (можна повертатися тими ж дорогами), а порядок вибору елементів не важливий:
