Краткая методичка по логике

Постраничный перечень понятий и теорем. Логика. Язык. Высказывание. Истинное высказывание. Ложное высказывание. Истина. Ложь. Обозначение для истины. Обозначение для лжи. Истинностное значение высказывания. Равносильные высказывания. Синонимы для истинного высказывания. Доказательство.

Правило вывода. Обозначение для конструктивного правила. Компоненты конструктивного правила. Посылки конструктивного правила. Заключение конструктивного правила. Индуктивная последовательность объектов. Правила порождения индуктивной последовательности. Формальный язык. Логические знаки. Вспомогательные знаки. n-местные функциональные знаки. n-местные

предикатные знаки. Переменные. Алфавитный порядок знаков. Выражение. Синонимы для выражения. Обозначения для нульместных функциональных знаков. Обозначения для функциональных знаков. Обозначения для предикатных знаков. Обозначения для выражений. Обозначения для переменных. Обозначение для соединения выражений. Терм. Правила порождения термов.

Обозначения для термов. Индуктивная последовательность термов. Высказывание. Синонимы для высказывания. Правила порождения высказываний. Индуктивная последовательность высказываний. Обозначения для высказываний. Соглашения об упразднении скобок. Константа. Квантор всеобщности. Квантор существования. Предикат. Элементарное высказывание.

Компонента высказывания. Синоним для компоненты высказывания. Пропозициональная компонента высказывания. Интерпретация формального языка. Универсум интерпретации. Синоним для универсума. Значение переменной. Значение функционального знака. Значение предикатного знака. Значение терма. Значение высказывания. Денотаты термов и высказываний.

Индуктивное определение значения терма. Индуктивное определение значения высказывания. Обобщение высказывания по данной переменной. Синонимы для выражения обобщения. Подтверждение высказывания по данной переменной. Синонимы для выражения подтверждения. Отрицание высказывания. Синонимы для выражения отрицания. Конъюнкция высказываний. Конъюнкты. Синонимы для выражения конъюнкции.

Дизъюнкция высказываний. Дизъюнкты. Синонимы для выражения дизъюнкции. Импликация высказываний. Посылка импликации. Заключение импликации. Синонимы для выражения импликации. Эквиваленция высказываний. Левая и правая части эквиваленции. Синонимы для выражения эквиваленции. Замечание о языковой смеси. Замечание об использовании знака равенства для высказываний.

Пропозициональная логика. Синоним для пропозициональной логики. Логические пропозициональные операции. Истинностная таблица высказываний. Входные и результирующие столбцы истинностной таблицы. Тавтология и ее синоним. Тавтологическое следствие. Теорема об отрицании отрицания. Теорема об отрицании конъюнкции.

Теорема об отрицании дизъюнкции. Теорема об исключении импликации. Теорема об исключении эквиваленции. Теорема об устранении альтернативы. Теорема о коммутативности Теорема о равносильности. Теорема о тавтологическом следствии. Арифметическая запись высказываний. 12 равенств. Правило отделения. Теорема о выводе в пропозициональной логике.

Теорема о самодостаточной выразительности пропозициональной логики. Кванторная логика. Синоним для кванторной логики. Кванторные операции. Кванторологически истинное высказывание. Кванторологическое следствие. Связанное вхождение переменной. Свободное вхождение переменной. Результат подстановки в высказывание терма вместо переменной и его

обозначение. Допустимый заменитель. Замкнутое высказывание. Открытое высказывание. Теорема о всезначности переменной. Теорема об отрицании обобщения и подтверждения. Теорема о взаимоисключении кванторов. Теорема о перестановочности кванторов. Типовые кванторы. Теорема о равносильной замене. Позитивное высказывание.

Позитивная форма высказывания. Теорема о позитивной форме. Теорема о выводе в логике предикатов. Правило тавтологии. Правило отделения. Правило обобщения. Правило подтверждения. Правило общевнесения. Правило сущевнесения. Эгалитарная логика. Синоним для эгалитарной логики. Эгалитарная интерпретация.

Логическое следствие. Обозначение для логического следствия. Логически истинное высказывание. Обозначение для логически истинного высказывания. Правило тождества. Правило равенства. Правило неотличимости. Теорема об эгалитарной замене. Теорема о транзитивности логического следствия. Теорема о расширении списка гипотез. Теорема о конъюнктивизации гипотез.

Теорема дедукции. Теорема о выводе в эгалитарной логике. Теорема о сравнительной силе выводов. Алгоритм. Теорема о неразрешимости проблемы логического следствия. Теорема о неразрешимости проблемы логической истинности. Замечание о слове ЛОГИКА. Формальные теории. Аксиомы формальной теории. Теоремы формальной теории. Доказательный текст. Девять основных правил вывода.

Способы компактизации доказательных текстов. Операционная форма записи для двухместных функциональных и предикатных знаков. Соглашение об упразднении скобок. Соглашение о сравнительной силе связи логических и нелогических знаков. Специальные начертания знаков. Знаковые фигуры. Определяющая аксиома для нового предикатного знака. Определяющая аксиома для нового функционального знака.

