Краткая методичка по логике (стр. 4 из 10)

Ø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 является тавтологическим

следствием из р₁,…,p_n тттк р₁Ù…Ùр Þ q является тавтологией. Эти три теоремы

легко доказываются с помощью истинностных таблиц.

Арифметическийспособ записи высказываний: исключаются знаки Þ, Û

и вместо Л, И, Øp, pÙq, pÚq употребляются соответственно 0, 1, `p, pq, p + q.

Например, арифметической записью высказывания (rÚpÞqÙr) будет

.

При арифметической записи высказываний с ними можно обращаться так, как будто они обозначают числа 0, 1, а. Логический плюс отличается от арифметического только тем, что 1 + 1 = 1. При этом полезно помнить следующие равенства:

p Þ q = `p + q

p Û q = p q + `p `qp p = p

p + p = p

p`p = 0

p + `p q = p + qp +`p = 1

p + p q = `p + q1 + 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

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

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

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

DpÞ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)

DpÞØØp

DØØpÞp

Другими словами, какое–либо высказывание p₀ является тавтологическим следствием из p₁,…,p_n тттк p₀ можно сделать членом последовательности высказываний, которая является индуктивной относительно этих шестнадцати правил и правил D p₁,…, Dp_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	Да	pq

r =`p`q + pq = pÛq т. e. турист должен спросить: верно ли, что Вы скажите правду если и только если эта дорога ведет в столицу.

Пример проверки рассуждения «(Профсоюзы поддержат президента на предстоящих выборах |p) только если (он подпишет законопроект о повышении заработной платы ½q). (Фермеры окажут президенту поддержку ½r) только если (он наложит вето на законопроект ½s). Очевидно, что он не подпишет законопроекта или не наложит на него вето. Следовательно президент потеряет голоса профсоюзников или голоса фермеров».

(pÞq)Ù(rÞs)Ù(ØpÚØs) ÞØpÚØr =

+`p +`r =`pq + rs + qs +`p +`r = + qs = + qs =`p +`q +`r +`s +qs =`p +`r + + qs =`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 + pqr +`p = qr +`q`r +`p

– не тавтология.

Пример проверки рассуждения «(Если наступит мир |p), то (возникнет депрессия |q), разве что (страна проведет программу перевооружения |r) или осуществит грандиозную социальную программу |s). Но договориться о целях такой грандиозной программы невозможно. Следовательно если наступит мир и не будет депрессии, то будет осуществляться программа перевооружения».

(pÞqÚØqÙ(rÚs))ÙØsÞpÙØqÞr =

=

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

Пример сокращения текста «Члены финансового комитета должны избираться среди членов дирекции. Нельзя быть одновременно членом дирекции и членом библиотечного совета, не будучи членом финансового комитета. Член библиотечного совета не может быть членом финансового комитета».