БУЛЕВЫ ФУНКЦИИ ОДНОЙ И ДВУХ ПЕРЕМЕННЫХ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «КРЫМСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ИМЕНИ В.И. ВЕРНАДСКОГО»

ГУМАНИТАРНО-ПЕДАГОГИЧЕСКАЯ АКАДЕМИЯ (ФИЛИАЛ) в г. ЯЛТЕ

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

ПО ВЫПОЛНЕНИЮ ПРАКТИЧЕСКИХ РАБОТ

ПРИ ИЗУЧЕНИИ ДИСЦИПЛИНЫ «ТЕОРИЯ АЛГОРИТМОВ»

(Модуль 1 «БУЛЕВА АЛГЕБРА, АЛГЕБРЫ ЛОГИКИ И ЖЕГАЛКИНА»)

направления подготовки 09.03.03 «Прикладная информатика»

профиля подготовки «Прикладная информатика в менеджменте»

Ялта 2016

УДК 510.5/.6 (07)

ББК 22.12Я73

М 54

Утверждено на заседании ученого совета Гуманитарно-педагогической академии (филиал) ФГАОУ ВО «Крымский федеральный университет им. В.И. Вернадского» в г. Ялте от 8 июня 2016 года (протокол № 7)

Методические рекомендации по выполнению практических работ при изучении дисциплины «Теория алгоритмов» (модуль 1 «Булева алгебра, алгебры логики и Жегалкина») направления подготовки 09.03.03 «Прикладная информатика» профиля подготовки «Прикладная информатика в менеджменте» / сост. М.В. Остапович, П.В. Хмара. Ялта: РИО ГПА, 2016. 64 с.

Настоящие методические рекомендации содержат основные теоретические сведения модуля «Булева алгебра, алгебры логики и Жегалкина» дисциплины «Теория алгоритмов», методические материалы для выполнения практических работ, примеры их выполнения и задания для самостоятельной работы. Методические рекомендации предназначены для студентов направления подготовки 09.03.03 «Прикладная информатика».

Рецензенты:

Маковейчук К.А., кандидат экономических наук, доцент;

Линник Е.П., кандидат физико-математических наук.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ. 5

1. ЛОГИЧЕСКИЕ ПЕРЕМЕННЫЕ И ОПЕРАЦИИ.. 6

2. БУЛЕВЫ ФУНКЦИИ.. 8

3. БУЛЕВЫ ФУНКЦИИ ОДНОЙ И ДВУХ ПЕРЕМЕННЫХ.. 10

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 1. 12

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ.. 13

4. СИСТЕМЫ БАЗОВЫХ (ЭЛЕМЕНТАРНЫХ) ОПЕРАЦИЙ.. 16

5. БУЛЕВЫ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ.. 19

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 2. 20

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ.. 20

6. БУЛЕВА АЛГЕБРА. АЛГЕБРА ЛОГИКИ.. 22

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 3. 24

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ.. 25

7. АЛГЕБРА ЖЕГАЛКИНА.. 25

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 4. 27

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ.. 28

8. ДИЗЬЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ 28

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 5. 31

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ.. 32

9. СОВЕРШЕННАЯ ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА БУЛЕВОЙ ФУНКЦИИ.. 32

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 6. 35

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ.. 36

10. КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ 37

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 7. 39

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ.. 40

11. СОВЕРШЕННАЯ КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА БУЛЕВЫХ ФУНКЦИЙ.. 41

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 8. 44

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ.. 45

12. ПРИНЦИП ДВОЙСТВЕННОСТИ. ДВОЙСТВЕННОСТЬ БУЛЕВЫХ ФУНКЦИЙ 46

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 9. 49

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ.. 50

13. ПОЛИНОМ ЖЕГАЛКИНА, ЛИНЕЙНЫЕ ФУНКЦИИ.. 50

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 10. 53

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ.. 54

14. ФУНКЦИИ, СОХРАНЯЮЩИЕ 0, ФУНКЦИИ, СОХРАНЯЮЩИЕ 1, МОНОТОННЫЕ ФУНКЦИИ.. 55

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 11. 57

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ.. 57

