Математическая логика. Логика алгебры высказываний

Математическая логика. Логика алгебры высказываний

Введение

Согласно одному из самых распространенных определений, логика есть анализ методов рассуждений. Если предметом анализа являются математические рассуждения, то это математическая логика. Главная ее цель - дать точное и адекватное определение понятию доказательства. Применение методов математической логики делает шаг к машинному доказательству теории и созданию искусственного интеллекта. Еще в 30-х годах нашего столетия логика казалась наиболее абстрактной и далекой от практических приложений дисциплиной. Сейчас положение коренным образом изменилось. Из идей математической логики возникла теория булевых функций, являющаяся теоретической базой современных ЭВМ, возникло понятие алгоритма, что позволило решать многие неразрешимые проблемы. Именно через математическую логику и теорию алгоритмов происходит сейчас проникновение математических методов в биологию, лингвистику, экономику, вплоть до философии естествознания.

Математическая логика

Логика алгебры высказываний

Логические операции

Под высказыванием будем понимать величину, которая может принимать два значения: “истина” и “ложь”. Например, высказывание “клин – дерево” истинно, а 3>5 – ложно.

Будем обозначать высказывания большими латинскими буквами A, B, ..., а их значения, т. е. истину и ложь буквами И и Л.

Рассматривания высказывания как величины, принимающие значения И, Л, можно определить над ними операции, которые позволяют из одних высказываний получать новые.

Пусть даны два произвольных высказывания A и B.

1. Конъюнкцией называется высказывание A L B = A & B, которое истинно тогда и только тогда, когда A и B истинны.

2. Дизъюнкцией называется высказывание A V B, которое истинно тогда и только тогда, когда истинно хотя бы одно из высказываний A или B.

3. Импликация A ® B ложна тогда и только тогда, когда A – истина, а B – ложь. При этом А называется посылкой, а В – следствием.

4. Эвиваленция А ~ В истинна тогда и только тогда, когда и А, и В либо оба истинны, либо оба ложны.

Отрицание ( инверсия ) истинна тогда и только тогда, когда А ложно.

Пусть X, Y, Z, ... – произвольные высказывания, т. е. величины, принимающие значения И и Л. Всякое сложное высказывание, составленное из них с помощью операций алгебры высказываний (1-5) называется формулой алгебры высказываний.

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

X ® ( Y V Z ), , X V ( Y L Z ).

Исходные значения могут быть постоянными, т. е. иметь определенные значения И или Л. В этом случае можно определить и значение формулы. Например, если X = И, Y = И, Z = Л, то

X ® ( Y V Z ) – истина, – ложь, X V ( Y L Z ) – истина.

Но высказывания X, Y, Z, ... можно рассматривать также как некоторые переменные, принимающие значения из множества {И, Л}. В этом случае каждая формула определяет некоторую логическую функцию с аргументами X, Y, Z, ... . В первом случае мы имеем постоянные элементарные высказывания, например X = И, Y = И, Z = Л, а во втором – переменные элементарные высказывания.

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

Приведем таблицы истинности простейших функций:

X	Y	X L Y	X V Y	X ® Y	X ~ Y
Л	Л	Л	Л	И	И	И
Л	И	Л	И	И	Л	И
И	Л	Л	И	Л	Л	Л
И	И	И	И	И	И	Л

Равносильность формул

Пусть V и W – две формулы, содержащие переменные x1, ..., xn. Эти формулы будем называть равносильными ( обозначим V » W ), если они принимают одинаковые значения при любых значениях переменных x1,..., xn. Очевидно, что такие формулы имеют совпадающие таблицы истинности.

Например:

Свойства логических операций L, V задаются следующей совокупностью равносильностей:

1. Коммутативность:

2. Ассоциативность:

3. Дистрибутивность:

– I дистрибутивный закон;

– II дистрибутивный закон.

4. Идемпотентность:

5. Теоремы Де Моргана:

6. Инволюция:

7. Свойство нуля:

.

8. Свойство единицы:

