Содержание и значение математической символики
Заметим, что булевых функций от n
аргументов имеется лишь конечное число, а именно столько, сколько возможно
функциональных таблиц. Число возможных наборов аргументов равно 2n, а каждому набору аргументов можно независимо друг от друга
сопоставлять одно из значений и или л. Таким образом, число всевозможных
булевых функций от n аргументов равно
– Оно очень быстро
растет с ростом n. Изучение свойств булевых функций
имеет большее значение как для алгебры и математической логики, так и для их
приложений в кибернетике и теории автоматов. Естественно распространить
определение высказывательных связок, так как мы их определили выше, на булевы
функции. Мы ограничимся рассмотрением лишь связок Ù, Ú, ù называемых булевыми связками (или булевыми операциями).
Такое ограничение оправдано тем, что, как легко проверить, связки Þ и Û могут быть выражены через другие булевы связки. При помощи
таблиц истинности, приведенных выше, легко проверяются следующие тождества:
a Þ b º (ù a) Ú b;
a Û b º (a Ù b) Ú (ù a Ù ùb),
которые позволяют повсеместно заменить связки Þ, Û на Ù, Ú, ù.
Если мы теперь имеем булевы функции {F (xl, х2, ..., хn), G (х1, х2, ..., хn)} от n переменных, то действие связок над ними определяется естественным образом:
F (xl, x2, ..., хn) Ù G (х1, x2, ..., хn), F (xl, x2, ...,хn) Ú G (xl, x2, ..., хn), ùF (xl, x2, ..., хn) – это такие булевы функции, которые принимают значения, предписываемые соответствующими таблицами для каждого возможного значения аргументов. Кратко: булевы операции так переносятся на булевы функции, как действия арифметики переносятся на обычные функции числовых аргументов. Вообще имеет место далеко идущая аналогия между обычной алгеброй чисел и числовыми функциями, с одной стороны, и высказываниями и булевыми функциями – с другой. При этом можно отметить, что в одном определенном смысле алгебра булевых функций проще алгебры числовых функций: если рассматривать лишь функции некоторого конечного числа аргументов, то таких функций лишь конечное число. Поэтому выкладки с булевыми функциями вполне доступны пониманию школьников старших классов.
Естественно, закономерности булевой алгебры менее привычны и вызывают удивление и недоверие: это судьба всякого новшества.
Выпишем законы булевой алгебры. Большими латинскими буквами А, В, ..., X, Y, Z мы обозначим объекты, над которыми осуществляются булевы операции Ù, Ú, ù. Для определенности будем считать, что эти объекты – булевы функции некоторого фиксированного числа переменных. Среди них есть два особых элемента: 1, 0. Это соответственно функции, принимающие для всех аргументов значения 0 и 1 (постоянные функции – нуль и единица). Тогда
А Ù В = В Ù А, A Ú B = B Ú A
A Ù (В Ù C) = (А Ù В) Ù C A Ú (В Ú C) = (А Ú В) Ú C
A Ù A = A A Ú A = A
A Ù 1 = A A Ú 1 = A
A Ù 0 = 0 A Ú 0 = A
ù(A Ù B) = ùA Ú ùB ù(A Ú B) = ùA Ù ùB
A Ù (B Ú C) = (A Ù B) Ú (A Ù C) A Ú (B Ù C) = (A Ú B) Ù (A Ú C)
ù ùA = A
Если, как это обычно делают, булевы операции Ú, Ù, ù считать аналогом сложения, умножения и перехода к противоположному числу, то некоторые из вышеприведенных законов те же, что для числового сложения и умножения, другие же существенно отличаются от привычных.
4.1.3 Задания для учащихся.
Верно ли высказывание: ù(205 кратно 5); 7
7; ù(8>10); 1£3£3.
А – множество точек треугольника и В – множество точек четырехугольника.

