Название работы	Кол-во страниц	Размер
Высшей математики	4	581.47kb.
Кафедра высшей математики	4	1159.67kb.
Математический факультет	1	52.04kb.
Методические указания к курсу «Элементы дискретной математики и биоинформатики»	3	385.63kb.
Элементы высшей математики	1	194.43kb.
Учебник включены основные разделы математики, необходимые для подготовки...	1	181.57kb.
О введении понятия производной в курсе математического анализа (математики)	1	43.39kb.
Кафедра математики и информатики	14	2458.17kb.
Учебная программа Дисциплины 08 «Численное моделирование в акустике...	1	97.4kb.
Кафедра «Прикладная математика и фундаментальная информатика»	1	35.66kb.
Программа дисциплины Математический анализ для направления 010500.	1	206.3kb.
Закон Алгебра логики Аналог в алгебре действительных чисел Законы...	1	27.32kb.
Викторина для любознательных: «Занимательная биология»	1	9.92kb.

Кафедра высшей математики

Семенчук В.Н.

Текст лекций по курсу «Дискретная математика»

для студентов 1 курса математического факультета

специальности 1-31 03 03 «Прикладная математика (научно-производственная деятельность и научно-педагогическая деятельность )» и студентов 3 курса

специальности 1-40 01 01 «Программное обеспечение информационных технологий»

ТЕМА 1 ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

1.1 Логические операции

1.2 Булевы функции

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

Алгебра логики – самый простой раздел математической логики. Язык алгебры логики является одним из простейших языков математики. Основными объектами данного раздела являются высказывания. Понятие «высказывание» является первичным, оно не определяется, а поясняется. Под высказыванием понимают предложение, о котором можно сказать одно из двух: истинно оно или ложно. Например, высказывание «2 + 3 = 5» – истинное, высказывание «существует действительное число х такое, что

х² = –1» – ложное. Очевидно, не каждое предложение является высказыванием. Например, предложения: «Когда ты был дома?», «Пойдем со мной!» не являются высказываниями. Высказывания будем обозначать малыми латинскими буквами x, y, z,…, а их значения, т.е. истину и ложь, соответственно 1 и 0. Из двух данных высказываний с помощью связок «не», «и», «или», «если … то», «тогда и только тогда, когда …» можно образовать новые высказывания. Например, из высказываний «число 2 простое», «число 2 четное» с помощью указанных выше связок получаем высказывания: «число два простое и четное», «число 2 непростое», «число 2 простое или четное». Высказывание «если π иррационально, то π² тоже иррационально» получается связыванием двух высказываний связкой «если … то». Эти операции соответствуют упомянутым выше связкам, употребляемым в обычной речи.

Рассмотрим примеры логических операций.

1 Логическая операция, соответствующая связке «и», называется конъюнкцией и обозначается &. В некоторых книгах эту операцию обозначают символом . Пусть x и y – высказывания. Высказывание xy назовем конъюнкцией x и y. Данное высказывание истинно тогда и только тогда, когда истинны оба высказывания x и y.

Соответствующее определение запишем в виде таблицы истинности:

x	y	xy
0	0	0
0	1	0
1	0	0
1	1	1

Определение конъюнкции двух высказываний естественным образом распространяется на любое конечное число высказываний.

Конъюнкция x₁x₂…x_n, которую мы кратко обозначим через , истинна тогда и только тогда, когда истинны все высказывания.

2 Логическая операция, соответствующая связке «или», называется дизъюнкцией и обозначается .

Пусть x и y – высказывания. Высказывание xy назовем дизъюнкцией x и y. Данное высказывание истинно тогда и только тогда, когда хотя бы одно из высказываний x и y истинно.

Данное определение запишем в таблицы истинности:

x	y	xy
0	0	0
0	1	1
1	0	1
1	1	1

Определение дизъюнкции двух высказываний естественным образом распространяется на любое конечное число высказываний. Дизъюнкция x₁ x₂  …  x_n, которую мы кратко обозначим через , истинна тогда и только тогда, когда хотя бы одно из высказываний x₁, x₂, …, x_n истинно.

3 Логическая операция, соответствующая связке «не», называется отрицанием.

Отрицание высказывания x записывается так: и определяется следующей таблицей истинности:

