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

Роль нулевого элемента будет играть нижння грань данного числового множества, т. е. число О, роль единичного элемента — верхняя грань — число А. Закон противоречия и закон исключенного третьего из (1А 1) булуг иметь вид х х = О, х+ х = А.

Тогла множество М отак определенными оперениями н так определенными элементами О, 1 является булевой аггеброй. В там случае, когда множество М состоит из двук чисел 0 и 1, зта система представляет собой алгебру высказываний, в которой истина заменяетса вылслснной единицей,вложь -- нулем. Пусть М и йг — две булевы алгебры.Огображенне « =! х, ставюлее каждому хб М в соответствие элемент х е дГ, называется сомолюрфиэмом булевой алгебрм М вбулеву алгебру гУ, если Г Линза л л яи (алгебра еисказивания! =О'(! в М' втоца М7, 23 х с у, =(хну) (лгззъюыкцг~я элементов в Л( соответствует канзлалкнии этих элементов в М 7; лу =(хо у) (конъюнкция элементов в М совналаег с н«днзъюнкцией в М! булева алгебра М называется деойыиеенлаи к М Очевидно, что (М)-=М 1.7. Функции алгебры логики Формула алгебры логики является функцией входящих в нес эл«ментарных высказываний, ес аргученгы лринимают два значения О и (, лрн т~ом зна ~ение формулы может быть равно О или ! Фулюгией аягеоры логики и л ременных (илн фупкигки Бгегг7 наз~лвгзется функция и логических переменных, г е функцией алгебры логики 7(б,хз, ,«„) от и переменных л;,х„...,.ь„ называется функция, принимающая значения О, (, аргументы которой такзкс лрннимаюз юачсния О, ! Функция / (х„хз,, з;, ) задается своей истин востной таблицей (табл (.7 Ц.

Уа 'л Ия 1.7. Г р(з этой таблицы видно, что ~исло раюичнык дваичньм наборов длины л 'т ~,...,х«конечно и равно 2" йсно, что тавто1югии и тождественно ложные функции аягебры логики пред- ставляют собой постоянные функции, а две рав~ юсюзьные формулы вырывают Чя щ |. Яатюипмиеяаллоюяа одну и ту же функцию. Каждая функция определлетоя таблицей истинности, состоящей из 2" строк, т. е. принимает 2' значений (каждое О или!). Общее г' число наборов из О и 1 длины 2е равно 2 . Это число равно числу рюличных фупк~гий аягебры логики и персменнмх. Функция влгебры логики ~(хн...,х, |,х|,х, |,...,ха) зависит существенным образом от аргумента х„если существуют такие значения а„...а,, а„п„„,ж„переменных х,,х,, х„х,„,,...,х„, что 7(ан...,а, а О,а,,,...,п„) и г (а|,...,а, ! 1.а, н.,,,а„).

В этом слУчае пеРе- ценная х, называется существеггногт, в противном случае — несущеелгеенлой, нли фикммщой. Очевидно, что постоянные функции не имеют еущественнык переменных. Пример. г (х) — функция одной переменной. Ее возможные значения приведени е табл. 1.7.2. ТггМлце |.7.2 7 (х) = 1 (постоянная, не зависит от х, х — финтивная переменнщ), Ях)= О(постоянная, не зависит от х, х — фиктивная переменная), уз(х)=х, уз(х)=х, в (т и /, х — сУЩестыннал пеРеменнаа. Если л = 2, то 2 = 16. Именно столько существует различных функций двух переменных. Перечислим их в таблице истинности (табл. 1.7.3).

Тевлина |. 23 ;- ив г. ллгебла логики 1влгебла и к и иийу Вшразим теперь всс эти фувкции ~ерш зиачеиия аргумситав хиу: 1, и1, и шх;у, гтих, .гкж хлу, .гзж х-+у хаму — зх, лтизт)ч гз УшхьчУ, Дих, ~юих~ У, уциу, Д„иУ, Узмхлт ум ш — у, У„ и у - , У„ и О. Определим теперь операцию супсрпозиции функций.

Интуитивный смысл атой опсрацив состоит в том, ~то в аргументы фуикции подставляются другие функции, иекагорыс персмсииыс могуч атозштсстьлчяться. Пусть С = (Рг (х~ и тз г - * «1 г ) гйз (ь ш ° г гл —. Хз л, ) . зри (хи и хи з...г'„„))— конечны система фуикций алгебры логики. Функция цг иазывастся сулсриозицией лереоло раяга или згешешлариой сшерлозггггисй зув С, соли оца н мажет быть получена одним из следуюшил способов: 1.

Из какой-та функции гр, и С псрсимсиоваиием какой-то сс псромеииой х „иапРимсР ф = Ф( х, ил, з,..., х,, У, хы,, л, г ) . 2. Подстаиовкой иекоторой фуикш~и гр, и С вместо какого-нибудь аргумсита х, вфуикции йз, б С,т.е. тр = гр, (х,, х, „..., л,, гр, (х,, х, „..., х,, ) х, „,,..., .т, „) .

Оуперпознции г ч-1-го ранга являются злемеизариымп суперпозициями фуикций из суцерпозиции г-го ранга, т. с, С1 = 10 / Кажлой форьгулс алгебры логики соответствует сво» функция. Ешш формулы А и В эквившеитиы, то сошвстствуююие им фуикции равиы' гк(хз лз,...х ) = ~л(й,хы...,л'„). Это значит. чзо при всех зиачсииях псрсмеииых х,.к,,,ли зиачспи» у, и ~гг совпадают 1.8.

Разложение булевых функций по переменным рассмотрим вопрос прелставлепия л -мсстиой булевой функции -и ( ч. хы....х,) какойнибудь формулой алгебры высказываиий В водим обозначение: х' = ш о \.. где о — параметр, равпый О или 1 (л, о=0, Очевидна, что л = 1 (т; о=1.

Че юг Магемагнческеялотка георе Эго 1.4. Каждую функцию алгебры логики г(х,, хз,...,х,) при любом ги (1 < т < л) можно представить в следующей формег 2 "", (1,8,1) где днзьюнкцна берегся по всевозможным наборам значений псремеивыз х,х,...,х) Докоэангельснгео. Указанное в теореме представление функции 4(~,~,...,хпх„и,...,х„) называется риэложеяием функции по Эп переменным ц,х,...,х,, Рассмотрим произвольный набор аппз,...,ак значений всех переменных данной функции.

Покажем, что на этом наборе левая и праеан часть формулы (1.8.1) принимают одно и то же значение. Левая часть равна 1(а ма,...,а„), правая 2 Л1(цыцз,...,а„„а„„,,...,ак)= ((аицз,...,ал,ам„.,ц„) т к. а,' =1, если только п=п, если же а ьп, то п,' =О н соотвеютвующее логическое сласюмое можно отбросить. Сяедсмеие 1(разложение по одной переменной). У(хпхы.,.,х„пх„) = т„л г(хпх„...,х„п1)ч (1.8 2) чх„л г(хпх„...,х„пб) В ЭТОМ случае функции г(ХЭ,ХЭ,...,Х, ы1) н у(з'„хз,...,х ~ О) нюыыюгся комионеивгаинрщэгожсинг . Кледсмеие 2 (разложение по всем переменным). (1.83) ~(п --..., „) Очевидно,чтоесли 1(хыхз,...,х„)иб,то ) 2" (1.8.4) Хг ЛХЭ Л...Х„" ~яз.

»„, ва т, ЛлгедРалогики(алгедлэв к э в ннй( 27 Нтак, если функция /(х, т;...т„) не является тозкдсственио ложной функцией, то она мохгет быть выражена равносильной формулой. лредставнжоцгей собой логическую сумчу разяичных произведений вида т"', причем таксе представление единственно. бюрмула(1.8.3) называстсз шаьюнкмнаэай яорзгаэьлоя форной Ее вич может быль знач цельно упрошен Известил, ~та всякая формула ллгсбры логи- «и может бьжь путем жвивалснтных прсобраюваний по формуяам (1 4,13 (1,4.33 свелсца к формуле, содержаоген талька кгзнъюн~гцию н огрицапис няи дизъюнкцию и отрицание. В результате прэвсдсния эквивалентных прсобра. зований могут получиться несколько формул.

однако только одна из ннт будет обл ада зь следу юши ми с во(юаами 1. Каждое логическое слагаемое содсрзкит все переменные. входящие в формулу ((т,,кз,...,х.) 2. Ни одно логическос слагаемое нс содержит алновремсшю переменную н ее отрицание. 3. Все логические слашсмыс в формуле различны. 4. Ни одна лагичсскос слагаемое не содсрзкит одну и ту жс переменную дважды.

Эти четыре свойства наззчва ются гаоншлспгн соаеригслгтггси Если ((з;, т„,х„) залана таблицей истинности, то ооогвстотвуюшая формула алгебры логики «осстанавяивастсв довольна просто. Для всех значений аргументов .т„.т„ ,х„. нри коюрых Г принимает значение!, нужно записать конъюнкцию элементарныт переменных вьюказьшаний, взяв за шеи коныонкции .~;. если х, =1, и х;, если х =. О Днзъюнкция всех записанных гюнъюнкций н будет необходимой формулой О э~~янсонах Д = О мо кно не беспокоиться. т.

к, соатаетствузошсе слагаемое в формуяе будет равно О и его можно отбросить вон ~у условия ( ой м (. Пример Задана ~аблица иотинности (табл. ! 813 функции Р(х, у, ) Тэаяила (.а. ( Чашь /. Мегемапмеашя лопе/а Отсюда Лх,у,з) = хуан хухч дуя ч хух г.туг. Упростим эту формулу. ) (х у, х) и ух(х ч х)ч хя(у ч у) ч хуэ н ухч «хч хух ю ну«их(хч рхх)м ухчх(я гуигчх) и щчх(эту) ю м(ухчх) л/узч »чу) н((у их)л(хи х))л(уч хч у)л(хм хч у/ш м (у ч х) л (хч х) л и ч 1) л (у ч 1) н (у ч х) л (я ч х) н (х ч у) л (х ч х) н и х ч (у л х) и х — + ух.

1.9. Дизьюнктивная и коньюнктивная нормальные формы ФоРмУла хч лхзз л/..ах„'", где а =(ама„,,а„) — какой-нибУдь двоичный набор, а среди переменных х, могут быть совпадающие, называетсз элемениюрлой коиьюняиией, ини «о«ьюи«шаи. Всяка» дизъюнкциа элемеитарнык «онъюнкций называстс» дизьюикшиевой нор«ать»ой форлюй (сокращенно ДНФ). О ней уже упоминалось в следствии 2 теоремы 1.4. Элема//тарная «онъюнкция называется «раеилыюи, если шждан переменная входит в нее не более одною разе, включв» вхождения нод знаком отрицания. Правильнан элементарная коиыонкция называется лолвой относительно переменных Х,х„...,.т„, если кеждея из переменных входит в нее одни и только олин раз. Например, х,х,х,х, — полна» правильна» элементарная конъюнкиия, а Х Х х, — неправильна» эчементарная коиъюнкци». Для любой формулм алгебры логики путем элементарных преобразований можно получить ее ДНФ, причем не единственную (не все формулы в цепочке преобразований будут ДНФ, но многие: именно те, которые содержат лишь операции, ч н л).