русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Приведение к СКНФ. Алгоритм приведения.


Дата добавления: 2013-12-23; просмотров: 5252; Нарушение авторских прав


Рассматриваем только те строки таблицы, где формула принимает значение 0. Каждой такой строке соответствует дизъюнкция всех переменных (без повторений). Причем аргумент, принимающий значение 0, берется без отрицания, значение 1 – с отрицанием. Наконец, образуют конъюнкцию полученных дизъюнкций.

Пример 30.

Построить СКНФ для данных формул логики высказываний.

1. .

2.

Решение.

  1. Строим таблицу значений, используя предыдущий пример (табл. 15).

Таблица 15

x y z

Рассматриваем только наборы, на которых формула принимает значение ноль.

СКНФ (0): № 0, 1, 2, 3, 6:

  1. Строим таблицу значений, используя предыдущий пример (табл. 16).

Таблица 16

x y F=(x® y)ÙxÙy

СКНФ (0): № 0, 1, 2:

2.2. Булевы функции

2.2.1. Представление булевой функции формулой логики высказываний

Определение. Булевой функцией f(x1, x2, …, xn) называется n-местная функция, аргументы которой принимают значения во множестве {0, 1} и сама функция принимает значения в этом же множестве.

Всякую булеву функцию от n переменных можно задать таблицей из 2n строк, в которой в каждой строке записывают одну из оценок списка переменных, принимающих значение 0 или 1.

Пример 31.

Для n=3 булеву функцию можно задать таблицей 17.

Таблица 17

x1 x2 x3 f(x1, x2, x3)
f(0, 0, 0)
f(0, 0, 1)
f(0, 1, 0)
f(0, 1, 1)
f(1, 0, 0)
f(1, 0, 1)
f(1, 1, 0)
f(1, 1, 1)

 



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

Пример 32.

Пусть задана булева функция от трех переменных (табл. 18). Тогда число наборов .

Таблица 18

№ набора х1 х2 х3 f
0 0 0 0 0
1 0 0 1 0
2 0 1 0 1
3 0 1 1 0
4 1 0 0 1
5 1 0 1 1
6 1 1 0 0
7 1 1 1 1

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

Эту же функцию можно записать f(х1, х2, х3)=00101101.

Существует ровно различных булевых функций от n переменных. Константы 0 и 1 считают нуль-местными булевыми функциями.

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

Пример 33.

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

Решение.

Поскольку n=2, различных булевых функций от двух переменных существует ровно 16 (табл. 19).

Таблица 19

функции Значение функции Формула, соответствующая функции
1. 1 f=0000 f=0
2. 2 f=0001 f=x1Ùx2
3. 3 f=0010 f=
4. 4 f=0011 f=x1
5. 5 f=0100 f=
6. 6 f=0101 f=x2
7. 7 f=0110 f=x1Åx2
8. 8 f=0111 f=x1Úx2
9. 9 f=1000 f=
10. 10 f=1001 f=
11. 11 f=1010 f=
12. 12 f=1011 f=
13. 13 f=1100 f=
14. 14 f=1101 f=x1®x2
15. 15 f=1110 f=
16. 16 f=1111 f=1

 

Теорема. Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно нулю, то существует такая формула F, зависящая от списка переменных x1, x2, …, xn и находящаяся в СДНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки дизъюнктивных членов.

Теорема 2. Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно единице, то существует такая формула F, зависящая от списка переменных x1, x2, …, xk и находящаяся в СКНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки конъюнктивных членов.

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

Пример 34.

Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 00101110.

Решение.

Строим таблицу значений функции (табл. 20):

Таблица 20

x1 x2 x3 f(x1, x2, x3)

СКНФ (0): № 0, 1, 3, 7

СДНФ (1): № 2, 4, 5, 6

 

 

2.2.2. Минимизация нормальных форм

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

Определение. Минимальной ДНФ (МДНФ) функции f(x1, x2, …, xn) называется ДНФ, реализующая функцию f и содержащая минимальное число символов переменных по сравнению со всеми другими ДНФ, реализующими функцию f.

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

Каждый из рассмотренных ниже методов состоит из двух этапов:

· построение сокращенной ДНФ;

· построение матрицы покрытий. Построение МДНФ.