x
0	1
1	0

4 Логическая операция, соответствующая связке «если … то», называется импликацией. Эту операцию будем обозначать символом . При этом высказывание «если x, то y» записывается в виде xy. Высказывание x называется посылкой импликации, y – ее заключением. Импликация двух высказываний x и y задается следующей таблицей истинности:

x	y	xy
0	0	1
0	1	1
1	0	0
1	1	1

Из определения импликации вытекает, что:

• 
  импликация с ложной посылкой всегда истинна;
  
• 
  импликация с истинным заключением всегда истинна;
  
• 
  импликация ложна тогда и только тогда, когда посылка истинна, а заключение ложно.
  

5 Логическая операция, соответствующая связке «тогда и только тогда, когда …» называется эквивалентностью и обозначается символом .

Пусть x и y – высказывания. Высказывание xy назовем эквивалентностью x и y. Данное высказывание истинно тогда и только тогда, когда оба

высказывания x и y или истинны или ложны.

Данное определение запишем в виде таблицы истинности:

x	y	xy
0	0	1
0	1	0
1	0	0
1	1	1

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

Пусть исходный алфавит переменных.

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

Обычно функции алгебры логики называют булевыми функциями. Название «булевы функции» возникло в связи с использованием функций рассматриваемого типа в алгебре логики, начало которой было положено трудами ирландского ученого 19 века Дж. Буля. Областью определения булевой функции от n переменных служит совокупность всевозможных

n-мерных упорядоченных наборов , где .

Следует отметить, что любой такой набор можно рассматривать как представление некоторого целого неотрицательного числа в двоичной системе счисления. Например, набору (0,1,0,1) соответствует число , а набору (1,1,1) – число .

Все наборы размерности n нумеруются целыми числами от 0,2ⁿ-1. Отсюда нетрудно заметить, что число таких наборов равно 2ⁿ.

Всякая булева функция от n переменных может быть задана с помощью таблицы истинности:

x1	x2	…	xn-1	xn	f(x1,x2,…,xn-1,xn)
0	0	…	0	0	f (0,0,…,0,0)
0	0	…	0	1	f (0,0,…,0,1)
0	0	…	1	0	f (0,0,…,1,0)
…	…	…	…	…	…
1	1	…	1	1	f (1,1,…,1,1)

Данная таблица состоит из 2ⁿ строк, причем в ней все наборы расположены в порядке возрастания их номеров.

Очевидно, что булевы функции от n переменных однозначно определяются своими последними столбцами из этой таблицы, т.е. наборами из 2ⁿ нулей и единиц. Следовательно, различных булевых функций от n переменных будет столько, сколько имеется различных наборов длины 2ⁿ, а их число равно . Итак, мы доказали следующую теорему:

Теорема 1 Имеется точно булевых функций от переменных.

В алгебре логики особое значение имеют следующие булевы функции, которые называют элементарными булевыми функциями:

1. 
   – константа 0;
   
2. 
   – константа 1;
   
3. 
   – тождественная функция;
   
4. 
   – отрицание х;
   
5. 
   – конъюнкция x и y;
   
6. 
   – дизъюнкция х и у;
   
7. 
   – импликация х и у;
   
8. 
   – эквивалентность х и у;
   
9. 
   – сложение х и у по mod2;
   
10. 
    – функция Шеффера;
    
11. 
    – стрелка Пирса.
    

Последние три функции задаются следующими таблицами истинности:

0	0	0	1	1
0	1	1	1	0
1	0	1	1	0
1	1	0	0	0

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

Переменная x_i в функции называется фиктивной, если = при любых значениях остальных переменных. В этом случае функция , по существу, зависит от (n-1) – переменной, т.е. представляет собой функцию от (n-1) переменной. Говорят, что функция g получается из функции f удалением фиктивной переменной, а функция f получается из g введением фиктивной переменной, причем эти функции являются равными.

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

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

2 Дайте определение булевой функции.

3 Что такое таблицы истинности булевой функции?

4 Каково число булевых функций от переменных?

5 Какие булевы функции называются элементарными?

ТЕМА 2 ФОРМУЛЫ АЛГЕБРЫ ЛОГИКИ

2.1 Равносильные формулы алгебры логики

2.2 Законы алгебры логики

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

