Аппаратное обеспечение Интеллектуальных систем. 3 лаб ed. Минимизация булевых функций
 Скачать 43.13 Kb.
|
|
МИНИСТЕРСТВО ЦИФРОВЫХ ТЕХНОЛОГИЙ РЕСПУБЛИКИ УЗБЕКИСТАН ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНИ МУХАММАДА АЛ-ХОРАЗМИЙ Факультет: «ТАТУ-БГУИР совместный факультет информационных технологий» Направление: «Искусственный Интеллект» ПРЕДМЕТ: Аппаратное обеспечение интеллектуальных систем Лабораторная работа 2 Тема: Минимизация булевых функций Выполнил: Исамиддинов Ботир Студент группы: 12-21 Ташкент 2023 Задание на лабораторную работу 1. Записать формулу функции ( , , ) в виде СДНФ и минимизировать ее графическим методом, методом неопределенных коэффициентов и методом минимизирующих карт Карно. Сравнить полученные результаты. 2. Записать формулу функции ( , , , ) в виде СДНФ и минимизировать ее методами Квайна, Мак-Класки и диаграммами Вейча. Сравнить полученные результаты. 3. Реализовать один из методов программным образом (методы раздаются на практике преподавателем) 10 вариант Введённый вектор: 11100110 Таблица истинности:
Совершенная дизъюнктивная нормальная форма (СДНФ)¬x1¬x2¬x3 ∨ ¬x1¬x2x3 ∨ ¬x1x2¬x3 ∨ x1¬x2x3 ∨ x1x2¬x3 Полином Жегалкина1⊕x2x3⊕x1⊕x1x3⊕x1x2⊕x1x2x3 РешениеПостроение совершенной дизъюнктивной нормальной формы:Найдём наборы, на которых функция принимает истинное значение: { 0, 0, 0 } { 0, 0, 1 } { 0, 1, 0 } { 1, 0, 1 } { 1, 1, 0 } В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием: K1: { 0, 0, 0 } — ¬x1¬x2¬x3 K2: { 0, 0, 1 } — ¬x1¬x2x3 K3: { 0, 1, 0 } — ¬x1x2¬x3 K4: { 1, 0, 1 } — x1¬x2x3 K5: { 1, 1, 0 } — x1x2¬x3 Объединим конъюнкции с помощью операции ИЛИ и получим совершенную дизъюнктивную нормальную форму: K1 ∨ K2 ∨ K3 ∨ K4 ∨ K5 = ¬x1¬x2¬x3 ∨ ¬x1¬x2x3 ∨ ¬x1x2¬x3 ∨ x1¬x2x3 ∨ x1x2¬x3 Построение полинома Жегалкина методом Паскаля:
Построение полинома Жегалкина методом треугольника:
1. Строится треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности. 2. Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже. 3. Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности. 4. Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. 5. Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина. Построение полинома Жегалкина методом неопределённых коэффициентов:Запишем данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами: f(x1,x2,x3) = a000 ⊕ a100x1 ⊕ a010x2 ⊕ a001x3 ⊕ a110x1x2 ⊕ a101x1x3 ⊕ a011x2x3 ⊕ a111x1x2x3 f(0,0,0) = a000 = 1 ⇒ a000 = 1 f(1,0,0) = a000 ⊕ a100 = 1 ⊕ a100 = 0 ⇒ a100 = 1 f(0,1,0) = a000 ⊕ a010 = 1 ⊕ a010 = 1 ⇒ a010 = 0 f(0,0,1) = a000 ⊕ a001 = 1 ⊕ a001 = 1 ⇒ a001 = 0 f(1,1,0) = a000 ⊕ a100 ⊕ a010 ⊕ a110 = 1 ⊕ 1 ⊕ 0 ⊕ a110 = 1 ⇒ a110 = 1 f(1,0,1) = a000 ⊕ a100 ⊕ a001 ⊕ a101 = 1 ⊕ 1 ⊕ 0 ⊕ a101 = 1 ⇒ a101 = 1 f(0,1,1) = a000 ⊕ a010 ⊕ a001 ⊕ a011 = 1 ⊕ 0 ⊕ 0 ⊕ a011 = 0 ⇒ a011 = 1 f(1,1,1) = a000 ⊕ a100 ⊕ a010 ⊕ a001 ⊕ a110 ⊕ a101 ⊕ a011 ⊕ a111 = 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ a111 = 0 ⇒ a111 = 1 Окончательно получаем: 1 ⊕ x1 ⊕ x1x2 ⊕ x1x3 ⊕ x2x3 ⊕ x1x2x3 2. Записать формулу функции ( , , , ) в виде СДНФ и минимизировать ее методами Квайна, Мак-Класки и диаграммами Вейча. Сравнить полученные результаты. Введённый вектор: 11100110 Таблица истинности:
Совершенная дизъюнктивная нормальная форма (СДНФ)¬x1¬x2¬x3 ∨ ¬x1¬x2x3 ∨ ¬x1x2¬x3 ∨ x1¬x2x3 ∨ x1x2¬x3 Совершенная конъюнктивная нормальная форма (СKНФ)(x1∨¬x2∨¬x3) ∧ (¬x1∨x2∨x3) ∧ (¬x1∨¬x2∨¬x3) Полином Жегалкина1⊕x2x3⊕x1⊕x1x3⊕x1x2⊕x1x2x3 Карта Карно:
Минимизированная ДНФ:x2¬x3∨¬x2x3∨¬x1¬x2 Минимизированная КНФ:(¬x2∨¬x3)∧(¬x1∨x2∨x3) РешениеПостроение совершенной дизъюнктивной нормальной формы:Найдём наборы, на которых функция принимает истинное значение: { 0, 0, 0 } { 0, 0, 1 } { 0, 1, 0 } { 1, 0, 1 } { 1, 1, 0 } В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием: K1: { 0, 0, 0 } — ¬x1¬x2¬x3 K2: { 0, 0, 1 } — ¬x1¬x2x3 K3: { 0, 1, 0 } — ¬x1x2¬x3 K4: { 1, 0, 1 } — x1¬x2x3 K5: { 1, 1, 0 } — x1x2¬x3 Объединим конъюнкции с помощью операции ИЛИ и получим совершенную дизъюнктивную нормальную форму: K1 ∨ K2 ∨ K3 ∨ K4 ∨ K5 = ¬x1¬x2¬x3 ∨ ¬x1¬x2x3 ∨ ¬x1x2¬x3 ∨ x1¬x2x3 ∨ x1x2¬x3 Построение совершенной конъюнктивной нормальной формы:Найдём наборы, на которых функция принимает ложное значение: { 0, 1, 1 } { 1, 0, 0 } { 1, 1, 1 } В соответствие найденным наборам поставим элементарные дизъюнкции по всем переменным, причём если переменная в наборе принимает значение 1, то она будет записана с отрицанием: D1: { 0, 1, 1 } — x1∨¬x2∨¬x3 D2: { 1, 0, 0 } — ¬x1∨x2∨x3 D3: { 1, 1, 1 } — ¬x1∨¬x2∨¬x3 Объединим дизъюнкции с помощью операции И и получим совершенную конъюнктивную нормальную форму: D1 ∧ D2 ∧ D3 = (x1∨¬x2∨¬x3) ∧ (¬x1∨x2∨x3) ∧ (¬x1∨¬x2∨¬x3) Построение полинома Жегалкина методом Паскаля:
Построение полинома Жегалкина методом треугольника:
1. Строится треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности. 2. Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже. 3. Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности. 4. Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. 5. Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина. Построение полинома Жегалкина методом неопределённых коэффициентов:Запишем данную функцию в виде полинома Жегалкина с неопределёнными коэффициентами: f(x1,x2,x3) = a000 ⊕ a100x1 ⊕ a010x2 ⊕ a001x3 ⊕ a110x1x2 ⊕ a101x1x3 ⊕ a011x2x3 ⊕ a111x1x2x3 f(0,0,0) = a000 = 1 ⇒ a000 = 1 f(1,0,0) = a000 ⊕ a100 = 1 ⊕ a100 = 0 ⇒ a100 = 1 f(0,1,0) = a000 ⊕ a010 = 1 ⊕ a010 = 1 ⇒ a010 = 0 f(0,0,1) = a000 ⊕ a001 = 1 ⊕ a001 = 1 ⇒ a001 = 0 f(1,1,0) = a000 ⊕ a100 ⊕ a010 ⊕ a110 = 1 ⊕ 1 ⊕ 0 ⊕ a110 = 1 ⇒ a110 = 1 f(1,0,1) = a000 ⊕ a100 ⊕ a001 ⊕ a101 = 1 ⊕ 1 ⊕ 0 ⊕ a101 = 1 ⇒ a101 = 1 f(0,1,1) = a000 ⊕ a010 ⊕ a001 ⊕ a011 = 1 ⊕ 0 ⊕ 0 ⊕ a011 = 0 ⇒ a011 = 1 f(1,1,1) = a000 ⊕ a100 ⊕ a010 ⊕ a001 ⊕ a110 ⊕ a101 ⊕ a011 ⊕ a111 = 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ a111 = 0 ⇒ a111 = 1 Окончательно получаем: 1 ⊕ x1 ⊕ x1x2 ⊕ x1x3 ⊕ x2x3 ⊕ x1x2x3 Минимизация ДНФ
Выделим на карте Карно прямоугольные области из единиц наибольшей площади, являющиеся степенями двойки и выпишем соответствующие им конъюнкции: Область 1:
K1: x2¬x3 Область 2:
K2: ¬x2x3 Область 3:
K3: ¬x1¬x2 Объединим их с помощью операции ИЛИ и получим минимизированную ДНФ: x2¬x3∨¬x2x3∨¬x1¬x2 Минимизация КНФ
Выделим на карте Карно прямоугольные области из нулей наибольшей площади, являющиеся степенями двойки и выпишем соответствующие им дизъюнкции: Область 1:
D1: (¬x2∨¬x3) Область 2:
D2: (¬x1∨x2∨x3) Объединим их с помощью операции И и получим минимизированную КНФ: (¬x2∨¬x3)∧(¬x1∨x2∨x3) 3. Реализовать один из методов программным образом (методы раздаются на практике преподавателем) Карта Карно:
Выделим на карте Карно прямоугольные области из единиц наибольшей площади, являющиеся степенями двойки и выпишем соответствующие им конъюнкции: Область 1:
K1: x2¬x3 Область 2:
K2: ¬x2x3 Область 3:
K3: ¬x1¬x2 Объединим их с помощью операции ИЛИ и получим минимизированную ДНФ: x2¬x3∨¬x2x3∨¬x1¬x2 Минимизация КНФ
Выделим на карте Карно прямоугольные области из нулей наибольшей площади, являющиеся степенями двойки и выпишем соответствующие им дизъюнкции: Область 1:
D1: (¬x2∨¬x3) Область 2:
D2: (¬x1∨x2∨x3) Объединим их с помощью операции И и получим минимизированную КНФ: (¬x2∨¬x3)∧(¬x1∨x2∨x3) |