Логическое высказывание

Такие функции называются булевыми функциями (по имени Д. Буля). Например, формула F (а, b, с) = (а Ù b) Þ (с  Ù а) описывает, учитывая определение  входящих в нее связок, булеву функцию, задаваемую следующей таблицей:

а	b	с	F(a, b, с)	а	b	с	F(a, b, с)
и	и	и	и	л	и	и	и
и	и	л	л	л	и	л	и
и	л	и	и	л	л	и	и
и	л	л	и	л	л	л	и

Заметим, что булевых функций  от n аргументов имеется лишь конечное число, а именно столько, сколько  возможно функциональных таблиц. Число  возможных наборов аргументов равно 2n, а каждому набору аргументов можно  независимо друг от друга сопоставлять одно из значений и или л. Таким  образом, число всевозможных булевых  функций от n аргументов равно   – Оно очень быстро растет с ростом n. Изучение свойств булевых функций имеет большее значение как для алгебры и математической логики, так и для их приложений в кибернетике и теории автоматов. Естественно распространить определение высказывательных связок, так как мы их определили выше, на булевы функции. Мы ограничимся рассмотрением лишь связок Ù, Ú, ù называемых булевыми связками (или булевыми операциями). Такое ограничение оправдано тем, что, как легко проверить, связки Þ и Û могут быть выражены через другие булевы связки. При помощи таблиц истинности, приведенных выше, легко проверяются следующие тождества:  

a Þ b º (ù a) Ú b;  

a Û b º (a Ù b) Ú (ù  a Ù ùb), 

которые позволяют повсеместно  заменить связки Þ, Û на Ù, Ú, ù. 

Если мы теперь имеем булевы функции {F (xl, х2, ..., хn), G (х1, х2, ..., хn)} от n переменных, то действие связок над  ними определяется естественным образом:

F (xl, x2, ..., хn) Ù G (х1, x2, ..., хn), F (xl, x2, ...,хn) Ú G (xl, x2, ..., хn), ùF (xl, x2, ..., хn) – это такие булевы функции,  которые принимают значения, предписываемые  соответствующими таблицами для  каждого возможного значения  аргументов. Кратко: булевы операции  так переносятся на булевы  функции, как действия арифметики  переносятся на обычные функции  числовых аргументов. Вообще имеет  место далеко идущая аналогия  между обычной алгеброй чисел  и числовыми функциями, с одной  стороны, и высказываниями и  булевыми функциями – с другой. При этом можно отметить, что в одном определенном смысле алгебра булевых функций проще алгебры числовых функций: если рассматривать лишь функции некоторого конечного числа аргументов, то таких функций лишь конечное число. Поэтому выкладки с булевыми функциями вполне доступны пониманию школьников старших классов. 

Естественно, закономерности булевой алгебры менее привычны и вызывают удивление и недоверие: это судьба всякого новшества.

Выпишем законы булевой алгебры. Большими латинскими буквами А, В, ..., X, Y, Z мы обозначим объекты, над которыми осуществляются булевы операции Ù, Ú, ù. Для определенности будем считать, что эти объекты – булевы функции  некоторого фиксированного числа переменных. Среди них есть два особых элемента: 1, 0. Это соответственно функции, принимающие  для всех аргументов значения 0 и 1 (постоянные функции – нуль и единица). Тогда 

А Ù В = В Ù А,                                                A Ú B = B Ú A

A Ù (В Ù C) = (А Ù  В) Ù C                             A Ú (В Ú C) = (А Ú В) Ú C

A Ù A = A                                                        A Ú A = A

A Ù 1 = A                                                        A Ú 1 = A

A Ù 0 = 0                                                         A Ú 0 = A

ù(A Ù B) = ùA Ú ùB                                          ù(A Ú B) = ùA Ù ùB

A Ù (B Ú C) = (A Ù B) Ú (A Ù C)                   A Ú (B Ù C) = (A Ú B) Ù (A Ú C)

ù ùA = A

Если, как это обычно делают, булевы операции Ú, Ù, ù считать аналогом сложения, умножения и перехода к  противоположному числу, то некоторые  из вышеприведенных законов те же, что для числового сложения и  умножения, другие же существенно отличаются от привычных.

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

Элементарное высказывание (буква) является формулой нулевого уровня. Если элементарное высказывание всегда верно, мы будем его обозначать буквой И, а если оно всегда неверно, - буквой Л. Тогда формулы первого уровня - это элементарные высказывания, к которым применена только одна логическая связка.

Пусть Ф1 и Ф2 - формулы ненулевого уровня. Тогда записи (¬(Ф1)), ((Ф1)&(Ф2)), ((Ф1)V(Ф2)), ((Ф1)->(Ф2)), ((Ф1)~(Ф2)) также являются формулами. Если же одна из формул Ф1 и Ф2 , к которым применяется логическая связка, имеет нулевой уровень, то она в скобки не заключается.

Теперь, зная буквы-элементарные высказывания, мы никогда не ошибёмся, определяя, является ли формулой запись, содержащая эти буквы, скобки и символы  связок, то есть правильно ли построено  сложное высказывание. В процессе подобного опознавания мы выделяем части формулы, то есть более короткие формулы, из которых на каждом этапе  строится более длинная формула  с применением одной связки. Самыми простыми частями формулы являются, разумеется, элементарные высказывания. Значит, логический анализ формулы  сводится к выделению всех её частей.

