2. Основы математической логики

2.1. Высказывания и функции на высказываниях

Математическая логика изучает высказывания, значениями которых может быть «истина» либо «ложь».

Так, например, высказывание 3 > 5 ложно, а высказывание 5 > 3 истинно. Высказывания могут носить не только мате­матический характер. Например, высказывание «документ получен» может быть истинным или ложным в зависимости от того, какой документ, когда, кем получен и др. Формальный анализ этой ситуации и подобных ей невозможен без изучения основных понятий математической логики.

Эти понятия вводятся следующим образом.

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

Поясним это на примере. Пусть переменные x₁ и x₂ представляют два различных высказывания: x₁ = а > 0, x₂ = =a < 1, где а — вещественная переменная. Заметим, что значения пере­менных x₁ и x₂ истинны либо ложны в зависимости от того, какие значения принимает вещественная переменная а. Так если а = 3, то x₁ — истинно, а x₂ — ложно. Ограничившись только значениями переменных x₁ и x₂, а не способами их получения, можно формализовать процесс перехода от более простых высказываний к более сложным, введя функции F на множестве переменных x_{1, … ,} x_n, значения которых также могут быть только «истина» или «ложь». Такие функции, называются логическими или булевыми.

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

Считают, что атомами могут быть высказывания, которые нельзя представить функциями алгебры логики, кроме как записав их в виде логических переменных. Примерами таких высказываний могут быть: «Сократ — человек», «5 > 3», «a + b = c».

С другой стороны, молекулы могут быть представлены функциями алгебры логики любой сложности. Ниже они будут подробно рассматриваться. От атомов они отличаются, например, тем, что содержат логические связки «и», «или», «не», которым поставлены в соответствие логические операции. Примерами молекул могут быть высказывания: «Сократ — человек и Сократ — философ», «5 > 3 или 5 > 0», «не истина — ложь».

Работая с молекулами, имеем возможность на абстрактном уровне иссле­довать свойства логических функций, выполнить обоб­ще­ния, а затем, в случае необходимости, получить новые смысловые формы, строго определив условия их истинности либо ложности. Так, например, высказывание x₁ = а  0 принимает значение «истина», в том и только в том случае, когда а принадлежит положительному лучу, а выс­казывание x₂ = a  1 принимает значение «истина», тогда и только тогда, когда а принадлежит полуинтервалу (-∞,1]. Располагая переменными x₁, x₂ мы можем, например, поставить задачу о построении функции F(x₁, x₂), которая принимает значение «истина» тогда и только тогда, когда оба значения аргументов х₁ и х₂ истинны без всякого отношения к ато­марному смыслу.

Предположим, что мы построили такую булеву функцию истинности. Тогда мы можем попытаться пост­роить и новое высказывание в атомарном смысле, которое бы соот­вет­ствовало данной функции. В нашем случае оно выразится так: «точка а принадлежит отрезку [0,1]».

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

Рассмотрим вопрос о построении логических функций.

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

Поскольку каждая логическая переменная может при­нимать одно и только одно из двух значений, то множество всех значений n переменных имеет мощность m = 2ⁿ, что эквива­лентно размещению всех двоичных чисел в разрядной сетке длины n.

В 1.4 нами рассмотрен вопрос о мощности множества всех бинарных функций построенных на дискретном множестве мощ­ности m. Мощность этого множества равна 2^m. Это мно­жество функций можно построить путем перебора всех бинарных значений функции на множестве всех бинарных значений аргументов.

Поэтому число всех функций F, построенных на мно­жестве переменных x₁, x₂, …, x_n, будет равно 2^m, где m = 2ⁿ. Это число обозначается p(n).

Необходимо отметить, что p(n) растет очень быстро в зависимости от n. Так для различных n имеем: p(1) = 4, p(2) = 16, а p(4) = 65536.

Поэтому, несмотря на то, что при любом конечном n значение p(n) конечно, уже при n > 10 простой перебор всех функций становится практически нереальным даже на су­пермощных компьютерах.

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

Все функции одного переменного представлены в таб­лице 2.1. В этой таблице и далее мы условимся для обоз­начения «истина» применять символ «1», а для обоз­начения «ложь» — символ «0». Эти обозначения также яв­ляются общепринятыми. Кроме того они экономят символы.

Таблица 2.1 — Функции одной переменной

X	F0^1	F1^1	F2^1	F3^1
0	0	0	1	1
1	0	1	0	1

При рассмотрении таблицы 2.1 заметим следующее. Значения функций F₀¹ и F₃¹ не зависят от х. Функция F₁¹ то­ждественна х. Эти функции не представляют суще­ственного интереса в том , чтобы присвоить им специальные наименования.

Из рассмотренного множества можно выделить функцию F₂¹_, значения которой обратны по отношению к значениям аргумента. В связи с этим F₂¹ получила специальное название — отрицание.

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

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

Таблица 2.2 — Функции двух переменных

х		F^2i, (i = 1,n)
1	2	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1