Логика высказываний (или пропозициональная логика от англ. propositional logic) — это формальная теория, основным объектом которой служит понятие логического высказывания. С точки зрения выразительности, её можно охарактеризовать как классическую логику нулевого порядка. Логика высказываний является простейшей логикой, максимально близкой к человеческой логике неформальных рассуждений и известна ещё со времён античности.
Содержание |
Базовыми понятиями логики высказываний являются пропозициональная переменная — переменная, значением которой может быть логическое высказывание, — и (пропозициональная) формула, определяемая индуктивно следующим образом:
Знаки и (отрицание, конъюнкция, дизъюнкция и импликация) называются пропозициональными связками. Подформулой называется часть формулы, сама являющаяся формулой. Собственной подформулой называется подформула, не совпадающая со всей формулой.
Теперь, зная буквы-элементарные высказывания, мы никогда не ошибёмся, определяя, является ли формулой запись, содержащая эти буквы, скобки и символы связок, то есть правильно ли построено сложное высказывание. В процессе подобного опознавания мы выделяем части формулы, то есть более короткие формулы, из которых на каждом этапе строится более длинная формула с применением одной связки. Самыми простыми частями формулы являются, разумеется, элементарные высказывания. Значит, логический анализ формулы сводится к выделению всех её частей.
Пусть элементарными высказываниями являются А, В, С. Записи
¬ A BC и (B)(BA→C)
c формальной точки зрения не являются формулами, так как мы натыкаемся при их разборе на нарушение правил построения формул. (В первом случае отсутствует логическая связка между B и C и отсутствуют скобки вокруг ¬A. Во втором случае формула нулевого уровня В включена в скобки). А записи
(¬ A)(BC) и B((BA)→C)
вполне соответствуют требованиям построения формулы. В процессе анализа формулы (¬ A)(BC) выделяются следующие её части:
( ¬A ) ( BC ) | Связующее действие ¬A B C | Разделённые части (формулы первого уровня) ¬ | Связующее действие A B C | Разделённые части (формулы нулевого уровня) | Все разделённые части являются элементарными высказываниями; разбор закончен.
В этом примере все элементарные высказывания были выделены на втором шаге исследования дерева. Но это совпадение; если бы вместо формулы первого уровня (¬A) была использована формула нулевого уровня А, то левая ветвь была бы короче правой.
Построенная нами конструкция отдалённо напоминает дерево, растущее вверх ногами. «Корень» его — исходная формула, роль «веток» играют логические связки. Там, где имеется разветвление, стоят части формулы. А на концах веток растут «листья» — элементарные высказывания.
Подобные конструкции часто используются в математике и в программировании, они так и называются «деревьями».
Поскольку в построенных по определению формулах оказывается слишком много скобок, иногда и не обязательных для однозначного понимания формулы, математики приняли соглашения о скобках, по которым некоторые из скобок можно опускать. Записи с опущенными скобками восстанавливаются так:
Когда говорят о длине формулы, имеют в виду длину подразумеваемой (восстанавливаемой) формулы, а не сокращённой записи.
Например: запись означает формулу , а её длина равна 12.
Оценкой пропозициональных переменных называется функция из множества всех пропозициональных переменных в множество {0, 1} (т.е. множество истинностных значений). Основной задачей логики высказываний является установление истинностного значения формулы, если дана оценка (т.е. определены истинностные значения входящих в неё переменных). Истинностное значение формулы в таком случае определяется индуктивно (с шагами, которые использовались при построении формулы) с использованием таблиц истинности связок.
Оценка отрицания задаётся таблицей:
|
|
|
|
Значение двуместных логических связок (импликация), (дизъюнкция) и (конъюнкция) определяются так:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Формула является тождественно истинной, если она истинна при любых значениях входящих в неё переменных. Вот несколько широко известных примеров тождественно истинных формул логики высказываний:
1) ;
2) ;
;
Законы поглощения:
1) ;
2) ;
1) ;
2) .
Одним из возможных вариантов (Гильбертовской) аксиоматизации логики высказываний является следующая система аксиом:
;
;
;
;
;
;
;
;
;
;
.
вместе с единственным правилом:
Теорема корректности исчисления высказываний утверждает, что все перечисленные выше аксиомы являются тавтологиями, а с помощью правила modus ponens из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.
Это заготовка статьи по логике. Вы можете помочь проекту, исправив и дополнив её. |
Логика высказываний.