|
|
Краткая методичка по логике
lip; Пример индуктивной последовательности термов: f[pic] (1 f[pic] ((1, f[pic]) f[pic] ((1, (1, f[pic]((1, f[pic])) (2 f[pic]((1, f[pic], f[pic]((1, f[pic]), (2) f[pic]((2) f[pic](f[pic]((2)) Высказываниями, соотношениями, формулами называются знакосочетания с такими правилами порождения: ( g здесь g нульместный ( g(а1,…,аn) здесь g n-местный, n(0 ( u, (x(u) ( u, (x(u) ( u, ((u) ( u, v, (u)((v) ( u, v, (u)((v) ( u, v, (u)((v) ( u, v, (u)((v) Пример индуктивной последовательности формул (на основе термов из предыдущего примера) g[pic](f[pic], (1) g[pic] ((5(g[pic]) ((1(g[pic](f[pic], (1)) ((((5(g[pic])) g[pic] (g[pic])((((5(g[pic])) g[pic](f[pic]((1, f[pic]), (2, (2) Обозначениями для высказываний: p, q, r, s, t, p0, q0, r0, s0, t0,… С целью удобства обозрения формул некоторые скобочные диады можно опускать, принимая соглашение о правосторонней группировке скобок для нескольких одинаковых логических знаков и соглашение об убывании силы связи в алфавитном порядке логических знаков. Пример: p(q(r означает (p)(((q)((r)), а запись ((xp(q(r понимается как ((((x(p)))(((q)((r)). Следует помнить, что любое высказывание с пропущенными парами скобок не является высказыванием формального языка, оно является лишь обозначением соответствующего высказывания. Нульместные функциональные знаки называются константами. Знакосочетание (x называется квантором всеобщности по х, а (х - квантором существования по х. Начинающееся с предикатного знака высказывание называется предикатом. Высказывание называется элементарным, если оно начинается с квантора или предикатного знака. Высказывание q называется подвысказыванием или компонентой высказывания р, если q есть часть р. Элементарная компонента q высказывания р называется его пропозициональной компонентой, если q имеет хотя бы одно такое вхождение в р, которое не является вхождением в какую-нибудь другую элементарную компоненту высказывания р. Например, высказывание ((5(g[pic](g[pic])(g[pic] имеет пять компонент: ((5(g[pic](g[pic]), g[pic], g[pic], g[pic](g[pic], ((5(g[pic](g[pic])(g[pic], из которых только первые три являются элементарными, первые две - пропозициональными, только g[pic] и g[pic] - предикатными. Интерпретация формального языка. Переменная выражает, нотирует, обозначает произвольный объект из некоторого не пустого множества, которое называется денотарием или универсумом данной интерпретации и элементы которого тем самым являются денотатами или значениями переменной. 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[pic](x) - х есть кулик g[pic](x) - х есть болото g[pic](x, у) - х хвалит у g[pic](x, у) - у свое для х ((1((((g[pic]((1))((g[pic]((2)))((g[pic]((1, (2)))((g[pic]((1, (2))) Пример. Сумма квадратов двух положительных чисел меньше квадрата их суммы. Универсум - множество положительных чисел. f[pic](x) - квадрат числа x f[pic](x, y) - сумма чисел x, y g[pic](x, y) – x меньше y g[pic](f[pic](f[pic]((1), f[pic]((2)), f[pic](f[pic]((1, (2))) Можно записать по-другому: универсум - множество действительных чисел f[pic] - число 0 ((g[pic](f[pic], (1))((g[pic](f[pic], (2)))((g[pic](f[pic](f[pic]((1), f[pic]((2)), f[pic](f[pic]((1, (2))) Пример. Только я один знаю об этом. Универсум – множество людей f[pic] - я g[pic](x) - x знает об этом g[pic](x, y) - x идентичен y (g[pic](f[pic]))((((1((((g[pic]((1, f[pic])))((((g[pic]((1)))) Никто не знает об этом: ((1(((g[pic]((1))) Все знают об этом: ((1(g[pic]((1)) Кто-нибудь знает об этом: ((1(g[pic]((1)) Пример. Здесь холодно, но не сыро: (g[pic])((((g[pic])) Пример. Ни p ни q: (p и (q Пример. Если p то q иначе r: (p(q)(((p(r) Пример. p либо q: p((q((p(q Пример. p поэтому q: p((p(q) Пример. Чай без сахара не сладкий и не вкусный. g[pic] - чай содержит сахар g[pic] - чай сладкий g[pic] - чай вкусный (((g[pic]))((((( g[pic]))(((( g[pic]))) Возможен другой перевод: ((((g[pic]))(((( g[pic])))((((( g[pic]))((((( g[pic]))) Пример. Его отец слесарь, а все братья токари. Универсум – множество мужчин f[pic] - он f[pic](x) - отец для x g[pic](x) - x есть слесарь g[pic](x) - x есть токарь g[pic](x, y) - x идентичен y (g[pic](f[pic](f[pic])))((((1(((((g[pic]((1, f[pic])))((g[pic](f[pic]((1), ( f[pic](f[pic]))))((g[pic]((1)))) Тема 3. Пропозициональная логика или логика элементарных высказываний изучает свойства логических операций (, (, (, (, (, которые по смыслу их введения являются операциями над истинностными значениями: |p |q |(p |p(q |p(q |p(q |p(q | |Л |Л |И |Л |Л |И |И | |Л |И |И |Л |И |И |Л | |И |Л |Л |Л |И |Л |Л | |И |И |Л |И |И |И |И | Если высказывания р, q различны и элементарны, то эта таблица называется истинностной таблицей высказываний (p, q,) (p, p(q, p(q, p(q, p(q. В общем случае при составлении истинностной таблицы какого-либо перечня высказываний надо поместить на ее вход все различные пропозициональные компоненты этих высказываний, сделать полный перебор истинностных значений во входных столбцах и записать соответствующие истинностные значения в результирующих столбцах. Пример. В комнате без окон темно и неуютно. Универсум - множество комнат g[pic]((1) - (1 имеет окно p - комната имеет окно g[pic]((1) - в (1 темно q - в комнате темно g[pic]((1) – в (1 уютно r - в комнате уютно (((g[pic]((1)))(((g[pic]((1))((((g[pic]((1)))) (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, p q, p + q. Например, арифметической записью высказывания (r(p(q(r) будет [pic]. При арифметической записи высказываний с ними можно обращаться так, как будто они обозначают числа 0, 1, а. Логический плюс отличается от арифметического только
| | скачать работу |
Краткая методичка по логике |
|
|
|
Погода в Алматы |
на 10 дней |
другой город |
|