Верно ли высказывание: CÎA Ù CÎB; KÎB Ù KÎA; SÎB Ú SÎA; ù(SÎA)ÙSÎB?
Известно, что А=и, В=и, Х=л, Y=л. Найдите значение высказывания:
АÚùХ; ùYÙùA; AÞX; ù(ùВÚY); (AÙB)ÚX; (XÚB)ÞY; (XÙA)Þ(YÚB); ù (AÚX)Ù(YÚùX).
Составьте таблицу истинности высказываний: ùХÙХ; (ХÚY)ÚùY; (XÙY)ÚùX; ùXÞY; (XÙY)ÞY.
Используя переменные X, Y, Z, запишите сочетательное свойство операции «и».
Проверьте равенство (XÚY)ÙZ º (XÙZ)Ú(YÙZ) и (XÙY)ÚZº(XÚZ)Ù(YÚZ), составляя таблицы истинности для левой и правой части.
4.2 Предикаты и кванторы.
4.2.1 Предикаты.
Алгебра предикатов – тот раздел математической логики, который непосредственно надстраивается над алгеброй высказываний.
Как мы видели, одной из основных задач алгебры высказываний является изучение истинности или ложности высказываний в зависимости от истинности или ложности входящих в них высказываний. Несмотря на большую важность этой области логики, она оказывается слишком бедной для описания и для изучения даже простейших заключений науки и практики. В рамки алгебры высказываний не укладываются ни простейшие заключения арифметики и геометрии, не говоря уже о довольно сложных логических выводах, с которыми мы сталкиваемся в других науках и в повседневной жизни.
Действительно, рассмотрим следующие простейшие заключения.
Из истинных высказываний «3 меньше 5» и «5 меньше 7» мы заключаем, что «3 меньше 7». Из истинных высказываний «Все птицы – животные» и «Все воробьи – птицы» мы делаем заключение: «Все воробьи – животные». Из высказываний «Петр – сын Ивана» и «Павел – сын Петра» мы заключаем: «Павел – внук Ивана» и т. д.
Заметим, что во всех рассмотренных примерах истинность заключения зависит не только от истинности посылок, но и от их содержания. Если изменить вид посылок, то может оказаться, что заключение будет неверным. Так (в первом примере) из истинных высказываний «3 меньше 5» и «5 не равно 7» нельзя делать заключение (которое оказывается истинным), что «3 меньше 7», или, изменив немного второй пример, из истинных высказываний «Все птицы – животные» и «Никакие рыбы не птицы» нельзя выводить ни ложное высказывание «Никакие рыбы не животные», ни истинное высказывание «Все рыбы – животные». Наконец, видоизменив последний пример, из истинных высказываний «Петр – сын Ивана» и «Павел – родственник Петра» мы не имеем права делать заключение (которое в действительности может быть как истинным, так и ложным), что «Павел – внук Ивана» (но можем вывести истинное заключение: «Павел – родственник Ивана»).
Чтобы построить систему правил, позволяющую логически выводить правильные заключения, учитывающие в какой-то мере содержание посылок, мы должны проанализировать строение простых высказываний. И здесь нам опять кое-что может подсказать грамматика. Следуя по такому пути, мы придем к разделу логики, называемому алгеброй предикатов. Она предполагает алгебру высказываний уже известной, но идет дальше: простые высказывания, из которых состоят сложные, в свою очередь расчленяются.
Теория предикатов исходит из следующей установки. Простые высказывания выражают, что некоторые объекты обладают некоторыми свойствами или находятся между собой в некоторых отношениях.
При этом понятия «свойство» и «отношение» рассматриваются как частные случаи общего понятия «предиката». Объекты, о которых говорится в высказываниях, называются «термами». Постараемся выяснить смысл этих понятий на примерах.
Рассмотрим сначала некоторое число простых предложений – высказываний, выражающих, что некоторый объект обладает некоторым свойством:
«Сократ – грек»;
«Платон – ученик Сократа»;
«Три – простое число»;
«Василий – студент» и т. д. ,
Все приведенные примеры – простые предложения, С точки зрения грамматики они состоят из подлежащего («Сократ», «Платон», «три», «Москва», «Василий») и сказуемого («есть грек», «есть ученик Сократа», «есть простое число»). Подлежащее является наименованием некоторого объекта – конкретного или абстрактного, сказуемое выражает некоторое свойство. В латинской грамматике сказуемое называется предикатом, и этим термином принято теперь пользоваться в математической логике в рассматриваемых ситуациях. Основным для алгебры предикатов является второй член предложения – сказуемое-свойство. Как же алгебра предикатов трактует понятие «свойство»? Она рассматривает его как некоторую функцию следующим образом.
Возьмем первый пример: «Сократ есть грек».
Вместо человека Сократ мы можем подставить имена всевозможных людей и будем получать всегда осмысленные предложения. Одни предложения будут истинными, другие – ложными:
«Сократ есть грек» – истинно;
«Платон есть грек» – истинно;
«Наполеон есть грек» – ложно;
«Ньютон есть грек» – ложно и т. д.
Более обще можно рассматривать выражение вида «X есть грек», где буква X указывает место, на которое нужно подставить имя некоторого человека, чтобы получить высказывание — истинное или ложное. Но, как нам уже известно, существенным свойством высказывания является его значение истинности и или л. Становясь на эту точку зрения, логика предикатов считает выражение «X есть грек» функцией, аргумент которой X пробегает класс всех людей, а сама функция принимает в качестве значений и или л. Если мы будем, как это принято в математике, «X есть грек» записывать сокращенно, например в виде Гр (X), то для значения X = Сократ получим Гр (Сократ) – и, а скажем Гр (Наполеон) – л и т. д. Относительно других приведенных примеров можно дословно повторить все то, что было сказано относительно первого.
Таким образом, предикатом или, лучше, предикатом-свойством будем считать функцию, определенную на некотором универсальном множестве и принимающую значения и и л. Те элементы, для которых значение предиката «истинно», обладают данным свойством, остальные не обладают.
Отсюда сразу видно, что в действительности всякий предикат-свойство вполне определяется подмножеством тех объектов, на которых данная функция принимает значение «истинно». Полезно привести примеры предикатов-свойств из области арифметики. Такими будут, например, свойства натуральных чисел «быть простым числом», «быть четным числом», «быть квадратом» и т. д.
Остановимся на примере «три есть простое число» и на соответствующем предикате-свойстве «быть простым числом». Введем для этого свойства сокращенное обозначение Пр (X). Предикат Пр (X) определен на множестве натуральных чисел. Имеем Пр(1) = л (поскольку 1 не принято рассматривать как простое число). Пр (2) = и, Пр (3) = и, Пр (4) = л, ..., Пр (10) = л, Пр (11) = и и т. д.
Подобно приведенным предикатам-свойствам, математическая логика рассматривает более общее понятие предиката-отношения. В зависимости от того, между каким числом объектов устанавливается отношение, мы различаем двухместные (бинарные), трехместные (тернарные) и т. д., в общем случае – n-местные отношения. Рассмотренные выше предикаты-свойства считаются унарными предикатами. Наконец, оказывается удобным в понятие предиката-отношения как частный случай включить и высказывания в качестве «0 – местных предикатов».
Все математические дисциплины имеют дело с предикатами-отношениями, причем самыми распространенными являются бинарные отношения. Они описываются, различными словами: «равны», «не равны», «больше», «меньше», «делить», «перпендикулярны», «параллельны» и т. д.
По аналогии с предикатом-свойством двухместным предикатом считается опять функция, на этот раз от двух аргументов, определенных на некотором универсальном множестве, принимающая значение и (истинно) и л (ложно): те пары элементов, для которых функция принимает значение и, находятся в рассматриваемом отношении, остальные пары в этом отношении не находятся.
Рассмотрим пример бинарного отношения, определенного на множестве натуральных чисел, а именно отношение, описываемое словом «больше». Если рассматривать это отношение как функцию от двух переменных X и Y (на множестве натуральных чисел), принимающую значения и или л в зависимости от того, будет ли соответствующее отношение выполняться или нет, то эта функция определяет предикат, который обозначим через > (X, Y). Тогда имеем, например, > (3, 2) = и, > (1, 3) = л, > (7, 5) = и и т. д. Более полно и обозримо двухместный предикаты >(Х, Y).
| 1 | 2 | 3 | 4 | 5 | … | |
| 1 | л | и | и | и | и | … |
| 2 | л | л | и | и | и | … |
| 3 | л | л | л | и | и | … |
| 4 | л | л | л | л | и | … |
| 5 | л | л | л | л | л | … |
| … | … | … | … | … | … | … |
Конечно, совсем нетрудно указать в элементарной математике примеры трехместных предикатов и предикатов от еще большего числа аргументов. Так, трехместным предикатом является в геометрии отношение, описываемое словом «между»: «Точка Y лежит между точками X и Z». В арифметике хорошо известны понятия наибольшего общего делителя и наименьшего общего кратного двух целых чисел: фраза