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

>

и вместо Л, И, 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

Т. о. … = {…} т. е. являются равносильными два полученных ранее перевода высказывания «чай …».

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

Теорема о выводе в пропозициональной логике: высказывание p₀ является тавтологическим следствием из p₁,…,p_n тттк его можно получить из p₁,…, p_n с помощью правила отделения и нижеследующих пятнадцати беспосылочных правил:

 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

Другими словами, какое–либо высказывание p₀ является тавтологическим следствием из p₁,…,p_n тттк p₀ можно сделать членом последовательности высказываний, которая является индуктивной относительно этих шестнадцати правил и правил  p₁,…, p_n. Теорема не исключает случай n = 0.

Теорема о самодостаточной выразительности пропозициональной логики: для любой истинностной таблицы с n входными столбцами p₁,…,p_n и любого распределения истинностных значений в ее результирующем столбце можно составить соответствующее этому столбцу высказывание: справа от всех строк с истиной в результирующем столбце записываем конъюнкцию p₁… p_n, затем над некоторыми p_k ставим черту отрицания так, чтобы все эти конъюнкции для всех строк были истинными, затем составляем дизъюнкцию из получившихся конъюнкций. Например:

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)

Замечание. Если в результирующем столбце содержится только Л, то в качестве искомого высказывания можно взять p₁p₁.

Пример применения теоремы о самодостаточной выразительности. Турист приехал в страну, где каждый житель всегда лжет либо всегда говорит правду. Какой вопрос должен задать турист местному жителю, чтобы узнать, какая из двух дорог ведет в столицу.

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, понимаются соответственно как конъюнкция p₁p₂p₃… и дизъюнкция p₁p₂p₃… значений высказывания p для всевозможных значений переменной х. Высказывание p называется кванторологически истинным при любой интерпретации.

Из определений следует, что тавттологически истинное высказывание является кванторологически истинным. Обратное вообще говоря не верно: высказывание хpхp является кванторологически истинным, но не является тавтологически истинным.

Истинностная таблица.

хp	хp	хpхp
Л	Л	И
Л	И	И
И	Л	Л
И	И	И

Истинностная схема.

p1, p2, p3…	хp p1p2p3…	хp p1p2p3…	хpхp
ЛЛЛ…	Л	Л	И
ЛЛЛ…	Л	И	И
………	…	…	…
ИИИ…	И	И	И

Высказывание q называется кванторологическим следствием (из) высказываний р₁,…,p_n, если p является истинным в любой интерпретации, в которой истинными являются p₁,…,p_n.

Вхождением переменной  в высказывание p называется связанным, если оно является вхождением в некоторое подвысказывание вида х(q) или вида х(q); в противном случае это вхождение называется свободным.

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

((g(₁))(g(₁, ₂)))( ₁(g(₁)))

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

