1 - Алгебра высказываний. Введение. Алгебра логики. Тавтологии и эквивалентность формул. Функции алгебры логики (Конспект лекций), страница 4

Подставив вместо всех вхождений переменной x формулу X, получим эквивалентность X ∧ X ≡ X.Остальные эквивалентности доказываются аналогично. IÌÃÒÓÔÍ-12Теорема 1.3. Для любых пропозициональных формул X, Y и Z верны следующие эквивалентности: 1) X ∧ X ≡ X; 2) X ∧ Y ≡ Y ∧ X; 3) (X ∧ Y ) ∧ Z) ≡ (X ∧ (Y ∧ Z); 4) X ∨ X ≡ X;5) X ∨ Y ≡ Y ∨ X; 6) (X ∨ Y ) ∨ Z) ≡ (X ∨ (Y ∨ Z); 7) X ∧ (Y ∨ Z) ≡ (X ∧ Y ) ∨ (X ∧ Z);8) X ∨ (Y ∧ Z) ≡ (X ∨ Y ) ∧ (X ∨ Z); 9) X ∧ (Y ∨ X) ≡ X; 10) X ∨ (Y ∧ X) ≡ X.ÌÃÒÓÌÃÒÓС помощью подстановки можно получать эквивалентные формулы, отталкиваясь от известных свойств логических операций.ÔÍ-12ÔÍ-12ÌÃÒÓ8ÌÃÒÓÌÃÒÓÔÍ-12J Формулу (Z ◦ W ), где ◦ — одна из логических связок, можно рассматривать как результатзамены в формуле (X ◦ Y ) сперва подформулы X эквивалентной формулой Z, а затем подформулы Y эквивалентной формулой W .

Согласно доказанной теореме такая замена приводит кэквивалентной формуле. Аналогичны рассуждения и для отрицания. IПриходим к эквивалентностиÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. АЛГЕБРА ВЫСКАЗЫВАНИЙÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓ9ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. АЛГЕБРА ВЫСКАЗЫВАНИЙзаключаем, чтоt1 ,...,tnt1 ,...,tnt1 ,...,tnX ∗ = Y ∗ ∧ Z ∗ ≡ ¬Y¬t∧¬Z=(¬Y∧¬Z)¬t1 ,...,¬tn1 ,...,¬tn¬t1 ,...,¬tnt1 ,...,tn≡ ¬X¬t.1 ,...,¬tnАналогично доказательство в случае второй операции.Под функцией алгебры логики, или булевой функцией понимают любое отображениеf : {0, 1}n → {0, 1}.

Это значит, что каждый аргумент булевой функции, как и сама функция,принимает два значения 0 и 1. Частными случаями булевых функций являются логическиеоперации, которые формально оперируют высказываниями, но по сути своей есть функции, вкоторых и аргументы, и значение могут принимать лишь два значения: ИСТИНА и ЛОЖЬ.Так, отрицание есть булева функция одного переменного, а дизъюнкция, конъюнкция, импликация, эквиваленция — функции двух переменных.Булеву функцию можно рассматривать как некое логическое условие, которые по входам —значениям аргументов вырабатывает логическое значение 0 (ложь) или 1 (истина).Для булевых функций можно ввести операцию суперпозиции.

Это вариант обычной композиции отображений, использующий понятие формулы. Пусть заданы функции f (x1 , . . . , xn ),g1 (u11 , . . . , u1,m1 ), . . . , gn (un1 , . . . , un,mn ). Тогда можно образовать функциюF (u11 , . . . , u1,m1 , . . . , un1 , . . . , un,mn ) = f (g1 (u11 , . . . , u1,m1 ), .

. . , gn (un1 , . . . , un,mn )),ÌÃÒÓÔÍ-12которую и назовем суперпозицией функций f , g1 , . . . , gn . В действительности при суперпозиции некоторые из переменных uij могут совпадать. В частном случае все функции gi могутиметь один и тот же набор переменных, и тогда суперпозиция — это обычная композиция отображений.