Определение. Если для всякого набора а = (а1, а2, …, an) значений переменных условие g(a) = 1 влечет f(a) = 1, то функция g называется частью функции f (или функция f накрывает функцию g). Если при этом для некоторого набора с = (с1, с2, …, сn)функция g(c)=1, то говорят, что функция g накрывает единицу функции f на наборе с (или что g накрывает конституенту единицы функции f).

Конституента единицы функции f есть часть функции f, накрывающая единственную единицу функции f.

Определение. Элементарная конъюнкция К называется импликантомфункции f, если для всякого набора а = (а1, а2, …, an) из 0 и 1 условие К(а)=1 влечет f(a)=1.

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

Всякий импликант функции f есть часть функции f.

Теорема. Всякая функция реализуется дизъюнкцией всех своих простых импликант.

Определение. Сокращенная ДНФ функции f есть дизъюнкция всех простых импликант функции f.

Утверждение. Всякая функция f реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.

Теорема (Куайна). Если в СДНФ функции f провести все операции неполного склеивания, а затем все операции поглощения и удаления дублирующих членов, то в результате получится сокращенная ДНФ функции f.

2.2.2.1. Алгоритм Куайна построения сокращенной ДНФ

1. Получить СДНФ функции.

2. Провести все операции неполного склеивания.

3. Провести все операции поглощения.

Пример 35.

Минимизировать функцию f=1111010010101111.

Решение.

1. Строим таблицу значения для данной функции (табл. 20). Строим СДНФ функции. При этом слагаемые нумеруем и записываем в столбец (табл. 21).

Таблица 20

x1 x2 x3 x4 f(x1, x2, x3, х4)

СДНФ (1): № 0, 1, 2, 3, 5, 8, 10, 12, 13, 14, 15.

Таблица 21

№ слагаемого слагаемое

 

2. Проводим все операции неполного склеивания.

Первый этап склеивания (табл. 22):

Таблица 22

Слагаемые Склеивание по Результат Новые слагаемые
1, 2 x4 1
1, 3 x3 2
1, 6 x1 3
2, 4 x3 4
2, 5 x2
3, 4 x4 6
3, 7 x1 7
5, 9 x1 8
6, 7 x3 9
6, 8 x2 10
7, 10 x2 11
8, 9 x4 12
8, 10 x3 13
9, 11 x3 14
10, 11 x4 15

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

Пронумеруем дизъюнктивные члены в полученной ДНФ в порядке их следования от 1 до 15 (табл. 23).

Второй этап склеивания:

Таблица 23

Слагаемые Склеивание по Результат
1, 6 x3
2, 4 x4
2, 9 x1
3, 7 x3
9, 13 x2
10, 11 x3
12, 15 x3
13, 14 x4

В процедуре склеивания на втором этапе не принимали участие слагаемые № 5, 8 с предыдущего шага, поэтому после второго этапа склеивания и последующих поглощений получаем, что

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

 

2.2.2.2. Построение сокращенной ДНФ в классе дизъюнктивных нормальных форм

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

Пусть булева функция задана таблицей истинности или СДНФ.

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

Шаг 1. Столбцы для аргументов, как обычно в таблицах истинности, заполняются всевозможными наборами 0 и 1. В столбцах для конъюнкций проставляются десятичные значения двоичных чисел, соответствующих наборам значений аргументов. Последний столбец заполняется соответственно значению функции.

Далее работа чередуется по строкам, по столбцам.

Шаг 2. Вычеркиваются строки, в которых функция обращается в нуль.

Шаг 3. В каждом столбце из сохранившихся чисел вычеркивают те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге.

Шаг 4. В сохранившихся строках выбирают «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводят их кружочками.

Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркивают все, кроме одного.

Шаг 6. С помощью оставшихся обведенных чисел образуют конъюнкции. Для этого переводят каждое число в двоичную систему. Переменную, которой соответствует 1, берут сомножителем без отрицания, которой соответствует 0 – с отрицанием.

Шаг 8. Составляют дизъюнкцию полученных конъюнкций. В результате получаем сокращенную ДНФ функции.

Пример 36.

Построить сокращенную ДНФ для функции f=11100101.

Решение.

1.Строим минимизационную карту (табл. 24):

Таблица 24

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)
1
1
1
0
0
1
0
1

 

2. Вычеркиваем строки, в которых функция обращается в нуль (табл. 25):

Таблица 25

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)
1
1
1
0
0
1
0
1

 

3. В каждом столбце из сохранившихся чисел вычеркиваем те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге (табл. 26):

Таблица 26

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)
1
1
1
0
0
1
0
1

 

