Математическая логика. Шапорев С.Д (1019113), страница 3
Текст из файла (страница 3)
Формулы алгебры логики С памоюью яогичсских операций над высказываниями молгно строить различные новые, более сложныс выскюьнгания Обычно при этом порядок операций указывается скобками. Определим поныне формулы логики высказы- Гар Ы р сцз )б р)ззяз — !961З вЂ” авя яс«яь«мы вт вх Ча гь 1. Маюмвшческвялогике га ваний. Пераой частью любой формальной системы являетая ее язык. ь!тобы определить язык, нужна прежде всего определить алфавит и ега спмеояы. Алравиягам будем называть любое непустое мнол<ество.
Элементы этого множестаа называются симеалами данного ктфавита. Любая конечная последовательность символов алфавита называется славам, кли еырагееиие, данного языка. Алфавит логики высказываний содержит такие символы: высказывания — буквы латинского алфавита с индексом или без него, логические свЯзки гчч, — ь,г-», , Раздсаители(,).
Слово в алфавите логики высказываний называется фориулай, если оно удовлетворяет следующим условиям. 1 Любое высказыеанне (выакюывательнсе переменное) — формула. 2. Если А и В формулы, то А, А л В, А ч В, А-ь В, А <-~  — тоже фор- мулы. Вадгроуьш атой формулы А называется любое падслоео А, само яеляющееси формулой. Таким образом, нз приведенною формального определения формуяы как определенной конструкции языка алгебрм логики можно определить более простое понятие формулы.
Исякае сложное высказывание, «аторое может быть получено из злементарнык высказываний с помощью логических связок, называется формулой алгебры логики. Формулы алгебры логики обозначаются большими буквами латинского алфавита А, В, С, При этом скобки можно опускать, придерживаясь аледующик правил: конъюнкция выполняется прежде еаего, дизьюнкцня выполи»- ется второй, импликация и зкеимленци» равноправны и выполняются последними.
Какие» формула алгебры логики принимает спас логическое значение, «оторса определяетая логическими значениями акодящих я нее элементарных высказываний. Например, составим таблицу истинности для формулы (х -э у)-е (х л у и х — + у). Получим табл. 1Э,1. тая. «и 1.дг Глава 1. длг б а логики !алгебра амсщзияяиий1 г! Вали формула сгютоит нз и элементов, то ее таблица истинности состоит из 2л строк. Приписывание значений истиниосги илн лоэкноези высказываниям, вхоля- щим в формулу, называется ыанернрюианней юох высказываний. Под интер- претацией формулы понимается приписывание шачений истинности выска- зываниям, входящим с эзу формулу 1.4.
Равносильные группы формул и равносильные преобразования Две формулы алгебры логики А и В нюываются ргзлг гэсггтьэгызгзг, если онн принимают одинзковые логические згючення при яюбом наборе зиа ~еннй входящнк в формулы элементарных высказыаящззд Равноснлыюсзь обоша чается знаком =-. Очевиднгч например, .тих, .\ ч з = — х нт, д. 1.
Основные равносильности. 1.1. Ал Л - =А — закон идсмпозентности коньюнкцви 1,2. А ч А и А — закон идсмпотсн гнссти дизъюнкцни. 1.3. Л ° 1иЛ, ! — ззстгнга 1.4 Ач1и! 1.5. А л Π— О, Π— ло»гь. 1.6. А и О = А 12. Л л Л =- Π— закон прозиворечи» 1.8 А и А †= ! — закон исключенного третье~а.
1.9 А =— Л вЂ” закон снятия двойного отрицания. (1 4 !) Макду понягщем равносильности и знаком эквнвалеигзюстгз т-э сущестлуег щ~едующая связь. если ~юрьзуяы А и В равносильны, то формула .! оэ В принимает значение ! при всех значениях переменных, и обрюно: если Зюрмула А ьч В принимает зиа ~ение ! при всех зна ~ениях входящих в нее высказываний, то формулы А н В равносильны.
т. е А и В. При этом глслует помнгггь, по знак ьо являсюя символом бюрчкзьно~о языка, с похзгэщмо которого строятся формулы а символ и заменяет слово "равносильно'. Для любых формул А, В. С снраоедлпвы слсдуюнгие равносильг~осзи Чаем 1 Ыагемлпм сюя лагняе 1.10. Ал(ВоЛ) А — первый закон поглощения. 1.11. А о (В л А) — А — второй закон поглощения. 1.12 Л =— (Л л В)ч (Ал В) — первая формула расцгеплени». 1 13 Л и (А о В)л (А о В) — вторая формула расщепления. Все эти соотношения легко проверяются по таблицам иатинностн.
2. Равносильности, выражающие одни логические операции через другие. 21. АеэВм(АэВ)л( — эА)и(АлВ)ч(АлВ)~~ оВ)луйоА) — сановная формула доказательств теорем существования. 22 АэВм Лай и(АлВ). 23 АоВнА — эВиАлВ 2 4. А л В и (А — э В) = Л о В (!.4.2) 2.5. Лл В и Л ч  — первый закон де Моргана*. 2 б, А и В и А л  — второй закон де Моргана. 2.7. Л л В и А о В 28. АоВмАлВ. Именно из равнссильностей этой группы формул следует, что всякую фор лгулу алгебры логики можно заменить равносильной ей формулой, содержащей только две логические операции: конъюнкцию и отрицание нли дизьюнкцию и отрицание. 3. Равносильности, вырюкающие основные законы алгебры логики. 3.!. А л В В л А — коммугативный закон конъюнкции. 3.2.
А и В и Во А — коммутативный закон дизьюнкции. 3.3. А л (В л С)м (А л В)л С вЂ” ассоциативность конъюнкции. (1.4.3) 3 4 Лм (В о С)м (Ач В)о С вЂ” ассоциативность диэъюнкции. 35. Ал (В о С) (Лл В)ч (А л С) — дистрибутнвность коггыонкцни относительно дизъюнкции. З,б, А и (В л С) и (А о В)л (А о С) — дистрибутивность лиэъюнкции относительна конъюнкции. 'О и М е (ля мелею)йэсг ~зтэ) — мю лсомнэт вил улаш т, длгеб л логики !алгол вм я а валид> гэ Рассмотрим несколько примерое л)и (х -е у) л (у -+ т) — з (з -ь т) и (т ч у) л (у ч З) — > (т ч =Г,.б.*>.Р *!х=бэ».~ г~!.*!г и (х л у >)ч ((у л ляг ч и) и (х и )и (у и )ч у>х г х) — «ч(злу ч зч(улх)ж хч -.
хлхлх — ь ул у — > ,-)ох ч(ул т)ч(улт)м ( и(хлΠ— ~Оьх)гхо(ул )ч(гг ) (хлΠ— ьОэх) з (у г)и — (хлΠ— зе) хч(т г) Очхчзч(улт)и — = 1'. х; (у л з) н1 ~ (у г ) и!, 2. 3, доказать равносильность !хч » л (хи у! — = т. (хчу) л (хчу>=-хлх ч улх ч хлучулу=- л >' =- х л !1ч у ч у > =- л'11 ч Пи х. ° хч тлх ч х Приведем теперь несколько отодних равносильностей к правил, с помощью которых мозкно переходить другим.
дгобак из раинссильностей легко может быть показана с помпщыо таблиц истинности. Часто равнссильносгь произеольиой формулы логики высказыааиий экономнее доказыеать без составления таблицы, с помощью логиисского рассуждения и упрощения формулы с использованием приведенных равносильностей. При этом обычно операции эквнаапентнсстн и импликации заменяют операциями конъюнкции и лизьгонкпии, а отрицание относят к злю ментарным еыс казы ваннам.
Можно еще упростить запись формул, опуская некоторые скобки и используе старшинство логиясских связок. Кроме того, знак отрицания, стоящий над формулой, делает излишними скобки, е которые она заклюиена. Отношение равносильности есть отношение эквивалентности. Оно рсфяексивно, т. к, дл» любой формулы А: Ам А; снмнегриино, т к.
для любых формул А и В: если Аж В, то В в = А; транзитиено, т к дл» любых формул А,В С:если Ам В и Вп С,то А и С. Ге Чщ 1 Ма вм ьмескеялщике Теоркип 1.1. Пусть Ам В н С вЂ” произвольная формула. Тогдп А в = В, АлС ВлС, СлАмСлВ, АЧСаВчС, СчАмСчВ, А-гСмВчС,С вЂ” +АиС вЂ” эВ,АьчС=— Вч-»С,СьчАиСьчВ. Докажем, например, форлгулу Л ч Си В ч С. Так как А — = В, то при одинаковом набора входящих ь них простых высказываний А и В приниммот одпнаковыс .чогические значения. Пуать, например, это будет 1. Пусть прн том же наборе значение С равно О.
Тогда обе части рассматриваемой равносильности прнннлгают одно и то же значение 1 ч О = — 1 ч О . уеорема 1 д Пусть А= В и С вЂ” формула, в которой выделено адно вхождение переменной х,. Пусть С(А) получаетс» нз С заменой этого вчоищеннп т, па А,а С(В) — из С заменой того же вхождения х па В. Тогда С(А) — = С(В), Оставим данную теорему без доказательстее, отметим только, что лигбой симеол алфаеьпа может несколько раз появиться е данной формуле. Каждое такое появление называется вхождением этого символа е формулу.
уеорема 1.3. Пусть С(А) — формула, салернмщая А в качестве своей подфармулы. Пусть С(В) получается нз С(А) заменой А я этом вхождении не В. Тогда, сели А= — В, то С(А)м С(В). Формула А называется мааглалогией (тождественно истинной), если она принимает значение 1 при асех значениях вхолящнх в нее переменных. Формула А называется мождесгнеенно ложной или лрамиеаргчивоц если она ранна О при всех значе~щя» входящим в нее переменнык. Формула А называется выполнимой, если при каком-то наборе скалящих в нщ переменных она принимает значение 1. Формула А называетоя онроеерлсимой, если при каком-то наборе входящих е нее переменных она принимает значение О.
С точки зрения логики тавтологии это логические законы, т. к. они принимают истинные значения при любом наборе переменных. В практических вычислениях часто исполюуют слсдугощие тавтологии (А, В, С вЂ” ароизаольные формулы). 1. А ч А — гепщщ пов1ащг — закон исюгючен ного третьего. 2. АьА.
3. Л -ч ( — г А). 4. (А — ч В)щ (( — ч С) — г (А ч С)) — пенное рассужаение. Глава !, Ллгеб а логики !алгеб а высказывания! (А — з (В -з С)) о ((Л -з В ) — ь (А — з С)). б. (АлВ)-эА. (ЛлВ)-ь 8 7. А — э (В -з А л 8) б. А — ь (Л о В)  — з (Л о 8) 9.
( — з А)-» ((В -ь А) — ь 8). !О. ((Л -з В)-з А)-ь А — закон Пирса . П.4 4! ки, причем запись Р,Ры..,,Р„оопимвсжя как Р л Р, ° ..ь Р„. Р— заключение. Л-з В,Л Л вЂ” з В,В Распространенные схемы прявнлыюо, рассузкденпй В Л Легко проверить, что фориулм ((Л -з 8) л А) — з В и ((Л вЂ” ь В) л В)-ь Л являются тозкдественно истпнными. г!аггриыер логические значения послед ией при всех наборах аргумеито» припедены а табл. !4.!. тлел че гмВ 3тн формулы тоже можно легко проверить по таблипам при произвольных значениях А, В, С Прп доказательстве угзмр кдепий различных мюоьгатнчсских теорий обычно используют рассуждения, котэрые на языке логики можно выразить формулами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
