Булева алгебра (стр. 1 )

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

Федеральное государственное бюджетное образовательное учреждение высшего

профессионального образования

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ

ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

ЮРГИНСКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ

Утверждаю Зам. директора ЮТИ ТПУ по УР _____________ «_____» ______________ 2012г.

БУЛЕВА АЛГЕБРА

Методические указания по дискретной математике для студентов очной, очно-заочной и заочной формы обучения всех направлений

Издательство

Юргинского технологического института (филиал)

Томского политехнического университета

2012

УДК 519.1

Булева алгебра: методические указания по дискретной математике для студентов очной, очно-заочной и заочной формы обучения всех направлений / Сост. . – Юрга: Изд-во Юргинского технологического института (филиала) Томского политехнического университета, 2012. – 44с.

Рецензент

кандидат физико-математических наук

доцент

Методические указания рассмотрены и рекомендованы к изданию методическим семинаром кафедры ЕНО ЮТИ ТПУ «20» марта 2012г.

Зав. кафедрой ЕНО

канд. пед. наук, доцент

 

СОДЕРЖАНИЕ

Предисловие………………………………….….…………...…………..4

1.  Введение в булеву алгебру ………………….……..………….….….5

2.  Булевы функции….………...………………..………..…………........6

3.  Существенные и фиктивные переменные…….……………....16

4.  Определение формулы……………………………….…………...…17

5.  Тождества булевой алгебры………………………….……...…...…19

6.  Получение эквивалентных формул………………….………......…20

7.  Дизъюнктивные и конъюнктивные нормальные формы….....……21

8.  Совершенная дизъюнктивная и совершенная конъюнктивная нормальная формы……………………………………………....…..22

9.  Минимизация булёвых функций с помощью карты Вейча…....…26

10.  Функциональная полнота системы булевых функций……….…..29

10.1. Полные системы…………………………………………….…….29

10.2. Понятие функциональной полноты……………..………….……29

10.3. Замкнутые классы булевых функций……………………………30

10.4. Пять замкнутых классов…………….……………..…..…….…….31

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

ПРЕДИСЛОВИЕ

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

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

1.  Введение в булеву алгебру

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

Базовым понятием булевой алгебры является понятие высказывания, под которым понимается любое утверждение, рассматриваемое только с точки зрения его истинности или ложности. В булевой алгебре не существует истинно-ложных или ложно-истинных высказываний. Высказывание можно рассматривать как логическую переменную, которая может принимать различные значения, например, высказывание “сегодня понедельник” будет истинным в понедельник и ложным во все остальные дни недели. Исчисление высказываний как раз и основано на том, что их можно рассматривать как двоичные переменные, которые могут принимать одно из двух своих значений. Примерами двоичных логических переменных являются разряды чисел, представленных в двоичной системе счисления; замкнутый или разомкнутый контакт; наличие или отсутствие тока в цепи; высокий или низкий потенциал в какой-либо точке схемы и т. п.

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

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

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

В дискретной математике в качестве области определения и в качестве области значения функции будет выступать одно множество Е2. Двоечка снизу обозначает размерность данного множества. В этом множестве будет всего два элемента 0 и 1. Итак дискретное множество Е2={0,1}.

Определение. Функция F(х1,х2,…,хn)- называется булевой, если значение её аргументов определены на множестве Е2, и значение самой функции определено на Е2.

Способы задания булевых функций

Способы задания булевых функций не отличаются от способов задания обычных функций анализа. К таковым способам задания стандартно относятся:
1)табличный;
2)графический;
3) аналитический.

Табличный способ задания

Пусть – булева функция n аргументов. Область определения данной функции можно рассматривать и как множество упорядоченных наборов (или векторов, или двоичных наборов) , на каждом из которых функция принимает одно из двух значений: . Количество таких наборов (x1,x2,…,xn), согласно правилу прямого произведения, равно

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

Таблица 1

№	x y z	w=f(x, y,z)
1	0 0 0
1	0 0 1
2	0 1 0
3	0 1 1
4	1 0 0
5	1 0 1
6	1 1 0
7	1 1 1

В качестве примера рассмотрим табличное представление булевой функции трех аргументов где Π{0,1}. Область определения функции – это множество двоичных наборов

D={(x, y,z), |  x, y,zΠ{0,1}}. Их число есть |D|==8, а количество таких функций равно . Значения функции удобно представить в виде табл. 1.3, где перечислены всевозможные наборы из нулей и единиц длины 3 и для каждого набора указано значение функции Π{0,1} на этом наборе.

В таблицах, аналогичных табл. 1 обычно употребляется расположение наборов, соответствующих порядку естественного роста двоичных чисел 0,1,…,в примере n=3.
Определение. Таблицы значений булевых функций, подобные табл. 1, называются таблицами истинности булевых функций. Название таблиц происходит от интерпретации значений 1 – истина (TRUE), 0 – ложь (FALSE).

