Партнерка на США и Канаду по недвижимости, выплаты в крипто
- 30% recurring commission
- Выплаты в USDT
- Вывод каждую неделю
- Комиссия до 5 лет за каждого referral
ВАРИАНТ 10
ИТ 13. Классы Поста
Для функций 
и 
выяснить вопрос о их принадлежности к классам 
.
В случае, когда какая-то функция является функционально полным классом, выразить из нее с помощью суперпозиций констант 0, 1, отрицание и конъюнкцию 
.
Полученные результаты проверить с помощью составления таблиц.
Решение
.
Выпишем таблицу функций 
и 
в развернутом виде:
|
|
|
1 | 000 | 0 |
1 | 001 | 0 |
0 | 010 | 0 |
1 | 011 | 1 |
1 | 100 | 1 |
1 | 101 | 0 |
0 | 110 | 1 |
0 | 111 | 0 |
1. Исследуем функцию . Проверим на принадлежность к классам Поста.
,
.
Наборы 
и 
являются противоположными и 
.
Поскольку 
, но 
.
Найдем полином Жегалкина для функции с помощью преобразования СДНФ функции:
Т. к. полином функции содержит конъюнкцию, то 
.
Получаем, функция не принадлежит ни одному из пяти классов Поста, поэтому 
является функционально полным классом.
Выразим из отрицание с помощью лишь одних суперпозиций. Рассмотрим функцию 
.
Найдем все значения функции 
:
.
Построено отрицание: 
.
Построим константу 1. Для этого возьмем набор из пары противоположных наборов, на которых функция равна 1, например, 
, , и рассмотрим функцию 
:
.
Найдем значение функции на ее наборах:
Построена константа 1: 
.
Для построения константы 0 возьмем отрицание функции и обозначим полученную функцию как 
.
.
.
Для построения конъюнкции зафиксируем переменную 
, присвоив ей значение 1. Получаем: 
, то есть получим выражение вида 
, где 
.
Рассмотрим функцию
Найдем значение функции 
на всех ее наборах.
;
;
;
.
Таблицу конъюнкции 
:
|
|
00 | 0 |
01 | 0 |
10 | 0 |
11 | 1 |
Как видим, эта таблица совпадает с таблицей функции , поэтому получена конъюнкция: 
.
2. Исследуем функцию . Проверим на принадлежность к классам Поста.
.
Отсюда следует, что 
не является функционально полным классом, т. к. целиком принадлежит классу функций, сохраняющих константу 0.
.
Наборы 
и 
являются противоположными и 
.
Отсюда следует, что не является функционально полным классом, т. к. целиком принадлежит классу самодвойственных функций.
Поскольку 
, но 
.
|
|
|
1 | 000 | 0 |
1 | 001 | 0 |
0 | 010 | 0 |
1 | 011 | 1 |
1 | 100 | 1 |
1 | 101 | 0 |
0 | 110 | 1 |
0 | 111 | 0 |
Найдем полином Жегалкина для функции с помощью преобразования СДНФ функции:
Т. к. полином функции содержит конъюнкций, то 
.
ИТ 15. Анализ конечного автомата
По заданной диаграмме Мура построить систему канонических уравнений.
Решение
Построим таблицу переходов-выходов:
а | b | |
1 | 4,1 | 1,0 |
2 | 1,0 | 4,1 |
3 | 3,0 | 2,1 |
4 | 2,0 | 3,0 |
Кодирование состояний:
Новая таблица переходов-выходов:
а | b | |
00 | 11,1 | 01,0 |
01 | 01,0 | 11,1 |
10 | 10,0 | 01,1 |
11 | 01,0 | 10,0 |
Каноническая таблица:
|
|
|
|
|
|
0 | 0 | 0 | 1 | 1 | 1 |
0 | 0 | 1 | 0 | 1 | 0 |
0 | 1 | 0 | 0 | 1 | 0 |
0 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 | 1 | 0 |
1 | 1 | 1 | 1 | 0 | 0 |
Составим канонический уравнения.
Из канонической таблицы видно, что 4-й столбец соответствует операции эквивалентности второго и третьего столбца:
.
Для четвертого столбца выпишем СКНФ (обозначим первые 3 столбца буквами 
), и преобразуем используя основные законы и определения логических операций:
Тогда 
.
Для шестого столбца напишем СДНФ и преобразуем используя основные законы и определения логических операций:
Получаем: 
.
Система канонических уравнений
ИТ 16. Синтез конечного автомата
По заданной системе канонических уравнений конечного автомата построить диаграмму Мура.
Решение
Построим каноническую таблицу:
|
|
|
|
|
|
0 | 0 | 0 | 1 | 1 | 1 |
0 | 0 | 1 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 1 | 0 |
1 | 0 | 1 | 1 | 1 | 1 |
1 | 1 | 0 | 1 | 1 | 1 |
1 | 1 | 1 | 1 | 1 | 0 |
Таблица переходов:
0 | 1 | |
00 | 11,1 | 01,1 |
01 | 10,1 | 00,1 |
10 | 11,0 | 11,1 |
11 | 11,1 | 11,0 |
Кодирование состояний:
Новая таблица переходов:
0 | 1 | |
0 | 3,1 | 1,1 |
1 | 2,1 | 0,1 |
2 | 3,0 | 3,1 |
3 | 3,1 | 3,0 |
Диаграмма Мура:
Начальное состояние – 0.
Основные порталы (построено редакторами)