Пример Пусть элементарными  высказываниями являются А, В, С. Записи

¬ A^BC и (B)V(ВVA->C)

c формальной точки зрения  не являются формулами, так  как мы натыкаемся при их  разборе на нарушение правил  построения формул. А записи

(¬ A)^(BVC) и BV((ВVA)->C)

вполне соответствуют  требованиям построения формулы. В  процессе анализа формулы (¬ A)^(BVC) выделяются следующие её части:

               ( ¬A ) ^ ( BVC )

                      ^

                 ¬A B V C

Построенная нами конструкция  отдалённо напоминает дерево, растущее вверх ногами. «Корень» его - исходная формула, роль «веток» играют логические связки. Там, где имеется разветвление, стоят части формулы. А на концах веток растут «листья» - элементарные высказывания.

Подобные конструкции  часто используются в математике и в программировании, они так  и называются «деревьями».

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

Если опущены внешние  скобки, то они восстанавливаются.

Если рядом стоят две конъюнкции или дизъюнкции (например, ), то в скобки заключается сначала самая левая часть (т.е. две подформулы со связкой между ними). (Говорят также, что эти связки левоассоциативны.)

Если рядом стоят разные связки, то скобки расставляются согласно приоритетам: и → (от высшего к низшему).

Когда говорят о длине  формулы, имеют в виду длину подразумеваемой (восстанавливаемой) формулы, а не сокращённой  записи.

Например: запись означает формулу , а её длина равна 12.

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

Оценка отрицания ¬p задаётся таблицей:

	¬p

Значение двуместных логических связок → (импликация), (дизъюнкция) и (конъюнкция) определются так:

		p→q
0	0	1	0	0
0	1	1	0	1
1	0	0	0	1
1	1	1	1	1

Тождественно  истинные формулы

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

Законы де Моргана:

1) ;

2) ;

Закон контрапозиции:

;

Законы поглощения:

1) ;

2) ;

Законы дистрибутивности:

1) ;

2) .

Одним из возможных вариантов (Гильбертовской) аксиоматизации логики высказываний является следующая система аксиом:

A1:A→(B→A);

A2:((A→(B→C))→((A→B)→(A→C)));

;

;

;

;

;

;

A9:¬A→(A→B);

A10:(A→B)→((A→¬B)→¬A);

.

вместе с единственным правилом:

(Modus ponens)

Теорема корректности исчисления высказываний утверждает, что все  перечисленные выше аксиомы являются тавтологиями, а с помощью правила modus ponens из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода - это так называемая теорема полноты логики высказываний.

1.4. Логика первого и  второго порядка

Логика первого порядка (исчисление предикатов) - формальное исчисление, допускающее высказывания относительно переменных, фиксированных функций, и предикатов. Расширяет логику высказываний. В свою очередь является частным случаем логики высшего порядка.

Язык логики первого порядка строится на основе сигнатуры, состоящей из множества функциональных символов и множества предикатных символов . С каждым функциональным и предикатным символом связана арность, то есть число возможных аргументов. Допускаются как функциональные так и предикатные символы арности 0. Первые иногда выделяют в отдельное множество констант. Кроме того используются следующие дополнительные символы

Символы переменных (обычно x,y,z,x1,y1,z1,x2,y2,z2, и т. д.),

Пропозициональные связки: ,

Кванторы: всеобщности и существования ,

Служебные символы: скобки и  запятая.

Перечисленные символы вместе с символами из и образуют Алфавит логики первого порядка. Более сложные конструкции определяются индуктивно:

Терм есть символ переменной, либо имеет вид , где f - функциональный символ арности n, а - термы.

Атом имеет вид , где p - предикатный символ арности n, а - термы.

Формула - это либо атом, либо одна из следующих конструкций: , где F,F1,F2 - формулы, а x - переменная.

Переменная x называется связанной  в формуле F, если F имеет вид  либо , или же представима в одной из форм , причем x уже связанна в H, F1 и F2. Если x не связанна в F, ее называют свободной в F. Формулу без свободных переменных называют замкнутой формулой, или предложением. Теорией первого порядка называют любое множество предложений.

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

,

,

где A[t / x] - формула, полученная в результате подстановки терма t вместо переменной x в формуле A.

Правил вывода 2:

Modus ponens:

Правило обобщения (GEN):

В классическом случае интерпретация формул логики первого порядка задается на модели первого порядка, которая определяется следующими данными

Несущее множество  ,

Семантическая функция σ, отображающая

каждый n-арный функциональный символ f из в n-арную функцию ,

каждый n-арный предикатный  символ p из в n-арное отношение .

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

Предположим s - функция, отображающая каждую переменную в некоторый элемент из , которую мы будем называть подстановкой. Интерпретация терма t на относительно подстановки s задается индуктивно

, если x - переменная,

В таком же духе определяется отношение истинности формул на относительно s

, тогда и только тогда, когда  ,

, тогда и только тогда, когда  - ложно,

, тогда и только тогда, когда  и истинны,'

, тогда и только тогда, когда  или истинно,

, тогда и только тогда, когда  влечет ,