Матлогика(Лагодинский)

кращенная ДНФ может содержать лишние импликанты, удаление которых не меняет таблицы истинности. Если их удалить, получается ДНФ, которая называется тупиковой. Тупиковая ДНФ, содержащая наименьшее число вхождений переменных, называется

минимальной ДНФ (МДНФ).

Для получения сокращенной ДНФ используются две операции: 1) неполное склеивание AÙxÚ AÙxº AÙ(xÚx) Ú AÙxÚ AÙx; 2) элементарное поглощение AÙxσ Ú Aº AÙ(xσ Ú1) º A, σÎ{0,1}. Например, рассмотрим функцию с приведенной ранее таблицей истинности (знаки конъюнкции опускаем, как это обычно и дела-

ется):

f =xyzÚxyzÚxyzÚxyzº

ºxz(yÚy) Úyz(xÚx) Úxy(zÚz) ÚxyzÚxyzÚxyzÚxyzº

ºxzÚyzÚxyÚxyzÚxyzÚxyzÚxyzº

ºxz(1Úy) Úyz(1Úx) Úxy(1Úz) Úxyzº

ºxzÚyz(1Úx) ÚxyºxzÚyzÚxy.

Таким образом, импликантами этой формулы являются конъюнкты: xyz, xyz, xyz, xyz,xz, yz, xy, причем лишь три последних импликанты являются простыми. Сокращенная ДНФ имеет вид: f =xzÚyzÚxy. Для получения минимальной ДНФ из сокращенной используем матрицу Квайна:

xyz xyz xyz xyz

xy – * * –

xz * – * –

yz – * – *

В тупиковую ДНФ выбирается минимальное число простых импликант, дизъюнкция которых сохраняет таблицу истинности функции, т. е. каждый столбец матрицы Квайна содержит по крайней мере одну звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импликант. Затем из тупиковой ДНФ выбирается минимальная ДНФ. В нашем случае тупиковая ДНФ равна xzÚyz, она же будет равна МДНФ.

21

Полиномы Жегалкина

Существует и другой, отличный от СДНФ и СКНФ стандартный способ представления логических функций. Любая логическая функция (в том числе тождественно ложная и тождественно истинная функции) может быть представлена в виде полинома Жегалкина:

где коэффициенты ai1i2 ik имеют значения 0 или 1. Для примера снова рассмотрим функцию

f =xyzÚxyzÚxyzÚxyz.

Поскольку AÅBº( AÚB) \ ( AÙB) и конъюнкция любых двух конъюнктов, входящих в f равна нулю, знаки дизъюнкции в выражении функции f можно заменить на :

f =xyzÅxyzÅxyzÅxyz.

Кроме того, воспользуемся тем, что aºaÅ1:

f=xy(zÅ1) Åx(yÅ1)zÅx(yÅ1)(zÅ1) Å(xÅ1)(yÅ1)zº

ºxyzÅxyÅxyzÅxzÅxyzÅxyÅxzÅxÅxyzÅxzÅyzÅz.

Поскольку a a≡0, окончательно получаем: f=xz yz x z.

Заметим, что xzÅyzÅxÅzºxzÚyz.

Полные системы функций и базисы

Как уже говорилось, логические функции можно определять с помощью суперпозиций: подставив в функцию f(x,y) вместо x функцию g(x,y), а вместо y функцию h(x,y), получим, вообще говоря, новую функцию F(x,y)=f(g(x,y), h(x,y)). Такой набор логических функций {f, g, h, …}, что с помощью суперпозиций функций из этого набора можно получить любую логическую функцию, называется полной системой функций. Очевидно, такие системы существуют, например, система всех логических функций. Однако поскольку любую логическую функцию можно представить либо в виде СДНФ, либо в виде СКНФ, либо и в том, и в другом виде, полной системой функций является уже набор из трех функций: отрицание, конъюнкция и дизъюнкция. Поскольку любую функцию

22

можно представить в виде полинома Жегалкина, полной системой функций является набор из сложения по модулю 2, конъюнкции и единицы. Но конъюнкцию можно представить в виде суперпози-

ции отрицания и дизъюнкции: xÙyºxÚy, а дизъюнкцию – в виде

суперпозиции отрицания и конъюнкции: xÚyºxÙy. Поэтому наборы из отрицания и конъюнкции и отрицания и дизъюнкции – тоже полные системы функций. Но если из любого из этих наборов исключить хотя бы одну функцию, этот набор перестанет быть полной системой функций – эти полные системы функций являются минимальными, т. е. базисами.Базисами являются еще два набора, каждый из которых состоит только из одной функции. Это базис

