logika (675739), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

p q r

Тавтология или тавтологически истинное высказывание - это высказывание со сплошными И в его столбце его истинностной таблицы. Высказывание q называется тавтологическим следствием (из) высказываний p₁,…,p_n, если в истинностной таблице высказываний p₁,…,p_n,,q столбец q содержит И в любой строке, которая содержит И во всех столбцах p₁,…,p_n. Например, построенная выше таблица показывает, что:

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, 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)

Таким образом, можно отбросить подчеркнутую часть текста.

Характеристики

Список файлов реферата