Логика высказываний

1) всякая пропозициональная  переменная есть формула;

2) Если А и В —  формулы, то (¬А), (А^В), (А٧В), (А→В), (А↔В) тоже формулы;

3) Никакие другие выражения  не являются формулами. Примерами  формул являются р, ¬q, ¬(p٧q). Внешние скобки при записи формул будем опускать. Таким образом, правила задают эффективный способ распознавания, является ли выражение логики высказываний формулой. Множество всех формул обозначим посредством For.

Теперь сделаем два  основных допущения, на которых основывается семантика классической логики высказываний:

(1) Каждое простое высказывание  является или только истинным, или только ложным (принцип двузначности). «Истина» и «ложь» называются истинностными значениями высказывания и обозначаются соответственно И и Л или 1 и О.

(2)  Истинностное значение  сложного высказывания определяется  только истинностными значениями  составляющих его простых высказываний (принцип экстенсиональности). Это означает, что пропозициональные связки являются знаками истинностных функций.

Возникает вопрос, какие  истинностные функции соответствуют  нашим связкам?

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

 

 

 

p	¬p
1	0
0	1

 

P	Q	p→q	p٧q	P^q
1	1	1	1	1
1	0	0	1	0
0	1	1	1	0
0	0	1	0	0

p↔q

1

0

0

1

 

 

Отсюда, например, следует, что высказывание р→q ложно тогда и только тогда (т.т.т.), когда р истинно и q ложно. Приведенные выше таблицы называются истинностными таблицами, а определенные посредством их пропозициональной связки называются классическими связками.

Легко определить, сколько имеется различных классических связок. Число различных строк в таблице для истинностной функции с m аргументами равно 2 и на каждой из них значение функции можно задать двумя способами: 1 или 0. Поэтому число таких функций составляет 2 в степени 2. Отсюда, например, число одноместных связок равно 4, а число двухместных связок равно 16.

 

2.2. Законы логики

Каждая формула определяет некоторую истинностную функцию, которая  графически может быть представлена истинностной таблицей. Другими словами, каждая формула может быть представлена как функция от пропозициональных переменных, пробегающих по множеству (0, 1). Посредством истинностных таблиц функция единственным образом расширяется на всё множество For. Функцию ß: For — {0, 1) будем называть логической оценкой множества формул Fоr для любых А, В€ For

ß(¬А) 1 т.т.т., когда ß(А) = О

ß(А → В) = 0 т.т.т., когда  ß(А) = 1 и ß(В) = 0

ß(А٧В) = 0 т.т.т., когда ß(А) = ß(В) = 0

ß(А&В)=1 т.т.т., когда  ß(А) = ß(В) = 1

ß(А↔В) 1 т.т.т., когда ß(А) =ß(В)

Среди всего множества формул выделяются формулы, которые каждой строке истинностной таблицы принимают только значение, равное 1, т.е. ß(А) = 1 при любом приписывании значений пропозициональным переменным, входящим в А. Такие формулы называются тавтологиями (тождественно истинными высказываниями). В формальной логике тавтологии играют важную роль. Они служат для записи её законов, так как тавтологии являются всегда истинными высказываниями только в силу своей символической формы, независимо от содержания входящих в них исходных высказываний. Легко установить, что формулы

(1) р→ р,

(2)р ٧¬р,

(3) ¬(р ٨ ¬р)

являются тавтологиями. Законы, выражаемые этими формулами, называются соответственно законом  тождества, законом исключенного третьего и законом непротиворечия и были сформулированы уже Аристотелем. Использование этих законов в качестве способов рассуждения привело к тому, что они были названы основными законами мышления. Наиболее распространенной формулировкой закона исключенного третьего является следующая: одно из утверждений р или не р должно быть истинным. Эта формулировка получила в схоластической логике название tertium non datur. Закон непротиворечия формулируется следующим образом: два взаимно противоречащих высказывания не могут быть одновременно истинными, т. е. одно из них должно быть ложным. Последний закон формулируется у Аристотеля, прежде всего как универсальный принцип бытия, наиболее достоверный из всех начал. Однако уже на заре ХХ в., еще до того, как окончательно оформилась классическая логика, оба эти закона подверглись серьезной критике, что положило начало развитию неклассических логик. В связи с трехзначной логикой Лукасевича мы к этим законам ещё вернемся, а сейчас дополним список законов классической логики:

(4) ¬¬р↔p   (закон двойного отрицания)

(5) (р → q)→(¬q→¬p)  (закон контрапозиции)

(6) (¬р →¬q) →(q→p) (обратный закон контрапозиции).

Особое место среди  законов занимают чисто импликативные  тавтологии:

(7) р→(q→p) (закон утверждения консеквента)

(8) (p→(q→r))→((р→q)→(р→r)) (закон самодистрибутивности)

(9) (р→q)→((q→r) →(р→r)) (закон транзитивности)

(10) (р→(р→q))→(р→q) (закон сокращения).

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

Приведем некоторые общие факты  о тавтологиях, настолько общие, что они называются правилами  логики высказываний.

1. Правило отделения (modus ponens). Если А и А→В тавтологии, то В тавтология (сокращенно МР).

2. Правило подстановки. Если  А(р) есть тавтология, то А(В)  тоже тавтология, где В замещает  каждое вхождение р, те. подстановка  в тавтологию приводит к тавтологии (сокращенно Subst). Уже отсюда следует бесконечное множество тавтологий.

2.3. Функциональная полнота

Будем называть формулы А и В  логически эквивалентными, если формула  А↔В есть тавтология. Очевидно, что  если формулы эквивалентны, то они  равны как истинностные таблицы, т.е. принимают одинаковые истинностные значения.

Назовем систему пропозициональных  связок М полной, если истинностная функция представима некоторой  формулой, в которую входят только связки из системы М, т.е. посредством  такой системы можно выразить все истинностные функции. Используя свойства логической эквивалентности, можно показать, что каждая логическая связка может быть определена в терминах ¬,٨,٧ в классической логике, т.е. система пропозициональных связок {¬,٨,٧ } является функционально полной. Более точно, для истинностной функции * можно найти такую формулу D, использующую только связки ¬, ٨, ٧, что истинностные таблицы для * и D равны.

Теорема о функциональной полноте. В классической логике каждая истинностно-фукциональная связка может быть определена в терминах ¬, ٨, ٧

Впервые подобная теорема была доказана Э.Постом

 

Отметим некоторые эквивалентности, показывающие взаимовыразимость одних связок через другие:

р٧q↔¬p→q,  p٧q↔(p→q)→q,  р٧q↔¬(¬p^¬q);

р^q↔¬(p→¬q),  р^q↔¬(¬p٧¬q);

p→q↔¬p٧q,  p→q↔¬(p^¬q);

(p↔q)↔(p→q)^(q→p).

Тогда системы связок {¬,→}, {¬,٧} и {¬,^} являются функционально полными. Это значит, что мы можем строить логику высказываний, взяв в качестве исходной любую из указанных систем связок.

2.4. Аксиоматизация. Адекватность

Наряду с понятием тавтологии фундаментальным для  логики является понятие логического  следования. Одна из главных задач  логики заключается в том, чтобы  устанавливать, что из чего следует, и тем самым определять, какие  высказывания являются теоремами при заданных условиях. Говорят «В логически следует из А или является логическим следствием из А» и пишут А ╞ В. Если в совместной таблице истинности для А и В формула В имеет значение И во всех тех строках, где А имеет значение И. Отсюда следует, что А ╞ В т.т.т., когда А→В сеть тавтология. Если формула А является тавтологией, то иногда пишут ╞А. Приведенное определение логического следования без труда может быть расширено на некоторую систему формул Г и тогда пишут Г╞В. Примером логического следования (вывода) из посылок является правило modus ponens. Отметим также, что в силу табличного определения импликации получаем, что тождественно истинная формула А логически следует из любой системы формул. А из того, что имеется разрешающая процедура для тавтологий, получаем, что проблема выводимости произвольной формулы В из заданной системы посылок также разрешима.

Если определено понятие  тавтологии и определено семантическое  понятие логического следования (как это сделано выше), то говорят, что дано семантическое представление логики высказываний, а сама логика высказываний зачастую отождествляется с множеством тавтологий или с самим отношением логического следования. Однако при этом возникает следующая серьезная проблема: как обозреть все тавтологии, которых бесконечное множество? Для решения этой проблемы переходят к синтаксическому представлению логики высказываний.

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