4. В сохранившихся строках выбираем «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводим их (табл. 27):

Таблица 27

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)
1
1
1
0
0
1
0
1

 

5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркиваем все, кроме одного (табл. 28):

Таблица 28

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)
1
1
1
0
0
1
0
1

 

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

Сокращенная ДНФ имеет вид:

Пример 37.

Построить сокращенную ДНФ функции f=1111010010101111 с использованием минимизационной карты.

Решение.

Строим минимизационную карту (табл. 29) и пошагово выполняем алгоритм.

Шаг 1.

Таблица 29

x1 x2 x3 x4 x1x2 x1x3 x1x4 x2x3 x2x4 x3x4 x1x2x3 x1x2x4 x1x3x4 x2x3x4 x1x2x3x4 f
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Шаг 2. Вычеркиваем строки, в которых функция обращается в нуль (табл. 30):

Таблица 30

x1 x2 x3 x4 x1x2 x1x3 x1x4 x2x3 x2x4 x3x4 x1x2x3 x1x2x4 x1x3x4 x2x3x4 x1x2x3x4 f
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

 

Шаг 3. В каждом столбце из сохранившихся чисел вычеркиваем те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге (табл. 31):

Таблица 31

x1 x2 x3 x4 x1x2 x1x3 x1x4 x2x3 x2x4 x3x4 x1x2x3 x1x2x4 x1x3x4 x2x3x4 x1x2x3x4 f
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

 

Шаг 4. В сохранившихся строках выбираем «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводим их (табл. 32):

Таблица 32

x1 x2 x3 x4 x1x2 x1x3 x1x4 x2x3 x2x4 x3x4 x1x2x3 x1x2x4 x1x3x4 x2x3x4 x1x2x3x4 f
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркиваем все, кроме одного (табл. 33):

Таблица 33

x1 x2 x3 x4 x1x2 x1x3 x1x4 x2x3 x2x4 x3x4 x1x2x3 x1x2x4 x1x3x4 x2x3x4 x1x2x3x4 f
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Шаг 6. Сокращенная ДНФ имеет вид

 

 

2.2.2.3. Построение всех тупиковых ДНФ

Определение. Тупиковой ДНФ (ТДНФ) функции f называется такая ДНФ ее простых импликант, из которых нельзя выбросить ни одного импликанта, не изменив функции f.

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

Для получения МДНФ функции f необходимо построить все ТДНФ функции f и выбрать те из них, которые содержат минимальное число букв.

Алгоритм построения всех тупиковых ДНФ.

Пусть f(x1, x2, …, xn) есть булева функция.

Шаг 1. Построим СДНФ функции f и пусть P1, P2, …,Pn есть ее конституенты (единицы).

Шаг 2. Построим сокращенную ДНФ функции f и пусть К1, К2, …, Кm – ее простые импликанты.

Шаг 3. Построим матрицу покрытий простых импликант функции f ее коституентами единицы (табл. 34), полагая, что

Таблица 34

N P1 P2 Pj Pn
K1 a11 a12 a1j a1n
K2 a21 a22 a2j a2n
Ki ai1 ai2 aij ain
Km am1 am2 amj amn

 

Шаг 4. Для каждого столбца j (1 £ j £ n)найдем множество Ej всех тех номеров i строк, для которых aij=1. Пусть Составим выражение Назовем его решеточным выражением. Это выражение можно рассматривать как формулу, построенную в свободной дистрибутивной решетке с образующими 1, 2, …, m и с операциями конъюнкции и дизъюнкции.

Шаг 5. В выражении А раскроем скобки приведя выражение А к равносильному выражению , где перечислены все конъюнкции элементы ei1, ei2, …, ein которой взяты из скобок 1, 2, …, n соответственно в выражении А.

Шаг 6. В выражении В проведем все операции удаления дублирующих членов и все операции поглощения. В результате получим равносильное выражение С, представляющее собой дизъюнкцию элементарных конъюнкций.

Пример 38.

Построить все минимальные ДНФ для функции f=1111010010101111.

Решение.

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

Строим матрицу покрытий (табл. 35).

Таблица 35

Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 - - + + + +
2 0 0 - - + + + +
3 - 0 - 0 + + + +
4 1 - - 0 + + + +
5 0 - 0 1 + +
6 - 1 0 1 + +

 