Здесь нетрудно увидеть, что суперпозиция — это построение некоторой формулыиз исходных функций и выбор функции, определяемой этой формулой. Порядок переменныхопределяется порядком функций и порядком их аргументов.Мы не будем здесь проводить строгие построения, но поставим следующий вопрос: каковомножество булевых функций, которое может быть получено из данного множества функций Fс использованием суперпозиции? Ясно, что ответ зависит от множества F . В первую очередьнас будут интересовать условия на множество F , при выполнении которых можно утверждать,что каждая булева функция может быть построена таким способом.Множество всех булевых функций, которые могут быть получены из данного множества Xфункций с использованием суперпозиции, назовем замыканием X и обозначим [X]. Множество X булевых функций назовем полным, если его замыкание совпадает с множеством P2всех булевых функций. Конечное полное множество называют базисом в множестве булевыхфункций.ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓПонятие булевой функции.

Множества P2,n и P2 . Композиция функций. Множество функций и его замыкание. Замкнутые и полные множества функций. Теорема: если F полно ивсе функции в F выражаются через функции множества G, то G полно. Понятие базиса.Стандартный базис. Базис Жегалкина. Понятие ДНФ и КНФ. Примеры построения ДНФ иКНФ. Совершенные ДНФ и КНФ. Теорема о существовании СДНФ и СКНФ.

Утверждение:каждая истинностная функция соответствует некоторой пропозициональной формуле. ШтрихШеффера и стрелка Пирса.ÔÍ-12ÔÍ-121.4. Функции алгебры логикиÌÃÒÓÌÃÒÓПринцип двойственности приводит к еще одному способу получения эквивалентных формул.ÔÍ-12ÔÍ-12t1 ,...,tnt1 ,...,tnJ Действительно, из эквивалентности X ≡ Y получаем ¬X ≡ ¬Y и ¬X¬t≡ ¬Y¬t.1 ,...,¬tn1 ,...,¬tnСогласно (1.5) делаем вывод X ∗ ≡ Y ∗ . IÌÃÒÓÌÃÒÓТеорема 1.5. Если формулы X и Y эквивалентны, то и формулы X ∗ , Y ∗ эквивалентны.ÌÃÒÓJ Так как каждая функция из F есть формула над G, то F ⊂ [G]. Из свойств замыканиявытекает, что[F ] ⊂ [[G]] = [G].Но поскольку [F ] совпадает с множеством всех булевых функций, то и [G] совпадает с множеством всех булевых функций, т.е. G — полный базис.

IДоказанная теорема позволяет строить базисы исходя из уже известных базисов. Одиниз таких базисов (это станет ясно из дальнейшего) составляют дизъюнкция, конъюнкция иотрицание. Этот базис назовем стандартным. Через эти операции можно выразить другиелогические операции:X ∼ Y ≡ (X ∧ Y ) ∨ (¬X ∧ ¬Y ).ÔÍ-12Теорема 1.7. Каждая формула алгебры высказываний, не являющаяся противоречием,имеет эквивалентную ей совершенную ДНФ.

Каждая формула алгебры высказываний, не являющаяся тавтологией, имеет эквивалентную ей совершенную КНФ. #ÌÃÒÓИмея в виду эти формулы можно было бы ограничиться только тремя операциями ¬, ∨, ∧.Более того, можно ограничиться двумя операциями, заменив ∨ или ∧.Среди формул, содержащих дизъюнкцию, конъюнкцию и отрицание можно выделить в некотором роде канонические формулы.Назовем элементарной конъюнкцией формулу X1 ∧X2 ∧.

. .∧Xn , в которой каждая подформулаXi либо элементарная, либо отрицание элементарной. Удобно ввести обозначение xσi i c σi ∈{0, 1}, считая, что x1i = xi и x0i = ¬xi . Тогда элементарную конъюнкцию можно записать ввиде xσ1 1 ∧ xσ2 2 ∧ . . . ∧ xσnn .Элементарная конъюнкция или дизъюнкция нескольких элементарных конъюнкций называется дизъюнктивной нормальной формой, или ДНФ.

