42424

Минимизация булевых функций методом Квайна

Лабораторная работа

Математика и математический анализ

Теоретическая часть Рассмотренные выше совершенная дизъюнктивная и конъюнктивная нормальные формы СДНФ и СКНФ используются для первоначального представления заданной переключательной функции через функции основной системы. Но эти формы не удобны для построения логических схем ЭВМ так как часто содержат элементы которые можно исключить при синтезе схем исходя из других форм представления функции. Существует ряд эффективных способов нахождения минимальной ДНФ булевой функции. Применяемая в методе Квайна операция неполного склеивания...

Русский

2013-10-29

686 KB

146 чел.

Практическое занятие №11

Тема: Минимизация булевых функций методом Квайна.

Цель работы: практическое овладение  минимизацией булевых функций методом Квайна.

Теоретическая часть

Рассмотренные выше совершенная дизъюнктивная и конъюнктивная нормальные формы (СДНФ и СКНФ) используются для первоначального представления заданной переключательной функции через функции основной системы. Но эти формы не удобны для построения логических схем ЭВМ, так как часто содержат элементы, которые можно исключить при синтезе схем, исходя из других форм представления функции. Поэтому  очередная задача построения логических схем заключается в упрощении выражений для переключательных функций. Этот этап синтеза логических схем называют минимизацией булевых функций.

Определение1: Конституентой единицы (минтермом) называют переключательную функцию n аргументов, которая принимает значение, равное 1 только на одном кортеже аргументов. Число различных конституент единицы среди функций n аргументов равно числу различных кортежей – наборов, т.е. равно 2n.

Определение 2: Конституентой нуля (макстермом) называют переключательную функцию n аргументов, которая принимает значение, равное 0 только на одном наборе. Имеется 2n конституент нуля.

Определение 3: Простыми импликантами ПФ называются термы – элементарные произведения, которые сами входят в данную функцию, но никакая собственная часть этих произведений в функцию f не входит.

Простые импликанты представляют собой самые короткие термы – элементарные произведения, входящие в данную ПФ.

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

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

Следовательно, минимальную ДНФ данной формулы можно найти, перебрав конечное число равносильных ей ДНФ и выбрав среди них ту, которая содержит минимальное число переменных. Однако при большом числе переменных такой перебор практически невыполним.  

Существует ряд эффективных способов нахождения минимальной ДНФ булевой функции.

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

Операция полного склеивания: (1).

Операция поглощения:    (2).

Применяемая в методе Квайна операция  неполного склеивания получается из соотношений (1) и (2) и определяется формулой

(3)

Теорема Квайна: Если в СДНФ переключательной функции провести все операции неполного склеивания, а затем все операции поглощения, то в результате получится сокращенная ДНФ этой функции, т.е. дизъюнкция всех её простых импликант.

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

Пример: Найти минимальную ДНФ булевой функции

 1. Нахождение первичных импликант.

Все минтермы данной функции сравниваются попарно. Если минтермы m и  n таковые, что имеют вид  и , то выписывается конъюнкция , являющаяся минтермом (n-1)-го ранга. Минтермы n-го ранга, для которых произошло склеивание, отмечаются. После построения всех минтермов

(n-1)-го ранга вновь сравнивают их попарно, выписывают минтермы

(n-2)-го ранга, вновь сравнивают их попарно, выписывают минтермы

(n-3)-го ранга и т.д. Этап заканчивается, когда минтермы уже не склеиваются между собой. Все отмеченные минтермы называются первичными или простыми импликантами.

На этом этапе составляется  таблица заданных в условии минтермов n-го ранга.

1

1

1

1

1

1

1

1

Минтермы третьего ранга:

, , ,  , , ,  , , ,

Таблица 2 заполняется для минтермов 3-го ранга по аналогии.

Получаем минтермы 2-го ранга:

Так как дальнейшее склеивание не возможно, то этап получения простых импликант закончен. Простыми импликантами являются:

2. Расстановка меток ().

