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

Размещено на http://www.allbest.ru/

25

Содержание

1. Булевы функции. Суперпозиции

2. Булевы функции и теория множеств

3. Нормальные формы и полиномы

4. Классы Поста

5. Минимизация нормальных форм всюду определённых булевых функций

Список используемой литературы



1. Булевы функции. Суперпозиции

Переменная Х_i называется существенной переменной функции f , если существует хотя бы одна пара u, v наборов значений переменных соседних по i -той переменной, такая, что

f(u) ? f(v).

Переменная Х_i называется фиктивной переменной функции f , если для любых наборов u, v соседних по i -той переменной

f(u) = f(v).

Суперпозицией функций f₁, f₂, …, f_n называется функция, полученная с помощью подстановок этих функций друг в друга на места переменных, а также с помощью переименования переменных. Выражение, описывающее суперпозицию называется формулой.

1.1 Задание №1

Построить таблицу данной булевой функции

x	у	z
0	0	0	1	0	0	0
0	0	1	1	0	0	0
0	1	0	0	1	1	0
0	1	1	1	0	0	1
1	0	0	1	0	1	1
1	0	1	1	0	1	1
1	1	0	0	1	1	0
1	1	1	1	0	1	0



Исходная формула задаёт булеву функцию f(x,y,z), имеющую вектор значений (0001 1100).

1.2 Задание №2

Написать таблицу функции h(x, у), являющейся суперпозицией функций, если f₂ = (0110 1011) и f₃ = (0110 1011). h(x, у) = f₃ (x, f₂(y,x,y), y) Запишем таблицу функций f₁ и f₂

X	y	z	f2	f3
0	0	0	0	1
0	0	1	1	1
0	1	0	1	1
0	1	1	0	0
1	0	0	1	0
1	0	1	0	1
1	1	0	1	1
1	1	1	1	0

Составим таблицу функции h(x,у). Для этого запишем формулу, задающую функцию h(x,у), выпишем под символами переменных все наборы значений, которые эти переменные принимают, а под символами булевых функций будем выписывать значения функций, соответствующие этим наборам.

xy	x	Y	x	f2		xy	x	f2	Y	f1		x	y	H
00	0	0	0	0		00	0	0	0	1		0	0	1
01	0	1	0	1		01	0	1	1	1		0	1	1
10	1	0	1	0		10	1	0	0	1		1	0	1
11	1	1	1	1		11	1	1	1	0		1	1	0

Итак , h(x,у) = (1110).



1.3 Задание №3

Для данной функции f(x, у, z) = (1010 0000)

Выяснить, какие её переменные являются существенными, а какие -- фиктивными.

Выразить f(x, у, z) формулой, содержащей только существенные переменные.

x	y	Z	F
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	0

Переменная x является существенной для данной булевой функции, так как, например, наборы (0,0,0) и (1,0,0) являются соседними по переменной x и f (0,0,0) ? f (1,0,0)

Переменная z является существенной для данной булевой функции, так как, например, наборы (0,0,0) и (0,0,1) являются соседними по переменной z и f (0,0,0) ? f (0,0,1)

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

f (0,0,0) = f (0,1,0), f (1,0,0) = f (1,1,0),

f (0,0,1) = f (0,1,1), f (1,0,1) = f (1,1,1).

Выпишем таблицу функции f, как функцию только от существенных переменных



x	Z	F
0	0	1
0	1	0
1	0	0
1	1	0

1.4 Задание №4

1. Написать таблицу булевой функции f(x,y,z), заданной формулой.

2. Найти фиктивные переменные данной функции.

3. Преобразовать данную формулу в эквивалентную ей, но не содержащую фиктивных переменных.

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

x	y	z	x	y	z							f
0	0	0	1	1	1	0	0	0	0	0	1	1
0	0	1	1	1	0	1	0	0	0	1	0	1
0	1	0	1	0	1	0	1	0	1	1	0	1
0	1	1	1	0	0	0	0	0	1	1	0	1
1	0	0	0	1	1	0	0	1	0	1	0	1
1	0	1	0	1	0	1	0	0	0	1	0	1
1	1	0	0	0	1	0	0	0	0	1	0	0
1	1	1	0	0	0	0	0	0	0	1	0	0

