Элементы общей алгебры. Алгебра логики. Понятия алгебры логики, страница 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.

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

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

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

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

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

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

Представим число 17 в виде двоичного числа 10001. Запишем конъюнкцию пяти переменных  x₁ x₂ x₃ x₄ x₅  и возьмем с отрицанием те переменные, которым соответствуют нули - это элементарное произведение будет конституентой единицы. 17^го набора.

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

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

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

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

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

Пример. Представить в СДНФ логическую функцию пяти аргументов F=F(x₁ x₂ x₃ x₄ x₅) которая равняется единице на наборах с номерами 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 = F(х₁,х₂,х₃) j = j(х₁,х₂,х₃) Z = Z(х₁,х₂,х₃)