Теорема об определениях. Правило отделения конъюнкта. Правило присоединения дизъюнкта. Теорема о методе от противного. Формальная арифметика. Определяющие аксиомы для 2 3 4 5 . Множество. Элемент множества. ХА. ХА. Подмножество. АВ. AB. ар. Пустое множество и его обозначение. Х1

Хn Объединение двух множеств и его обозначение. Пересечение двух множеств и его обозначение. Дополнение множества В относительно множества А, его обозначение и синоним. Обозначение для множества натуральных, целых и действительных чисел. Упорядоченная n-ка, ее обозначение и синонимы. k-ая компонента упорядоченного набора, ее обозначение и синоним. Декартово произведение множеств и его обозначение.

К-ая проекция n-мерного множества и ее обозначение Аn. Функция. Область определения функции, ее синоним и обозначение. Область значений функции, ее синоним и обозначение. Значение функции F в х и его обозначение. Образ множества относительно функции и его обозначение. Отображение множества в множество. Отображение множества на множество.

F А В. Сужение функции. Расширение функции. Обратная функция. Симметричность понятия обратной функции. n-аргументная функция. Обозначение F Х1 Хn. Однозначная функция. Многозначная функция. Взаимнооднозначная функция и ее синоним. Последовательность. n-ый член последовательности. Бесконечное множество. Конечное множество. Тема 1.

Предмет и основные понятия логики. Логика - наука о мышлении, наука о языковом выражении мыслей. Язык - знаковая система, предназначенная для фиксации, передачи и переработки информации. Высказывание - языковое выражение, о котором представляется естественным спросить, истинно оно или ложно. Высказывание является истинным, если его содержание соответствует действительности в противном случае высказывание является ложным. Т. о. любое высказывание является либо истинным либо ложным и тем

самым служит обозначением либо истины либо лжи, которые мы можем рассматривать как два различных умозрительных объекта, обозначаемых обычно буквами И, Л и называемых истинностными значениями высказываний И есть истинностное значение истинного высказывания, Л есть истинностное значение ложного высказывания. Высказывания с одинаковыми истинностными значениями называются равносильными.

Про истинное высказывание говорят, что оно справедливо, верно, имеет место. Доказательством называется конечная последовательность высказываний, в которой каждое высказывание получается из некоторых предыдущих по какому-либо правилу вывода. Правила вывода - это конструктивные операции над высказываниями, сохраняющие свойство истинности, т. е. такие операции, в результате которых из истинных высказываний получаются истинные высказывания.

Конструктивное правило преобразования объектов u1 un-1 в объект un будем записывать в виде u1 un. При этом u1 un называются компонентами, последняя из которых называется заключением, а остальные посылками. Последовательность объектов называется индуктивной относительно некоторого набора правил, если каждый ее член получается из предыдущих по какому-либо из этих правил, которые называются правилами порождения данной последовательности. Например, возрастающая последовательность всех нечетных чисел и последовательность 1, 3, 1, 5, 7, 3

являются индуктивными относительно правил 1 и х, х2, а последовательность 1, 3, 7 не является индуктивной относительно этого набора правил. Тема 2. Унификация языка. Для четкого выражения мыслей ученые придумали формальный язык, в котором все осмысленные выражения строятся по определенным правилам из следующих знаков, символов Логические знаки вспомогательные знаки , нульместные функциональные знаки f одноместные функциональные

знаки нульместные предикатные знаки g g g g одноместные предикатные знаки g g g g переменные 0 1 2 3 Порядок в котором здесь перечислены знаки, называется алфавитным порядком. Выражением, знакосочетанием, символосочетанием в этом формальном языке называется несколько записанных друг за другом в направлении слева на право знаков. c, c0, c1, обозначают нульместные функциональные знаки. f, f0, f1, обозначают функциональные знаки. g, g0, g1, обозначают предикатные знаки. u, v, w,

u0, v0, w0, u1, v1, w1, обозначают выражения. х, y, z, х0, y0, z0, х1, y1, z1, обозначают переменные. uv обозначает результат написания выражения v после выражения u. Термами называются знакосочетания с такими порождающими правилами х c u1 un, f u1, ,un. f n-местный, n0. Обозначения для термов a, b, a0, b0, a1, b1, Пример индуктивной последовательности термов 1 1, 1, 1, 1, 2 1 1 2 2 2 Высказываниями, соотношениями, формулами называются знакосочетания с такими правилами порождения g здесь

g нульместный gа1 аn здесь g n-местный, n0 u, xu u, xu u, u u, v, uv u, v, uv u, v, uv u, v, uv Пример индуктивной последовательности формул на основе термов из предыдущего примера g , 1 g 5g 1g , 1 5g g g 5g g 1 2, 2 Обозначениями для высказываний p, q, r, s, t, p0, q0, r0, s0, t0, С целью удобства обозрения формул некоторые скобочные диады можно опускать, принимая соглашение о правосторонней группировке скобок для нескольких одинаковых логических знаков и соглашение об убывании силы связи в

