Исчисление высказываний (ив). Основные понятия.

Высказывания - предложения естественного языка, в которых содержится информация о предмете, факте, явлении, событии или процессе, и которые могут быть оценены как истинные или ложные (напр. повествовательные предложения). Пример: “Колумб открыл Америку” – истина; “Киев – столица Узбекистана” - ложь. Иногда истинность/ложность высказывания зависит от контекста. В ИВ абстрагируются от состава и структуры предложения, а также от его конкретного содержания, опираясь лишь на его значение истины или лжи. Для этого в текст вместо высказываний вводят пропозициональные переменные (propositio (лат.) – предложение) (обозн. A, B, C, …). Текст представляет собой последовательную цепочку пропозициональных переменных, связанных между собой системой дополнительных символов. Пропозициональные переменные используют, как в математике числовые переменные x, y, z, … В математике вместо числовых переменных можно подставить конкретные числа, а в ИВ вместо пропозициональной переменной можно подставить значение, которое принимает высказывание в конкретном предложении (True/False). Соединение простых повествовательных предложений с помощью союзных слов (доп. символов) формирует сложное суждение. Для обозначения союзных слов в ИВ используют логические связки, а для построения грамматически правильного предложения – вспомогательные символы – скобки. Система правил построения сложных высказываний как последовательности записи пропозициональных переменных, лог. связок и вспомогательных символов определяют возможность формальной записи правильно построенных формул. Система правил преобразования сложных высказываний – алгебра высказываний. Система правил вывода новых высказываний на базе множества имеющихся высказываний, основанная на задании множества отношений между правильно построенными формулами определяет ИВ. Т. о. ИВ – логико-математическая модель, обеспечивающая формальное рассуждение на множестве правильно построенных формул и отношений между ними, отвлекаясь от внутренней структуры элементарного высказывания. Посылки – высказывания, из которых делают вывод нового высказывания. Заключение – полученное высказывание. 2) Исчисление высказываний. Алгебра высказываний. Основные логические операции. Пусть дан алфавит:T = T1  T2  T3, гдеT1 = {A; B; C; …} – пропозициональные переменные;T2 = {, &, , , } – лог. связки;T3 = {;; (; )} – вспомогательные символы. Формула – последовательность символов алфавита T. Правильно построенные формулы (ППФ) задаются системой правил: 1) пропозициональная переменная есть формула, т. е. Fi = A; 2) если F1 и F2 – формулы, то (F 1); (F 2); (F1 & F 2); (F1  F 2); (F1  F 2) и (F1  F 2) также формулы; 3) никаких других формул нет. Лог. связка, используемая при формировании ППФ, определяет исполнение лог. операции. Отрицание (F) – одноместная операция, посредством которой из данной формулы получают её отрицание. Истинно т. и только т., когда F ложно. Ест. яз. : “неверно, что …”. Конъюнкция (F1 & F 2) – двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F, отражающую сложное высказывание. Истинно т. и только т., когда истинны F1 и F2. Ест. яз. : “… и …”, “… а …”, “… но …”, “… также …”, “… хотя …”, “… несмотря на …”, “… вместе с …” и т. п. Дизъюнкция (F1  F 2) – двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F, отражающую сложное высказывание. Истинно т. и только т., когда хотя бы одна из формул F1 или F2 была истинной. Ест. яз. : “… или …”, “… либо …” и т. п. Импликация (F1  F 2) – двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F, отражающую сложное высказывание. Ложно т. и только т., когда F1 истинно, а F2 ложно. Ест. яз. : “если …, то …”, “тогда …, когда …”, “постольку …, поскольку …”, “при наличии …, следует …”, “в случае …, следует …”, “… влечёт …”, “… есть достаточное условие для …”, “…есть необходимое условие для …”, “… при условии, что …” и т. п. Эквиваленция (F1  F 2) – двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F, отражающую сложное высказывание. Истинно т. и только т., когда формулы F1 и F2 имеют одинаковые значения. Ест. яз. : “для того чтобы …, необходимо и достаточно, чтобы …”, “… лишь при условии, что …”, “… в том и только в том случае, когда …” и т. п. 3) Исчисление высказываний. Правила записи сложных суждений. При записи сложных суждений следует обратить внимание, что в формулах нет 2-х рядом стоящих логических связок, они должны быть разделены вспомогательными символами – скобками, нет 2-х рядом стоящих формул, они должны быть разъединены логической связкой. Если принять значимость и силу логических связок в следующем порядке: ; & ; ; , то можно опускать те пары скобок, без которых ясен порядок исполнения логических операций: 1) каждое вхождение лог. связки  относится к пропозициональной переменной или формуле, следующей непосредственно за логической связкой слева; 2) каждое вхождение лог. связки & после расстановки скобок, относящихся к лог. связке , связывает пропозициональные переменные или формулы, непосредственно окружающие лог. связку; 3) каждое вхождение лог. связки  после расстановки скобок, относящихся к лог. связке &, связывает пропозициональные переменные или формулы, непосредственно окружающие лог. связку и т. д. При использовании этих правил к одной и той же лог. связке скобки следует расставлять постепенно, продвигаясь слева направо. В зависимости от знаний и навыков можно опускать многие скобки. 4) Исчисление высказываний. Законы эквивалентных преобразований формул. Fi = Fj означает, что формула (Fi  Fj) = true при любых значениях подформул при пропозициональных переменных, включаемых в Fi и Fj. Тождественная истинность формулы (Fi  Fj) определяет множество законов эквивалентных преобразований алгебры высказываний, часть из которых приведена ниже:коммутативность(F1  F 2) = (F1  F 2); (F1 & F 2) = (F1 & F 2)ассоциативность F1  (F2  F 3) = (F1  F 2)  F3; F1 & (F2 & F 3) = (F1 & F 2) & F3;дистрибутивность F1  (F2 & F 3) = (F1  F 2) & (F1  F 3); F1 & (F2  F 3) = (F1 & F 2)  (F1 & F 3);идемпотентность F  F = F; F & F = F;противоречия F  F = true; F & F = false;де Моргана(F1  F 2) = F1 & F2; (F1 & F 2) = F1  F2;поглощения F1  (F1 & F 2) = F1; F1 & (F1  F 2) = F1;дополнения (F) = F;свойства констант F  false = F; F & false = false;F  true = true; F & true = f;true = false; false = true. Если формула сложного высказывания F содержит подформулу Fi, то замена подформулы Fi всюду в формуле F на эквивалентную ей формулу Fj не изменяет значения формулы F при любом наборе пропозициональных переменных. Если необходима подстановка в формулу F вместо какого-либо символа формулы или пропозициональной переменной Fi новой формулы Fj, то эта операция должна быть выполнена всюду в формуле F по символу Fi. Правила замены и подстановки расширяют возможности эквивалентных преобразований формул сложных высказываний. 5) Исчисление высказываний (ИВ). Проблемы разрешимости формул. Таблицы истинности. Всё множество правильно построенных формул можно разбить на 3 класса: тождественно истинные, тождественно ложные и выполнимые. Тождественно истинные формулы (общезначимые или тавтологии) – это особый класс сложных высказываний, которые принимают значение только true при любом наборе пропозициональных переменных. Тождественно ложные формулы (противоречия) – это особый класс сложных высказываний, которые принимают значение только false при любом наборе пропозициональных переменных. Выполнимые формулы – это сложные высказывания, которые принимают значения true или false для различных наборов пропозициональных переменных. Отнесение формулы к тому или иному классу не имеет единого алгоритма, поэтому эта проблема получила название проблемы разрешимости ИВ. Это можно определить по таблице истинности. 6) Исчисление высказываний. Метод дедуктивного вывода. Modus ponens. Выводимость формулы B из множества формул F1; F2; … Fn со всей очевидностью равносильна доказательству теоремы ├─ (F1 & F2 & … Fn  B), т. е. доказательству того, что B логически следует (имплицирует) из конъюнкции всех посылок (F1 & F2 & … Fn). Т. о., если каждая Fi имеет значение true, то (F1 & F2 & … Fn) также имеет значение true, а если (F1 & F2 & … Fn) имеет значение true, то B также имеет значение true, что и требовалось доказать. Используя правила эквивалентных преобразований алгебры высказываний, можно показать следующее: 1) ├─ (F1 & F2 & … & Fn  B) 2) ├─ ((F1 & F2 & … & Fn)  B) 3) ├─ (F1  F2  …  Fn  B) 4) ├─ (F1  F2  …  (Fn  B)) 5) ├─ (F1  (F2  …  (Fn  B)…)Так формируется система отношений между формулами (система дедуктивного вывода), что формирует логическую цепь рассуждений от посылки до заключения. Удаление импликации. Modus ponens:F1; (F1  F 2)F2Остальные аксиомы см. вопрос 8)