Рассмотрим пары наборов, соседних по переменной z, и значения функции на этих наборах:

f (0,0,0) = f (0,0,1), f (1,0,0) = f (1,0,1),

f (0,1,0) = f (0,1,1), f (1,1,0) = f (1,1,1)

Значит, z -- фиктивная переменная.

Так как f (0,0,0) ? f (1,0,0) , значит x - существенная переменная.

Неравенство f (0,0,0) ? f (0,1,0) показывает, что y так же существенная переменная.

3. Преобразуем формулу к виду, не содержащему фиктивной переменной.



2. Булевы функции и теория множеств

2.1 Задание №1

Выяснить взаимное расположение множеств D, E, F, если А, В, С -- произвольные подмножества универсального множества U.

D
E
F

Найдём соответствующие булевы функции: f(D), f(E), f(F)

a	b	c	f(E)				f(D)				f(F)
0	0	0	1	0	0	1	1	0	0	1	1
0	0	1	0	0	0	0	0	0	0	0	0
0	1	0	1	0	0	1	1	1	0	0	1
0	1	1	1	1	0	0	1	1	0	0	1
1	0	0	1	0	1	0	1	1	0	1	1
1	0	1	1	0	1	0	1	1	1	0	1
1	1	0	1	0	0	0	0	0	0	0	0
1	1	1	1	1	0	0	1	0	1	0	1

f(D) = (1011 1101)

f(E) = (1011 1111)

f(F) = (1011 1101)

Так как f(F)? f(D) то D=F. Заметим , что f_E ? f_F , и построив таблицу, можем убедиться, что f_D > f_E ? 1. Значит справедливы соотношения: F = D E.

2.2 Задание №2

Проверить, что для любых множеств А, В, С выполнение включения ? влечёт выполнение включения ?.



?	?

Составим булеву функцию, соответствующую высказыванию, которое надо доказать:

a	b	c						f
0	0	0	0	1	0	0	1	1
0	0	1	0	1	0	1	1	1
0	1	0	0	1	1	1	1	1
0	1	1	0	1	1	1	1	1
1	0	0	0	1	0	0	1	1
1	0	1	0	1	0	1	1	1
1	1	0	1	0	0	0	0	1
1	1	1	1	1	0	1	1	1

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

2.3 Задание №3

Для произвольных множеств А, В, Н проверить, является ли выполнение включения ? необходимым и достаточным условием выполнения равенства ?.

?	?

Составим булеву функцию, соответствующую высказыванию, которое надо доказать: f(a, b, h) =

Построим таблицу



a	b	h								f
0	0	0	0	1	0	0	0	0	0	1
0	0	1	0	1	0	0	0	0	0	1
0	1	0	1	1	1	1	1	1	1	1
0	1	1	0	1	1	0	1	1	1	1
1	0	0	0	0	1	0	0	0	0	1
1	0	1	0	0	1	0	0	0	0	1
1	1	0	1	1	1	1	0	1	1	1
1	1	1	0	0	1	0	0	0	0	1

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

2.4 Задание №4

Выяснить, верно ли равенство ? для произвольных А, В, С.

?

Составим булеву функцию, соответствующую высказыванию

a	b	c					f
0	0	0	0	0	0	0	1
0	0	1	0	0	0	0	1
0	1	0	0	0	0	0	1
0	1	1	0	0	0	0	1
1	0	0	0	0	0	0	1
1	0	1	1	0	1	1	1
1	1	0	1	1	0	1	1
1	1	1	1	1	0	1	1

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



3. Нормальные формы и полиномы

Формула вида

в которой ?_i - параметры, принимающие значения 0 либо 1, а среди переменных x_i могут быть совпадающие, называется элементарной конъюнкцией (ЭК).

Любая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).

Для любой булевой функции, отличной от тождественно ложной, существует единственное её представление в виде

,

которое называется её совершенной дизъюнктивной нормальной формой (СДНФ).

Формула вида

,

в которой ?_i- параметры, принимающие значения 0 либо 1 , а среди переменных x_i могут быть совпадающие, называется элементарной дизъюнкцией (ЭД).

Любая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ).

Для любой булевой функции, отличной от тождественно истинной, существует единственное её представление в виде