алфавитном порядке логических знаков. Пример pqr означает pqr, а запись xpqr понимается как xpqr. Следует помнить, что любое высказывание с пропущенными парами скобок не является высказыванием формального языка, оно является лишь обозначением соответствующего высказывания. Нульместные функциональные знаки называются константами. Знакосочетание x называется квантором всеобщности по х, а х - квантором существования по х.

Начинающееся с предикатного знака высказывание называется предикатом. Высказывание называется элементарным, если оно начинается с квантора или предикатного знака. Высказывание q называется подвысказыванием или компонентой высказывания р, если q есть часть р. Элементарная компонента q высказывания р называется его пропозициональной компонентой, если q имеет хотя бы одно такое вхождение в р, которое не является вхождением в какую-нибудь другую элементарную

компоненту высказывания р. Например, высказывание 5g g g имеет пять компонент 5g g , g , g , g g , 5g g g , из которых только первые три являются элементарными, первые две - пропозициональными, только g и g - предикатными. Интерпретация формального языка. Переменная выражает, нотирует, обозначает произвольный объект из некоторого не пустого множества, которое называется денотарием или универсумом данной интерпретации и элементы которого тем самым являются денотатами

или значениями переменной. n-местный функциональный знак обозначает n-местную операцию на универсуме. n-местный предикатный знак обозначает изначальную взаимосвязь между любыми n объектами универсума. Термы обозначают объекты универсума, а высказывания обозначают истину или ложь, т. е. денотатами термов являются объекты универсума, а денотатами высказываний являются истина и ложь. Задать интерпретацию формального языка значит задать ее универсум и связанные с ним значения всех нужных

нам функциональных и предикатных знаков тогда значения всех нужных термов и формул при любых значениях фигурирующих в них переменных определяются индукцией по их построению с учетом такой интерпретации логических знаков xp - обобщение высказывания р по х является истинным тттк р является истинным для всех значений переменной х синонимы р для каждого х, р для любого х, р для всех x, р для произвольного х. xp - подтверждение высказывания р по х является истинным тттк р является истинным хотя бы для одного значения переменной

х синонимы существует х т.ч. р, р для некоторого х. p - отрицание высказывания р является истинным тттк р является ложным синонимы не р, неверно что р. pq - конъюнкция высказываний р, q является истинной тттк оба ее конъюнкта р, q являются истинными синонимы р и q, и р и q. pq - дизъюнкция высказываний p, q является ложной тттк оба ее дизъюнкта р, q являются ложными синонимы р или q, или р или q. pq - импликация высказываний p, q является ложной тттк посылка р является истинной, а заключение q является

ложным синонимы р только если q, если р то q, q если р, р тогда q, q когда р, для того чтобы р необходимо чтобы q, для того чтобы q достаточно чтобы р, р следовательно q, из того что р следует что q. pq - эквиваленция высказываний р, q является истинной тттк ее части р, q обе являются истинными или обе являются ложными синонимы р если и только если q, р тогда и только тогда когда q, для того чтобы р необходимо и достаточно чтобы q, р эквивалентно q. Замечание. Иногда высказывания записывают на смеси формального, обычного

и математического языка. Все такие записи будем рассматривать как обозначения соответствующих высказываний формального языка. Замечание. Введение обозначений для высказываний порождает двусмысленность в использовании знака равенства, поскольку сами высказывания являются некоторыми обозначениями, а именно обозначениями истины или лжи. При наличии иерархии обозначений такую двусмысленность обычно снимают соглашением о том, что равенство понимается как равенство между исходными объектами.

Т. о. равенство pq означает, что р и q имеют одинаковые истинностные значения т. е. являются равносильными. Пример. Каждый кулик свое болото хвалит. Универсум - множество куликов и болот g x - х есть кулик g x - х есть болото g x, у - х хвалит у g x, у - у свое для х 1g 1g 2g 1, 2g 1, 2 Пример. Сумма квадратов двух положительных чисел меньше квадрата их суммы. Универсум - множество положительных чисел. x - квадрат числа x x, y - сумма чисел x, y g x, y x меньше

y g 1, 2, 1, 2 Можно записать по-другому универсум - множество действительных чисел - число 0 g , 1g , 2g 1, 2, 1, 2 Пример. Только я один знаю об этом. Универсум множество людей - я g x - x знает об этом g x, y - x идентичен y g 1g 1, g 1 Никто не знает об этом 1g 1 Все знают об этом 1g 1 Кто-нибудь знает об этом 1g 1 Пример. Здесь холодно, но не сыро g g

Пример. Ни p ни q p и q Пример. Если p то q иначе r pqpr Пример. p либо q pqpq Пример. p поэтому q ppq Пример. Чай без сахара не сладкий и не вкусный. g - чай содержит сахар g - чай сладкий g - чай вкусный g g g Возможен другой перевод g g g g Пример. Его отец слесарь, а все братья токари. Универсум множество мужчин - он x - отец для x g x - x есть слесарь g x - x есть токарь g x, y - x

