Булевы функции.
презентация к уроку по теме

Слайд 1

Булеву функцию одного аргумента можно определить таблицей : X’- функция называется отрицанием. X X’ 0 1 1 0 X Y X · Y X V Y X → Y X ↔ Y X | Y X ↓ Y X+Y 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 0 0 0 В таблице(ниже) приведены основные булевы функции от двух аргументов : Здесь: X · Y - конъюнкция, X V Y –дизъюнкция, X → Y – импликация, X ↔ Y – эквивалентность, X|Y – штрих Шеффера, X ↓ Y – стрелка Пирса X+Y – сумма Жегалкина .

Слайд 2

Иван Иванович Жегалкин (1869-1947) – российский математик и логик, один из основоположников современной математической логики. Из его открытий наибольшую известность получил так называемый полином Жегалкина. Жегалкин награжден Орденом Трудового Красного Знамени. В своем письме М. Я. Выгодскому известный советский математик Николай Лузин, вспоминая студенческие годы, говорит, что из профессоров не боялся лишь Жегалкина. Чарльз Сандерс Пирс (1839-1914)- американский философ, логик, математик, основоположник прагматизма и семиотики. Ввёл в философию термин фанерон , предложил концепцию тихизма . В логику — стрелку Пирса, в картографию — проекцию Пирса. Немецкий философ Апель назвал Пирса «Кантом американской философии».

Слайд 3

Число булевых функций n аргументов равно . Для задания булевой функции нужно указать её значение для каждого из 2 в степени n различных значений её аргументов. Если значение функции равно 0, то такая функция постоянна и называется константой 0. Если значение функции равно 1, то такая функция называется константой 1. Для функций справедливы равенства: a v a = a; aa=a a v b = b v a; ab=ba (a v b) v c = a v (b v c); (ab)c=a(bc) a v 1 = 1, a ·1=1 a v (b · c)=(a v b) ·( a v c) a · (b v c)=(a · b) v (a · c) a v (b · a)=a; a · (b v a) (X v Y)’=X’ · Y’; (X · Y)’=X’ v Y’ X v X’ = 1; X · X’= 0 X’’=X a v 0 = a; a · 0 = 0 a → b=a’ v b’ a ↔b =(a → b) ·(b → a)

Слайд 4

Все приведённые выше формулы проверяются с помощью таблиц булевых функций. Докажем последнюю формулу. 1. Составим таблицу : a b a ↔ b a → b b → a (a → b) ·( b → a) 0 0 1 1 1 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 1 1 2. Сравним третий и шестой столбцы, видим, что они одинаковы, значит функции стоящие в левой и правой части доказываемой формулы, принимают одинаковые значения для одинаковых наборов аргументов

Слайд 5

Конъюнктивным(дизъюнктивным) одночленом от переменных ( , , … ) называется конъюнкция(дизъюнкция) этих переменных или их отрицаний. Формула, равносильна данной формуле алгебры высказываний и являющаяся дизъюнкцией элементарных произведений (конъюнктивных одночленов), называется дизъюнктивной нормальной формулой(ДНФ) данной формулы: Например: ABC v A v CB v - ДНФ Формула, равносильна данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных произведений (дизъюнктивных одночленов), называется конъюнктивной нормальной формулой(КНФ) данной формулы. Например: ( v B v C )( A v ) B – КНФ.

Слайд 6

Для каждой формулы алгебры высказываний можно найти множество дизъюнктивных и конъюнктивных нормальных форм. Для этого нужно: Избавится от всех логических операций, содержащихся в формуле, заменив их основными – конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать используя равносильные формулы : A →B=A v B ;A↔B=(A v B) ∙(A’ v B’); A↔B=(A∙B) v (A’∙B’). Заменить знак отрицания, относящийся к выражениям типа АВ или А v B, знаками отрицания. Относящимся к отдельным переменным высказываниям на основании формул А v B = AB; A’B’= A’ v B’ Избавится от знаков двойного отрицания: A=A’’ Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности, формулы поглощения. Теорема: Формула алгебры высказываний является тождественно ложной тогда и только тогда, когда каждое слагаемое (т. е. каждое элементарное произведение) ее ДНФ содержит пару сомножителей, один из которых есть элемен­тарное высказывание, другой — его отрицание.

Слайд 7

Можно построить КНФ для отрицания исходной формулы. Если окажется, что она удовлетворяет условиям теоремы, то исходная формула невыполнима, так как ее отрицание тож­дественно истинно. В не перечисленных выше случаях формулы являются вы­полнимыми. Рассмотрим, например, формулу: (a ٨ b ٨ c)(a ٨ b ٨ c)(a ٨ b ٨ c) При приведении этой формулы к КНФ среди дизъюнктивных одночленов будет а v b v с, что противоречит условию суще­ствования тавтологии . Поэтому данная формула - не тавтология. При решении ряда задач часто бывает удобно использо­вать совершенную дизъюнктивную нормальную форму функ­ции (СДНФ) или совершенную конъюнктивную нормальную форму функции (СКНФ). Одночлен от некоторых переменных называется совершен­ным, если каждая из этих переменных входит в него точно один раз либо со знаком отрицания, либо без него .