Пирса, включающий лишь стрелку Пирса ( x¯xºxÚxºx ) и базис

Шеффера, включающий только штрих Шеффера ( x| xºxÙxºx ). На множестве логических функций выделяют функционально замкнутые классы функций, (замкнутые относительно суперпозиций, классы Поста): если функции f, g, h, … принадлежат к одному классу Поста, то и любая их суперпозиция принадлежит этому

классу Поста. Этих классов пять. Рассмотрим эти классы.

1. P0 – класс функций, сохраняющих ноль, т. е. если

f(x1,x2, ,xn) ÎP0, то f(0, 0, …, 0)=0. Очевидно, к этому классу принадлежат тождественный нуль, f(x)=x, конъюнкция, дизъюнкция, вычитание и сложение по модулю 2, но не принадлежат тождественная единица, отрицание, импликация, стрелка Пирса, штрих Шеффера и эквиваленция.

2. P1 – класс функций, сохраняющих единицу, т. е. если

f(x1,x2, ,xn) ÎP1, то f(1, 1, …, 1)=1. Очевидно, к этому классу принадлежат тождественная единица, f(x) ºx, конъюнкция, дизъюнкция, импликация и эквиваленция, но не принадлежат тождественный нуль, отрицание, вычитание, стрелка Пирса, штрих Шеффера и сложение по модулю 2.

4. L – класс линейных функций, т. е. если f(x1,x2, ,xn) ÎL, то

f(x1,x2, ,xn) =a0 Åa1x1 Åa2x2 Å Åanxn, где a1, a2,..., an – коэф-

фициенты, каждый из которых равен либо 0, либо 1. Очевидно, к этому классу принадлежат тождественная единица, тождественный нуль, f(x)≡x, f(x) ºx и не принадлежат все остальные функции.

23

5. M – класс монотонных функций. Для определения этого класса надо ввести отношение частичного порядка на множестве наборов значений переменных. Для двух наборов s1={a1, a2,..., an}, s2={b1, b2,..., bn} выполнено отношение предшествования s1 s2,

если ai≤bi, i=1,2,...,n. Функция f(s) ÎM, если s1 s2 ®f(s1) £f(s2). Очевидно, к этому классу принадлежат тождественные нуль и еди-

ница, функция f(x)≡x, конъюнкция и дизъюнкция и не принадлежат все остальные функции.

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

Теорема Поста. Для того чтобы набор функций был полной системой функций, необходимо и достаточно, чтобы он не содержался целиком ни в одном из классов Поста.

Секвенции

Отношение равносильности, введенное на множестве формул алгебры логики, является отношением эквивалентности. Это отношение делит множество всех возможных высказываний на классы эквивалентности: высказывания, относящиеся к одному классу, утверждают, в сущности, одно и то же, хотя, возможно, другими словами. Но в рассуждениях часто устанавливается, что из одного высказывания логически следует другое, причем из второго высказывания первое может и не следовать. Например, из высказывания ‘‘Число N делится на 6’’ следует высказывание ‘‘Число N делится на 3’’, но не наоборот. Отношение логического следования является отношением частичного порядка. Пусть Γ={A1, A2,..., An} – набор формул, B – формула. Выражение Γ|=B называется секвенцией. Секвенция называется истинной, если на всех наборах значений переменных, на которых истинна каждая из формул набора Γ, истинна и формула B. Если набор Γ пуст, и секвенция имеет вид |=B, она называется тавтологией. Такая секвенция истинна в том и только том случае, если B – тождественно истинная формула. Наоборот, выражение Γ|= указывает на то, что набор формул Γпротиворечив.

Иначе говоря, секвенция Γ|=B означает, что из истинности высказываний A1, A2,..., An (в совокупности) следует истинность высказывания B (набор Γ={A1, A2,..., An} и формула B связаны отношением следования). Необходимо специально рассмотреть случай, когда не существует таких наборов значений переменных, при которых каждое из высказываний A1, A2,..., An истинно. В этом случае секвенция Γ|=B истинна при любом B. Здесь полная аналогия с

24

импликацией. Конечно, истинность такой секвенции не доказывает истинность B.

Свойства знака следования |=. Пусть Γ={A1,..., An} – список формул, B1,..., Bk, C – формулы.