которое называется её совершенной конъюнктивной нормальной формой (СКНФ).

Алгоритм (перехода к ДНФ (КНФ)). Для этого необходимо:

Выразить формулу через отрицание, конъюнкцию и дизъюнкцию.

Пользуясь законами де Моргана, перейти к формуле с тесными отрицаниями, т.е. содержащей отрицание не выше, чем над переменными (пропустить отрицание внутрь формулы).

Пользуясь дистрибутивными законами, сделать дизъюнкцию внешней операцией (или конъюнкцию для КНФ).

Представление булевой функции в виде суммы по модулю 2 некоторых элементарных конъюнкций, констант называется е арифметическим полиномом (полиномом по модулю 2).

Представление булевой функции f(x₁, x₂,…, x_n) в виде

суммы по модулю 2 некоторых правильных элементарных конъюнкций и, быть может, константы 1 называется е полиномом Жегалкина.

3.1 Задание №1

Преобразовать f(x₁,x₂,x₃,x₄), используя формулу дизъюнктивного разложения по совокупности переменных х₂, x₃ представляя получаемые функции от двух переменных формулами над множеством элементарных связок: отрицание, конъюнкция, дизъюнкция, импликация, сумма по модулю два, эквиваленция, запрет, штрих Шеффера, стрелка Пирса.

f(x₁,x₂,x₃,x₄)= (0110 1110 1101 1001)

Запишем таблицу функции f(x₁,x₂,x₃,x₄) и с её помощью составим таблицы всех четырёх функций от переменных х₂, x₃.

x1	x2	x3	x4	f
0	0	0	0	0
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	1
0	1	0	1	1
0	1	1	0	1
0	1	1	1	0
1	0	0	0	1
1	0	0	1	1
1	0	1	0	0
1	0	1	1	1
1	1	0	0	1
1	1	0	1	0
1	1	1	0	0
1	1	1	1	1

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

3.2 Задание №2

Найти двумя способами полином функции, заданной векторно.

Найти СДНФ.

СКНФ данной функции.

f(x, y, z) = (0111 1001)

Запишем таблицу данной функции в развёрнутом виде

X	y	z	F
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

x	y	z	f
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Способ 1. Найдём полином Жегалкина данной функции, исходя из формулы:

Применим метод неопределённых коэффициентов. Будем искать полином для данной функции в виде:

f(x, у, z) = а₀ ? а₁х ? а₂у ? a₃z ? а₄ху ? a₅xz ? a₆yz ? a₇xyz. (*)

Используя таблицу функции, будем подставлять наборы значений переменных и значения функции в соотношение (*) и последовательно находить неопределённые коэффициенты а_i:

f(0, 0, 0)= а₀ ? а₁·0 ? а₂·0? a₃·0? а₄·0? a₅·0? a₆·0? a₇·0 = 1

а₀ = 1

f(0, 0, 1)= а₀ ? а₃ => а₃ =1

f(0, 1, 0) = а₀ ? а₂ => а₂ =1

f(1, 0, 0) = а₀ ? а₁ => а₁ =1

f(0, 1, 1) = а₀ ? а₂ ? а₃ ? а₆ => а₆ =1

f(1, 0, 1) = а₀ ? а₁ ? а₃ ? a₅ => а₅ =1

f(1, 1, 0) = а₀ ? а₁ ? а₂ ? а₄ => а₄ =1

f(1, 1, 1) = а₀ ? а₁ ? а₂ ? а₃ ? а₄ ? a₅ ? а₆ ? a₇ => а₇ =1

Получили, что

f(x, у, z) = 1 ? 1·х ? 1·у ? 1·z ? 1·ху ? 1·xz ? 1·yz ? 1·xyz =

1 ? x ? y ? z ? ху ? xz ? yz ? xyz.

4. Классы Поста

Любая совокупность М булевых функций, замкнутая относительно суперпозиции (суперпозиция функции из М снова принадлежит М) называется функционально замкнутым классом (ФЗК).

Пусть

f Р₂(п).

Говорят, что эта функция сохраняет ноль, если f(0,0,. . . ,0) = 0 .

Мощность множества Т₀(п) определяется по формуле

