Математическая логика. Шапорев С.Д (1019113), страница 4
Текст из файла (страница 4)
При эюм рассужлсннс называюся пратпьюя и, если из коныонкпии посылок следует заключение, т е. всякий раз, когда все посылки истинны, заключение голее истпнзю. Правило вывода заключения Ры Р„..., Р„ в этом случае можно записать в виде ' '-', где Р, Р,Р, -- посыл- Члсп 1 Ыаг магкческеялопна гл Доказательстао иыполнается по следующей схеме А -+ В м (Аъ В) — ь (С л С) н (А л В) — ь (С л С).
01.4.5) Приведем е заключение еще дие более простые схемы даказательстаа от про- тнаного: А — ьВн Ал — ьА, А-ьВм л — ьВ 01.4.6) 1.5. Практическое занятие 8)йй 1. Алгебра высказываний 1.5.1. Среди следующих предложений еылелить те, которые яелшотся аьюказыааниями, и установить, если зто еозможно, истинны они или ложны. !) Дляпроизеольныхмножесте А и В еерноакяючение Ас АътВ. 2) Сумма углов а треугольнике равна ! 80'. 3) ад тт. 4) Солнечная система насчитывает девять больших планет. 5) Па улице светит солнце. б) Летайте салюлещми Аэрофлота! 7) Всякое подмножество конечного мнажестю конечно. 1.5.2. Даны деа аысказыеаннж 1) р = ( число 3 яеляетсяделитилеч числа!74 ), 0 = ( идетдшкць ).
В чем заключаются аьюказыаання Р, Р ни Рл0, Рад, Р— ь Гц Р ~-» 07 2) р =( конъюнкция коммутатиана ), 0= ( если число простое, то оно нечетное ). Один из способое доказательстаа математических предложений — метод доказательстаа от противного. Предположим, что некоторое угаерждение а форме ичпликации А — э В ложно. Тогда необкодима прийти к прстнеоречию, т. е. доказать, что лругое утверждение С одновременно выполняется и не выполняется. г-гала г, ллгеврл лшлхв !ллшдлв вы юяыеаллй) В чем заюночаютая высказывания «, « -«р, (р л «) — «р, (г) м р)-««? Какие из этих высказываний ис«инны, а какие лал ны? ! 5,3. Какие из следУ«аших \твсРжлсний Явлаютса выскюываниамн и какие из высказываний истинны и какие ложны? 1) Сумма корней приведенного квалратноп» уравнения равна свобод.
наму члену. 2) Сумма корней любого приведенного квачратного уравнения равна свободному члену. 3) Существует приведенное квадратное уравнение, сумма корней которого равна свободному ш«сну. 1 5.4. В каких случаях приведенные ниже данные праги ворсчнвьи !) л=1, илЬы!; 2) л ыО, олЬ =1; 3) и ы1, им Ь= О; 4) о =О, имЬ=.1, 1.5.5. Определить, является ли данная последоватсш,ность формулой.
И (А, л А«)А« Аз ' 2) ((А, — » ~«)л А ); 3) (А„-» ( ) — »»( о А,; 4) г( л А, -«А, АП 5) (.( — » А,) г (»4 -«А, л А, ) 1.5.6 Выписать все падформулы слелуюших формул; и ((А, -«,5 ) л (,( -» А,))-«А, ' А,, 2) (А, — «А«) с-«(А ьч А,); 3) А л(А, г А, л(ВмС)) 1.5? Проверить, не составляя таблиц истинности, явля«шея ли следующие Формулы тождественно истинными !) р-+ р; Часы | Маюмапжаслаллогича гл 2) р -+ р л (р — » р л р); 5) (р ч р)-» р. 1.5.8. Известно, гго х — » у имеет значение 1. Что можно сказать о значениил з — » (х — » у) х х-» у -» у, (х — » у)-+ - ч 1 5.9.
Составить таблицы истинности дан формул !) (Д - А,)л(Д и А,); 2) Ц (А, А,)) ((А, А,) Ц А,)); 3) (Р г-» Д) — + (Р л Д) ! 4) (Р г (Д -» Р))ч Р; 5) (Р л (() ч Р))л Я вЂ” + Р)ч Д) б) Р -» Д л Р— » Р ч Рч 21 (Рл(Дч Р))г (Я-» Р)ч Д); 8) (Р— » Д)ч(Р— »(Ял Р)) ! .5.10 Доказать выполнимость формул. 1) Р-+ Р, 2) (Д вЂ” » Рл)2)л Рч )2 — » Д, 5) (Р-» д)-»(а — » Р).
1.5.1!. Какие из высказываний РЯ,)2 должны быть истинны, а какие ложны, чтобы формула (Рч Р л !4) — » )2 была истиннойз 1.5.12. Доказать тожлестаеннуго истинность формул: 1) Р- (а-» рла)1 2) (Р— » »А) — » ((Р -» »2) — » Р): 5) (Р-»Л)- ((д-ч)2)-ь(род- )2)); 4) (й — » Р) — » (Р ч й — » Рч )2)! 5) 1у — » Р) — » (Я вЂ” » Р) — » Д)! 1-„даа 5.
Дмнб логнни )алгебра еыскяенванн 3 6) Р— «),Р— »ф; 1) 1Р-» О)-«((~-~ И)-е(Р-» )7)). 6) Р-» Р 1 5,!3 При каких значениях переменных Р, !5, )1 сяедуюшие формулы лоя ныу )(( а- ) В )) а, 3)1!Ро д); Л)-А»)Р г О)л) Р г я)), 3)(Р" Д) 4)(Рл~ч(РлД)) 1.5.14. Доказать, что: П Если формулы Рн ц«и Ро Я тождественно истинны, то формула йо Л тождественно истинна. 3) Если формулы Р ц» и )7~ ») то»кдественно истинны. то формула Р-» )!тождественно истинна. 3) Если формулы РнΠР— »)1, з) — » И' тождественно истюшы.
то формула )7ч Иг тождественно истинна 1.5Л5. Скаггько имеется различнык 1т е. отлнчмащихсх истинное»ными п«6- лицами) лвумсюных логически«операций" 1.5.16. Выразить все осноаиыс операции через когжгонкциго и отрицание„через днзьюнкцюо и отрицание. 1.5.17. Пуси имсетсх некоторан логическая операция ф пад простыми высказываниями А»,А«...., А„. Операция З с точноспю ло равцосплыюсти характеризуется истинностной табницен Например, воз«не » !табл.1.5 1) некоторую »гонкретную операцию нал тремя просгымп вьюказыванияии. П Яж Н 1.5.1 20 Часть ! Лигеывгнчеея я по кю Тогда операцию, имеющую данную истинностную таблицу, можно получить, перечисляя ситуаггни, в которых высказывание Е истинна, т.
е. (гь л А» л А )о ( ( л А л А, )о (гд л А, л Аэ )и (Дз л А, л А, ). Обобщить приведенную «онструкцию на случай произвольных логических операний Е. 1.5 ! 8. Доказать следующие равносильности: 1) А-+В— = Ал В; 2) Ал(АоС)л(ВзгС)м (АлВ)о (Ал С)! 3) АлАмА; 4) А т (В л А) и А; Я Ао(Вл С)м(Атг В)л(АоС); 6) (Ал В )г((АтгВ)л(АнВ))м Ао В; 7) Ао Вм АлВ. 1.5 Э 9. Доказать, что лля любой форыулы существует эквивалентная ей формула с тесными отрицаниями, т.
е. формула, в которой нет символа -+ н отрицания относятся только к пропозициональным переменным. '(.6. Алгебра Буля Равносильности (!.4.3) говорят о том, что алгебра логики обладает коммутативным, ассоциативным в дистрибутивным законами точно так же, как алгебра чисел. Это значит, что нвд формулами алгебры логики можно производить те же преобразования, что и в алгебре чисел (раскрывать скобки, выносить общие множители и т. д.) Однако здесь есть и дополнительные возможности, основанные, например, х л (у о х) и — х) на формулах (!.4.1) и (1 4.2), типа з. ч)=1, — законы по* хтг(у ля) их~ глощения, законы де Моргана и др Эти новые возможности позволяют сделать несколько обобщений в виде интерпретаций формул алгебры логики. Представим непустое множество М элементов любой природы 34 = (о, о, г...), на когором определены две двуместные операции: х,у =к х-у — умножение и х,у =к хе у — сложение и одна одноместная 1-дава г длгеб логнян (эл еср е аэы и л) 2! сдардция к=э .х — отрицания и выделены два элемента О и 1 е М.
причем дда этих операций и элементов выполняются следующие аксиомьь дт о= о+ д) 1, ~ — коммутативный закон. о б= б.о о+ (о+ т) = (о+ о)+ г) 2. — ассоциативный закон. (о+ о) я = (д с)+(о т) ! 3. 1 — дистрибутивный закан. (д б)-ь л=(о+я) (б-г 2); о+д=д — законы идемпотентности. д о=о 11.6 1) о+ о= д. б! — законы лс Моргана. о б=о+б~ 4. х = х — закон двойного отрицания. о+(б. о) = д — законы поглощения о (о ч- о) = б Тогда такое множество М нюывается 6).щсддг олгсорон Если пал основными операциями "+", "", " " "=" понимать дизъюнкпию, конъюнкцию, отрицание и равнооильность то из !)юрмул (1 4 1) ()А 3) видно, что нсе аксиомы булевой алгебры выполнлзатсн Б таких случанх говорят, что имеется ысяернреягонн» (молсль) данной системы аксиом. нзак, алгебра логики — интерпрпщция ю~гсбры Буля. Моэкно было бы при опрелелснии булевой юпсбры исходить из одной днумсстной операции, например умножения доопределив другую при помощи законов де Моргана Булевы аагсбры «ызяююя примерами аксиоматически зщщнного алщбраического объекта.
Зги обьскгы прсдстааляют собой мноэксства, в котсрь|х вылслеиы некоторые эззементы (напримср О и 1) и определены искоторыс операции. Эти элементы и операции долягиы уловлстворюь коне ~ному гмбору аксиом Существуют и нные пело~ щеские мио.кесзва, также образующие алгебру Буля. Например, извссзиая интерпретация — юория множеств, а 'ч.", ".", ' — объединение. пересечение и дополнение в теории мгюжеств. 'Мсгь !.
Мвгю агичв ав липла О, (м х — (л =х, (1.62) =хну, =«ау хи у хлу лла всех х уи М. Нижние индексы у 0 н 1 указывают, в какой алгебре они являются выделсннмми элементами. )юли гомоморфюм х =э х устанавливает взаимно однозначное соответствие ме:кду М и йг, то он называетс» нзоморфнэмолт булевьп алгебр М и У, а сами булевм «лгебрь~ в этом случае назывмотся гиолгорй)лмлгп. Примеров изоморфизма булевых влгебр очень много. Первый пример — алгебра вмсказываний и алгебра множеств. Другой вюкный пример изоморфизма относится к самой алгебре высказываний.
Аксиомы (1.6Л) булевой алгебры таковы, что если всюду поменять местами 0 и 1, дизыонкцию и коныонкпню, то получится та же аксиоматика. Пусть М вЂ” булеза алгебра. Построим новую булаву алгебру М', которая булет состоять из тех же элементов, что и М, но с другичи операциями. Злемснты х, у,... из М, рассматриваемые как элементы М', будем обозна- чать х',у',..., элементы О, (лля М' — через О,, 1,. Тогда положим !. О, = Г (О в М' — зто 1 н М ); Укюкем еще одну систему, удовлетворяюжую (1,бй). Пусть М вЂ” ограниченное множество действительных чисел х таких, что 0 < х< А, Ам О. Положим я = А — х, х+ у = гнал(х, уд х у= в!и(х,у).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