Для нахождения минимального покрытия интервалами максимального ранга необходимо произвести удаление некоторых первичных импликант. На этом этапе составляется таблица, число строк которой равно числу полученных первичных импликант минимизируемой функции. Число столбцов равно числу минтермов СДНФ. Если в некоторый минтерм входит какая-либо из первичных импликант, то на пересечении соответствующего столбца и строки ставится метка.

   

Минтермы заданной функции

Первичные импликанты

abcd

abcd

abcd

abcd

abcd

abcd

abcd

abcd

cd

ac

ad

3. Нахождение существенных импликант.

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

В нашем случае все импликанты существенные.

4. Вычеркивание лишних столбцов.

Исследуется полученная таблица после 3-го этапа. Если в ней есть два столбца, в которых имеются  метки в одинаковых строках, то один из них вычеркивается. Это можно сделать в силу того, что покрытие оставшегося столбца будет осуществлять покрытие вычеркнутого минтерма.

5. Вычеркивание лишних первичных импликант.

Если после удаления некоторых столбцов на 4-ом этапе появляются строки, в которых нет ни одной метки, то соответствующая им первичная импликанта исключается из дальнейшего рассмотрения.

6. Выбор максимального покрытия минимальными интервалами.

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

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

Минимальная ДНФ этой функции имеет вид:

f(a,b,c,d)=cdacad

Контрольные вопросы

  1.  Какая ДНФ называется  минимальной? Как найти ее?
  2.  Назовите этапы метода Квайна?

Индивидуальные задания

Сложное высказывание формализовано и имеет вид  логической функции.

Исследуйте эту формулу на разрешимость, постройте её ДНФ (КНФ), СДНФ (СКНФ).