Через р{х, а} обозначается результат подстановки терма, а вместо всех свободных вхождений переменной х в высказывание р, причем, если при такой подстановке все вхождения переменных из а остаются свободными, то терм а называется допустимым заменителем для х в р. Например, терм f(₅) является допустимым заменителем для ₆ в высказывании g((₅, (₆), и не является

допустимым заменителем для ₆ в высказывании ₅ (g(₅, ₆)). Высказывание р называется замкнутым (открытым), если оно не имеет свободных (связанных) вхождений переменных.

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

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

хр равносильно хр

хр равносильно хр

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

хр равносильно хр

хр равносильно хр

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

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

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

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

Теорема о равносильной замене: пусть q есть результат замены в высказывании р какого-либо вхождения подвысказывания r₁ на высказывание r₂; тогда если r₁ и r₂ равносильны, то р и q тоже равносильны.

Позитивным высказыванием называется такое, которое не имеет вхождений знака . Позитивной формой высказывания р называется любое равносильное ему позитивное высказывание .

Теорема о позитивной форме: если отрицания предикатных компонент высказывания р имеют равносильные себе предикаты, то р равносильно некоторому позитивному высказыванию q; высказывание q можно построить с помощью теоремы о равносильной замене, теорем об исключении операций ,  и теорем об отрицании для операций , , , , .

Пример построения позитивной формы отрицания высказывания: «для каждого положительного числа е существует положительное число  т.ч. для каждого числа х из х< следует, что х<е или х1».

ех(х<х<ех1 = eх(х<хх1) = eх(х<хх1) = eх(х<хх1) = eх(х<хeх>1) = « существует положительное число е т.ч. для каждого положительного числа  существует число х т.ч. х< и хe и х>1».

Теорема о выводе в логике предикатов: нижеследующие шесть правил преобразования высказываний образуют достаточный набор правил вывода в логике предикатов т.е. р₀ является кванторологическим следствием из p₁,…,p_n тттк р₀ может быть получено из р₁,…,р_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. Эгалитарная логика

или логика предикатов с равенством, т.е. с двухместным предикатным символом g²_0, который интерпретируется как знак равенства. Т.о. в эгалитарной логике предикат g²₀(a, b) выражает то, что мы привыкли выражать в виде a = b и понимать как констатацию того, что объекты с обозначениями a, b являются одинаковыми, равными, неотличимыми, идентичными. Эгалитарной интерпретацией формального языка называется такая, в которой g интерпретируется как знак равенства. Запись p₁, …, p_n│=q_{1, …}, q_m означает, что каждое из высказываний q_{1, …}, q_m является логическим следствием из высказываний p₁, …, p_n т.е. что оно является истинным в любой эгалитарной интерпретации, в которой оказываются истинными p₁, …, p_n. Высказывание p называется логически истинным, если │=p т.е. если p является истинным в любой эгалитарной интерпретации.

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

g(x, x)

g(x_1, y₁)… g(x_n, y_n)g(f(x_1, …, x_n), f(y_1, …, y_n))

g² (x_1, y₁)… g(x_n, y_n)(g f(x_1, …, x_n)(y_1, …, y_n))

Теорема об эгалитарной замене: пусть q есть результат замены в p некоторых вхождений терма a термом b; тогда если выражение g²₀(a, b) является истинным, то p равносильно q.

Теорема о транзитивности логического следствия: если p₁, …, p_n│=q₁, _…, q_m и q₁, …, q_m│= r_{1, …}, r_e, то p₁, …, p_n│= r_{1, …}, r_e.

Теорема о расширении списка гипотез: если p₁, …, p_n│= q, то p₀, …, p_n│= q.

Теорема дедукции: если высказывания p₁, …, p_n являются замкнутыми, то p₁, …, p_n│= p тогда и только тогда когда = p₁… p_np.

Теорема о конъюнктивизации гипотез: p₁, …, p_n│= p тттк p₁…p_n│= p.

Теорема о выводе в эгалитарной логике: правила тавтологии, отделения, обобщения, подтверждения, общевнесения, сущевнесения, тождества, равенства, неотличимости образуют достаточный набор правил вывода в эгалитарной логике, т.е. p₁, …, p_n│= p тттк p может быть получено из p₁, …, p_n с помощью этого набора правил.

Теорема о сравнительной силе выводов. Если p является тавтологическим следствием из p₁, …, p_n, то p является кванторологическим следствием из p₁, …, p_n. Если p является кванторологическим следствием из р₁,…,р_n, то p является логическим следствием из р₁,…,р_n.

Алгоритм – это…

Теорема о неразрешимости проблемы логического следствия (логической истинности): нельзя придумать алгоритм, который для любых высказываний p₀, …, p_n позволял бы разрешить вопрос о том, является или нет p₀ логическим следствием из p₁, …, p_n. Полезно обратить внимание на то, что проблема тавтологического следствия является разрешимой с помощью истинностных таблиц.

Замечание последние семь теорем не исключают случай n = 0.

Замечание если не оговорено противное, слово логика понимается как эгалитарная логика.

Тема 6. Формальные теории

предназначены для четкого изложения и развития тех или иных отраслей человеческих знаний. Задать формальную теорию – значит задать ее функциональные и предикатные символы, а также аксиомы, т. е. некоторые из высказываний, которые являются истинными в данной отрасли знаний. Развивать формальную теорию – значит пополнять запас ее теорем, т. е. таких высказываний, которые являются логическими следствиями аксиом.

Изложение любой формальной теории в принципе можно оформить в виде книжек с доказательными текстами:

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             Copyright © yurii.ru - 2023