Лекция
Сразу хочу сказать, что здесь никакой воды про правила логики высказываний, и только нужная информация. Для того чтобы лучше понимать что такое правила логики высказываний, факты о тавтологиях, классическая логика высказываний , настоятельно рекомендую прочитать все из категории Логика.
Логика высказываний, пропозициональная логика (лат. propositio — «высказывание» ) или исчисление высказываний , также логика нулевого порядка — это раздел символической логики, изучающий сложные высказывания, образованные из простых, и их взаимоотношения. В отличие от логики предикатов, пропозициональная логика не рассматривает внутреннюю структуру простых высказываний, она лишь учитывает, с помощью каких союзов и в каком порядке простые высказывания сочленяются в сложные .
Несмотря на свою важность и широкую сферу применения, логика высказываний является простейшей логикой и имеет очень ограниченные средства для исследования суждений[2
Ниже приведены некоторые общие факты о тавтологиях , настолько общие, что они называются правилами логики высказываний:
Из последнего правила следует, что можно преобразовывать формулы, получая другие, им эквивалентные, на более простые (содержащие меньше пропозициональных связок и переменных). Можно теперь любую формулу привести к какому-либо каноническому виду и этим решать определенного рода задачи. Более того, некоторые эквиваленции выражают основные свойства пропозициональных связок. Например, эквиваленции (Α ∧ B) ≡ (B ∧ Α) и (Α ∨ B) ≡ (Α ∨ B) выражают коммутативный закон конъюнкции и соответственно дизъюнкции. Все эти вопросы (и другие) изучает алгебра логики, основы которой заложены в работах Дж. Буля (1847, 1854) и А. де Моргана (1847).
Отметим некоторые эквиваленции, указывающие на взаимовыразимость одних связок через другие: Α ∧ B ≡ ¬ (¬ Α ∨ ¬ Β), Α ∨ B ≡ ¬ (¬ Α ∧ ¬ B), Α ⊃ B ≡ ¬ Α ∨ B, (Α ≡ B) ≡ (Α ⊃ B) ∧ (B ⊃ Α). Система пропозициональных связок M называется полной, если всякая формула эквивалентна некоторой формуле, в которую входят только связки из системы М, то есть посредством такой системы можно выразить все истинностные функции. Так, системы связок {¬, ∧, ∨), {¬, ∧}, {¬, ∨} и {¬, ⊃} являются полными. Это значит, что мы можем строить логику высказываний на основе любой из указанных систем связок. Оказывается, полной может быть система, состоящая только из одной связки |, которая называется «штрих Шеффера»: высказывание p|q истинно тогда и только тогда, когда неверно, что p и q оба истинны. Достаточность связки | следует из тавтологий: ¬ Α ≡ Α|Α, Α ∨ B ≡ (Α|Α) | (B|B).
Наряду с понятием тавтологии фундаментальным для логики высказываний является понятие логического следования, поскольку одной из главных задач логики является устанавливать, что из чего следует, и тем самым указывать, какие высказывания являются теоремами при заданных условиях. Всякую теорему можно записать в виде импликации и таким образом выделить ее условие и заключение. Говорят, B логически следует из Α или является логическим следствием из Α, и пишут Α | = B, если в таблицах истинности для Α и B формула B имеет значение И во всех тех строках, где Α имеет значение И. Об этом говорит сайт https://intellect.icu . Отсюда вытекает, что Α | = B тогда и только тогда, когда Α ⊃ B есть тавтология. Если формула Α тавтология, то иногда пишут | = Α. Приведенное определение логического следования без труда расширяется на некоторую систему формул (систему посылок) Α1, … Αn, которая обозначается посредством Г, и тогда пишут Г | = B. Примером логического следования (вывода) из посылок является уже упомянутое правило modus ponens. Выводимость B из высказываний Α и Α ⊃ B следует из того, что формула (Α ∧ (Α ⊃ B) ⊃ B является тавтологией. Следует также отметить, что в силу таблиц истинности для связки импликации получаем, что тождественно истинная формула логически следует из любой системы формул. Α из того, что имеется разрешающая процедура для тавтологий, получаем, что проблема выводимости произвольной формулы B из заданной системы посылок также разрешима.
Если определено понятие тавтологии и определено семантическое понятие логического следования (как это сделано выше), то говорят, что дано семантическое представление логики высказываний, а сама логика высказываний зачастую отождествляется с множеством тавтологий или с самим отношением логического следования. Однако такое представление ставит серьезную проблему: как обозреть все тавтологии, которых бесконечное множество? Для решения этой проблемы нужно перейти к синтаксическому представлению логики высказываний.
Формальный (символический) язык логики высказываний и понятие формулы остаются прежними. Но теперь из всего множества тавтологий выбирают некоторое их конечное (и, вообще говоря, определяемые неоднозначно) подмножество, элементы которого называются аксиомами. Например:
Таким образом, в отличие от табличного определение логических связок ¬, ∧, ∨, ⊃ задается аксиоматически. Затем с помощью уже известных правил, но чисто формально осуществляется вывод — переход от высказывания или системы высказываний к высказыванию: из Α и Α ⊃ B следует B (правило заключения); из Α (p) следует Α (B) (подстановка). Так, заданную логику высказываний обозначим посредством C2 и назовем классической.
Каждая аксиоматическая система, которая использует правило подстановки, может быть переформулирована в виде системы аксиомных схем, где вместо пропозициональных переменных используются символы произвольных высказываний (так называемые метапеременные). В этом случае каждая аксиомная схема представляет бесконечное множество аксиом и тогда правило подстановки оказывается излишним.
Логическое исчисление, заданное посредством некоторого множества аксиом и некоторого множества правил вывода, называется исчислением гилбертовского типа. Выводом в нем называется всякая последовательность Α1, … Αn формул такая, что для любого i формула Αi, есть либо аксиома, либо непосредственное следствие каких-либо предыдущих формул по одному из правил вывода. Формула Α называется теоремой, если существует вывод, в котором последней формулой является Α; такой вывод называется выводом формулы Α. Запись |– Α служит сокращением утверждения «Α есть теорема». Если формула Α выводима из некоторого множества Г исходных формул, то тогда запись принимает вид Г |– Α.
Исходя из синтаксического представления логики высказываний, последняя зачастую отождествляется с множеством теорем или, что более принято, с отношением выводимости. Итак, при семантическом подходе формулы понимаются содержательно (как функции на множестве из двух элементов И, Л), а при синтаксическом подходе формула — это определенный набор символов и различаются только теоремы и нетеоремы. Однако, несмотря на такое различие, оба подхода к построению логики высказываний по существу совпадают и, как говорят, являются адекватными. Это значит, что совпадают понятия логического следования и понятия вывода. Рассмотрим следующую примечательную теорему, которая иногда называется теоремой адекватности: для всех Α, |– Α тогда и только тогда, когда |= Α.
Доказательство в одну сторону, а именно: для всех Α, если |– Α, то |= Α носит название теоремы о корректности. Это минимальное условие, которое мы требуем от логического исчисления и которое состоит в том, что представленная нами семантика корректна для выбранной аксиоматизации. Для доказательства теоремы нужно проверить, во-первых, что все аксиомы (1)–(11) являются тавтологиями, что легко устанавливается непосредственной проверкой с помощью истинностных таблиц, и, во-вторых, что правила вывода выбраны таким образом, что они сохраняют тавтологичность. Поэтому все формулы последовательности, образующей доказательство какой-либо теоремы исчисления C2, в том числе и сама доказуемая теорема, являются тавтологиями. Из этой теоремы следует наиболее важное свойство нашего исчисления высказываний C2: в C2 формулы Α и ¬ Α одновременно недоказуемы, то есть исчисление высказываний C2 непротиворечиво. Ели бы это было не так, то (с использованием аксиомы (10) и двойным применением modus ponens) в C2 была бы доказуема любая формула B. В силу этого противоречивая логика высказываний никакой ценности не представляет. В ней истина и ложь неразличимы и поэтому любая теорема одновременно истинна и ложна.
Имеет место и обратное утверждение о том, каждая тавтология доказуема, то есть для всех Α, если |= Α, то |– Α. Доказательство этой теоремы не столь тривиально и носит название теоремы о полноте исчисления высказываний относительно предложенной семантики. По существу здесь утверждается, что логических средств, то есть аксиом и правил вывода, исчисления высказываний C2 вполне достаточно для доказательства всех тавтологий. Таким образом, поставленная цель достигнута: используя минимальные средства, можно обозреть все множество тавтологий.
Имеется много различных аксиоматизаций C2, в том числе состоящих из одной аксиомы и содержащих только одну связку (штрих Шеффера). Понятно, что чем меньше аксиом, тем сложнее доказательства. И вообще, в гилбертовских исчислениях доказательство теорем и сам поиск вывода весьма громоздок. Поэтому используются другие формулировки исчисления, более или менее приближенные к естественным рассуждениям, такие, как исчисление секвенций, исчисление натурального вывода и другие. Но соотношение между семантикой и синтаксисом здесь не столь прозрачно.
Первая аксиоматизация классической логики C2 была предпринята Г. Фреге (1879). Однако в терминах современного символического языка аксиоматизация C2 появилась в «Princіріа Mathematica» А. Уайтхеда и Б. Рассела (1910–1913). В обеих работах вопрос о полноте просто не возникал. Их целью было показать, что вся логика, а в действительности вся математика может быть развита внутри их системы. Первая публикация доказательства полноты принадлежит Э. Посту (1921), который исходил из системы Уайтхеда и Рассела. Еще ранее это было сделано П. Бернайсом. В обоих случаях использовались двузначные истинностные таблицы (приведенные выше) для доказательства теоремы адекватности. В этом случае говорят еще, что эти таблицы являются характеристическими для C2.
Теперь можно перейти к характеризации того, что называется классической логикой высказываний:
Если в приведеной аксиоматизации C2 отбросить последнюю аксиому (закон исключенного третьего), то получим аксиоматизацию пропозициональной интуиционистской логики. Оказывается, она имеет континуум расширений (В. Л. Янков, 1968) и никакие конечнозначные истинностные таблицы не являются для нее характеристическими (К. Гедель, 1932). Есть логики, которые имеют только одно расширение, то есть саму C2.
Что касается множества логик, то результат Янкова говорит о том, что существует континуум различных пропозициональных исчислений только определенного класса, то есть таких логик, которые включают интуиционистскую логику (такие логики называются суперинтуиционистскими или промежуточными). Более того, в этом классе существует бесконечное множество логик, не имеющих конечной аксиоматизации, бесконечное множество неразрешимых логик, а также существуют конечнозначные логики с произвольным числом истинностных значений.
Следует отметить широкое применение алгебраических методов для решения различных задач логики высказываний. Это становится возможным прежде всего с истолкованием логики высказываний как некоторой структуры (в смысле алгебраической «теории структур»). Так, дистрибутивная структура с дополнениями (булевы алгебры) соответствует классической логике высказываний, а импликативная структура, где импликация является некоторым аналогом деления, если конъюнкция трактуется как умножение (псевдобулевы алгебры или алгебры Гейтинга), соответствует интуиционистской логике высказываний. Кроме того, в основе приложений булевой алгебры к логике лежит интерпретация элементов булевой алгебры как высказываний.
В заключение следует обратить внимание, что именно классическая логика высказываний лежит в основе проектирования микросхем для современной цифровой электронной техники, в том числе и для компьютеров, хотя в последнее время ведутся подобные работы, основанные на других логиках — многозначных, нечетких, паранепротиворечивых.
Пожалуйста, пиши комментарии, если ты обнаружил что-то неправильное или если ты желаешь поделиться дополнительной информацией про правила логики высказываний Надеюсь, что теперь ты понял что такое правила логики высказываний, факты о тавтологиях, классическая логика высказываний и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Логика
Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.
Комментарии
Оставить комментарий
Логика
Термины: Логика