2.1 Равносильные формулы алгебры логики.

Приведем определение формулы алгебры логики.

1) каждая «элементарная» булева функция – формула;

2) если некоторое выражение N есть формула, то тоже формула;

3) если некоторые выражения M и N есть формулы, то выражения , , , тоже формулы;

4) других формул, кроме построенных по п.п.1), 2), 3), нет.

Формулы алгебры логики мы будет обозначать большими N, M, … Например, следующие выражения являются формулами алгебры логики:

, .

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

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

Две формулы N и M называются равносильными, если они определяют одну и ту же булеву функцию (запись N = M будет означать, что формулы N и M равносильны).

Пример 1 Формулы и равносильны, т.е. .

Действительно, построим таблицы истинности для данных формул.

0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

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

Очевидно, что отношение равносильности формул алгебры логики является:

1. 
   рефлексивным, т.е. N = N для любой формулы N;
   
2. 
   симметричным, т.е. если N = M, то M = N для любых формул N и M;
   
3. 
   транзитивным, т.е. если N = M и M = J, то N = J для любых формул N,M,J.
   

Таким образом, отношение равносильности является отношением эквивалентности.

Если какую-нибудь формулу N₁, являющуюся частью формулы N заменить формулой N₂, равносильной N₁, то полученная формула окажется равносильной N. Это свойство лежит в основе преобразования формул с целью их упрощения или приведения к определенной форме.

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

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

1. 
   – закон тождества;
   
2. 
   – закон противоречия;
   
3. 
   – закон исключительного третьего;
   
4. 
   – закон двойного отрицания;
   
5. 
   , – законы идемпотентности;
   
6. 
   , – законы коммутативности;
   
7. 
   , – законы дистрибутивности;
   
8. 
   , – законы ассоциативности;
   
9. 
   , – законы де Моргана;
   
10. 
    ,
    
11. 
    ,
    
12. 
    , – законы поглощения;
    
13. 
    , – законы склеивания.
    

Перечисленные законы алгебры логики доказываются с помощью таблиц истинности. В качестве примера докажем справедливость закона .

0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

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

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

, ;

, .

Первые две равносильности легко доказываются с помощью таблиц истинности. Две последние равносильности докажем с помощью законов де

Моргана и двойного отрицания:

; .

Итак, справедливы следующие утверждения:

1) импликацию и эквивалентность можно выразить через конъюнкцию, дизъюнкцию и отрицание;

2) конъюнкцию можно выразить через дизъюнкцию и отрицание;

3) дизъюнкцию можно выразить через конъюнкцию и отрицание;

4) все операции посредством равносильных выражений можно заменить двумя: конъюнкцией и отрицанием или дизъюнкцией и отрицанием.

Естественно возникает следующий вопрос. Для чего вводить пять логических операций, когда можно обойтись двумя? Использование лишь двух операций существенным образом усложнило бы запись, что привело бы к громоздким формулам. Однако в некоторых приложениях математической логики удобно ограничиться двумя операциями. Аналогичная ситуация имеет место в арифметике. Всякое натуральное число можно записать с помощью цифр 0 и 1. Однако записи чисел и выкладки в двоичной системе громоздки. К этой системе прибегают лишь в некоторых случаях.

Множество булевых функций, рассматриваемое вместе с операциями отрицания, конъюнкции и дизъюнкции, называют булевой алгеброй. Законы 1-13 являются основными законами булевой алгебры.

Обратим внимание на характер соответствий между равносильностями, объединенными в пару под номерами (5-13). В этих соответствиях проявляется так называемый закон двойственности.

Назовем формулу алгебры логики двойственной к формуле , если =.

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

Как показано в пункте 2.2, всякая формула алгебры логики может быть

приведена равносильными преобразованиями к формуле, содержащей только операции конъюнкции, дизъюнкции и отрицания. Поэтому, учитывая законы де Моргана и двойного отрицания, две формулы алгебры логики N и M, содержащие только операции конъюнкции, дизъюнкции и отрицания, будут двойственными, если одна получается из другой заменой каждой операции на двойственную и 1 заменяется на 0, а 0 на 1.

Например, формула двойственная к формуле , а формула двойственная к формуле .

Теперь сформулируем закон двойственности.