Слайд 8

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

Слайд 9

Конструктивно СДНФ для каждой формулы алгебры выс­казываний, приведенной к ДНФ, можно определить так: Совершенной дизъюнктивной нормальной формой (СДНФ) формулы алгебры высказываний называется ее ДНФ, облада­ющая следующими свойствами : ДНФ не содержит двух одинаковых слагаемых . Ни одно слагаемое не содержит одновременно двух одина­ковых сомножителей . Ни одно слагаемое не содержит одновременно некоторое высказывание и его отрицание. Каждое слагаемое содержит в качестве сомножителя либо переменное высказывание, либо его отрицание для всех переменных входящих в формулу . Приведем, например, к СДНФ булеву функцию( a v b’ ) ∙ ( a→c ). Используя свойства булевых функций, получаем: ( a v b’ ) ∙ ( a→c ) = (a’ ∙ b’ )v (a’ ∙ c)=(a’ ∙ b’ ∙ a’) v (a’ ∙ b’ ∙ c)=(a’ ∙ b’) v (a’ ∙ b’ ∙ c)=a’ ∙ b‘=a’ ∙ b’(c v c’)=(a’ ∙ c ∙ b’) v (a’ ∙ c’ ∙ b’)

Слайд 10

Совершенной конъюнктивной нормальной формой функции (СКНФ) будем называть функцию вида: Ф( ) = V Ф ( ) , , Где А конъюнкция распространяется на все выражения , для которых Ф ( ) =0 Конструктивно СКНФ для каждой формулы алгебры высказываний, приведенной к КНФ, можно определить так: Совершенной конъюнктивной нормальной формой (СКНФ) данной формулы алгебры высказываний называется такая ее КНФ, которая удовлетворяет следующим свойствам.

Слайд 11

1.КНФ не содержит одинаковых сомножителей. 2. Ни один из сомножителей не содержит двух одинаковых слагаемых. 3. Ни один сомножитель не содержит одновременно неко­торое переменное высказывание и его отрицание. 4. Каждый сомножитель СКНФ содержит в качестве слага­емого либо переменное высказывание, либо его отрицание для всех переменных высказываний, входящих в формулу. Из определений и теорем следует, что тождественно ис­тинная формула не имеет СКНФ, а тождественно ложная не имеет СДНФ. Каждая не тождественно истинная и не тождественно лож­ная формула имеют единственные СКНФ и СДНФ. Можно доказать следующие утверждения. Каждая булева функция от п переменных, отличная от константы 0, имеет единственную (с точностью до пе­рестановки дизъюнктивных членов) СДНФ. Каждая булева функция от п переменных, отличная Щ константы 1, имеет единственную (с точностью до пе­рестановки конъюнктивных членов) СКНФ .

Слайд 12

Рассмотрим обратную задачу. Задана некоторая функция f( , … ) своей таблицей истинности, нужно построить для нее формулу. Задача эта неоднозначна, существует множество равносильных между собой формул, соответствующих данной функции. Будем строить СДНФ. СДНФ содержит столько слагаемых, сколько единиц име­ет истинностная таблица. Эти единицы соответствуют тем на- борам переменных, при которых каждое слагаемое ('элемен­тарная конъюнкция) обращается в единицу, т. е. переменным, входящим в элементарную конъюнкцию без знака отрицания, соответствует 1, а со знаком отрицания 0. Чтобы написать СКНФ по заданной истинностной таблице, нужно выбрать все встречающиеся в ней значения 0 и рассмот­реть наборы значений переменных, отвечающие этим нулям. СДНФ содержит столько сомножителей, сколько нулей имеет истинностная таблица. Эти нули соответствуют тем на* борам переменных, при которых каждый сомножитель (каж­дая элементарная сумма) обращается в нуль, т. е. переменным , входящим в элементарную сумму без знака отрицания, соответствует 0, а со знаком отрицания 1…

Слайд 13

Построим, СДНФ и СКНФ для формулы A=( p → q ) ^ (p v q). Для решения задачи используем истинную таблицу для А. p q q p → q p v q ( p → q )^(p v q) 1 1 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 В таблице отметим строки, где А принимает значение 1(3 и 4 строки). В третьей строке А=1, если р=1, q=0, составим конъюнкцию p ^ В четвертой строке А=1 если p=0, q=1, следовательно p ^ q . Полученные конъюнкции соединим законом дизъюнкции и получим СДНФ. B=(p ^ q) v (p ^ q)

Слайд 14

Отметим в таблице строки, в которых А = 0. Это втора и пятая строки. Составим дизъюнкции: для второй строки v для пятой строки p v q. Соединив дизъюнкции конъюнкцией, получим СКНФ: С=( p v q ) ^ (p v q) Если построить истинные таблицы то можно проверить эквивалентности А и В, А и С. p q q p → q p v q ( p → q )^(p v q) 1 1 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 Например используя СКНФ, найдем булеву функцию, принимающую значение 0 на следующих наборах переменных, и только на них: f(0,0,0)=f(0,1,0)=f(0,1,1)=0

Слайд 15

Выпишем наборы переменных при которых булева функция обращается в нуль:(0,0,0),(0,1,0),(0,1,1). Для каждого набора выпишем совершенный, дизъюнктивный одночлен, обращающейся в нуль только на этом наборе переменных: f(0,0,0)=0 если a v b’ v c; f(0,1,0 )= 0 если a v b’ v c ; f(0,1,1)=0 Если a ’ v b ’ v c’. Соединяя полученные совершенные дизъюнктивные одночлены конъюнкцией, получим СКНФ: f(a, b, c)= (a v b v c) (a v b’ v c) (a v b’ v c) Система булевых функций называется полной, если любая функция может быть выражена через функции c помощью суперпозиций. Пусть К° = { } — конечная си­стема булевых функций. Функция / называется элементарной суперпозицией ( перпозицией ранга 1) функций f 1 , f 2 , ..., f m если /может быть получена одним из следующих способов: а) переименованием некоторой переменной х, какой-ни­будь функции f i . б) подстановкой некоторой функции f i (1 i т) вмес­то какой-либо переменной х. любой из функций . Суперпозиции ранга 1 образуют класс функций К 1 . Класс функций, получающийся из функций класса К*~ 1 суперпози­цией ранга s — 1 с помощью элементарных суперпозиций, называется классом функций К 3 суперпозиций ранга s . Суперпо­зициями функций из К 0 называются функции, входящие в какой-то из классов К\ Согласно введенным определениям, можно говорить, что система булевых функций полна. Тогда любую булеву функцию можно представить в виде многочлена от своих переменных. Многочленом Жигалкина называется многочлен, являющий­ся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой сте­пени .