Найдите минимальную ДНФ (КНФ) булевой функции методом Квайна.

  1.  F(A,B,C,D)=(((BCDDDCCD
  2.  F(A,B,C,D)=CDCCC
  3.  F(A,B,C,D)=CDCD
  4.  F(A,B,C,D)=CCD
  5.  F(A,B,C,D)=CDCDD
  6.  F(A,B,C,D)=DDCD
  7.  F(A,B,C,D)=DCCDD
  8.  F(A,B,C,D)=DC
  9.  F(A,B,C,D)=CDCDC
  10.  F(A,B,C,D)=DDCCCDC
  11.  F(A,B,C,D)=CDCC
  12.  F(A,B,C,D)=DCDDCD
  13.  F(A,B,C,D)=DCDCD
  14.  F(A,B,C,D)=CDD
  15.  F(A,B,C,D)=CDC
  16.  F(A,B,C,D)=CDCD
  17.  F(A,B,C,D)=CDCD
  18.  F(A,B,C,D)=CDCD
  19.  F(A,B,C,D)=DC
  20.  F(A,B,C,D)=CDCD
  21.   F(A,B,C,D)=DCCDD
  22.  F(A,B,C,D)=DC
  23.  F(A,B,C,D)=CDCDC
  24.  F(A,B,C,D)=DDCCCDC
  25.  F(A,B,C,D)=CDCC
  26.  F(A,B,C,D)=CDCD
  27.  F(A,B,C,D)=CDCD
  28.  F(A,B,C,D)=CDCD
  29.  F(A,B,C,D)=DC
  30.  F(A,B,C,D)=CDCD

Практическое занятие №12

Тема: Минимизация булевых функций методом  Мак-Класки.

Цель работы: овладение минимизацией булевых функций методом Мак-Класки

Теоретическая часть

В рассмотренном ранее методе Квайна есть один существенный недостаток. Он связан с необходимостью полного попарного сравнения всех минитермов на этапе нахождения простых импликант. С ростом числа минитермов, определяющих СДНФ данной функции, растёт число сравнений. Этот рост характеризуется факториальной функцией. Поэтому при достаточно большом числе минитермов применение метода Квайна, становится затруднительным.

       В  1956 г. Мак-Класки  предложил модификацию первого этапа метода Квайна, дающую существенное уменьшение числа сравнений минитермов. Идея заключается в следующем:1) записать минитермы в виде двоичных наборов;

2) разбить все наборы по числу единиц в них на непересекающиеся группы.

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

Пример:  Функция задана в СДНФ минитермами с номерами 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 15.               

           Найти минимальную  ДНФ  методом Мак-Класки.

           Решение:

Запишем минитермы в двоичном коде по группам:

           1. 0-я группа: 0000

           2. 1-я группа: 0001, 0010, 0100, 1000

           3. 2-я группа: 0011,0110,1001,0101

           4. 3-я группа: 0111,1011

           5. 4-я группа: 1111

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

            0-я группа: 000-, 00-0, 0-00,-000

            1-я группа: 00-1, -001, 001-, 0-10, 01-0, 100-, 0-01, 010-

            2-я группа: 0-11,011-,01-1,-011 ,10-1

            3-я группа: -111,1-11

Теперь найдём минитермы второго ранга:

            0-я группа: 00--, -00-, 0--0,0-0-

            1-я группа: -0-1, 0-1-, 0--1

            2-я группа: --11

Сравнивая ещё раз 0-ю группу с 1-й, получим: 0 - - - .

2. Составим таблицу меток:

0000

0001

0010

0011

0100

0110

0111

1000

1001

1011

1111

00--

+

+

+

+

-00-

+

+

+

+

0--0

+

+

+

+

-0-1

+

+

+

+

0---

+

+

+

+

+

+

+

--11

+

+

+

+

Дальнейшая минимизация по методу Мак-Класки совпадает с минимизацией по методу Квайна.

3. Для нашего случая существенными являются импликанты: -00- и --11.

Выписываем оставшуюся таблицу меток:

0110

0100

00--

+

0--0

+

+

0---

+

+

Для рассматриваемой функции минимальная ДНФ имеет вид:

Контрольные вопросы

1. Перечислите этапы метода Мак-Класки?

2. На каком этапе он совпадает с методом Квайна?

Индивидуальные задания

7.1 Используя метод Мак-Класки, найдите минимальную ДНФ заданной функции, если известно, что f(a,b,c,d) задана в виде двоичных наборов:

 Номер                             вашего                               варианта

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

0

0

0

1

0

1

0

0

1

0

1

0

1

0

1

0

0

1

0

0

1

0

1

0

1

0

0

1

0

2

2

1

3

2

2

2

2

2

2

1

2

2

2

1

2

2

2

2

1

1

2

2

2

1

2

2

2

2

1

3

3

2

4

3

4

5

4

4

3

3

4

4

3

2

3

3

3

3

3

3

4

4

3

2

3

3

3

3

3

4

4

5

5

5

5

6

6

5

4

5

5

5

6

5

4

5

4

4

5

5

5

5

6

5

4

5

4

4

5

6

5

7

7

7

7

7

7

6

5

7

6

6

7

4

6

6

6

5

7

7

6

6

7

4

6

6

6

5

7

8

7

8

8

8

9

8

8

8

7

9

9

8

8

6

7

9

8

8

9

9

9

8

8

6

7

9

8

8

9

10

8

10

9

10

10

10

9

7

10

10

11

9

9

8

8

10

10

9

10

10

11

9

9

8

8

10

10

9

10

11

9

11

10

11

11

11

10

9

11

12

13

10

10

11

9

11

12

10

12

12

13

10

10

11

9

11

12

10

12

13

12

13

12

12

13

12

11

11

12

13

14

11

12

12

10

12

14

12

13

13

14

11

12

12

10

12

14

12

13

15

13

14

14

14

15

13

13

12

13

14

15

13

13

14

12

13

15

13

14

14

15

13

13

14

12

13

15

13

14

14

15

15

14

14

13

14

15

15

15

15

14

15

15

15

15

15

15

15

14

15

15

15

Практическое занятие №13

Тема: Минимизация булевой функции методом Карно-Вейча.

Цель работы: овладение навыками получения тупиковых и минимальных дизъюнктивных нормальных форм методом Карно-Вейча.

Теоретическая часть

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

Определение 2. Некоторые функции имеют несколько тупиковых форм. Тупиковые формы, содержащие наименьшее количество символов букв, будут минимальными.

Теорема 2. Любая минимальная ДНФ переключательной функции является тупиковой.

Определение 3. Для получения минимальной ДНФ достаточно получить все тупиковые формы заданной функции и выбирать из них минимальные.

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

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

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

Формы карт Карно для булевых функций 1) двух, 2) трёх, 3) четырех и 4) пяти переменных: а) дизъюнктивная форма; в) конъюнктивная форма.

