Дискретная математика (998286), страница 18
Текст из файла (страница 18)
Интерпретация Пусть А(х„...,х„) —.пропознциональная формула, где хы...,х„— входящие в нее пропозициональные переменные. Конкретный набор истинностных зйачений, приписанных переменным хы ...,х„, называется интерпрепгацией формулы А. Формула может быть истинной (иметь значение И) при одной интерпретации и ложной (иметь значение Л) при другой интерпретации. Значение формулы А в интерпретации 1 будеы обозначать 1(А). Формула, истинная при некоторой интерпретации, называется выполнимой.
Формула, истинная при всех возможных интерпретациях, называется общезначимой (или тавтологией). Формула, ложная при всех возможных интерпретациях, называется невыполнимой (илн противоречием). Пример А ч' А — тавтология, Авг- А — противоречие, А — к — А — выполнимая формула, она истинна при 1(А) = Л. ТЕОРЕМА Пусть А — некоторая формула.
Тогда: 1. если А — тавтология, то А — противоречие, и наоборот; 2, если А — противоречие, то . А — тавтология, и наоборот; 3. если А — тавтология, то неверно, что А — противоречие, но не наоборот; 4. если А — противоречие, то неверно, что А — тавтология, но не наоборот.
Доклзатвльство Очевидно из определений. ТЕОРЕМА Если формулы А и А -к  — тавтологии, то формула  — тавтология. Доказательство От противного. Пусть 1(В) = Л. Но 1(А) = И, так как А — тавтология. Значит, 1(А — + В) = Л, что противоречит предположению о том„что А — к В— тавтология. П 1оз 4Л, Логические связки 4.1.4. Логическое следование и логическая эквивалентность Говорят, что формула В логически следует из формулы А (обозначается А=ЬВ), если формула В имеет значение И при всех интерпретациях, при которых формула А имеет значение И. Говорят, что формулы А и В логически эквивалентны (обозначается А с=в В или просто А = В), если они являются логическим следствием друг друга. Логически эквивалентные формулы имеют одинаковые значения при любой интерпретации.
ТЕОРЕМА (Р -+ Я) е=ь (-Р1гЯ). ДОКАЗАТЕЛЬСТВО Для доказательства достаточно проверить, что формулы действительно имеют одинаковые истинностные значения при всех интерпретациях. ТЕОРЕМА Если А, В, С вЂ” любие грормулы, то имеют место следующие логиче- ские эквивалентности: -(А ч'В) = -Ай В; АйА = Л. Доказательство Непосредственно проверяется построением таблиц истинности. ЗАМЕЧАНИЕ Таким образом, алгебра ((И,Л);Ч,й, ) является булевой алгеброй, которая называется алгеброй высказываний. 1. А1гА = А, 2. АчВ = В'ч'А, 3. А 1г (В 1г С) = (А ~г В) ц С, 4. Аг(ВЙС) =(АгВ)й(А1гС), 5.
(АйВ) ч'А = А, б. АцЛ=А, 7. Ач'И = И, 8. -( А)=А; 9. (АйВ) = -А1г-В, 10. А 1г-А = И, АйА =А; АйВ = ВЙА; Ай(ВйС) =(АЙВ)ЙС; Ай(В ~ С) = (АЙ В) ц (АЙ С); (А ч'В)йА = А; АйЛ =Л; АйИ=А; Глава 4. Логические исчисления ТЕОРЕМА Р,й...йР„=ь Ятогдаитолькотогда,когда(Р,й...йР„) -+ Я— тавтология. ДОКАЗАтЕЛЬСтВО Необходимость. Пусть 1(Р, й...3сР„) = И. Тогда 1Д) = И и 1(Ргй... йЄ— г Я) = И. Пусть 1(Ргй... 3гР„) = Л.
Тогда 1(Ргй... йР„-г Я) = И при любой интерпретации 1. Таким образом, формула Ргй... йр„-ь 9 общезначима. Достаточность. Пусть 1(Ргй... 3гр„) = И. Тогда 1(Я) = И, иначе бы формула Рг й... йр„-ь Я не была бы тавтологией. Таким образом формула Я вЂ” логическое следствие формулы Ргй...
34Р„. П ТЕОРЕМА Р,й...йр„=ьЯ тогда и только тогда, когда Р, й...йр„й-Я— противоречие. ДОКАЗАТЕЛЬСТВО По предыдущей теореме Рг й... 3г Р„=ь Я тогда и только тогда, когда формула Рг й...йР„-+ Я вЂ” тавтология. По первой теореме подраздела 4А.З формула Р, й... 8г Є— ь Я является тавтологией тогда и только тогда, когда формула (Рг й... й Р„-+ Я) является противоречием. Имеем: (Ргй...йР„-+ Я) = ( (Ргй...йр„) ЧЯ) = (Ргй...йр„)й-Я) =Р,й...3гР„3г Я. П 4.1.5.
Подстановки Пусть А — некоторая формула, в которую входит переменная х (обозначается А(...х...)) или некоторая подформула В (обозначается А(...В...)), и пусть С вЂ” некоторая формула. Тогда А(... х... ) (С//х) обозначает формулу, полученную из формулы А подстановкой формулы С вместо всех вхождений переменной х, а А(... В... ) (С/В) обозначает формулу, полученную из формулы А подстановкой формулы С вместо некоторых (в частности, вместо одного) вхождений подформулы В. ТЕОРЕМА Если А(...
х; .. ) — тавтология и  — любая формула, то А(... х... ) (В//х) — тавтология. 105 4.2. Формальные теории ДОКАЗАТЕЛЬСТВО Пусть С: = А(...х... )(В//х). Пусть 1 — интерпретация С (она не содержит х), Пусть Р:=1 0 (х:=1(С)). Тогда Р(А) = 1(С), но Р(А) = И, следовательно 1(С) = И. ь) ТЕОРЕМА Если А(...В...) и В=С, а Р:=А(...В...)(С/В), то А= Р Доклзкткльство Пусть 1 — любая интерпретация. Тогда 1(В) = 1(С), значит 1(А) = 1(Р), Е) 4.2.
Формальные теории Исторически понятие формальной теории было разработано в период интенсивных исследований в области оснований математики для формализации собственно логики и теории доказательства. Сейчас этот аппарат широко используется при создании специальных исчислений для решения конкретных прикладных задач. Рамки книги не позволяют привести развернутых примеров таких специальных исчислений (они довольно объемны), но, тем не менее, такие примеры существуют. 4.2.1. Определение формальной теории Формальная теория Т вЂ” это: 1, множество Я символов, образующих 'алфавит; 2. множество У слов в алфавите Я, 9 с Я*, которые называются формулаии; 3. подмножество З формул, З С У, которые называются аксиомами; 4.
множество й отношений В на множестве формул, В е Х, В с л"+', которые называются правилами вывода. Множество символов А может быть конечным или бесконечным. Обычно для образования символов используют конечное множество букв, к которым, если нужно, приписываются в качестве индексов натуральные числа.
Множество формул У обычно задается индуктивным определением, например с помощью формальной грамматики. Как правило, зто множество бесконечно. Множества А и У в совокупности определяют язык, или сигнатуру, формальной теории. Множество аксиом З может быть конечным или бесконечным.
Еоли множество аксиом бесконечно, то, как правило, оно задается с помощью конечного множества схем аксиом н правил порождения конкретных аксиом из схемы аксиом. Обычно аксиомы делятся на два вида: логические аксиомы (общие для целого класса формальных теорий) и нвлогичвскив (или собственные) аксиомы (определяющие специфику и содержание конкретной теории). Множество правил вывода к, как правило, конечно, 1 Об Глава 4. Логические исчисления 4.2.2.
Выводимость Пусть ею..., Ря, С вЂ” формулы теории Т, то есть Рю..., Г„, С Е У. Если существует такое правило вывода В, В б зс, что (Гы..., Р, С) Е В, то говорят, что рормула С непосредственно выводима из формул Гм...,Г„по правилу вывода В. Обычно этот факт записывают следуюпгим образом: Р'" Р-В С где формулы Рм..., Р„называются посылками, а формула С вЂ” заключением. ЗАМЕЧАНИЕ Обозначение правила вывода справа от черты, разделяющей посылки и заключение, часто опускают, если оно ясно иэ контекста.
Выводом формулы С из формул Рм...,Р„в формальной теории Т называется такая последовательность формул Ям..., Еь что Еь = С, а любая формула Ц (1 < и) является либо аксиомой (Ег б З), либо исходной формулой В (Е, = Р ), либо непосредственно выводима из ранее полученных формул Е~„..., Е,„(л„..., г'„< 1). Если в теории Т существует вывод формулы С из формул Г~..., л„, то зто записывают следующим образом: Р„...,Р„~-, С, где формулы ею..., В„называются гипотезами вывода.
Если теория Т подразумевается, то ее обозначение обычно опускают. Если ~-т С, то формула С называется теоремой теории У (то есть теорема — это формула, выводимая только из аксиом, без гипотез). Если Г ~-т С, то Г, Ы-т С, где Г и Ь вЂ” любые множества формул (то есть при добавлении лишних гипотез выводимость сохраняется). ЗАМЕЧАНИЕ При изучении формальных теорий нужно различать теоремы формальной теории и теоремы о формальной теории, или метатеоремы.
Это различие пе всегда явно формализуется, яо всегда является существенным. В этой главе теоремы конкретной формальной теории, как правило, записываются в виде формул, составленных из специальных знаков, а метагеоремы формулируются ла естественном языке, чтобы их легче было отличать от теорем самой формальной теории. 4.2.3.
Интерпретация Интерпретацией формальной теории Т в область интерпретации М называется функция у: 9' — к М, которая каждой формуле формальной теории Т однозначно сопоставляет некоторое содержательное высказывание относительно объектов множества (алгебраической системы) М. Это высказывание может быть истинным или ложным (или не иметь истинностного значения). Если соответствующее высказывание является истинным, то говорят, что формула еьтолняется в данной интерпретации.
107 4 2. Формальные теории ОТСТУПЛЕНИЕ В конечном счете нас интересуют такие формальные теории, которые описывают какие-то реальные объекты н связи между ними. Речь идет прежде всего о математических объектах н математических теориях, которые выбираются в качестве области интерпретации. Интерпретация 1 называется моделью множества.формул Г, если все формулы этого множества выполняются в интерпретации 1. Интерпретация 1 называется моделью формальной теории Т, если все теоремы этой теории выполняются в интерпретации 1 (то есть все выводимые формулы оказываются истинными в данной интерпретации).
4.2.4. Общезначимость и непротиворечивость Формула называется о6щезначимой (или тавтологией), если она истинна в любой интерпретации. Формула называется противоречивой, если она ложна в любой интерпретации. Формула С называется логическим следствием множества формул Г, если С выполняется в любой модели Г. Формальная теория Т называется семантически непротиворечивой, если ни одна ее теорема не является противоречием.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
