Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 7
Текст из файла (страница 7)
Таблицы астияности Аля связок л, илл, не ы вллчсл!. Гл. о. пРедВАРительные МАтемАтическис сведения УПРАЖЦе ИИЯ Из этой таблицы видно, что Р )! ложно только тогда, когда Р истинно, а ),) ложно. Может показаться несколько странным, что если Р ложно, то Р влечет (! всегда истинно независимо от значения 9. Но в логике это обычное явление: если гипотеза ложна, из нее следует все, что угодно. Рассмотрим теперь утверждение Р если и только если )',).
Это утверждение состоит из двух частей: Р если !г и Р только если )',). Вместо Р если 9 обычно говорят если !г то Р— это лишь другой способ выражения утверждения !") влечет Р. Вместо Р только если )',) часто говорят Р только тогда, когда !г. В действительности следующие шесть утверждений равносильны: (1) Р влечет сг, (2) если Р то сг, (3) Р только если 9, (4) Р только тогда, когда )г, (5) (с — необходимое условие для Р, (6) Р— достаточное условие для сг. Чтобы показать, что утверждение Р тогда и только тогда, когда !г (или Р если и только если !г) истинно, нужно показать, что одновременно )Ч влеыт Р и Р влечет 9. Таким образом, утверждение Р вагди и только тогда, когда сг истинно в точности тогда, когда Р и с! либо оба истинны, либо оба ложны. Существует несколько различных способов показать, что утверждение Р влечет 9 всегда истинно. Один из ннх заключается в том, чтобы показать, что утверждение не !г влечет не Р') всегда истинно.
Читателю следует проверить, что не )е влечет не Р имеет точно ту же таблицу истинности, что и Р влечет 9. Утверждение не С! влечет не Р называешься конт рапозицией утверждения Р влечет Один из важных методов доказательства — доказательство от противного, иногда называемое косвенным доказательством илн приведением к противоречию. Чтобы этим методом показать, что Р влечет !г истинно, нужно показать, что )тверждение не )',) и Р влечет ложь истинно.
Иначе говоря, мы предполагаем, что гг ложно, и если яз предположения, что Р истянно, мы сможем получить заведомо ложное утверждение, то Р влечет >4 должно быть истинно. Утверждением, обратным к утверждению естл Р то )',) (или его обращением), называется утверждение если с) то Р. Утвер- ') Г)редподагается, чго связка нв предшествует связке влечет. Таким образоч, правяавпая фразировка етого )твер>кдеккя такая: (нв >г) влечет (не Р).
Вообще не предшествует и, и предшествует или, или предшествует влечет. ение Р тогда и только тогда, когда часто пишут так: если Р то !) и о ранено. а е' ес б о. Заметим, что утверждение и его обращение им еют разные таблицы истинности. упРАЖНЕНИЯ Определение. ХоРоший пример Р " ление вый п име о мальной математической сказываний можно определить как систему т, состоящую из (1) множества исходных символов, ( ) правил о ре б езования правильно построенных утверждений (высказываний), (3) множества аксиом, (4) правил вывода. (1) И х ными символами системы д' являются (, ),— ечное множество символов переменны и ескоиечно , а символ — †к яе. С в л можно трактовать как влечет, им о (2) Правильно построенное утверждение обр у р об аз ется в результ одного или более применений следующих правил: тате од> ( ) Символ переменной является утвержд ением.
а (б) Если А и  — утверждения, то (- — А и А — В) — тоже П А, В С вЂ” утверждения. Тогда аксиомы системы (3) усть, и е)г — это утверждения А1: (А ( — А)) А2: ((А (В-С)) -((А В) (А - С))) Аз: ((-В- — А) ((-В--еА)-В)) я шобпа о. (4) Правилом вывода является схема заключения (ш р ° пепз, т. е. из утверждений р дений (А — В) и А можно вывести утвер- ждение В. Мы будем опускать некоторые скобки, когда это не вызывает недоразумений. Утверждение а в а являет я ре е ся тео смой системы в качестве ее доказательства можно взять , д после овательность утверждений (1) (а ((а — а) — а)) — ((а — (а а)) — (а — а)) полу- чается из А2 при А.=а, В=(а — а) и с=а.
(В) а ((а- а) — а) в силу А1. ()>!) (а — (а а)) — (а а) по схеме заключения из (!) и (В), (!У) а — (а — а) из А1. (У) а- а по схеме заключения из (1В) и ()У). *О 3.1. Докажите, что (-а-- а) а является теоремой си- стемы,К. гл. о. пввдвлгитвльныв мхтемхтичвскин свадвния эпихжнв ния 0.3,2. Таетологией называется утверждение, истинное для всевозможных значений входящих в него переменных.
Покажите, что каждая теорема системы У' является тавтологией. Указание: Докажите это ипдукцией по числу шагов вывода, необходимых для получения теоремы. **О.З.З. Докажите обращение утверждения, сформулированного в упр. 0.3.2, а именно: каждая тавтология является теоремой. Таким образом, простой метод выяснения того, является ли утверждение исчисления высказываний теоремой, заключается в том, чтобы выяснить, является ли это утверждение тавто- логией. 0.3.4. Постройте таблицу истинности утверждения если Р то если 9 то Рт.
Определение. Вулеву алгебру можно трактовать как систему, в которой можно комбинировать переменные, принимающие значения истина и ложь, с помощью логических связок, нефор- мально интерпретируемых как и, или и нет. Формально бдлееа алгебр!) — это множество В вместе с операциями (и), тР (или) и (не). Аксиомами булевой алгебры служат следующие утвер- ждения: Для всех а, Ь и с, принадлежащих В, (1) а + (6+ с) = (а+ Ь) + е (ассоциативность) а (6 е) =(а Ь).с, (2) а+Ь=-Ь+ а (коммутативность) аЬ=6 а, (3) а (Ь+ с) =-. (а Ь)+(а е) (дистрибутивность) а+(Ь с) =(а+Ь) (а+ с). В множестве В имеются два выделенных элемента, ! и О (в наиболее распространенной булевой алгебре они представ- ляют соответственно истину и ложь), подчиняющиеся следующим законам: (4) а+О=а а 1=а, (6) а+ а=1 а.а= О.
Правилом вывода явлнется замена равного равным. *0.3.3. Покажите, что следующие утверждения являются тео- ремами в любой булевой алгебре: (а) 0=1, (б) а + (Ь а) =- а + 6, (в) а=а. Какова неформальная интерпретация этих теорем? 0.3.0. Пусть А — множество. Покажите, что У(А) — булева алгебра, если операциями +,, и служат О, () и дополнение относительно универсального множества Л, ээ0.3.7. Пусть  — булева алгебра и цЬ В=а. Покажите, что п =-2 для некоторого натурального числа т. 0.3.3.
Докажите индукцией, что и (л+!) 1+2+... +а= 0.3.0. докажите индукцией, что (1 ) 2+ +л)з р+ 2е ! ., +ле *0,3.10. Что неверно в следующем рассуждении? Теорема. Все кошки одного цвета. До к аз а тельство. Пусть Л вЂ” множество, состоящее из и кошек, л . 1. „Докажем" иидукцией по л, что все кошки в А одного цвета. Базис. Если и =1, то все кошки в А, очевидно, одного цвета. Шаг индукции. Предположим, что если А — любое множество, состоящее из а кошек, то все они одного цвета.
Пусть А' — мно. ж ство, состоящее из и+1 кошек, л) 1. Выбросим из А' одну е. з п кошку. Тогда у нас останется множество А", состоя!цее нз кошек, которые по предположени!о индукции все одного цвета. Выбросим из А" вторую кошку и вернем туда ранее выброшен- ну ю.
Снова имеем множество, состоящее из и кошек, которые по предположению индукции все одного цвета. Так как две выброшенные кошки должны иметь один и тот же цвет, то мно- жество Л' должно состоять из кошек одного цвета. Таким об- разом, в любом множестве, состоящем из а кошек, все оня одного цвета. () "О.ЗЛ1. Пусть ?? — полный порядок на множестве А и 5(а)— утверждение об элементе аЕА. Предположим, что если 5(6) истинно для всех таких 6~а, что 6??а, то 5(а) тоже истинно. Покажите, что тогда 5(а) истинно для всех аЕА.
Заметим, что это — обобщение принципа простой математической индукции. 0.3.12. Покажите, что существуют только четыре унарных логических связок. Постройте для них таблицы истинности. 0.3.13. Покажите, что существуют 16 бинарных логических связок.
0,3.14. Два логических утверждения эквивалентны, если они имеют одинаковые таблицы истинности, Покажите, что (а) — (Р Р, (~) эквивалентно Р У' — О, (б) - (Р ~/ 9) эквивалентно — Р /~ !г. ГЛ. О. ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СЗЕДЕНИЯ АЛГОРИТМЫ (ЧАСТИЧНЫЕ И ВСЮДР ОП рр ЕЛЕ ННЫЕ) 0.3.15. Покажите, что Р— 1,! эквивалентно — 9 — — Р. 0.3.16. Покажите, что Р- )г эквивалентно Р,'~-9- ложь. е0.3.17. Множество логических связок полно, если для любого логического утверждения можно найти эквивалентное утверждение, содержащее только эти логические связки. Покажяте, что (уч, -) и (чГ', -) — полные множества логических связок.
Замечания по литературе Черч [)956! н Мендельсон [)9681 написали хороепне учебники по мятемзтнческой догяке '). хвлмоюу [!963) прннвдчежнт удачное введение н будевы алгебры. 0.4. АЛГОРИТМЫ [ЧАСТИЧНЫЕ И ВСЮДУ ОПРЕДЕЛЕННЫЕ) Понятие алгоритма — центральное в вопросах, связанных с вычислениями. К определению этого понятия можно подойти с разных сторон. В этом разделе мы обсудим неформально термин алгоритм и укажем, как получить более формальное определение. 0.4Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
