реферат, рефераты скачать
 

Краткая методичка по логике


|И |Л |Л |Л |И |Л |И |

|И |Л |И |Л |Л |Л |И |

|И |И |Л |Л |И |И |И |

|И |И |И |Л |Л |Л |И |

Тавтология или тавтологически истинное высказывание - это высказывание

со сплошными И в его столбце его истинностной таблицы. Высказывание 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) будет [pic].

При арифметической записи высказываний с ними можно обращаться так, как

будто они обозначают числа 0, 1, а. Логический плюс отличается от

арифметического только тем, что 1 + 1 = 1. При этом полезно помнить

следующие равенства:

p ( q = (p + q [pic]

p ( q = p q + (p (q p p = p

[pic] p + p = p

[pic] 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 =[pic] + p q = 1

((p((q)(((q(p)(q = [pic] +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)) = [pic] = ((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 = [pic] + 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

Т. о. (…( = {…} т. е. являются равносильными два полученных ранее

перевода высказывания «чай …».

Правилом отделения называется правило ( p, (p)((q), q

Теорема о выводе в пропозициональной логике: высказывание p0 является

тавтологическим следствием из p1,…,pn тттк его можно получить из p1,…, pn с

помощью правила отделения и нижеследующих пятнадцати беспосылочных правил:

( p(q(p

( (p(p(q)((p(q)

( (p(q)(((q(r)((p(r))

( p(q(p

( p(q(q

( (p(q)(((p(r)((p(q(r))

( p(p(q

( q(p(q

( (p(r)(((q(r)((p(q(r))

( (p(q)((p(q)

( (p(q)((q(p)

( (p(q)(((q(p)((p(q))

( (p(q)(((q((p)

( p(((p

( ((p(p

Другими словами, какое–либо высказывание p0 является тавтологическим

следствием из p1,…,pn тттк p0 можно сделать членом последовательности

высказываний, которая является индуктивной относительно этих шестнадцати

правил и правил ( p1,…, (pn. Теорема не исключает случай 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 = [pic] +(p +(r =(p q + r s + q s +(p +(r =

[pic] + q s = [pic] + q s =(p +(q +(r +(s +q s =(p +(r + [pic] + q s = (p

+(r +1 = 1 – тавтология, т.е. рассуждение правильное.

Пример проверки рассуждения «(В бюджете возникнет дефицит ( p), если

(не повысят пошлины ( (q). Если в бюджете будет дефицит, то

(государственные расходы на общественные нужды сократятся ( r). Значит,

если повысят пошлины, то государственные расходы на общественные нужды не

сократятся».

((q(p)((p(r)((q((r) = [pic] +(q + (r =(q(p + p(r +(q +(r = (q((p +1) +(r(p

+ 1) =(q +(r = [pic] - не тавтология, т.е. нельзя сказать, что рассуждение

правильно.

Пример проверки рассуждения «Если (подозреваемый совершил эту кражу (

p), то (она была тщательно подготовлена ( q) или (он имел соучастника ( r).

Если бы кража была подготовлена тщательно, то, если бы был соучастник,

украдено было бы гораздо больше. Значит, подозреваемый невиновен».

(p(q(r)((q((r((p))((p = [pic] +(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 = [pic] = [pic]

т.е. рассуждение правильное.

Пример сокращения текста «Члены финансового комитета должны избираться

среди членов дирекции. Нельзя быть одновременно членом дирекции и членом

библиотечного совета, не будучи членом финансового комитета. Член

библиотечного совета не может быть членом финансового комитета».

p – он является членом финансового комитета

q – он является членом дирекции

r – он является членом библиотечного фонда

(p(q)(((p(((q(r))((r((p) = ((p + q)(p +(q +(r)((r +(p) = ((p +q)[pic] = ((p

+ q)[pic]=((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 = [pic] +(p = [pic] +(p = p + s +(p = 1 + s = 1

Задача. Выяснить, кто из четверых виновен на основе информации «Петров

виновен, только если виновен Кулагин. Неверно, что виновность Родионова

влечет виновность Сидорова и что Кулагин виновен, а Сидоров нет».

p, q, r, s – виновен Петров, Кулагин, Родионов, Сидоров.

(p(q)(((r(s)(((q((s) = ((p + q)[pic] = ((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 |(хp |(хp((хp |

| |p1(p2(p3(… |p1(p2(p3(… | |

|ЛЛЛ… |Л |Л |И |

|ЛЛЛ… |Л |И |И |

|……… |… |… |… |

|ИИИ… |И |И |И |

Высказывание q называется кванторологическим следствием (из)

высказываний р1,…,pn, если p является истинным в любой интерпретации, в

которой истинными являются p1,…,pn.

Вхождением переменной ( в высказывание p называется связанным, если

оно является вхождением в некоторое подвысказывание вида (х(q) или вида

(х(q); в противном случае это вхождение называется свободным.

Например, первое и второе вхождения (1 в высказывание

((g[pic]((1))((g[pic]((1, (2)))((( (1(g[pic]((1)))

являются свободными, а третье и четвертое – связанными.

Через р{х, а} обозначается результат подстановки терма, а вместо всех

свободных вхождений переменной х в высказывание р, причем, если при такой

подстановке все вхождения переменных из а остаются свободными, то терм а

называется допустимым заменителем для х в р. Например, терм f[pic]((5)

является допустимым заменителем для (6 в высказывании g[pic](((5, ((6), и

не является

допустимым заменителем для (6 в высказывании ((5 (g[pic]((5, (6)).

Высказывание р называется замкнутым (открытым), если оно не имеет свободных

(связанных) вхождений переменных.

Теорема о всезначности переменной: р = И тттк (хр = И

Теорема об отрицании обобщения и подтверждения:

((хр равносильно (х(р

((хр равносильно (х(р

Теорема о взаимоисключении кванторов:

(хр равносильно ((х(р

(хр равносильно ((х(р

Теорема о перестановочности кванторов:

(х(ур равносильно (у(хр

(х(ур равносильно (у(хр

Типовые кванторы. Запись (qхр обозначает высказывание (х(q(р), а

запись (qхр обозначает высказывание (х(q(р).

Теорема о равносильной замене: пусть q есть результат замены в

высказывании р какого-либо вхождения подвысказывания r1 на высказывание r2;

тогда если r1 и r2 равносильны, то р и q тоже равносильны.

Позитивным высказыванием называется такое, которое не имеет вхождений

знака (. Позитивной формой высказывания р называется любое равносильное ему

позитивное высказывание .

Теорема о позитивной форме: если отрицания предикатных компонент

высказывания р имеют равносильные себе предикаты, то р равносильно

некоторому позитивному высказыванию q; высказывание q можно построить с

помощью теоремы о равносильной замене, теорем об исключении операций (, ( и

теорем об отрицании для операций (, (, (, (, (.

Пример построения позитивной формы отрицания высказывания: «для

каждого положительного числа е существует положительное число ( т.ч. для

каждого числа х из х1) = « существует

положительное число е т.ч. для каждого положительного числа (

существует число х т.ч. х1».

Теорема о выводе в логике предикатов: нижеследующие шесть правил

преобразования высказываний образуют достаточный набор правил вывода в

логике предикатов т.е. р0 является кванторологическим следствием из p1,…,pn

тттк р0 может быть получено из р1,…,рn с помощью этих шести правил:

( t – правило тавтологии

( s, s ( r, r – правило отделения

((хр(p{x, a} – правило обобщения

( p{x, a} (( xp – правило подтверждения

( q(r, q ((хr – правило общевнесения

( r(q, ( xr(q – правило сущевнесения

где t есть тавтология, q не имеет свободных вхождений x, терм а является

допустимым заменителем для х в р. Теорема не исключает случай n = 0.

Тема 5. Эгалитарная логика

или логика предикатов с равенством, т.е. с двухместным предикатным

символом g20, который интерпретируется как знак равенства. Т.о. в

эгалитарной логике предикат g20(a, b) выражает то, что мы привыкли выражать

в виде a = b и понимать как констатацию того, что объекты с обозначениями

a, b являются одинаковыми, равными, неотличимыми, идентичными. Эгалитарной

интерпретацией формального языка называется такая, в которой g[pic]

интерпретируется как знак равенства. Запись p1, …, pn|=q1, …, qm означает,

что каждое из высказываний q1, …, qm является логическим следствием из

высказываний p1, …, pn т.е. что оно является истинным в любой эгалитарной

интерпретации, в которой оказываются истинными p1, …, pn. Высказывание

p называется логически истинным, если |=p т.е. если p является истинным в

любой эгалитарной интерпретации.

Правилами тождества, равенства, неотличимости называются следующие три

правила соответственно:

(g[pic](x, x)

(g[pic](x1, y1)(…( g[pic](xn, yn)(g[pic](f(x1, …, xn), f(y1, …, yn))

(g2 (x1, y1)(…( g[pic](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 логическим

Страницы: 1, 2, 3


ИНТЕРЕСНОЕ



© 2009 Все права защищены.