Все эти утверждения доказываются на основе определения операций или с помощью таблиц истинности. Запись формул можно упростить, опуская скобки. При этом принят следующий порядок действий: L, V, а затем ~ и ®.

Логические операции L, V, ~, ®, – не являются независимыми друг от друга. Одни из них выражаются через другие.

Запишем основные равносильности, используемые при упрощении формул:

;

.

Закон двойственности

Будем говорить, что операция L двойственна операции V и наоборот.

Если рассматривать только формулы, выражающиеся через операции L, V, –, то формулы W и W* двойственны, если одна получается из другой заменой каждой операции на двойственную.

Например,

двойственна .

двойственна .

Отношение двойственности взаимно: если формула W двойственна W*, то W* двойственна W.

Теорема

Если двойственны, то .

Из этой теоремы следует закон двойственности

Если формулы и равносильны, то равносильны и двойственные им формулы.

Проблема разрешения

Будем называть формулу тождественно истинной, если она принимает значение И при всех значениях входящих в нее переменных высказываний . Формула называется тождественно ложной, невыполнимой, если она принимает значение Л при всех значениях переменных . Формула называется выполнимой, если она не является тождественно ложной.

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

Назовем элементарным произведением (элементарной суммой) произведение (сумму) переменных и их отрицаний.

Теорема

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

Теорема

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

Формула, равносильная данной формуле и представляющая собой сумму элементарных произведений, называется дизъюнктивной нормальной формой (ДНФ) данной формулы.

Любую формулу можно выразить через операции L, V, – , причем знак отрицания относится только к элементарным высказываниям. С этими формулами можно производить такие же преобразования, что и с алгебраическими выражениями. В частности, можно перемножить скобки и представить формулу в виде суммы элементарных произведений, т. е. в виде ДНФ. Это означает, что для любой формулы существует ДНФ.

Конъюнктивной нормальной формой данной формулы (КНФ) называется равносильная ей формула, представляющая собой произведение элементарных сумм.

Пример

Определить ДНФ и КНФ для формулы

.

Исключим операцию ~, пользуясь выражением

.

Получаем

–ДНФ.

Для получения КНФ берем промежуточный результат:

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

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

В силу симметричности операций L, V можно однозначно показать критерий тождественной ложности.

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

Пример

Выяснить, является ли тождественно истинной формула

Приведем эту формулу к КНФ. Используем второй дистрибутивный закон:

.

Получаем:

Так как КНФ содержит множитель , не содержащий переменной с ее отрицанием, то данная формула не является тождественно истинной, т. к. сама формула имеет вид ДНФ причем ее слагаемые не содержат переменной вместе с ее отрицанием, то формула не является и тождественно ложной. Следовательно, она выполнима.

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

Пусть – произвольная функция n переменных, причем и область определения и область значений функции есть 2-элементное множество .

Теорема

Любую двузначную функцию можно представить в виде следующей формулы алгебры высказываний:

( * )

Для любой функции можно построить равносильную ей формулу в виде произведения. Действительно, представим в виде суммы функцию , используя (*):

Возьмем отрицание правой части и, используя формулы Де Моргана, получим:

(**)

Это представление есть произведение из сумм.

Оба выражения (*), (**) можно упростить, если заменить выражения функции их значениями в виде И или Л.

Если не является тождественно ложной, то из (*) мы получим сумму элементарных произведений, т. е. ДНФ, не содержащую ложных слагаемых. Если не является тождественно истинной, то подставив в (**) значения функции и удалив из произведения истинные множители, мы получим КНФ. Это представление будет двойственным первому.

Пример

Пусть принимает значение И, если все переменные принимают одинаковые значения и Л во всех остальных случаях.

x1	x2	x3	F
Л	Л	Л	И
Л	Л	И	Л
Л	И	Л	Л
Л	И	И	Л
И	Л	Л	Л
И	Л	И	Л
И	И	Л	Л
И	И	И	И

Тогда в соответствии с (*)

Получим ДНФ. Запишем теперь КНФ, используя (**):

Замечание.

