18 Логические операции. Понятие высказывания. Типология высказываний.

Алгебра, образованная множеством В вместе со всеми возможными операциями на нем, называется алгеброй ло­гики. Функцией алгебры, логики (или логической функцией) от п переменных называется n-арная операция на В. Первый термин более точен, однако второй более распространен, особенно в приложениях. Он и будет использоваться в дальнейшем. Итак, логическая функция f(x₁, ... ...,x_n) —это функция, принимающая значения 0, 1. Множество всех логических функций обозначается Р₂, множество всех логических функций п переменных—P₂(n).

Таблица 3.1

Всякая логическая функция п переменных может быть задана таблицей, в левой части которой перечислены все 2" наборов значений переменных (т, е. двоичных векторов длины п), а в правой части — значения функции на этих наборах. Например, табл. 3.1 задает функцию трех переменных.

X1	X2	X3	f
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

Функция ₁(x₁, x₂) называется конъюнкцией х₁ и x₂ ее обозначения: x₁&x₂, x₁/\x₂, х₁*x₂ (во всех случаях знак конъюнкции аналогично умножению часто опускают и пи­шут x₁x₂). В этой книге конъюнкция будет обозначаться знаком &. Она равна 1, только если х₁ и x₂ равны 1, поэтому ее называют часто функцией И. Еще одно ее название—«логическое умножение», поскольку ее таблица дей­ствительно совпадает с таблицей обычного умножения для чисел 0 и 1.

Функция ₇(x₁, x₂) называется дизъюнкцией x₁ и x₂; ее обозначения: х₁ \/ х₂, х₁+x₂. Она равна 1, если х₁ или x₂ равен 1 («или» здесь понимается в неразделительном смысле—хотя бы один из двух). Поэтому ее называют часто функцией ИЛИ.

Функция ₆(x₁, x₂)—это сложение по модулю 2 (см. пример 2.1,6). Ее обозначения: х₁ х₂, х₁ х₂, х₁ х₂. Она равна 1, когда значения ее аргументов различны, и рав­на 0, когда они равны. Поэтому функцию ₆ иногда называют неравнозначностью.

Функция ₉(x₁, x₂) называется эквивалентностью, или равнозначностью. Ее обозначения: x₁~x₂, x₁x₂. Она равна 1, когда значения ее аргументов равны, и равна 0, когда они различны.

Еще три функции имеют свои названия:

₁₃(x₁, x₂)—импликация; обозначения x₁->x₂, x₁x₂, чи­тается «если х₁, то x₂»;

₈(x₁, x₂) —стрелка Пирса; обозначение х₁x₂;

₁₄(x₁, x₂)—штрих Шеффера; обозначение x₁|x₂.

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

19 Понятие предиката. Типология логических формул. Кванторы.

Предикаты. Предикатом P(x₁, ..., x_n) называется функция Р : Mⁿ—>B, где М — произвольное множество, а В — двоичное множество, определенное в начале § 3.1. Иначе говоря, n-местный предикат, определенный на М, — это двузначная функция от п аргументов, принимающих значения в произвольном множестве М. М называется предметной областью предиката, а х₁, ..., x_n—предметными переменными. В принципе ничто не мешает определить предикат в более общем виде как функцию Р : МХ.М₂Х...ХM_n—>В, т. е. разрешить разным аргументам принимать значения из разных множеств. Иногда это оказывается удобным; однако, как правило, в логике предикатов исходят из первого определения.Для любых М и n существует взаимно однозначное со­ответствие между n-местными отношениями и n-местными предикатами на М: а) каждому n-местному отношению R соответствует предикат Р, такой, что P(a₁, ..., a_n)=1, если и только если (a₁, ..., a_n)R; б) всякий предикат Р(х₁, ..., x_n) определяет отношение R, такое, что (a₁, ..., a_n)R, если и только если Р(а₁, ..., а_n)=1. При этом R задает область истинности предиката Р.

