Краткая методичка по логике - (шпаргалка)
p>Тавтологияили тавтологически истинное высказывание - это высказывание со сплошными И в его столбце его истинностной таблицы. Высказывание 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) Таким образом, можно отбросить подчеркнутую часть текста.