эта функция сохраняет единицу, если f(1,1,. . . ,1) = 1 .

Мощность множества Т₁(п) определяется по формуле



Говорят, что эта функция самодвойственна, если

Мощность множества S(n) определяется по формуле

Пусть f Р₂(п). Говорят, что эта функция монотонна, если для любых наборов значений переменных (?₁, ?₂,…, ?n)и (?₁, ?₂,…, ?_n) таких, что, выполняется неравенство

Пусть f Р₂(п). Говорят, что эта функция линейна, если её полином Жегалкина не содержит произведений переменных (т.е. если коэффициенты при слагаемых, содержащих произведения переменных, равны нулю)

Мощность множества L(n) определяется по формуле

|L(n)| = 2ⁿ⁺¹.

Для того, чтобы множество (система функций) М было полным, необходимо и достаточно, чтобы (выполнялось любое из трёх равносильных условий):

е условие: оно (это множество) не входило ни в один из классов Поста.

е условие: для каждого класса Поста среди функций из М нашлась функция, не принадлежащая этому классу (может быть одна на несколько классов).

е условие: нашлись такие функции из М , что в каждом столбце их таблицы Поста был бы хотя бы один минус.

4.1 Задание №1

Доопределить функции f(x,y,z), g(x,y,z), h(x,y,z) так, чтобы f M, gL, h S.

Если построение какой-либо функции невозможно, докажите это.

Выясните вопрос о принадлежности построенных функций к классам T₀ и T₁.

f(x,y,z)= (--0 -01-)

g(x,y,z)= (0-10 --1)

h(x,y,z)= (-10 -01)

Изобразим развёрнутую таблицу данных функций

x	y	Z	F	g	H
0	0	0	-	0	-
0	0	1	-	-	0
0	1	0	-	1	1
0	1	1	0	0	0
1	0	0	-	-	-
1	0	1	0	-	-
1	1	0	1	-	0
1	1	1	-	1	1

Доопределим функцию f, используя определение монотонной функции.

Так как f (1,0,1) = 0, то на всех наборах, предшествующих набору (1,0,1), функция тоже должна равняться 0, т. е. f (0, 0, 1) = f (1, 1, 1) = 0.

Так как f (1,1,0) = 1, то на всех наборах, которым предшествует набор (0,0,1), функция f должна принять значение 0, т. е. f (0, 1, 0) = f(1,0,0)=1. По определению монотонной функции f(0,0,0)=0, f(1,1,1)=1.

Получаем: f (x, у, z) = (00101011).

Доопределим функцию g, учитывая, что она -- линейная. Общий вид линейной функции от переменных х, у, z имеет вид: g(x,y,z) = a₀ + a₁x + a₂y + a₃z.

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

Получим систему соотношений:

0 = a₀ + a₁·0 + a₂·0 + a₃·0

1 = a₀ + a₁·0 + a₂·1 + a₃·0

0 = a₀ + a₁·0 + a₂·1 + a₃·1

1 = a₀ + a₁·1 + a₂·1 + a₃·1

a₀ = 0

a₀ + a₂ = 1

a₂ = 1

a₂ + a₃ = 0

a₃ = 1

a₁ + a₀ +a₂ + a₃ = 1

a₁ = 1

Итак, g(x,y,z) = 0 + x +y + z = x + y + z

Исходя из этой формулы, найдём значения функции g на тех наборах, на которых она была не определена.

В итоге имеем: g(x,y,z) = (01101111).

Доопределим функцию h, используя определение самодвойственной функции. Так как наборы (0, 0, 0) и (1, 1, 1) противоположны и h(0, 0, 0) = 0 => h(1, 1, 1) = 1.

Противоположными парами наборов значений переменных являются также (0,0,1) и (1,1,0), (0,1,0) и (1,0,1), (0,1,1) и (1,0,0). Используя известные значения функции h , получим:

Итак, h (x,y,z)= (01101001)

Так как h (0,0,0) = g(0,0,0) = 0 ? f (0,0,0), то f T₀ , g T₀, hT₀.

Так как f (1,1,1) = 1 ? f (1,1,1) то f T₁, g T₁, hT₁

4.2 Задание №2

1. Можно ли из функции f(x,y,z) с помощью суперпозиций