идентичен y g 1g 1, g 1, g 1 Тема 3. Пропозициональная логика или логика элементарных высказываний изучает свойства логических операций которые по смыслу их введения являются операциями над истинностными значениями pqppqpqpqpqЛЛИЛЛИИЛИИЛИИЛИЛЛЛИЛЛИИЛИИИИ Если высказывания р, q различны и элементарны, то эта таблица называется истинностной таблицей высказываний p, q, p, pq, pq, pq, pq. В общем случае при составлении истинностной таблицы какого-либо перечня высказываний надо поместить

на ее вход все различные пропозициональные компоненты этих высказываний, сделать полный перебор истинностных значений во входных столбцах и записать соответствующие истинностные значения в результирующих столбцах. Пример. В комнате без окон темно и неуютно. Универсум - множество комнат g 1 - 1 имеет окно p - комната имеет окно g 1 - в 1 темно q - в комнате темно g 1 в 1 уютно r - в комнате уютно g 1g 1g 1 pqr p q r pqrprqrpqrЛЛЛИИЛЛЛЛИИЛЛЛЛИЛИИИИЛИИИЛЛЛИЛ

ЛЛИЛИИЛИЛЛЛИИИЛЛИЛЛЛИ Тавтология или тавтологически истинное высказывание - это высказывание со сплошными И в его столбце его истинностной таблицы. Высказывание q называется тавтологическим следствием из высказываний p1 pn, если в истинностной таблице высказываний p1 pn q столбец q содержит И в любой строке, которая содержит И во всех столбцах p1 pn. Например, построенная выше таблица показывает, что pqr - есть тавтологическое следствие из p, qr r,

q являются тавтологическими следствиями из qr r есть тавтологическое следствие из p, p. Теорема об отрицании отрицания p p Теорема об отрицании конъюнкции pq pq Теорема об отрицании дизъюнкции pq pq Теорема об исключении импликации pq pq Теорема об исключении эквиваленции pq pqpq Теорема об устранении альтернативы ppq pq, ppq pq Теорема о коммутативности конъюнкции pq qp Теорема о коммутативности дизъюнкции pq qp

Теорема об ассоциативности конъюнкции pqr pqr Теорема об ассоциативности дизъюнкции pqr pqr Теорема о дистрибутивности конъюнкции pqr pqpr Теорема о дистрибутивности дизъюнкции pqr pqpr Теорема о равносильности р q тогда и только тогда когда pq И Теорема о тавтологическом следствии q является тавтологическим следствием из р1 pn тттк р1р q является тавтологией. Эти три теоремы легко доказываются с помощью истинностных таблиц.

Арифметический способ записи высказываний исключаются знаки , и вместо Л, И, p, pq, pq употребляются соответственно 0, 1, p, p q, p q. Например, арифметической записью высказывания rpqr будет . При арифметической записи высказываний с ними можно обращаться так, как будто они обозначают числа 0, 1, а. Логический плюс отличается от арифметического только тем, что 1 1 1.

При этом полезно помнить следующие равенства p q p q p q p q p q p p p p p p pp 0 p p q p q p p 1 p p q p q 1 p 1 Равенства в левой колонке представляют собой другую запись уже доказанных выше теорем, а равенства в правой колонке устанавливаются непосредственной проверкой с учетом равенств 0 1, 1 0. Пример. Доказательство тавтологичности высказываний pqp p qp p q p p p q 1 q 1 pqpq p q p q p q 1 pqqpq q q p qp q q p p q q q 1 Пример. Выразительная достаточность пар pq pq pq pq pq pq pq pq pq pq pqpq

pq pqpq pq pq qp Доказательство последнего равенства pq p q pq pqqp p qq p pq p p q q q p pq 0 0 q p p q pq Пример. Упрощение высказываний. pqrqppqq p q rq p qp q p qp q r q p q1 p r p q pq pqp p pq p pq 1 p 1 p Пример. Доказательство равносильности высказываний. pqr p qr p qr p qr pqpr pqpr p qp r p pr q p qr p1 r q qr p qr Т. о. т. е. являются равносильными два полученных ранее перевода высказывания чай . Правилом отделения называется правило p, pq, q

Теорема о выводе в пропозициональной логике высказывание p0 является тавтологическим следствием из p1 pn тттк его можно получить из p1 pn с помощью правила отделения и нижеследующих пятнадцати беспосылочных правил pqp ppqpq pqqrpr pqp pqq pqprpqr ppq qpq prqrpqr pqpq pqqp pqqppq pqqp pp pp Другими словами, какое либо высказывание p0 является тавтологическим следствием из p1 pn тттк p0 можно сделать членом последовательности высказываний, которая является индуктивной относительно этих шестнадцати