1)

а)       б)

x

xy

xy

x

xy

xy

y

y

x

xy

xy

xy

xy

y

y

2) а)

y

y

x

xyz

xyz

xyz

xyz

x

xy z

xyz

xyz

xyz

z

z

z

б)

y

y

x

xyz

xyz

xyz

xyz

x

xyz

xyz

xyz

xyz

z

z

z

3)

B

B

A

C

C



C

D

D

D

4)

B

B

A

E

E

E

C

C



C

D

D

D

D

D

Аналогично строятся карты Карно и для булевых функций большего числа переменных. Необходимо знать, что карты Карно для 3-х переменных следует представлять себе в виде цилиндра, образованного соединением первой и последней колонок.

Тогда,  любая пара склеивающихся между собой конституент, будет находиться в соседних клетках. В картах для 4-х переменных, первую и последнюю колонки карты, а также верхнюю и нижнюю строки, следует считать соседними. Поэтому эту карту следует представлять нанесённой на поверхность тора.

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

.

Можно склеивать и четыре терма

 ,

а также любое число 2k термов, отличающихся друг от друга только k символами, входящими в эти термы. Практическое применение склеивания затрудняется тем, что не всегда удается заметить все возможности подобного склеивания непосредственно из выражений минимизирующих функций. Поэтому весьма полезными при формальной проектировании оказываются диаграммы Карно-Вейча, наглядность которых можно сравнить с наглядностью графиков для объектных функций.

Имеется опыт успешного применения диаграмм на 10 переменных и, по-видимому, это не предел. Ниже представлены диаграммы для  7-и переменных. Аналогичным образом могут быть построены диаграммы и для большего числа переменных.

Правила минимизации следующие: две соседние клетки образуют 1-куб, четыре клетки – 2-куб, восемь клеток – 3-куб, 16 клеток – 4-куб и т.д.

На карте для четырех переменных приведен пример образования 4-куба и 2-куба.

Первоначально функция представляется в одной из 2-х совершенных форм: СДНФ или СКНФ. Далее ищут 1-кубы, 2-кубы, 3-кубы и т.п., начиная со старшего, т.е. вначале 3-куб, затем 2-куб и т.п. Чем выше номер куба, тем проще терм, т.к. он содержит меньше переменных (больше переменных исключается).

Диаграмма Карно-Вейча для 7-и переменных

Контрольные вопросы

1. Изобразите карты Карно для 2-7 переменных.

2. В чем преимущество этого метода перед другими, ранее изученными?

3. Назовите правила минимизации метода Карно-Вейча.

Методические указания

Метод получения минимальных форм с помощью карт Карно объясняется   на примерах.

Пример 1:Найти минимальные ДНФ и КНФ функции f(a,b,c) методом Карно-Вейча.

f(a,b,c)=abcabcabcabcabc

Объединить единицы можно двумя способами:

а)

b

b

a

1

1

1

0

a

0

0

1

1

c

c

c

б)

b

b

a

1

1

1

0

a

0

0

1

1

c

c

c

Этим вариантам соответствуют две минимальных ДНФ:

а) f(a,b,c,d)=abacab;

б) f(a,b,c,d)=abbc ab.

Для получения минимальной КНФ следует объединить нули функции:

b

b

a

1

1

1

0

a

0

0

1

1

c

c

c

f(a,b,c)=(a b)( abc)

