Математическая логика. Шапорев С.Д (1019113), страница 8
Текст из файла (страница 8)
Другой способ основан на приведении формулы А к КНФ или ДНФ и использовании спецначьного алгоритма, который позволяет определить, является ли данная формула тождественно истинной или нет. Одновременно с этим решаетсв проблема разрешимости. е ! Алгебра л пми !мкебре енскаэива Ф Нмпзепюваннмй алгоритм таков Сначала рассмюриыегсл формула А Еслп А в 1, то задач» решена Бели эта ис тэк, то рассмлтривщтся формула А ради Ам 1, та А в О и задача решена Если это ие так. за А — имполпимаа формулл. Устанпвлспис тозкдсстаеииой иатиниасти фармуззь~ А основано иа следующих теоремах. Теорема ! 9 Дл» того чтобы э.юментарив» днтыопкннн был» заждесздснно истинной, необходимо и восппочно, чтобы в ией содержалась вс.
ремеивав и ее отрицание. Например, х, ах, в! Теорема 1 1О Дла гаго чтобы элемеитарпав коныон кипя была тождественно ложной, щюбходнма н лосзащчно, пабы в пей солержялась пере. псина» и ее отрицание. Здесь та же самое; для одной переменной эта очевидно .глз, . О, дл набора и переменных это )т всрждеиис легко доказмваетсл. Теорема !11 Для того стобы формула плгебры логики А была тождесю лепно истинна, веобхацнмо н достаточно, чтобы любая элементариан дизьюнкцвя, вхоцящав л КНФ А, содержала переменную я ес отрицание. Даьазамсщстса 1, Нсабхобтюслв, Пуан, А = — !. Таз да К1!гр А = — 1 и КНФА в А, л Аз л Аз л ...
л Ае — и 1 и У! А в 1. Так как А, — элементарнаяя лизьюнкцпл, та по теореме 1.7 А, содержит персмспиую и сс ат- рицаиис. 2. Дасгззгзгззатласлзь. Пуать Д содержит переменную и ее отрицание Тогда по теореме 17 Л в1, !=1,п Но КНФА=ПА, и!, Следовательно А — тождественна истинная формула. Теорема! 12 для зого чтобы формул» алгебры логика А была такдаственно ложной, иевбходньго и достаточно, чтобы любая злемевтарняв коныанкции, входащаи в дНФА, солсржава переменнузо и ее агриппине.
Пример. А=!.ту — э.х)л(ху-ту). Пшзучить СДНФ и СКНФ с помощью таблицы истнниости (таба. 113.П и пуюм элементарных пРеобразований Чаво 1. Математическая лспгна Твялияа 1.13.1 Из табл. 1.13.1 сразу получаем СДНФ А н х л у. Из згой жс таблицы видно, что формула А — выполнимая формула. Найдем таперь СКНФ ло формуле СКНФ А=СДНФ А, СДНФА м(хо у)ч(хо у) ч (х лу), СКНФА - =(х л у) и (х л у) ч (х л у) =- (х о у) л о (х л у) и (х о у) и (х ч у) л (х о у) о (х л у) = — (х ч у) л (х и у) л (х ч у). Элементарными преобразованиями исходной формулы получить СДНФ и СКНФ часто бывает значительно сложней, чем из таблицы истинности А ж (хг -эх)л (ху — ь у) и (ху ох) л (ху ч у) н ж (хуч «) о (ху о у) и (ху и х) о (ху л у) и (ху ч .т) л (ху) и ху(хм 1) ж — ху = — х о у — срюу ДНФ и СДНФ СДНФ вЂ” дизъюнкци» элементарных коньюнкций. й ней только одно слагаемое «у, другик нет, Найдем теперь СКНФ, для этого нуягна хоть «аказ-то КНФ.
Например, ху— КНФ, т. к. х н у можно считать элементарными дизьюнкциями. ту и (х ч (у л у)) л (у ч (х о х)) и (х ч у) о (х ч у) о (у и х) л (у и х) и ж (х ч у) л (х ч у) л (х и у). Получеггная СДНФ Л не является тождественно ложной, т.к. входящая в нее злеьгентарная коньюнкция не содержит переменную и ее отрицание. Следовательно, формула А или тождественно истинна или выполнима. СКНФ А не является тождественно истинной, т. к. все элементарные дизьюнкшги не содержат какую-то переменную и ее отрицание '1хким обрзэои, А — выполнимая формула. гдаю 7, Аяеядалсгяяя !алтея а внскаанвачяй) 1Л4. Полиномы Жегалкина' кшшюнкцня ху в булевой атгебре (0,1) совпадает с арнфметнчсской операцгмб умнолюння нвд чнсламн. Обычное арнфьгетнческсе сложенне вывалят за цРеделы множества !01), но можно нспользовать сложение по модУлю 2, раесмотрнм логическую связь, определяемую в табл.
1.14 1. Тядлнни !.!я.! В результате возникает новая логическая операцня, которую мы будем обозначать хЮ у. Жегадкнн И. И. предложил зту логическую связь называть суммой х н у н обозначать х Ю у . Сумма истинна тогда н только тогда, копы нстннно одно н только одно составляющее высказывание, т. с знак б) алесь означает союз "нлн", употребленный в строго разлслнтельном смысле.
Сравннвая таблнпы нстннносгн основных лагнческнх связощ замсгньг, что ха У вЂ” х ч-» у. Подобным зке образом могут быть арнфмепззнрованы все 14 операцнй, ранее рассматривавшихся лля функцнй двух перс ченных. Дла двух введенных операций: ввелснного сложеннл цо модулю 2 н умноже. вня 1конъюгзкцнн) имеют место все основные логические законы: комм)тат~занесть, ассоцнатнвность, днстрнбутнвность умноженн» атяоснтсльно сложення Операцня слаженна па модулю 2 нспсльзусгся в логнческнл функцнях, назы- Ваемых яолвяомани (мягмочленамн) Жеязмкяна. Вбголсчаеяом Жегажила называетсн многочлен, являющийся суммой консгмгпя О нлн 1 н рехзнчгзых одночленов, в которых все переменные входят нс ВЫШе, чем в нервой степени: (!.14.1) 3' 4 зднымчкнычнааясья 1~В69-!9ят! — мм««в с ыи Часы ! Маюмагнчесяае логика причем на каждом наборе (гн!з,...,!г) все г () =1,2,...,!г) различны, вача „.(О4 Подсчитаем число полиночов Жегыкина от переменных Ж,х„...,х„, т.
е число выражений вида (! !4.!). Число членов х„хч...хв равно количеству полмноягеств вида (!!, гз,...,гг ) множества из и чисел (1 2,..., н), т, е, 2" . По- скольку а,, =0 или 1, то общее число многочленов 2 . Так «ак число 3' булевых функций от л перемеинык также равна 2, то каждая булева з' функция может быть предспщлена многочлсном Жеилкина. Заметим, что какова бы ни была булева функция от двух переменных г (х,, х ), ее логическое значение )(ам аз) при любом наборе (аназ) вырзжасюя формулой )(а!,аз)=Г(11)а!аз Ю)(10)а,(! оаз)бз (01)(1гВа!)азй В з' (О ОХ! гВ а! )(1 гВ аз ), !1.14.2) в справедливости которой легко убедитьсн. Рассмотрим несколько примеров. Сначала с помощью таблицы истинности 12 4 2 найдем, как выражытся многочлен Жсгвлкина для х. Твелине !.!42 1. Такимобразом, х=хгВ1.
х1 "' хз — = х! л хз = (х! зо 1)(хз ОЗ 1)Ю! = х!хз гВ х! гВ хз го 1 гВ 1 = = х,хз о х, го хз, То же самое полусытая по формуле !1.14.1); х, ьгхз =ах!хзагйхзчзсхзеИ, при х, =ха=о имеем г) =0; прн х, =О, хз = 1, к =1; при х, = 1, хз =О,Ь = 1; при .т, = хз =1, а = 1, тогда х, о хз = х,ха !В х, (В хз . удела г, длгедра мгпгли 1алгед а аыеклеиеанид! 2, и охго к, = х охг ох; =!а ог1)(хе бг1)(агре!)Ю1= = х хзх, Ю хзхз бй хетт Ю хз бр х хз Ю х, Ю х, Ю! Ж 1 = х л,лз Э т х, бр Ехх, Юх, Юх, Ю тп !З.змогезчение припадем вновь таблипу ееех булевых функций (табл. 1.14.31 !гадах переменных и нх представление миог очленами Жегалкина, Уаби ца 1 Гг 3 А м1=1, У- ,их=а, уз и х — з у = ту ог х . от = х ч у = ху го х го т о 1, У;мх=хЮ1, Х~ и!'= уй!, Лз х г, у = ху гй 1, Лз - =у -е х = ху гр у он 1. Ут и х о У = ху Ю х ог У, — = хо г'=ту, уе — = у-о х =худ!у, ӄ— и х г — г у = .т бр у, Уо = — хт-г у=л бЗуог!. .Г" му=у у~а =.
х — г у = ху о х Ю 1 ,гп и 0=0 Часи 1 Магемеп ческая логике 1.1б. Полнота и замкнутость функций алгебры логики Система булевых функций С = (Уы Рз,...,г',„) называется поеной, если любая булева функция может быть выражена черщ функции из 6 с помощью суперпозиций. Система Р, — множество всех булевых функций — является полной системой. Теореме 1,12 Пусть ланы две системы функций (1„)г,...,),„) н 18, мтг с...,йг), относительно котоРых известно, что пеРвап система полна н люба» из ее функций может быть вырюкена с помощью суиериознцаи чеРез фУикцми йпйгс...,й .
Тогда система (бой„...мтг) также «в. ляетея полной системой. Докитимелььтео Пусть р — произвольная функция яз Рз. Так как система функций Ы гг -,1„) полна то р = дз(~ы Тз, ., ) ), причем переменных в р может быть любое «онечнсе число ст 1 до гн. Л =Р~(8~ йз,-.,йг) По условию теоремы з ~з(~'уз"'"дг) Теперь функция ф может быть У„=ф (8,,8з,-.,у ) выРажена чеРез системУ фУнкций (йг,йз,...,йе) с помощью сУпеРпознцгю р р(%(йг йз '" Л)грз(рн 82" йг)" ...,Р„,(йпйг,...,й ))= Р(а,йз,...,йь). Таким обРазом, пРоизвсльнаа фУнкция из Р, выражена через функции системы (ймй„...,йг), т. с.
зтв система функций полна. Рассмотрим несколько примеров и докажем полноту следующих систем функций: 1. ),гчч». Полнота втой системы непосредственно следует нз формул 11.9.1) и (1,92). Г, , ч» и ), л». Для доказательства полноты системы 1, ч» воспользуемся теоремой 1.8. Здесь роль системы (Л, Рт,гз) играют функции 1, л, ч». т, Ддлзб ЛОГНКЧ !аятвбРВ ВН Яазиеачнй! аь системы (Кобэ) — фУнкции 1,ч). Тогда У, =Ко уз =Из, Рз--х! мхз =фт(Я~ Яз). рбщиога систеиьг 1,д локазываетс» аналогично с использованием рае. ицсидьнссти ~ н хз н ~ л хз, (з зф,1) — система, связанна» с полнноиами Жегаякина.
Докажтельетво ес полноты проводится анщэогично: возьмем (Ди~з)=1,д), е (К„бз,бз)=(з9,1) гогда поскольку л=хгб1, то !', =ф,(бз,бз) У =быт.е. снстемафУнкций (,ю,1) полна. фаены образом, мы получилп резучьтат, ксггорып можно сформулировать в ниле следующей теоремы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