Графический способ задания

Рассмотрим графическое представление булевой функции трех аргументов , заданной таблично (табл. 1). Заметим, что множество наборов области определения функции D={(x, y,z) , | x, y,z Î

{0,1}} является множеством координат точек вершин единичного трехмерного куба (рис. 1.2). Очевидный способ графического представления булевой функции – это отметить каким-то образом вершины куба, в которых функция принимает значение 1. Именно так на рис. 1.2 и сделано. В соответствии с таблицей значений (табл. 1) отмечены вершины, в которых булева функция равна 1.

Замечание. Очевидно, что область определения булевой функции n аргументов составляется из наборов координат точек вершин единичного n-мерного куба.

Аналитический способ задания

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

Функции одной переменной – функции, зависящие только от одного аргумента.

Первая функция const 1 (читается "константа один" или "тождественная единица"). В первом столбце мы указываем значения, которые может принимать переменная х, таких значений всего два 0 и 1. Во втором столбце указывается значение самой функции. Когда х=0, f(х)=1, когда x=1, f(x) также равно 1.

Определение. Тождественной единицей - называется, функция которая принимает значение единицы при любых значениях аргументов. Функция обозначается «1».

x	1
0	1
1	1

Определение. Тождественной нулем - называется функция, которая принимает значение нуля при любых значениях аргументов. Функция обозначается «0».

x	0
0	0
1	0

Определение. Тождественной функцией - называется функция, которая принимает значения равные значению аргумента. Функция обозначается «х».

x	х
0	0
1	1

Определение. Инверсия - функция принимающая значения противоположные значениям аргумента. Читается “инверсия икс” или “не икс”. Обозначается «».

x
0	0
1	1

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

Таблица 2. или комбинации 0 и 1

х1 х2				→	~	/
0 0	0	0	0	1	1	1	1
0 1	1	0	1	1	0	1	0
1 0	1	0	1	0	0	1	0
1 1	1	1	0	1	1	0	0

1. - дизъюнкция х1 х2;

2. - конъюнкция х1х2;

3.- сумма по модулю два х1х2;

4.→ - импликация х1→х2;

5. функция эквивалентности х1~х2;

6. функция штрих Шеффера х1/х2 или х1х2;

7. функция стрелка Пирса х1х2.

Рассмотрим каждую из функций отдельно на языке высказываний. Под высказыванием мы понимаем предложение русского языка, о котором можно сказать, истинно оно или ложно. Если высказывание х истинно, мы будем писать х=1; если высказывание х ложно, мы будем писать х=0.

Нашу обычную речь мы строим из ряда последовательных высказываний или утверждений: строгих и не строгих. Например, вы можете сказать: «Меня зовут Виктор. Я учусь в ЮТИ ТПУ. У меня есть брат, который любит шоколад и не любит мороженое». Этот отрывок состоит из высказываний:

1.  Меня зовут Виктор;

2.  Я учусь в ЮТИ ТПУ;

3.  У меня есть брат;

4.  Брат любит шоколад;

5.  Брат не любит мороженое.

Каждое из этих высказываний может быть истинным или ложным. Если тебя действительно зовут Виктор, а не Петя, Ваня и т. д., то первое высказывание будет истинным, в противном случае ложным. Если ты учишься в ЮТИ ТПУ, а это значит, что второе высказывание будет истинным. Если ты один в семье или у тебя есть только сестры, то третье высказывание для тебя также окажется ложным. Если у тебя все-таки есть брат, который любит и мороженое и шоколад тоже, то третье и четвертое высказывания будут истинными, а пятое ложным. Любое высказывание может быть либо истинным либо ложным.

Каждому из высказываний мы можем сопоставить переменную. Обозначим через х высказывание "Меня зовут Виктор", через у - "Я учусь в ЮТИ ТПУ ", через z - "У меня есть брат", через и - "Брат любит шоколад" и v - "Брат любит мороженое". Обратите внимание на последнее высказывание, если v - "Брат любит мороженое", то утверждению, что «Брат не любит мороженое» в соответствие будет поставлена переменная .

Еще несколько примеров использования инверсии:

пусть х -«У меня есть собака», тогда «У меня нет собаки»,

у -«Волк поймает зайца», тогда «Волк не поймает зайца».

Двойной знак инверсии над переменной можно убирать = х.

Двойная инверсия, будет соответствовать высказыванию: « Неверно, что у меня нет собаки», это высказывание говорит о том, что «у меня есть собака».

Чтобы соединить два высказывания мы используем разные союзы И, ИЛИ. ЕСЛИ...ТО, ЛИБО...ЛИБО, и тд.

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