Содержание и значение математической символики (стр. 12 из 15)
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) = (А Ù В) ÙCAÚ (В Ú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) = и и т. д.