2. получить g(x,y,z) ?

3. Верно ли, что f(x,y,z) [g]? ([g] -- замыкание класса {g})

f (x,y,z)= (0110 1111)

g(x,y,z) = (1010 0100)

Проверим f(x,y,z) на принадлежность к классам Поста

f (0,0,0) = 0 => f T_0; f (1,1,1) = 1 => f T₁;

(0, 0, 1) (1, 0, 1) и f (0, 0, 0) > f (1, 0, 1) => f M;

f (0,0,1)= f (1,1,0)=> f S

x	y	z	f
0	0	0	0
0	0	1	1	(x?1)(y?1)z
0	1	0	1	(x?1) y(z?1)
0	1	1	0
1	0	0	1	x(y?1)(z?1)
1	0	1	1	x(y?1)z
1	1	0	1	xy(z?1)
1	1	1	1	xyz

f (x,y,z)= (x?1)(y?1)z ? (x?1)y(z?1) ? x(y?1)(z?1) ? x(y?1)z ? xy(z?1) ? xyz = xyz ? xz ? yz ? z ? xyz ? xy ? zy ? y ? xyz ? xy ? xz ? x ? xyz ? xz ? xyz ? xy ? xyz = xy ? xz ? z ? y ?x

Так как в полиноме функции f присутствуют конъюнкции, то f L.

Итак, мы видим, что функция f(x,y,z) сохраняет ноль и сохраняет единицу, значит, система {f}функционально полна в слабом смысле, и с помощью суперпозиций из f нельзя получить любую булеву функцию.

Проверим функцию g(x, y,z) на принадлежность к классам Поста:

f (0,0,0) = 1 => f T_0; f (1,1,1) = 0 => f T₁;

(0, 0, 0) (1, 1, 1) и f (0, 0, 0) > f (1, 1, 1) => f M;

f (0,1,1)= f (1,0,0)=> f S

x	y	Z	g
0	0	0	1	(x?1)(y?1)(z?1)
0	0	1	0
0	1	0	1	(x?1) y(z?1)
0	1	1	0
1	0	0	0
1	0	1	1	x(y?1)z
1	1	0	1	xy(z?1)
1	1	1	0

f (x,y,z)= (x?1)(y?1)(z?1)? (x?1)y(z?1) ? x(y?1)z ? xy(z?1) = xyz ? xz ? yz ? z ? xy ? x ? y ? 1 ? xyz ? xy ? zy ? y ? xyz ? xz ? xyz ? xy = xy ? x ? z ? 1

Значит, g L. Так как g не принадлежит ни одному из классов Поста, то g - функционально полный класс = > так как f функционально сильный в слабом смысле класс, то f .

4.3 Задание № 3

Для функций f(x,y,z)w g(x,y,z)выяснить вопрос об их принадлежности к классам T₀, T₁, L, S, М. В случае, если некоторая функция представляет из себя функционально полный класс, выразить из неё с помощью суперпозиций константы 0,1, отрицание и конъюнкцию ху. В случае, если некоторая функция представляет из себя функционально полный в слабом смысле класс, выразить из неё с помощью суперпозиций и фиксирования переменных отрицание и конъюнкцию ху. Полученные результаты проверить с помощью построения таблиц.

f (x,y,z)= (0110 1001)

g(x,y,z) = (1101 0100)

Исследуем функцию f (x,y,z) на принадлежность к классам Поста: Построим развернутую таблицу функции f:

X	y	z	f
0	0	0	0
0	0	1	1	(x?1)(y?1)z
0	1	0	1	(x?1) y(z?1)
0	1	1	0
1	0	0	1	x(y?1)(z?1)
1	0	1	0
1	1	0	0
1	1	1	1	xyz

f(0,0,0)=0 => f T₀ .

Отсюда следует, что {f} не является функционально полным классом.

f(1,1,1)=1=> f T₁

Так как наборы (0,0,0) и (1,1,1) противоположны и f(0,0,0)=f(1,1,1) , аналогично и для остальных наборов (0,0,1) и (1,0,0), (0,1,1) и (1,0,0) и тд., то f

Так как (0,1,0) (0,1,1), но f(0,1,0) > f(0,1,1), значит, f M.

