Профессии детского сада

Какие профессии бывают? Разберемся вместе! Кем бы хотели сстать дети когда выростут, какие у них ожидания.

Вы уже знаете о суперспособностях современного учителя?

Тратить минимум сил на подготовку и проведение уроков.

Быстро и объективно проверять знания учащихся.

Сделать изучение нового материала максимально понятным.

Избавить себя от подбора заданий и их проверки после уроков.

Наладить дисциплину на своих уроках.

Получить возможность работать творчески.

=> ПОЛУЧИТЬ СУПЕРСПОСОБНОСТИ УЧИТЕЛЯ <=

Просмотр содержимого документа
«Профессии детского сада»

4 вар, БСТ2352, Васильева А. А., ЗБСТ23426

Задача 1.

Постановка задачи:

Построить СДНФ функции, заданной таблицей истинности f = 1 на 1, 3, 4, 5, 6, 7, 9, 10, 11, 14, 15.

Ход решения:

Построим таблицу истинности для функции и выделим наборы, при которых f = 1.

	x1	x2	x3	x4	F
1	0	0	0	0	1
2	0	0	0	1	0
3	0	0	1	0	1
4	0	0	1	1	1
5	0	1	0	0	1
6	0	1	0	1	1
7	0	1	1	0	1
8	0	1	1	1	0
9	1	0	0	0	1
10	1	0	0	1	1
11	1	0	1	0	1
12	1	0	1	1	0
13	1	1	0	0	0
14	1	1	0	1	1
15	1	1	1	0	1
16	1	1	1	1	0

Построим конъюнкции для этих наборов, где переменные, равные 0, записываются с отрицанием, а переменные, равные 1, без отрицания:

Для набора (1) : ∧ ∧ ∧

Для набора (3) : ∧ ∧ ∧

Для набора (4) : ∧ ∧ ∧

Для набора (5) : ∧ ∧ ∧

Для набора (6) : ∧ ∧ ∧

Для набора (7) : ∧ ∧ ∧

Для набора (9) : ∧ ∧ ∧

Для набора (10) : ∧ ∧ ∧

Для набора (11) : ∧ ∧ ∧

Для набора (14) : ∧ ∧ ∧

Для набора (15) : ∧ ∧ ∧

Запишем дизъюнкцию всех этих конъюнкций, получив СДНФ.

СДНФ = ∧ ∧ ∧ + ∧ ∧ ∧ + ∧ ∧ ∧ + ∧ ∧ ∧ + ∧ ∧ ∧ + ∧ ∧ ∧ + ∧ ∧ ∧ + ∧ ∧ ∧ + ∧ ∧ ∧ + ∧ ∧ ∧ + ∧ ∧ ∧

Вывод:

Построена совершенная дизъюнктивная нормальная форма (СДНФ) для функции f, заданной таблицей истинности

Задача 2.

Постановка задачи:

По полученной СДНФ для функции f с помощью метода Квайна построить сокращенную ДНФ.

Ход решения:

Запись СДНФ:

СДНФ = + + + + + + + + + +

Метод Квайна:

Метод Квайна основан на применении двух основных операций:

- Операция попарного неполного склеивания:

- Операция элементарного поглощения:

Где A – некоторая элементарная конъюнкция, в которой каждая из переменных входит не более одного раза

Метод состоит в последовательном выполнении всех возможных склеиваний и затем всех поглощений частей СДНФ, пока это может быть осуществимо.

Выпишем все минитермы 4 ранга и выполним операции попарного склеивания и поглощения.

Минитерм – это элементарные конъюнкции СДНФ.

№	Минитермы 4 ранга	Минитермы 3 ранга	Минитермы 2 ранга
1		(1 – 2)	(1 – 8)
2		(1 – 4)	(2 – 5)
3		(1 – 7)	(1 – 12)
4		(2 – 3)	(3 – 6)
5		(2 – 6)	(5 – 14)
6		(2 – 9)	(6 – 10)
7		(4 – 5)
8		(4 – 6)
9		(5 – 10)
10		(6 – 11)
11		(7 – 8)
12		(7 – 9)
13		(8 – 10)
14		(9 – 11)

В приведенной таблице пометим все минитермы 3 ранга, которые были использованы для получения минитермов 2 ранга. Минитермы 1 ранга отсутствуют.

Запишем минитермы 2 ранга и те минитермы 3 ранга, которые не участвовали в склейке, получим сокращенную ДНФ на данном этапе.

Сокращенная ДНФ = + + + + + +
+

Составим таблицу покрытия:

Единицы ДНФ, покрываемые элементами или обозначаются "+". Пары и , попадающие в ядро помечаются "цветом".
Единицы функции, которые покрываются только каким-то одним конъюнктом из системы элементов сокращённой ДНФ, помечаются “цветом”.
Единицы функции, покрываемые ядром, но не покрываемые только каким-то одним конъюнктом из системы элементов сокращённой ДНФ помечаются “цветом”.


+	+		+		+
+	+					+		+
	+				+			+		+
+	+	+
			+	+
				+					+
						+	+
							+		+

Из конъюнктов, которые не вошли в ядро функций, выбираем те, которые максимально покрывают оставшиеся единицы функции. Таким образом получаем сокращенную ДНФ без лишних конъюнкций.

Сокращенная ДНФ = + + + +

Вывод:

С помощью метода Квайна была сокращена СДНФ функции f, то есть получена сокращенная ДНФ функции.

Задача 3.

Постановка задачи:

Для функции f, используя карту Карно, получить сокращенную ДНФ. Сравнить результатами, полученными в задаче 2.

Ход решения:

