Лекции мат логика. Курс лекций по элементам математической логике Балашиха 2014 г 1
 Скачать 0.79 Mb.
|
|
§1.7. Функциональная полнота В типичной современной цифровой вычислительной машине цифрами являются 0 и 1. Следовательно, команды, которые выполняет процессор, суть булевы функции. Ниже будет показано, что любая булева функция реализуется через конъюнкцию, дизъюнкцию и отрицание. Следовательно, можно построить нужный процессор, имея в распоряжении элементы, реализующие конъюнкцию, дизъюнкцию и отрицание. Этот раздел посвящен ответу на вопрос существуют ли (и если существуют, то какие) другие системы булевых функций, обладающих тем свойством, что сих помощью можно выразить все другие функции. Введем в рассмотрение ряд классов функций. 1. Класс 0 T функций, сохраняющих константу 0, те. таких функций y=f(x 1 ,x 2 ,…,x что f(0,0,…,0)=0. Например, x y( x). 2. Класс 1 T функций, сохраняющих константу 1, те. таких функций y=f(x 1 ,x 2 ,…,x что f(1,1,…,1)=1. Например, x (yx). 15 3. Класс S самодвойственных функций, те. таких функций y=f(x 1 ,x 2 ,…,x n ), что 1 2 n 1 2 n f(x ,x , ,x ) f (x ,x , ,x ) 4. Класс L линейных функций, те. таких функций y=f(x 1 ,x 2 ,…,x n ), которые могут быть представлены в виде f(x 1 ,x 2 ,…,x n )=c 0 c 1 x 1 c 2 x 2 … c n x n , где с, c 1 , коэффициенты, которые могут принимать значение 0 или 1. 5. Класс M монотонных функций. На множестве наборов из нулей и единиц В) | x i {0,1}, i=1,2,…,n} введем частичный порядок следующим образом (a 1 ,,a 2 ,...,a n ) (b 1 ,b 2 ,...,b n ) тогда и только тогда когда a 1 b 1 , Функция f(x 1 , х 2 ,...,х n ) называется монотонной, если для любых двух элементов из В таких, что (a 1 ,,a 2 ,...,a n ) (b 1 ,b 2 ,...,b n ) следует, что f(a 1 ,,a 2 ,...,a n ) f(b 1 ,b 2 ,...,b n ). Система F булевых функций, суперпозицией которых может быть представлена любая булева функция, называется функционально полной. Говорят, что функционально полная система F булевых функций образует базисв логическом пространстве. Базис F называется минимальным, если удаление из него любой функции превращает эту систему в неполную. Критерий полноты Теорема Поста. Система F булевых функций является полной тогда и только тогда, когда она включает хотя бы одну функцию не сохраняющую константу 0, не сохраняющую константу 1, не самодвойственную, нелинейную и немонотонную. Доказательство теоремы Поста приведено в приложении 1, однако для понимания ее доказательства необходимо ознакомится с главами II и III. В таблице 1.7 приведены свойства, которыми обладают элементарные булевы функции (символ * - отмечает свойство, которым обладает данная функция. 16 Таблица 1.7 Название Обо зн. Не сохрани- мость константы 0 Не сохрани- мость константы 1 Не Самодвойс твенность Не Линейность Не Монотонность Конст.0 0 * * Конст.1 1 * * Отриц. * * * Конъюн. & * * Дизъюн. * * Имплик. * * * * Эквивал. * * * Сумма по модулю 2 * * * Штрих Шеффера * * * * * Стрелка Пирса * * * * * Используя теорему Поста и таблицу 1.7 можно строить базисы из элементарных функций последующему правилу. Выбрав любую элементарную булеву функцию и дополнив ее при необходимости другими функциями так, чтобы все они вместе удовлетворяли теореме о функциональной полноте. Через функции этого базиса можно выразить все другие булевы функции. 1. Система функций S 1 ={ , , } образует базис. Для приведения булевой функции к виду содержащему лишь связки из базиса S1 могут быть полезны следующие эквивалентности y x у, x y (x y)(x y) , y x y x y x , y x y x , y & x y x 17 2. Система S 2 ={ ,&} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S 1 а затем использовать соотношение y x y x 3. Система S 3 ={ , } образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S 1 а затем использовать соотношение y x y x 4. Система S 4 ={1,&, } образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S 1 а затем использовать соотношения y x y x y x , x 1 x 5. Система S 5 ={ } образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S 2 а затем использовать соотношения y x y x , x x x 6. Система S 6 ={ } образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S 3 а затем использовать соотношения y x y x , x x x 7. Система S 7 ={ ,0} образует базис. Пример 1.7.1. Записать функцию x (y z) в базисе S1={ , , }. ) z y z y x ( ) z y z y x ( )) z y ( x ( ) z y x ( ) z Пример 1.7.2. Используя теорему Поста проверить, является ли полной система функций S={f 1 ,f 2 }, где Решение Проверим какими свойствами обладают данные функции. 1. Сохранимость константы 0. f 1 (0,0)=0 1=0 – сохраняет константу 0. f 2 (0,0)= 1 1 1 0 0 – не сохраняет константу 0. 2. Сохранимость константы 1. 18 f 1 (1,1)=1 0=0 – не сохраняет константу 1. f 2 (1,1)=0 0=1 – сохраняет константу 1. 3. Самодвойственность. y x y x f y x y x y x y x f ) , ( ) , ( 1 1 – не самодвойственная. Составим таблицы истинности для функций , ) , ( 2 y x y x y x f и ) , ( 2 y x y x f X Y X Y Y X X Y Y X 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 1 Из таблицы истинности видно, что y x y x f ) , ( 2 y x y x f ) , ( 2 те. f 2 - не самодвойственна. 4. Линейность. Построим полином Жегалкина для функции f 2 методом неопределенных коэффициентов. P(x,y) имеет вид ) , ( 3 2 1 Используя таблицу истинности для f 2 , полученную в п, имеем P(0,0)=C 0 =1 C 0 =1 P(0,1)=C 0 C 2 =0 1 C 2 =0 C 2 =1 P(1,0)=C 0 C 1 =1 1 C 1 =1 C 1 =0 P(1,1)=C 0 C 1 C 2 C 3 =1 1 0 1 C 3 =1 C 3 =1. Итак, f 2 =1 y xy – нелинейна Монотонность. Очевидно, что наборы упорядочены следующим образом (0,0) (0,1); (0,0) (1,0); (0,0) (1,1); (0,1) (1,1); (1,0) (1,1). Проверим на монотонность функцию f 1 : 19 f 1 (0,0)=0 1=0 f 1 (0,1)=0 0=0; f 1 (0,0)=0 f 1 (1,0)=1 1=1; f 1 (0,0)=0 f 1 (1,1)=1 0=0; f 1 (0,1)=0 0=0 f 1 (1,1)=1 0=0; f(1,0)=1 1=1 f 1 (1,1)=1 0=0. Итак, мы получили, что для (1,0) (1,1), не выполняется f 1 (1,0) f 1 (1,1), следовательно функция немонотонна. Проверим на монотонность функцию f 2 (0,0)=1; f 2 (0,1)=0. Итак, для (0,0) (0,1) мы не получили что f 2 (0,0) f 2 (0,1). Следовательно, функция немонотонна. Сведем наши вычисления в таблицу. Функция Не сохр.0 Не Сохр.1 Не Самодв. Не Линейность Не Монотонность f 1 f 2 * * * * * * * * Из теоремы Поста, заключаем, что система , S x y x y – полная. 20 Глава II. Булева алгебра Множество всех булевых в базисе S 1 ={ , &, } образуют булеву алгебру. Таким образом в булевой алгебре все формулы записываются при помощи трех связок , &, . Частично свойства этой алгебры мы рассмотрели в главе I (см, например, основные эквивалентности. В этой главе рассматриваются свойства, специфичные для булевой алгебры и поэтому везде в этой главе мы будем иметь дело только стремя функциями, &, . §2.1. Нормальные формы Нормальные формы являются синтаксически однозначным способом записи формулы, реализующей заданную функцию. Если х - логическая переменная, а σ {0,1} то выражение если если x x или x если x если, называется литерой. Литеры x и x называются контрарными. Конъюнктом называется конъюнкция литер. Дизъюнктом называется дизъюнкция литер. Например, формулы x x y x и являются конъюнктами, формулы x y и z y x - дизъюнктами, а формула z x является одновременно и конъюнктом и дизъюнктом. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конечного числа конъюнктов. Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа дизъюнктов. Более просто ДНФ - это сумма произведений, а КНФ - это произведение логических сумм Примеры. 21 1. x y y z x ― это ДНФ (сумма произведений. 2. z ) y x ( ) z y x ( это КНФ (произведение сумм. 3. w z y x ― это ДНФ и КНФ (одновременно. 4. w z y x ― это ДНФ и КНФ (одновременно. 5. (x x y)·(y z x)·z ― это КНФ. 6. x x y и z y x ― это ДНФ. 7. z y x ) yz x ( x ― это ненормальная форма (не ДНФ и не КНФ). Пусть функция f записана в базисе S 1 . Данная функция приводится к нормальной форме следующим путем 1) используем законы де Моргана, чтобы преобразовать формулу к виду, в котором знаки отрицания относятся только к отдельным переменным 2) применяем правило снятия двойного отрицания x=x; 3) далее использовать законы дистрибутивности, причем необходимо использовать первый закон дистрибутивности для приведения к ДНФ H 1 &(H 2 H 3 )=(H 1 &H 2 ) (H 1 &H 3 ) , и второй закон дистрибутивности для приведения к КНФ. H 1 (H 2 &H 3 )=(H 1 H 2 )&(H 1 H 3 ). Любая булева функция может иметь бесконечно много представлений в виде ДНФ и КНФ. Например, используя дополнительно законы инверсий и правила операций с константами можно добиться, чтобы в каждом отдельном конъюнкте или дизъюнкте любая переменная входила бы не более одного раза либо сама либо ее отрицание. Пример 2.1.1. Для приведения к ДНФ используемый закон дистрибутивности. ) z y ( ) z y x y y x x y x ( ) z y ( ) z y x ( y x ) z y ( z y x y x -это КНФ ) z y ( ) z y x y x ( ) z y ( ) z y x y x 0 ( -это другая КНФ 22 z y x z y x 0 0 z z y x z y x y z y x у x z y x z y x -это ДНФ Пример 2.1.2. Для приведения к КНФ необходимо использовать второй закон дистрибутивности. z ) y x ( y x ) z y x ( y x z y x y x ) y 1 ( ) z x ( ) y x ( ) y x x ( ) z y x ( ) y x ( z y x ) z x ( ) y x ( это КНФ §2.2. Совершенные нормальные формы Если в каждом члене нормальной формы представлены все переменные либо сами, либо их отрицания, причем в каждом отдельном конъюнкте или дизъюнкте любая переменная входит ровно один раз (либо сама либо ее отрицание, то эта форма называется совершенной нормальной формой (СДНФ или СКНФ). Примеры Пусть задана функция трех переменных f(x,y,z). 1. z y x z y x z y x это совершенная ДНФ. 2. ) z y x ( ) z y x ( ) z y x ( это совершенная КНФ. 3. ) z x ( ) y x ( это несовершенная КНФ, т.к. например, в первую сумму не входит переменная z. 4. x y z это совершенная ДНФ. Теорема 2.2.1. 1. Любая булева функция, не являющаяся тождественным нулем, имеет только одну СДНФ, с точностью до расположения членов. 2. Любая булева функция, не являющаяся тождественной 1, имеет только одну СКНФ, с точностью до расположения членов. 23 Доказательство теоремы проведем конструктивно, как решение следующей задачи поданной таблице истинности построить СДНФ. Решение рассмотрим на примере функции f(x,y,z) заданной таблично (таб.2.2) при n=3. Пример 2.2.1. Поданной таблице истинности (таб.2.2) построить СДНФ. Решение. Таблица 2.2 x y z основные конъюнкции f(x,y,z) 0 0 0 z y x 0 0 0 1 z y x 1 0 1 0 z y x 1 0 1 1 z y x 0 1 0 0 z y x 0 1 0 1 z y x 1 1 1 0 z y x 1 1 1 1 z y x 1 Основные конъюнкции (или конституенты_1), включенные в таблицу, соответствуют конкретному набору нулей и единиц, которые принимают переменные x, y, z. Строятся конституенты_1 последующему правилу переменная входит в произведение сама, если на данном наборе она принимает значение 1, в противном случаев произведение входит ее отрицание. Так, например, на наборе (0,0,1) переменные x,y принимают значение 0 и поэтому в произведение входят их отрицания, а переменная z принимает значение 1 и поэтому входит в произведение сама. Для данного набора (0,0,1) конституента_1 равна z y Очевидно, что конъюнкция z y x равна 1 только на наборе (0,0,0), а z y x равна 1 на наборе (0,0,1) и т.д. (см. по таблице. Далее, заметим, что 24 дизъюнкция двухосновных конъюнкций равна 1 ровно на двух наборах, которые соответствуют данным основным конъюнкциям. Например, функция z y x z y x равна 1 только на двух наборах – (0,0,0) и (0,0,1), а на всех других наборах она равна 0. Аналогично, дизъюнкция трех основных конъюнкций равна 1 ровно на трех наборах, которые соответствуют данным основным конъюнкциям и т.д. Т.о. получаем правило для построения СДНФ следует выбрать строки, в которых функция равна 1, а затем взять дизъюнкцию соответствующих основных конъюнкций, получим искомую СДНФ. Так для нашего примера, имеем z y x z y x z y x z y x z Задача Поданной таблице истинности построить СКНФ. Конституента_0 для набора нулей и единиц (которые принимают переменные x, y, z) строится следующим образом переменная входит в дизъюнкцию сама, если на данном наборе она принимает значение 0, в противном случаев произведение входит ее отрицание. Правило для построения СКНФ: следует выбрать строки, в которых функция равна 0, а затем взять конъюнкцию соответствующих конституент_0. В результате получится искомая СКНФ. Так для нашего примера, имеем ) z y x ( ) z y x ( ) z Замечание. Для построения совершенной КНФ функции f, достаточно построить совершенную ДНФ для функции f , а затем использовать f f и законы де Моргана. Построим СКНФ для нашего примера на основании замечания. 1. Строим СДНФ для отрицания. z y x z y x z y x 2. Используем законы де Моргана z y x & z y x & z y x z y x z y x z y x f f 25 ) z y x ( ) z y x ( ) z Описанный способ нахождения СДНФ (и СКНФ) по таблице истинности бывает часто более трудоемким, чем следующий алгоритм. 1. Для нахождения СДНФ данную формулу приводим сначала к ДНФ. 2. Если в некоторый конъюнкт К (те. К это произведение некоторого числа переменных или их отрицаний) не входит скажем переменная у, то этот конъюнкт заменяем на эквивалентную формулу ) y и, применяя закон дистрибутивности, приводим полученную формулу к ДНФ; если недостающих переменных несколько, то для каждой из них к конъюнкту добавляем соответствующую формулу вида ) y y ( 3. Если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ. Замечание Для построения СКНФ в дизъюнкт не содержащий скажем переменную у добавляем формулу вида y y , те. этот дизъюнкт заменяем на эквивалентную формулу и, применяя й закон дистрибутивности. Пример 2.2.2. Построить СДНФ для функции f при помощи эквивалентных преобразований. ) x x ( z y ) z z ( ) y y ( x z y x f x z y x z y z y x z y x z y x z y x x z y z y x z y x z y x z Отступление Вычисление СДНФ имеет не только теоретическое, но и большое практическое значение. Например, во многих современных программах с графическим интерфейсом для составления сложных логических условий используется наглядный бланк в виде таблицы в клетках записываются условия, причем клетки одного столбца считаются |