15. КЛАССЫ ПОСТА. ТЕОРЕМА ПОСТА.. 58

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 12. 60

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ.. 61

ЛИТЕРАТУРА.. 63

ВВЕДЕНИЕ

Математическая логика и теория алгоритмов возникла почти 100 лет назад в связи с внутренними потребностями математики. Но со временем она нашла применение также в теоретическом и практическом программировании и сегодня помогает преодолеть недостатки естественных языков – их неточность, многозначность и сложность.

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

В данных методических указаниях представлены основные теоретические сведения двухэлементной булевой алгебры, алгебры логики и алгебры Жегалкина, которые составляют первый модуль дисциплины «Теория алгоритмов» и которые необходимы для решения практических задач, примеры решений этих задач, задания для самостоятельного решения, что должно способствовать приобретению обучающимися соответствующих умений и навыков.

1. ЛОГИЧЕСКИЕ ПЕРЕМЕННЫЕ И ОПЕРАЦИИ

Пусть множество . Элементы этого множества называются логическими значениями, а переменные, которые могут принимать логические значения логическими переменными.

На множестве можно определить следующие логические операции.

0-арные (нольместные)операции:

– константа 0; (1.0)

– константа 1. (1.1)

1-арные (одноместные) операции:

– повторение

(1.2)

– отрицание

(1.3)

2-арные (двухместные) операции:

– конъюнкция

(1.4)

– импликация

; (1.5)

– отрицание импликации

; (1.6)

– сложение по модулю 2

; (1.7)

– дизъюнкция

; (1.8)

– стрелка Пирса

; (1.9)

– эквивалентность

; (1.10)

– штрих Шиффера

; (1.11)

Выражения 0, 1, , , , , , , , , называются простейшими логическими выражениями (формулами).

С помощью операции суперпозиции из простейших логических формул можно построить сложные логические формулы. Операция суперпозиции заключается в замене переменных логического выражения другими формулами.

/* Пример 1.1¹

Если в простейшую формулу

подставить

,

,

то получим сложную логическую формулу

.

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

. */

2. БУЛЕВЫ ФУНКЦИИ

Функция называется булевой, если она при любом значении аргумента принимает значения 0 или 1:

, ( ).

Область определения логической функции

( раз).

Элементы этого множества – кортежи (n-ки) , которые в математической логике называются словами и обозначаются строкой символов

или столбцом символов

.

Количество слов конечно и равно .

/* Пример 2.1

При:

существуют два слова: 0, 1;

четыре слова: 00, 01, 10, 11;

восемь слов: 000, 111, 001, 101, 010, 011, 100, 110. */

Каждому слову можно сопоставить целое число (номер слова)

. (2.1)

/* Пример 2.2

Номер слова 01 0101 равен

. */

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

/* Пример 2.3

При упорядоченное множество слов следующее: 000 (номер 0), 001(1), 010(2), 011(3), 100(4), 101(5), 110(6), 111(7). */

Область значений булевой функции

.

Количество булевых функций конечно и равно . Это количество быстро возрастает с увеличением n.

/*Пример 2.4

При:

существуют 4 булевы функции 1-ой переменной;

16функций 2-х переменных;

256функций 3-х переменных;

больше 4-х миллиардов функций 5-ти переменных.*/

Булевой функции n переменных можно сопоставить число (номер функции)

, (2.2)

где значение функции на слове с номером 0, на слове с номером 1 и т. д.

Номера функций n переменных устанавливают на их множестве идеальный строгий порядок:функция з меньшим номером предшествует функции с большим номером.

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

/*Пример 2.5

Таблица истинности функции , с учетом того, что , имеет вид

.

или в более короткой форме записи

,

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

БУЛЕВЫ ФУНКЦИИ ОДНОЙ И ДВУХ ПЕРЕМЕННЫХ

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

Функции одной переменной:

(3.1)

Функции двух переменных:

(3.2)

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

константа 0;

повторения аргумента;

отрицание аргумента,

константа 1;

константа 0;

конъюнкция;

отрицание импликации;

повторение аргумента ;

отрицание обратной импликации;

повторение аргумента ;

сложение по модулю 2;

дизъюнкция;

стрелка Пирса;

эквивалентность;

отрицание аргумента ;

обратная импликация;

отрицание аргумента ;

импликация;

штрих Шиффера;

константа 1.

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

/*Пример 3.1

,

. */

