Файл: Lektsii-po-DM-dlya-2-kursa_chast-2nov.pdf

6 

2.3. Методы построения сокращённых ДНФ. 

Метод Квайна-Мак-Класки

  представляет  собой  формализованный  на  этапе 

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

1.

Все конъюнкции (конституанты единицы) из СДНФ булевой функции f 
записываются их двоичными номерами (0 для переменной с отрицанием и 1 
– без отрицания).  

2.

Все номера разбиваются на непересекающиеся группы. Признак 
образования 

i

-й группы: 

i

 единиц в каждом двоичном номере конституенты 

единицы.  

3.

Склеивание производят только между номерами соседних групп, 
склеиваются номера, отличающиеся в одной позиции. В результате 
склеивания в этой позиции ставим “ * ”, которая не считается, как и ноль, 
при подсчёте номера группы для склеенного номера. Склеиваемые номера 
отмечаются каким-либо знаком (зачёркиванием).  

4.

Склеивания производят всевозможные. Неотмеченные после склеивания 
номера являются простыми импликантами.  

5.

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

Пример 2

.

 Пусть функция 

f

 задана таблицей истинности 

7 

Таблица истинности 

x

1

x

2

x

3

x4 

  f   

0000 
0001 
0010 
0011 
0100 
0101 
0110 
0111 
1000 
1001 
1010 
1011 
1100 
1101 
1110 
1111 

0 
1 
0 
1 
0 
1 
0 
1 
0 
0 
0 
0 
0 
0 
1 
1 

СДНФ функции 

f

 запишем в виде  

0001

0011

0101

0111 1110 1111











. 

Образуем группы двоичных номеров 

Таблица номеров 

Номер 
группы 

Двоичные номера 
конституент единицы 

              (1) 

              . . . 

              (2) 

              . . . 

              (3) 

0 

    — 

1 

0001

00 *1

, 

0 * 01

0 **1

2 

0011

, 

0101

0 *11

, 

01*1

3 

0111

, 

1110

*111,  111*

4 

1111

В результате получили тр простые импликанты *111, 111* и 

0 **1

. 

Строим импликантную матрицу по методу Квайна, 
 

Импликантная 

8 

таблица  

Простые 

импликанты 

Конституенты единицы в СДНФ 

f

0001  0011  0101  0111  1110  1111 

0**1 

X 

X 

X 

X 

*111 

X 

X 

111* 

Х 

Х 

 
по которой определяем  МДНФ  0**1 111*



 или  

1 4

1 2 3

x x

x x x



. 

Упражнение 2.3.1. 

Упражнение 2.3.2. 

Упражнение 2.3.3. 

С помощью алгоритма Квайна-Мак-Класки найти МДНФ. 

а)

б) 

9 

в) 

2.4. Введение в теорию графов . 

2.4.1. Основные определения и примеры. 

10 

Изоморфизм графов обладает свойствами: 

1.

рефлективности (любой граф изоморфен себе); 

2.

симметричности (если 

1

G

 изоморфен 

2

G

, то 

2

G

 изоморфен 

1

G

); 

3.

транзитивности (если 

1

G

 изоморфен 

2

G

 и 

2

G

 изоморфен 

3

G

, то 

1

G

 изоморфен 

3

G

).