правил и правил p1 pn. Теорема не исключает случай n 0. Теорема о самодостаточной выразительности пропозициональной логики для любой истинностной таблицы с n входными столбцами p1 pn и любого распределения истинностных значений в ее результирующем столбце можно составить соответствующее этому столбцу высказывание справа от всех строк с истиной в результирующем столбце записываем конъюнкцию p1 pn, затем над некоторыми pk ставим черту отрицания так, чтобы все эти

конъюнкции для всех строк были истинными, затем составляем дизъюнкцию из получившихся конъюнкций. Например p q r 0 0 0 0 0 0 1 0 0 1 0 1 p qr 0 1 1 0 1 0 0 1 pqr 1 0 1 0 1 1 0 1 p qr 1 1 1 0 p qr pqr p qr p qr prq q p qr pr rp q p rp q rpq Замечание. Если в результирующем столбце содержится только Л, то в качестве искомого высказывания можно взять p1p1. Пример применения теоремы о самодостаточной выразительности.

Турист приехал в страну, где каждый житель всегда лжет либо всегда говорит правду. Какой вопрос должен задать турист местному жителю, чтобы узнать, какая из двух дорог ведет в столицу. p житель говорит правду q эта дорога ведет в столицу r высказывание для вопроса pqrНужный ответ001Нетpq010Да100Нет111Даp q r pq p q pq т. e. турист должен спросить верно ли, что Вы скажите правду если и только если эта дорога ведет в столицу.

Пример проверки рассуждения Профсоюзы поддержат президента на предстоящих выборах p только если он подпишет законопроект о повышении заработной платы q. Фермеры окажут президенту поддержку r только если он наложит вето на законопроект s. Очевидно, что он не подпишет законопроекта или не наложит на него вето. Следовательно президент потеряет голоса профсоюзников или голоса фермеров . pqrsps pr 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. Значит, если повысят пошлины, то государственные расходы на общественные нужды не сократятся . qpprqr q r qp pr q r qp 1 rp 1 q r - не тавтология, т.е. нельзя сказать, что рассуждение правильно.

Пример проверки рассуждения Если подозреваемый совершил эту кражу p, то она была тщательно подготовлена q или он имел соучастника r. Если бы кража была подготовлена тщательно, то, если бы был соучастник, украдено было бы гораздо больше. Значит, подозреваемый невиновен . pqrqrpp p pqr p q r p q r qr p не тавтология. Пример проверки рассуждения Если наступит мир p, то возникнет депрессия q, разве что страна проведет программу перевооружения r или осуществит грандиозную социальную программу s.

Но договориться о целях такой грандиозной программы невозможно. Следовательно если наступит мир и не будет депрессии, то будет осуществляться программа перевооружения . pqqrsspqr т.е. рассуждение правильное. Пример сокращения текста Члены финансового комитета должны избираться среди членов дирекции. Нельзя быть одновременно членом дирекции и членом библиотечного совета, не будучи членом финансового

комитета. Член библиотечного совета не может быть членом финансового комитета . p он является членом финансового комитета q он является членом дирекции r он является членом библиотечного фонда pqpqrrp p qp q rr p p q p q p qpq r p qp qq r p qq r pqqr Таким образом, можно отбросить подчеркнутую часть текста. Пример анализа рассуждения это преступление совершено в Кустанае q. Петров во время совершения преступления находился в

Ростове r. Следовательно Петров не совершал этого преступления p . qrp не тавтология Преступление совершено в Кустанае. Поэтому если Петров совершил это преступление, то он во время совершения преступления находился в Кустанае s. Но Петрова в это время в Кустанае не было. Значит, Петров не совершал этого преступления . qqpsp 1 тавтология т.е. рассуждение правильное. Рассуждение останется правильным, если из него выбросить первое предложение и ссылку на

него во втором предложении pssp p p p s p 1 s 1 Задача. Выяснить, кто из четверых виновен на основе информации Петров виновен, только если виновен Кулагин. Неверно, что виновность Родионова влечет виновность Сидорова и что Кулагин виновен, а Сидоров нет . p, q, r, s виновен Петров, Кулагин, Родионов,

Сидоров. pqrsqs p q p q rsq s p qr sq pq rs т.е. Родионов виновен, остальные не виновны. Задача Кислера. Обвиняемые в подделке налоговых документов Браун, Джонс и Смит дают под присягой такие показания. Браун Джонс виновен, а Смит не виновен. Джонс Если Браун виновен, то виновен и Смит. Смит Я не виновен, но хотя бы один из них двоих виновен.

Вопрос 1 Совместимы ли данные показания Вопрос 2 Какое показание следует из другого Вопрос 3 Если все виновны, то кто лжесвидетельствует Вопрос 4 Если все сказали правду, то кто виновен Вопрос 5 Если невинный говорит правду, а виновный лжет, то кто виновен, а кто невиновен Б виновен Браун. Д виновен Джонс. С виновен Смит. БДСБДСБДДСБССБДЛЛЛИИИЛЛИЛЛЛИИИЛЛЛИЛЛИЛИЛ

