Лекции мат логика. Курс лекций по элементам математической логике Балашиха 2014 г 1
 Скачать 0.79 Mb.
|
|
§2.3. Минимизация ДНФ методом Квайна Каждая формула имеет конечное число вхождений переменных. Под вхождением переменной понимается место, которое переменная занимает в формуле. Задача заключается в том, чтобы для данной булевой функции f найти ДНФ, представляющую эту функцию и имеющую наименьшее число вхождений переменных. Если х - логическая переменная, а σ {0,1} то выражение если если x x называется литерой. Конъюнктом называется конъюнкция литер. Например, формулы x x y x и y x являются конъюнктами. Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза (либо сама либо ее отрицание. Формула f 1 называется импликантой формулы f, если f 1 — элементарное произведение и те. для соответствующих формулам функций справедливо неравенство f 1 f. Импликанта f 1 формулы f называется простой, если после отбрасывания любой литеры из f 1 не получается формула, являющаяся импликантой формулы f. Пример 2.3.1. Найдем все импликанты и простые импликанты для формулы f=x y. Всего имеется 8 элементарных произведений с переменными хи у Ниже, для наглядности, приведены их таблицы истинности 27 x y x y y x y x y x y x x y x y 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 Из таблиц истинности заключаем, что формулы y x , y x , y x , x ,y— все импликанты формулы x y, а из этих импликант простыми являются формулы x и у (формула y x , например, не является простой импликантой, поскольку, отбрасывая литеру y , получаем импликанту x ). Сокращенной ДНФ называется дизъюнкция всех простых импликант данной формулы (функции. Теорема 2.3.1. Любая булева функция, не являющаяся константой 0, представима в виде сокращенной ДНФ. В примере 2.3.1 функция, соответствующая формул x y представима формулой которая является ее сокращенной ДНФ. Сокращенная ДНФ может содержать лишние импликанты, удаление которых не меняет таблицы истинности. Если из сокращенной ДНФ удалить все лишние импликанты, то получается ДНФ, называемая тупиковой Заметим, что представление функции в виде тупиковой ДНФ в общем случае неоднозначно. Выбор из всех тупиковых форм, формы с наименьшим числом вхождений переменных дает минимальную ДНФ {МДНФ). Рассмотрим метод Квайна, для нахождения МДНФ, представляющей данную булеву функцию. Определим следующие три операции 1. операция полного склеивания f ) x x ( f x f x f ; 2. операция неполного склеивания x f x f f x f x f ) x x ( f x f x f ; 28 3. операция элементарного поглощения } 1 , 0 { , f f x Теорема 2.3.2 (теорема Квайна). Если исходя из СДНФ функции произвести всевозможные операции неполного склеивания, а затем элементарного поглощения, тов результате получится сокращенная ДНФ, те. дизъюнкция всех простых импликант. Пример 2.3.2. Пусть функция f(x,y,z) задана совершенной ДНФ z y x z y x z y x z y x z y x f . Тогда, производя в два этапа всевозможные операции неполного склеивания, а затем элементарного поглощения, имеем ( ) ( ) ( ) ( ) ( ) f x y z z y z x x y z x x x z y y x y z z z y x z y x z y x z y x z y x y x z x z y z y y x z y x z y x z y x z y x z y x y x z x z y z y y x ) z z ( y ) x x ( y z y x z y x z y x z y x z y x y x z x z y z y y x y z y x z y x z y x z y x z y x z x Таким образом, сокращенной ДНФ функции f является формула y x·z. На практике при выполнении операций неполного склеивания на каждом этапе можно не писать члены, участвующие в этих операциях, а писать только результаты всевозможных полных склеиваний и конъюнкты, не участвующие нив одном склеивании. Пример 2.3.3. Пусть функция f{x,y,z) задана совершенной ДНФ z y x z y x z y x z y x f 29 Тогда, производя операции склеивания, а затем элементарного поглощения, имеем z x z y y x ) y y ( z x ) x x ( z y ) z z ( y Для получения минимальной ДНФ из сокращенной ДНФ используется матрицаКвайна, которая строится следующим образом. В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк — простые импликанты из полученной сокращенной ДНФ. В таблице звездочками отмечаются те пересечения строки столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца. Для примера 2.3.3. матрица Квайна имеет вид импликанты z y x z y x z y x z y x y x * * z y * * z x * * В тупиковую ДНФ выбирается минимальное число простых импликант, дизъюнкция которых сохраняет все конституенты единицы, те. каждый столбец матрицы Квайна содержит звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импликант. В качестве минимальной ДНФ выбирается тупиковая, которая имеет наименьшее число вхождений переменных. В примере 2.3.3 по матрице Квайна находим, что минимальная ДНФ заданной функции есть y x z Замечание Для построения минимальной КНФ функции f, достаточно построить минимальную ДНФ для функции f , а затем использовать f f и законы де Моргана. 30 § 2.4. Карты Карно Другой способ получения простых импликант формул с малым числом переменных (и, значит, нахождения минимальной ДНФ) основан на использовании так называемых карт Карно. Карта Карно - это специального вида таблица, которая позволяет упростить процесс поиска минимальных форм и успешно применяется, когда число переменных не превосходит шести. Карты Карно для функций, зависящих от n переменных, представляет собой прямоугольник, разделенный на 2 n клеток. Каждой клетке диаграммы ставится в соответствие двоичный n- мерный набор. Значения заданной функции f из таблицы истинности вносятся в нужные квадраты, однако если клетке соответствует 0, то обычно она остается пустой. В таб.2.4.1. показан пример разметки карты Карно для функции, зависящей от трех переменных. Нижние четыре клетки карты соответствуют двоичным наборам, в которых переменная x принимает значение 1, четыре верхние клетки соответствуют наборам, в которых переменная x принимает значение 0. Четырем клеткам составляющим правую половину карты, соответствуют наборы, в которых переменная y; принимает значение 1 и т.д. В таб.2.4.2. приведена разметка карты Карно для n=4 переменных. таблица 2.4.1. 31 таблица 2.4.2. Для построения минимальной ДНФ производится процедура склеивания "1". Склеивающимся значениям "1" соответствуют соседние клетки, те. клетки отличающиеся лишь значением одной переменной (на графическом изображении разделенных вертикальной или горизонтальной линией с учетом соседства противоположных крайних клеток. Процесс склеивания "1" сводится к объединению в группы единичных клеток карты Карно, при этом необходимо выполнять следующие правила 1. Количество клеток, входящих в одну группу, должно выражаться числом кратным 2, те. 2 m где m=0,1,2,... 2. Каждая клетка, входящая в группуиз 2 m клеток, должна иметь m соседних в группе. 3. Каждая клетка должна входить хотя бы в одну группу. 4. В каждую группу должно входить максимальное число клеток, тени одна группа не должна содержаться в другой группе. 5. Число групп должно быть минимальным. Считывание функции f по группе склеивания производится следующим образом переменные, которые сохраняют одинаковые значения в клетках группы склеивания, входят в конъюнкцию, причем значениям 1 соответствуют сами переменные, а значениям 0 их отрицания. Приведем шаблоны, которые помогают строить покрытия 1 (переменные считаем теми же, но их писать не будем. Для упрощения записи мы не будем 32 отмечать переменные, хотя сохраним их обозначения как ив таблицах 2.4.1, 2.4.2. Приведем шаблоны для n=3, которые помогают строить покрытия единицы (1). Приведем шаблоны для n=4, которые помогают строить покрытия единицы (1). 33 Пример 2.4.1. С помощью Карт Карно, построить МДНФ и МКНФ функций заданных вектором своих значений. 1) f(x,y,z)=(1011 0101); 2) f(x 1 ,x 2 ,x 3 ,x 4 )=(1011 1111 1011 1100). Решение 1) Занесем данные в карту Карно. Удобно сначала отметить клетки, где функция равна нулю. Функция f равна нулю на наборах, являющимся двоичными разложениями чисел 1,4,6 (т.к. отсчет начинается с 0). Таким образом, f(0,0,1)=f(1,0,0)=f(1,1,0)=0. 34 z x y x xz f − min ДНФ. Для построения МКНФ, построим МДНФ для функции f : z y x z x f − min ДНФ f . Переходя к функции f, получим ) )( ( z y x z x z y x z x f f – min КНФ. 2) Заносим данные в карту Карно. Получаем, что f(0,0,0,1)=f(1,0,0,1)=f(1,1,1,0)=f(1,1,1,1)=0. Далее, Сначала смотрим, есть ли покрытия из 16 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 8 клеток. Смотрим, есть ли покрытия 1 из 8 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 4 клеток. Смотрим, есть ли покрытия 1 из 4 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий четыре. Таким образом, все 1 стали покрытыми. Далее, смотрим можно ли убрать некоторые покрытия, так чтобы все единицы остались покрытыми. Убрать некоторые покрытия нельзя. Производим считывание функции 3 2 4 3 3 1 3 2 x x x x x x x x f – МДНФ. 35 Для построения МКНФ Функции f , построим сначала МДНФ, функции 4 3 2 3 2 1 x x x x x x f – min ДНФ f . Переходя к функции f, получим ) )( ( 4 3 2 3 2 1 4 3 2 3 2 1 x x x x x x x x x x x x f f – min КНФ. Замечание Для построения минимальной КНФ функции f, достаточно построить минимальную ДНФ для функции f , а затем использовать f f и законы де Моргана. Глава III. Алгебра Жегалкина Множество булевых функций, заданный в базисе Жегалкина S 4 ={ ,&,1} называется алгеброй Жегалкина. Основные свойства. 1. коммутативность H 1 H 2 =H 2 H 1 , H 1 &H 2 =H 2 &H 1 ; 2. ассоциативность H 1 (H 2 H 3 )=(H 1 H 2 ) H 3 , H 1 &(H 2 &H 3 )=(H 1 &H 2 )&H 3 ; 3. дистрибутивность H 1 &(H 2 H 3 )=(H 1 &H 2 ) (H 1 &H 3 ); 4. свойства констант H&1=H, H&0=0, H 0=H; 5. H H=0, Утверждение 3.1.1. Через операции алгебры Жегалкина можно выразить все другие булевы функции 36 x=1 x, x y=x y xy, x y=1 x y, x y=1 x xy, x y=1 x y xy, x y=1 xy. Определение. Полиномом Жегалкина (полиномом по модулю 2) от n переменных x 1 ,x 2 ,…,x n называется выражение вида с n x n c 12 x 1 x 2 … c 12…n x 1 x 2 …x n , где постоянные с к могут принимать значения 0 ли 1. Если полином Жегалкина не содержит произведений отдельных переменных, то он называется линейным ( линейная функция. Например, f=x yz xyz и полиномы, причем второй является линейной функцией. Теорема (Жегалкина). Каждая булева функция представляется в виде полинома Жегалкина единственным образом. Приведем основные методы построения полиномов Жегалкина от заданной функции. 1. Метод неопределенных коэффициентов Пусть P(x 1 ,x 2 ,…,x n ) - искомый полином Жегалкина, реализующий заданную функцию f(x 1 ,x 2 ,…,x n ). Запишем его в виде P= с n x n c 12 x 1 x 2 … c 12…n x 1 x 2 …x Найдем коэффициенты с к. Для этого последовательно придадим переменным x 1 ,x 2 ,…,x n значения из каждой строки таблицы истинности. В итоге получим систему из 2 n уравнений с 2 n неизвестными, имеющую единственное решение. Решив ее, находим коэффициенты полинома P(x 1 ,x 2 ,…,x n ). 2. Метод, основанный на преобразовании формул надмножеством связок { , &}. Строят некоторую формулу Ф надмножеством связок, реализующую данную функцию f(x 1 ,x 2 ,…,x n ). Затем заменяют всюду подформулы видана, раскрывают скобки, пользуясь дистрибутивным законом (см. свойство 3), а затем применяют свойства 4 и 5. 37 Пример 3.1.1. Построить полином Жегалкина функции f(x,y)=x y. Решение 1. (метод неопределенных коэффициентов. Запишем искомый полином в виде P= с Пользуясь таблицей истинности x 0 0 1 1 y 0 1 0 1 x y 1 1 0 1 получаем, что f(0,0)=P(0,0)= c 0 =1, f(0,1)=P(0,1)= c 0 c 2 =1, f(1,0)=P(1,0)= c 0 c 1 =0, f(1,1)=P(1,1)= с Откуда последовательно находим, c 0 =1, с, c 2 =0, c 12 =1. Следовательно x y=1 x xy (сравните с утверждением 3.1). Метод преобразования формул) Имеем y x x 1 1 )) 1 y ( x ( y x y x y Заметим, что преимущество алгебры Жегалкина (по сравнению с другими алгебрами) состоит в арифметизации логики, что позволяет выполнять преобразования булевых функций довольно просто. Ее недостатком по сравнению с булевой алгеброй является громоздкость формул. 38 Глава IV. Высказывания. Предикаты §4.1. Высказывания При построении алгебры логики мы использовали функциональный подход. Однако, можно было бы построить эту алгебру конструктивно. Сначала определить объекты изучения (высказывания, ввести операции над этими объектами и изучить их свойства. Дадим формальные определения. Высказыванием назовем повествовательное предложение относительно которого можно однозначно сказать истинно оно (значение И или 1) или ложно значение Лили) в конкретный момент времени. Например, простое число, нажата клавиша «Esc»» и т.д. При помощи связок не, и, или, если то, если и только если (им отвечают операции « », «&», « », « », « » соответственно) можно построить более сложные высказывания предложения. Так строится алгебра высказываний. Для упрощения записи сложных высказываний вводится старшинство связок « », «&», « », « », « », что помогает опустить лишние скобки. Простые высказывания назовем пропозициональными переменными. Введем понятие формулы. 1. Пропозициональные переменные являются формулами. 2. Если А, В формулы, то выражения А, А В, А В, А В, А В являются формулами. 3. Формулами являются только выражения, построенные в соответствии с пунктами 1 и 2. Формула, принимающая значение И при всех значениях пропозициональных переменных называется тавтологией тождественно истинной формулой, общезначимой формулой),а формула, принимающая значение Л при всех значениях пропозициональных переменных называется 39 противоречием или невыполнимой).Если формула не является общезначимой и невыполнимой, то она называется нейтральной. Описание свойств алгебры высказываний аналогично описанию соответствующих функций в булевой алгебре и мы их опускаем. Пример После обсуждения состава участников предполагаемой экспедиции было решено, что должны выполняться два условия а) если поедет Арбузов, то должны поехать еще Брюквин или Вишневский; б) если поедут Арбузов и Вишневский, то поедет и Брюквин. Требуется установить, кто из перечисленных сотрудников войдет в состав экспедиции. Решение. Назначение в экспедицию Арбузова, Брюквина и Вишневского будем обозначать буквами А, Б, В соответственно. Тогда условие а) можно записать в виде А Б В, а условие б) в виде А&В Б. Так как оба условия должны выполняться одновременно, то они должны быть соединены логической связью и (конъюнкция равна 1 только водном случае, когда все переменные равны 1). Поэтому принятое решение можно записать в виде формулы L=(А Б В)&(А&В Б) эта формула должна быть истинной. Следовательно, для решения задачи можно построить таблицу истинности формулы L и найти значение пропозициональных переменных А,Б,В на которых формула L равна 1. А можно построить СДНФ или СКНФ и естественным образом сделать заключение. Однако, далее применим искусственный подход, с целью записать компактный ответ к задаче. Подвергнем формулу L равносильным преобразованиям, получим L=( А Б B)&( B & A В)=( А Б B)&( А В Б). Применяя к последнему выражению второй закон дистрибутивности, получим L= А [(Б В)&(Б В )] = А [Б (B& В )] = А Б=A Б. |