Всякой функции f: Мⁿ—>М можно поставить в соответствие (n+1)-местный предикат Р, такой, что P(a₁, ..., a_n, а_n+1)=1, если и только если f(a₁, ..., а_п)=а_n+1. Поскольку функция должна быть однозначной, то это соответствие тре­бует, чтобы для любого а^’_n+1a_n+1 P(a₁, ..., а_п, a^’_n+1)=0. Поэтому обратное соответствие [от (n+1)-местного преди­ката к n-местной функции] возможно не всегда, а только при выполнении указанного условия.

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

Выражение Р(а₁, ..., a_п) (и другие, более сложные выражения логики предикатов), где а₁,..., a_nM, будем понимать как высказывание «Р(а₁, ..., а_n)=1» или в соответствии с логической интерпретацией как «Р(а₁, ..., a_п) истинно», а выражение р(x₁,..., x_п), где х₁,..., x_п —переменные, как переменное высказывание, истинность которого определяется подстановкой элементов М вместо х₁, ..., Хп. При этом р(х₁, ..., Хп) —это логическая (двоичная) переменная, а х₁,..., x_п — нелогические переменные. Поскольку предикаты принимают два значения и интерпретируются как высказывания, из них можно образовывать выражения логики высказываний, т.е. формулы вида P₁(x₁, x₂) V (Р₂ (х₃, х₄)&P₁(x₂, x₄).Эта формула может рассматриваться и как составная булева формула, описывающая функцию алгебры логики от трех логических переменных P₁(x₁, х₂), Р₁(x₂, х₄), P(x₃, x₄), [P₁(x₁, x₂) и P₁ (x₂, x₄) —разные логические переменные, так как предикат Pi в этих выражениях зависит от разных переменных, и как составной четырехместный предикат, значение которого определяется четырьмя предметными переменными х₁, x₂, x₃, х₄.

В дальнейшем, если это не вызовет разночтении, будем употреблять одинаковые обозначения для отношений и соответствующих им предикатов; при этом, помимо функциональных обозначений вида Р(х), Р(х₁, х₂), для двухместных предикатов будем пользоваться обозначениями вида х₁Рх₂, которые уже употреблялись в гл. 1 для бинарных отношений.

Пример 3.11. а. Предикат х₁>х₂—это двухместный предикат, предметной областью которого могут служить любые множества действительных чисел. Высказывание 6>5 истинно, а высказывания 7>7 и 3>10 ложны. Различ­ные подстановки чисел вместо одной предметной перемен­ной дают различные одноместные предикаты: х₁>5, x₁>0, 7>x₂ и т. Д

Кванторы. Пусть Р(х)—предикат, определенный на М. Высказывание «для всех х из М Р(х) истинно» обозначается хР(х) (множество М не входит в обозначение и должно быть ясно из контекста). Знак x называется квантором общности; другое его обозначение (х). Высказывание «существует такой х из М, что Р(х) истинно» обозначается хР(х). Знак x называется квантором существования; другое его обозначение (Ех). Переход от Р(х) к vxP(x) или к хР(х) называется связыванием переменной х, а также навешиванием квантора на переменную х (или на предикат Р), иногда—квантификацией переменной х. Переменная, на которую навешен квантор, называется связанной; несвязанная переменная называется свободной.

Смысл связанных и свободных переменных в предикатных выражениях различен. Свободная переменная — это обычная переменная, которая может принимать различные значения из М; выражение Р(х) —переменное высказывание, зависящее от значения х. Выражение xP(x) не зависит от переменной х и при фиксированных Р и М имеет вполне определенное значение. Это, в частности, означает, что переименование связанной переменной, т. е. переход от xP(x) к yP(y), не меняет истинности выражения. Переменные, являющиеся по существу связанными, встречаются не только в логике. Например, в выражениях  f(x) или Г f(x)dx переменная х

^х=л

связана; при фиксированной f первое выражение равно определенному числу, а второе становится функцией от а и b.

Навешивать кванторы можно и на многоместные предикаты, и вообще на любые логические выражения, которые при этом заключаются в скобки. Выражение, на которое навешивается квантор  или х, называется областью действия квантора; все вхождения переменной х в это выражение являются связанными. Навешивание квантора на многоместный предикат уменьшает в нем число свободных переменных и превращает его в предикат от меньшего числа переменных.