Пошагово будем выбирать слагаемые, которые войдут в минимальную ДНФ. Если слагаемое нами выбрано, то мы помечаем конституенты единицы функции f, которые будут покрыты (по строке). При этом автоматически исключаем из рассмотрения конституенты единицы, которые уже покрыты, но относятся к другим слагаемым сокращенной ДНФ.

Шаг 1. Выбираем слагаемое 1 (табл. 36):

Таблица 36

Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 - -               + + + +
2 0 0 - - + + + +              
3 - 0 - 0 +   +     + +        
4 1 - - 0           + + +   +  
5 0 - 0 1   +     +            
6 - 1 0 1         +       +    

Шаг 2. Выбираем слагаемое 2 (табл. 37):

Таблица 37

Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 - -               + + + +
2 0 0 - - + + + +              
3 - 0 - 0 +   +     + +        
4 1 - - 0           + + +   +  
5 0 - 0 1   +     +            
6 - 1 0 1         +       +    

 

Шаг 3. Выбираем слагаемое 4 (табл. 38):

Таблица 38

Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 - -               + + + +
2 0 0 - - + + + +              
3 - 0 - 0 +   +     + +        
4 1 - - 0           + + +   +  
5 0 - 0 1   +     +            
6 - 1 0 1         +       +    

Шаг 4. Выбираем слагаемое 5 (табл. 39):

Таблица 39

Простые импликанты Конституенты единицы функции f
x1 x2 x3 x4 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
1 1 1 - -               + + + +
2 0 0 - - + + + +              
3 - 0 - 0 +   +     + +        
4 1 - - 0           + + +   +  
5 0 - 0 1   +     +            
6 - 1 0 1         +       +    

Поскольку все конституенты единицы покрыты, то одна из ТДНФ имеет вид

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

Все найденные ТДНФ являются минимальными ДНФ.

Пример 39.

Построить одну из МДНФ функции f=11100101.

Решение.

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

Строим матрицу покрытий (табл. 40):

Таблица 40

Простые импликанты Конституенты единицы функции f
x1 x2 x3 000 001 010 101 111
1 0 0 - + +      
2 0 - 0 +   +    
3 1 - 1       + +
4 - 0 1   +   +  

Шаг 1. Выбираем слагаемое 3 (табл. 41):

Таблица 41

Простые импликанты Конституенты единицы функции f
x1 x2 x3 000 001 010 101 111
1 0 0 - + +      
2 0 - 0 +   +    
3 1 - 1       + +
4 - 0 1   +   +  

Шаг 2. Выбираем слагаемое 2 (табл. 42):

Таблица 42

Простые импликанты Конституенты единицы функции f
x1 x2 x3 000 001 010 101 111
1 0 0 - + +      
2 0 - 0 +   +    
3 1 - 1       + +
4 - 0 1   +   +  

Шаг 3. Выбираем слагаемое 1(табл. 43):

Таблица 43

Простые импликанты Конституенты единицы функции f
x1 x2 x3 000 001 010 101 111
1 0 0 - + +      
2 0 - 0 +   +    
3 1 - 1       + +
4 - 0 1   +   +  

В результате получаем МДНФ:

 

 

2.2.2.4. Алгоритм минимизации функций в классе ДНФ

1. Строим СДНФ функции f.

2. Строим сокращенную ДНФ функции f.

3. С помощью матрицы покрытий и решеточного выражения строим все ТДНФ функции f.

4. Среди построенных ТДНФ выбираем все минимальные дизъюнктивные нормальные формы функции f.

Пример 40.

В классе нормальных форм минимизировать функцию f=01011110.

Решение.

Для построения сокращенной ДНФ используем алгоритм Куайна.

  1. Строим СДНФ для функции f. Таблица значений имеет вид (табл. 43):

Таблица 43

x1 x2 x3 f

СДНФ (1): № 1, 3, 4, 5, 6 (табл.44):

Таблица 44

№ слагаемого Слагаемое СДНФ

 

2. Проводим все операции неполного склеивания (табл. 45):

Таблица 45

Слагаемые Склеивание по Результат
1, 2 х2
1, 4 х1
3, 4 х3
3, 5 х2

Дальнейшее склеивание невозможно. Все слагаемые предыдущего шага участвовали в операции склеивания, поэтому сокращенная ДНФ имеет вид:

ÚÚÚ.

3. Строим матрицу покрытий (табл. 46).

Таблица 46

