Представление произвольной двузначной функции посредством

формулы алгебры высказываний. Рассмотрим способ построения

формулы с наперед заданной таблицей истинности. Пусть A — про-

извольная формула алгебры высказываний, содержащая переменные

X1,X1, . . .,Xn. Имеется ровно 2n наборов значений И, Л переменных

X1,X1, . . .,Xn. Каждому набору в таблице истинности соответствует зна-

чение формулы A Иили Л, которое обозначим через f(X1,X1, . . .,Xn).

Тем самым произвольной формулеA сопоставляется двузначная функция

f = f(X1,X1, . . .,Xn) от n аргументов. Значения аргументов и значение

функции содержатся во множестве из двух элементов { И , Л}.

Рассмотрим обратную задачу: пусть задана функция f =

f(X1,X1, . . .,Xn) от n аргументов, где значения аргументов и зна-

чение функции содержатся во множестве { И , Л}. Требуется найти

формулу алгебры высказываний A, которой соответствует данная функ-

ция f. Другими словами у нас заполнены значения таблицы истинности,

а требуется подобрать формулу с данной таблицей.

Итак, имеем заданные значения

f(И,И, . . . ,И), f(И,И, . . . ,Л), . . . , f(Л,Л, . . . ,Л) (4)

Укажем способ построения формулы A, принимающую данные, напе-

ред указанные, значения. Он состоит из 3 шагов.

1. Рассмотрим любой из 2n наборов аргументов для функции f, на-

пример, набор И,И, . . . ,Л. Сопоставим набору элементарную конъ-

юнкцию переменных X1,X2, . . .,Xn или их отрицаний. Если пере-

менная Xi в наборе (4) имела значение И, то переменную Xi в эле-

ментарную конъюнкцию помещаем без отрицанию, иначе—с отри-

цанием. Затем присоединяем к элементарной конъюнкции с помо-

щью знака ∧ коэффициент – значение функции от данного набо-

ра, т.е. одно из значений f(И,И, . . . ,И), . . . , f(Л,Л, . . . ,Л). Полу-

чаем 2n членов. В частности, для набора И,И, . . . ,Л получаем член

f(И,И, . . . ,Л)∧X1 ∧ X2 ∧ . . .∧ ￢Xn.

2. Соединяем полученные члены знаком дизъюнкции.

3. Отбрасываем члены, имеющие коэффициент Л, у членов, имеющих

коэффициент Иотбр асываем только сам коэффициент. Получаем

формулу A.

Нетрудно проверить, что формула A принимает требуемые значения.

Пример. Построить формулу A, содержащую буквы X, Y,Z, и

принимающую следующие значения: A(И,И,И)=И, А(И,И,Л)=И,

А(Л,Л,Л)=И. Остальные значения формулы A равны Л.

Ответ A = (X ∧ Y ∧ Z) ∨ (X ∧ Y ∧ ￢Z) ∨ (￢X ∧￢Y ∧ ￢Z).

Совершенная конъюнктивная и совершенная дизъюнктивная

нормальные формы

Пусть F = F1 ∨ F2 ∨ . . .Fk — дизъюнктивная нормальная форма

для формулы A, содержащая переменные X1,X2, . . .,Xn. Однозначна ли

нормальная форма F? Нетрудно привести пример двух различных дизъ-

юнктивных (и конъюнктивных ) нормальных форм для данной формулы

A. Желательно иметь некоторую однозначность в выборе нормальных

форм. Пусть

F = F1 ∨ F2 ∨ . . .Fk (5)

дизъюнктивная нормальная форма для формулы A, являющаяся дизъ-

юнкцией элементарных конъюнкций F1, F2, . . ., Fk.

Дизъюнктивная нормальная форма F называется совершенной, если

выполнены следующие условия.

1. В форме F нет двух одинаковых элементарных конъюнкций

F1, F2, . . ., Fk.

2. Пусть Xi, ( i = 1, 2, . . ., n) — произвольная переменная и Fj (j =

1, 2, . . ., k)—элементарная конъюнкция из формы F. Тогда имеется

ровно одно вхождение переменной Xi или отрицания ￢Xi в элемен-

тарную конъюнкцию Fj .

Пусть

F = F1 ∧ F2 ∧ . . .Fk (6)

конъюнктивная нормальная форма для формулы A, являющаяся конъ-

юнкцией элементарных дизъюнкций F1, F2, . . ., Fk.

Конъюнктивная нормальная форма F называется совершенной, если

выполнены следующие условия.