Пример 2: Найти минимальную ДНФ булевой функции:

f(a,b,c,d)=abcdabcdadcdabcdabcdabcdabcd.

Карта Карно для этой функции приведена ниже. На ней показан способ наиболее рационального покрытия единиц.

b

b

a

1

0

0

0

c

1

0

0

1

c

a

1

0

1

1

0

1

0

0

c

d

d

d

Минимальная ДНФ этой функции будет иметь вид:

f(a,b,c,d)=cdabd abcabcd.

Индивидуальные задания

 8.1 С помощью карт Карно найдите МДНФ и МКНФ булевой функции:

  1.  

  1.  f(a,b,c,d)=ab (cd a
  2.  f(a,b,c,d)=dcbac
  3.  f(a,b,c,d)=adc a b
  4.  f(a,b,c,d)=dba c ab
  5.  f(a,b,c,d)=bac d
  6.  f(a,b,c,d)=ad bac
  7.  f(a,b,c,d)=dbadcb
  8.  f(a,b,c,d)=acbdba
  9.  f(a,b,c,d)=bdcada
  10.  f(a,b,c,d)=bcdabc
  11.  f(a,b,c,d)=bcadbd
  12.  f(a,b,c,d)=cbadcb
  13.  f(a,b,c,d)=dbca
  14.  f(a,b,c,d)=dcdba
  15.  f(a,b,c,d)=dbaca
  16.  f(a,b,c,d)=dbdbac
  17.  f(a,b,c,d)=cbdbdac
  18.  f(a,b,c,d)=cbdab
  19.  f(a,b,c,d)=adaddcb
  20.  f(a,b,c,d)=ccaddcb;
  21.   f(a,b,c,d)=acbdba
  22.  f(a,b,c,d)=bdcada
  23.  f(a,b,c,d)=bcdabc
  24.  f(a,b,c,d)=bcadbd
  25.  f(a,b,c,d)=cbadcb
  26.  f(a,b,c,d)=dbadcb
  27.  f(a,b,c,d)=acbdba
  28.  f(a,b,c,d)=bdcada
  29.  f(a,b,c,d)=bcdabc
  30.  f(a,b,c,d)=bcadbd.


Практическое занятие №14

Тема: Геометрический метод нахождения минимальной ДНФ и КНФ.

Цель работы: овладение минимизацией булевых функций методом  Блейка-Порецкого и геометрическим методом.

Теоретическая часть

Геометрическое представление  функций алгебры логики

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

На каждой оси откладываются единичные отрезки X1X2 и получаем квадрат, вершины которого соответствуют комбинациям переменных. Это и будет геометрическое представление функций 2-х переменных (рис.1).

Рис.1.

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

.

Для функций 3-х переменных геометрическое представление интерпретируется в виде куба (рис.2.), вершины которого обозначают  десятичными цифрами, двоичными цифрами и переменными Х. Ребра куба поглощают вершины, грани поглощают свои ребра и, следовательно, вершины.

В общем случае совокупность векторов  отображается на множество вершин n-мерного куба. Все такие вершины образуют логическое пространство.

Булева функция отображается на n-мерном кубе путем выделения вершин, соответствующих векторам , на которых функция принимает значения «1». Такие значения отмечаются точками.

Рис.2.

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

Рис.3.

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

Функция 4-х переменных геометрически представляется в виде 4-мерного куба (рис.3).

Функция 5-ти переменных представляется в виде 5-мерного куба (рис 4).и т.д

Рис. 4

Формулировка геометрической задачи (задачи о покрытии): необходимо найти для данного множества N такое покрытие гранями, принадлежащими Nf,

, чтобы ранг был наименьшим.

Эта задача эквивалентна задаче о минимизации булевой функции.

Следовательно, задача минимизации булевых функций имеет две постановки:

  •  в аналитической форме;
  •  в геометрической форме (задача о покрытии).

Употребляются два языка: аналитический и геометрический.

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

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

Определение 2. ДНФ, соответствующая неприводимому покрытию множества, называется тупиковой (в геометрическом смысле).

Методические указания

Пример1. Метод Блейка-Порецкого.

Для заданной функции найти СДНФ методом Блейка -Порецкого:

 f(x1,x2,x3)=x1x2x1x2x3x1x2x3x2x3x1x3

Для этой функции имеется две пары конъюнкций, удовлетворяющих условию теоремы:

(x1x2x3; x1x2x3) и (x1x2; x2x3). Поэтому, используя операции неполного склеивания и поглощения  соответственно AxiBxi=AxiBxiAB и xxy=x, произведём элементарные поглощения.

Получаем СДНФ:

f(x1,x2,x3)=x1x2x3x1x2x3x1x2x2x3x1x3x1x3x1x3=x1x2x2x3x1x3

Дальнейшее нахождение минимальной ДНФ производится как по методу Квайна.

Пример 2.

Геометрический метод нахождения минимальной ДНФ и КНФ булевой функции.

Задана функция  (таблица 1). Этой функции соответствует множество минтермов:. Геометрически это может быть отображено в виде (см. рис. 5).     

   Таблица 1

000

0

100

0

001

1

101

0

010

1

110

1

011

1

111

1

Функции соответствуют грани.

,

имеющие соответственно ранги 2 и 1. Эти грани (рис. 3.5) являются соответственно одномерной гранью (ребром) и двумерной гранью (плоскостью). Грани  и  расположены внутри множества:

.

Рис.5.

Пример 3.

Рассмотрим пример получения тупиковой формы. Функция задана в виде таблицы 2.

Таблица 2

0100

0

0110

0

1001

0

1110

0

1110

0

на остальных ребрах

1

Эта функция геометрически изображается в виде четырехмерного куба (рис. 3.15).

Напоминание. Тупиковая ДНФ получается из сокращенной путем удаления некоторых членов. Минимальная ДНФ является тупиковой. Среди тупиковых ДНФ находится и минимальная ДНФ.

Рис.6 Геометрическое представление для 4-х переменных.

Контрольные вопросы

1. Дайте формулировку геометрической задачи (задачи о покрытии).

2. Какое покрытие множества называется неприводимым?

3. Какая ДНФ называется тупиковой (в геометрическом смысле)?

4. Сформулируйте теорему, для метода Блейка-Порецкого. Какие операции используются в этом методе?

Индивидуальные задания

9.1 Найдите минимальную ДНФ методом Блейка-Порецкого, если булева функция задана в виде:

1) F(A,B,C,D)=СDСВ  