Простые импликанты Конституенты единицы функции f
x1 x2 x3 001 011 100 101 110
1 0 - 1 + +      
2 - 0 1 +     +  
3 1 0 -     + +  
4 1 - 0     +   +

 

Последовательно выбираем слагаемые: № 4, 1, 2 (табл. 47).

Таблица 47

Простые импликанты Конституенты единицы функции f
x1 x2 x3 001 011 100 101 110
1 0 - 1 + +      
2 - 0 1 +     +  
3 1 0 -     + +  
4 1 - 0     +   +

В результате МДНФ имеет вид: ÚÚ.

Пример 41.

Построить МДНФ функции f=11011011.

Решение.

Для построения сокращенной ДНФ используем минимизационную карту (табл. 48).

Шаг 1.

Таблица 48

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)
1
1
0
1
1
0
1
1

 

Шаг 2. Вычеркиваем строки, в которых функция обращается в нуль (табл. 49):

Таблица 49

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)
0 0 0 0 0 0 0 1
0 0 1 0 1 1 1 1
0 1 0 1 0 2 2 0
0 1 1 1 1 3 3 1
1 0 0 2 2 0 4 1
1 0 1 2 3 1 5 0
1 1 0 3 2 2 6 1
1 1 1 3 3 3 7 1

 

Шаг 3. В каждом столбце из сохранившихся чисел вычеркиваем те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге (табл. 50):

Таблица 50

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)

 

Шаг 4. В сохранившихся строках выбираем «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводим их (табл. 51):

Таблица 51

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)

 

Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркиваем все, кроме одного (табл. 52):

Таблица 52

x1 x2 x3 x1x2 x1x3 x2x3 x1x2x3 f(x1, x2, x3)

 

Шаг 6. Сокращенная ДНФ имеет вид:

Строим матрицу покрытий (табл. 53).

Таблица 53

Простые импликанты Конституенты единицы функции f
x1 x2 x3 000 001 011 100 110 111
1 0 0 - + +        
2 1 1 -         + +
3 0 - 1   + +      
4 1 - 0       + +  
5 - 0 0 +     +    
6 - 1 1     +     +

 

Последовательно выбираем слагаемые: № 1, 2, 5, 6 (табл. 54).

Таблица 54

Простые импликанты Конституенты единицы функции f
x1 x2 x3 000 001 011 100 110 111
1 0 0 - + +        
2 1 1 -         + +
3 0 - 1   + +      
4 1 - 0       + +  
5 - 0 0 +     +    
6 - 1 1     +     +

 

В результате МДНФ имеет вид:

 

2.2.3. Полные системы булевых функций

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

Пример 42.

Исходя из определения полной системы булевых функций, следует, что система {Ù, Ú, Ø} является полной, так как любая булева функция может быть представима в виде СДНФ и/либо СКНФ.

Дадим определение суперпозиции функций.

Определение. - конечная система булевых функций. Функция f называется суперпозицией ранга 1(или элементарной суперпозицией) функций f1, f2, …, fm, если f может быть получена одним из следующих способов:

  1. переименованием некоторой переменной xj какой-нибудь функции fi, т. е. f=fi(x1, …, xj-1, y, xj+1, …, xk1), где y может совпасть с любой переменной;
  2. подстановкой некоторой функции fl (1£ l m) вместо какой-либо переменной xj любой из функций fiÎK0, т. е. f=fi(x1, …, xj-1, fl(x1, x2, …, xk1), xj+1, ..., xki).

Определение. Суперпозиции ранга 1 образуют класс функций К1. Класс функций, получающихся из функций класса Кr-1 суперпозиций ранга r-1 с помощью элементарных суперпозиций, называется классом функцийKr суперпозиций ранга r. Суперпозициями функций из К0 называются функции, входящие в какой-либо из классов Kr.

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

Пример 43.

1. Четыре булевы функции одной переменной (f1 = 00, f2 = 11, f3 = 01, f4 = 10) образуют замкнутый класс.

2. Булевы функции f1 = x и образуют замкнутый класс.

Теорема. Класс T0={f | f(0, 0, …, 0)=0} функций, сохраняющих константу ноль на нулевом наборе, замкнут относительно суперпозиций.

Теорема. Класс T1={ f | f(1, 1, …, 1)=1} функций, сохраняющих константу один на единичном наборе замкнут относительно суперпозиций.

 



<== предыдущая лекция | следующая лекция ==>
Приведение к СДНФ. Алгоритм приведения. | Двойственные функции


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.058 сек.