1. A1,..., An|= Ai при i=1,..., n (элементарные следствия). 2. Если Γ|= C, то Γ, B1,..., Bk|= C (добавление допущений). 3. Если Γ|= Bi при i=1,..., k и B1,..., Bk|= C, то Γ|= C (доказатель-

ство с помощью лемм) [3].

Для доказательства истинности секвенций можно использовать табличный метод. Докажем, например, истинность секвенции (aÙb) ®b, bÚ(aÙc) |=(a®b) Ú(aÙc). При этом удобнее будет обозначать отрицание знаком Ø. Кроме того, значения переменных будем записывать под самими переменными, а значения функций под знаками функций. Строчки, соответствующие тем наборам переменных, при которых каждая из формул набора в левой части принимает значение 1, будем подчеркивать:

Видно, что в пересечениях подчеркнутых строк с выделенными столбцами везде стоят единицы. Следовательно, секвенция доказана.

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

25

Правила преобразования списков допущений

Пусть Γ, Γ1, Γ2 – списки формул, A, B, C – формулы и Γ|=C. Следующие списки допущений равносильны:

1) Γ1, A, B, Γ2 и Γ1, B, A, Γ2 (правило перестановки), 2) Γ1, A, A, Γ2 и Γ1, A, Γ2 (правило сокращения),

3) Γ1, A,B,Γ2и Γ1, AÙB (правила объединения и расщепления).

Пример. Доказательство тавтологии |=( A ® B) ~ (B® A) с помощью свойств символа следования, правил введения и удаления знаков логических операций и правил преобразования списков допущений.

Метод резолюций

Для доказательства тавтологий существует метод, называемый методом резолюций. Этот метод основан на истинности двух секвенций 1) A, AÚB|= B и 2) AÚB, AÚC|= BÚC. Докажем пер-

26

вую секвенцию. Эта секвенция истинна, если при всех наборов значений переменных, при которых истинна каждая из формул A и AÚB, истинна и формула B. Но если истинна формула A, то формула A ложна, поэтому, если истинны и A, и AÚB, то истинна формула B. Доказательство второй секвенции: среди наборов значений переменных есть такие, при которых формула A истинна, и такие, при которых она ложна. Других нет, поскольку AÚ Aº1. Но при тех наборах значений переменных, при которых формула A истинна, формула A B истинна при любых B, а формула AÚC истинна, только если истинна формула C. Наоборот, при тех наборах значений переменных, при которых формула A ложна, формула AÚC обязательно истинна, а формула A B истинна только, если истинна B. Таким образом, из истинности обеих этих формул следует, что хотя бы одна из формул B или C истинна. Эти секвенции и называют резолюциями.

Рассмотрим метод резолюций на примере доказательства следующей тавтологии:

|=( A® B) Ù(C® D) ®( AÚC® BÚD).

Тавтология будет доказана, если доказать тождественную ложность противоположного высказывания:

( A ® B) Ù(C® D) ®( AÚC® BÚD) |=

Сначала мы преобразуем формулу в левой части, чтобы получить ее КНФ:

( A® B) Ù(C® D) ®( AÚC® BÚD) º

º( A® B) Ù(C® D) Ú( AÚC® BÚD) º

º( A® B) Ù(C® D) Ù AÚCÚBÚDº

º( AÚB) Ù(CÚD) Ù( AÚC) ÙBÙD.

При этих преобразованиях использовались законы де Моргана, снятие двойного отрицания и равносильность a®bºaÚb. В результате получилась КНФ формулы в левой части. Для доказательства тождественной ложности этой формулы достаточно доказать противоречивость списка допущений:

1)  AÚB; 2) CÚD; 3)  AÚC; 4)  B; 5)  D (формулы нумеруем для удобства ссылок), т. е. наличие в нем взаимно противоположных высказываний.

27

Рассмотрев этот список, видим, что в нем нет очевидных противоречий.Однакоиспользуярезолюциюпервоготипа,получаем,что из формул AÚB и B следует формула A. Это записываем в виде:

resB( AÚB,B) = A.

Добавляем формулу A в список допущений:

1)  AÚB, 2) CÚD, 3)  AÚC, 4)  B, 5)  D, 6)  A.

Обозреваем этот список, и в нем не обнаруживаем очевидных противоречий. Снова используем резолюцию первого типа и получаем, что из формул AÚC и A следует формула C. Записываем:

resA( AÚC, A) =C.

Добавляем и эту формулу в список допущений:

1)  AÚB, 2) CÚD, 3)  AÚC, 4)  B, 5)  D, 6)  A, 7) C.

Явных противоречий в этом списке также нет, поэтому опять применяем резолюцию первого типа, на этот раз к формулам CÚD и C, из которой следует, что

resC(CÚD,C) = D.

Пополнив список допущений последней формулой, получим:

1)  AÚB, 2) CÚD, 3)  AÚC, 4)  B, 5)  D, 6)  A, 7) C, 8)  D.

Теперь очевидно, что список допущений противоречив – противоречат друг другу допущения 5) и 8). Тавтология доказана.

3. Исчисления высказываний

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

1) явная формулировка аксиом теории; 2) явная формулировка правил вывода, используемых для по-

следовательного построения теории; 3) использование искусственно построенного формального язы-

ка для изложения всех утверждений теории.

28

Вэтом разделе рассматриваются аксиоматические логические теории, называемые исчислениями высказываний. Значение этих теорий состоит в том, что они являются простейшими моделями аксиоматических теорий и позволяют изучить и сформулировать свойства и правила построения аксиоматических теорий.

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

Множество символов (‘‘абстрактных букв’’), используемых в те-

ории, называется ее алфавитом. Алфавит исчисления высказываний σ состоит из объединения четырех множеств: σ=σ1 σ2 σ3 σ4,

где σ1={a, b,..., z, A1, B2,..., Zn} σ2={ , , →, ¬}, σ3={(,),,}, σ4={|–}.

Других символов алфавит исчисления высказываний не содержит.

Буквы множества σ1 называются пропозициональнымипеременны-

ми. Символ |– называется символом следования. Конечный ряд написанных друг за другом букв называется словом в этом алфавите.

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

та, удовлетворяющее следующим условиям: 1) пропозициональная переменная является формулой, которая

называется элементарной, или атомарной.

2) если A и B – формулы, то ( AÙB),( AÚB),( A® B) и A – тоже формулы.

Никаких других формул нет, поэтому слово ( AÚB) ÙC – не формула, так как не имеет внешних скобок, однако принято внешние скобки опускать, и тогда ( AÚB) ÙC – тоже формула.

Различных исчислений высказываний существует много. Все они делятся на два типа: исчисления гильбертовского типа (по имени крупнейшего немецкого математика конца девятнадцатого – начала двадцатого века Д. Гильберта) и исчисления генценовского типа (по имени немецкого математика и логика первой половины двадцатого века Г. Генцена). В исчислениях гильбертовского типа много аксиом и мало (основных) правил вывода, а в исчислениях генценовского типа – наоборот.

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

I.A1. A®(B® A);

A2. ( A®(B®C)) ®(( A® B) ®( A®C));

II. A3. AÙB® A;

29

A11. A® A.

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

Выводом формулы B из набора формул Γ={A1, A2,..., An} в исчислении высказываний ИВ называется конечная последовательность формул B1, B2,..., Bm, такая, что каждая из формул последовательности либо есть одна из формул набора Γ, либо аксиома, либо получается из предыдущих с помощью правил вывода, а последней является формула Bm=B. Если такой вывод существует, это записывается в виде секвенции: Γ|–B. Формула B в этом случае называется выводимой из набора Γ. Если набор Γ пуст, такая секвенция записывается в виде |–B, и формула B называется доказуемой или теоремой. Тогда вывод обычно называют доказательством теоремы.

Основное правило вывода в ИВ всего одно: правило простого заключения: если в выводе есть формулы A и A→C, то в вывод можно добавить формулу C. Аналогичное правило известно с древности, его латинское название ‘‘modus ponens’’ (сокращенно MP).

В качестве примера рассмотрим доказательство теоремы |–F→F. 1) (F→((F→F)→F))→((F→(F→F))→(F→F));

2) F→((F→F)→F); 3) (F→(F→F))→(F→F); 4) F→(F→F);

5) F→F.

Формула 1) представляет собой схему A2, в которой вместо A подставлено F, вместо B – формула F→F, вместо C – формула F. Формула 2) представляет собой схему A1 с той же подстановкой. Формула 3) получена из формул 1) и 2) по правилу MP. Формула 4) получена из схемы 1 подстановкой формулы F вместо A и B. Формула 5) получена по правилу MP из формул 4) и 3).

30