Математическая логика. Шапорев С.Д, страница 7

2) Две переменных. 3) Три переменных. 1.113!. Найти СКНФ для всякой тождественна ложной формулы, содержащей: !) Одну переменную. 2) Две переменных 3) Три переменных. 1.11.12 Построить формулу от трех переменных, которая истинна в том и толысо том случае, когда ровно две переменные ложны.

1.1!.13, Построить формулу от трех переменных, которая принимает такое же значение, как и большинство !меньшинство) переменных. 1.11.14. Построитьформулу у огпеременных х,у,атак,чтобы ( хл) нхлу, х»у их» х. 1.11.15. По данным СДНФА н СДНФВ построить: СДНФ(А»В) и СКНФ(А» В). 1Л1.16.

По СКНФА построить СдНФ А*, где А — формула, двойатвенная к А. 1.11,17. Построить функции, двойственные следующим функциям: 1) Основным логическим операциям и конатаитам О, 1. 2) Функции от трех переменных, равной 1, если четное число переменнык равно единице. 1.11.!8. Показать,что функция ху» хг» уг является самодвайатвенной.

1.11.!9. Сколько имеется самодвойственных функций от и переменных? г, дпгвб а логики ! лгвб вам квэмевнпй! ! Нзб дана прзизвольная несамодвойственная функция. Отождествить у нее переменныс так, чтобы получилась песамодвойстееиная функци» от возмовгно меньшего числа перененнык. Каким может быть зю число? 1Л2. Минимизация булевых функций в классе ДНФ Квртй! Карно" Как было ранее гюказано, произвольная булез» функция может быть представлена в дизыонкгнвной л копъюнктивной нормальной форме. Очевипно, чте среди этих форм будут такие, какие содержат меньшее число перемениЫх,чем исходная.

Визъюнктивная нормальна» форма называется милимаяьной, если она содержит наименьшее число вкождсний переменных по сравнению со всеьги ршносильныыи сй ВНФ. Формула А(хохз,..,,х„) нвзываетсв шп пж апой формулы В(хох„...,.т„), сели А — лравильнав злсмснтарнав конъюнкция и Ал В и В. Импликанта А(х,х,...,х„)=х,.'х, з...х,"з формулы В называется просгной, если после отбрасывания любой переменной из А не получается форыулц являющаяся нмпликантой формулы В.

Пример. Пусть А = ху 2 о худ о х уз о х у" . Найлем все им ил икаю ы и простые иыпликанты этой формулы па табл !. 22 ! Тлблвла !.!Д! Дмаеии К О то чогэиззз-Иззз — фва чу ' а ме мю Част !. Ьсагемагпческае лсгпю Тебляге 1.12.1 (прод жена 1 Табличе 1.11.1 1октмо пге1 Правильнык элементарнык конъюнкций у этой формулы 26, они все привелены в табл. 1 12А. Импликаиты по таблице накодвтсл очень легко; импликант всего семь: т2, ху, «2, «ут, хут, «у2 и хут.

Ктждуто на них можнопроверить аналитически, например, Ал у2 = (худ чху2 ч «ух и ху2)л ут =- - =ХУХУ2 О ХУГУ2 ОХУХРХ и ХУ212 М «Ухо«УХ М У«тт Е Х)— = У«. ИРОСтво ми импликантами ввтжстся формулы ух. «у и «2. Таким образом, сокра- уз»ел г, легеерв логики Ытеб а ем юзм ниа1 эл сипая ДНФ формулы А будет дизьюггкцггей зшх простых импликант сощениая крашенная Д11ФА = ху ч хх ч эт Оиевидно, это всякая булева функция, не равная нулю, предо~а»зяма в виде сокращен крашенной ДНФ. Сшсращенпая ДНФ может содержать лишнис имплиьанты.

у ы удаление которых нс меняет таблицы истинности. Нели улалить -ти лнш. дне импликапты, то пол>»аеп:я ДНФ, называемая жупеловой. Тупнко»а» ДНФ, солержашая наименьшее число ехозкдсний переменньгх высказываний, называется мнлггиа»ыюРДУФ 1МДНФ). Сокращенную ДНФ мо кца получить и с гюмащыо аншппическнх преобразований без таблицы истинности. Для з юго используются три операции 1, Полное склеивание Ах ч Ах =— А(х ох)м А, 2.

Неполное склеивание 1ьт ч Ах и А(х ч «) ч А гч Ах и А г Агч А г. 3. Элементарное поглощение Ах* ч Ан А(х ч1)м А, пп (Ой) Теорама КЯ 1Теорс а Ке г1гю1 Если в СДНФ формулы А згроизвщтзг все возможные операции непшиюга еклеиванн», а затем он»рвани элементарного поглощении, то полувитсн сокращешгая ДНФ, т. е. дпзьюнкпия всщ простьш нмплнкант. рассмотрим формулу А из предыдущего примера. Произведем в ней все возможные операции неполного склсиваии», а зателг элементарного поглощения. Тогда А = хух чхухчхухчху» и = — хт(уч у)чу»(хчх)чхг(гч;) хутчхухчхутчхут иххч утч чхучхухч хухч хухч »у и гх(1 ч у)чу (!ох)чту(1 ч х)ч »ух и — = хх ч ху ч гх (1 ч х) = — ' .ту ч х" ч ух .