Теорема 1 Если формулы алгебры логики N и M равносильны, то и двойственные им формулы N^* и M^* равносильны.

Докажем данный закон. Пусть N(x₁,x₂,…,x_n) = M(x₁,x₂,…,x_n). Согласно определению двойственной формулы

и .

Так как N(x₁,x₂,…,x_n) и M(x₁,x₂,…,x_n) принимают одинаковые значения при любых значениях переменных x₁,x₂,…,x_n, то

=.

Отсюда следует, что

.

Так как формулы и равносильны соответственно формулам и , то они равносильны между собой.

Принцип двойственности позволяет сократить усилие на вывод равносильностей.

Пример 2 Из равносильности вытекает равносильность

. Из равносильности вытекает равносильность .
Вопросы для самоконтроля

1 Дайте определение формулы алгебры логики.

2 Какие формулы алгебры логики называются равносильными?

3 Сформулируйте законы алгебры логики.

4 Какая формула алгебры логики называется двойственной к данной формуле алгебры логики?

5 Сформулируйте принцип двойственности.

ТЕМА 3 НОРМАЛЬНЫЕ ФОРМЫ

3.1 Разложение булевых функций по переменным

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

3.1 Разложение булевых функций по переменным.

Пусть G – параметр, равный 0 или 1. Введем обозначение:

Проверкой легко установить, что x^G = 1, тогда и только тогда, когда

x = G. Отсюда следует, конъюнкция равна 1 (здесь G равен 0 или 1) тогда и только тогда, когда . Например, конъюнкция (в которой G₂ = G₁ = 0, G₃ = G₄ = 1) равна 1 только в случае, когда x₁ = x₂ = 0, x₃ = x₄ = 1.

Теорема 1 Всякая булева функция f(x₁,x₂,…,x_n) может быть представлена в следующей форме:

, (3.1)

где 1 ≤ k ≤ n, в дизъюнкции берется по всем наборам значений переменных.

Это представление носит название разложения функции по переменным . Например, при n = 4, k = 2 разложение (3.1) имеет вид:

.
Докажем справедливость разложения (3.1). Для этого возьмем произвольный набор значений переменных . Покажем, что левая и правая части соотношения (3.1) принимают при нем одно и то же значение. Действительно, так как x^G = 1 тогда и только тогда, когда x = G, то среди 2^К конъюнкции правой части (3.1) в единицу обращается только одна, в которой . Все остальные конъюнкции равны нулю.

Поэтому . В качестве следствия из разложения (3.1) получаем следующие два специальных разложения.

Разложение по переменной x_n:

(3.2)

Если булева функция не есть константа 0, то справедливо разложение

Разложение по всем переменным:

, (3.3)

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

Разложение (3.3) называется совершенной дизъюнктивной нормальной формой (сокращенная запись СДНФ) функции.

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

Таким образом, существует взаимно однозначное соответствие между таблицей истинности функции и ее СДНФ. А это значит, что СДНФ для булевой функции единственна.

Единая булева функция, не имеющая СДНФ, есть константа 0.

Пример 1 Найти совершенную дизъюнктивную форму для функции .

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

0	0	0	1	1	0
0	0	1	1	1	1
0	1	0	0	1	0
0	1	1	0	1	1
1	0	0	1	1	0
1	0	1	1	1	1
1	1	0	0	0	1
1	1	1	0	0	1

Отсюда получаем: ==.

Важную роль в алгебре логики играет следующее разложение булевых функций.

Теорема 2 Всякая булева функция может быть представлена в следующей форме:

(3.4)

где 1≤k≤n, а конъюнкция берется по всем 2^k наборам значений переменных.

Действительно, пусть – произвольный набор значений переменных. Покажем, что левая и правая части соотношения (3.4) принимают при нем одно и то же значение. Так как только тогда, когда , то среди 2^k дизъюнкций правой части (3.4) в 0 обращается только одна, в которой . Все остальные дизъюнкции равны 1.

Поэтому ==.

Непосредственно из разложения (3.4) следуют разложения булевых функций:

(3.5)

, (3.6)

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

Единственная булева функция, не имеющая СКНФ, есть константа 1.

Пример 2 Найти совершенную конъюнктивную нормальную форму для функции .

Составим таблицу истинности для данной функции.

