пропозициональная логика

пропозициональная логика
        ЛОГИКА ВЫСКАЗЫВАНИЙ, пропозициональная логика — раздел символической логики, изучающий
        сложные высказывания, образованные из простых, и их взаимоотношения. В отличие от логики предикатов, простые высказывания при этом выступают как целые образования, и их внутренняя структура не рассматривается, а учитывается лишь то, с помощью каких союзов и в каком порядке простые высказывания сочленяются в сложные. Под высказыванием понимается то, что выражается повествовательным предложением.
        В естественном языке существует много способов образования сложных высказываний из простых. Мы выберем пять общеизвестных грамматических связок (союзов): «не», «и», «или», «если..., то» и «если и только если». Процесс символизации естественного языка средствами Л. в. состоит в следующем. Элементарные высказывания замещаются пропозициональными переменными р, q, r,... с индексами или без них; указанные выше грамматические связки называются пропозициональными (логическими) связками и соответственно получили следующие обозначения и названия: -• (отрицание), л или & (конъюнкция), v (дизъюнкция), г> (импликация) и = (эквиваленция); и, наконец, используются скобки (,), для того чтобы можно было по-разному группировать высказывания и этим определять порядок выполнения операций. Отрицание является одноместной связкой, а остальные четыре — двухместные связки. Выражением языка Л. в. будем называть любую последовательность указанных выше символов. Некоторые из этих выражений являются правильно построенными. Такие выражения называются формулами, определение которых задается следующими Правилами, где буквы А, В... используются как метапеременные: 1) всякая пропозициональная переменная есть формула; 2) если А и В — формулы, то -тА, А л В, AVB,AZDB, A = B тоже формулы; 3) никакие др. выражения не являются формулами. Таким образом, правила задают эффективный способ распознавания, является ли выражение Л. в. формулой.
        Теперь сделаем два основных допущения, на которых основывается семантика классической Л. в. I. Каждое простое высказывание является или только истинным, или только ложным (принцип двузначности). «Истина» и «ложь» называются истинностными значениями высказывания и обозначаются соответственно И и Л, или 1 и 0. II. Истинностное значение сложного высказывания определяется только истинностными значениями составляющих его простых высказываний (принцип экстенсиональности). Это Означает, что пропозициональные связки являются знаками истинностных функций. Возникает вопрос: какие истинностные функции соответствуют нашим связкам?
        Удобным способом задания истинностных функций является табличный, где слева указываются все возможные приписывания значений аргументам (пропозициональным переменным), а справа — значения самой функции.
        Опишем этот способ словесно. Если высказывание р истинно, то высказывание -<р ложно; и наоборот: если ->р истинно, тор ложно. Высказываниер л q истинно тогда и только тогда (т.т.т.), когда истинны оба высказывания р и q. Высказывание р v q ложно т.т.т., когда ложны оба высказывания р и q. Высказывание р z> q ложно, если р истинно, a q ложно; В остальных случаях высказывание р з q истинно. Высказывание р = q истинно т.т.т., когда оба высказывания р и q принимают одинаковые значения.
        Каждая формула определяет некоторую истинностную функцию, которая графически может быть представлена истинностной таблицей. При этом формула может быть такой, что на каждой строке она принимает только значение, равное И, или только значение, равное Л. В первом случае она называется тавтологией (тождественно истинным высказыванием), а во втором — противоречием (тождественно ложным высказыванием). В формальной логике тавтологии играют важную роль. Они служат для записи ее законов (см. Логический закон), т.к. тавтологии являются всегда истинными высказываниями только в силу своей символической формы, независимо от содержания входящих в них исходных высказываний. Легко установить, что формулы Аз А, А v - > А, -А л -iA) являются тавтологиями. Законы, выражаемые этими формулами называются соответственно законом тождества, законом исключенного третьего и законом непротиворечия.
        Обратим внимание на исключительно важное свойство истинностных таблиц: они дают нам эффективную процедуру для решения вопроса о том, является ли данная пропозициональная формула тавтологией. Указанная процедура называется разрешающей процедурой, и отсюда следует, что развиваемая здесь Л. в. является разрешимой логикой (см. Разрешения проблема). Приведем некоторые общие факты о тавтологиях, настолько общие, что они называются правилами Л. в.
        1. Правило отделения (modus ponens). Если А и A Z) В тавтологии, то В тавтология.
        2. Правило подстановки. Если А(р) есть тавтология, то А(В) тоже тавтология, где В замещает каждое вхождение р, т.е. подстановка в тавтологию приводит к тавтологии. Уже отсюда следует, что имеется бесконечное множество тавтологий.
        Отметим некоторые эквивалентности, указывающие на взаимовыразимость одних связок через другие: А л В H-.(-,Av-iB),AvBH-,(-,AAnB),ADB = -.AvB,(A = B) = (АэВ)л(ВэА). Назовем систему пропозициональных связок М полной, если всякая истинностная функция представима некоторой формулой, в которую входят только связки из системы М, т.е. посредством такой сиетемы можно выразить все истинностные функции. Тогда системы связок - i, л, v, - л, - i, v и - >, з являются полными. Это значит, что мы можем строить Л. в., взяв в качестве исходной любую из указанных систем связок. Оказывается, полной может быть система, состоящая только из одной связки |, которая называется «штрих Шеффера»: высказывание pq истинно, когда неверно, что р и q оба истинны. Достаточность связки | следует из тавтологий -A = А|А, AvB = (AA) (BB).
        Наряду с понятием тавтологии фундаментальным для Л. в. является понятие логического следования. Запись А |= В обозначает, что В логически следует из А, а р= А обозначает, что А есть тавтология.
        Если определено понятие тавтологии и определено семантическое понятие логического следования, то говорят, что дано семантическое представление Л. в., а сама Л. в. зачастую отождествляется с множеством тавтологий или с самим отношением логического следования. Однако такое представление ставит следующую серьезную проблему: как обозреть все тавтологии, которых бесконечное множество? Для решения этой проблемы переходят к синтаксическому представлению Л. в.
        Формальный (символический) язык Л. в. и понятие формулы остаются прежними, и теперь из всего множества тавтологий выбирается некоторое их конечное подмножество, элементы которого называются аксиомами. Напр.: 1. р з (q з р), 2. (р з ( < j з г)) з ((р з q) з (р з г)), 3. р з (р v q), 4. qз (p v q), 5. ( p з г) з ((qэг)э ((p vq) =>r)), 6. (pл < ? ) з р, 7. (pлq) з q, 8. (p з q ) з ( ( p з г) з (р з (q л r))), 9. (p з -.< ? ) D ( p -.p), 10. p з ( - n p = > < j), ll.p v-ip.
        С помощью уже известных правил, но чисто формально, осуществляется переход от высказывания, или системы высказываний, к высказыванию. Так, заданную Л. в. обозначим посредством С₂ и назовем классической Л. в. Именно классическая Л. в. лежит в основе абсолютного большинства научных теорий и в силу ее интерпретации посредством релейно-контактных схем получила самое широкое применение в компьютерных науках.
        Логическое исчисление, заданное посредством некоторого множества аксиом и некоторого множества правил вывода, называется гильбертовским исчислением. Доказуемыми формулами (или теоремами) рассматриваемого исчисления называются любые формулы, которые могут быть получены из аксиом исчисления в результате применения (возможно, многократного) указанных правил. Запись |- А служит сокращением утверждения «А есть теорема». Если формула А выводима из некоторого множества Г исходных формул (посылок), то тогда запись принимает вид Г-А (см. Вывод логический).
        Исходя из синтаксического представления Л. в., последняя зачастую отождествляется с множеством теорем или с отношением выводимости. Несмотря на различие семантического и синтаксического подходов к построению Л. в., оба подхода к построению Л. в., по существу, эквивалентны и, как говорят, являются адекватными. Это значит, что понятия логического следования и понятия вывода равнозначны. Рассмотрим следующую примечательную теорему, которая иногда называется теоремой адекватности: для всякой формулы А, -А т.т.т., когда |= А.
        Доказательство в одну сторону, а именно: для всех А, если |-А, то р А, носит название теоремы о корректности. Это минимальное условие, которое мы требуем от логического исчисления и которое состоит в том, что представленная нами семантика корректна для выбранной аксиоматизации. Отсюда следует, что С₂ является непротиворечивым исчислением. Имеет место и обратное утверждение: каждая тавтология доказуема, т.е для всякой формулы А, если |= А, то - А. Доказательство этой теоремы носит название теоремы о полноте исчисления высказываний относительно предложенной семантики. По существу здесь утверждается, что логических средств, т.е. аксиом и правил вывода, исчисления высказываний С₂ вполне достаточно для доказательства всех тавтологий.
        Первая аксиоматизация классической логики С₂ была предпринята Г. Фреге в 1879. Однако в терминах современного символического языка аксиоматизация С₂ появилась в «Principia Mathematica» А. Уайтхеда и Б. Рассела в 1910—1913. Первая публикация доказательства полноты принадлежит Э. Посту (1921), который исходил из системы Уайтхеда и Рассела и использовал двузначные истинностные таблицы (приведенные выше) для доказательства теоремы адекватности.
        Теперь мы можем дать характеристику того, что называется классической Л. в. а) С. основана на принципе двузначности (Двузначности принцип). Ь) С₂ является максимальной в том смысле, что она не имеет непротиворечивых расширений: всякое добавление к ней в качестве аксиомы какой-либо формулы, не доказанной в ней, делает ее противоречивой, с) С имеет наиболее простую семантику.
        Посредством модификации, исключением или добавлением др. аксиом получают различные неклассические логики высказываний.
        См.: Алгебра логики, Логика, Символическая логика.
        А.С. Карпенко

Энциклопедия эпистемологии и философии науки. М.: «Канон+», РООИ «Реабилитация». И.Т. Касавин. 2009.