Выполнение

Выполнение домашнего задания рассмотрим на примере приведенного выше варианта основного задания.

Вариант хх

1. Проверить двумя способами эквивалентность формул

а) составлением таблиц истинности,

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

Дано: и .

Решение:

а) Составление и сравнение таблиц истинности.

Порядок действий здесь таков:

Преобразуем функции.

Составляем промежуточные таблицы истинности.

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

Сравниваем значения функций.

Преобразования функций:

, ,

, , .

В формулах по три переменные, поэтому в таблицах будет по восемь наборов. Расположим переменные в таком порядке: xyz, где x – старшая переменная.

Составление таблицы истинности для первой функции:

Таблица 37
№	x	y	z				ƒ1,1			ƒ1,1	ƒrez1

Составление таблицы истинности для второй функции:

Таблица 38

№

x

y

z

y

ƒ2,1

z

ƒ2,2

2,1

2,2

ƒrez2

Сравниваем ƒ_rez1 и ƒ_rez2. Как видим, функции не эквивалентны.

б) Приведение формул к СДНФ путем эквивалентных преобразований.

– ДНФ первой функции.

Получили СДНФ первой функции.

– ДНФ и СДНФ второй функции.

СДНФ функций не совпадают, следовательно, функции не эквивалентны.

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

Дана формула .

Решение:

Преобразуем:

Получили КНФ.

Раскрыв скобки, и приведя подобные члены, получим ДНФ:

Вместо недостающих переменных в термы ДНФ ставим 1, выполнив преобразования, получим СДНФ:

в термы КНФ вместо недостающих переменных ставим 0, выполнив преобразования, получим СКНФ:

Полином Жегалкина построим преобразованием ДНФ:

Результаты преобразований:

– КНФ,

– ДНФ,

– СДНФ,

– СКНФ,

– Полином Жегалкина.

3. С помощью карт Карно найти все минимальные ДНФ функции трех переменных ƒ(x,y,z).

Дано: .

Решение:

Функция задана нулевыми наборами {0, 1, 4, 6}, значит, на остальных наборах она имеет значения, равные 1.

Строим таблицу истинности:

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

Таблица 40
xy/ z
	0
			1

– минимальная ДНФ функции.

Других вариантов нет.

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

Дано:= (1110 1001 0111 0001),

где первый символ слева – значение функции при входном наборе 0000.

Решение:

Строим таблицу истинности:

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

Таблица 42
x1x2/ x3x4
	1			0
		1
	1			1

–минимальная ДНФ функции.

Здесь возможен и другой вариант (см. табл. 43)

Таблица 43
x1x2/ x3x4
	1
				1
		1		1
	1

По таблице 44 получаем минимальную КНФ функции

.

Других вариантов нет.

Таблица 44
x1x2/ x3x4
			0
	1
11
	1

5. Является ли полной система функций? Образует ли она минимальный базис?

Дана система функций .

Решение:

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

не сохраняет «0» f(0,0,…,0) ≠ 0;

не сохраняет «1» f(1,1,…,1) ≠ 1;

не является самодвойственной;

не является монотонной;

не является линейной.

Проверим:

1) Сохранение «0»

– сохраняет «0» (см. табл. 45),

– не сохраняет «0» (см. табл. 46).

2) Сохранение «1»

– не сохраняет «1» (см. табл. 45),

– сохраняет «1» (см. табл. 46).

3) Самодвойственность

Двойственная функция для равна . Так как , то не самодвойственная функция.

Для функции двойственная функция равна . Поскольку , то, следовательно, и f₂ не самодвойственна.

4) Монотонность

Функция не монотонна, так как не выполняется условие монотонности на наборах 2 и 3 (см. табл. 45).

Функция не монотонна, так как не выполняется условие монотонности на наборах 0 и 1, а также на наборах 0 и 2 (см. табл. 46).

5) Линейность

Для проверки этого свойства представим функции полиномами Жегалкина.

– не линейна,

– линейная функция.

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

Список литературы

1. Яблонский С. В. Введение в дискретную математику. – М.: Высшая школа, 2002. – 384 с.

2. Горбатов В. А. Фундаментальные основы дискретной математики. Информационная математика. – М.: Наука, Физматгиз, 2000. – 544 с.

3. Новиков Ф. А. Дискретная математика для программистов. – СПб.: Питер, 2002. – 304 с.

4. Судоплатов С. В., Овчинникова Е. В. Элементы дискретной математики: Учебник. – М.: ИНФРА–М, – Новосибирск: Издательство НГТУ, 2002. – 280 с.

5. Москинова Г. И. Дискретная математика. Математика для менеджера в примерах и упражнениях: Учебное пособие. – М.: Логос, 2003. – 240 с.

6. Схемотехника электронных систем. Цифровые устройства / В.И. Бойко, А.Н. Гуржий, В.Я. Жуйков и др. – СПб.: БХВ–Петербург, 2004. –512 с.

Учебное издание

Федоров Валентин николаевич