f(x,y,z)= (x?1)(y?1)z ? (x?1) y(z?1) ? x(y?1)(z?1) ? xyz =xyz ? xz ? yz ? z ? xyz ? xy ?yz ? y ? xyz ? y ? xz ? x ? xyz =xyz

Так как полином функции не содержит конъюнкцию, то L.

Так как f M, мы можем построить с помощью данной функции только отрицание. Для этого выразим из f отрицание с помощью фиксирования переменных. На соседних наборах (0,1,0) и (0,1,1) нарушается монотонность, рассмотрим функцию p(x) = f(0,1,x).

Найдем все значения функции p(x):

p(0) = f(0,1,0)=1 , p(1)=f(0,1,1)=0 => p(x)=x.

Отрицание построено.

Построим развернутую таблицу функции g:

X	y	z	g
0	0	0	1	(x?1)(y?1)(z?1)
0	0	1	1	(x?1)(y?1)z
0	1	0	0
0	1	1	1	(x?1)yz
1	0	0	0
1	0	1	1	x(y?1)z
1	1	0	0
1	1	1	0	xyz

g(0,0,0)=1 => g T₀ .

g(1,1,1)=0=> g T₁

Так как наборы (0,0,0) и (1,1,1) противоположны и g(0,0,0)=g(1,1,1) , аналогично и для остальных наборов (0,0,1) и (1,0,0), (0,1,1) и (1,0,0) и тд., то g

Так как (0,1,0) (0,1,1) и g(0,1,0) < g(0,1,1), аналогично и для остальных наборов значит, g M. Из этого следует, что {g} не является функционально полным классом.

g(x,y,z)= (x?1)(y?1)(z?1) ? (x?1)(y?1)z ? (x?1)yz ? x(y?1)z ? x(y?1)z

Так как полином функции содержит конъюнкцию, то L.

Из функции g невозможно получить отрицание и конъюнкцию.



5. Минимизация нормальных форм всюду определенных булевых функций

Элементарная конъюнкция Е называется импликантой булевой функции f, если Е > f ? 1. Импликанта Е называется простой, если при удалении любой буквы из неё она перестаёт быть импликантой булевой функции f.

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

Ядровая импликанта -- импликанта, удаление которой из ДНФ некоторой булевой функции / приводит к ДНФ, не равносильной f.

Минимальная ДНФ данной функции f -- ДНФ, имеющая наименьшее число символов переменных из всех ДНФ, задающих функцию f.

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

Сложностью ДНФ (КНФ) называется количество символов переменных, использованных в записи формулы.

Сокращённая ДНФ может быть получена из СДНФ последовательным применением, пока это возможно, формулы неполного склеивания Кu v Кu = Ku v Кu v К, а затем -- формулы поглощения Ku v К = К.

5.1 Задание № 1

Для данной функции f(x,y,z,w), заданной векторно, проделать следующее:

1) Записать её СДНФ и СКНФ

2) Методом Квайна найти сокращенную ДНФ

3) Для сокращенной ДНФ построить матрицу Квайна, указать ядровые импликанты.

4) С помощью матрицы Квайна найти минимальную ДНФ, указать ее сложность.

5) Найти минимальную ДНФ данной функции с помощью карт Карнау, сравнить полученный результат с ДНФ, найденной в п.4.

f=(1101 0101 1101 1111)

1) Изобразим таблицу функции f(x,y,z,w)

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

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

0000	000_ _000	_00_	___1
0001 1000	00_1 0_01 _001 100_ 1_00	0__1 __01 _0_1 1_0_
0011 0101 1001 1100
0111 1011 1101 1110	0_11 _011 01_1 _101 10_1 1_01 110_ 11_0	__11 _1_1 1__1 11__
1111	_111 1_11 11_1 111_

1 полоса 2 полоса 3 полоса

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

3)Для получения из сокращенной ДНФ минимальной ДНФ изобразим следующую таблицу - матрицу Квайна. Ядровыми импликантами будут 1,4,5, так как для каждой из них найдется единичный набор, на котором она одна принимает значение 1.