1. В форме F нет двух одинаковых элементарных дизъюнкций

F1, F2, . . ., Fk.

2. Пусть Xi (i = 1, 2, . . ., n) — произвольная переменная и

Fj (j = 1, 2, . . . , k)— элементарная дизъюнкции из формы F. Тогда

имеется ровно одно вхождение переменной Xi или отрицания ￢Xi в

элементарную дизъюнкцию Fj .

ТЕОРЕМА 6 Пусть A – произвольная не тождественно истин-

ная формула. Тогда A имеет однозначно определенную совершен-

ную конъюнктивную нормальную форму.

Доказательство. Вычислим таблицу истинности для формулы A. По

предыдущему пункту построим формулу F = F1 ∧ F2 ∧ . . .Fk с задан-

ной таблицой истинности. При этом члены F1 ∧F2 ∧. . .Fk удовлетворяют

двум условиям из определения совершенной конъюнктивной нормальной

формы. Поэтому F —требуемая нормальная форма.

Пусть F_ произвольная совершенная конъюнктивная нормальная

форма. Нетрудно проверить, что форма F_ содержит в точности те чле-

ны F1, F2, . . ., Fk, которые соответствуют наборам, при которых значение

формулы A равно И.Отсюда члены F1, F2, . . ., Fk определены однозначно

с точностью до порядка. Теорема доказана.

ТЕОРЕМА 7 Пусть A – произвольная не тождественно ложная

формула. Тогда A имеет однозначно определенную совершенную

дизъюнктивную нормальную форму.

Доказательство самостоятельно.

Лекция 4. Построение исчисления высказываний в виде

формальной системы

В предыдущей лекции рассматривались тождественно истинные фор-

мулы. Если перед нами конкретная формула, то вычисляя таблицу ис-

тинности или КНФ формулы, мы можем определить, будет ли она тож-

дественно истинной. Такие методы позволяют провести проверку на тож-

дественную истинность конкретной формулы, но не дают представления

об общем устройстве, обозрении всех тождественно истинных формул.

Исчисление высказываний — раздел математической логики, изучаю-

щий построение всех тождественно истинных формул. В этом разделе мы

получим более глубокое понимание природы таких формул. Исчисление

высказываний будет построено в виде формальной системы. Понятие

формальной системы необходимо не только в исчисление высказываний.

В дальнейшем и другой раздел математической логики «Теории первого

порядка» будет построен в виде формальной системы. Формальная си-

стема отражает синтаксические аспекты математической теории, т.е. ее

символы, формулы, аксиомы, правила вывода. Приведем точные опреде-

ления трех составных частей формальной системы.

Первая часть формальной системы — ее язык. Чтобы определить

язык формальной системы нужно задать символы этого языка и его фор-

мулы. Если сравнить язык формальной системы с русским языком, то по-

лучим аналогию символов и формул с буквами и словами в русском язы-

ке.

Однако символы формальной системы могут быть произвольными

знаками, например, знаками &, ∗,+. Единственное требование — неде-

лимость символа (символ не имеет частей, из которых составлен) и воз-

можность его распознания в один прием.

Последовательность символов языка называется выражением это-

го языка. Число символов в выражении – длина выражения. Аналогия

в естественном языке: слово насос имеет длину 5. Одно выражение мо-

жет входить в другое. Например, выражение ма имеет два вхождения в

выражение математика. Замена первого вхождения ма на выражение

на выражение на дает выражение натематика.

Не все выражения в естественном языке являются осмысленными

словами. Точно также в формальной системе лишь часть выражений счи-

тается формулами. В каждой формальной системе свои правила обра-

зования формул. Как уже отмечалось, язык формальной системы задан

если определены символы этого языка и его формулы.

Вторая часть формальной системы—аксиомы. Задать аксиомы озна-

чает выделить некоторые формулы формальной системы, присвоив им

название аксиомы.

Третья часть формальной системы — правила вывода. Они имеют

вид

A1, A2, . . ., An

B

, (7)

где A1, A2, . . ., An и B – формулы формальной теории. При этом формулы

A1, A2, . . ., An называются посылками правила вывода, а B его заключе-

нием.

Правила указывают способ для получения теорем. Вначале все аксио-

мы объявляются теоремами. Из этого начального списка теорем получа-

ются новые теоремы с помощью правил вывода. Если уже установлено,

что A1, A2, . . ., An – теоремы и имеется правило вывода (7) с посылками

A1, A2, . . ., An, то его заключение добавляется в список теорем. Тем са-

