Решение. Решение По условию задачи начальная конфигурация ленты мт имеет вид

• Название: Решение По условию задачи начальная конфигурация ленты мт имеет вид
• Дата: 14.02.2022
• Размер: 62.58 Kb.
• Имя файла: Решение.docx
• Тип: Решение; #360992

Задача 1

Составьте программу машины Тьюринга, стирающей данный массив единиц. В результате работы программы происходит следующее преобразование машинных слов:

01^x0^y1^z-1q₁10 -> 01^x-1q₀101^y+z+10
Решение:

По условию задачи начальная конфигурация ленты МТ имеет вид:



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



головка МТ обозревает правую единицу группы из х единиц.

Сравнивая начальную и конечную конфигурации, определяем: для того, чтобы получить требуемую конфигурацию, необходимо:

1) к группе из z единиц приписать справа еще две единицы, после этого на ленте будет х единиц, у нулей и z+2 единиц;

2) в группе из у нулей заменить все нули, кроме самого левого, на единицы, после этого на ленте будет х единиц, один нуль и y-1+z+2 = y+z+1 единиц;

3) установить головку МТ на самую правую единицу в группе из х единиц и завершить работу.

Предполагая, что алфавит МТ – {0,1} и справа и слева от начальной конфигурации на ленте записаны нули, составляем программу МТ в соответствии с описанным выше алгоритмом.

состояние	обозреваемый символ		Комментарий
	0	1
q1		1Rq2	Из начального состояния q1 сдвигаем головку МТ вправо, переходим в состояние q2, ожидаем увидеть 0. В начальном состоянии должны видеть 1, поэтому команды для 0 нет.
q2	1Rq3		Увидели первый 0 слева от группы из z единиц. Заменяем его на 1, сдвигаем головку МТ вправо, переходим в состояние q3, ожидаем увидеть 0. В начальном состоянии справа от z-группы должны быть 0, поэтому команды для 1 нет.
q3	1Lq4		Увидели второй 0 слева от группы из z единиц. Заменяем его на 1, сдвигаем головку МТ влево, переходим в состояние q4. В начальном состоянии справа от z-группы должны быть только 0, поэтому команды для 1 нет.
q4	1Lq5	1Lq4	Сдвигаем головку МТ влево, пока не увидим самый правый 0 в группе из у нулей. Если увидели 0, заменяем его на 1, сдвигаем головку МТ влево, переходим в состояние q5.
q5	1Lq5	1Rq6	Сдвигаем головку МТ влево и заменяем 0 на 1, пока не увидим самую правую 1 в группе из x единиц. Если увидели 1, смещаемся вправо для вставки 0 и переходим в состояние q6.
q6		0Lq0	Заменяем 1 на 0, разделяя x-группу единиц и y+z+1-группу единиц, смещаемся влево и переходим в финальное состояние q0.

Задача 2

1. Функция f(x₁,x₂,x₃) принимает единичные значения на наборах №№ 0, 1, 4, 6, 7.

2. Является ли полной система булевых функций, состоящая из дизъюнкции и конъюнкции

1. Для указанной функции трех переменных:

- составить таблицу истинности;

- определить, к каким классам булевых функций она относится;

- записать совершенные СДНФ и СКНФ;

- найти минимальную ДНФ;

- для полученной минимальной ДНФ построить логическую схему в базисах а) {дизъюнкция, отрицание}, б) {конъюнкция, отрицание}.

2. Доказать полноту (или неполноту) приведенной системы булевых функций.
Решение:

1. Функция f(x₁,x₂,x₃) принимает единичные значения на наборах №№ 0, 1, 4, 6, 7.

1. Составляем таблицу истинности для указанной функции трех переменных, в строки с номерами 0, 1, 4, 6, 7 записываем значение функции 1, в остальные строки (2, 3, 5) – значение функции 0:

№	x1	x2	x3	f(x1,x2,x3)
0	0	0	0	1
1	0	0	1	1
2	0	1	0	0
3	0	1	1	0
4	1	0	0	1
5	1	0	1	0
6	1	1	0	1
7	1	1	1	1

Определяем, к каким классам булевых функций относится данная функция:









Для определения принадлежности функции к классу L линейных функций найдем полином Жегалкина для данной функции, используем для этого треугольник Паскаля:

x1 x2 x3	f(x1,x2,x3)
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1	1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1

Получаем:

.

Таким образом, данная функция принадлежит только классу Т1 функций, сохраняющих единицу.

Записываем СДНФ данной функции, используем для этого строки таблицы истинности, в которых она принимает значение 1:



Записываем СДНФ данной функции, используем для этого строки таблицы истинности, в которых она принимает значение 0:


Находим минимальную ДНФ данной функции с помощью карты Карно:

x 3 \ x1 x2	0 0	0 1	1 1	1 0
0	000		110	100
1	001		111

Получаем импликанты:

{000, 001}: K₁ =

{000, 100}: K₂ =

{110, 100}: K₃ =

{110, 111}: K₄ =

Следовательно, сокращенная ДНФ имеет вид:

f_сокр. = .

Две единицы (001 и 111) имеют единственное покрытие импликантами К₁

и К₄, которые образуют ядровую ДНФ:

f_ядр. = .

Единственная единица, не покрываемая ядром (100), имеет два варианта покрытия импликантой К₂ или К₃, получаем две тупиковых ДНФ:

f_туп.1. =

f_туп.2 = ,

которые и являются минимальными ДНФ:

f_мин.1. =

f_мин.2 = .

Для полученных минимальных ДНФ строим логическую схему в заданных базисах.

а) Для базиса {дизъюнкция, отрицание}, используя закон де Моргана , запишем первую минимальную ДНФ в виде:

f_мин.1. =
Соответствующая логическая схема имеет вид:


б) Для базиса {конъюнкция, отрицание}, используя закон де Моргана , запишем вторую минимальную ДНФ в виде:

f_мин.2 = .

Соответствующая логическая схема имеет вид:


2. Для доказательства полноты (или неполноты) системы булевых функций, состоящей из дизъюнкции и конъюнкции, определим принадлежность функций системы классам Поста:

- для дизъюнкции определяем:











;

- для конъюнкции определяем:











Итоговая таблица принадлежности функция системы классам Поста имеет вид:

	Т0	Т1	S	M	L
дизъюнкция	+	+	-	+	-
конъюнкция	+	+	-	+	-

Система булевых функций является полной, если функции системы не принадлежат одновременно ни одному из классов Поста.

Однако обе функции данной системы, состоящей из дизъюнкции и конъюнкции, принадлежат одновременно классам поста Т0 (функций, сохраняющих 0), Т1 (функций, сохраняющих 1) и М (монотонных функций). Следовательно, данная система функций не является полной.