2) F(A,B,C,D)= DС

3) F(A,B,C,D)= DC

4) F(A,B,C,D)= АСDС

5) F(A,B,C,D)= СDА

6) F(A,B,C,D)= DCDА

7) F(A,B,C,D)= DСС

8) F(A,B,C,D)= DСВ.

9) F(A,B,C,D)= САDС

10) F(A,B,C,D)= DСС

11) F(A,B,C,D)= DВС 

12) F(A,B,C,D)= СD

13) F(A,B,C,D)= (DСА

14) F(A,B,C,D)= АСD

15) F(A,B,C,D)= DСАD 

16) F(A,B,C,D)= СDСВ.

17) F(A,B,C,D)= D)С 

18) F(A,B,C,D)= АСDС

19) F(A,B,C,D)= DССА 

  1.  F(A,B,C,D)= АСD;

21)F(A,B,C,D)= DCDА

22) F(A,B,C,D)= DСС

23) F(A,B,C,D)= DСВ.

24) F(A,B,C,D)= САDС

25) F(A,B,C,D)= DСС

26) F(A,B,C,D)= DВС 

27) F(A,B,C,D)= СD

28) F(A,B,C,D)= (DСА

29) F(A,B,C,D)= АСD

30) F(A,B,C,D)= DСАD.

9.2 Определите МДНФ и МКНФ булевой функции с помощью геометрического метода.

1) СD 11) DС   21) СD 

2) СD 12) DС     22) СD