мым получаем следующее определение теоремы формальной системы.

1. Любая аксиома формальной системы F является ее теоремой.

2. Если A1, A2, . . ., An – теоремы и A1,A2,...

B – правило вывода, то B –

теорема.

3. То, что формула A является теоремой устанавливается несколькими

применениями правил 1 и 2.

Тоже самое можно выразить иначе. Считаем аксиомы теоремами ша-

га 1. Обозначим множество теорем шага 1 через F1. Назовем теоремами

шага m все теоремы шага m − 1 и все заключения правил вывода (7), где

A1, A2, . . ., An теоремы шага m − 1. Рассмотрим F = F1 ∪ F2 ∪ F3 ∪ . . ..

Формула A—теорема тогда и только тогда, когда A ∈ F. Любая теорема

имеет наименьший номер шага n, на котором она получена. Мы можем

доказывать различные утверждения для теорем индукцией по числу n.

Построение исчисления высказываний. Рассмотрим исчисление

высказываний как формальную систему, построенную в 3 шага.

Шаг 1. Определим язык исчисления высказываний. Для этого зада-

дим символы и формулы. Символами исчисления высказываний являют-

ся.

1. Латинские буквы a, b, . . . , z, A, B . . ., Z и буквы с индексами, штри-

хами и т.п.

2. Символы ￢ и ∨.

Формулы определяются следующим образом.

1. Буквы является формулами.

2. Если U и V – формулы, то ￢U и ∨UV – формулы.

3. То, что выражение A является формулой, устанавливается несколь-

кими применениями правил 1) и 2).

Это определение можно сформулировать иначе. Буквы считаем фор-

мулами шага 1. Назовем формулами шага n все формулы шага n − 1 и

формулы ￢U и ∨UV , где U и V формулы шага n − 1. Пусть Fi —множе-

ство формул шага i и F = F1 ∪F2 ∪. . .. Выражение A является формулой

тогда и только тогда, когда A ∈ F. Мы можем доказывать различные

утверждения для формул индукцией по наименьшему шагу n, на котором

получена формула.

Шаг 2. Зададим аксиомы исчисления высказываний.

Мы рассмотрим всего лишь один вид аксиомы – пропозициональные

аксиомы. Они имеют вид

￢A ∨ A, (8)

где A – произвольная формула.

Шаг 3. Зададим 4 правила вывода исчисления высказываний. Они

имеют следующий вид, где A, B, C – произвольные формулы.

Правило расширения

A

B ∨ A

(9)

Правило сокращения

A ∨ A

A

(10)

Правило ассоциативности

A ∨ (B ∨ C)

(A ∨ B) ∨ C

(11)

Правило сечения.

A ∨ B, ￢A ∨ C

B ∨ C

(12)

В исчислении высказываний обычно вместо слова «теорема» употреб-

ляется слова «выводимая формула». То, что формула A является выво-

димой формулой, записывается в виде

_ A

Приведем некоторые пояснения к приведенным определениям. Вместо

привычной записи U∨V использовалась запись ∨UV .Хотя в дальнейшем

мы применяем запись U ∨ V , но всегда подразумеваем вместо нее запись

∨UV . При определении формулы не использовались скобки.Оказывает-

ся, что мы сможем обойтись без употребления скобок. Для наглядности

мы будем использовались скобки, например, записывать (A∨B). Однако

под этой записью понимаем A ∨ B.

Запись F = A1 ∨ A2 ∨ . . . ∨ An подразумевает правостороннюю рас-

становку скобок, а именно, сборку формулы F в виде F = A1 ∨ (A2 ∨

. . . (An−1 ∨ An)).

При определении формулы мы не использовали также знаки ∧,→,↔.

Определяемые символы . В математике и других дисциплинах посто-

янно встречаются символы, которые служат для обозначения некоторой

последовательности символов. Это определяемые символы. Обозревая

формулу с определяемыми символами мы должны представить ее как

формулу с исходными символами, которая получена заменой определя-

емых символов на то, что они изображают. Введем следующие определя-

емые символы

→, ∧, ↔

• A → B является обозначением для ￢A ∨ B,

• A ∧ B является обозначением для ￢(￢A∨ ￢B),

• A ↔ B является обозначением для (A → B) ∧ (B → A).

Отметим еще раз, что обозревая формулу с определяемыми символами

мы должны представить на ее месте формулу с исходными символами.

Например, длина формулы A → B равна 4, так как в нее входит 4 символа

￢, A, ∨, B, а не 3 символа A, →, B.

22