0	0	0	1	1	1
0	0	1	1	1	1
0	1	0	1	0	0
0	1	1	1	1	1
1	0	0	0	1	0
1	0	1	0	1	0
1	1	0	1	0	0
1	1	1	1	1	1

Отсюда получаем СКНФ

.

Формула вида (краткая запись ), где – конъюнкции называется дизъюнктивной нормальной формой (ДНФ).

В силу приведенного определения ДНФ будут, например, выражения: , .

Как отмечено в пункте 2.2, все логические операции можно свести к трем: конъюнкции, дизъюнкции и отрицания. Причем, ввиду закона

де Моргана, знак отрицания можно предполагать отнесенным только к переменным.

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

Теорема 3 Для любой формулы алгебры логики существует равносильная ей дизъюнктивная нормальная форма.

Доказательство данной теоремы дает способ построения дизъюнктивной нормальной формы для любой формулы алгебры логики.

Пример 3 Найти дизъюнктивную нормальную форму для следующей формулы: .

Исключая знак по закону и применяя законы де Моргана и двойного отрицания, получаем:

Затем, применяя закон дистрибутивности, раскроем скобки

Последнее выражение есть дизъюнктивная нормальная форма.

Форма вида (краткая запись ), где - дизъюнкции называется конъюнктивной нормальной формой (КНФ).

Такими являются, например, выражения:

, .

Как показано выше, для любой формулы алгебры логики существует равносильная ей дизъюнктивная форма. Используя дистрибутивный закон , из данной ДНФ легко получить КНФ.

Итак, справедлива следующая теорема.

Теорема 4 Для любой формулы алгебры логики существует равносильная ей конъюнктивная нормальная форма.

Доказательство данной теоремы дает способ построения конъюнктивной нормальной формы для любой формулы алгебры логики.

Пример 4 Найти дизъюнктивную и конъюнктивную нормальные формы для следующей формулы: .

Используя закон , исключаем знак . Получаем формулу .

Используя закон де Моргана, получаем формулу . Раскрывая скобки, получаем дизъюнктивную нормальную форму

.

Чтобы получить конъюнктивную нормальную форму, применим к формуле дистрибутивный закон, получаем:

.

Последнее выражение является конъюнктивной нормальной формой. Так как и , то полученная КНФ равносильна следующей КНФ:

.

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

1) все конъюнкции попарно различны;

2) каждая конъюнкция содержит ровно n переменных;

3) в каждой конъюнкции встречаются все n переменных.

На примере 1 мы рассмотрели один из способов построения СДНФ, основанный на составлении таблицы истинности. Следующий способ построения СДНФ основан на применении законов алгебры логики.

Пример 5 Найти совершенную дизъюнктивную форму формулы .

Используя, что , получаем . Ввиду законов

де Моргана и двойного отрицания имеем получили дизъюнктивную нормальную форму . Данная ДНФ равносильна формуле .

Раскрывая скобки, получаем: .

Используя закон идемпотентности, получаем требуемую СДНФ:

.

Учитывая разложение (3.6), нетрудно заметить, что совершенная конъюнктивная нормальная форма формулы алгебры логики, содержащей ровно n различных переменных, есть ее конъюнктивная нормальная форма, в которой:

1) все дизъюнкции попарно различны;

2) каждая дизъюнкция содержит ровно n членов;

3) в каждой дизъюнкции встречаются все n переменных.

На примере 2 мы рассмотрели один из способов построения СКНФ, основанный на составлении таблицы истинности. Следующий способ построения СКНФ основан на применении законов алгебры логики.

Пример 6 Найти совершенную конъюнктивную нормальную форму формулы .

Используя, , получаем .

Данная формула является конъюнктивной нормальной формой. Она равносильна формуле .

Используя закон дистрибутивности, получаем:

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

.

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

Примерами тождественно истинных формул являются формулы:

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

Примерами тождественно ложных формул являются формулы:

,

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

Примерами выполнимых формул являются следующие формулы:

, .

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

Рассмотрим следующие два способа решения этой задачи.

Способ 1 (табличный) Для того, чтобы определить, является ли данная формула тождественно истинной или нет, достаточно составить ее таблицу истинности.

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

Способ 2 основан на приведении формул к нормальной форме.

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

