Реферат: Краткая методичка по логике
--PAGE_BREAK--Интерпретацияформального языка. Переменная выражает, нотирует, обозначает произвольный объект из некоторого не пустого множества, которое называется денотарием или универсумом данной интерпретации и элементы которого тем самым являются денотатами или значениями переменной. n-местный функциональный знак обозначает n-местную операцию на универсуме. n-местный предикатный знак обозначает изначальную взаимосвязь между любыми nобъектами универсума. Термы обозначают объекты универсума, а высказывания обозначают истину или ложь, т. е. денотатами термов являются объекты универсума, а денотатами высказываний являются истина и ложь. Задать интерпретацию формального языка значит задать ее универсум и связанные с ним значения всех нужных нам функциональных и предикатных знаков; тогда значения всех нужных термов и формул при любых значениях фигурирующих в них переменных определяются индукцией по их построению с учетом такой интерпретации логических знаков:"xp— обобщение высказывания р по х является истинным тттк р является истинным для всех значений переменной х; синонимы: р для каждого х, р для любого х, р для всех x, р для произвольного х.
$xp— подтверждение высказывания р по х является истинным тттк р является истинным хотя бы для одного значения переменной х; синонимы: существует х т.ч. р, р для некоторого х.
Øp— отрицание высказывания р является истинным тттк р является ложным; синонимы: не р, неверно что р.
pÙq— конъюнкция высказываний р, q является истинной тттк оба ее конъюнкта р, q являются истинными; синонимы: р и q, и р и q.
pÚq— дизъюнкция высказываний p, q является ложной тттк оба ее дизъюнкта р, q являются ложными; синонимы: р или q, или р или q.
pÞq — импликация высказываний p, q является ложной тттк посылка р является истинной, а заключение q является ложным; синонимы: р только если q, если р то q, q если р, р тогда q, q когда р, для того чтобы р необходимо чтобы q, для того чтобы q достаточно чтобы р, р следовательно q, из того что р следует что q.
pÛq — эквиваленция высказываний р, q является истинной тттк ее части р, q обе являются истинными или обе являются ложными; синонимы: р если и только если q, р тогда и только тогда когда q, для того чтобы р необходимо и достаточно чтобы q, р эквивалентно q.
Замечание.Иногда высказывания записывают на смеси формального, обычного и математического языка. Все такие записи будем рассматривать как обозначения соответствующих высказываний формального языка.
Замечание.Введение обозначений для высказываний порождает двусмысленность в использовании знака равенства, поскольку сами высказывания являются некоторыми обозначениями, а именно обозначениями истины или лжи. При наличии иерархии обозначений такую двусмысленность обычно снимают соглашением о том, что равенство понимается как равенство между исходными объектами. Т. о. равенство p=q означает, что р и q имеют одинаковые истинностные значения т. е. являются равносильными.
Пример.Каждый кулик свое болото хвалит.
Универсум — множество куликов и болот
g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1081">(x) — х есть кулик
g<img width=«11» height=«24» src=«ref-1_290262052-197.coolpic» v:shapes="_x0000_i1082">(x) — х есть болото
g<img width=«11» height=«25» src=«ref-1_290262249-201.coolpic» v:shapes="_x0000_i1083">(x, у) — х хвалит у
g<img width=«11» height=«24» src=«ref-1_290256662-200.coolpic» v:shapes="_x0000_i1084">(x, у) — у свое для х
"c1((((g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1085">(c1))Ù(g<img width=«11» height=«24» src=«ref-1_290262052-197.coolpic» v:shapes="_x0000_i1086">(c2)))Ù(g<img width=«11» height=«24» src=«ref-1_290256662-200.coolpic» v:shapes="_x0000_i1087">(c1, c2)))Þ(g<img width=«11» height=«25» src=«ref-1_290262249-201.coolpic» v:shapes="_x0000_i1088">(c1, c2)))
Пример.Сумма квадратов двух положительных чисел меньше квадрата их суммы.
Универсум — множество положительных чисел.
f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1089">(x) — квадрат числа x
f<img width=«11» height=«24» src=«ref-1_290263608-197.coolpic» v:shapes="_x0000_i1090">(x, y) — сумма чисел x, y
g<img width=«11» height=«24» src=«ref-1_290263608-197.coolpic» v:shapes="_x0000_i1091">(x, y) – xменьше y
g<img width=«11» height=«24» src=«ref-1_290263608-197.coolpic» v:shapes="_x0000_i1092">(f<img width=«11» height=«24» src=«ref-1_290263608-197.coolpic» v:shapes="_x0000_i1093">(f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1094">(c1), f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1095">(c2)), f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1096">(f<img width=«11» height=«24» src=«ref-1_290263608-197.coolpic» v:shapes="_x0000_i1097">(c1, c2)))
Можно записать по-другому:
универсум — множество действительных чисел
f<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1098"> — число 0
((g<img width=«11» height=«24» src=«ref-1_290263608-197.coolpic» v:shapes="_x0000_i1099">(f<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1100">, c1))Ù(g<img width=«11» height=«24» src=«ref-1_290263608-197.coolpic» v:shapes="_x0000_i1101">(f<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1102">, c2)))Þ(g<img width=«11» height=«24» src=«ref-1_290263608-197.coolpic» v:shapes="_x0000_i1103">(f<img width=«11» height=«24» src=«ref-1_290263608-197.coolpic» v:shapes="_x0000_i1104">(f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1105">(c1), f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1106">(c2)), f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1107">(f<img width=«11» height=«24» src=«ref-1_290263608-197.coolpic» v:shapes="_x0000_i1108">(c1, c2)))
Пример.Только я один знаю об этом.
Универсум – множество людей
f<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1109"> — я
g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1110">(x) — xзнает об этом
g<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1111">(x, y) — xидентичен y
(g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1112">(f<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1113">))Ù("c1((Ø(g<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1114">(c1, f<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1115">)))Þ(Ø(g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1116">(c1))))
Никто не знает об этом: "c1(Ø(g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1117">(c1)))
Все знают об этом: "c1(g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1118">(c1))
Кто-нибудь знает об этом: $c1(g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1119">(c1))
Пример. Здесь холодно, но не сыро: (g<img width=«9» height=«24» src=«ref-1_290251301-188.coolpic» v:shapes="_x0000_i1120">)Ù(Ø(g<img width=«11» height=«24» src=«ref-1_290251489-197.coolpic» v:shapes="_x0000_i1121">))
Пример.Ни pни q: Øpи Øq
Пример. Если pто qиначе r: (pÞq)Ù(ØpÞr)
Пример.pлибо q: pÙØqÚØpÙq
Пример.pпоэтому q: pÙ(pÞq)
Пример.Чай без сахара не сладкий и не вкусный.
g<img width=«9» height=«24» src=«ref-1_290251301-188.coolpic» v:shapes="_x0000_i1122"> — чай содержит сахар
g<img width=«11» height=«24» src=«ref-1_290251489-197.coolpic» v:shapes="_x0000_i1123"> — чай сладкий
g<img width=«9» height=«25» src=«ref-1_290251686-194.coolpic» v:shapes="_x0000_i1124"> — чай вкусный
(Ø(g<img width=«9» height=«24» src=«ref-1_290251301-188.coolpic» v:shapes="_x0000_i1125">))Þ((Ø( g<img width=«11» height=«24» src=«ref-1_290251489-197.coolpic» v:shapes="_x0000_i1126">))Ù(Ø( g<img width=«9» height=«25» src=«ref-1_290251686-194.coolpic» v:shapes="_x0000_i1127">)))
Возможен другой перевод:
((Ø(g<img width=«9» height=«24» src=«ref-1_290251301-188.coolpic» v:shapes="_x0000_i1128">))Þ(Ø( g<img width=«11» height=«24» src=«ref-1_290251489-197.coolpic» v:shapes="_x0000_i1129">)))Ù((Ø( g<img width=«9» height=«24» src=«ref-1_290251301-188.coolpic» v:shapes="_x0000_i1130">))Þ((Ø( g<img width=«9» height=«25» src=«ref-1_290251686-194.coolpic» v:shapes="_x0000_i1131">)))
Пример.Его отец слесарь, а все братья токари.
Универсум – множество мужчин
f<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1132"> — он
f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1133">(x) — отец для x
g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1134">(x) — xесть слесарь
g<img width=«11» height=«24» src=«ref-1_290262052-197.coolpic» v:shapes="_x0000_i1135">(x) — xесть токарь
g<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1136">(x, y) — xидентичен y
(g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1137">(f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1138">(f<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1139">)))Ù("c1(((Ø(g<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1140">(c1, f<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1141">)))Ù(g<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1142">(f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1143">(c1), ( f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1144">(f<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1145">))))Þ(g<img width=«11» height=«24» src=«ref-1_290262052-197.coolpic» v:shapes="_x0000_i1146">(c1))))
Тема 3. Пропозициональная логика
или логика элементарных высказываний изучает свойства логических операций Ø, Ù, Ú, Þ, Û, которые по смыслу их введения являются операциями над истинностными значениями:
продолжение
--PAGE_BREAK--
Если высказывания р, q различны и элементарны, то эта таблица называется истинностной таблицей высказываний (p, q,) Øp, pÙq, pÚq, pÞq, pÛq. В общем случае при составлении истинностной таблицы какого-либо перечня высказываний надо поместить на ее вход все различные пропозициональные компоненты этих высказываний, сделать полный перебор истинностных значений во входных столбцах и записать соответствующие истинностные значения в результирующих столбцах.
Пример.В комнате без окон темно и неуютно.
Универсум — множество комнат
g<img width=«9» height=«25» src=«ref-1_290274327-188.coolpic» v:shapes="_x0000_i1147">(c1) - c1имеет окно p— комната имеет окно
g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1148">(c1) — в c1темно q— в комнате темно
g<img width=«11» height=«24» src=«ref-1_290262052-197.coolpic» v:shapes="_x0000_i1149">(c1) – в c1уютно r— в комнате уютно
<img width=«79» height=«2» src=«ref-1_290274892-159.coolpic» v:shapes="_x0000_s1033"><img width=«79» height=«2» src=«ref-1_290274892-159.coolpic» v:shapes="_x0000_s1032"><img width=«79» height=«2» src=«ref-1_290274892-159.coolpic» v:shapes="_x0000_s1031">(Ø(g<img width=«9» height=«25» src=«ref-1_290274327-188.coolpic» v:shapes="_x0000_i1150">(c1)))Þ((g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1151">(c1))Ù(Ø(g<img width=«11» height=«24» src=«ref-1_290262052-197.coolpic» v:shapes="_x0000_i1152">(c1)))) ØpÞqÙØr
p q r
p
q
r
Ø
p
Ø
r
q
Ù
Ø
r
Ø
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, pq, p+ q.
Например, арифметической записью высказывания (rÚpÞqÙr) будет <img width=«61» height=«28» src=«ref-1_290275934-245.coolpic» v:shapes="_x0000_i1153">.
При арифметической записи высказываний с ними можно обращаться так, как будто они обозначают числа 0, 1, а. Логический плюс отличается от арифметического только тем, что 1 + 1 = 1. При этом полезно помнить следующие равенства:
p Þq = `p + q <img width=«39» height=«28» src=«ref-1_290276179-219.coolpic» v:shapes="_x0000_i1154">
p Ûq = p q + `p `q p p = p
<img width=«83» height=«25» src=«ref-1_290276398-277.coolpic» v:shapes="_x0000_i1155"> p + p = p
<img width=«68» height=«25» src=«ref-1_290276675-258.coolpic» v:shapes="_x0000_i1156"> 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 =<img width=«21» height=«25» src=«ref-1_290276933-202.coolpic» v:shapes="_x0000_i1157"> + p q = 1
(ØpÞØq)Þ(ØqÞp)Þq= <img width=«92» height=«31» src=«ref-1_290277135-269.coolpic» v:shapes="_x0000_i1158"> +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)) = <img width=«81» height=«31» src=«ref-1_290277404-282.coolpic» v:shapes="_x0000_i1159"> = (`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 = <img width=«36» height=«28» src=«ref-1_290277686-226.coolpic» v:shapes="_x0000_i1160"> + 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является тавтологическим следствием из p1,…,pnтттк его можно получить из p1,…, pnс помощью правила отделения и нижеследующих пятнадцати беспосылочных правил:
DpÞqÞp
D(pÞpÞq)Þ(pÞq)
D(pÞq)Þ((qÞr)Þ(pÞr))
DpÙqÞp
DpÙqÞq
D(pÞq)Þ((pÞr)Þ(pÞqÙr))
DpÞpÚq
DqÞ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является тавтологическим следствием из p1,…,pn тттк pможно сделать членом последовательности высказываний, которая является индуктивной относительно этих шестнадцати правил и правил Dp1,…, 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+ pq= pÛqт. e. турист должен спросить: верно ли, что Вы скажите правду если и только если эта дорога ведет в столицу.
Примерпроверки рассуждения «(Профсоюзы поддержат президента на предстоящих выборах |p) только если (он подпишет законопроект о повышении заработной платы ½q). (Фермеры окажут президенту поддержку ½r) только если (он наложит вето на законопроект ½s). Очевидно, что он не подпишет законопроекта или не наложит на него вето. Следовательно президент потеряет голоса профсоюзников или голоса фермеров».
(pÞq)Ù(rÞs)Ù(ØpÚØs) ÞØpÚØr= <img width=«123» height=«28» src=«ref-1_290277912-346.coolpic» v:shapes="_x0000_i1161"> +`p+`r=`pq+ rs+ qs+`p+`r= <img width=«91» height=«31» src=«ref-1_290278258-285.coolpic» v:shapes="_x0000_i1162"> + qs= <img width=«111» height=«28» src=«ref-1_290278543-325.coolpic» v:shapes="_x0000_i1163"> + qs=`p+`q+`r+`s+qs=`p+`r+ <img width=«19» height=«25» src=«ref-1_290278868-206.coolpic» v:shapes="_x0000_i1164"> + qs=`p+`r+1 = 1– тавтология, т.е. рассуждение правильное.
Пример проверки рассуждения «(В бюджете возникнет дефицит |p), если (не повысят пошлины |Øq). Если в бюджете будет дефицит, то (государственные расходы на общественные нужды сократятся |r). Значит, если повысят пошлины, то государственные расходы на общественные нужды не сократятся».
(ØqÞp)Ù(pÞr)Þ(qÞØr) = <img width=«85» height=«28» src=«ref-1_290279074-293.coolpic» v:shapes="_x0000_i1165"> +`q+ `r=`q`p+ p`r+`q+`r= `q(`p+1) +`r(p+ 1) =`q+`r= <img width=«19» height=«25» src=«ref-1_290279367-200.coolpic» v:shapes="_x0000_i1166"> — не тавтология, т.е. нельзя сказать, что рассуждение правильно.
Примерпроверки рассуждения «Если (подозреваемый совершил эту кражу |p), то (она была тщательно подготовлена |q) или (он имел соучастника |r). Если бы кража была подготовлена тщательно, то, если бы был соучастник, украдено было бы гораздо больше. Значит, подозреваемый невиновен».
(pÞqÚr)Ù(qÞ(rÞØp))ÞØp= <img width=«128» height=«28» src=«ref-1_290279567-340.coolpic» v:shapes="_x0000_i1167"> +`p= p`q`r+ pqr+`p= qr+`q`r+`p
– не тавтология.
Примерпроверки рассуждения «(Если наступит мир |p), то (возникнет депрессия |q), разве что (страна проведет программу перевооружения | r) или осуществит грандиозную социальную программу |s). Но договориться о целях такой грандиозной программы невозможно. Следовательно если наступит мир и не будет депрессии, то будет осуществляться программа перевооружения».
(pÞqÚØqÙ(rÚs))ÙØsÞpÙØqÞr = <img width=«340» height=«28» src=«ref-1_290279907-425.coolpic» v:shapes="_x0000_i1168"> = <img width=«661» height=«28» src=«ref-1_290280332-712.coolpic» v:shapes="_x0000_i1169">
т.е. рассуждение правильное.
Примерсокращения текста «Члены финансового комитета должны избираться среди членов дирекции. Нельзя быть одновременно членом дирекции и членом библиотечного совета, не будучи членом финансового комитета. Член библиотечного совета не может быть членом финансового комитета».
p– он является членом финансового комитета
q– он является членом дирекции
r– он является членом библиотечного фонда
(pÞq)Ù(ØpÞØ(qÙr))Ù(rÞØp) = (`p+ q)(p+`q+`r)(`r+`p) = (`p+q)<img width=«64» height=«28» src=«ref-1_290281044-267.coolpic» v:shapes="_x0000_i1170"> = (`p+ q)<img width=«52» height=«25» src=«ref-1_290281311-244.coolpic» v:shapes="_x0000_i1171">=(`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 = <img width=«51» height=«28» src=«ref-1_290281555-252.coolpic» v:shapes="_x0000_i1172"> +`p = <img width=«20» height=«28» src=«ref-1_290281807-207.coolpic» v:shapes="_x0000_i1173"> +`p = p + s +`p = 1 + s = 1
Задача.Выяснить, кто из четверых виновен на основе информации «Петров виновен, только если виновен Кулагин. Неверно, что виновность Родионова влечет виновность Сидорова и что Кулагин виновен, а Сидоров нет».
p, q, r, s– виновен Петров, Кулагин, Родионов, Сидоров.
(pÞq)ÙØ(rÞs)ÙØ(qÙØs) = (`p + q)<img width=«57» height=«28» src=«ref-1_290282014-263.coolpic» v:shapes="_x0000_i1174"> = (`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, понимаются соответственно как конъюнкция p1Ùp2Ùp3Ù… и дизъюнкция p1Úp2Úp3Ú… значений высказывания pдля всевозможных значений переменной х. Высказывание pназывается кванторологически истинным при любой интерпретации.
Из определений следует, что тавттологически истинное высказывание является кванторологически истинным. Обратное вообще говоря не верно: высказывание "хpÞ$хpявляется кванторологически истинным, но не является тавтологически истинным.
Истинностная таблица.
"
х
p
$
х
p
"
х
p
Þ
$
х
p
Л
Л
И
Л
И
И
И
Л
Л
И
И
И
Истинностная схема.
p
1
,
p
2
,
p
3
…
"
х
p
p1
Ù
p2
Ù
p3
Ù
…
$
х
p
p1
Ú
p2
Ú
p3
Ú
…
"
х
p
Þ
$
х
p
ЛЛЛ…
Л
Л
И
ЛЛЛ…
Л
И
И
………
…
…
…
ИИИ…
И
И
И
Высказывание qназывается кванторологическим следствием (из) высказываний р1,…,pn, если p является истинным в любой интерпретации, в которой истинными являются p1,…,pn.
Вхождениемпеременной cв высказывание pназывается связанным, если оно является вхождением в некоторое подвысказывание вида "х(q) или вида $х(q); в противном случае это вхождение называется свободным.
Например, первое и второе вхождения c1в высказывание
((g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1175">(c1))Ù(g<img width=«11» height=«24» src=«ref-1_290282457-191.coolpic» v:shapes="_x0000_i1176">(c1, c2)))Þ($c1(g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1177">(c1)))
являются свободными, а третье и четвертое – связанными.
Через р{х, а} обозначается результат подстановки терма, а вместо всех свободных вхождений переменной х в высказывание р, причем, если при такой подстановке все вхождения переменных из а остаются свободными, то терм а называется допустимым заменителем для х в р. Например, терм f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1178">(c5) является допустимым заменителем для c6в высказывании g<img width=«11» height=«24» src=«ref-1_290282457-191.coolpic» v:shapes="_x0000_i1179">((c5, (c6), и не является
допустимым заменителем для c6в высказывании $c5 (g<img width=«11» height=«24» src=«ref-1_290282457-191.coolpic» v:shapes="_x0000_i1180">(c5, c6)). Высказывание р называется замкнутым (открытым), если оно не имеет свободных (связанных) вхождений переменных.
продолжение
--PAGE_BREAK--Теорема о всезначности переменной: р = И тттк "хр = И
Теоремаоб отрицании обобщения и подтверждения:
Ø"хр равносильно $хØр
Ø$хр равносильно "хØр
Теоремао взаимоисключении кванторов:
"хр равносильно Ø$хØр
$хр равносильно Ø"хØр
Теоремао перестановочности кванторов:
"х"ур равносильно "у"хр
$х$ур равносильно $у$хр
Типовые кванторы. Запись "qхр обозначает высказывание "х(qÞр), а запись $qхр обозначает высказывание $х(qÙр).
Теорема о равносильной замене: пусть qесть результат замены в высказывании р какого-либо вхождения подвысказывания r1на высказывание r2; тогда если r1 и r2 равносильны, то р и q тоже равносильны.
Позитивным высказыванием называется такое, которое не имеет вхождений знака Ø. Позитивной формой высказывания р называется любое равносильное ему позитивное высказывание .
Теорема о позитивной форме: если отрицания предикатных компонент высказывания р имеют равносильные себе предикаты, то р равносильно некоторому позитивному высказыванию q; высказывание qможно построить с помощью теоремы о равносильной замене, теорем об исключении операций Þ, Ûи теорем об отрицании для операций ", $, Ø, Ù, Ú.
Пример построения позитивной формы отрицания высказывания: «для каждого положительного числа е существует положительное число dт.ч. для каждого числа х из х<dследует, что х<е или х£1».
Ø"е$d"х(х<dÞх<еÚх£1 = $e"d$хØ(х<dÞх<eÚх£1) = $e"d$хØ(Øх<dÚх<eÚх£1) = $e"d$х(х<dÙØх<eÙØх£1) = $e"d$х(х<dÙх³eÙх>1) = « существует положительное число е т.ч. для каждого положительного числа dсуществует число х т.ч. х<dи х³eи х>1».
Теорема о выводе в логике предикатов: нижеследующие шесть правил преобразования высказываний образуют достаточный набор правил вывода в логике предикатов т.е. р0является кванторологическим следствием из p1,…,pn тттк р0может быть получено из р1,…, рn с помощью этих шести правил:
Dt– правило тавтологии
Ds, sÞr, r– правило отделения
D"хрÞp{x, a} – правило обобщения
Dp{x, a} Þ$xp– правило подтверждения
DqÞr, qÞ"хr – правило общевнесения
DrÞq, $xrÞq– правило сущевнесения
где tесть тавтология, qне имеет свободных вхождений x, терм а является допустимым заменителем для х в р. Теорема не исключает случай n= 0.
продолжение
--PAGE_BREAK--Тема 5. Эгалитарная логика
или логика предикатов с равенством, т.е. с двухместным предикатным символом g20, который интерпретируется как знак равенства. Т.о. в эгалитарной логике предикат g20(a, b) выражает то, что мы привыкли выражать в виде a = b и понимать как констатацию того, что объекты с обозначениями a, b являются одинаковыми, равными, неотличимыми, идентичными. Эгалитарной интерпретацией формального языка называется такая, в которой g<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1181"> интерпретируется как знак равенства. Запись p1, …, pn│=q1, …, qm означает, что каждое из высказываний q1, …, qm является логическим следствием из высказываний p1, …, pn т.е. что оно является истинным в любой эгалитарной интерпретации, в которой оказываются истинными p1, …, pn. Высказывание p называется логически истинным, если │=p т.е. если p является истинным в любой эгалитарной интерпретации.
Правиламитождества, равенства, неотличимости называются следующие три правила соответственно:
Dg<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1182">(x, x)
Dg<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1183">(x1, y1)Ù…Ùg<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1184">(xn, yn)Þg<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1185">(f(x1, …,xn), f(y1, …,yn))
Dg2 (x1, y1)Ù…Ùg<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1186">(xn, yn)Þ(g f(x1, …,xn)Þ(y1, …,yn))
Теорема об эгалитарной замене: пусть q есть результат замены в p некоторых вхождений терма a термом b; тогда если выражение g20(a, b) является истинным, то p равносильно q.
Теорема о транзитивности логического следствия: если p1, …, pn│=q1,…, qm и q1, …, qm│= r1, …, re, то p1, …, pn│= r1, …, re.
Теорема о расширении списка гипотез: если p1, …, pn│= q, то p0, …, pn│= q.
Теорема дедукции: если высказывания p1, …, pn являются замкнутыми, то p1, …, pn│= p тогда и только тогда когда ê= p1Ù…ÙpnÞp.
Теорема о конъюнктивизации гипотез: p1, …, pn│= p тттк p1Ù…Ùpn│= p.
Теорема о выводе в эгалитарной логике: правила тавтологии, отделения, обобщения, подтверждения, общевнесения, сущевнесения, тождества, равенства, неотличимости образуют достаточный набор правил вывода в эгалитарной логике, т.е. p1, …, pn│= p тттк p может быть получено из p1, …, pn с помощью этого набора правил.
Теорема о сравнительной силе выводов. Если p является тавтологическим следствием из p1, …, pn, то p является кванторологическим следствием из p1, …, pn. Если p является кванторологическим следствием из р1,…, рn, то p является логическим следствием из р1,…, рn.
Алгоритм– это…
Теорема о неразрешимости проблемы логического следствия (логической истинности): нельзя придумать алгоритм, который для любых высказываний p0, …, pn позволял бы разрешить вопрос о том, является или нет p0логическим следствием из p1, …, pn. Полезно обратить внимание на то, что проблема тавтологического следствия является разрешимой с помощью истинностных таблиц.
Замечаниепоследние семь теорем не исключают случай 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-×-×-×-×-×-×-×-×-×-
Здесь штрих-пунктирная линия обозначает пояснение о том, с помощью какого правила порождения получено соответствующее знакосочетание. Для удобства таких пояснений знакосочетания a1,…, tnнумеруются последовательно от 1 до k+е+m+n. Вспомним, что правила порождения теорем являются правилами вывода, что конечная индуктивная последовательность теорем является доказательством и что следующие девять правил, называемых основными, образуют достаточный набор правил вывода из аксиом: правила тавтологии, отделения, обобщения, подтверждения, общевнесения, сущевнесения, тождества, равенства, неотличимости.
Такая форма изложения делает доказательство легко проверяемым, но практически не применяется из-за ее громоздкости.
Способы более компактного изложения формальной теории.
1. Последовательность a1,…, reне записывается, потому что при достаточном навыке термы и формулы распознаются без построения их индуктивных последовательностей.
2. В последовательность t1,…, tnвключаются теоремы из других доказательных текстов.
3. Для двухместного функционального или предикатного знака vиспользуется операционная форма записи: вместо v(a,b) пишут (a)v(b).
4. При операционной форме записи принимается соглашение об упразднении некоторых пар скобок в соответствии с соглашением об убывании силы связи в последовательности: одноместный функциональный знак, двухместный функциональный знак, одноместный предикатный знак, двухместный предикатный знак, логический знак.
5. Используются специальные начертания для функциональных и предикатных знаков. Например в теории чисел: 0, 1, 2, 3 — нульместные функциональные знаки; Ö, sin, cos — одноместные функциональные знаки; +, -, ´, /,— двухместные функциональные знаки; <,>,£,³— двухместные предикатные знаки.
6. Используются знаковые фигуры. Например, åх=3х обозначает сумму 3+4+5.
7. Вводится определяющая аксиома g(х1,..., х11)Ûр для нового n-местного предикатного символа g. Здесь переменные х1,..., хnпопарно различны, а высказывание р не имеет свободных вхождений переменных, отличных от х1,..., хn.
8. Вводится определяющая аксиома р{х, ¦( х1,..., хn)}для нового n— местного функционального символа ¦в тех случаях, когда формула $рх является теоремой. Здесь переменные х, х1,..., хnпопарно различны, а р не имеет свободное вхождение переменных, отличных от х, х1,..., хn.
Теорема об определениях: если теория Т2 получена из теории Т1 путем добавления определяющей аксиомы для нового функционального или предикатного символа vто для каждой теоремы теории Т2 существует равносильная ей теорема теорииТ1.
9. Кроме девяти основных применяются дополнительные правила вывода, например правило отделения конъюнкта DpÙg, р и правило присоединения дизъюнкта Dр, pÚg.
10. Применяются известные методы доказательства. Обоснование таких методов дается в учебниках логики. Например метод доказательства от противного основан на следующей теореме.
Теоремао доказательстве методом от противного: если формальная теория Т2 получена путем добавления аксиомы Øр к аксиомам теории Т1 и если формулы q, Øqявляются теоремами теории Т2, то формула р является теоремой теории Т1.
Формальная арифметикаформализует систему знаний о целых неотрицательных числах, использует в качестве исходных четыре функциональных и два предикатных знака
интерпретируемых в соответствии с их известными со школы специальными начертаниями, имеет такие аксиомы
Ø1=0
х + 1= y+ Þx= y
x + 0 = x
x + (y + 1) = (x + y) + 1
x×0 = 0
x×(y + 1) = x×y + x
Øx <
x <y + 1 Ûx <y Úx = y
p íx, 0ýÚ"(pÞíx, x + 1ý)Þp
Здесь при записи аксиом использованы ранее перечисленные соглашения о компактизации изложения и известное соглашение о том, что знак умножения связывает сильнее знака сложения. Если такие соглашения не принимать, то к примеру первую аксиому следовало бы записать в виде Ø(g<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1193">(¦<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1194">,¦<img width=«9» height=«24» src=«ref-1_290251301-188.coolpic» v:shapes="_x0000_i1195">)).
Примеропределяющих аксиом для новых нульместных функциональных знаков 2, 3, 4, 5 и новых двухместных предикатных знаков >, £,³,¹:
продолжение
--PAGE_BREAK--
Заметим, что знак <можно было бы не включать в перечень исходных знаков формальной арифметики, а ввести его с помощью определяющей аксиомы c1<c2 Û$c3(Øc3= 0 Ùc1+ c3 = c2).
Примердоказательного текста в формальной арифметике (k= 3, е = 6, m= 1, n= 3):
Компактизированный текст:
Словесный вариант: «Если единица не равна нулю, то тем самым существует не равное нулю число. Но единица не равна нулю. Следовательно, существует число, не равное нулю».
Тема 7. Множества и функции.
В этой теме A, B, C, D, E, F, G, X, Y, Z, X1, Z1,…, Xn, Yn, Zn обозначают попарно различные переменные. Множество – это совокупность различных объектов, мыслимая как единый новый объект. Различные объекты, из которых составлено множество, называются его элементами. Соотношение xÎA означает, что объект х есть элемент множества A. Отрицание соотношения xÎA записывается в виде xÏA. Соотношение АÌВ означает, что А есть подмножество множества В, т.е. что каждый элемент множества А является элементом множества В. Отрицание соотношения АÌВ записывается в виде АËВ. Множество, элементами которого являются все те и только те объекты вида а, для которых истинно соотношение p, обозначается через {a|p}. Множество {x|"A(xÏA)} называется пустым множеством и обозначается символом Ø. Множество {x|x = x1Ú…Úx = xn} обозначается через {x1,…,xn}. Множество {x|xÎAÚxÎB} называется объединением множеств А, В и обозначается через АÈВ. Множество {x|xÎAÙxÎB} называется пересечением множеств А, В и обозначается через АÇВ. Множество {x|xÎAÙxÏB} называется дополнением множества В относительно А или результатом удаления из множества А элементов множества В и обозначается через А\В.
Простейшие
теоремы
: 3Ï{9, 7, 3}, {x+5|x2 = 4} = {3, 7], AÏA, AÌA, …
Обозначения для некоторых множеств:
N — множество натуральных чисел
Z -множество целых чисел
R — множество действительных чисел
Упорядоченная n-ка объектов x1,…,xn обозначается через (x1,…,xn) и определяется так: (x1) = x1
(x1, x2) = {{x1}, { x1, x2}}
(x1, x2, x3) = ((x1, x2), x3)
(x1, x2, x3,x4) = ((x1, x2, x3), x4)
………………………………..
Упорядоченная n-ка называется еще n-мерным упорядоченным набором, вектором, точкой, кортежем. Объект x1 называется k-той компонентой или координатой n-мерного набора (x1,…,xn) и обозначается через koor<img width=«11» height=«24» src=«ref-1_290292335-196.coolpic» v:shapes="_x0000_i1228">(x1,…,xn). Множество {x1,…,xn|x1Îz1Ù…ÙxnÎzn} называется декартовым произведением множеств z1,…,zn и обозначается через z1´…´zn. Если А — множество упорядоченных n-ок, то множество {xk|(x1,…,xnÎA} называется k-той проекцией n-мерного множества А и обозначается через π<img width=«11» height=«24» src=«ref-1_290292335-196.coolpic» v:shapes="_x0000_i1229">А. Через Аn обозначается множество А´…´А (n множителей). Соглашение: знаки ´, Ç, связывают сильнее чем È, \.
Простейшие теоремы: (x1,…,xn) = (y1,…,yn)Ûx1= y1Ù…Ùxn= yn, (9, 9, 9)¹(9, 9), p<img width=«9» height=«25» src=«ref-1_290292727-193.coolpic» v:shapes="_x0000_i1230">(A´B´C´D´E) = C, {5. 7}2 = {(5, 5), (5, 7), (7, 5), (7, 7)}, koor<img width=«11» height=«24» src=«ref-1_290292920-203.coolpic» v:shapes="_x0000_i1231">(5, 7, 9) = 9, koor<img width=«11» height=«24» src=«ref-1_290263608-197.coolpic» v:shapes="_x0000_i1232">(5, 7, 9) = koor<img width=«9» height=«24» src=«ref-1_290293320-194.coolpic» v:shapes="_x0000_i1233">(5, 7, 9) = koor<img width=«11» height=«24» src=«ref-1_290293514-194.coolpic» v:shapes="_x0000_i1234">(5, 7, 9) = H, {7}´{8, 5}´{9} = {(7, 8, 9), (7, 5,9)}. {4}5 = {(4, 4, 4, 4, 4)}, p<img width=«11» height=«24» src=«ref-1_290292920-203.coolpic» v:shapes="_x0000_i1235">{(1, 2, 3), (1, 3, 2), (2, 3, 4)} = {2, 3}. A´B´C = (A´B)´C.
Функцией называется множество, любой элемент которого есть упорядоченная двойка. Множество π<img width=«11» height=«24» src=«ref-1_290263608-197.coolpic» v:shapes="_x0000_i1236">F называется областью определения или доменом функции F и обозначается dom F. Множество π<img width=«11» height=«24» src=«ref-1_290282457-191.coolpic» v:shapes="_x0000_i1237">F называется областью значений или ранжиром функции F и обозначается ran F. Если (x,y)ÎF, то y называется значением функции F в x и обозначается F(x). Если АÌdomF, то множество {y|$ÎAÙ(x, y)ÎF)} называется образом множества А относительно функции F и обозначается F[А]. Функция F в случае dom F = A и ran FÌB / ranF=B называется еще отображением множества А в/на множество В. Запись F: А®В означает что F есть отображение множества А в множество В. Функция F называется сужением функции G (на множество dom F), а функция G называется расширением функции F (на множество dom G), если F есть результат удаления из G всех тех (x, y), для которых xÏdom F. Если F есть функция, то {(y, x)ï(x, y)ÎF} тоже есть функция, называемая обратной по отношению к F. Очевидно, что если функция G является обратной по отношению к функции F, то F является обратной по отношению к G. Если dom F есть множество упорядоченных n-ок, то функция F называется n-аргументной и вместо F((x1,…,xn)) используют более короткое обозначение F(x1,…,xn). Функция F называется однозначной, если из (x, y)ÎF и (x, z)ÎF следует y=z. Функция называется взаимно однозначной или биективной, если она сама и обратная к ней функция являются однозначными. Последовательностью называется однозначная функция F т.ч. dom F = N. Если F есть последовательность и nÎN, то F(n) называется n-м членом последовательности и обычно обозначается через Fn.
Множество А называется бесконечным, если существует биективное отображение множества N в множество А. Множество называется конечным, если оно не является бесконечным.
Простейшие теоремы: cos(0)=1, cos[{0}]= {1}, Аrccos и cos обратны друг к другу, функция arccos не является обратной к cos и является обратной к сужению функции cos на множество ran arccos.
--PAGE_BREAK--g<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1239">$; f<img width=«9» height=«25» src=«ref-1_290254163-191.coolpic» v:shapes="_x0000_i1240"> f<img width=«11» height=«24» src=«ref-1_290294854-194.coolpic» v:shapes="_x0000_i1241"> f<img width=«11» height=«25» src=«ref-1_290262249-201.coolpic» v:shapes="_x0000_i1242">; c4c8f<img width=«9» height=«25» src=«ref-1_290295249-188.coolpic» v:shapes="_x0000_i1243"> g<img width=«9» height=«25» src=«ref-1_290295249-188.coolpic» v:shapes="_x0000_i1244">; "$ØÙÚÞÛвыяснить следуют ли в нем его знаки в алфавитном порядке [ДНДНД].
2.2 Для терма f<img width=«11» height=«25» src=«ref-1_290295625-198.coolpic» v:shapes="_x0000_i1245">(f<img width=«9» height=«25» src=«ref-1_290295823-188.coolpic» v:shapes="_x0000_i1246">(c1), f<img width=«11» height=«24» src=«ref-1_290296011-194.coolpic» v:shapes="_x0000_i1247">,f<img width=«11» height=«25» src=«ref-1_290295625-198.coolpic» v:shapes="_x0000_i1248">(f<img width=«11» height=«24» src=«ref-1_290296011-194.coolpic» v:shapes="_x0000_i1249">, c1,f<img width=«9» height=«25» src=«ref-1_290295823-188.coolpic» v:shapes="_x0000_i1250">(f<img width=«11» height=«24» src=«ref-1_290296011-194.coolpic» v:shapes="_x0000_i1251">))) составить индуктивную последовательность термов[f<img width=«11» height=«24» src=«ref-1_290296011-194.coolpic» v:shapes="_x0000_i1252">, c1, f<img width=«9» height=«25» src=«ref-1_290295823-188.coolpic» v:shapes="_x0000_i1253">(f<img width=«11» height=«24» src=«ref-1_290296011-194.coolpic» v:shapes="_x0000_i1254">), f<img width=«11» height=«25» src=«ref-1_290295625-198.coolpic» v:shapes="_x0000_i1255">(f<img width=«11» height=«24» src=«ref-1_290296011-194.coolpic» v:shapes="_x0000_i1256">, c1, f<img width=«9» height=«25» src=«ref-1_290295823-188.coolpic» v:shapes="_x0000_i1257">(f<img width=«11» height=«24» src=«ref-1_290296011-194.coolpic» v:shapes="_x0000_i1258">) f<img width=«11» height=«25» src=«ref-1_290295625-198.coolpic» v:shapes="_x0000_i1259">(f<img width=«9» height=«25» src=«ref-1_290295823-188.coolpic» v:shapes="_x0000_i1260">(c1), f<img width=«11» height=«24» src=«ref-1_290296011-194.coolpic» v:shapes="_x0000_i1261">, f<img width=«11» height=«25» src=«ref-1_290295625-198.coolpic» v:shapes="_x0000_i1262">(f<img width=«11» height=«24» src=«ref-1_290296011-194.coolpic» v:shapes="_x0000_i1263">, c1, f<img width=«9» height=«25» src=«ref-1_290295823-188.coolpic» v:shapes="_x0000_i1264">(f<img width=«11» height=«24» src=«ref-1_290296011-194.coolpic» v:shapes="_x0000_i1265">)))].
2.3 Пусть p, q, r обозначают нульместные предикаты. Для высказывания pÚØqÙrÞpÞqÞr составить индуктивную последовательность высказываний [p, q, r, Ø(q), (Ø(q)Ù(r), (p)Ú((Ø(q))Ù(r)), (q)Þ(r), (p)Þ((q)Þ(r)), ((p)Ú((Ø(q))Ù(r)))Þ((p)Þ((q)Þ(r)))].
2.4 Для высказывания $c5g<img width=«11» height=«24» src=«ref-1_290299683-198.coolpic» v:shapes="_x0000_i1266">(c1, f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1267">(c2), c1)составить индуктивную последовательность термов и высказываний [c1, c2, f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1268">(c2), g<img width=«11» height=«24» src=«ref-1_290299683-198.coolpic» v:shapes="_x0000_i1269">(c1, f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1270">(c2), c1), $c5 (g<img width=«11» height=«24» src=«ref-1_290299683-198.coolpic» v:shapes="_x0000_i1271">(c1, f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1272">(c2), c1))].
2.5 Для каждого из семи обозначений а: f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1273">(a), g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1274">(a), g<img width=«11» height=«24» src=«ref-1_290262052-197.coolpic» v:shapes="_x0000_i1275">(a, b); Z; $Xg<img width=«9» height=«25» src=«ref-1_290301554-194.coolpic» v:shapes="_x0000_i1276">(X, X, Z); "Xf<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1277">(X, X)выяснить, обозначает ли оно: Терм, Высказывание, Ни-то-ни-другое [TTBHTBH].
2.6 Для каждой из шести скобочных диад в высказывании ((p)Þ(q))Þ((r)Þ(s)) выяснить можно ли ее отбросить без нарушения смысла данного высказывания [HДДДДД].
2.7 В высказывании pÛqÚØrÙØpвосстановить все скобки [(p)Û((q)Ú((Ø(r))Ù(Ø(p))))].
2.8 В высказываниях pÚØqÙrÞpÙrÚØp, pÚØqÙ(rÞpÙr)ÚØpвосстановить все скобки с помощью нумерации логических знаков и скобок в порядке их восстановления.
é((p)Ú((ù(q))Ù(r)))Þ(((p)Ù(r))Ú(ù(p))), (p)Ú(((ù(q))Ù((r)Þ((p)Ù(r)))Ú(ù(p)))ù
ëû
2.9 Пустьp обозначаетвысказывание("c1$c2g<img width=«11» height=«24» src=«ref-1_290263608-197.coolpic» v:shapes="_x0000_i1278">(c2, f<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1279">(c1, c2)))Ùg<img width=«11» height=«24» src=«ref-1_290263608-197.coolpic» v:shapes="_x0000_i1280">(f<img width=«9» height=«25» src=«ref-1_290251686-194.coolpic» v:shapes="_x0000_i1281">, f<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1282"> (c2))Þg<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1283">Úg<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1284">(c1). Индукцией по построению высказывания определить его истинностное значение на универсуме при такой интерпретации функциональных и предикатных знаков.
Ответ:
2.10 Указать истинностные значения высказываний 2<2ÞХ>3, Х<3+4ÛХ<9, 7<Х<9ÞХ=8, Х£3ÚХ>3, "Х(Х>3)Þ5=3, $c1"c2(c2<c1), "c2$c1(c2<c1) [ИПИИИЛИ].
2.11 Для каждого из правил Dp, q, r, pÙqÙr; Dp, pÞp; DpÞp, p; DpÚq, Øp, q; DØØØØp, p; Dp, $XP; D$XP, P; DP, "XP; D"XP; P выяснить является ли оно правилом вывода [ДДНДДДНДД].
2.12 Для каждого из высказываний g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1291">(a), "X g<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1292">(X,C), $X(g<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1293">Þg<img width=«9» height=«24» src=«ref-1_290251301-188.coolpic» v:shapes="_x0000_i1294">), $Xg<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1295">Þg<img width=«9» height=«24» src=«ref-1_290251301-188.coolpic» v:shapes="_x0000_i1296">, g<img width=«9» height=«25» src=«ref-1_290251686-194.coolpic» v:shapes="_x0000_i1297">, Øg<img width=«9» height=«25» src=«ref-1_290251686-194.coolpic» v:shapes="_x0000_i1298">, g<img width=«9» height=«25» src=«ref-1_290251686-194.coolpic» v:shapes="_x0000_i1299">Ûg<img width=«9» height=«25» src=«ref-1_290254163-191.coolpic» v:shapes="_x0000_i1300">, g<img width=«11» height=«25» src=«ref-1_290306292-189.coolpic» v:shapes="_x0000_i1301"> выяснить, является ли оно: предикатом [ДНННДННД], элементарным высказыванием [ДДДНДННД].
2.13 Для высказывания "X(g<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1302">Þg<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1303">(X))Úg<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1304"> записать: все его компоненты [g<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1305">,g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1306">(X), g<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1307">Þg<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1308">(X), "X(g<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1309">Þg<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1310">(X)), "X(g<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1311">Þg<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1312">(X))Úg<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1313"> продолжение
--PAGE_BREAK--], все его элементарные компоненты, все его пропозициональные компоненты [g<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1314">, "X(g<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1315">Þg<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1316">(X))], все его предикатные компоненты [g<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1317">, g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1318">(X)].
2.14 Записать все пропозициональные компоненты высказываний $XPÙ$ZP, $XPÙØ$ZP. [$XP, $ZP – если X, Z различные переменные, $cnP – если X, Z обозначают одну и ту же переменную cn].
3.1 Вычислить:
ИÚØЛÞИÞЛÙИÛИÛЛÚИÚЛÚØИÞЛÙИÙЛÙØИÙØЛÙИÙЛÙØИÙИÙЛ
[И].
3.2 Выяснить, является ли высказывание ØpÙqÙ(rÞs)Û(pÚØqÚrÙØs) тавтологией [Д].
3.3 Пусть p, q, r– различные элементы высказывания. Для каждого из высказываний pÞØrÚqÚp, pÞØr, rÞØpÚq выяснить, является ли оно тавтологией [ДНН] и является ли оно тавтологическим следствием двух других [ДНД].
3.4 Решить истинностное уравнение (pÞq)ÞØqÞp= Л с двумя неизвестными p, q [Л, Л].
3.5 Из p, q, r составить высказывание, истинное только при p=q=r
[(pÛq) Ù(qÛr)].
4.1 Пусть Р обозначает g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1319">(x). Для каждого из высказываний pÞ$XP, $XPÞP, $XPÞØP выяснить является ли оно кванторологически истинным [ДНН]и является ли оно кванторологическим следствием двух других [ДДН].
4.2 Для каждого вхождения переменной в высказывание из задачи 2.9 выяснить, является ли оно свободным или связанным [связанное, связанное, связанное, связанное, свободное, свободное].
4.3 Записать обозначенное через "c3g<img width=«11» height=«25» src=«ref-1_290309741-201.coolpic» v:shapes="_x0000_i1320">(c3, c4) íc4,¦<img width=«9» height=«25» src=«ref-1_290274327-188.coolpic» v:shapes="_x0000_i1321">(c3)ýвысказывание ["c3g<img width=«11» height=«25» src=«ref-1_290309741-201.coolpic» v:shapes="_x0000_i1322">(c3,¦<img width=«9» height=«25» src=«ref-1_290274327-188.coolpic» v:shapes="_x0000_i1323">(c3))].
4.4 Пусть Pобозначает высказывание $c3g<img width=«11» height=«24» src=«ref-1_290256662-200.coolpic» v:shapes="_x0000_i1324">(c6, c3)Ú"c6g<img width=«11» height=«24» src=«ref-1_290256662-200.coolpic» v:shapes="_x0000_i1325">(c6, c3) Úg<img width=«11» height=«24» src=«ref-1_290256662-200.coolpic» v:shapes="_x0000_i1326">(c6, c4).
Указать высказывания с обозначениями Píc3, c6ý, Píc3, ¦<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1327">(c5)ý, Píc3, c3ý. [$c3g<img width=«11» height=«24» src=«ref-1_290256662-200.coolpic» v:shapes="_x0000_i1328">(c6, c3)Ú"c6g<img width=«11» height=«24» src=«ref-1_290256662-200.coolpic» v:shapes="_x0000_i1329">(c6, c6) Ùg<img width=«11» height=«24» src=«ref-1_290256662-200.coolpic» v:shapes="_x0000_i1330">(c6, c6), $c3g<img width=«11» height=«24» src=«ref-1_290256662-200.coolpic» v:shapes="_x0000_i1331">(c3, c3)Ú"c6g<img width=«11» height=«24» src=«ref-1_290256662-200.coolpic» v:shapes="_x0000_i1332">(c6, c3) Ùg<img width=«11» height=«24» src=«ref-1_290256662-200.coolpic» v:shapes="_x0000_i1333">(c3, c3), P, P].
4.5 Для каждого из терминов ¦<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1334">(c1), ¦<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1335">(c2), ¦<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1336">(c8), ¦<img width=«9» height=«24» src=«ref-1_290293320-194.coolpic» v:shapes="_x0000_i1337">(c1, c5, c8), ¦<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1338"> выяснить, является ли он допустимым заменителем для c8в высказывании $c2g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1339">(c8)Ú"c5g<img width=«11» height=«24» src=«ref-1_290262052-197.coolpic» v:shapes="_x0000_i1340">(c8) [ДНДНД].
4.6 Для каждого из высказываний [$c1g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1341">(c1), "c2g<img width=«11» height=«24» src=«ref-1_290282457-191.coolpic» v:shapes="_x0000_i1342">(c2, c3), g<img width=«11» height=«24» src=«ref-1_290292920-203.coolpic» v:shapes="_x0000_i1343">(c1, c2, c3), g<img width=«8» height=«24» src=«ref-1_290256122-180.coolpic» v:shapes="_x0000_i1344">(¦<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1345">) выяснить, является ли оно замкнутым [ДННД]и является ли оно открытым [ННДД].
4.7 Высказывание Ø"C$Z(C£ZÛZ¹ÙØ$C(C>Z))Þ$C"Z(C³Z)привести к позитивной форме
[$C"Z(C>ZÙZ¹Ù"C(C£Z)ÚC£ZÙ(Z=Ú$C(C>Z)))Þ"C$Z(C<Z)].
4.8 В высказывании $c3g<img width=«11» height=«25» src=«ref-1_290314728-202.coolpic» v:shapes="_x0000_i1346">(c3, c5)ÚØ"c5g<img width=«11» height=«25» src=«ref-1_290314728-202.coolpic» v:shapes="_x0000_i1347">(c3, c5) Þg<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1348">Ûg<img width=«11» height=«25» src=«ref-1_290314728-202.coolpic» v:shapes="_x0000_i1349">(¦<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1350">, c5) второе вхождение высказывания g<img width=«11» height=«25» src=«ref-1_290314728-202.coolpic» v:shapes="_x0000_i1351">(c3, c5) заменить высказыванием Øg<img width=«11» height=«25» src=«ref-1_290314728-202.coolpic» v:shapes="_x0000_i1352">(c3, c5) Þg<img width=«11» height=«25» src=«ref-1_290314728-202.coolpic» v:shapes="_x0000_i1353">(c3, c5). [$c3g<img width=«11» height=«25» src=«ref-1_290314728-202.coolpic» v:shapes="_x0000_i1354">(c3, c5)ÚØ"c5(Øg<img width=«11» height=«25» src=«ref-1_290314728-202.coolpic» v:shapes="_x0000_i1355">(c3, c5) Þg<img width=«11» height=«25» src=«ref-1_290314728-202.coolpic» v:shapes="_x0000_i1356">(c3, c5) Þg<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1357">Ûg<img width=«11» height=«25» src=«ref-1_290314728-202.coolpic» v:shapes="_x0000_i1358">(¦<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1359">, c5) и выяснить, равносилен ли результат замены исходному высказыванию [Д].
5.1 Для каждого из высказываний g<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1360">(¦<img width=«9» height=«24» src=«ref-1_290251301-188.coolpic» v:shapes="_x0000_i1361">, ¦<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1362">), $c1g<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1363">(c1, c2), g<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1364">(¦<img width=«9» height=«24» src=«ref-1_290251301-188.coolpic» v:shapes="_x0000_i1365">, ¦<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1366">)Ùg<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1367">(¦<img width=«9» height=«25» src=«ref-1_290251119-182.coolpic» v:shapes="_x0000_i1368">, ¦<img width=«11» height=«24» src=«ref-1_290251489-197.coolpic» v:shapes="_x0000_i1369">)выяснить, является ли оно логически истинным [НДН]и является ли оно логическим следствием остальных [ДДН].
5.2 Указать высказывания p, qт.ч. p½=q, но pÞqне есть логически истинное высказывание [c1= c2, c1= c3].
6.1 Выяснить, является ли последовательность высказываний P, PÞ$CR, $CR, PÞ$CRÞR, $CRÞR, $CRÞ"CR, "CR, R=QÞRÙQ, Q, RÙQдоказательством в теории с аксиомами R,Q[Д].
6.2 Для каждого из высказываний 3<5, 5=5, Х<6Þ$C(C<6), 5<6Þ5<6 выяснить, является ли оно: истинным [ДДДД], логически истинным [НДДД], кванторологически истинным [ННДД], тавтологически истинным [НННД].
6.3 Для каждого из высказываний g<img width=«11» height=«25» src=«ref-1_290267566-197.coolpic» v:shapes="_x0000_i1370"> продолжение
--PAGE_BREAK--
еще рефераты
Еще работы по математике
Реферат по математике
Геометрические фигуры
20 Июня 2015
Реферат по математике
Призма и параллелепипед
3 Сентября 2013
Реферат по математике
Математическое моделирование тепловой работы вращающейся печи
3 Сентября 2013
Реферат по математике
Корреляционно-регрессионный, факторный и компонентный анализы деятельности предприятии
3 Сентября 2013