Тема 3. Пропозициональная логика
или логика элементарных высказываний изучает свойства логических операций Ø, Ù, Ú, Þ, Û, которые по смыслу их введения являются операциями над истинностными значениями:
Если высказывания р, q различны и элементарны, то эта таблица называется истинностной таблицей высказываний (p, q,) Øp, pÙq, pÚq, pÞq, pÛq. В общем случае при составлении истинностной таблицы какого-либо перечня высказываний надо поместить на ее вход все различные пропозициональные компоненты этих высказываний, сделать полный перебор истинностных значений во входных столбцах и записать соответствующие истинностные значения в результирующих столбцах.
Пример. В комнате без окон темно и неуютно. Универсум - множество комнат g g g
p q r
Тавтология или тавтологически истинное высказывание - это высказывание со сплошными И в его столбце его истинностной таблицы. Высказывание 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 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)Þ(Ø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) pÛq = Ø((pÞq)Þ Ø(qÞp))
Доказательство последнего равенства: pÛq = p q +`p`q Ø((pÞq)ÞØ(qÞp)) =
Пример. Упрощение высказываний.
(Ø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ÞØ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 – высказывание для вопроса
r =`p`q + p q = pÛq т. e. турист должен спросить: верно ли, что Вы скажите правду если и только если эта дорога ведет в столицу.
Пример проверки рассуждения «(Профсоюзы поддержат президента на предстоящих выборах | p) только если (он подпишет законопроект о повышении заработной платы ½q). (Фермеры окажут президенту поддержку ½r) только если (он наложит вето на законопроект ½s). Очевидно, что он не подпишет законопроекта или не наложит на него вето. Следовательно президент потеряет голоса профсоюзников или голоса фермеров».
(pÞq)Ù(rÞs)Ù(ØpÚØs) Þ ØpÚØr =
Пример проверки рассуждения «(В бюджете возникнет дефицит | p), если (не повысят пошлины | Øq). Если в бюджете будет дефицит, то (государственные расходы на общественные нужды сократятся | r). Значит, если повысят пошлины, то государственные расходы на общественные нужды не сократятся». (ØqÞp)Ù(pÞr)Þ(qÞØr) =
Пример проверки рассуждения «Если (подозреваемый совершил эту кражу | p), то (она была тщательно подготовлена | q) или (он имел соучастника | r). Если бы кража была подготовлена тщательно, то, если бы был соучастник, украдено было бы гораздо больше. Значит, подозреваемый невиновен». (pÞqÚr)Ù(qÞ(rÞØp))ÞØ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) Таким образом, можно отбросить подчеркнутую часть текста. Пример анализа рассуждения «(это преступление совершено в Кустанае | q). (Петров во время совершения преступления находился в Ростове | r). Следовательно (Петров не совершал этого преступления | Øp)».
qÙrÞØp – не тавтология «Преступление совершено в Кустанае. Поэтому если Петров совершил это преступление, то (он во время совершения преступления находился в Кустанае |s). Но Петрова в это время в Кустанае не было. Значит, Петров не совершал этого преступления». qÙ(qÞpÞs)ÙØp = … = 1 – тавтология т.е. рассуждение правильное. Рассуждение останется правильным, если из него выбросить первое предложение и ссылку на него во втором предложении: (pÞs)ÙØsÞØp = Задача. Выяснить, кто из четверых виновен на основе информации «Петров виновен, только если виновен Кулагин. Неверно, что виновность Родионова влечет виновность Сидорова и что Кулагин виновен, а Сидоров нет». p, q, r, s – виновен Петров, Кулагин, Родионов, Сидоров. (pÞq)ÙØ(rÞs)ÙØ(qÙØs) = (`p + q) т.е. Родионов виновен, остальные не виновны. Задача Кислера. Обвиняемые в подделке налоговых документов Браун, Джонс и Смит дают под присягой такие показания. Браун: Джонс виновен, а Смит не виновен. Джонс: Если Браун виновен, то виновен и Смит. Смит: Я не виновен, но хотя бы один из них двоих виновен.
Вопрос 1: Совместимы ли данные показания? Вопрос 2: Какое показание следует из другого? Вопрос 3: Если все виновны, то кто лжесвидетельствует? Вопрос 4: Если все сказали правду, то кто виновен? Вопрос 5: Если невинный говорит правду, а виновный лжет, то кто виновен, а кто невиновен?
Б – виновен Браун. Д – виновен Джонс. С – виновен Смит.
1. Да, только за счет третьей строки. 2. Из первого третье. 3. Браун и Смит. 4. Джонс виновен, остальные невиновны. 5. Джонс невиновен, остальные виновны.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|