Действительно, если каждая дизъюнкция в конъюнктивной нормальной форме содержит переменную вместе с ее отрицанием, то все дизъюнкции равны 1, ибо , . Отсюда следует, что КНФ является тождественно истинной.

Пусть теперь данная формула является тождественно истинной, и пусть есть некоторая дизъюнкция в КНФ данной формулы. Допустим, что данная дизъюнкция не содержит переменной вместе с ее отрицанием. В таком случае мы можем каждой переменной, не стоящей под знаком отрицания, дать значение 0, а каждой переменной, стоящей под знаком отрицания – значение 1. После указанной подстановки все дизъюнкции станут равны 0, следовательно, формула не является тождественно истинной. Получили противоречие.

Пример 7 Выяснить, будет ли тождественно истинной формула

.

Используя, что , получаем .

Применяя закон дистрибутивности, получаем КНФ:

. Так как каждая дизъюнкция содержит некоторую переменную вместе с ее отрицанием, то формула тождественно истинна.

Аналогично предыдущей теореме доказывается теорема:

Теорема 5 Формула алгебры логики тогда и только тогда является тождественно ложной, когда каждая конъюнкция в ее дизъюнктивной форме содержит некоторую переменную вместе с ее отрицанием.
3.2 Алгебра Жегалкина.

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

Непосредственно проверкой (с помощью таблиц истинности) устанавливаются следующие законы:

1. 
   – закон коммутативности;
   
2. 
   – закон ассоциативности;
   
3. 
   – закон дистрибутивности;
   
4. 
   ;
   
5. 
   .
   

В алгебре Жегалкина роль совершенных нормальных форм булевой алгебры играют полиномы Жегалкина.

Полиномом Жегалкина называется полином вида

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

а – константа 0 или 1.

Например, выражение является полиномом Жегалкина, а выражения и – нет, так как в первом выражении имеется конъюнкция, содержащая две переменные y, а второе выражение содержит два одинаковых слагаемых и .

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

Рассмотрим теперь взаимосвязь, существующую между операциями булевой алгебры и алгебры Жегалкина. Непосредственной проверкой устанавливается

(3.7)

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

Число различных слагаемых (конъюнкций) полинома Жегалкина от n переменных равно числу всех подмножеств из n элементов, т.е. 2ⁿ. Число различных полиномов, которые можно образовать из этих конъюнкций, равно числу всех подмножеств множества данных конъюнкций, т.е. . Следовательно, число всех полиномов Жегалкина от n переменных равно числу всех булевых функций от n переменных. Отсюда следует единственное представление булевой функции посредством полинома Жегалкина. Итак, справедлива следующая теорема.

Теорема 6 Каждая булева функция может быть единственным образом выражена при помощи полинома Жегалкина.

Пример 8 Выразить в виде полинома Жегалкина.

Способ 1 (табличный) Ищем требуемый полином методом неопределенных коэффициентов: .

1. 
   при x = y = 0 имеем: d = 1;
   
2. 
   при x = 0, y = 1 имеем: a = 0;
   
3. 
   при x = 1, y = 0 имеем: b = 1;
   
4. 
   при x = 1, y = 0 имеем: 1 = a + b + c + d = a + 1 + 0 + 1 = a, т.е. а = 1.
   

Отсюда

Способ 2
Вопросы для самоконтроля

1 Сформулируйте теорему о разложении и следствие из нее.

2 Дайте определение СДНФ.

3 Приведите алгоритмы построения СДНФ.

4 Дайте определение СКНФ.

5 Приведите алгоритмы построения СКНФ.

6 Дайте определение ДНФ.

7 Как найти ДНФ?

8 Дайте определение КНФ.

9 Как найти КНФ?

10 Какая формула алгебры логики называется тождественно истинной?

11 Какая формула алгебры логики называется тождественно ложной?

12 Какая формула алгебры логики называется выполнимой?

13 Что называется проблемой разрешимости?

14 Сформулируйте методы решения проблемы разрешения.

15 Что называется алгеброй Жегалкина?

16 Сформулируйте законы алгебры Жегалкина.

17 Что называется полиномом Жегалкина?

18 Сформулируйте алгоритмы построения полиномов Жегалкина.


следующая страница >>