ИЛИИИЛЛИЛИЛИЛЛЛИИИЛЛИИЛИЛИЛИЛИЛИИЛЛЛИИИЛ ИИИИЛЛЛИЛИЛПоказанияБраунаДжонсаСмита 1. Да, только за счет третьей строки. 2. Из первого третье. 3. Браун и Смит. 4. Джонс виновен, остальные невиновны. 5. Джонс невиновен, остальные виновны. Тема 4. Кванторная логика. или логика предикатов является расширением пропозициональной логики путем изучения операций Из определения этих операций следует, что значения

высказываний хp, хp, понимаются соответственно как конъюнкция p1p2p3 и дизъюнкция p1p2p3 значений высказывания p для всевозможных значений переменной х. Высказывание p называется кванторологически истинным при любой интерпретации. Из определений следует, что тавттологически истинное высказывание является кванторологически истинным. Обратное вообще говоря не верно высказывание хpхp является кванторологически истинным, но не является тавтологически истинным. Истинностная таблица. хpхpхpхpЛЛИЛИИИЛЛИИИ

Истинностная схема. p1, p2, p3хp p1p2p3хp p1p2p3хpхpЛИЛЛЛЛИ Высказывание q называется кванторологическим следствием из высказываний р1 pn, если p является истинным в любой интерпретации, в которой истинными являются p1 pn. Вхождением переменной в высказывание p называется связанным, если оно является вхождением в некоторое подвысказывание вида хq или вида хq в противном случае это вхождение называется свободным.

Например, первое и второе вхождения 1 в высказывание g 1g 1, 2 1g 1 являются свободными, а третье и четвертое связанными. Через рх, а обозначается результат подстановки терма, а вместо всех свободных вхождений переменной х в высказывание р, причем, если при такой подстановке все вхождения переменных из а остаются свободными, то терм а называется допустимым заменителем для х в р. Например, терм 5 является допустимым заменителем для 6 в высказывании g 5, 6, и не является допустимым

заменителем для 6 в высказывании 5 g 5, 6. Высказывание р называется замкнутым открытым, если оно не имеет свободных связанных вхождений переменных. Теорема о всезначности переменной р И тттк хр И Теорема об отрицании обобщения и подтверждения хр равносильно хр хр равносильно хр Теорема о взаимоисключении кванторов хр равносильно хр хр равносильно хр Теорема о перестановочности кванторов хур равносильно ухр хур равносильно ухр

Типовые кванторы. Запись qхр обозначает высказывание хqр, а запись qхр обозначает высказывание хqр. Теорема о равносильной замене пусть q есть результат замены в высказывании р какого-либо вхождения подвысказывания r1 на высказывание r2 тогда если r1 и r2 равносильны, то р и q тоже равносильны. Позитивным высказыванием называется такое, которое не имеет вхождений знака . Позитивной формой высказывания р называется любое равносильное ему позитивное высказывание .

Теорема о позитивной форме если отрицания предикатных компонент высказывания р имеют равносильные себе предикаты, то р равносильно некоторому позитивному высказыванию q высказывание q можно построить с помощью теоремы о равносильной замене, теорем об исключении операций , и теорем об отрицании для операций Пример построения позитивной формы отрицания высказывания для каждого положительного числа е существует положительное число т.ч. для каждого числа х из х следует, что х е или х1 . ехх х ех1 eхх х eх1 eхх

х eх1 eхх х eх1 eхх хeх 1 существует положительное число е т.ч. для каждого положительного числа существует число х т.ч. х и хe и х 1 . Теорема о выводе в логике предикатов нижеследующие шесть правил преобразования высказываний образуют достаточный набор правил вывода в логике предикатов т.е. р0 является кванторологическим следствием из p1 pn тттк р0 может быть получено из р1 рn с помощью этих шести правил t правило тавтологии s, s r, r правило отделения хрpx, a правило обобщения px, a xp правило подтверждения qr, q хr правило

общевнесения rq, xrq правило сущевнесения где t есть тавтология, q не имеет свободных вхождений x, терм а является допустимым заменителем для х в р. Теорема не исключает случай n 0. Тема 5. Эгалитарная логика или логика предикатов с равенством, т.е. с двухместным предикатным символом g20, который интерпретируется как знак равенства. Т.о. в эгалитарной логике предикат g20a, b выражает то, что мы привыкли выражать в виде a b и понимать как констатацию того, что объекты с обозначениями

a, b являются одинаковыми, равными, неотличимыми, идентичными. Эгалитарной интерпретацией формального языка называется такая, в которой g интерпретируется как знак равенства. Запись p1 pnq1 qm означает, что каждое из высказываний q1 qm является логическим следствием из высказываний p1 pn т.е. что оно является истинным в любой эгалитарной интерпретации, в которой оказываются истинными p1 pn. Высказывание p называется логически истинным, если p т.е. если p является истинным