Слайд 16

Теорема : Любая функция булевой алгебры может быть представлена, и притом единственным образом, с помощью по­линома Жигалкина вида J = . Представим, например, виде полинома выражение вида Х 1 v Х 2 . Для этого проведем следующие рассуждения. Пусть Х 1 v Х 2 = а Х 1 Х 2 + b Х 1 + сХ 2 + k , где а , b , с, k — неопределенные коэффициенты. При Х 1 = Х 2 = 0 имеем к = 0. При Х 1 = 1, Х 2 = 0 имеем b = 1. При Х 1 = 0 , Х 2 = 1 имеем с = 1. При Х 1 = Х 2 = 1 имеем а + b + с = 1, т. е. а = - 1 . Таким образом, получаем: Х 1 v Х 2 = - Х 1 Х 2 + Х 1 + Х 2 . Пусть дана булева функция f ( x 1 … x k ) . Функция f* ( x 1 … x 1 ) на­зывается двойственной если f* ( x 1 … x k ) = Двойственной к f ( x 1 ) = 0 является f ( x 2 ) = 1 и , наоборот, двойственной к a v b , является а ^ b и наоборот. Функция называется самодвойственной , если f ( x 1 .. x k ) = f '( x 1 .. x k ). Функция называется линейной , если f( ) = a 0 + a 1 х … + a k x k , где a i { 1,0}. Функция называется монотонной , если для любых из списка переменных таких, что , имеем f ( ) f ( ). Множество К булевых функций называется функционально замкнутым , если вместе с функциями из этого класса он содержит все их суперпозиции. Справедливо следующее утверждение: никакая полная сис­тема булевых функций не может содержаться в функционально замкнутом классе отличном от класса К 1 всех булевых функций. Функционально замкнутыми являются следующие классы: Т 0 — класс функций, сохраняющих 0 ( f(0 , 0, ..., 0) = 0); Т 1 — класс функций, сохраняющих 1 ( f ( 1, 1, ..., 1) = 1); S — класс самодвойственных функций; L — класс линейных функций; М —класс монотонных функций. Теорема Поста: Для того чтобы система бу­левых функций { f x , f v … f m } была полной, необходимо и доста­точно, чтобы для каждого из классов Т 0 , Т 1 , S , L , М нашлась функция f i не принадлежащая этому классу.

Слайд 17

Докажем, например, полноту системы {+, V, 1}. Составим таблицу Поста (ниже): в клетках таблицы будем писать + или - в зависимости от того, принадлежит рассматриваемая функция выбранному замкнутому классу или нет. Согласно теореме Поста, для полноты системы необходи­мо и достаточно, чтобы в каж д ом столбце был хотя бы один минус. Следовательно, рассматриваемая система полна. Система функций W называется независимой, если ника­кая функция f W не представляется суперпозициями фун­кций из множества W \ { f } . Независимая система функций на­зывается базисом функционального замкнутого класса К, если всякая функция из К — суперпозиция функций из W . Например, система функций {+, •, 1} независимая, так как + • , 1 , + L, • L, 1 L, + , • , 1 f S L M A + B + - - + - A v B + + - - + 1 - + - + + f S L M A + B + - - + - A v B + + - - + 1 - + - + +