1. р→(q→p)

2. (p→(q→r))→((p→q)→(p→r))

3. р→(р٧q)

4. q→(р٧q)

5. (p→r)→((q→r)→((p٧q)→r))

6. (р^q)→p

7. (р^q)→q

8. (p→q)→((p→r)→(p→(q^r)))

9. (р→¬q)→(q→¬p)

10. р→(¬р→q)

11. p٧¬p

Таким образом, мы задали аксиоматическое определение логических связок ¬, ^, ٧,→ в отличие от табличного при семантическом описании логики высказываний. Переход от формулы или системы формул к формуле осуществляется с помощью уже известных правил, которые записываются следующим образом:

R1.Из А и А→В следует В (modus ponens)

      R2.Из ├А(р) следует ├А(В) (подстановка).

Так заданную логику высказываний обозначим посредством C₂ и назовем классической логикой высказываний

Из раздела (2.3) следует, что логику высказываний можно развивать на основе системы связок {¬,→}. Именно так впервые и представлена аксиоматизация С₂ в работе Г.Фреге Следующая аксиоматизация С₂ принадлежит Лукасевичу  который значительно упростил аксиоматизацию, предложенную Фреге:

1. p→(q→p)

2. (p→(q→r))→((p→q)→(p→r))

3. (¬p→¬q)→(q→p)

Правила вывода: modus ponens и подстановка. Детально эта аксиоматизация С₂ исследуется А.Чёрчем

Логическое исчисление, заданное посредством некоторого множества  аксиом и некоторого множества правил вывода, называется гильбертовским исчислением. Доказуемыми формулами (или теоремами) рассматриваемого исчисления называются любые формулы, которые могут быть получены из аксиом исчисления в результате применения (возможно, многократного) указанных правил. Запись ├А служит сокращением утверждения «А есть теорема». Если формула А выводима из некоторого множества Г исходных формул (посылок), то запись принимает вид Г ├А.

В качестве «вспомогательного» правила весьма полезной является теорема дедукции, когда какое-нибудь утверждение В доказывают в предположении верности другого утверждения А, после чего заключают, что верно утверждение «если А, то В»:

 

Теорема дедукции. Если Г — множество формул, А  и В—формулы и Г, А├В, то Г├А→В. В частности, если А├В, то ├А→В.

Исходя из синтаксического  представления логики высказываний, последняя зачастую отождествляется с множеством теорем или, что более принято, с отношением выводимости. Итак, при семантическом подходе формулы интерпретируются как функции на множестве из двух элементов {0, 1}, а при синтаксическом — как определенный набор символов, и различаются только теоремы и не теоремы. Однако, несмотря на такое различие, оба подхода к построению логики высказываний, по существу, эквивалентны и, как говорят, являются адекватными. Это значит, что понятия логического следования и понятия вывода эквивалентны. Рассмотрим в связи с этим теорему

Теорема адекватности. Для всякой формулы А, ├А т.т.т., когда ╞ А.

Доказательство в одну сторону, а именно: для всех А, если ├А, то ╞А носит название теоремы о корректности. Это минимальное условие, которое мы требуем от логического исчисления и которое состоит в том, что представленная нами семантика корректна для выбранной аксиоматизации. для доказательства теоремы нужно проверить, что все наши аксиомы (1)— (11) являются тавтологиями, что легко устанавливается непосредственной проверкой с помощью истинностных таблиц. А наши правила вывода выбраны таким образом, что они сохраняют тавтологичность. Поэтому все формулы последовательности, образующей доказательство какой-либо теоремы исчисления С₂ , в том числе и сама доказанная теорема, являются тавтологиями. Из этой теоремы следует важнейшее свойство нашего исчисления высказываний С₂: в С₂ формулы А и ¬А не могут быть одновременно доказуемыми т.е. исчисление высказываний С₂ непротиворечиво. Ели бы это было не так, то используя аксиому (10) и применяя дважды modus ponens, получаем, что в С₂ доказуема любая формула В. В силу этого противоречивая логика высказываний никакой ценности не представляет. В ней истина и ложь неразличимы и поэтому любая теорема одновременно истинна и ложна.