Любая булева функция многих переменных может быть представлена логическим выражением (формулой).

/*Пример 3.2

. */

Логическое выражение представляет одну булеву функцию. Обратное утверждение не верно. Любая логическая функция может быть представлена многими формулами (теоретически неограниченным количеством). Формулы, представляющие одну и ту же функцию, называются равносильными. Равносильные формулы соединяются знаком равенства (=).

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 1

Упражнение 1. Записать таблицу истинности булевой функции по ее номеру.

Выполнение. Заданная функция зависит от четырех аргументов. Количество слов . Номер функции . Дополняем его (номер) слева нулями до 16 (в соответствии количеству слов): .

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

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

Определить номер k этой функции.

Выполнение.

Упражнение 3. Определитьномер булевой функции

заданной логической формулой.

Выполнение.

В результате:

ВАРИАНТЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Вариант	k =	Таблица истинности функции
1.	= 234.
2.	= 214.		.
3.	= 227.
4.	= 134.
5.	= 124.
6.	= 119.		=
7.	= 89.
8.	= 95.
9.	= 108.
10.	= 117.		=
11.	= 146.
12.	= 158.
13.	= 128.		.
14.	= 185.		.
15.	= 194.
16.	= 137.		= .
17.	= 194.		.
18.	= 239.		.
19.	= 253.		=
20.	= 246.		=
21.	= 125.
22.	= 113.
23.	= 114.		=
24.	= 249.
25.	= 223.		= .

4. СИСТЕМЫ БАЗОВЫХ (ЭЛЕМЕНТАРНЫХ) ОПЕРАЦИЙ

Определение булевых функций двух переменных (3.2) дает возможность убедиться в справедливости следующих равенств

(4.1)

На основании этого можно записать следующие тождества:

(4.2)

; (4.3)

, ; (4.4)

, ; (4.5)

, ; (4.6)

, . (4.7)

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

Примером (одним из важнейших) систем элементарных операций есть

(4.8)

Эта система элементарных операций избыточна. Это следует из истинности равенств

, (4.9)

, (4.10)

Эти равенства доказываются с использованием таблицы истинности:

Из равенств (4.9) и (4.10) следует, что систему элементарных операций (4.8) можно сократить, например, к системе:

( (4.11)

Система элементарных операций (4.11) очень удобна и широко используется на практике. Она избыточна, так как

, (4.12)

, (4.13)

и поэтому ее можно сократить до

(4.14а)

или

. (4.14б)

Однако, и эти системы избыточны, если учесть тождества

, (4.15)

, (4.16)

. (4.17)

С этих формул следует, что системы (4.14а) и (4.14б) можно сократить до одной операции:

(4.18)

или

. (4.19)

Впрочем, особенного практического значения это не имеет.

При вычислениях значений формул с операциями (4.8) следует учитывать их приоритеты:

– отрицание ;

– конъюнкция ;

– дизъюнкция

– импликация

– эквивалентность

(сначала выполняются операции с меньшим номером в этом списке операции с большим приоритетом).

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

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

/*Пример 4.1.

Вычислить значение выражения

при , , , .

Выполнение:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. . */

5. БУЛЕВЫ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ

Булевы функции многих переменных ( ) обычно записываются в виде логических формул, содержащих n логических переменных. Эти формулы можно получить суперпозицией с формул с одной или двумя переменными. Таблица истинности для функций многих переменных вычисляется по определению логических операций (1.1.0 1.1.11).

/*Пример 5.1

Пусть задана функция двух переменных

.

Подставим

, ,

в выражение заданной функции и получим функцию трех переменных

.

Построим таблицу истинности этой функции.

. */

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 2

Упражнение 1. Вычислить значение выражения