Математическая логика. Шапорев С.Д (1019113), страница 15
Текст из файла (страница 15)
Известно следующее. если Пети не видел Котю на улице, то либо Кол» ходил в «ино, либо Петя сказал правду; если Коля не ходил в кино, то Петя не видел Колю на улице, и Коля сказал правду, если Кола сказалэ правду, то либо он холил в кино, либо Петя солгал. Выясните, лодел ли Кол» в кино? 1.2!.17. Четыре друга Антонов (А), Вехов (В), Сомов (С) и Деев (Д) решили провести каникулы в четырех разных городах — Москве, Одессе, Киеве и Ташкенте. Определить, в какой город должен поехать каждый из них, если имеютса слелующие ограничения.
1) Если А не едсг в Москву, то С не едет в Одессу. 2) Если В не едет ни в Москву, ни е Ташкент, то А едет в Москву. 3) Если С не едет в Тшнкент, то В едет в Киев 4) Если Д не едет в Москву, то В не едет в Москву. 5) Если Д не едет в Одессу, то В не едет в Москву. 1.21.18 В школе, перешедшей на самообслуживание, четырем старшекчассникам: Андрееву, Костину, Савельеву н Давыдову поручили убрать Казш 1. Аззара лажи )злшб виеказыважвй 7-й, 8-й, 9-й н 1О-й классы. При проверке оказалось, что 1О-й юысс убран плохо. Не ушедшие домой ученики сообщили о следующем: ! ) Андреев: "Я убирал 9-й класс, а Савельев — 7-й".
2) Костин; "Я убирал 9-й класс, а Андреев — 8-8". 3) Савельев: "Я убирал 8-й класс, а Костин — 1О-й". Давидов уже ушел домой. В дальнейшем выяснилось, что каждый ученик в одном из двух высказываний говорил правду, а во втором ложь. Какой класс убирал каждый учеиик7 Глава 2 Исчисление высказываний* 2.1. Язык, система аксиом и правила вывода исчисления высказываний Исчисление выскюыеаний как з)юрмальную теорию можно опрелслггн, с гюмощыо аксиомагичсскаго методд который характеризуется следующими тремя частяьги.
1, Явная формул правка исходных аксиом той ияи иной теории. 2. Явная формулировка правил вывода, используемых Л,ы ззоследователы ного построения этой теории. 3. Использование искусствешю построснпьщ формальных языков дл» изло- жения всех теорем рассматриваемой теории. В понятие исчисления входят такие коипоиенты, как формальный язык исчисления, аксиомы исчисленгщ и правила нывода. Онн позволжот дать строгое математическое определение понятии локазагсльсгва и ~золучить точные утверждения о ыэзьгожности или невозможности доказательства тех нининых предложений теорив. В любом исчислении ращнчают си~паксические и семантззчсские вопросы исчисления. В синтаксической части изучают понятие доказательства 1тсория доказательств), в семантической — струкгуру форьзальных языков (теоргзя моделей).
Исчисления позволяют формализовать многие разделы математики и других Наук. Исчисление высказываний — это аксноматичсска» логичсскан система, описывающая тождественно истинныс схемы, а ес интерпретация — алгебра высказываний. 'Изл эом нс нмк ьем мэ щсэ эт к чщсм и Н.и Гэысьсэ Ч г Г. М г млщщесяая логика Описание всякого исчисления включает в себя описание его алфавита, формул, являющихся конечными конфигурациями символов, аксиом и правил вывода.
Миолгсство абстрактных букв называется аафпенлмм. Консчньгй ряд написанных друг за другом букв алфавита нвзывается слпаом в этом алфавите. Слово, не содсрзкащее ни одной буквы, называетс» нусвгым и обозначаетсв символом Л. Два конкретных слова п,пд..п, и Ьда..Ь„ алфавита А равны, если а, =Ь,, ат =Ь,,, а„=Ь„. Если а,а ..пав слово алфавита А, ссыпя~гасе из л букв аыа,...,а„, то число и называется длиной этого слова. Два слова ц и В определяют слово аб, которое получается приписыванием к слову а слова б. Слово аб называется соедпяениен слав а и б.
Очевидно, что для любых слов а и б имеем Ла=аЛ=а, аЛБ =аб. Слово а алфавита А называется «одсяоепн слова б этого же алфавита, если В =Чай для некоторых слов у и Ь. Можетоказаться что В =у«Ь = у аЬ, и у и у,. Вэтом случае голорято различных вхождениях подслова а в б. Алфавит исчисления высказываний состоит из объединения чстмрсх множеств о=а, Оозоп, ъэог, тле о, =(а Ь,,т,г(,В„...,У„), о, = (гчч,— ь, У о, = ((,)„), и» = (! -). дРУгих аимполов в алфавите исчисление высказываний не содержит.
буквы мнохгества а, называются лролтнцпопппгьльглгп перемелнымп. Символ ~ — нюываетс» сциеолон следования. Форму.гой псчпщтеггпя еысказылпннй называется слово алфавита исчисления высказываний, удовлетворяющее слелующим условиям: Е Пропозиционаяьная переменная является формулой, котора» называется пленен марной, или пмпмарпой. 2. Если А и В формулы, то (ААВ), (АчВ), (А-»В) и А — тоже формулы Никакое другое слово формулой исчислени» высказываний не «власте».
Из этого опредаеенгг» следует, что (А ч В)л С вЂ” не формула, т. к, она не имеет внешних скобок Однако в целях сокращения записи очень часто внешние скобки опускают. Подформулогй А формулы В исчисления высказываний назыюется подслово В, »аляющееся формулой. Пиеа д Исчисление еискеэиеания Теорема 2 1 Всниан неатомарнвн формула А исчислении высказываний иредстввнма в одном и только в влвом нз следуюслия видов« (Вл С), (Вч С), (В-+ С) или В ллн одиозна иго определенных формул В в С. Секемщнл «и называние» выражения следующего вида: 1 А«,Аз,,Лч «-Л, где л>О, Л,,дз,,,Лэ,А — любые формулы. Читается "из ЛоЛ,....,Аэ следует А".
четыре группы 1. Е х-«(»-«х) 2. (т — «(у — «)) — «((х — «у)-+ (х — «1)). К 3.хлу-«х; 4. хлу — «у; Х (х — «х) — «((х-«>') — «(1-«хо у)). О5. б. х — «хо у; 7 у-+х««у; 8. (х-«т) — «((у-«х) — «(яму -«!)). «Р. Р. (х- у)- (у .), !Х1,!! 1О х -« х; 1!. х — «х. 2, ьВ Читается " В доказуема". 3 А«,Аз,..., Л„«-, л > О. Читается "система Ао А,,..., А„противоречива" Если формулы исчисления высказываний можно рассматривать как «!юрмы сложиык высказываний, та секвенции ягюкются формами утверждений и теорем, в коюрых можно отчетливо выделить ус човия (посылки! и закл«очеиич. Х,,Х„...,Х, Правилом еь«авда называется лыражеиие вида, где ХоХз,...,Х,,«' — пРоизвольные секвеннии.
ОыРюкение Х называетса иеиосрег«с«лее«г«гым о«еосмтгсм секееинин ХиХз,...,Х, по данному прав«юу вывода. Исчисление высказываний определяется своей схемой аксиом и праеичами вывода. Схема аксиом состоит из одиннаднати формул, поделенных иа Чесж Е Магвма яч я алоиза ,хь( ) Го Гз - =Г Ьт Гз — объединение последовательностей формул, Г(-(Ал В) Г( — (Ал В) 2, ( — удаление коиьюнкции. Т( — А Г(- В 3...,, — ваеление дизъюнкции.
Г)-(Ао В);Гз,А) — С;Г„В)-С вЂ” удаление днзъю пкпн и. Г, и' — В 5. — г — — т — введение имплнкацни (теорема дедукции). Ц-(А -+ Вз Гг)-(А-з В);Гй-А б., — удаление имляикации (прааила заключения). Г, гй'- 7. = — введение отрицания. 1~ — А (2А.2) Г, А(- 8., — удаление отрицания. 21 — А Ц ! — А; Гз( — А 9. ~ — сведение к противоречию. Пй — — правило утончения. (-А Все прапила схемм проеержотся непосредсюаенно.
Правил вывода в исчислении высказываний довольна много. Среди них вмдсляются основнме н производные прааила. Перечислим некоторме ю них, которые впоследствии будем использовать без доказательства. Пусть ГоГт,Гмà — конечные последовательности формул, возможно пусть~о, А, В, С вЂ” любые формулы.
Тогда справедливы слелуюшне правила вмаода исчисления высказываний: улеаа у Исчиспемю еиюаэнеаппд )- 11 — — правило расширения. ' Г,В~-А Г,,А,В,Г,~-С 12. — правило пересзиноьки. ' Гнв,А,Г,~ — С Г,АА,Г,) — С 13. — правиле сокращения. Г,А,Гз~ — С Присина вывода исчисления высказываний формализуют определенныс стандартные логические способы рассуждений. Правило вывода называется доиуспзниылз е исчислении еысказыпаний, если его добапление е исчисление Не расширяет множество доказуемых се клен ций. Оснопиых правил вывода е исчислении высказываний дна: прееило подстанопки н правило простого заключения. Вопи формула Л доказуема е исчислении высказываний, .т — переменная,  — произаольиая формула исчисления еьюказыпанпй, то формула, получающаяся и результате замены п формуле А переменной х исзоду, где она входит е формулу А, формулой В, яеляетсп также доказуемой формулой.
Это пролило подсшсиаекп, Символически оно записыпается так )(А), т.е. есин А(х) выводимая )-А формула, то замена х на В тоже дает еыюдимую формулу, илн 1 — —. ~-) (А) если А(х) доказуема, то А(В) тоже доказуема. Часпзые случаи формулы е е е л ИА) могут быть, например, такие ) (х)м В, ) (у)н у, ) (А)п А, и л 1М Аз) — = ) (А~)т ) (Аз) ) (А) — ) (А), глс под знаком т понимается любой Пз символов гч щ — ь. Эти полстаноеки очеенлоы. Второе ссиоенос праеило еыеола е исчислении высказываний назыпаеюя )- А,) — А — ь В лраегмои просаого зогмючсппя 1ППЗГ Оно имеет еид и (-в читается "если формулы А и АьВ доказуемы, то формула В тоже Часп |.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
