Математическая логика. Шапорев С.Д (1019113), страница 19
Текст из файла (страница 19)
Пусть кояечнв» совокупяость формул (х,,селии,. = 1, Г=~',х,"',...,х,",), где х,"' = — Тогда, если значение (хг, если а, = О. формулы А при наборе п„аз,...,пч иеременныз х„х„...,х„равно 1, то Г~- А, если же значение формулы А прв наборе попс,, п„рвано б, то Г~ — А. Докозамелестео.
Докажем теорему методом математической индукции па длине рассматриваемой формулы. Пусть формула А есть переменив» х,. Тогда, если х,~ =1, то х,~ — х, и х," ~ †.к, т. е. хч ~ — А но Г = (л," ), следовательно Г( — А.
Если же «) =О, то хь =х и хьГ-х,, т.е. х,."~ — А. Аналогично, Г=(л,") ! и Г)-А. Увеличим теперь длину формулы А. Очевидно, что А может иметь один иэ следующих четырех видов: а) Д, б) В, л В, в) В и В, г)  — з Вз, причем по только чтодоызанному лл» 4 и Вз теорема 2.5 справедлива.
Рассмотрим лишь случаи а) и г). а) Пусть А имеет вид В, . Если В>(аппз,...,п„)=1.то В(апас,...,п„)=0 и, следовательно, Г~ — В,, т.е. Г~ — А. Если же В~(онпз,...,п„)=0, то !левад Ис пеленке апов и агмл гав В~(аназ,...,п,)=! и Г)-В, . Продолзким теперь вывод по прввнчам исчзшления высказываний Г:Вы В,-эв,, В, .Но В, =А,тогда)~ — А. г) Пусть А= В, -е Вз.
Если А(аопз,..,,п„)=1, то по свойству имплнкации либо В~(поаз,...,п„)=0, либо Вз(онпз,...,п„)=!. Если В~(аназ,...,п„)=б,то Г~ — В, .Запишем вывалив Г. Г: в„в, — ~в, . в,), Гв, — в,)-4в, — в,)), (г~) ~-вн (вэ П) Гц) -(а, чл,) (вш в -в,-,(в,-,в!)-(в, в,) Гв,-аг) ~в,-(в, вз) ~-в, в,-вз ( ) Г ~-в л в -в гв в ) — з) Гвз в, в, г ~-в, в,-+вэ (в! (Гг, нз) ~-52()вийей. вз) ~-в~ (вш ш) В| (в~ е ) (.В~ вт 11-В, — эВ,.
Если же Вз(онпз,..,,а)=1, 1~-Вг. Тогда вывел нз Г имеет следугащнй вил: Г:Вз, Вз — э(В, — эВ ), В, -эВз . Итак, и а этом свучас вг.вг ~~вез з~ ~~,~~~~,в ) ! (ьИ-вз.,(в, вз) Г) — В, — эВ,. Пунктьз б) и в) этой теоремы докатила~отса аналоги нзо. Предостввллем читателем сделать это салзосто тельно Час«а 1 Маг матковская лоп«ка Теорему!.5 часто применакт дся добавление в вывод из множества Г какой-нибудь сложной формулы, включающей в себя предыдущие члены вывода в качестве составных частей. ° Пример. Дана формула А=(хну)-е(хаз) и наборы значений перемеиньж: а) (1,0,0) и б! (0,1,1).
Записать вывод формул А или А из соответствующей совокупности формул. а) А(1,0,0)=(!оО)-е(1аО)н(1о1) — «(Ол1)м! — «0=0. Следовательно, из множества Г = (х, у, з ~'— А, т. е. 4-Г 5хйтй Г;х у,з х-+х (хну-«хат)-+(хну-«хат), 10 Р|-(-. !.!) ( -1-!) лоу†«(хну †«хат)-«хлх, х †«хчу, хтгу ( *.3 * ..
6'*-*ТО * х-+хлз, хлх,хну — «ха хм А л а ч н ппз ппз "'6:-''"' —— Каждую из формул этого вывода можно было непосредственно поставить в вывод, проверив ее значение на наборе (1,0,0), например, хат =1лО=Ол1=0=1 =1.. = Ко,о) б) А(0 1 1) = (О о!)-+ (О л!) = (О о О) е (1 л О) = Π— + О = 1. Значит, Г= ьт,У,ЗТ-А улаы 2 Исчисленное кг ы ииа гяг Проверим зто. Г.луг,х~)туях)!ту~я)~~~~у)з'ь~) Ь,Г~-, )5.,) 1О, ~! <-,,).1,,-,) ,'--~-+б-,~ 1; -,~ ! б ) г 1-- г х -ь у, г о у -ь !1х и у — ь х л г), х л у 1- У (-*» ! Проверка по теореме 2.5 лля каждого члена приведенного «ыеада ласт аналогичный результат.
например, х -+ у!1,,! —— О ь! =!, х -я (х -ь у ) = Π— з )Π— з !) = ! -ь ! = ! и т. д. 11адО Теорема 2.6, Каждая тыкдесгвеннв пстииаан формула алгебры высказываний доказуема в исчислении высказываний. Догма а в ель сглео. Пусть А — тождественно истинная бгормула алгебры высказываний, а х;,х„...,т„— список всех ее переменных. рассмотрим произвольный набор этих переменных а,,оз,...,о„.
А!х~ ° тз - хя)!й „ следовательно, по тсореме25 Г„~ — А, где Г„=~х,"',хзг,...,хГ ~, причем Г„~ — А на всех 2" различных л-ках чисел (пна„...,пя). Ча ь!. Магемегям гея лелька Пусть Г„, = (~',~*,...,х,'," ), тогда если и„=1, имеем Г„!,х„~ — А, Гьмх„~-А а е случае пя =О Г„„х,1-А. По теореме дедукции Г, „х„)-А . Залил»ем теперь яыаод из Г„,. Г„ »~-х„ -» А Г,,; х„— » А,х, — » А, (х„-» А) -» (1х, -» А)-» А) л,е (х„-» А)-» А, А ю ппз Итак, Г„»~ — А. Точно так же, обозначая через Г„=~',х~',...,х„"т*), получим Г„з~ — А,То!дан Г, =(т,"')~-А. Если п, =1,то (х»11-Л,если же — д) — А х~ — А а, =О, то Тх!)~-А.
По теореме дедукции ~-х! -» А Аналогичный емаод дает !-А, т.е. формула А доказуема а любой соаокупности формул, если она тождсстееино истинна. 2.?. Некоторые алгоритмы проверки выводимости формул в исчислении высказываний Выявление того, что из некоторого множества формул исчисления логически следует другая формула, яаляется по существу одной из ссиоанык задач исчисления аыскззыааннй. Для доказательства аыяодимостн часто используется теорема 2.6. Глава Д и ги л ым енаы н и Л Рнс.
2.1 Алгоритм Каайна Для проверки тождественной истинности формулы А(х„зз,,х„) вспальзуется так называемое семантическое дерева, представляющее собой бинарное одиокорнсвое дерево грпс.2.12 удовлетворяющее следующим условиям: О калозое ребро помечено хк; ГУ ребра, выходящие из одной вершины, соотвезствугот противоположным псреьгенным х, и х,; П ребра соответствуют одной и той же переменной тогда и только тогда, когда они находятся на одинаковом расстоянии от корня. Граф, изображенный на рис.
2,1, имеет 2" висачих вершин, т. с. вершин последнего ряла, и длл проверки тождественной истинности в общем случае нужно исследовать 2" маршрутов от корня до каждой текущей вершины. Алгоритм Квайна позволяет проходить лишь часть дерсла н заключается в последовательном переборе переменных х, и придании нм значений О, 1. Дл» каждого такого набора анализируется таблица истинности формулы А(хп хз,...,х„), пРнчсм эта таблица из-за фиксиРоваиного значеоиа х, содержит меньшее число переменных.
гзв Часть ! Мягемвпнесявя ломив пример 1. А(х,у,х)= (хе т) е ((у — ь г)-+ (хо у -» г)). Пусть х = 1. Тагд» формула А преобразуется следующим образом: А(1, у х) = (1 — ь х) — з ((у -+ х) — ь (1 ч у — ь х)) =- (1 ч х)-+ ((у — ь х)-+ -+(1-+х)). 0 значении полученной формулы определенный вывод сделать еще нельзя. Придадим значение у =1, полу щм А(11,2)=(1-зх)ь((1 — ьх)з(1-+т)) — (1 — зт) — ь! — 1. Бели же у=О, то А(1,0,г)=(1-+т) — >((Оех) — ь(1-+т))ж(1-+в) — е(1-е(1ег)). Продолжим вронесс последовательного перебора значений переменных, х=!, А(1,1,1)=(1 — ь1)ь(1-ь(1 — ь1))м1, А(1,1,0)=(1-зО) — з(1-ь(! — «О))мО-з(1-ьО)мΠ— зОм1. Рнс.
2.2 Рассмотрим теперь случай х = О. Получим А(0 у х)=(0 — за)-+((у-+х)е(Очу ьх))-=. = 1 — ь ((у — ь х) — з (у — ь х)) м 1 — ь ! м 1 . Таким обрезом, все рассмотренные случаи приводят к тождественно истинным формулам, и формула А тождественно истинна, а значит доказуема. Па рис. 2 2, а изображен граф, соответствующий формуле, а на рис. 2.2, б его подграф, использованный для проверки выводимости.
Прямер 2. А(х, у)= хл (х — з у)л (х — + у). Придадим значение х = 1. А(1, у) = 1 л (1 — з у) л (1 -ч у) ж (1 ь у) л (1 -ь у); у = 1, А(1,1) = (! -+ 1) е (1 ч 0) и 1 — з 0 и О, Формула А выполнима и не пыводимв из произвольного !может быть пустого) множества формул !рис. 2.3). Глава 2 Нс и нне емсклемеанлй УЗ! Рис. З.з Алгоритм методе редукций Алгоритм метода релукций похож на алгоритм только что рассмотренного метода Клайна.
Г!ри переборе наборов значений переменных исследуемой форчулы используется свойство импликации бьуть лоукной только тогла, когда посылка истинна, а следстлие ложно. Куетод зффекзиеен лля формул, содержащих много имцлнкаций. рассмотрим ту жс функцию А(х,у,г)= (л-ь з) — «((у -ь е) — ь (л у у -ь л)), Предположим, что формуяа А ложна прн некотором наборе переменных (ц,,пз,п,) Тогда по свойству импликацин х-у л =1, а (у -у !) -у(л ч у — ь г) = О, т.
е. у -ь л = 1 и х о у — ь г = О, хзу у = 1, .' = и, = О . Но если .. = О, та л -ус = О и у -у т = О а нс 1, как бььто получено раньше. Данное противоречие говорит о там, по исходное предпололгение о ложнукти формулы А неверно. Таким образом, формула А тождественно иоганна Метод резолюций Рассуягдения, явлающиеся основой метола логического вывода, называемого мемедом резоеоций, заключауотся в сяедующем. Чтобы доказать, что (Ау,АУ,...,Алд-А необхолимо показать, что А, лА, л...лА„— уА— тавтологив. Действительно, пусть Г=(А„А,...,А„).
Так как А, б Г ! =1 н, то Г~ — Д. 1)-А,1)-в По правилу введения коны нкции, т. е. если 11-А„АУ,...,А„, 1)-Алв то Г! — А, лА, л...лД, . Оледовательууо, формулу А, лда л ..лД, можно Г,А~-В добавить в Г. Тогда по теореме дедукции т е. 1) — А-» В тгг Чаем !. Метвиагичемсы логмм Г,А, аА, л...лА„~ — А . Таким образам, если ~ — Л, лЛз л...лА„еА, Г( — щ лА, л...„-„-~А то формула ~ лА, л...лА, — ь Ам1 (тавтология). Введем еще несколько определений.
Пусть А, =А,'иВ, А, =А,'иВ, Дизъюнкт Д' и А,' называется реюльееитой дизъюнктов Л, и А, по переменной В и обозначается через геле(А„~). Резальвентой дизъюнкгов зд и А, называется резальвента па некиюрой переменной и обозначается гез(А,,А ). Если дизъюнкты Ч и ~ ие содержат пратиеопалолгных Псрсыоиимю та рЕЗОЛЬВЕит у НИК НЕ Сущсетеуст. ОЧЕВИдна, Чта ГЕЛ(А,А)мО. Если гее(Л,, зч ) существует, то (А,, Лз ))-гез(Ап Аз). Действ итыгьно, пусть Л, =Аз иВ, ~ =Аг иВ, геле(АоА )идг гА,'. Очепидно, что -1 , и В,Аз иВя-Д и Аз Дая докажтелытва достаточно воспользоваться -1 правилами удаления и введения дизьюнкнви.
! !усть Г = (зц, Лз„, А„) — множество дизъюнктов. Поалелоаательиосгь формул В„Вз,...,В„называется резалюешенмм еыеадаи из Г, если для каждой фориулы В„г = 1, л, выполняется адно из условий: !. В, и Г; 2. БД 1 < 1, такие, что В, = гез(В,, В, ). Теорема 2.7 Гюеаре а а подломе меюада резолюций!.
Множество днзъюнктав Г противоречиво в том и только в том случае, когда существует резолютивный вывод и» Г, заканчивающий нулем. Применим эту теорему дл» проверки вывадамссти формулы А из данного множества формул Г = (А,, Аз,...,Л„). Условие (Аа Аз,..., А„) — А раянссильно условию (Л„Аз,...,Ае,Л! —. Дейатвительно, если (А„Аз,..., А„ й'- А, то А,а Азад, л Л„ -+ А =- 1, тогда, Аз лАз л...лАг иЛ— = О, А, лАз л...лАи аА=О, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