Дла получения минимальной дНФ из агар»щенной испо»шуше» матрппа ~варна, имеющая следующую структуру: в заголовки сголбцов матрицы запнсыщютс» конституепгы единииы СдНФ, а в заголовки строк — простые нмпликанты сокращенной дНФ. В матрице звезда»кеми отме»аютс».ш пересе»ения строк и столбцов, дая которыя элемеигарная коньюнкция. стоящая в заголовке строки, входит в констигуенту единицы, стоягг~у~гз в заголовке спшбца. Часгь ! Мвгем пн нв гию Составим матрицу Квайна длк формулы А в табл. 1.12,2. Поскольку формула А дана в виде СДНФ (см. табл.!.! 2.1), матрица будет иметь следующий вид. Теле гще 1.

22.2 В тупиковую ДНФ выбирается минимальное число простых импликант, днзъюикцня которых сохраняет все конституенты единицы СДНФ, т. е. каждый столбец матрицы Квайна содержит по крайней мере одну звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных имплнкант. Затем из тупиковой выбирается минимальная ДНФ. В нашем случае тупиковая Днф равна хх о ух, она же будет равна мДПФ. Вще один, на наш взгляд, более громоздкий способ получения минимальной ДНФ дает использование карт Карно.

Карта Карно содержит 2" кчетск, каждая из которых соответствуог одной из 2л мтзможных комбинаций значений л логических переменных х„х„...,х„. Обычно карта строится в зиле г -г матрицы размером 2 на 2" так, что ее столбцы аютветствуют значениям переменных х„хз,...,хг, строки — значениям перемениык хг„„хг,т,...,х„, а сгюедние клетки отличаются только значением одной переменной как по вертикали, так и по горизантюи. Дл» каждой функции может быть построено несколько рюличных карт Карно.

Дая формулы А, содержащей три переменных, карта Карно может иметь вид, показанный нв рис.!.1 и !.2. В этих картах все клетки, отмеченные скобкой, представляют комбинации соответствующей переменной со значением "единица", неотмечениые клетки соответствуют переменной сс значением "нуль". В карте Карно юзкдая клетка может иметь не более четырех соседних клеток (по горизонтали н по вертикали), поэтому дл» представлению точек, огли- у два г, длщдда лаги«к !алгебра вы анна«на! зщихся только на одну координату, часта бывает необходимо испальзободее удаленные клетки булеза функция мог«не быть представлена на карте Карно выделением кле,е е «оторых она црииимщт значение, равное единице.

Для посграснщ дрпстых импликант берутся всевозможные наборы «леток, образующих нерщины некоторого 2 -куба, т е. 2 точек таких, что пары соседних отличаютсд ровно одной координатой. Совпадающие координаты образуюг набор ,, „,), ц,ц,,а„,), и нужная импликация имеет вид х,'х,,' .ж " ', где х р тперемениая, соответствующая о, . к г Рнс. 1.1 Рщ. 1.2 После просмотра всех пар точек, образующих 1-кубы, нужно персбрагь ~северки точек, входящих в 2-кубы и т. д. Следует отметить, что прктыс цмпликанты находятся только в й -«убах, ие содержащихся в кубах более высокого порядка Для формулы Л(т,у,з)= ху'м.хуанлу.

чхут карта Карно црел. ставлена на рис.1.3. Здесь Л(ООО)=Л(0!0)=Л(011)=А(111)=0, а А(110)=А(100)= Л(00,!)= Л(10!)=1, !кэти «арте лля формулы Л можно выдели гь только 1-кубы, 2 кубов злесь иет ИмеетсЯ три пары точек 11,1,0У(1,0,0), 11,0,0)-(1,0,11 и 11,0,!НО,0,1). отличающихся значением ровно одной коорлинагы.

Скютвеютвующне простые импликанты имеют вид ллл первой пары: хх !или хут н хут =— хз ), лля юо!юй ху и для третьей пары уз. Таким образом, сокращсннаяДНгР будет Равна ху м хз и уа Чл ь Г. Ывгемвгическеял гяя лг Р е. 1.3 После нахождении нростых импликащ построение МДНФ сводится к изучению матрицы Ксайна. На картах Карно простой структуры удается непосредственно нахолшь МДНФ, выбирая те прощые импликанты, которые покры. вают все единицы и имеют наименьшее возможное числа вкождсинй переменных.

В случае нашего примера это дее пары точек: (1,1,0)-(1,0,0) и (0,0,1)-(1,0,1), т. е. МДНФ = хг ч ут В силу принципа двойственности все приведенные рассузкдения могут бызь применены после необходимого преобразования лля нахождения минимальных «оньюнктивных нормальньж форм (МКНФ). 1.13. Проблема разрешимости Все формулы алгебры логики делятся на трн квасса: 1. Тащологии. 2. Тождественно ложные.

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