Основы логики. 1 Изучаем вычисление булевых функций, приобретаем навыки вычислений

• Название: 1 Изучаем вычисление булевых функций, приобретаем навыки вычислений
• Анкор: Основы логики
• Дата: 18.04.2022
• Размер: 26.01 Kb.
• Имя файла: Olu_1-8.docx
• Тип: Документы; #481957

1) Изучаем вычисление булевых функций, приобретаем навыки вычислений.

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

___ _ _______ _ _ _

х₁х₂х₃х₂(х₁х₃)х₂=х₁х₂х₃

б) вычислить значения одной из функций задания №2 на всех наборах без преобразования (по таблицам истинности).

2) Привести с помощью основных законов БФ к ДНФ и КНФ. Определить их сложность и цену по Квайну.

_________

_ _ _______

1) х₁х₂х₃х₂ (х₁х₃) х₂
_____________

2) х₁х₂х₃(х₁х₂)х₃
3) .

2) Изучаем построение выражений по таблице истинности, приводим к совершенным, сокращенным ДНФ и КНФ.

Таблица истинности для f_1, f_2, f_3, f₄

х1х2х3х4	f1	f2	х1х2х3	f3	f4
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1	1 1 0 1 0 0 1 0 1 1 0 0 0 1 1 0	1 0 0 1 0 0 1 0 0 1 1 1 1 0 1 0	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 0 0 0 1 1 1 0	0 1 1 0 1 0 0 1

Составить отчет на листах формата А4 или в электронной форме. Выполнять задания с пояснениями каждого действия. Сделать вывод по результатам работы, отразив в нем объем и содержание выполненных заданий.

Подготовить ответы на контрольные вопросы.

КОНТРОЛЬНЫЕ ВОПРОСЫ

Булевы функции, определение, способы задания. Таблицы истинности основных булевых функций. Приоритет вычисления булевых функций в выражении. Основные законы алгебры логики Что такое кортеж? Что такое конституента 1 или 0? Как конституенты соотносятся с кортежами?

«Определение мощности производственного оборудования»

Задание

Оборудование цеха позволяет реализовать несколько вариантов производственно-технологических процессов. Известна производительность каждой единицы оборудования, исчисляемая в количестве выполняемых операций за единицу времени. Необходимо определить максимально возможную общую мощность имеющегося в цехе оборудования, если производство можно организовать одновременно по нескольким возможным технологическим процессам (ТП).

Варианты ТП представлены в виде ориентированного графа или сети с начальной вершиной «исходная заготовка» и конечной – «готовая деталь». Промежуточные вершины – состояния детали в процессе обработки, дуги – операции, изменяющие состояние детали. Дуги взвешены весовыми коэффициентами предельной производительности каждой единицы оборудования.

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

Порядок выполнения:

1. 
   Построить исходный граф
   
2. 
   По исходному графу построить граф достижимости, каждая вершина которого взаимно однозначно соответствует дуге исходного графа, и соединяются ребрами, если соответствующие им дуги входят в маршрут от начальной вершины к конечной в исходном графе. Так, каждый такой маршрут (вариант техпроцесса) исходного графа будет связным полным подграфом в графе достижимости.
   
3. 
   Любой пустой подграф графа достижимости взаимно однозначно соответствует разрезу исходной сети. Минимальная сумма пропускных способностей дуг разреза – максимальный поток в сети или максимальная производственная мощность имеющегося оборудования. По алгоритму получения пустых подграфов определить все возможные подграфы и выбрать тот, который определяет пропускную способность сети.
   

Выполнить задание, обосновать решение, сделать выводы.

Алгоритм определения пустых подграфов в графе достижимости D

Сопоставляем корню синтезируемого дерева граф достижимости D. Фиксируем в графе вершину с минимальной локальной степенью v0 сопоставляем ее концу дуги из корня. Вершины окрестности вершины v0 (Гv0 ) сопоставляем остальным дугам этого яруса с корнем в G. Граф неокрестности вершины v0 -¬Гv0 - припишем вершине v0 Выберем в графе неокрестности v0 (¬Гv0 ) вершину с минимальной локальной степенью vα. . Сопоставим ее концу дуги из v0.													Назовем vα. - v0. Повторим пп.3-5, пока неокрестность очередной вершины остается непустой - |¬Гv0 | ≠ Ø. Иначе - пометить очередную v0 значком «Ø» - это означает, что пустой подграф построен. Если очередная ветвь является подмножеством уже построенной – действует закон поглощения и следует перейти к следующей ветви. Достроить таким же образом все остальные ветви до их маркировки значком «Ø».
		1	2	3	4	5	6	7	8	9	10
	1	-	6	6	4
	2		-				4
	3			-		6	5
	4				-	8		4
	5					-			5	4
	6						-			2
	7							-			8
	8								-	3
	9									-	4