Центральная Научная Библиотека |
|
|
|
|
|
|
Главная |
|
|
Тавтология или тавтологически истинное высказывание - это высказывание со сплошными И в его столбце его истинностной таблицы. Высказывание q называется тавтологическим следствием (из) высказываний p1,…,pn, если в истинностной таблице высказываний p1,…,pn,,q столбец q содержит И в любой строке, которая содержит И во всех столбцах p1,…,pn. Например, построенная выше таблица показывает, что: ØpÞqÙØr - есть тавтологическое следствие из Øp, qÙØr; Ør, q являются тавтологическими следствиями из qÙØr; r есть тавтологическое следствие из p, Øp.
Теорема об отрицании отрицания: ØØp = p Теорема об отрицании конъюнкции: Ø(pÙq) = ØpÚØq Теорема об отрицании дизъюнкции: Ø(pÚq) = ØpÙØq Теорема об исключении импликации: pÞq = ØpÚq Теорема об исключении эквиваленции: pÛq = pÙqÚØpÙØq Теорема об устранении альтернативы: pÚØpÙq = pÚq, ØpÚpÙq = ØpÚq Теорема о коммутативности конъюнкции: pÙq = qÙp Теорема о коммутативности дизъюнкции: pÚq = qÚp Теорема об ассоциативности конъюнкции: pÙ(qÙr) = (pÙq)Ùr Теорема об ассоциативности дизъюнкции: pÚ(qÚr) = (pÚq)Úr Теорема о дистрибутивности конъюнкции: pÙ(qÚr) = (pÙq)Ú(pÙr) Теорема о дистрибутивности дизъюнкции: pÚ(qÙr) = (pÚq)Ù(pÚr) Теорема о равносильности: р = q тогда и только тогда когда pÛq = И Теорема о тавтологическом следствии: q является тавтологическим следствием из р1,…,pn тттк р1Ù…Ùр Þ q является тавтологией. Эти три теоремы легко доказываются с помощью истинностных таблиц. Арифметический способ записи высказываний: исключаются знаки Þ, Û и вместо Л, И, Øp, pÙq, pÚq употребляются соответственно 0, 1, `p, p q, p + q. Например, арифметической записью высказывания (rÚpÞqÙr) будет . При арифметической записи высказываний с ними можно обращаться так, как будто они обозначают числа 0, 1, а. Логический плюс отличается от арифметического только тем, что 1 + 1 = 1. При этом полезно помнить следующие равенства: p Þ q = `p + q p Û q = p q + `p `q p p = p p + p = p p`p = 0 p + `p q = p + q p +`p = 1 p + p q = `p + q 1 + p = 1 Равенства в левой колонке представляют собой другую запись уже доказанных выше теорем, а равенства в правой колонке устанавливаются непосредственной проверкой с учетом равенств 0 = 1, 1 = 0. Пример. Доказательство тавтологичности высказываний: pÞqÞp =`p + (qÞp) =`p +`q + p =`p + p +`q = 1 +`q = 1 pÞqÞpÙq =`p +`q + p q = + p q = 1 (ØpÞØq)Þ(ØqÞp)Þq = +q =`q p +`q`p + q = `q (p +`p) + q =`q + q = 1 Пример. Выразительная достаточность пар ØÙ, ØÚ, ØÞ. pÙq = Ø(ØpÚØq) = Ø(pÞØq) pÚq = Ø(ØpÙØq) = ØpÞq pÞq = Ø(pÙØq) = ØpÚq pÛq = Ø(Ø(pÙq)ÙØ(ØpÙØq)) pÛq = Ø(ØpÙq)ÙØ(pÙq) pÛq = Ø((pÞq)Þ Ø(qÞp)) Доказательство последнего равенства: pÛq = p q +`p`q Ø((pÞq)ÞØ(qÞp)) = = (`p + q)(q +`p) = `p`q +`p p +`q q + q p =`p`q + 0 + 0 + q p = p q +`p`q Пример. Упрощение высказываний.
(ØpÚØqÚØr)Ù(qÚØp)Ú(pÞq)Ùq = (`p +`q +`r)(q +`p) + q(`p + q) = (`p + q)(`p +`q +`r + q) = (`p + q)(1 +`p + `r) = `p + q = pÞq (pÞq)Þp = + p = p`q + p = p(`q + 1) = p 1 = p Пример. Доказательство равносильности высказываний. [ØpÞØqÙØr] = `p Þ`q`r = `p +`q`r = p +`q`r {(ØpÞØq)Ù(ØpÞØr)} = (`pÞ`q)(`pÞ`r) = (p +`q)(p +`r) = p + p`r +`q p +`q`r = p(1 +`r +`q) +`q`r = p +`q`r Т. о. […] = {…} т. е. являются равносильными два полученных ранее перевода высказывания «чай …». Правилом отделения называется правило D p, (p)Þ(q), q Теорема о выводе в пропозициональной логике: высказывание p0 является тавтологическим следствием из p1,…,pn тттк его можно получить из p1,…, pn с помощью правила отделения и нижеследующих пятнадцати беспосылочных правил: D pÞqÞp D (pÞpÞq)Þ(pÞq) D (pÞq)Þ((qÞr)Þ(pÞr)) D pÙqÞp D pÙqÞq D (pÞq)Þ((pÞr)Þ(pÞqÙr)) D pÞpÚq D qÞpÚq D (pÞr)Þ((qÞr)Þ(pÚqÞr)) D (pÛq)Þ(pÞq) D (pÛq)Þ(qÞp) D (pÞq)Þ((qÞp)Þ(pÛq)) D (pÞq)Þ(ØqÞØp) D pÞØØp D ØØpÞp Другими словами, какое–либо высказывание p0 является тавтологическим следствием из p1,…,pn тттк p0 можно сделать членом последовательности высказываний, которая является индуктивной относительно этих шестнадцати правил и правил D p1,…, Dpn. Теорема не исключает случай n = 0. Теорема о самодостаточной выразительности пропозициональной логики: для любой истинностной таблицы с n входными столбцами p1,…,pn и любого распределения истинностных значений в ее результирующем столбце можно составить соответствующее этому столбцу высказывание: справа от всех строк с истиной в результирующем столбце записываем конъюнкцию p1… pn, затем над некоторыми pk ставим черту отрицания так, чтобы все эти конъюнкции для всех строк были истинными, затем составляем дизъюнкцию из получившихся конъюнкций. Например: p q r ? 0 0 0 0 0 0 1 0 0 1 0 1 p q`r 0 1 1 0 1 0 0 1 p`q`r 1 0 1 0 1 1 0 1 p q`r 1 1 1 0 `p q`r + p`q`r + p q`r = `p q`r + p`r(`q + q) =`p q`r + p`r =`r(`p q + p) =`r(p + q) = ØrÙ(pÚq) Замечание. Если в результирующем столбце содержится только Л, то в качестве искомого высказывания можно взять p1ÙØp1. Пример применения теоремы о самодостаточной выразительности. Турист приехал в страну, где каждый житель всегда лжет либо всегда говорит правду. Какой вопрос должен задать турист местному жителю, чтобы узнать, какая из двух дорог ведет в столицу. p – житель говорит правду q – эта дорога ведет в столицу r – высказывание для вопроса | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
p |
q |
r |
Нужный ответ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
0 |
0 |
1 |
Нет |
`p`q |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
0 |
1 |
0 |
Да |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1 |
0 |
0 |
Нет |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1 |
1 |
1 |
Да |
p q |
r =`p`q + p q = pÛq т. e. турист должен спросить: верно ли, что Вы скажите правду если и только если эта дорога ведет в столицу.
Пример проверки рассуждения «(Профсоюзы поддержат президента на предстоящих выборах | p) только если (он подпишет законопроект о повышении заработной платы ½q). (Фермеры окажут президенту поддержку ½r) только если (он наложит вето на законопроект ½s). Очевидно, что он не подпишет законопроекта или не наложит на него вето. Следовательно президент потеряет голоса профсоюзников или голоса фермеров».
(pÞq)Ù(rÞs)Ù(ØpÚØs) Þ ØpÚØr = +`p +`r =`p q + r s + q s +`p +`r = + q s = + q s =`p +`q +`r +`s +q s =`p +`r + + q s = `p +`r +1 = 1 – тавтология, т.е. рассуждение правильное.
Пример проверки рассуждения «(В бюджете возникнет дефицит | p), если (не повысят пошлины | Øq). Если в бюджете будет дефицит, то (государственные расходы на общественные нужды сократятся | r). Значит, если повысят пошлины, то государственные расходы на общественные нужды не сократятся».
(ØqÞp)Ù(pÞr)Þ(qÞØr) = +`q + `r =`q`p + p`r +`q +`r = `q(`p +1) +`r(p + 1) =`q +`r = - не тавтология, т.е. нельзя сказать, что рассуждение правильно.
Пример проверки рассуждения «Если (подозреваемый совершил эту кражу | p), то (она была тщательно подготовлена | q) или (он имел соучастника | r). Если бы кража была подготовлена тщательно, то, если бы был соучастник, украдено было бы гораздо больше. Значит, подозреваемый невиновен».
(pÞqÚr)Ù(qÞ(rÞØp))ÞØp = +`p = p`q`r + p q r +`p = q r +`q`r +`p
– не тавтология.
Пример проверки рассуждения «(Если наступит мир | p), то (возникнет депрессия | q), разве что (страна проведет программу перевооружения | r) или осуществит грандиозную социальную программу | s). Но договориться о целях такой грандиозной программы невозможно. Следовательно если наступит мир и не будет депрессии, то будет осуществляться программа перевооружения».
(pÞqÚØqÙ(rÚs))ÙØsÞpÙØqÞr = =
т.е. рассуждение правильное.
Пример сокращения текста «Члены финансового комитета должны избираться среди членов дирекции. Нельзя быть одновременно членом дирекции и членом библиотечного совета, не будучи членом финансового комитета. Член библиотечного совета не может быть членом финансового комитета».
p – он является членом финансового комитета
q – он является членом дирекции
r – он является членом библиотечного фонда
(pÞq)Ù(ØpÞØ(qÙr))Ù(rÞØp) = (`p + q)(p +`q +`r)(`r +`p) = (`p +q) = (`p + q)=(`p + q)(`p`q +`r) = (`p + q)(`p + q)`q +`r) = (`p + q)(`q +`r) = (pÞq)ÙØ(qÙr)
Таким образом, можно отбросить подчеркнутую часть текста.
Пример анализа рассуждения «(это преступление совершено в Кустанае | q). (Петров во время совершения преступления находился в Ростове | r). Следовательно (Петров не совершал этого преступления | Øp)».
qÙrÞØp – не тавтология
«Преступление совершено в Кустанае. Поэтому если Петров совершил это преступление, то (он во время совершения преступления находился в Кустанае |s). Но Петрова в это время в Кустанае не было. Значит, Петров не совершал этого преступления».
qÙ(qÞpÞs)ÙØp = … = 1 – тавтология т.е. рассуждение правильное.
Рассуждение останется правильным, если из него выбросить первое предложение и ссылку на него во втором предложении:
(pÞs)ÙØsÞØp = +`p = +`p = p + s +`p = 1 + s = 1
Задача. Выяснить, кто из четверых виновен на основе информации «Петров виновен, только если виновен Кулагин. Неверно, что виновность Родионова влечет виновность Сидорова и что Кулагин виновен, а Сидоров нет».
p, q, r, s – виновен Петров, Кулагин, Родионов, Сидоров.
(pÞq)ÙØ(rÞs)ÙØ(qÙØs) = (`p + q) = (`p + q) r`s(`q + s) = (`p + q)`r s`q = `p`q r`s
т.е. Родионов виновен, остальные не виновны.
Задача Кислера. Обвиняемые в подделке налоговых документов Браун, Джонс и Смит дают под присягой такие показания.
Браун: Джонс виновен, а Смит не виновен.
Джонс: Если Браун виновен, то виновен и Смит.
Смит: Я не виновен, но хотя бы один из них двоих виновен.
Вопрос 1: Совместимы ли данные показания?
Вопрос 2: Какое показание следует из другого?
Вопрос 3: Если все виновны, то кто лжесвидетельствует?
Вопрос 4: Если все сказали правду, то кто виновен?
Вопрос 5: Если невинный говорит правду, а виновный лжет, то кто виновен, а кто невиновен?
Б – виновен Браун.
Д – виновен Джонс.
С – виновен Смит.
Б
Д
С
ØБ
ØД
ØС
БÚД
ДÙØС
БÞС
ØСÙ(БÚД)
Л
Л
Л
И
И
И
Л
Л
И
Л
Л
Л
И
И
И
Л
Л
Л
И
Л
Л
И
Л
И
Л
И
И
И
И
И
Л
И
И
И
Л
Л
И
Л
И
Л
И
Л
Л
Л
И
И
И
Л
Л
И
И
Л
И
Л
И
Л
И
Л
И
Л
И
И
Л
Л
Л
И
И
И
Л
И
И
И
И
Л
Л
Л
И
Л
И
Л
Показания
Брауна
Джонса
Смита
1. Да, только за счет третьей строки.
2. Из первого третье.
3. Браун и Смит.
4. Джонс виновен, остальные невиновны.
5. Джонс невиновен, остальные виновны.
Тема 4. Кванторная логика.
или логика предикатов является расширением пропозициональной логики путем изучения операций ", $. Из определения этих операций следует, что значения высказываний "хp, $хp, понимаются соответственно как конъюнкция p1Ùp2Ùp3Ù… и дизъюнкция p1Úp2Úp3Ú… значений высказывания p для всевозможных значений переменной х. Высказывание p называется кванторологически истинным при любой интерпретации.
Из определений следует, что тавттологически истинное высказывание является кванторологически истинным. Обратное вообще говоря не верно: высказывание "хpÞ$хp является кванторологически истинным, но не является тавтологически истинным.
Истинностная таблица.
"хp
$хp
"хpÞ$хp
Л
Л
И
Л
И
И
И
Л
Л
И
И
И
Истинностная схема.
p1, p2, p3…
"хp
p1Ùp2Ùp3Ù…
$хp
p1Úp2Úp3Ú…
"хpÞ$хp
ЛЛЛ…
Л
Л
И
ЛЛЛ…
Л
И
И
………
…
…
…
ИИИ…
И
И
И
Высказывание q называется кванторологическим следствием (из) высказываний р1,…,pn, если p является истинным в любой интерпретации, в которой истинными являются p1,…,pn.
Вхождением переменной c в высказывание p называется связанным, если оно является вхождением в некоторое подвысказывание вида "х(q) или вида $х(q); в противном случае это вхождение называется свободным.
Например, первое и второе вхождения c1 в высказывание
((g(c1))Ù(g(c1, c2)))Þ($ c1(g(c1)))
являются свободными, а третье и четвертое – связанными.
Через р{х, а} обозначается результат подстановки терма, а вместо всех свободных вхождений переменной х в высказывание р, причем, если при такой подстановке все вхождения переменных из а остаются свободными, то терм а называется допустимым заменителем для х в р. Например, терм f(c5) является допустимым заменителем для c6 в высказывании g((c5, (c6), и не является
допустимым заменителем для c6 в высказывании $c5 (g(c5, c6)). Высказывание р называется замкнутым (открытым), если оно не имеет свободных (связанных) вхождений переменных.
Теорема об отрицании обобщения и подтверждения:
Ø"хр равносильно $хØр
Ø$хр равносильно "хØр
Теорема о взаимоисключении кванторов:
"хр равносильно Ø$хØр
$хр равносильно Ø"хØр
Теорема о перестановочности кванторов:
"х"ур равносильно "у"хр
$х$ур равносильно $у$хр
Типовые кванторы. Запись "qхр обозначает высказывание "х(qÞр), а запись $qхр обозначает высказывание $х(qÙр).
Теорема о равносильной замене: пусть q есть результат замены в высказывании р какого-либо вхождения подвысказывания r1 на высказывание r2; тогда если r1 и r2 равносильны, то р и q тоже равносильны.
Позитивным высказыванием называется такое, которое не имеет вхождений знака Ø. Позитивной формой высказывания р называется любое равносильное ему позитивное высказывание .
Теорема о позитивной форме: если отрицания предикатных компонент высказывания р имеют равносильные себе предикаты, то р равносильно некоторому позитивному высказыванию q; высказывание q можно построить с помощью теоремы о равносильной замене, теорем об исключении операций Þ, Û и теорем об отрицании для операций ", $, Ø, Ù, Ú.
Ø"е$d"х(х<dÞх<еÚх£1 = $e"d$хØ(х<dÞх<eÚх£1) = $e"d$хØ(Øх<dÚх<eÚх£1) = $e"d$х(х<dÙØх<eÙØх£1) = $e"d$х(х<dÙх³eÙх>1) = « существует положительное число е т.ч. для каждого положительного числа d существует число х т.ч. х<d и х³e и х>1».
Теорема о выводе в логике предикатов: нижеследующие шесть правил преобразования высказываний образуют достаточный набор правил вывода в логике предикатов т.е. р0 является кванторологическим следствием из p1,…,pn тттк р0 может быть получено из р1,…,рn с помощью этих шести правил:
D t – правило тавтологии
D s, s Þ r, r – правило отделения
D"хрÞp{x, a} – правило обобщения
D p{x, a} Þ$ xp – правило подтверждения
D qÞr, q Þ"хr – правило общевнесения
D rÞq, $ xrÞq – правило сущевнесения
где t есть тавтология, q не имеет свободных вхождений x, терм а является допустимым заменителем для х в р. Теорема не исключает случай n = 0.
или логика предикатов с равенством, т.е. с двухместным предикатным символом g20, который интерпретируется как знак равенства. Т.о. в эгалитарной логике предикат g20(a, b) выражает то, что мы привыкли выражать в виде a = b и понимать как констатацию того, что объекты с обозначениями a, b являются одинаковыми, равными, неотличимыми, идентичными. Эгалитарной интерпретацией формального языка называется такая, в которой g интерпретируется как знак равенства. Запись p1, …, pn│=q1, …, qm означает, что каждое из высказываний q1, …, qm является логическим следствием из высказываний p1, …, pn т.е. что оно является истинным в любой эгалитарной интерпретации, в которой оказываются истинными p1, …, pn. Высказывание p называется логически истинным, если │=p т.е. если p является истинным в любой эгалитарной интерпретации.
Правилами тождества, равенства, неотличимости называются следующие три правила соответственно:
Dg(x, x)
Dg(x1, y1)Ù…Ù g(xn, yn)Þg(f(x1, …, xn), f(y1, …, yn))
Dg2 (x1, y1)Ù…Ù g(xn, yn)Þ(g f(x1, …, xn)Þ(y1, …, yn))
Теорема об эгалитарной замене: пусть q есть результат замены в p некоторых вхождений терма a термом b; тогда если выражение g20(a, b) является истинным, то p равносильно q.
Теорема о транзитивности логического следствия: если p1, …, pn│=q1, …, qm и q1, …, qm│= r1, …, re, то p1, …, pn│= r1, …, re.
Теорема о расширении списка гипотез: если p1, …, pn│= q, то p0, …, pn│= q.
Теорема дедукции: если высказывания p1, …, pn являются замкнутыми, то p1, …, pn│= p тогда и только тогда когда ê= p1Ù…Ù pnÞp.
Теорема о конъюнктивизации гипотез: p1, …, pn│= p тттк p1Ù…Ùpn│= p.
Теорема о выводе в эгалитарной логике: правила тавтологии, отделения, обобщения, подтверждения, общевнесения, сущевнесения, тождества, равенства, неотличимости образуют достаточный набор правил вывода в эгалитарной логике, т.е. p1, …, pn│= p тттк p может быть получено из p1, …, pn с помощью этого набора правил.
Теорема о сравнительной силе выводов. Если p является тавтологическим следствием из p1, …, pn, то p является кванторологическим следствием из p1, …, pn. Если p является кванторологическим следствием из р1,…,рn, то p является логическим следствием из р1,…,рn.
Алгоритм – это…
Теорема о неразрешимости проблемы логического следствия (логической истинности): нельзя придумать алгоритм, который для любых высказываний p0, …, pn позволял бы разрешить вопрос о том, является или нет p0 логическим следствием из p1, …, pn. Полезно обратить внимание на то, что проблема тавтологического следствия является разрешимой с помощью истинностных таблиц.
Замечание последние семь теорем не исключают случай n = 0.
Замечание если не оговорено противное, слово логика понимается как эгалитарная логика.
предназначены для четкого изложения и развития тех или иных отраслей человеческих знаний. Задать формальную теорию – значит задать ее функциональные и предикатные символы, а также аксиомы, т. е. некоторые из высказываний, которые являются истинными в данной отрасли знаний. Развивать формальную теорию – значит пополнять запас ее теорем, т. е. таких высказываний, которые являются логическими следствиями аксиом.
Изложение любой формальной теории в принципе можно оформить в виде книжек с доказательными текстами:
1
a1 - × - × - × - × - × - × - × - × - × -
ü индуктивная
ý последовательность
þ термов
…
××××××××××××××××××××××××××××××××××××××××××××××××××××××
k
ak - × - × - × - × - × - × - × - × - × -
k+1
r1 - × - × - × - × - × - × - × - × - × -
ü индуктивная
ý последовательность формул
þ на основе a1,…, ak
…
××××××××××××××××××××××××××××××××××××××××××××××××××××××
k+е
re - × - × - × - × - × - × - × - × - × -
k+е+1
s1 - × - × - × - × - × - × - × - × - × -
ü аксиомы
ý s1,…, sm есть
þ среди r1,…, re
…
××××××××××××××××××××××××××××××××××××××××××××××××××××××
k+е+m
sm - × - × - × - × - × - × - × - × - × -
k+е+m+1
t1 - × - × - × - × - × - × - × - × - × -
ü индуктивная
ý последовательность теорем
þ t1,…, tn есть среди r1,…, re
…
××××××××××××××××××××××××××××××××××××××××××××××××××××××
k+е+m+n
tn - × - × - × - × - × - × - × - × - × -
Здесь штрих-пунктирная линия обозначает пояснение о том, с помощью какого правила порождения получено соответствующее знакосочетание. Для удобства таких пояснений знакосочетания a1,…, tn нумеруются последовательно от 1 до k+е+m+n. Вспомним, что правила порождения теорем являются правилами вывода, что конечная индуктивная последовательность теорем является доказательством и что следующие девять правил, называемых основными, образуют достаточный набор правил вывода из аксиом: правила тавтологии, отделения, обобщения, подтверждения, общевнесения, сущевнесения, тождества, равенства, неотличимости.
Такая форма изложения делает доказательство легко проверяемым, но практически не применяется из-за ее громоздкости.
Способы более компактного изложения формальной теории.
1. Последовательность a1,…, re не записывается, потому что при достаточном навыке термы и формулы распознаются без построения их индуктивных последовательностей.
2. В последовательность t1,…, tn включаются теоремы из других доказательных текстов.
3. Для двухместного функционального или предикатного знака v используется операционная форма записи: вместо v(a,b) пишут (a)v(b).
4. При операционной форме записи принимается соглашение об упразднении некоторых пар скобок в соответствии с соглашением об убывании силы связи в последовательности: одноместный функциональный знак, двухместный функциональный знак, одноместный предикатный знак, двухместный предикатный знак, логический знак.
5. Используются специальные начертания для функциональных и предикатных знаков. Например в теории чисел: 0, 1, 2, 3 - нульместные функциональные знаки; Ö, sin, cos - одноместные функциональные знаки; +, -, ´, /, - двухместные функциональные знаки; <, >, £, ³ - двухместные предикатные знаки.
6. Используются знаковые фигуры. Например, åх=3х обозначает сумму 3+4+5.
7. Вводится определяющая аксиома g(х1,...,х11)Û р для нового n-местного предикатного символа g. Здесь переменные х1,...,хn попарно различны, а высказывание р не имеет свободных вхождений переменных, отличных от х1,...,хn.
8. Вводится определяющая аксиома р{х, ¦( х1,...,хn)} для нового n - местного функционального символа ¦ в тех случаях, когда формула $рх является теоремой. Здесь переменные х, х1,...,хn попарно различны, а р не имеет свободное вхождение переменных, отличных от х, х1,...,хn.
Теорема об определениях: если теория Т2 получена из теории Т1 путем добавления определяющей аксиомы для нового функционального или предикатного символа v то для каждой теоремы теории Т2 существует равносильная ей теорема теории Т1.
9. Кроме девяти основных применяются дополнительные правила вывода, например правило отделения конъюнкта D pÙg, р и правило присоединения дизъюнкта Dр, pÚg.
10. Применяются известные методы доказательства. Обоснование таких методов дается в учебниках логики. Например метод доказательства от противного основан на следующей теореме.
Теорема о доказательстве методом от противного: если формальная теория Т2 получена путем добавления аксиомы Øр к аксиомам теории Т1 и если формулы q, Øq являются теоремами теории Т2, то формула р является теоремой теории Т1.
Формальная арифметика формализует систему знаний о целых неотрицательных числах, использует в качестве исходных четыре функциональных и два предикатных знака
¦
¦
¦
¦
g
g
0
1
+
×
=
<
интерпретируемых в соответствии с их известными со школы специальными начертаниями, имеет такие аксиомы
Ø1=0
х + 1= y + Þ x = y
x + 0 = x
x + (y + 1) = (x + y) + 1
x×0 = 0
x×(y + 1) = x×y + x
Øx < 0
x < y + 1 Û x < y Ú x = y
p íx, 0ýÚ"(pÞíx, x + 1ý)Þ p
Здесь при записи аксиом использованы ранее перечисленные соглашения о компактизации изложения и известное соглашение о том, что знак умножения связывает сильнее знака сложения. Если такие соглашения не принимать, то к примеру первую аксиому следовало бы записать в виде Ø(g(¦,¦ )).
Пример определяющих аксиом для новых нульместных функциональных знаков 2, 3, 4, 5 и новых двухместных предикатных знаков >, £ ,³ ,¹ :
2 = 1 + 1
c1>c2 Û c2<c1
3 = 2 + 1
c1£c2 Û c1 < c2 Ú c1 = c2
4 = 3 + 1
c1³c2 Û c1 > c2 Ú c1 = c2
5 = 4 + 1
c1¹c2 Û Øc1 = c2
Заметим, что знак < можно было бы не включать в перечень исходных знаков формальной арифметики, а ввести его с помощью определяющей аксиомы c1<c2 Û $c3(Øc3 = 0 Ù c1+ c3 = c2).
Пример доказательного текста в формальной арифметике (k = 3, е = 6, m = 1, n = 3):
1
¦ ----------------------------------------------
Константа
2
¦-----------------------------------
Константа
3
c1 -----------------------------------------
Переменная
4
g(¦, ¦)---------------------------------
Предикат от 2,1
5
Ø(g(¦, ¦))-----------------------------
6
g(c1, ¦)---------------------------------
Предикат от 3,1
7
Ø(g(c1, ¦))------------------------------
Отрицание 6
8
$c1(g(c1, ¦)))---------------------------
Подтверждение 7 по c1
9
(Ø(g(¦, ¦)))Þ$c1(Ø(g(c1, ¦))))----
Импликация 5,8
10
Ø(g(¦, ¦))-----------------------------
5: аксиома
11
(Ø( g(¦,¦ )))Þ$c1(Ø(g(c1,¦))))----
9: пр. подт. 7, c1, 2
12
Ø(g(¦, ¦))-----------------------------
5: аксиома 10
13
$c1(Ø( g(c1, ¦)))-----------------------
8: пр. отделения для 12, 11
Компактизированный текст:
11
Ø1 = 0 Þ$c1Øc1 = 0---------------------
Правило подтверждения
12
Ø1 = 0-------------------------------------
Аксиома
13
$c1Øc1 = 0--------------------------------
Правило отд. для 12, 11
Словесный вариант: «Если единица не равна нулю, то тем самым существует не равное нулю число. Но единица не равна нулю. Следовательно, существует число, не равное нулю».
Тема 7. Множества и функции.
В этой теме A, B, C, D, E, F, G, X, Y, Z, X1, Z1,…, Xn, Yn, Zn обозначают попарно различные переменные. Множество – это совокупность различных объектов, мыслимая как единый новый объект. Различные объекты, из которых составлено множество, называются его элементами. Соотношение xÎA означает, что объект х есть элемент множества A. Отрицание соотношения xÎA записывается в виде xÏA. Соотношение АÌВ означает, что А есть подмножество множества В, т.е. что каждый элемент множества А является элементом множества В. Отрицание соотношения АÌВ записывается в виде АËВ. Множество, элементами которого являются все те и только те объекты вида а, для которых истинно соотношение p, обозначается через a. Множество "A(xÏA) называется пустым множеством и обозначается символом Ø. Множество x обозначается через {x1,…,xn}. Множество xÎAÚxÎB называется объединением множеств А, В и обозначается через АÈВ. Множество xÎAÙxÎB называется пересечением множеств А, В и обозначается через АÇВ. Множество x называется дополнением множества В относительно А или результатом удаления из множества А элементов множества В и обозначается через А\В.
Простейшие теоремы: 3Ï{9, 7, 3}, x+5 = {3, 7], AÏA, AÌA, …
Обозначения для некоторых множеств:
N - множество натуральных чисел
Z - множество целых чисел
R - множество действительных чисел
Упорядоченная n-ка объектов x1,…,xn обозначается через (x1,…,xn) и определяется так: (x1) = x1
(x1, x2) = {{x1}, { x1, x2}}
(x1, x2, x3) = ((x1, x2), x3)
(x1, x2, x3,x4) = ((x1, x2, x3), x4)
………………………………..
Упорядоченная n-ка называется еще n-мерным упорядоченным набором, вектором, точкой, кортежем. Объект x1 называется k-той компонентой или координатой n-мерного набора (x1,…,xn) и обозначается через koor(x1,…,xn). Множество x1Îz1Ù…Ù xnÎzn называется декартовым произведением множеств z1,…,zn и обозначается через z1´…´zn. Если А - множество упорядоченных n-ок, то множество (x1,…,xnÎA называется k-той проекцией n-мерного множества А и обозначается через πА. Через Аn обозначается множество А´…´А (n множителей). Соглашение: знаки ´, Ç, связывают сильнее чем È, \.
Простейшие теоремы: (x1,…,xn) = (y1,…,yn)Û x1= y1Ù…Ù xn= yn, (9, 9, 9)¹ (9, 9), p(A´B´C´D´E) = C, {5. 7}2 = {(5, 5), (5, 7), (7, 5), (7, 7)}, koor(5, 7, 9) = 9, koor(5, 7, 9) = koor(5, 7, 9) = koor(5, 7, 9) = H, {7}´{8, 5}´{9} = {(7, 8, 9), (7, 5,9)}. {4}5 = {(4, 4, 4, 4, 4)}, p{(1, 2, 3), (1, 3, 2), (2, 3, 4)} = {2, 3}. A´B´C = (A´B)´C.
Функцией называется множество, любой элемент которого есть упорядоченная двойка. Множество πF называется областью определения или доменом функции F и обозначается dom F. Множество πF называется областью значений или ранжиром функции F и обозначается ran F. Если (x,y)ÎF, то y называется значением функции F в x и обозначается F(x). Если АÌ domF, то множество y называется образом множества А относительно функции F и обозначается F[А]. Функция F в случае dom F = A и ran FÌB / ranF=B называется еще отображением множества А в/на множество В. Запись F:А®В означает что F есть отображение множества А в множество В. Функция F называется сужением функции G (на множество dom F), а функция G называется расширением функции F (на множество dom G), если F есть результат удаления из G всех тех (x, y), для которых xÏ dom F. Если F есть функция, то {(y, x)ï (x, y)ÎF} тоже есть функция, называемая обратной по отношению к F. Очевидно, что если функция G является обратной по отношению к функции F, то F является обратной по отношению к G. Если dom F есть множество упорядоченных n-ок, то функция F называется n-аргументной и вместо F((x1,…,xn)) используют более короткое обозначение F(x1,…,xn). Функция F называется однозначной, если из (x, y)ÎF и (x, z)ÎF следует y=z. Функция называется взаимно однозначной или биективной, если она сама и обратная к ней функция являются однозначными. Последовательностью называется однозначная функция F т.ч. dom F = N. Если F есть последовательность и nÎN, то F(n) называется n-м членом последовательности и обычно обозначается через Fn.
Множество А называется бесконечным, если существует биективное отображение множества N в множество А. Множество называется конечным, если оно не является бесконечным.
Простейшие теоремы: cos(0)=1, cos[{0}] = {1}, Аrccos и cos обратны друг к другу, функция arccos не является обратной к cos и является обратной к сужению функции cos на множество ran arccos.
ЗАДАЧНИК-МИНИМУМ ПО ЛОГИКЕ
В квадратных скобках дается ответ к задаче, Д означает ДА, Н означает НЕТ, все высказывания о числах в задачах 1.1 – 6.4 являются арифметическими, т.е. высказываниями о целых неотрицательных числах.
1.1 Указать истинное значение для высказываний 5=5, 5¹5, 5>5, 5£5, 5³5, 5<5, Х<0, Х+2<5, Х+Х<6, Х-Х=0, Х³0, X+Z=Z+X [ИЛЛИИЛЛППИИИ] и для каждых двух соседних высказываний выяснить, являются ли они равносильными [НДНДНДНДНДД].
1.2 Для каждой из трех последовательностей 2, 3; 3, 2, 4, 5; 3, 2, 3, 6 выяснить, является ли она индуктивной относительно набора правил D3; DХ, Х-1; DХ,Z,X+[НДД].
1.3 Выяснить, являются ли Dа<b, a<b+3; Da³b, b³0, a³0 правилами вывода [ДД].
2.1 Для каждого из пяти знакосочетаний ØÚ; ¦g$; f f f; c4c8 f g; "$ØÙÚÞÛ выяснить следуют ли в нем его знаки в алфавитном порядке [ДНДНД].
2.2 Для терма f(f(c1), f, f(f, c1, f(f))) составить индуктивную последовательность термов [f, c1, f(f), f(f, c1, f(f) f(f(c1), f, f(f, c1, f(f)))].
2.3 Пусть p, q, r обозначают нульместные предикаты. Для высказывания pÚØqÙrÞpÞqÞr составить индуктивную последовательность высказываний [p, q, r, Ø(q), (Ø(q)Ù(r), (p)Ú((Ø(q))Ù(r)), (q)Þ(r), (p)Þ((q)Þ(r)), ((p)Ú((Ø(q))Ù(r)))Þ((p)Þ((q)Þ(r)))].
2.4 Для высказывания $c5g(c1, f(c2), c1) составить индуктивную последовательность термов и высказываний [c1, c2, f(c2), g(c1, f(c2), c1), $c5 (g(c1, f(c2), c1))].
2.5 Для каждого из семи обозначений а: f(a), g(a), g(a, b); Z; $Xg(X, X, Z); "Xf(X, X) выяснить, обозначает ли оно: Терм, Высказывание, Ни-то-ни-другое [TTBHTBH].
2.6 Для каждой из шести скобочных диад в высказывании ((p)Þ(q))Þ((r)Þ(s)) выяснить можно ли ее отбросить без нарушения смысла данного высказывания [HДДДДД].
2.7 В высказывании pÛqÚØrÙØp восстановить все скобки [(p)Û((q)Ú((Ø(r))Ù(Ø(p))))].
2.8 В высказываниях pÚØqÙrÞpÙrÚØp, pÚØqÙ(rÞpÙr)ÚØp восстановить все скобки с помощью нумерации логических знаков и скобок в порядке их восстановления.
é((p)Ú((ù(q))Ù(r)))Þ(((p)Ù(r))Ú(ù(p))), (p)Ú(((ù(q))Ù((r)Þ((p)Ù(r)))Ú(ù(p)))ù
ë76p666422q2444r4677753p333r355511p1577p77776544q45552r2221p111r12566633p367û
2.9 Пусть p обозначает высказывание ("c1$c2g(c2, f(c1, c2)))Ùg(f, f (c2))ÞgÚg(c1). Индукцией по построению высказывания определить его истинностное значение на универсуме при такой интерпретации функциональных и предикатных знаков.
f
g
X
f(X)
g(X)
X
Y
f(X, Y)
g(X, Y)
3
И
3
4
Л
3
3
3
И
4
3
И
3
4
4
И
4
3
4
И
4
4
4
Л
Ответ:
c2
p
3
Л
4
И
2.10 Указать истинностные значения высказываний 2<2ÞХ>3, Х<3+4ÛХ<9, 7<Х<9ÞХ=8, Х£3ÚХ>3, "Х(Х>3)Þ5=3, $c1"c2(c2<c1), "c2$c1 (c2<c1) [ИПИИИЛИ].
2.11 Для каждого из правил Dp, q, r, pÙqÙr; Dp, pÞp; DpÞp, p ; DpÚq, Øp, q; DØØØØp, p; Dp, $XP; D$XP, P; DP, "XP; D"XP; P выяснить является ли оно правилом вывода [ДДНДДДНДД].
2.12 Для каждого из высказываний g(a), "X g(X,C), $X(gÞ g), $XgÞ g, g, Ø g, gÛ g, g выяснить, является ли оно: предикатом [ДНННДННД], элементарным высказыванием [ДДДНДННД].
2.13 Для высказывания "X(gÞ g(X))Úg записать: все его компоненты [g, g(X), gÞg(X), "X(gÞg(X)), "X(gÞ g(X))Úg], все его элементарные компоненты , все его пропозициональные компоненты [g, "X(gÞg(X))], все его предикатные компоненты [g, g(X)].
2.14 Записать все пропозициональные компоненты высказываний $XPÙ$ZP, $XPÙØ$ZP. [$XP, $ZP – если X, Z различные переменные, $cnP – если X, Z обозначают одну и ту же переменную cn].
3.1 Вычислить:
ИÚØЛÞИÞЛÙИÛИÛЛÚИÚЛÚØИÞЛÙИÙЛÙØИÙØЛÙИÙЛÙØИÙИÙЛ
[И].
3.2 Выяснить, является ли высказывание ØpÙqÙ(rÞs)Û(pÚØqÚrÙØs) тавтологией [Д].
3.3 Пусть p, q, r – различные элементы высказывания. Для каждого из высказываний pÞØrÚqÚp, pÞØr, rÞØpÚq выяснить, является ли оно тавтологией [ДНН] и является ли оно тавтологическим следствием двух других [ДНД].
3.4 Решить истинностное уравнение (pÞq)ÞØqÞp= Л с двумя неизвестными p, q [Л, Л].
3.5 Из p, q, r составить высказывание, истинное только при p=q=r
[(pÛq) Ù(qÛr)].
4.1 Пусть Р обозначает g(x). Для каждого из высказываний pÞ$XP, $XPÞ P, $XPÞØP выяснить является ли оно кванторологически истинным [ДНН] и является ли оно кванторологическим следствием двух других [ДДН].
4.2 Для каждого вхождения переменной в высказывание из задачи 2.9 выяснить, является ли оно свободным или связанным [связанное, связанное, связанное, связанное, свободное, свободное].
4.3 Записать обозначенное через "c3g(c3, c4) íc4,¦(c3)ý высказывание ["c3g(c3, ¦(c3))].
4.4 Пусть P обозначает высказывание $c3g(c6, c3)Ú "c6g(c6, c3) Ú g(c6, c4).
Указать высказывания с обозначениями P íc3, c6ý, P íc3, ¦(c5)ý, P íc3, c3ý . [$c3g(c6, c3)Ú "c6g(c6, c6) Ù g(c6, c6), $c3g(c3, c3)Ú "c6g(c6, c3) Ù g(c3, c3), P, P].
4.5 Для каждого из терминов ¦(c1), ¦(c2), ¦(c8), ¦(c1, c5, c8), ¦ выяснить, является ли он допустимым заменителем для c8 в высказывании $c2g(c8)Ú "c5g(c8) [ДНДНД].
4.6 Для каждого из высказываний [$c1g(c1), "c2g(c2, c3), g(c1, c2, c3), g(¦) выяснить, является ли оно замкнутым [ДННД] и является ли оно открытым [ННДД].
4.7 Высказывание Ø"C$Z(C£ZÛZ¹0ÙØ$C(C>Z))Þ$C"Z(C³Z) привести к позитивной форме
[$C"Z(C>ZÙZ¹0Ù"C(C£Z)ÚC£ZÙ(Z=0Ú$C(C>Z)))Þ"C$Z(C<Z)].
4.8 В высказывании $c3g(c3, c5)ÚØ" c5g(c3, c5) Þ gÛg(¦, c5) второе вхождение высказывания g(c3, c5) заменить высказыванием Ø g(c3, c5) Þ g(c3, c5). [$c3g(c3, c5)ÚØ" c5(Ø g(c3, c5) Þ g(c3, c5) Þ gÛg(¦, c5) и выяснить, равносилен ли результат замены исходному высказыванию [Д].
5.1 Для каждого из высказываний g(¦, ¦), $c1g(c1, c2), g(¦, ¦)Ùg(¦, ¦) выяснить, является ли оно логически истинным [НДН] и является ли оно логическим следствием остальных [ДДН].
5.2 Указать высказывания p, q т.ч. p½=q, но pÞq не есть логически истинное высказывание [c1= c2, c1= c3].
6.1 Выяснить, является ли последовательность высказываний P, PÞ$CR, $CR, PÞ$CRÞR, $CRÞR, $CRÞ"CR, "CR, R=QÞRÙQ, Q, RÙQ доказательством в теории с аксиомами R,Q [Д].
6.2 Для каждого из высказываний 3<5, 5=5, Х<6Þ$C(C<6), 5<6Þ5<6 выяснить, является ли оно: истинным [ДДДД], логически истинным [НДДД], кванторологически истинным [ННДД], тавтологически истинным [НННД].
6.3 Для каждого из высказываний g(c1, c2), $c1g(c1), g(c1) выяснить, является ли оно из двух других: логическим следствием [НДД], кванторологическим следствием [НДН], тавтологическим следствием [ННН].
6.4 Записать определяющие аксиомы в формальной арифметике для термов ½c1- c2½,6. [c1+½c1- c2½=c2Úc2+½c1- c2½=c1, 6=(((((1)+(1))+(1))+(1))+(1)] и для высказываний: c1 есть четное число, c1, есть простое число, c1, есть делитель числа c2. [$c3=c3 + c3), Ø$c3$c4(c3×c4 Ùc3<c1Ùc4<c1) Ù1<c, Øc1=0Ù$c3(c2=(c1×c3)].
7.1 Пусть A, D, C, D, E, F, G, X, Y, Z, X1,..., Xn обозначают попарно различные переменные. Указать истинное значение каждого из высказываний 5Î{3,5}, 3Ï{3,5}, 4Ï{3,5}, {3,5}¹{5,3}, {3,5}={3,3,5}, {2,8}Ì{2,9,8}, {2,9,8}Ì{2,8}, 4Î{4}, 4Ì{4}, {4}Î4, 4¹4, {4}Ì{4}, {4}¹4, {6}Ï{2,6}, {2Х½Х=3ÚХ=4}={6,8}, {Х½Х¹Х}=Æ, {4,3}È{3,7}={4,3,7}, {4,3}Ç{3,7}={3}, {4,3}\{3,7}={4}, {3,5}È{5,3}¹{3,5}, A=BÛ"C(CÎAÛCÎB), CÏAÛØCÎA, AÎA, CÎÆ, AÌBÛ"C(XÎAÞCÎB), AËBÛØAÌB, AÌBÙBÌCÞAÌC, AËA, ÆËA, AÌAÈB, AÈBÌA, AÇBÌA, AÌAÇB, AÈƹA, AÇƹÆ, (AÈB)ÈC=AÈ(BÈC), AÈB¹AÈB, AÇB=BÇA, AÈA¹A, A¹BÛ$C(CÎAÙCÎBÚCÏAÙCÎB), AËBÛ$C(CÎAÙCÏB), (AÈB)\B=A, (A\B)\B=A\B, A\B=A(AÈB), A\(AÇB=A\B, A\B=B\A, AÇA¹A, AÌBÛAÈB=B, CÎ{C1,...,Cn}ÛC=C1Ú...ÚC=Cn, CÎAÈBÛCÎAÚBÎB, CÎAÇBÛCÎAÙBÎB, AÌBÞBÌA, A\A¹Æ, A\ƹA, AÌA, NÌZ, ZÌR, ZËN, RËZ, (2,2)=(2,2,2), (3,5)=(3,2+3), (3,5)=(5,3), {3,5}={5,3}, (4,8) ¹(8,4), (A,B)=(C,D)ÛA=CÙB=D, koor(8,5,4)=5, koor(8,5,4)=4, koor(8,5,4)=(8,5), koor(8,5,4)=8, (X,Z) ¹(Z,X), (X,Z) ¹(Z,X) ÛX¹Z, koor(a, b), koor(a, b)=(a, b), (a, b)=(b, a), (a, a)=a, {4,6}х{7,9}={4,7), (4,9), (6,7), (6,9)}, {5} х {3,2} х {6}={(5,3,6), (5,2,6)}, {5} х {6}={6} х {5}, A х B=B х A, A х B¹B х A, A х (B х C)=(A х B) х C, (A х B) х C=A х B х C, A1=A, A2=A х A, A3=A х A х A,
{8,5}2={(8,8), (8,5), (5,5)}, {6}4={(6,6,6,6)}, p(A*D*C*D*E)=B, p({a, b)}¹b, p{(3,7), (3,8), (3,9), (4,9)}={3,4}, p{(3,7), (3,8), (3,9), (4,9)}= {7,8,9}, p{(6,7,8,9)}=8, dom {(3,6), (6,4)}= {3,6,4}, dom {(3,6), (6,4)}= {3,6}, ran {(3,6), (6,4)}= {6,4}, ran {(3,6)} ¹6, {5,4,8} есть область определения функции {(5,5), (8,0). (4,)0}, есть образ множества {3} относительно функции {(3,7)}, dom sin =R, ran sin={X½RÎÙ½C½£1}, dom sin =dom tg, dom Arcsin=ransin, dom arcsin=R, ran arcsin=R,, функция sin биективна, cos(0)=1, функция sin и arcsin обратны друг другу, функция sin однозначна, функция arcsin однозначна, функция arcsin биективна, {(5,9), (5,8) (2,9)} есть расширение функции {(2,9)}, arcsin есть сужение функции Аrcsin, {(4,5), (5,8)} есть сужение функции {(4,7), (5,9) (5,8)}, функция {(4,4), (5,5)} биективна, функция sin È cos является многозначной. [1010110100011011111011001110101П1П00101011П1П1П0111111П00111110101111111П11П0110ПП011111110111011010110101011010110011]
Для A=BÞ"C(ÎAÞCÎB) построить доказательство [(X=CÙA=BÞCÎAÞCÎB)Þ(C=CÞA=BÞCÎACÎB),C=CÙA=BÞCÎAÞCÎB,C=CÞA=BÞCÎAÞCÎB,C=C,A=BÞCÎAÞCÎB,A=BÞ"C(CÎAÞCÎB)]
Информация | ||
| ||
|
|