в любой эгалитарной интерпретации. Правилами тождества, равенства, неотличимости называются следующие три правила соответственно g x, x g x1, y1 g xn, yng fx1 xn, fy1 yn g2 x1, y1 g xn, yng fx1 xny1 yn Теорема об эгалитарной замене пусть q есть результат замены в p некоторых вхождений терма a термом b тогда если выражение g20a, b является истинным, то p равносильно q. Теорема о транзитивности логического следствия если p1 pnq1 qm и q1 qm r1 re, то p1 pn r1 re.

Теорема о расширении списка гипотез если p1 pn q, то p0 pn q. Теорема дедукции если высказывания p1 pn являются замкнутыми, то p1 pn p тогда и только тогда когда p1 pnp. Теорема о конъюнктивизации гипотез p1 pn p тттк p1pn 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. Формальные теории предназначены для четкого изложения и развития тех или иных отраслей человеческих

знаний. Задать формальную теорию значит задать ее функциональные и предикатные символы, а также аксиомы, т. е. некоторые из высказываний, которые являются истинными в данной отрасли знаний. Развивать формальную теорию значит пополнять запас ее теорем, т. е. таких высказываний, которые являются логическими следствиями аксиом. Изложение любой формальной теории в принципе можно оформить в виде книжек с доказательными текстами 1a1 индуктивная последовательность термовkak k1r1 индуктивная последовательность

формул на основе a1 akkеre kе1s1 аксиомы s1 sm есть среди r1 rekеmsm kеm1t1 индуктивная последовательность теорем t1 tn есть среди r1 rekеmntn Здесь штрих-пунктирная линия обозначает пояснение о том, с помощью какого правила порождения получено соответствующее знакосочетание. Для удобства таких пояснений знакосочетания a1 tn нумеруются последовательно от 1 до kеmn. Вспомним, что правила порождения теорем являются правилами вывода, что конечная индуктивная последовательность

теорем является доказательством и что следующие девять правил, называемых основными, образуют достаточный набор правил вывода из аксиом правила тавтологии, отделения, обобщения, подтверждения, общевнесения, сущевнесения, тождества, равенства, неотличимости. Такая форма изложения делает доказательство легко проверяемым, но практически не применяется из-за ее громоздкости. Способы более компактного изложения формальной теории.

1. Последовательность a1 re не записывается, потому что при достаточном навыке термы и формулы распознаются без построения их индуктивных последовательностей. 2. В последовательность t1 tn включаются теоремы из других доказательных текстов. 3. Для двухместного функционального или предикатного знака v используется операционная форма записи вместо va,b пишут avb. 4. При операционной форме записи принимается соглашение об упразднении некоторых

пар скобок в соответствии с соглашением об убывании силы связи в последовательности одноместный функциональный знак, двухместный функциональный знак, одноместный предикатный знак, двухместный предикатный знак, логический знак. 5. Используются специальные начертания для функциональных и предикатных знаков. Например в теории чисел 0, 1, 2, 3 - нульместные функциональные знаки , sin, cos - одноместные функциональные знаки , двухместные функциональные знаки - двухместные предикатные знаки.

6. Используются знаковые фигуры. Например, х3х обозначает сумму 345. 7. Вводится определяющая аксиома gх1 х11 р для нового n-местного предикатного символа g. Здесь переменные х1 хn попарно различны, а высказывание р не имеет свободных вхождений переменных, отличных от х1 хn. 8. Вводится определяющая аксиома рх, х1 хn для нового n - местного функционального символа в тех случаях, когда формула рх является теоремой.

Здесь переменные х, х1 хn попарно различны, а р не имеет свободное вхождение переменных, отличных от х, х1 хn. Теорема об определениях если теория Т2 получена из теории Т1 путем добавления определяющей аксиомы для нового функционального или предикатного символа v то для каждой теоремы теории Т2 существует равносильная ей теорема теории Т1. 9. Кроме девяти основных применяются дополнительные правила вывода, например правило отделения конъюнкта

pg, р и правило присоединения дизъюнкта р, pg. 10. Применяются известные методы доказательства. Обоснование таких методов дается в учебниках логики. Например метод доказательства от противного основан на следующей теореме. Теорема о доказательстве методом от противного если формальная теория Т2 получена путем добавления аксиомы р к аксиомам теории

Т1 и если формулы q, q являются теоремами теории Т2, то формула р является теоремой теории Т1. Формальная арифметика формализует систему знаний о целых неотрицательных числах, использует в качестве исходных четыре функциональных и два предикатных знака g g интерпретируемых в соответствии с их известными со школы специальными начертаниями, имеет такие аксиомы 10 х 1 y x y x 0 x x y 1 x y 1 x0 0 xy 1 xy x x 0 x y 1 x y x y p x, 0px, x 1 p Здесь при записи аксиом использованы ранее перечисленные соглашения