№ простой импликанты	1	2	3	4	5
Простые импликанты Единичные наборы	yz	xw	xz	xy	w
0000	1
0001	1	1			1
0011		1			1
0101		1			1
0111		1			1
1000	1		1
1001	1		1		1
1011					1
1100			1	1
1101			1	1	1
1110				1
1111				1	1



4)Выбираем наименьшее число столбцов таких, чтобы для каждой строки из данной таблицы и хотя бы одной единицы в этой строке нашелся бы по крайней мере один столбец из множества выбранных столбцов, который содержит эту единицу. Тогда дизъюнкция членов, сопоставленных всем выбранным столбцам, является минимальной ДНФ.

Составляем символическое выражение:7

1 ? (1 v 2 v 5) ? (2 v 5) ? (2 v 5) ? (2 v5) ? (1 v 3) ? (1 v 3 v 5) ? 5 ? (3 v 4) ? (3 v 4 v 5) ? 4 ? (4 v 5) = 1 ? (2 v 5) ? (1 v 3) ? 5 ? (3 v 4) ? 4 ? (4 v 5) = 1 ? 5 ? 4 ? (4 v 5) = 1 ? 5 ? 4 = yz v xy vw

Минимальная ДНФ данной функции имеет сложность 6.

xy \ zw	00	01	11	10
00	1	1	1	0
01	0	1	1	1
11	1	1	1	1
10	1	1	1	0

Минимальная ДНФ, соответствующая этому покрытию, равна

yz v xy v w.

5.2 Задание № 2

булев функция множество полином

Для функций f(x,y,z), g(x,y,z,w), h(x,y,z,w,t) найти минимальные ДНФ и минимальные КНФ с помощью карт Карнау, указать сложности минимальных ДНФ.

f=(1010 1111), g=(1101 1100 1111 1101),

h=(1101 0011 1111 1101 1110 1101 0111 1100).

Карта Карнау для функции f (x,y,z) от трех переменных имеет такой вид:



Z xy	0	1
00	1	0
01	1	0
11	1	1
10	1	1

Для нахождения минимально ДНФ единицы карты Карнау покрываем прямоугольниками вида 2?2 и 1?4, отвечающим импликантам x и z соответственно.

Минимальная ДНФ: z v x

Ее сложность равна 2

Z Xy	0	1
00	1	0
01	1	0
11	1	1
10	1	1

Для нахождения минимальной КНФ покрываем нули карты Карнау одним прямоугольником размером 1?2.

Минимальная КНФ: z v x

Карта Карнау для g(x,y,z,w) примет следующий вид:

Zw xy	00	01	11	10
00	1	1	1	0
01	1	1	0	0
11	1	1	1	0
10	1	1	1	1

Минимальная ДНФ z v xy v wy v xw. Ее сложность равна 7.



Zw xy	00	01	11	10
00	1	1	1	0
01	1	1	0	0
11	1	1	1	0
10	1	1	1	1

Минимальная КНФ: (x v z v w)(y v z v w)(x v y v z)

Рассмотрим функцию h(x,y,z,w,t):

Карту Карнау для пяти переменных можно воспринимать, как «двухслойную карту Карнау для функции от 4 переменных, где верхний слой соответствует значениям x=0, а нижний x=1, причем клетки, образующие «двухслойный» прямоугольник, соответствуют импликантам, в которых переменная x отсутствует.

Wt xyz	00	01	11	10
000	1	1	1	0
001	0	0	1	1
011	1	1	1	0
010	1	1	1	1
100	1	1	0	1
101	1	1	1	0
111	1	1	0	0
110	0	1	1	1

Минимальная ДНФ:

Ее сложность равна:

Wt xyz	00	01	11	10
000	1	1	1	0
001	0	0	1	1
011	1	1	1	0
010	1	1	1	1
100	1	1	0	1
101	1	1	1	0
111	1	1	0	0
110	0	1	1	1



Список используемой литературы

1)Тишин В.В. Дискретная математика в примерах и задачах.-СПб.: БХВ-Петербург, 2008. 352 с.

2)Орлов Ю. Ф. Конспект лекций, 2012. 124 с.

3)Ерусалимский Я. М. Дискретная математика: теория, задачи, приложения. 3-е издание.-М.: Вузовская книга, 2000.-280с

Размещено на Allbest.ru