Пример: (x1 ∧ x2 ) ∨ (¬x1 ∧ x3 ).Двойственным к ДНФ понятием является конъюнктивная нормальная форма, илиКНФ. Это элементарная дизъюнкция или конъюнкция нескольких элементарных дизъюнкций.Количество переменных в элементарной конъюнкции называется ее длиной. Если в ДНФвсе элементарные конъюнкции имеют одинаковый состав переменных и отличаются толькораспределением между переменными знаков отрицания, то ДНФ называется совершенной(сокращенно СДНФ).

Аналогично вводится понятие совершенной КНФ (СКНФ).ÔÍ-12X → Y ≡ ¬X ∨ Y,ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12Теорема 1.6. Если F — полное множество булевых функций, каждая из которых представима формулой над множеством G, то и G — полное множество.ÌÃÒÓÌÃÒÓОперация замыкания сродни, например, замыканию множества элементов группы по операции группы или замыканию множества точек на плоскости, состоящему в присоединении кмножеству всех его предельных точек. Замыкание можно рассматривать как унарную операциюна подмножествах множества P2 . Свойства операции замыкания:1) [∅] = ∅;2) [[X]] = [X];3) F ⊂ [X];4) [X] ∪ [Y ] ⊂ [X ∪ Y ].Первое свойство носит формальный характер. Второе вытекает из конечности процедурыпостроения любой формулы: достаточно, следуя по дереву синтаксического анализа, последовательно заменять функции из [X] их формулами над X. Третье и четвертое свойства очевидны.Из четвертого свойства вытекает, что если X ⊂ Y , то [X] ⊂ [Y ].

Действительно, включениеX ⊂ Y равносильно равенству X ∪ Y = Y . Если X ⊂ Y , то в силу свойства 4 заключаем, что[X] ∪ [Y ] ⊂ [X ⊂ Y ] = [Y ]. Следовательно, [X] ⊂ [Y ].Из указанных свойств замыкания вытекает следующее утверждение.ÌÃÒÓÔÍ-12ÌÃÒÓ10ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121.

АЛГЕБРА ВЫСКАЗЫВАНИЙÌÃÒÓJ Действительно, доказательство теоремы построено так, что характер формулы не являетсясущественным. Если f (ξ1 , ξ2 , . . . , ξn ) не равна тождественно 0, мы можем для нее построитьСДНФ. Если f (ξ1 , ξ2 , . . .

, ξn ) не равна тождественно 1, мы можем построить СКНФ. Такимобразом, любая функция имеет либо СДНФ, либо СКНФ, либо и то, и другое. I1 ≡ x + x ≡ x ∨ ¬x,f (x1 , x2 , x3 ) = a0 ⊕ a11 x1 ⊕ a12 x2 ⊕ a13 x3 ⊕ a21 x1 x2 ⊕ a22 x1 x3 ⊕ a23 x2 x3 ⊕ a3 x1 x2 x3 .ÔÍ-12Итак, в многочлене Жегалкина 2n слагаемых и, значит, 2n коэффициентов. Записывая 2n значений функции, мы получим систему уравнений, из которой можем найти все коэффициентымногочлена. Этот подход носит название метода неопределенных коэффициентов. Впринципе можно показать, что такая система имеет и притом единственное решение (это следует из того, что любая булева функция представима многочленом Жегалкина, причем такоймногочлен единственный).Кроме базиса Жегалкина существуют и другие базисы.

Основным способом проверки множества функций на полноту является сведение к стандартному базису. Оказывается, такуюпроверку можно свести к простой проверке некоторых свойств функций заданного множества.ÌÃÒÓгде первое представление дано в альтернативной символике операций: дизъюнкция как сложение x + y, конъюнкция как умножение xy, отрицание как дополнение x.