Представление в виде ДНФ и КНФ, полученные на основе выражений (*) и (**), определяются однозначно. При этом, если не является тождественно ложной, то ее представление в виде ДНФ имеет вид:

а если не является тождественно истинной, то ее КНФ:

Здесь есть либо , либо ().

Совершенные нормальные формы

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

Таким образом, из множества ДНФ функции мы можем выбрать одну, которая единственным образом определяется для данной функции. Эту ДНФ будем называть совершенной (СДНФ).

СДНФ обладает следующими свойствами:

а) в ней нет двух одинаковых слагаемых;

б) ни одно слагаемое не содержит двух одинаковых множителей;

в) ни одно слагаемое не содержит переменной вместе с ее отрицанием;

г) в каждом слагаемом содержится либо переменная , либо ее отрицание ().

Используя эти свойства, к совершенному виду можно привести произвольную ДНФ.

Для этого выполним следующие действия:

Если какое-нибудь слагаемое R ДНФ не содержит переменной , ни ее отрицания, то заменим это слагаемое R следующей суммой

.

2. Если в полученном выражении окажутся одинаковые слагаемые, то удалим все из них, кроме одного.

3. Если в некоторых слагаемых окажутся одинаковые множители, то удалим лишние.

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

Если после этих действий сумма содержит хотя бы одно слагаемое, оно представляет собой СДНФ. Если же ни одного слагаемого не осталось, то данная функция тождественно ложна и не имеет СДНФ.

Пример

Определить СДНФ для формулы .

.

Аналогичным образом определяется СКНФ.

При табличном задании функции она строится по правилу (**) и всегда обладает следующими свойствами:

а) в ней нет двух одинаковых множителей;

б) ни один множитель не содержит двух одинаковых слагаемых;

в) ни один множитель не содержит переменной вместе с ее отрицанием;

г) каждый множитель содержит в качестве слагаемого либо , либо ().

Правила приведения произвольной КНФ к совершенному виду:

Если один из множителей R КНФ не содержит ни , ни , то его заменяют следующим множителем:

, равносильным R.

Если в полученном выражении есть одинаковые множители, то лишние выбрасываем.

Если в одном из множителей есть одинаковые слагаемые, то лишние выбрасываем.

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

Если после этого в форме останется хотя бы один множитель, то это СКНФ. В противном случае формула тождественно истинна.

Пример

Определить СКНФ для формулы

Совершенные нормальные формы для таблично заданных функций определяются с помощью выражений (*) и (**).

Булевы функции

Как мы уже говорили, система элементов с определенными в ней операциями L, V, – образует алгебру Буля. В алгебре Буля И обозначается как 1, а Л – как 0.

Функция называется булевой, если она принимает только два значения: 0 или 1, как и все переменные . Следовательно, областью определения булевой или логической функции является множество векторов , каждая координата которого принимает значения из множества {0,1}. Очевидно, что область определения X функции содержит различных векторов. Каждый конкретный вектор из 0 и 1 будем называть двоичным набором или просто набором. Так как число различных наборов для любой функции равно , т. е. конечно, то любую булеву функцию можно задать таблицей с строками. В левой части таблицы записываются наборы переменных, а справа – значения функции.

x1	x2	xn-1	xn	f (x1 , x2 ... , xn)	x
0	0	0	0	f	0
0	0	0	1	f	1
0	0	1	0	f	2
0	0	1	1	f	3
...	...	...	...	...	...
1	1	1	0	f	-1
1	1	1	1	f

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

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

Функция существенно зависит от элемента , если

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

Пример

имеет фиктивный аргумент .

0	0	0
0	1	0
1	0	1
1	1	1

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

Пример.

0	0	0	0	1	0	0	*
0	0	1	1	1	0	1	1
0	1	0	*	1	1	0	0
0	1	1	*	1	1	1	1

Здесь функция не определены на трех наборах. Если ее доопределить, то существует способов доопределения.

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

Элементарные булевы функции

Мы показали, что число булевых функций от n переменных равно . Выделим 11 элементарных булевых функций, которые имеют большое значение:

Две функции константы

Две функции одного переменного