3) DС 13) СD      23) DС

4) СD 14) DС   24) )DС

5) DС 15) DС       25) СD

6) СD 16) DС       26) DС

7) СDС 17) СD       27) СD

8) СD  18) DС    28) СD

9) С 19) DС     29) СD 

10) СD 20) DС;    30) СD.


 

А также другие работы, которые могут Вас заинтересовать

26383. Наружные половые органы самцов 21.5 KB
  Сливаясь образуют корень пениса radix penis а он продолжается в длинное тело. Заканчивается головкой glans penis в области которой имеется мочеполовой отросток или отверстие. У плотоядных здесь – кость os penis.
26384. Автономная (вегетативная) нервная система 20 KB
  Обеспечивает растительные функции организма пищеварение дыхание мочевыделение размножение. Осуществляет метаболическое осуществление соматической функции прежде всего двигательные функции.
26385. Автоподий грудной конечности, запястный и пальцевый суставы 24 KB
  Мышцы действующие на эти суставы сосредоточены в области предплечья: с латерокраниальной стороны экстензоры запястье: лучевой разгибатель запястья extensor carpi radialis длинный абдуктор большого пальца пальцы: общий разгибатель пальцев extensor digitorum communis латеральный разгибатель пальцев с каудомедиальной – флексоры запястье: локтевой разгибатель запястья локтевой сгибатель запястья лучевой сгобатель запястья; пальцы: поверхностный сгибатель пальцев глубокий сгибатель пальца.
26386. Автоподий тазовой конечности, заплюсневый и пальцевые суставы 24 KB
  Автоподий участвует в образовании следующих суставов: заплюсневого скакательного сложного одноосного блоковидного у лошадей и собак винтообразный; пальцевых простые одноосные блоковидные. Связки: заплюсны: боковые медиальные и латеральные длинная и короткая длинная плантарная межрядовые межкостные; пальцев: боковая латеральная и медиальная связки сесамовидных костей. Мышцы действующие на эти суставы сконцентрированы в области голени: краниолатерально флексоры скакательного сустава краниальная большеберцовая малоберцовая...
26387. Анализатор: анатомический состав 21 KB
  – ветви глазничной. Иннервация: 1 нервы расположенные по поверхности мышц глазного яблока: слёзный и лобный нервы от глазничной ветви тройничного скуловой от в челюстной ветви тройничного блоковый н. 4 пара; 2 под мышцами глазного яблока: 3 пара – глазодвигательный 4 – отводящий носоресничный от глазничной ветви тройничного 2 – зрительный.
26388. Анатомия как наука 20.5 KB
  Как наука она вскрывает закономерности строения организма животных обусловленные функцией и факторами окружающей внешней среды.
26389. БРЮШНАЯ ПОЛОСТЬ (cavum abdominis) и паховый канал 24.5 KB
  В этой области выделяют область мечевидного хряща regio xiphoidea и два подреберья regio hypochondrica dextra et sinistra. Чревная область mesogastrium от реберной дуги до маклока tuber coxae В ней выделяют пупочную область regio umbilicalis и два подвздоха regio iliaca dextra et sinistra. Здесь выделяют лонную область regio pubica и два паха regio inguinalis dextra et sinistra. На латеральной поверхности живота различают поясничную область regio lumbalis или почечную regio renalis и бедренную область regio femoralis.
26390. Виды соединения костей 21.5 KB
  Костные синостозы кости черепа таза эпифиз и диафиз трубчатой кости у взрослых. Компоненты сустава: сочленяющиеся кости покрытые гиалиновым хрящём суставная сумка капсула суставная полость заполненная синовиальной жидкостью.
26391. Волосы (pili) 20.5 KB
  Есть подниматель волоса из гладкой мышцы m. Стержень: сердцевина определяет толщину волоса отсутствует в пуховых волосах корковое вещество определяет прочность упругость растяжимость и гибкость волоса содержит пигмент и кутикула – чешуйчатый слой защищает от влаги микрофлоры определяет рисунок волоса.