о компактизации изложения и известное соглашение о том, что знак умножения связывает сильнее знака сложения. Если такие соглашения не принимать, то к примеру первую аксиому следовало бы записать в виде g Пример определяющих аксиом для новых нульместных функциональных знаков 2, 3, 4, 5 и новых двухместных предикатных знаков , 2 1 112 2 13 2 112 1 2 1 24 3 112 1 2 1 25 4 112 1 2 Заметим, что знак можно было бы не включать в перечень исходных знаков формальной арифметики, а ввести

его с помощью определяющей аксиомы 12 33 0 1 3 2. Пример доказательного текста в формальной арифметике k 3, е 6, m 1, n 3 Константа Константа31 Переменная4g , Предикат от 2,15g , Отрицание 46g 1, Предикат от 3,17g 1, Отрицание 681g 1, Подтверждение 7 по 19g , 1g 1, Импликация 5,810g , 5 аксиома11 g , 1g 1, 9 пр. подт. 7, 1, 212g , 5 аксиома 10131 g 1, 8 пр. отделения для 12, 11

Компактизированный текст 111 0 11 0 Правило подтверждения121 0 Аксиома1311 0 Правило отд. для 12, 11 Словесный вариант Если единица не равна нулю, то тем самым существует не равное нулю число. Но единица не равна нулю. Следовательно, существует число, не равное нулю . Тема 7. Множества и функции. В этой теме A, B, C,

D, E, F, G, X, Y, Z, X1, Z1 Xn, Yn, Zn обозначают попарно различные переменные. Множество это совокупность различных объектов, мыслимая как единый новый объект. Различные объекты, из которых составлено множество, называются его элементами. Соотношение xA означает, что объект х есть элемент множества A. Отрицание соотношения xA записывается в виде xA.

Соотношение АВ означает, что А есть подмножество множества В, т.е. что каждый элемент множества А является элементом множества В. Отрицание соотношения АВ записывается в виде АВ. Множество, элементами которого являются все те и только те объекты вида а, для которых истинно соотношение p, обозначается через ap. Множество xAxA называется пустым множеством и обозначается символом

O. Множество xx x1x xn обозначается через x1 xn. Множество xxAxB называется объединением множеств А, В и обозначается через АВ. Множество xxAxB называется пересечением множеств А, В и обозначается через АВ. Множество xxAxB называется дополнением множества В относительно А или результатом удаления из множества А элементов множества В и обозначается через АВ. Простейшие теоремы 39, 7, 3, x5x2 4 3, 7,

AA, AA, Обозначения для некоторых множеств 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 x1 xn. Множество x1 xn x1z1 xnzn называется декартовым произведением множеств z1 zn и обозначается через z1zn. Если А - множество упорядоченных n-ок, то множество xkx1 xnA называется k-той проекцией n-мерного множества А и обозначается через А. Через Аn обозначается множество АА n множителей. Соглашение знаки связывают сильнее чем

Простейшие теоремы x1 xn y1 yn x1 y1 xn yn, 9, 9, 9 9, 9, ABCDE C, 5. 72 5, 5, 5, 7, 7, 5, 7, 7, koor 5, 7, 9 9, koor 5, 7, 9 koor 5, 7, 9 koor 5, 7, 9 H, 78, 59 7, 8, 9, 7, 5,9. 45 4, 4, 4, 4, 4, 1, 2, 3, 1, 3, 2, 2, 3, 4 2, 3. ABC ABC. Функцией называется множество, любой элемент которого есть упорядоченная двойка. Множество называется областью определения или доменом функции

F и обозначается dom F. Множество называется областью значений или ранжиром функции F и обозначается ran F. Если x,yF, то y называется значением функции F в x и обозначается Fx. Если А domF, то множество yAx, yF называется образом множества А относительно функции F и обозначается FА. Функция F в случае dom F A и ran FB ranFB называется еще отображением множества

А вна множество В. Запись FАВ означает что F есть отображение множества А в множество В. Функция F называется сужением функции G на множество dom F, а функция G называется расширением функции F на множество dom G, если F есть результат удаления из G всех тех x, y, для которых x dom F. Если F есть функция, то y, x x, yF тоже есть функция, называемая

обратной по отношению к F. Очевидно, что если функция G является обратной по отношению к функции F, то F является обратной по отношению к G. Если dom F есть множество упорядоченных n-ок, то функция F называется n-аргументной и вместо Fx1 xn используют более короткое обозначение Fx1 xn. Функция F называется однозначной, если из x, yF и x, zF следует yz.

Функция называется взаимно однозначной или биективной, если она сама и обратная к ней функция являются однозначными. Последовательностью называется однозначная функция F т.ч. dom F N. Если F есть последовательность и nN, то Fn называется n-м членом последовательности и обычно обозначается через Fn. Множество А называется бесконечным, если существует биективное отображение множества

N в множество А. Множество называется конечным, если оно не является бесконечным. Простейшие теоремы cos01, cos0 1, Аrccos и cos обратны друг к другу, функция arccos не является обратной к cos и является обратной к сужению функции cos на множество ran arccos.