Элементы общей алгебры. Алгебра логики. Понятия алгебры логики, страница 3

х1

х2

х3

[    ]

{    }

х3

f=(f1, f2, f3)

0

0

0

1

0

0

0

1

0

0

1

1

0

0

1

1

0

1

0

0

1

0

0

1

0

1

1

1

1

1

1

1

1

0

0

1

1

1

0

0

1

0

1

0

1

0

1

1

1

1

0

1

0

0

0

1

1

1

1

0

0

0

1

1

Таким образом  f=  – искомая функция.

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

͎͢⭜¤Ü͢Ꟈ¶⳨мㄤㄤㄤ㆔邷邷邷ꛂ[1]ꛄꛄꛄꛄꛄꛄ$꡽Ƞl™͎邷贯Έ邷邷邷ꛨD Equation.3 

х1

х2

х3

[    ]

{    }

х3

f=(f1, f2, f3)

0

0

0

1

0

1

1

0

0

0

1

0

0

1

1

1

1

1

0

0

1

1

0

1

0

1

0

0

0

1

0

0

1

0

1

1

1

1

0

1

1

1

1

1

1

0

0

0

1

0

1

1

1

0

0

1

0

1

0

0

0

0

1

0

1

1

1

1

0

0

1

0

1

0

0

0

1

1

1

1

0

0

0

0

0

0

1

1

Таким образом  f=  – искомая функция.

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

Дизъюнктивные нормальные формы (ДНФ)

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

Пример:  ; ; , xyz –будут элементарными произведениями, а , хуÚ - нет , т.к. в них есть знак дизъюнкции или общее отрицание.

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

Теорема №1. Элементарное произведение равно 1 на одном наборе если переменным без отрицания из этого набора присвоены 1 и переменным с отрицанием – присвоены 0.

Пример: Элементарное произведение  равно единице только на наборе  x1=0   x2 = x3 = 1   т.к.   Этот набор единственный. Действительно для набора 0,0,1 имеем

Теорема №2 Для любого набора значений переменных существует только одно их элементарное произведение, которое равняется единице.

Теорема №3Элементарное произведение всех n переменных, входящих в функцию F, является конституентой единицы.

Теорема№4 Число конституент единицы для n переменных равняется 2n.

В соответствии с теоремой №1, чтобы представить конституенту единицы от n переменных которая будет равняться единице на m-том наборе, нужно представить число m в виде двоичного числа и в конъюнкции переменных, взять с отрицанием те переменные, которым в двоичном коде соответствуют нули.

Пример: Записать конституенту единицы для 17го набора.

Представим число 17 в виде двоичного числа 10001. Запишем конъюнкцию пяти переменных  x1 x2 x3 x4 x5  и возьмем с отрицанием те переменные, которым соответствуют нули - это элементарное произведение будет конституентой единицы. 17го набора.

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

Теорема №5 Любая логическая функция (кроме ”константы ноль”) может быть единственным образом представлена в СДНФ.

Задача представления функций в СДНФ (запись логических функций “по единицам”):

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

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

Пример. Представить в СДНФ логическую функцию пяти аргументов F=F(x1 x2 x3 x4 x5) которая равняется единице на наборах с номерами 5,14,16 и 31 и нулю на остальных наборах.

1.Выписываем четыре произведения и соединим их знаками дизъюнкции

Ú    Ú     Ú   

2. Под ними расставим наборы значений переменных в двоичной форме записи

00101 01110 10000 11111

тогда  F=`ÚÚÚ

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

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

В случае, если j является импликантой для F, то говорят, что j входит в функцию F (j Ì F).

Пример: В таблице заданы функции

F = F123) j = j123) Z = Z123)