42424

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

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

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

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

Русский

2013-10-29

686 KB

144 чел.

Практическое занятие №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.


 

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

79682. Проблемы и препятствия на пути воздействия на трудовую мотивацию персонала. Пути совершенствования мотивации труда 324.5 KB
  Государственное управление заключает в себе огромный материальный и человеческий риск. Это прежде всего высокие затраты, опасность ущемления общественного благосостояния, и, вызванная последним, низкая репутация чиновничества и государства в целом в глазах общественности.
79683. Факторы формирования чувства преданности организации 153.5 KB
  Определение понятия преданность организации. Психологические механизмы лежащие в основе чувства преданности организации. Приверженность организации и самочувствие.
79684. Формирование кадровой политики предприятия связи ОАО Липеком 739.5 KB
  Практика управления предприятием связи Липеком. Кадры управления менеджеры и их роль в процессе деятельности предприятия. Общая характеристика управления кадрами. Статья приложения структуры управления Липекома и статья приложения аудиторской проверки сканированы и отпечатаны с оригинала.
79685. Создание тренинга. Разработка программы тренинга 122 KB
  Разработка программы тренинга. С Заказчиком обсуждаются следующие вопросы: цели и задачи предстоящего тренинга Цели должны представлять направление на долгосрочную перспективу. Но можно по крайней мере оценить достаточно ли было упражнений на отработку навыков помогал ли тренер в процессе этих упражнений изучал ли тренер компанию и группу до тренинга и есть ли посттренинговое сопровождение.
79686. ПРИЧИНЫ ВОЗНИКНОВЕНИЯ БЕЗРАБОТИЦЫ. ВЛИЯНИЕ ЭКОНОМИКИ НА БЕЗРАБОТИЦУ 135 KB
  Закона о занятости населения в Российской Федерации Безработными признаются трудоспособные граждане которые не имеют работы и заработка зарегистрированы в органах службы занятости в целях поиска подходящей работы ищут работу и готовы приступить к ней. В Законе РФ О занятости населения в РФ определена политика государства в области занятости населения права граждан в области занятости а также вопросы регулирования организации занятости и создания государственной службы занятости населения. Международная Организация Труда...
79687. Деятельность кадрового подразделения организации 246.5 KB
  Любая организация существует только тогда, когда есть работающие в ней люди. Открытие какой угодно фирмы, предприятия, учреждения, организации начинается с подбора и оформления работников. Поэтому наличие службы кадров или специально выделенного сотрудника, занимающегося оформлением кадров, обязательно для организации не только любого масштаба, но и любой организационно-правовой формы.
79688. Обучение персонала как фактор повышения эффективности работы организации 785.5 KB
  Исследовать пути создания конкурентных преимуществ организации в рыночных условиях хозяйствования; обосновать важность человеческого ресурса как главного ресурса в организации; рассмотреть понятие кадрового потенциала и пути его повышения; рассмотреть порядок организации работы по обучению персонала и систематизировать методы обучения...
79689. Планирование кадров предприятия и их подбор 233.5 KB
  Любая организация создается для выполнения каких-либо целей и нуждается в управлении, а от того насколько эффективно ею управляют, и зависит достижение поставленных задач. Найти правильные методы налаживания связей между целями организации и людьми, которые их выполняют должен руководитель
79690. Презентационные и коммуникативные навыки тренинг-менеджера 177 KB
  Обычно выделяют четыре основные цели презентации в отношении других людей: сообщить информацию; научить; создать мотивацию; развлечь. Сообщить информацию значит дать другим людям полное представление о том что является предметом презентации.