1 - Алгебра высказываний. Введение. Алгебра логики. Тавтологии и эквивалентность формул. Функции алгебры логики (Конспект лекций), страница 2

В качестветаких элементов выступают, например, число 0 или 1, т.е. элементы, чем-то выделяющиеся сточки зрения других операций.Выделим пять операций над высказываниями:1) дизъюнкция (соответствует союзу или“);”2) конъюнкция (соответствует союзу и“);”3) импликация (соответствует фразе типа если . . . , то );””4) эквиваленция (соответствует фразе типа . . . тогда и только тогда, когда . . . );”5) отрицание (соответствует союзу не“).”Первые четыре из этих операций бинарные, последняя унарная. Относительно указанныхопераций можно сказать лишь, что они формируют новое высказывание. При этом, зная,истинны или ложны исходные высказывания, можно сказать, является ли истинным вновьÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-121.2.

Алгебра логикиÌÃÒÓÌÃÒÓНепротиворечивость конкретной теории можно установить, построив модель этой теории врамках другой теории. В результате мы придем к заключению: если та, другая теория непротивречива, то и наша теория непротиворечива. В этом случае говорят об относительнойнепротиворечивости. Абсолютная непротиворечивость означает, что данная теория непротиворечива независимо от того, являются непротиворечивыми другие теории или нет.В 20 в. практически все математические теории получили свои модели в рамках арифметики. Так, все числовые системы были построены на базе множества натуральных чисел.

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

Выходит, в математике, как и в других науках абсолютной истины нет.ÌÃÒÓÔÍ-12ÌÃÒÓ3ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. АЛГЕБРА ВЫСКАЗЫВАНИЙÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓобразованное высказывание. Введенные пять операций мы будем называть логическими илипропозициональными.Для символической записи высказываний и операций над ними необходимо ввести некоторыйнабор символов и сформулировать правила записи с помощью этих символов. Набор символов(алфавит) в сочетании с набором правил записи представляет собой некоторый язык — языкалгебры высказываний.

Вообще говоря, алфавит позволяет из заданного набора символов составлять цепочки символов (слова, фразы). Множество всех цепочек символов разделяется надве группы: правильные и неправильные. Правильные цепочки можно назвать словами, ихмножество и называется языком.На практике язык можно определить как множество цепочек, удовлетворяющих некоторымтребованиям, которые в конечном счете сводятся к тому, является ли данная цепочка интепретируемой с точки зрения выполнения операций или нет. Но часто язык определяют, указываяправила, по которым из уже построенных слов можно строить новые.

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

Притаком определении сначала задаются первичные, элементарные слова (это база индукции), азатем указываются правила, по которым из уже построенных слов формируются новые (шагиндукции).Алфавит языка алгебры высказываний составляют множество пропозициональных переменных, множество функциональных символов (символов операций, или логических связок) ∨, ∧, →, ∼, ¬ и множество служебных символов (две круглые скобки). Формулы языкавводятся индуктивно.База индукции: пропозициональные переменные представляют собой формулы.Шаг индукции: если X и Y — формулы, то формулами являются (X ∨ Y ), (X ∧ Y ), (X → Y ),(X ∼ Y ), ¬X.Договоримся о следующих обозначениях.

Будем обозначать: пропозициональные переменные — строчными латинскими буквами конца алфавита (x, y, z и т.д.); какие-либо формулы —прописными латинскими буквами конца алфавита (X, Y , Z и т.д.). Для сокращения количества скобок в формулах с целью улучшить их читаемость договоримся о дополнительныхправилах. Это правило приоритета операций. Вместо, например ((X∆Y )∆Z), как положенопо определению, будем писать X∆Y ∆Z, имея в виду, что операции выполняются слева направо,причем сначала отрицание, затем дизъюнкция и конъюнкция, а потом ипликация и эквиваленция. Соглашение не относится к самому языку и служит лишь для удобства: в любой моментсокращенную запись формулы однозначным образом можно преобразовать в полную запись совсеми нужными скобками. В математический язык эти правила вводить нет смысла, посколькуони ничего не добавляют к математической сути вопроса.В наших рассуждениях будут встречаться формулы, которые относятся к введенному языку,но, кроме того, придется использовать и дополнительные обозначения и символику, чтобы рассуждать не в рамках языка, а о самом языке и его формулах.

Так, обозначения переменных —это элемент языка алгебры высказываний, а обозначения формул или соглашение о приоритетеуже выходят за рамки языка. В этом случае говорят о расширении рассматриваемого языкаили о метаязыке. На практике язык и метаязык тесно переплетаются и трудно разделимы.Рассмотрим какую-либо формулу, например (x → y) → z. Об истинности этой формулыможно судить, если известно, истинны ли элементарные высказывания x, y, z. Например, еслиx и z ложны, а y истинна, то x→y является истинной, а (x→y)→z ложной. Приписав истиннойформуле значение 1, а ложной — 0, мы получаем функцию, которая по значениям истинностипропозициональных переменных (элементарных высказываний) определяет значение истинности всей формулы.

Эта функция есть отображение вида h: {0, 1}n → {0, 1} (и аргументы,и функция принимают значения 0 и 1). Она называется истинностной функцией даннойÌÃÒÓÔÍ-12ÌÃÒÓ4ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. АЛГЕБРА ВЫСКАЗЫВАНИЙÌÃÒÓПонятие истинностной функции позволяет и введенные логические операции рассматривать совершенно формально — как формульную запись некоторых истинностных функций(табл. 1.1). В дальнейшем через |X| мы будем обозначать истинностную функцию формулы X.Таблица 1.1ÌÃÒÓx0011y0101¬x10x∨y0111x∧y0001x→y1101x∼y10011.3. Тавтологии и эквивалентность формулÌÃÒÓÔÍ-12Среди формул алгебры высказываний выделяют:– тождественно истинные, или тавтологии, истинные при любой истинности переменных;– выполнимые, имеющие значение 1 хотя бы для одного набора значений пропозициональных переменных;– опровержимые, имеющие значение 0 хотя бы для одного набора значений пропозициональных переменных.– тождественно ложные, или противоречия, ложные при любой истинности переменных.Эти четыре понятия связаны между собой.

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

представляет собой противоречие.Для тавтологий (противоречий) истинностная функция есть константа 1 (0). Для выполнимых формул истинностная функция не равна постоянной 0, а для опровержимых —постоянной 0.ÔÍ-12Тавтологии. Формулы выполнимые и опровержимые. Теорема о правиле modus ponens: еслиX и X → Y — тавтологии, то и Y — тавтология. Подстановка. Эквивалентность формул алгебры высказываний. Теорема о заменах. Следствие 1: если X — тавтология, тои S(z1 , z2 , . . . , zn |Y1 , Y2 , .

. . , Yn |X) — тавтология. Следствие 2: инвариантность эквивалентности относительно логических операций. Способы получения эквивалентных формул: наоснове свойств логических операций; на основе взаимосвязей операций; на основе двойственности.ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓЗамечание. Отметим различия понятий формула“ и функция“.

Первое понятие связано””с языком, на котором описываются свойства математических объектов. Формула имеет некоторый набор переменных, если заданы значения этих переменных, то формула также имеетнекоторое значение. В этом смысле формулу можно рассматривать как запись некоего правила,которое заданным значениям переменных ставит в соответствие новое значение. Это похожена понятие функции, но функция (отображение) есть реальный математический объект, а незапись о нем в некотором языке.