Построение карты Карно, на основе заданной функции f.

/	00	01	11	10
00	1	0	1	1
01	1	1	0	1
11	0	1	0	1
10	1	1	0	1

Выделяем в полученной таблице группы единиц таким образом, чтобы количество ячеек в группе являлось степенью числа 2.

Группа 1:

/	00	01	11	10
00	1	0	1	1
01	1	1	0	1
11	0	1	0	1
10	1	1	0	1

Группа 2:

/	00	01	11	10
00	1	0	1	1
01	1	1	0	1
11	0	1	0	1
10	1	1	0	1

Группа 3:

/	00	01	11	10
00	1	0	1	1
01	1	1	0	1
11	0	1	0	1
10	1	1	0	1

Группа 4:

/	00	01	11	10
00	1	0	1	1
01	1	1	0	1
11	0	1	0	1
10	1	1	0	1

Группа 5:

/	00	01	11	10
00	1	0	1	1
01	1	1	0	1
11	0	1	0	1
10	1	1	0	1

После нахождения всех групп в карте Карно, минимизированная ДНФ будет выглядеть следующим образом:

Минимизированная ДНФ = + + + +

Сравним полученную минимизированную ДНФ с результатом задачи 2 (сокращение методом Квайна):

Сокращенная ДНФ = + + + +

Минимизированная ДНФ = + + + +

Видно, что результаты с помощью метода Квайна и метода карт Карно получен одинаковый. Следовательно, методом Квайна также была получена минимизированная ДНФ.

Вывод:

С помощью карт Карно была построена минимизированная ДНФ функции f. Она совпадает с сокращенной ДНФ, полученной методом Квайна.

Задача 4.

Постановка задачи:

Построить МТ: систему продукций, алфавит, множество состояний. Представить контрольный пример входного слова, а также проверочную последовательность конфигураций, образующуюся в результате применения МТ к контрольному примеру входного слова.

Дана последовательность двоичных чисел, разделенных точками. В конце последовательности справа стоят две точки. Заменить последнее (крайнее правое) число на цепочку единиц.

Ход решения:

Алфавит МТ:

0 и 1 – двоичные символы;
(.) – разделитель чисел;
(_) – символ пустой ячейки.

Множество состояний:

– начальное состояние. Двигаемся вправо, пока не найдем две подряд идущие точки (..).
– обнаружена первая точка. Проверяем следующий символ.
– обнаружены две точки (..). Переход к последнему числу, двигаемся влево.
– заменяем 0 на 1 и пропускаем 1, двигаясь влево, пока не дойдем до разделителя (.).
– возвращаемся вправо, проверяем правильность замены.

Система продукций:
1. Поиск конца последовательности (..).
  Двигаемся вправо, пока не найдем две точки подряд.

( , 0) → ( , 0, R) — пропускаем 0, движемся вправо.
( , 1) → ( , 1, R) — пропускаем 1, движемся вправо.
( , .) → ( , ., R) — нашли первую точку, проверяем следующий символ.

Обнаружение второй точки.
Если после первой точки идет снова точка – нашли конец последовательности.

( , 0) → ( ,, 0, R) — это не конец, возвращаемся в q0.
( , 1) → ( ,, 1, R) — это не конец, возвращаемся в q0.
( , .) → ( , ., L) — обнаружены (..), начинаем обработку.

Замена последнего числа на цепочку единиц.
Двигаемся влево и заменяем 0 на 1.

( , .) → ( , ., L) — пропускаем точку и двигаемся влево.
( , 0) → ( , 1, L) — заменяем 0 на 1, продолжаем влево.
( , 1) → ( , 1, L) — 1 уже правильная, просто двигаемся влево.
( , .) → ( , ., R) — дошли до разделителя, останавливаем замену.

Завершение работы.
Возвращаемся вправо к (..) и завершаем.

( , 1) → ( , 1, R) — идем вправо, пока не встретим (..).
( , .) → ( , ., N) — работа завершена.

Контрольный пример и последовательность конфигураций:

Входное слово: 101.11.010..

Ожидаемое преобразование: 101.11.111..

Последовательность конфигураций:

Начальное состояние читает первую 1, ничего не меняет и переходит вправо. Так продолжается до первой точки.
Конфигурация: 1 1.11.010..
Конфигурация: 10 .11.010..
Состояние находит первую точку, переходит в .
Конфигурация: 101 11.010..
Состояние читает следующую 1 и возвращается в состояние .
Конфигурация: 101.
Так продолжается до предпоследней точки.
Состояние считывает точку и переходит в состояние
Конфигурация: 101.11.010
Состояние считывает вторую точку и переходит в состояние . Двигается влево.
Конфигурация: 101.11.010.
Состояние пропускает точку и переходит в состояние , продолжая двигаться влево.
Конфигурация: 101.11.01 .
Состояние заменяет 0 на 1, продолжает двигаться влево.
Конфигурация: 101.11.0 1..
Состояние пропускает 1 и продолжает двигаться влево.
Конфигурация: 101.11. 11..
Состояние заменяет 0 на 1, продолжает двигаться влево.
Конфигурация: 101.11 111..
Состояние считывает точку, останавливает замену, меняет состояние на и двигается вправо.
Конфигурация: 101.11 111..
Состояние двигается вправо, пропуская 1 до первой точки, после чего останавливает работу.
Конфигурация: 101.11.111
После завершения работы МТ для всего слова получаем выход: 101.11.111..

Вывод:

Была построена МТ для чтения последовательности чисел, разделенных точками и заканчивающаяся двумя точками, которая заменяет последнее правое число на цепочку единиц.