Семь функций двух переменных

								f11
0	0	0	0	1	1	1	1	0
0	1	1	0	0	1	0	1	1
1	0	1	0	0	0	0	1	1
1	1	1	1	1	1	0	0	0

Здесь:

– дизъюнкция, логическое сложение;

– конъюнкция или логическое умножение;

– эквиваленция;

– импликация;

– функция Вебба (она истинна т. и т. т., когда

– ложны);

– функция Шеффера (она ложна т. и т. т., когда

– истинны );

– сложение по модулю 2 или исключающее “или”.

Рассмотренные одиннадцать элементарных функций позволяют строить новые функции алгебры логики двумя способами:

1. Путем перенумерации аргументов, например .

Путем подстановки в функцию, вместо аргументов, новых функций, например

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

Для любой суперпозиции можно построить потом таблицу истинности.

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

Ранее мы установили свойства конъюнкции, дизъюнкции и отрицания.

Рассмотрим теперь свойства импликации, сложения по модулю 2, функций Шеффера и Вебба.

( коммутативность ).

( ассоциативность ).

( дистрибутивность).

Для ® не выполняется коммутативность и ассоциативность, т. е.

Однако

Функции Шеффера и Вебба коммутативны

но не ассоциативны, т. е.

Для функций Шеффера и Вебба справедливы формулы Де Моргана:

Основные классы булевых функций

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

Класс функций, сохраняющих константу нуль, т. е. функций, удовлетворяющих условию

.

Класс функций, сохраняющих константу 1, т. е. функций, удовлетворяющих условию

.

3. Класс самодвойственных функций, т. е. функций, удовлетворяющих условию:

Например, , т. е. x есть самодвойственная функция.

4. Класс линейных функций, т. е. функций, которые можно представить в виде

где коэффициенты могут принимать значения 0 или 1.

Например, .

5. Класс монотонных функций

Будем говорить, что набор значений аргументов не меньше набора значений , если между всеми компонентами этих векторов существует следующее соотношение:

Например, (1, 0, 1, 1) не меньше (0, 0, 1, 1), а наборы (1, 0, 1, 1) и (1, 1, 0, 0) несравнимы. Функция называется монотонной, если для любых двух наборов , таких, что , имеет место неравенство Например,

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

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

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

Если рассматривать все множество функций n переменных, то оно образует - элементный базис, который, конечно, не является минимальным. Мы показали ранее, что любую формулу можно выразить через операции L, V, –, т. е. они тоже образуют базис. Но он тоже не является минимальным, т. к. L можно выразить через V и –, а V через L и –. Таким образом, – это минимальные базисы.

Полными системами являются также .

Система функций G называется независимой, если ни одна из функций f этой системы не может быть представлена суперпозицией функций из G\{f}.

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

Например, суперпозиция функций, сохраняющих 0, тоже сохраняет 0. Действительно, суперпозиция получается с помощью двух операций: 1) перенумерации переменных; 2) с помощью подстановки функции вместо аргумента.

Если , то перенумерацией аргементов это свойство не устраняется.

Если же вместо подставить такую, что

,

то

Используя это свойство, легко показать, что независимая система. Действительно, L нельзя представить суперпозицией функций –, т. к. L сохраняет 0 и 1, а суперпозиция функций –, как и сама – не сохраняет ни 0 ни 1.

Отсюда следует, что полная система фенкций не может содержать функции одного класса.

Теорема Поста-Яблонского

Система функций является полной тогда и только тогда, когда она содержит функцию:

не сохраняющую 0;

2) не сохраняющую 1;

3) несамодвойственную;

нелинейную;

немонотонную.

Замечание.

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

ЛИТЕРАТУРА

Введение в математическую логику. – М. : Наука, 1984.

Марков математической логики. – М: Изд-во МГУ, 1984.

, Драгалин в математическую логику: учебное пособие. – М. : Изд-во МГУ, 1982.

, Палютин логика: (Учеб. пособие для ВУЗов). – М.: Наука, 1979.

Новиков математической логики. – М. : Наука, 1973.