Множества и операции над ним

Работа добавлена на сайт samzan.net:

ТЕМА №1. Множества и операции над ними.

§1. Основные понятия о множествах.

1.  Основные определения.

Одним из основных понятий математики является понятие множества, и, как каждое основное понятие, не поддаётся точному определению (например, понятия “точка”, “прямая” являются одними из основных понятий геометрии).

МНОЖЕСТВОМ называется собрание, совокупность объектов, объединенных по какому-нибудь общему признаку, свойству.

Примеры:

1.  Множество студентов данной учебной группы.
2.  Множество планет солнечной системы.
3.  Множество букв русского алфавита.
4.  Множество натуральных чисел.

Математический смысл слова “множество” отличается от того, как оно используется в обычной речи. Так, в обычной речи понятие “множество” связывают с большим числом предметов, в математике же этого не требуется. Здесь могут рассматриваться множества, содержащие один объект, много объектов, несколько объектов или не содержащие ни одного объекта.

Объекты, из которых состоит множество, называются его ЭЛЕМЕНТАМИ.

Остановимся на символике, обычно использующейся при обращении с множествами.

Множества обозначаются прописными (заглавными) буквами латинского алфавита (без индексов или с индексами). Например: B, C,…,X,Y,…,A1,B1,…

 Элементы множества обозначаются  строчными (малыми) буквами латинского алфавита. Например: b,c,…,x,y,…,a1,b1,…

В математике особую роль играют множества, элементами которых являются числа. Такие множества называются ЧИСЛОВЫМИ. Некоторые числовые множества имеют специальные обозначения, вводимые для удобства пользования. Один из вариантов этих обозначений, которыми мы будем пользоваться в дальнейшем, выглядит следующим образом:

 N – множество всех натуральных чисел;

 Zc (или Z+ или C+) – множество всех целых неотрицательных чисел;

 Z (или C) – множество всех целых чисел;

 Q – множество всех рациональных чисел;

 R – множество всех действительных чисел;

 R+ - множество всех действительных положительных чисел.

По числу элементов, входящих в множество, множества делятся на три класса:

1 – конечные,  2 – бесконечные, 3 – пустые.

1. Если  элементы множества можно сосчитать, то множество является КОНЕЧНЫМ.

Пример 1.

Множество гласных букв в слове “математика” состоит из трёх элементов – это буквы “а”, “е”, “и”, причем, гласная считается только один раз, т.е. элементы множества при перечислении не повторяются.

2. Если элементы множества сосчитать невозможно, то множество БЕСКОНЕЧНОЕ.

Пример 2.

Множество натуральных чисел бесконечно.

Пример 3.

Множество точек отрезка [0;1] бесконечно.

3. Множество, не содержащее ни одного элемента, называется ПУСТЫМ. Символически оно обозначается знаком .

Пример 4.

Множество действительных корней уравнения  x2 +1=0.

Пример 5.

Множество людей, проживающих на Солнце.

В математике часто приходится определять принадлежность данного элемента конкретному множеству.

Пример 6.

Мы говорим, что число 5 натуральное, т.е. утверждаем, что число 5 принадлежит множеству натуральных чисел. Символически принадлежность множеству записывается с помощью знака . В данном случае символическая запись будет такой: 5  N. Читается: “5 принадлежит множеству натуральных чисел”.

Число 5,2 не принадлежит множеству натуральных чисел, т.к. не является натуральным числом. Символически отношение “не принадлежит” записывается с помощью знака  (реже ). Таким образом, здесь имеем: 5,2  N

Читается:  “5,2 не принадлежит множеству натуральных чисел”.

1.2 Способы задания множеств.

Множество считается заданным, если мы владеем способом, позволяющим для любого данного элемента определить, принадлежит он данному множеству или не принадлежит.

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

Пример 7.

Множество всех гласных букв русского алфавита:

  A={а; я; у; ю; э; е;о; ё; и; ы}.

Пример 8.

Множество цифр десятичной системы счисления:

 B={1; 2; 3; 4; 5; 6; 7; 8; 9; 0}.

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

Конечные и бесконечные множества могут быть заданы другим способом: указанием ХАРАКТЕРИСТИЧЕСКОГО СВОЙСТВА, т.е. такого свойства, которым обладает любой элемент данного множества и не обладает ни один элемент, не принадлежащий ему.

Пусть P обозначает некоторое свойство, которым обладают все элементы множества  А и не обладают элементы никакого другого множества. Тогда множество всех элементов, обладающих свойством Р, обозначим так:

А={х│х обладает свойством Р}={ х│Р(х)}={х : Р(х)}.

Свойство Р, задающее множество А, есть характеристическое свойство множества А.

Пример 9.

Множество чётных натуральных чисел. Зададим его с помощью характеристического свойства:

В={х │х – чётное натуральное число}={х │ х=2k, k Є N}.

Пример 10.

Множество всех действительных чисел на отрезке от 1 до 3 включительно запишется следующим образом:

R1-3={y│1≤ y≤ 3, y Є R}.

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

Пример 11.

Множество натуральных чисел, меньших, чем 10.

Первый способ: N<10={1; 2; 3; 4; 5; 6; 7; 8; 9}.

Второй способ: N<10={z│z<10, z Є N}.

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

Пример 12.

Множество квадратов.

Первый способ: A={x│x – ромб с прямыми углами}.

Второй способ: A={ x│x – прямоугольник с равными сторонами}.

1.3 Отношения между множествами.

 

Наглядно отношения между множествами изображают при помощи особых чертежей, называемых КРУГАМИ ЭЙЛЕРА (или диаграммами Эйлера – Венна).

Для этого множества, сколько бы они ни содержали элементов, представляют в виде кругов или любых других замкнутых кривых (фигур) – рис.1.

Рис. 1.

1. Пусть даны два множества: X={a; b; c; d} иY={l; k; m; b; c}. Множества Х и Y содержат некоторые одинаковые элементы, а именно “b” и “c” . В данном случае говорят, что множества X иY находятся в отношении ПЕРЕСЕЧЕНИЯ. С помощью кругов Эйлера данное отношение можно представить в виде рис. 2.

X   Y           B1                         B2

Рис. 2.        Рис. 3.

1.  Пусть даны множества B1={1; 2; 3} и B2={4; 5; 6}.

Данные множества различны, у них нет одинаковых элементов. В таком случае говорят, что множества B1 и B2 находятся в отношении НЕПЕРЕСЕЧЕНИЯ.

С помощью кругов Эйлера данное отношение показано на рис. 3.

1.  Пусть даны множества A={a; b; c; d; e} и B={a; b; c}.

Очевидно, что эти множества пересекаются; кроме того, каждый элемент
множества В является в то же время (одновременно) и элементом множества А. Тогда говорят, что множество В ВКЛЮЧЕНО в множество А, или что В есть ПОДМНОЖЕСТВО множества А.

Определение 1.1

Множество В является подмножеством множества А тогда и только тогда, когда каждый элемент множества В является элементом множества А.

Отношение “включено” обозначается знаком .

Соответственно отношение “включает” – знаком .

Определение 1.1 символически записывается так: ВА или АВ. С помощью кругов Эйлера данное отношение между множествами показано на рис.4.

Из определения подмножества следует, что всякое непустое множество А содержит по крайней мере два

множества: Ø и А, которые называются НЕСОБСТВЕННЫМИ

ПОДМНОЖЕСТВАМИ МНОЖЕСТВА. Все остальные подмножества (если они существуют) называются СОБСТВЕННЫМИ ПОДМНОЖЕСТВАМИ МНОЖЕСТВА. То есть, если В – собственное подмножество множества А, то имеем: Ø ВА, или иначе: АВ Ø.

4. Пусть даны множества C={x; y; z},  D={x; y; z}, которые состоят из одних и тех же элементов. В таком случае говорят, что множества С  и D равны и пишут C=D.

Определение 1.2

Множества С и D называются равными, если они состоят из одних и тех  же элементов.

Используя понятие “включено”, можно дать другое определение равенства множеств.

Определение 1.3

Множества C и D называются равными тогда и только тогда, когда множество С является подмножеством множества D, и наоборот.

Символически данное определение можно записать так:
С = D   С  D и D  С, или С = D  С  D  D  С,
где знак  означает “эквивалентность”  (равнозначность), а знак  (конъюнкция) означает одновременность (совместность) осуществления тех операций (или событий), которые он соединяет.

С помощью кругов Эйлера отношение “равенство” показано на рис.5.

Рис.5.       рис.6.

Универсальное множество.

Пусть U (или T – total) – некоторое фиксированное множество. Рассмотрим только такие множества А, В, С,…, которые являются подмножествами множества U. В этом случае множество U называется  универсальным множеством всех множеств А, В, С,…

Примером универсального множества может служить множество действительных чисел, множество людей на планете Земля…

Мы его будем изображать прямоугольником с буквой U в правом верхнем углу (рис.6), внутри которого будут размещаться те или иные множества.

§2. Операции над множествами.

Рассмотрим некоторые операции над множествами.

2.1 Пересечение множеств.

Пусть даны два множества: А={a; b; c; d} иB={c; d; e}.образуем новое множество Р, состоящее из всех  элементов, принадлежащих одновременно и множеству А, и множеству В, т.е. Р={c;d}. Тогда говорят, что множество Р является пересечением множеств А и В.

Определение 1.4

Пересечением множеств А и В называется множество, состоящее их всех тех и только тех элементов, которые принадлежат множествам А и В одновременно.

Символически пересечение множеств А и В обозначается так: АВ, где символ  - знак пересечения множеств. Используя характеристическое свойство, определение 1.4 можно записать следующим образом:

Р=АВ= {x xA и xB}={x  xA  xB}.      (1)

Таким образом, (1) есть характеристическое свойство пересечения двух множеств.

Союз “и” иногда заменяют фигурной скобкой, и тогда (1) будет иметь вид:

         (2)

Для обозначения одновременной принадлежности множеству А и множеству В используется также знак  (конъюнкция, или логическое “и”):

 xAB    xA    xB    (2а)

Читаются выражения (2) и (2а) одинаково: если х принадлежит пересечению множеств А и В, то х  принадлежит как множеству А, так и множеству В.

Если мы имеем ситуацию, когда х не принадлежит пересечению множеств А и В, то это означает, что х не принадлежит или множеству А, или множеству В.

Символически это может быть записано так:

    (3)

где квадратная скобка заменяет союз “или”.

В символической записи союз “или” может быть заменен также знаком  (дизъюнкция, логическое “или”):

 хАВ    хА  хВ.                                       (3а)

Читаются выражения (3) и (3а) одинаково: если х не принадлежит пересечению множеств А и В, то х не принадлежит или множеству А, или  множеству В.

Графическая иллюстрация вариантов пересечения двух множеств приведена на рис. 710 (пересечение заштриховано).

рис. 7        рис. 8     рис. 9  рис. 10

2.2 Объединение множеств.

Множества А и В входят в их объединение только один раз. Это вполне соответствует толкованию множества, принятому в математике: ни один элемент не может содержаться в множестве несколько раз.

Определение 1.5

Объединением двух множеств А и В называется такое множество С, которое состоит из всех тех элементов, которые принадлежат хотя бы одному из множеств А или В.

Символически объединение двух множеств А и В обозначается так:

А  В, где  - символ объединения множеств. Определение 1.5 можно записать с помощью характеристического свойства:

С= А  В={x xA или xB}.       (4)

Союз “или” иногда заменяют квадратной скобкой

          (5)

а также знаком дизъюнкции

х А  В   хА  хВ.                        (5а)

Читаются эти знаки одинаково: если элемент х принадлежит объединению двух множеств А и В, то он принадлежит множеству А или множеству В.

Если же элемент х  не принадлежит объединению множеств А и В, то он не принадлежит ни множеству А, ни множеству В. Символически это может быть записано так:

        (6)

или

  x AB  xA  xB.    (6а)

Графически варианты объединения двух множеств показаны на рис. 11÷14 (объединение заштриховано).

                 

рис. 11        рис. 12      рис. 13    рис. 14

Отметим  некоторые очевидные свойства операции объединения двух множеств:

АА=А,    А=А,  АU=U.       (7)

Замечание1.

Если А1, А2,…, Аn – несколько множеств, то аналогично тому, как это делалось для двух множеств, определяется их пересечение, т.е. составляется множество, представляющее их общую часть:

Р= А1 А2… Аn={x  x Ai, i=},

Где символ  (квантор всеобщности) заменяет слово “все”, и, таким образом, мы символически обозначили ту часть множеств Ai, которая принадлежит каждому множеству одновременно.

Замечание 2.

Если А1, А2,…, Аn – несколько множеств, то аналогично тому, как это делалось для двух множеств, определяется их объединение – составляется множество, состоящее из элементов, которые принадлежат хотя бы одному их них:

 C= A1A2…An={x  xA1 или xA2  или …или xAn}.

Замечание 3.

Если в выражении есть знаки  и  и нет скобок, то сначала выполняется операция пересечения, а потом – операция объединения (аналог сложению и умножению в арифметике).

2.3 Разность множеств.

Определение 1.6

Разностью двух множеств А и В называется множество, состоящее из всех тех  и только тех элементов, которые принадлежат множеству А и не принадлежат множеству В.

Символически разность двух множеств обозначается так:

А  В, где символ   является знаком разности для множеств. С помощью характеристического свойства запишем определение 1.6 следующим образом:

 C=A  B={x  xA и xB}       (8)

Или  

        (9)

а также     xAB  xA    xB.    (9а)

Пример 1.

Если E1={2; 4; 6} и E2={6; 8; 10},     то E3=E1E2={2; 4},         E4=E2E1={8;10}.

Пример 2.

Если M1={x1; x2; x3},  M2={y1; y2}, то M3=M1M2={ x1; x2; x3},

M4=M2M1={y1; y2}.

Пример 3.

Если K1={1; 3; 5; 7; 9}, K2={5; 7; 1}, то K3=K1K2={3; 9}, K4=K2K1=.

 

Графическое представление вариантов разности двух множеств А и В показано на рис. 15÷18, где множество А  В заштриховано.

рис. 15          рис. 16       рис. 17     рис. 18

2.4 Дополнение к множеству.

Определение 1.7

Пусть В  А. Множество всех элементов множества А, не принадлежащих множеству В, называют дополнением к множеству В и обозначают  или .

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

Определение 1.8

Пусть А – некоторое множество, являющееся частью универсального (основного) множества U. Дополнением множества А называется множество, состоящее из всех  тех и только тех элементов их множества U, которые не принадлежат А. Его обозначают      или .

Это определение может быть записано в виде:

= {x  xA}.       (10)

Графически дополнения (соответственно определениям 1.7 и 1.8) изображены на рис. 19 и 20 соответственно, на которых дополнения заштрихованы.

 рис. 19      рис. 20

§ 1. Понятие высказывания. Виды высказываний.

Основным (неопределяемым) понятием математической логики является понятие «простого высказывания».

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

Приведем примеры высказываний:

1.  Новгород стоит на Волхове.
2.  Париж – столица Англии.
3.  Карась не рыба.
4.  Число 6 делится на 2 и на 3.
5.  Если юноша окончил среднюю школу, то он получает аттестат зрелости.

Высказывания 1), 4), 5) истинны, а 2) и 3) – ложны.

Очевидно, предложение «Да здравствуют наши спортсмены!» не является высказыванием.

Высказывание, представляющее собой одно утверждение, принято называть простым или элементарным. Примерами элементарных высказываний могут служить высказывания 1) и 2).

Высказывания, которые получаются из элементарных с помощью грамматических связок «не», «и», «или», «если …, то …», «тогда и только тогда», принято называть сложными или составными. Так, высказывание 3) получается из простого высказывания «Карась – рыба» с помощью отрицания «не», высказывание 4) образовано из элементарных высказываний «Число 6 делится на 2», «Число 6 делится на 3», соединенных союзом «и». Высказывание 5) получается из простых высказываний «Юноша окончил среднюю школу», «Юноша получает аттестат зрелости» с помощью грамматической связки «если …,
то …». Аналогично сложные высказывания могут быть получены из простых высказываний с помощью грамматических связок «или», «тогда и только тогда».

В алгебре логики все высказывания рассматриваются только с точки зрения их логического значения, а от их житейского содержания отвлекаются. Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным и ложным.

В дальнейшем будем элементарные высказывания обозначать буквами латинского алфавита: a,b,c,…,x,y,z,…; истинное значение – буквой И или цифрой 1, а ложное значение – буквой Л или цифрой 0.

Если высказывание а истинно, то будем писать а=1, если же ложно, то а=0.

§ 2. Логические операции над высказываниями.

1. ОТРИЦАНИЕ.

Отрицанием высказывания х называется новое высказывание, которое является истинным, если высказывание х ложно, и ложным, если высказывание х истинно.

Отрицание высказывания х обозначается  и читается «не х» или «неверно, что х». Логические значения  высказывания  можно описать с помощью таблицы:

Таблицы такого вида принято называть ТАБЛИЦАМИ ИСТИННОСТИ.

Пусть х высказывание. Так как  также является высказыванием, то можно образовать отрицание высказывания , то есть высказывание , которое называется ДВОЙНЫМ ОТРИЦАНИЕМ высказывания х. Ясно, что логические значения высказываний  и х совпадают.

Например, для высказывания «Река Волхов вытекает из озера Ильмень» отрицанием будет высказывание «Неверно, что река Волхов вытекает из озера Ильмень» или «Река Волхов не вытекает из озера Ильмень», а двойным отрицанием будет высказывание «Неверно, что река Волхов не вытекает из озера Ильмень».

2. КОНЪЮНКЦИЯ (логическое умножение).

Конъюнкцией двух высказываний x, y называется новое высказывание, которое считается истинным, если оба высказывания x, y истинны, и ложным, если хотя бы одно из них ложно (т.е. в остальных случаях).

Конъюнкция высказываний x, y обозначается символом x&y или  (xy), читается «x и y». Высказывания x, y называются  членами конъюнкции. Все возможные логические значения конъюнкции двух высказываний x и y описываются следующей таблицей истинности.

Например, для высказываний «6 делится на 2», «6 делится на 3» их конъюнкцией будет высказывание «6 делится на 2 и 6 делится на 3», которое, очевидно, истинно.

Из определения операции конъюнкции видно, что союз «и» в алгебре логики употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом «и» два высказывания, далекие друг от друга по содержанию, а в алгебре логики рассматривается конъюнкция двух любых высказываний. (Например: «В огороде бузина и в Киеве дядька»).

Из определения операций конъюнкции и отрицания ясно, что высказывание  всегда ложно.

3. ДИЗЪЮНКЦИЯ  (логическое сложение).

Дизъюнкцией двух высказываний х, у называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний х, у истинно, и ложным, если они оба ложны.

Дизъюнкция высказываний х, у обозначается символом х  у, читается «х или у». Высказывания х, у называются членами дизъюнкции. Все возможные логические значения дизъюнкции двух высказываний х и у описываются следующей таблицей истинности:

Например, высказывание «В треугольнике DFE угол D или угол E острый истинно, так как обязательно истинно одно из высказываний: «В треугольнике DFE угол D острый», «В треугольнике DFE угол E острый». В повседневной речи союз «или» употребляется в различном смысле: исключающем и не исключающем. В алгебре логики союз «или» всегда употребляется в не исключающем смысле.

Из определения операций дизъюнкции и отрицания ясно, что высказывание  всегда истинно.

4. ИМПЛИКАЦИЯ.

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

Импликация высказываний x,y обозначается символом  (или  ), читается “если х, то y”или ”из х следует y”. Высказывание х называют УСЛОВИЕМ или ПОСЫЛКОЙ, высказывание y – СЛЕДСТВИЕМ или ЗАКЛЮЧЕНИЕМ,  высказывание  - СЛЕДОВАНИЕМ или ИМПЛИКАЦИЕЙ.

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

x	y	xy
1	1	1
1	0	0
0	1	1
0	0	1

 

Например, высказывание “если число 12 делится на 6, то оно делится на 3”, очевидно, истинно, так как здесь истинна посылка “ Число 12 делится на 6” и истинно заключение “Число 12 делится на 3”.

Употребление слов “если…, то…” в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что, если высказывание х ложно, то высказывание “Если х, то y” вообще не имеет смысла. Кроме того, строя предложение вида “ если х, то y” в обыденной речи, мы всегда подразумеваем, что предложение y вытекает из предложения х. Употребление слов “если…, то…” в математической логике не требует этого, поскольку в ней смысл  содержания высказываний не рассматривается.

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

5. ЭКВИВАЛЕНЦИЯ.

Эквиваленцией (или эквивалентностью) двух высказываний x,y называется новое высказывание, которое считается истинным, когда оба высказывания x,y либо одновременно истинны, либо одновременно ложны. И ложным во всех остальных случаях.

Эквиваленция высказываний x,y обозначается символом (или , реже ~), читается “ для того, чтобы x, необходимо и достаточно, чтобы y”, или “ х тогда и только  тогда, когда у”. Высказывания x, y называются ЧЛЕНАМИ ЭКВИВАЛЕНЦИИ. Логические значения операции эквиваленции описываются следующей таблицей истинности:

x	y	x↔y
1	1	1
1	0	0
0	1	0
0	0	1

 

Например, эквиваленция “Треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда P=Q” является истинной, так как высказывания “Треугольник SPQ с вершиной S и основанием PQ равнобедренный” и  “В треугольнике SPQ с вершиной S и основанием PQ” P=Q” либо одновременно истинны, либо одновременно ложны.

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

§3. Формулы алгебры логики. Вычисление их значений.

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

(xy)   и   x.

Первое из них есть дизъюнкция конъюнкции x,y и отрицания высказывания z, а второе высказывание есть импликация, посылкой которой является высказывание x, а заключением – отрицание дизъюнкции высказывания y и конъюнкции высказываний x,z.

Всякое сложное высказывание, которое может быть получено из элементарных высказываний посредством применения логических операций отрицания, конъюнкции, дизъюнкции, импликации и эквиваленции, называется  ФОРМУЛОЙ АЛГЕБРЫ ЛОГИКИ.

Формулы алгебры логики будем обозначать большими буквами латинского алфавита A, B, C,…,X, Y,Z,…

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

В связи с этим приведенные выше формулы (xy)  и   x могут быть написаны так:    и  x, а также xy   и   x.

Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в неё элементарных высказываний. Например, логическим значением формулы  в случае, если x=1, y=1, z=0 будет истина, т.е. =1.

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

Например, для формулы  таблица истинности имеет вид:

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

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

§4. Равносильные, ТИ и ТЛ формулы алгебры логики. Основные равносильности. (Законы логических операций). Закон двойственности.

Определение.

Две формулы алгебры логики А и В называются РАВНОСИЛЬНЫМИ, если они принимают одинаковые логические  значения на любом наборе входящих в формулы элементарных высказываний. Равносильность формул будем обозначать  знаком , а запись А В означает, что формулы А и В равносильны.

Формула А называется ТОЖДЕСТВЕННО ИСТИННОЙ (или ТАВТОЛОГИЕЙ), если она принимает значение 1 при всех значениях входящих в неё переменных.

Формула называется ТОЖДЕСТВЕННО ЛОЖНОЙ (или ПРОТИВОРЕЧИЕМ), если она принимает значение 0 при всех значениях входящих в неё переменных.

Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула АВ – тавтология, и обратно, если формула АВ – тавтология, то формулы А и В равносильны.

Важнейшие равносильности алгебры логики можно разбить на три группы.

1. Основные равносильности.

    законы   идемпотентности.

                                              - закон противоречия

        - закон исключенного третьего

                                               - закон снятия двойного отрицания

                       законы поглощения

2. Равносильности, выражающие одни логические операции через другие.

1.       4. .  

2. .          5. .   

3. .       6. .

Здесь 3, 4, 5, 6 – законы Моргана.

Ясно, что равносильности 5 и 6 получаются из равносильностей 3 и 4, соответственно, если от обеих  частей последних взять отрицания и воспользоваться законом снятия двойного отрицания.

Таким образом, в доказательстве нуждаются первые четыре равносильности. Докажем одну из них : первую .

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

Пусть теперь  x и y имеют различные логические значения. Тогда будут ложными эквивалентность  и одна из двух импликаций  или . Но при этом будет ложной и конъюнкция .

Таким образом, и в этом случае обе части равносильности имеют одинаковые логические значения.

 Аналогично доказываются равносильности  2 и 4.

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

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

Однако существуют операции, с помощью которых может быть выражена любая из пяти  логических операций, которыми мы пользуемся. Такой операцией является, например, операция “Штрих Шеффера”. Эта операция обозначается символом   и определяется  следующей таблицей истинности:

x	y	xy
1	1	0
1	0	1
0	1	1
0	0	1

3. Равносильности, выражающие основные законы алгебры логики.

1.  - коммутативность конъюнкции.

2.  - коммутативность дизъюнкции.

3.  - ассоциативность конъюнкции.

4.  - ассоциативность дизъюнкции.

5.  - дистрибутивность конъюнкции относительно

            дизъюнкции.

6.  - дистрибутивность дизъюнкции относительно

            конъюнкции.

4. Дополнительные законы.

1. Закон склеивания (расщепления).

, ;

,  .

2. Законы поглощения.

;  .

3. Закон Блейка- Порецкого.

.

4. Закон свертки логического выражения (СЛВ).

.

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

Определение.

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

Имеет место следующий закон двойственности: если формулы А и В равносильны, то равносильны и им двойственные формулы, т.е. А*  В*.

§5. Равносильные преобразования формул.

Используя равносильности, приведенные в §4, можно часть формулы или всю формулу заменить равносильной ей формулой. Такие преобразования формул называются равносильными. (Аналог тождественным преобразованиям в арифметике, алгебре и тригонометрии).

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

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

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

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

Рассмотрим ряд примеров равносильных преобразований.

Пример 1. Доказать равносильность .

Пример 2. Упростить формулу .

.

Пример 3. Доказать ТИ формулы .

Пример 4.  Доказать законы склеивания.

Пример 5.  Доказать закон  Блейка - Порецкого.

Пример 6. Доказать закон свертки логического выражения.

§6. Алгебра Буля.

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

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

      (7)  (16)

         (П)          (17)

         (П)   и т.д.

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

Рассмотрим непустое множество М элементов любой природы: {x; y; z;…}, в котором определены отношение “=” (равно) и три операции: “+”( сложение), “·”                   ( умножение) и “-”  (отрицание), подчиняющиеся следующим аксиомам:

Коммутативные законы:

1а.    1б.  

Ассоциативные законы:

2а. .  2б..

Дистрибутивные законы:

3а.  3б. .

Законы идемпотентности

4а.     4б.

Закон двойного отрицания:

5. .

Законы де Моргана:

6а.    6б. .

Законы поглощения:

7а. .   7б. .

Такое множество М называется БУЛЕВОЙ АЛГЕБРОЙ.

Если под основными элементами x,y,z,…подразумевать высказывания, под операциями “+”, “·”, “–“ дизъюнкцию, конъюнкцию, отрицание соответственно, а знак равенства рассматривать как знак равносильности, то, как следует из равносильностей рассмотренных выше трех групп, все аксиомы булевой алгебры выполняются.

В тех случаях, когда для некоторой системы аксиом удается подобрать конкретные объекты и конкретные соотношения между ними так, что все аксиомы выполняются, говорят, что найдена ИНТЕРПРЕТАЦИЯ ( ИЛИ МОДЕЛЬ) данной системы аксиом.

Значит, алгебра логики является интерпретацией булевой алгебры. Алгебра Буля имеет и другие интерпретации. Например, если под основными элементами x,y,z,…множества М подразумевать множества, под операциями “+”, “·”,
“–“ объединение, пересечение, дополнение соответственно, а под знаком равенства – знак равенства множеств, то мы приходим к алгебре множеств. Нетрудно убедиться, что  в алгебре множеств все аксиомы алгебры Буля выполняются.

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

§7. Функции алгебры логики.

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

Например, формула  является функцией трех переменных f(x,y,z). Особенностью этой функции является то обстоятельство, что ее аргументы принимают одно из двух значений: ноль или единицу, и при этом функция также принимает одно из двух значений: ноль или единицу.

Определение.

Функцией алгебры логики n переменных (или функций Буля) называется функция n переменных, где каждая переменная принимает два значения: 0 и 1, и при этом функция может принимать только одно из двух значений: 0 или 1.

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

Выясним, каково число функций n переменных. Очевидно, каждую функцию алгебры логики (как и формулу алгебры логики) можно задать с помощью таблицы истинности, которая будет содержать 2n строк. Следовательно, каждая функция n переменных принимает 2n значений, состоящих из нулей и единиц. Таким образом, функция n переменных полностью определяется набором значений из нулей и единиц длины 2n. Общее же число наборов, состоящих из нулей и единиц, длины 2n равно 22n. Значит, число различных функций алгебры логики n переменных равно 22n.

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

Рассмотрим таблицу истинности для различных функций одной переменной. Она, очевидно, имеет вид:

x	f1(x)	f2(x)	f3(x)	f4(x)
1	1	1	0	0
0	1	0	1	0

Из этой таблицы следует, что две функции одной переменной будут постоянными: f1(x)=1, f4(x)=0, а .

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

x	y	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15	f16
1	1	1	1	1	1	0	1	1	0	0	0	1	0	0	0	1	0
1	0	1	1	1	0	1	1	0	0	1	1	0	0	0	1	0	0
0	1	1	1	0	1	1	0	0	1	1	0	1	0	1	0	0	0
0	0	1	0	1	1	1	0	1	1	0	1	0	1	0	0	0	0

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

,  ,  ,  ,

, ,  ,  ,

, ,  ,  ,

, ,  ,  .

§8. Нормальные формы функций.

При решении ряда задач, связанных с использованием формул алгебры высказываний, важную роль играют формулы, построенные особым образом из высказывательных переменных с помощью только операций дизъюнкции, конъюнкции и отрицания и называемые ДИЗЪЮНКТИВНЫМИ и КОНЪЮНКТИВНЫМИ НОРМАЛЬНЫМИ ФОРМАМИ (ДНФ и КНФ).

8.1 Элементарные дизъюнкции и конъюнкции.

Пусть задана система высказывательных переменных

 (x1,x2,…,xn).        (1)

Элементарной  дизъюнкцией высказывательных переменных из системы (1) называется дизъюнкция некоторых высказывательных переменных этой системы или их отрицаний.

ЭЛЕМЕНТАРНОЙ КОНЪЮНКЦИЕЙ называется конъюнкция некоторых высказывательных переменных этой системы или их отрицаний.

Если в элементарную дизъюнкцию (конъюнкцию) входит каждое высказывательное переменное из системы (1) (с отрицанием или без него) и притом только один раз, то она называется ПОЛНОЙ ЭЛЕМЕНТАРНОЙ ДИЗЪЮНКЦИЕЙ (КОНЪЮНКЦИЕЙ).

Из “n” высказывательных переменных можно образовать 2n всевозможных неэквивалентных полных элементарных дизъюнкций и столько же полных элементарных конъюнкций. Каждая полная элементарная дизъюнкция  только для одного варианта значений высказывательных переменных системы (1) принимает значение, равное нулю, а именно – когда каждое высказывательное переменное xi, не находящееся в  под знаком отрицания, равно нулю, а каждое отрицательное – единице.

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

Так, нулями элементарных дизъюнкций (2) являются: (0,0,0), (0,0,1), (0,1,0), (1,0,0), (0,1,1), (1,0,1), (1,1,0), (1,1,1).

Если обратиться к полным элементарным конъюнкциям, то можно обнаружить, что каждая из них только один раз принимает значение, равное единице – когда неотрицаемое переменное равно единице, а отрицаемое – нулю. Такую  систему значений высказывательных переменных назовем ЕДИНИЦЕЙ соответствующей ПОЛНОЙ ЭЛЕМЕНТАРНОЙ КОНЪЮНКЦИИ.

8.2 Нормальные формы.

Определение 8.1.

Формула F называется КОНЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (КНФ) от высказывательных переменных системы (1), если она является конъюнкцией элементарных дизъюнкций, образованных из высказывательных переменных этой системы.

Формула F называется ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (ДНФ) от высказывательных переменных системы (1), если она является дизъюнкцией элементарных конъюнкций, образованных из этих переменных.

Это определение, учитывая закон двойственности, можно сформулировать иначе: формула F называется ДНФ от высказывательных переменных системы (1), если двойственная ей формула F* является КНФ, образованной из этих переменных.

Утверждение 3.

Для всякой формулы F существуют эквивалентные ей КНФ и ДНФ.

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

Определение 8.3

Формула F называется СОВЕРШЕННОЙ КОНЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (СКНФ) от высказывательных переменных системы (1) x1,…,xn, если она является конъюнкцией различных полных элементарных дизъюнкций от этих переменных (при этом равенство дизъюнкций понимается с точностью до порядка членов).

Определение 8.4

Формула F называется СОВЕРШЕННОЙ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (СДНФ) от высказывательных  переменных системы (1) x1,…,xn, если она является дизъюнкцией различных полных элементарных конъюнкций от этих переменных.

Или  иначе: если двойственная ей формула F* является СКНФ. Из замечания 2 следует, что СДНФ не может быть тождественно ложным высказыванием.

8.4 Правила приведения произвольной формулы алгебры логики к совершенной нормальной форме.

А. Правила приведения к СДНФ.

Из определения 8.4 следует, что формула F является СДНФ, если она отвечает следующим условиям (иначе, если она обладает следующими свойствами, называемыми “СВОЙСТВАМИ СОВЕРШЕНСТВА ”):

а) в ней нет двух одинаковых слагаемых (дизъюнктивных членов);

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

в) никакое слагаемое не содержит переменную вместе с её отрицанием;

г) в каждом слагаемом содержится в качестве множителя либо каждая из переменных , либо её отрицание , где .

Условия а) ÷г) являются, таким образом, необходимыми и достаточными для того, чтобы ДНФ являлась СДНФ. Вместе с тем, эти условия дают возможность высказать правила, позволяющие приводить с помощью равносильных преобразований любую не тождественно ложную формулу к СДНФ, которая является для неё единственной. Итак, приведем эти правила.

Пусть дана произвольная формула F

Проделаем пять операций, которые приведут формулу к СДНФ.

1.  Приведем её с помощью равносильных преобразований к какой-либо ДНФ.
2.  Если какое-нибудь из слагаемых этой ДНФ, например, В не содержит переменную , то заменим его суммой . Эта замена представляет собой равносильное преобразование, так как  (см. также формулу расщепления R). Проделав операции по п.2), мы удовлетворили требованиям п. г) свойств совершенства.
3.  Если в полученном выражении окажутся одинаковые слагаемые, то, удалив все, кроме одного из них ( в силу  закона идемпотентности (8)), мы получим опять равносильное выражение. Здесь мы удовлетворили п. а) свойств совершенства.
4.  Если после этого в некоторых слагаемых окажется по несколько одинаковых множителей, то лишние (в силу закона идемпотентности (9)) удаляем. Таким образом, мы удовлетворяем п. б) свойств совершенства.
5.  Наконец, удаляем все те слагаемые, которые содержат какую-нибудь переменную  вместе со своим отрицанием , так как, в силу закона противоречия (15), они являются тождественно ложными выражениями – удовлетворили п. в) свойств совершенства.

Если бы все слагаемые оказались таковыми, то и вся ДНФ была бы тождественно ложной. А тогда это значило бы, что исходная формула F – тождественно ложная формула и не имеет СДНФ. Именно поэтому мы утверждаем: если формула F не является тождественно ложной, то в её произвольной ДНФ  должны присутствовать слагаемые, удовлетворяющие условию п. в)  свойств совершенства.

После удаления всех слагаемых, содержащих какую-нибудь переменную вместе с её отрицанием, мы получили ДНФ, удовлетворяющую всем свойствам совершенства, т.е. СДНФ.

Заметим, что нам нет необходимости знать заранее, является ли формула F тождественно ложной или нет. Проделывая указанные операции, мы это выясним после того, как удалим все слагаемые, содержащие какую-нибудь  переменную вместе с её отрицанием. Если  формула F – тождественно ложная формула, то все слагаемые будут удалены, и мы не получим СДНФ.  

Б. Правила приведения к СКНФ.

Из определения 8.3 следует, что СКНФ обладает следующими свойствами совершенства (иными словами, СКНФ формулы F называется её КНФ, удовлетворяющая следующим условиям):

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

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

в) ни один множитель не содержит какую-нибудь переменную  вместе с её отрицанием ;

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

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

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

Пусть дана произвольная формула F.

Проделаем несколько операций, которые приведут формулу к СКНФ.

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

2) Если в полученной КНФ какой-либо дизъюнктивный сомножитель  В не содержит некоторую переменную  (т.е. не удовлетворяет условию совершенства п. г)), то, используя равносильность  , элементарную дизъюнкцию В заменяем на две элементарных дизъюнкции:  , каждая из которых уже содержит переменную  - удовлетворили  условию совершенства п. г).

3) Если  в КНФ входят две одинаковых  элементарных дизъюнкции В, то лишнюю отбрасываем, поскольку  - удовлетворили условию совершенства п. а).

8.6 Способ составления СНФ для произвольной формулы алгебры логики по таблице истинности.

Пусть некоторая функция f трёх переменных задана следующей таблицей истинности:

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

Проделаем следующие операции.

1) Выбираем наборы значений переменных, для которых :

 (0; 1; 1),  (1; 0; 1), (1; 1; 0), (1; 1; 1).

2) Каждому из этих наборов сопоставляем (ставим в соответствие) конъюнкцию переменных  или их отрицаний, принимающую при этих значениях переменных значение 1:

набору (0; 1; 1) – конъюнкцию ,

набору (1; 0; 1) – конъюнкцию ,

набору (1; 1; 0) – конъюнкцию ,

набору (1; 1; 1) – конъюнкцию .

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

.

Это выражение является, очевидно, СДНФ данной функции.

§9. Проблема разрешимости.

Все формулы алгебры логики делятся на тождественно истинные, тождественно ложные и выполнимые. Определения тождественно истинных и тождественно ложных формул даны выше.

Формулу F называют ВЫПОЛНИМОЙ, если она принимает значение “истина” (1) хотя бы на одном наборе значений входящих в неё переменных и не является тождественно истинной.

В связи с этим возникает задача получения ответа на вопрос: к какому классу относится данная формула?

Эта задача называется ПРОБЛЕМОЙ РАЗРЕШИМОСТИ.

Очевидно, что проблема разрешимости алгебры логики разрешима.

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

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

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

Применим критерий тождественной истинности к формуле . Если окажется, что формула  – тождественно истинная, то задача решена. Если же окажется, что  формула  не тождественно истинна, то применим критерий   тождественной истинности к формуле . Если окажется,  что формула - тождественно истинная, то ясно, что формула  - тождественно ложная, и задача решена. Если же формула  не тождественно истинная, то остаётся  единственный возможный результат: формула  выполнима.

Установим теперь критерий тождественной истинности произвольной формулы алгебры логики. С этой целью предварительно сформулируем и докажем критерий тождественной истинности элементарной дизъюнкции.

Теорема 1.

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

Доказательство необходимости.

Пусть элементарная дизъюнкция тождественно истинна, но в неё одновременно не входит некоторая переменная и её отрицание. Придадим каждой переменной, входящей в элементарную дизъюнкцию без знака отрицания, значение “ложь”, а каждой переменной, входящей в элементарную дизъюнкцию под знаком отрицания  - значение “истина”. Тогда, очевидно, вся элементарная дизъюнкция примет значение “ложь”, что противоречит условию.

Доказательство достаточности.

Пусть теперь элементарная дизъюнкция содержит переменную и её отрицание. Так как , то и вся элементарная дизъюнкция будет тождественно истинной.

Критерий тождественной истинности элементарной дизъюнкции позволяет сформулировать и доказать критерий тождественной истинности  произвольной формулы алгебры логики.

Теорема 2.

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

Доказательство необходимости.

Пусть  - тождественно истинна. Тогда и КНФ  - тождественно истинна.

Но КНФ , где  - элементарные дизъюнкции ().

Так как КНФ 1, то 1, . Но тогда по теореме 1 каждая элементарная дизъюнкция  содержит переменную и её отрицание.

Доказательство достаточности.

Пусть любая элементарная дизъюнкция , входящая в КНФ  , содержит переменную и её отрицание. Тогда по теореме 1 1, .

При этом  и КНФ 1.

Например, выясним, является ли формула  тождественно истинной.

Так как , то ясно, что каждая элементарная дизъюнкция  и , входящая в КНФ , содержит переменную и её отрицание. Следовательно, 1.

Аналогично имеют место теоремы, дающие критерии тождественной ложности элементарной конъюнкции и любой формулы алгебры логики.

Теорема 3.

Для того, чтобы элементарная конъюнкция была тождественно ложной, необходимо и достаточно, чтобы в ней содержалась переменная и её отрицание.

Теорема 4.

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

Рассмотрим некоторые приложения алгебры логики.

 

Математи́ческая ло́гика (теоретическая логика, символическая логика) — раздел математики, изучающий доказательства и вопросы оснований математики. «Предмет современной математической логики разнообразен.»[1] Согласно определению П. С. Порецкого, «математическая логика есть логика по предмету, математика по методу». Согласно определению Н. И. Кондакова, «математическая логика — вторая, после традиционной логики, ступень в развитии формальной логики, применяющая математические методы и специальный аппарат символов и исследующая мышление с помощью исчислений (формализованных языков).»[2] Это определение соответствует определению С. К. Клини: математическая логика — это «логика, развиваемая с помощью математических методов».[3] Также А. А. Марков определяет современную логику «точной наукой, применяющей математические методы».[4] Все эти определения не противоречат, а дополняют друг друга.

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

Важную роль в математической логике играют понятия дедуктивной теории и исчисления. Исчислением называется совокупность правил вывода, позволяющих считать некоторые формулы выводимыми. Правила вывода подразделяются на два класса. Одни из них непосредственно квалифицируют некоторые формулы как выводимые. Такие правила вывода принято называть аксиомами. Другие же позволяют считать выводимыми формулы A, синтаксически связанные некоторым заранее определённым способом с конечными наборами выводимых формул. Широко применяемым правилом второго типа является правило modus ponens: если выводимы формулы A и , то выводима и формула B.

Отношение исчислений к семантике выражается понятиями семантической пригодности и семантической полноты исчисления. Исчисление И называется семантически пригодным для языка Я, если любая выводимая в И формула языка Я является верной. Аналогично, исчисление И называется семантически полным в языке Я, если любая верная формула языка Я выводима в И.

Математическая логика изучает логические связи и отношения лежащие в основе логического (дедуктивного) вывода с использованием языка математики[источник не указан 76 дней].

Многие из рассматриваемых в математической логике языков обладают семантически полными и семантически пригодными исчислениями. В частности, известен результат К. Гёделя о том, что так называемое классическое исчисление предикатов является семантически полным и семантически пригодным для языка классической логики предикатов первого порядка. С другой стороны, имеется немало языков, для которых построение семантически полного и семантически пригодного исчисления невозможно. В этой области классическим результатом является теорема Гёделя о неполноте, утверждающая невозможность семантически полного и семантически пригодного исчисления для языка формальной арифметики.

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

Содержание [убрать]  1 Разделы математической логики  2 См. также  3 Примечания  4 Литература  5 Ссылки

[править] Разделы математической логики

•  Алгебра логики
•  Логика высказываний
•  Теория доказательств
•  Теория моделей

[править] См. также

•  Формальная логика
•  Неполнота математики
•  Формальная система
•  Теорема Гёделя о неполноте
•  Недоказуемые утверждения
•  Аксиома
•  Граница множества
•  Логическое программирование
•  Доказательное программирование
•  Логика в информатике
•  язык Пролог

[править] Примечания

1.  ↑ С. И. Адян, Математическая энциклопедия, М.: «Советская энциклопедия», т.3, с. 568, 571.
2.  ↑ Н. И. Кондаков, Логический словарь-справочник, М.: «Наука», 1975, с. 259.
3.  ↑ С. К. Клини, Математическая логика, М., 1973, с.12.
4.  ↑ А. А. Марков, Большая советская энциклопедия, Изд. 3, Предмет и метод современной логики.

[править] Литература

•  Марков А. А.. Элементы математической логики. М.: Изд-во МГУ, 1984.
•  Новиков П. С. Элементы математической логики. 2-ое изд. М.: Наука, 1973. — 400 с.
•  Столл Р. Р. Множества. Логика. Аксиоматические теории. М.: Просвещение, 1968. — 232 с.
•  Стяжкин Н. И. Формирование математической логики. М.: Наука, 1967. 508 с.
•  Шенфилд Дж. Математическая логика. М.: Наука, 1975.

[править] Ссылки

•  Н. К. Верещагин, А.Шень. Лекции по математической логике и теории алгоритмов (электронные версии трех частей книги)
•  Логика математическая
•  Математическая логика и цифровая вычислительная техника Меркухин Е.Н

http://www.mathlog.h11.ru/vyscaz.htm

. Исчисление высказываний.

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

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

§ 1. Понятие формулы исчисления высказываний.

Исчисление высказываний – это аксиоматическая логическая система, интерпретацией которой является алгебра высказываний.

Описание всякого исчисления включает в себя  описание символов этого исчисления (алфавита), формул, являющихся конечными конфигурациями  символов, и определение выводимых формул.

Алфавит исчисления высказываний состоит из символов трех категорий:

1.  Символы первой категории: Эти символы будем называть переменными высказываниями.
2.  Символы второй категории:  они носят общее название логических связок. Первый из них – знак дизъюнкции или логического сложения, второй – знак конъюнкции или логического умножения, третий – знак  импликации  или логического следования и четвертый – знак отрицания.
3.  Третью категорию составляет  пара символов (  ), называемая скобками.

Других символов исчисление высказываний не имеет.

Формулы исчисления высказываний представляют  собой последовательности символов алфавита исчисления  высказываний. Для обозначения формул будем пользоваться большими буквами латинского алфавита. Эти буквы не являются символами исчисления. Они представляют собой только условные обозначения формул.

Определение формулы исчисления высказываний.

1.  Всякая переменная  является формулой.
2.  Если А и В- формулы , то слова  - тоже формулы.
3.  Никакая другая строчка символов не является формулой.

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

Приведем примеры формул исчисления  высказываний.

Переменные  высказывания   являются формулами согласно п.1 определения формулы. Но тогда слова  являются формулами согласно           п.2 определения. По этой же причине будут формулами слова:

Очевидно, не являются формулами слова: поскольку  одни из них не взяты в скобки, в других скобка лишь одна,…

Одновременно с понятием формулы вводится понятие подформулы или части формулы.

1. Подформулой элементарной формулы является  она сама.

1.  Если формула имеет вид , то ее  подформулами являются: она сама, формула А и все подформулы формулы А.
2.  Если формула имеет вид (А*В)(здесь и в дальнейшем под символом * будем понимать любой из трех символов ), то ее подформулами являются: она сама, формулы А и В и все подформулы формул А и В.

Например, для формулы  ее подформулами будут:

- подформула нулевой глубины,

-подформулы первой глубины,

            -подформулы второй глубины,

-подформулы третьей глубины,

-подформула четвертой глубины.

Таким образом, по мере “погружения вглубь структуры формулы”  мы выделяем подформулы все большей глубины.

Очевидно, что на самой большой глубине находятся лишь элементарные формулы. Однако элементарные формулы могут быть  и на других глубинах.

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

В связи с этими правилами формулы  будем писать соответственно.

§ 2. Определение доказуемой (выводимой) формулы.

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

Определение доказуемых формул имеет тот же характер , что и определение формулы.

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

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

Система аксиом исчисления высказываний.

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

Первая группа аксиом (содержащая только импликацию).

: .                                :.

Вторая группа аксиом (к импликации присоединилась конъюнкция):

:              : .          : .

Третья  группа  аксиом (к импликации присоединилась дизъюнкция):

:             :          : .

Четвертая  группа  аксиом (к импликации присоединилось отрицание):

: :                 :

1.  Правила вывода.

1 Правило подстановки(ПП).

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

Операция замены в формуле А переменной х формулой В, носит название подстановки и символически записывается так:

или .

Уточним сформулированное правило:

а)  если формула А есть собственно переменная х , то подстановка  дает , очевидно, В;

б) если формула А есть переменная y , отличная от х ,то подстановка  дает А;

в)подстановка формулы В вместо х  в отрицание формулы А  есть отрицание подстановки , т. е.  подстановка  дает;

г) если А1 и А2- некоторые формулы, то подстановка  дает *, где через символ * обозначен любой из символов операций конъюнкция, дизъюнкция или отрицание

Если А- выводимая (доказуемая ) формула, то будем писать, как и ранее, ├А. Тогда ПП можно записать схематически следующим образом:

├А____  .

├

И читается эта запись так: “Если формула А выводима (доказуема), то выводима (доказуема) и формула .

2 Правило заключения (ПЗ).

Если формулы А и А→В выводимы (доказуемы) в исчислении высказываний, то формула В также выводима (доказуема). Схематическая запись этого правила имеет вид:

├А;├А→В                           (Modus ponens)

                                           ├В

Правомерность этого правила очевидна: если импликация и  посылка истинны, то заключение в импликации может быть только истинным(см. таблицу истинности операции “импликация”).

1.   Определение выводимой (доказуемой ) формулы.

а) Всякая аксиома является доказуемой формулой.

б)Формула, полученная из доказуемой формулы путем применения подстановки вместо переменной х  произвольной формулы В, есть доказуемая формула.

в) Формула В, полученная из доказуемых формул А и   путем применения ПЗ, есть доказуемая формула.

г) Никакая другая формула исчисления высказываний не считается доказуемой .

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

§3. Производные правила вывода.

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

1.  Правило сложной (одновременной) подстановки (СПП).

Пусть А – доказуемая формула; - переменные, а - любые формулы ИВ. Тогда результат одновременной подстановки в формулу А вместо  соответственно формул  является доказуемой формулой.

Схематично операция СПП записывается так:

├А______

├

Так, в рассмотренном выше  примере  вместо шагов 4-5-6 и 9-10-11 можно было сразу применить СПП и тогда вместо 12 получим желаемый результат за 8 ходов:

1)  . . . .( )     (1)

2)  . . .    (2)

3)  . . .( )                   (3)

4)        . . .        (4)

5)     (2),(4), ПЗ .                (5)

6)    . . . ()         (6)

7)                                   (7)    

8)             . . .             (5), (7), ПЗ                (8)

1.  Правило сложного заключения.

Правило сложного заключения также допускает обобщение.

Второе производное правило, получаемое в результате такого обобщения, применяется к формулам вида

и формулируется так :

если формулы     и    доказуемы, то и формула  L доказуема.   

Правило сложного заключения схематично записывается так:

├А1, ├А2, …,├Аn, ├A1→(A2→(A3→(...(An→L) …)))

├ L

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

1.  Правило силлогизма.

Если доказуемы формулы А→В и В→С, то доказуема формула А→С , т. е.

├А→В,├В→С

├А→С

1.  Правило контр позиции.

Если  доказуема формула А→В, то доказуема формула , т. е.

├ А →В

├

На примере этого правила покажем, как доказываются такие утверждения в исчислении высказываний. Сделаем одновременную подстановку , получим доказуемую формулу ├(А→В)→├().          (1)

Но по условию  доказуема формула ├А→В.      (2)

Из формул (2) и (1) по правилу заключения имеем  ├.

1.  Правило снятия двойного отрицания.

а) Если доказуема формула , то доказуема формула .

б) Если доказуема формула , то доказуема формула .

Схематичная запись :      ├ А →             и         ├ →В

                                          ├                         ├     .

§4.Понятие выводимости формул из совокупности формул.

Будем рассматривать конечную совокупность формул Н={А1,А2,…,Аn}.

Определение формулы, выводимой из совокупности Н.

1)Всякая формула Аi,является формулой, выводимой из Н.

2) Всякая доказуемая формула  выводима из Н.

3) Если формулы С и С→В выводимы из совокупности Н, то формула В также выводима из Н.

Если  некоторая формула В выводима из совокупности Н, то это записывают так: Н├В.

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

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

Пример.

Доказать, что из совокупности формул Н={А ,В} выводима формула .

Так как А и В, то по определению выводимой формулы

Н├А,                                     (1)  

Н├В.                (2)

Возьмемксиомы и , и выполним подстановки и .

В результате получим доказуемые формулы, которые выводимы из Н по определению выводимой формулы, т. е.

Н├(А→А)→((А→В)→(А)),            (3)

Н├В→(А→В),              (4)

Так как формула А→А доказуема, то Н├А→А.          (5)

Из формул (5) и (3) по правилу заключения получаем:                                                          Н├(А→В)→(А)).              (6)

Из формулы (2) и (4) по правилу заключения получаем:               Н├А→В.           (7)

Из формул (7) и (6) по правилу заключения получаем:        Н├А.      (8)

И, наконец,  из формул (1) и (8) получаем:

                Н├             (9)

Ясно, что при доказательстве выводимости формулы из совокупности формул можно пользоваться не только основным правилом заключения, но и правилом сложного заключения. Тогда, пользуясь этим правилом , предложение (9) можно получить из предложений (5), (7), (1) и (3).

§5. Понятие вывода.

Определение.

Выводом из конечной совокупности формул Н называется всякая конечная последовательность  формул В1,В2,…,Вк, всякий член которой удовлетворяет одному из следующих трех условий:

1.  он является одной из формул совокупности Н,

          2)  он является доказуемой формулой,

3) он получается по правилу заключения из двух любых предшествующих  членов последовательности В1,В2,…,Вк.

Как было показано в предыдущем примере, выводом из совокупности формул Н={А,В} является конечная последовательность формул:

А, В, (А→А)→((А→В)→(А)), (А→В), А→А, (А→В)→(А)), А→В, А, . (см. формулы 1,2,3,7,5,6,8).

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

А, В, (А→А)→((А→В)→(А)), В→(А→В), А→А, А→В, . (см. формулы 5, 7, 1, 3).

Из определения выводимой формулы и вывода из совокупности формул следуют очевидные свойства вывода:

1)Всякий начальный отрезок вывода из совокупности  Н есть вывод из Н.

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

3)Всякий член вывода из совокупности Н является формулой,  выводимой из Н. Всякий вывод из Н является выводом  его последней формулы.

4)Если (включено), то всякий вывод из Н является выводом из W.

5)Для того, чтобы формула В была выводима из совокупности Н, необходимо и достаточно, чтобы существовал вывод этой формулы из Н.

§6. Правила выводимости.

Эти правила непосредственно следуют из свойств вывода с использованием ПП и ПЗ.

Пусть Н и W – две совокупности формул исчисления высказываний. Будем обозначать  через Н, W их объединение, т. е. Н,W=.

В частности, если совокупность W состоит из  одной формулы С, то будем записывать объединение  в виде Н,С.

Укажем основные правила выводимости:

    1.  H ├ A              Это правило следует непосредственно из определения вывода

                H,W├A          из совокупности формул : “Если А выводима из Н, то она вы-     

                                              водима из  ”.

   2. H,C ├ A,H├C  

                    H├A          .

   3. H,C ├ A, W├C  

                    H,W├A       .

   4. H ├ C→A  

                 H,C├A    .

             5. Теорема дедукции:                  H, C├ A  .

                                                                     H├C→A

 5A. Обобщенная теорема дедукции:                                    {C1, C1, …, Ck}├ A  

                                                                             ├C1 →(C2→(C3→…(Ck→A)…))

  6. Правило введения конъюнкции:                  H├A,H├B   (показано в примере §4).

                                                                              H├

  7. Правило введения дизъюнкции:                  H,A├C;Н,B├C   .

                                                                                 H,├C

§7. Доказательство некоторых законов логики.

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

1.  Закон перестановки посылок.

├(x→(y→z)) →(y→(x→z)).        (1)

Доказательство:

Можно показать, что (аналогично тому, как это делалось в примере §4) из совокупности формул Н={x→(y→ z ), y, x}  следует вывод x→(y→ z), y, x, y→ z, z, т. е. из совокупности Н выводима формула z.  Тогда по обобщенной теореме дедукции доказуема формула (1). И тогда по ПЗ из закона перестановки посылок вытекает правило перестановки посылок в доказуемых формулах: ├(x→(y→ z))   

                           ├(y→(x→ z)).        (2)

Действительно, если ├x→(y→ z), (2), то из (1) и (2) по правилу заключения следует ├y→(x→z).                              

1.  Закон  соединения посылок.(формула (25) законов логики высказываний).

├(x→(y→ z)) →(→z).        (3)

Доказательство:

Можно показать, что из совокупности формул Н={x→(y→ z ), }  следует вывод x→(y→ z),  , → х, → y, x, y, y→ z, z, т. е. из совокупности Н выводима формула z.  Тогда по обобщенной теореме дедукции доказуема формула (3).

Из закона соединения  посылок вытекает правило соединения посылок в доказуемых формулах: ├(x→(y→z))   

       ├→z.          (4)

Действительно, если ├x→(y→z), (4), то из (3) и (4) по правилу заключения следует ├→z.                              

1.  Закон разъединения посылок (формула (25)) .

├(→z) →(x→(y→z)).         (5)

Так как  из совокупности формул Н={x, y, →z}  следует вывод x, y, →z,  , z, то из  совокупности  формул Н выводима формула z.  Тогда по обобщенной теореме дедукции доказуема формула (5).

Из закона разъединения  посылок вытекает правило разъединения посылок в доказуемых формулах: ├  → z   

                    ├х→(y→z).        (6)

Действительно, если ├→z)), (6), то из (5) и (6) по правилу заключения следует

├х→(y→z).

 

1.  ├х→().          (7)

Доказательство:

Сделаем подстановки в аксиомы и :   и .

В результате получим доказуемые формулы:

├х→(), (8)  и ├.        (9)

Из формул (8)и (9)по правилу силлогизма следует : ├.

Используя закон соединения посылок, получим: ├.

Используя правило снятия двойного отрицания, получим : ├.

И, наконец, применяя закон разъединения посылок, получим  (7).

5. Закон исключенного третьего:      ├.

Доказательство:

Воспользуемся  доказуемой формулой ├ .     (10)

и, сделав  в ней подстановку  , получим :

├.           (11)

Также сделаем подстановку в формуле (7), заменяя на  , а y на :

├().           (12)

Используя закон соединения посылок, будем иметь : ├ .    (13)

Из формул (11) и (13) по правилу силлогизма получаем ├.     (14)

Из формулы (14) по правилу контрапозиции следует├ .

Используя оба правила снятия двойного отрицания, получаем  ├     (15)

Пусть теперь y- любая доказуемая формула R, тогда из формул ├R, ├Rпо правилу заключения получаем ├.

6.├. Примем этот закон без доказательства.

§8. Связь между алгеброй высказываний и исчислением высказываний.

Формулы исчисления высказываний можно интерпретировать как формулы алгебры высказываний. Для этого будем трактовать переменные исчисления высказываний как переменные алгебры высказываний, т. е. переменные в содержательном смысле, принимающие два значения: истина и ложь (1 и 0).

Операции  определим так же, как в алгебре высказываний.

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

Введем понятие значения формулы исчисления высказываний. Пусть А- формула исчисления высказываний, х1,х2,…,хn- попарно различные переменные, среди которых находятся все переменные, входящие в формулу А. Обозначим через а1, а2,…,аn набор значений этих переменных, состоящих из 1 и 0, длины n. Очевидно, что вектор (а1, а2,…,аn) имеет  2n значений.

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

Теорема 1.

Каждая формула, доказуемая в исчислении высказываний, является тождественно истинной в алгебре высказываний.

Формулировка этой теоремы содержит в себе три положения:

1)Каждая аксиома исчисления высказываний – тождественно истинная формула в алгебре высказываний.

2)Правило подстановки, примененное к тождественно истинным формулам, приводит к тождественно истинным формулам.

3)Правило заключения, примененное к тождественно истинным формулам, приводит к тождественно истинным формулам.

Теорема 2.( о выводимости).

Пусть А –некоторая формула исчисления высказываний; х1,х2,…,хn – набор переменных, содержащих все переменные, входящие в формулу А; а1, а2,…,аn – произвольный фиксированный набор значений этих переменных. Обозначим через Н конечную совокупность формул

, где

Тогда:

1.  Если Ra1,a2,..,an(A)=1, то H├A .
2.  Если Ra1,a2,..,an(A)=0, то H├, где Ra1,a2,..,an(A)–значение формулы А на наборе а1, а2,…,аn.

Теорема 3.

 Каждая тождественно истинная формула алгебры высказываний доказуема в исчислении высказываний.

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

Всякая аксиоматическая теория для ее обоснования требует рассмотрения четырех проблем:

1.  проблемы разрешимости,
2.  проблемы непротиворечивости,
3.  проблемы полноты,
4.  проблемы независимости.

Проблема разрешимости исчисления высказываний.

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

Имеет место теорема: проблема разрешимости для исчисления высказываний разрешима.

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

Пусть А – любая формула исчисления высказываний, а х1,х2,…,хn – перечень входящих в нее переменных. Вычислим Ra1,a2,..,an(A) на всех наборах значений а1, а2,…,аn входящих в нее переменных. Если при этом Ra1,a2,..,an(A)=1, на всех наборах а1, а2,…,аn, то формула А – тождественно истинна, и, значит, по теореме о доказуемости тождественно истинной формулы она доказуема.

Если же существует набор значений переменных  такой, что , то формула А – не тождественно истинная, и, значит, по теореме 1 §8 она не доказуема.

2. Проблема непротиворечивости исчисления высказываний.

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

Иначе говоря, аксиоматическое исчисление называется непротиворечивым, если в нем не существует такая формула А, что доказуема как формула А, так и формула .

Проблема непротиворечивости заключается в выяснении вопроса: является данное исчисление непротиворечивым или нет?

Если в исчислении обнаруживаются доказуемые формулы вида А и , то такое исчисление называется противоречивым. В рассмотренном нами исчислении высказываний невозможно вывести одновременно формулы А и , т.е. это исчисление высказываний непротиворечиво.

3.Проблема полноты исчисление высказываний.

Определение 1.

Аксиоматическое исчисление высказываний называется полным в узком смысле, если добавление к списку его аксиом любой недоказуемой в исчислении формулы в качестве новой аксиомы приводит к противоречивому исчислению.

Определение 2.

Исчисление высказываний называется полным в широком смысле, если любая тождественно истинная формула в нем доказуема.

Из этих определений следует, что проблема полноты исчисления высказываний содержит два вопроса:

1.  Можно ли расширить систему аксиом аксиоматического исчисления путем добавления к ней в качестве новой аксиомы какой-нибудь недоказуемой в этом исчислении формулы?
2.  Является ли всякая тождественно истинная формула алгебры высказываний доказуемой  в исчислении высказываний?

Рассмотренное нами исчисление высказываний полно как в узком смысле, так и в широком.

4.Проблема независимости аксиом исчисления высказываний.

Для всякого аксиоматического исчисления возникает вопрос о независимости его аксиом. Вопрос этот ставится так : можно ли какую-нибудь аксиому вывести из остальных аксиом, применяя правила вывода данной системы?

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

Определение 3.

Аксиома А называется независимой от всех остальных аксиом исчисления, если она не может быть выведена из остальных аксиом. Система аксиом исчисления называется независимой, если каждая аксиома системы независима.

Рассмотренная нами система аксиом исчисления высказываний независима.

§1. Недостаточность логики высказываний. Понятие предиката.

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

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

Например, в рассуждении  “Всякий ромб – параллелограм; АВСD – ромб; следовательно, АВСD - параллелограм ” посылки и заключение являются элементарными высказываниями  логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

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

Такой логической системой является логика предикатов, содержащая всю логику высказываний в качестве своей части.

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

Субъект – это то, о чем что-то  утверждается в высказывании;

предикат – это то, что утверждается о субъекте.

Например, в высказывании “7 - простое число”,  “7” – субъект, “простое число” – предикат. Это высказывание  утверждает, что  “7” обладает свойством “быть простым числом”.

Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму “х – простое число”. При одних значения х (например, х=13, х=17) эта форма дает истинные высказывания, а при других значениях х (например, х=10, х=18) эта форма дает ложные высказывания.

Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1;0}. Здесь предикат становится функцией субъекта и выражает свойство субъекта.

Дадим несколько определений, относящихся к предикатам.

Определение 1.

Одноместным предикатом Р(x) называется произвольная функция переменного x, определенная на множестве M и принимающая значение из множества {1; 0}.

Множество М, на котором определен предикат Р(x), называется областью определения предиката Р(x).

Множество всех элементов , при которых предикат принимает значения “истина” (1), называется множеством (областью) истинности предиката Р(x), т.е. множество истинности предиката Р(х)- это  множество или иначе:  или так:  Так, например, предикат Р(x) – “x – простое число” определен на множестве N, а множество истинности IP для него есть множество всех простых чисел.

Предикат Q(x) – “sinx=0” определен на множестве R, а его множеством истинности является  

Предикат F(x) – “диагонали параллелограма x взаимно перпендикулярны” определен на множестве всех параллелограмов, а его множеством истинности является множество всех ромбов.

Из приведенных примеров видим, что одноместные предикаты выражают свойства предметов (субъектов).

Определение 2.

Предикат Р(х), определенный на множестве М, называется тождественно истинным, если его множество истинности совпадает с областью определения, т. е. Ip=M.

Определение 3.

Предикат Р(х), определенный на множестве М, называется тождественно ложным, если его множество истинности является пустым множеством, т. е. Ip=0.

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

Примером бинарного отношения, т. е. отношения между двумя предметами, является отношение “меньше ”. Пусть это отношение введено на множестве Z целых чисел. Оно может быть охарактеризовано высказывательной формой “х<y”, где , то–есть является функцией двух переменных Р(х,y), определенной на множестве упорядоченных пар целых чисел ZхZ=Z2 c множеством значений {1;0}.    

Определение 4.

Двухместным предикатом Р(x,y) называется функция двух переменных x и y, определенная на множестве М=М1хМ 2 и принимающая значения из множества {1;0}.

В числе примеров двухместных предикатов можно назвать такие предикаты:      Q(x, y) – “x=y” - предикат равенства, определенный на множестве RхR=R2; F(x,y) – “х параллелен y”, “прямая  х параллельна прямой y”, определенный на множестве  прямых, лежащих на данной плоскости.

Совершенно аналогично вводится понятие трехместного предиката. Приведем пример трехместного предиката (функции трех переменных): S(x,y,z) – “x+y=z”. Подстановка в него х=3 превращает его в двухместный предикат: S(y,z) – “3+y=z”, а подстановка х=3, z=2 – в одноместный предикат S(y) – “3+y=2”.Подстановка же S(2,3,5) превращает его в истинное высказывание, а S(1,7,4)– в ложное.

Аналогично определяется и n-местный предикат (функция n переменных). Пример п- местного предиката:

R(x1, x2,…,xn): a1 x1+…+anxn=0,

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

При n=0 будем иметь нульместный предикат – это логическая (пропозициональная) переменная, принимающая значения из множества {1;0}.

§2. Логические операции над предикатами.

Предикаты так же, как высказывания, могут принимать два значения: “истина” (1) и “ложь” (0), поэтому к ним применимы все операции логики высказываний, в результате чего из элементарных предикатов формируются сложные предикаты (как и в логике высказываний, где из элементарных высказываний формировались сложные, составные). Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов сохраняют тот же смысл, который был им присвоен в логике высказываний.

Пусть на некотором множестве M определены два предиката P(x) и Q(x).

 Определение 1.

Конъюнкцией двух предикатов P(x) и Q(x) называется новый (сложный) предикат , который принимает значение “истина” при тех и только тех значениях , при которых каждый из предикатов принимает значение “истина”, и принимает значение “ложь” во всех остальных случаях.

Очевидно, что областью истинности предиката  является общая часть области истинности предикатов P(x) и Q(x), т.е. пересечение .

Так, например, для предикатов P(x): “x – четное число” и Q(x): “x кратно 3” конъюнкцией  является предикат “x – четное число и x кратно трем”, т.е. предикат “x делится на 6”.

Определение 2.

Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат , который принимает значение “ложь” при тех и только тех значениях , при которых каждый из предикатов принимает значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Ясно, что областью истинности предиката  является объединение области истинности предикатов P(x) и Q(x), т.е. .

Определение 3.

Отрицанием предиката P(x) называется новый предикат  или, который принимает значение “истина” при всех значениях , при которых предикат P(x) принимает значение “ложь”, и принимает значение “ложь” при тех  значениях , при которых предикат P(x) принимает значение “истина”.

Очевидно, что , т.е. множество истинности предиката  является дополнением к множеству IP.

Определение 4.

Импликацией предикатов P(x) и Q(x) называется новый предикат , который является ложным при тех и только тех значениях , при которых одновременно P(x) принимает значение “истина”, а Q(x) – значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Поскольку при каждом фиксированном  справедлива равносильность , то .

Определение 5.

Эквиваленцией предикатов P(x) и Q(x) называется новый предикат , который обращается в “истину” при всех тех и только тех , при которых P(x) и Q(x) обращаются оба в истинные или оба в ложные высказывания.

Для его множества истинности имеем:

§3. Кванторные операции.

Рассмотрим операции, преобразующие предикаты в высказывания.

Пусть имеется предикат Р(х) определенный на множестве М. Если “а” – некоторый элемент из множества М, то подстановка его вместо х в предикат Р(х) превращает этот предикат в высказывание Р(а). Такое высказывание называют единичным. Например, r(x): “х – четное число” – предикат, а r (6)- истинное высказывание, r (3) – ложное высказывание.

Это же относится и к n – местным предикатам: если вместо всех предметных переменных хi, i= подставить их значения, то получим высказывание.

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

1.  Квантор всеобщности.

Пусть Р(х) – предикат, определенный на множестве М. Под выражением  понимают  высказывание, истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение звучит так: “Для всякого х Р(х) истинно ”.

Символ  называют квантором всеобщности (общности). Переменную х в предикате  Р(х) называют свободной (ей можно придавать различные значения из М), в высказывании же  х называют связанной квантором всеобщности.

1.  Квантор существования.

Пусть P(x) -предикат определенный на множестве М. Под выражением  понимают высказывание, которое является истинным, если существует элемент , для которого P(x) истинно, и ложным – в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение звучит так: “Существует x, при котором P(x) истинно.” Символ  называют квантором существования. В высказывании  переменная x связана  этим квантором (на нее навешен квантор).

Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве М задан двухместный предикат P(x,y). Применение кванторной операции к предикату P(x,y) по переменной x ставит в соответствие двухместному предикату P(x,y) одноместный предикат  (или одноместный предикат ), зависящий от  переменной y и не зависящий от переменной x. К ним можно применить кванторные операции по переменной y, которые приведут уже к высказываниям следующих видов:

Рассмотрим предикат P(x) определенный на множестве M={a1,…,an}, содержащем конечное число элементов. Если предикат P(x) является тождественно - истинным, то истинными будут высказывания P(a1),P(a2),…,P(an). При этом истинными будут высказывания  и конъюнкция .

Если же хотя бы для одного элемента   P(ak)окажется ложным, то ложными будут высказывание  и конъюнкция . Следовательно, справедлива равносильность .

Численные кванторы.

В математике часто встречаются выражения вида “по меньшей мере n” (“хотя бы n”), “не более чем n”, “n и только n” (“ровно n”), где n – натуральное число.

Эти выражения, называемые численными кванторами, имеют чисто логический смысл; они могут быть заменены равнозначными выражениями, не содержащими числительных и состоящими только из логических терминов и знака или ~, означающего тождество (совпадение) объектов.

Пусть n=1. Предложение “По меньшей мере один объект обладает свойством P” имеет тот же смысл, что и предложение “Существует объект, обладающий свойством P”, т.е. (*)

Предложение “не более чем один объект обладает свойством P” равнозначно предложению “Если есть объекты, обладающие свойством P, то они совпадают”, т.е. (**) Предложение “один и только один объект обладает свойством P” равнозначно конъюнкции вышеуказанных предложений (*) и (**).

1.  Отрицание предложений с кванторами.

Известно, что часто для отрицания некоторого предложения достаточно предпослать сказуемому этого предложения отрицательную частицу “не”. Например, отрицанием предложения  “Река х впадает в Черное море.” является предложение  “ Река х не впадает в Черное море ”. Годится ли этот прием для построения отрицаний предложений с кванторами? Рассмотрим пример.

Предложения “Все птицы летают ” и  “Все  птицы не летают ” не являются отрицаниями друг друга, т. к. они оба ложны. Предложения  “ Некоторые птицы летают ” и “ Некоторые  птицы не летают ” не являются отрицанием друг друга, т. к. они оба истинны.Таким образом , предложения , полученные добавлением частицы “не” к сказуемому предложений “Все х суть Р” и “Некоторые х суть Р” не являются отрицаниями этих предложений.Универсальным способом  построения отрицания данного предложения является добавление словосочетания “наверно, что” в начале предложения. Таким образом, отрицанием предложения “Все птицы летают” является предложение “Неверно, что все птицы летают”; но это предложение имеет тот же смысл, что и предложение “Некоторые птицы не летают”. Отрицанием предложения “Некоторые птицы летают” является предложение “Неверно, что некоторые птицы летают”, которое имеет тот же смысл, что и предложение “Все птицы не летают”.

Условимся отрицание предложения  записывать как , а отрицание предложения  – как . Очевидно, что предложение  имеет тот же смысл, а следовательно, то же значение истинности, что и предложение , а предложение – тот же смысл, что . Иначе говоря,  равносильно ;  равносильно .

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

Последовательно применяя сформулированное выше правило, получим: равносильно , что равносильно , что равносильно .

§4.Понятие формулы логики  предикатов.

В логике предикатов будем пользоваться следующей символикой :

1.  Символы p, q, r, …- переменные высказывания, принимающие два значения: 1- истина , 0 – ложь.
2.  Предметные переменные – x, y, z, … , которые пробегают значения из некоторого множества М;

x0, y0, z0 – предметные константы, т. е. значения предметных переменных.

1.  P(·), Q(·), F(·), … - одноместные предикатные переменные;

Q(·,·,…,·), R(·,·, …,·) – n-местные предикатные переменные.

P0(·), Q0(·,·, …,·) – символы постоянных предикатов.

1.  Символы логических операций:     
2.  Символы кванторных операций: 
3.  Вспомогательные символы: скобки, запятые.

Определение формулы логики  предикатов.

1.  Каждое высказывание как переменное, так и постоянное, является формулой (элементарной).
2.  Если F(·,·, …,·) – n-местная предикатная переменная или постоянный предикат, а x1, x2,…, xn– предметные переменные или предметные постоянные (не обязательно все различные), то F(x1, x2,…, xn) есть формула. Такая формула называется элементарной, в ней предметные переменные являются свободными, не связанными кванторами.
3.  Если А и В – формулы, причем, такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой – свободной, то слова  есть формулы. В этих формулах те переменные, которые в исходных формулах были свободны, являются свободными, а те, которые были связанными, являются связанными.
4.  Если А – формула, то  – формула, и характер предметных переменных при переходе от формулы А к формуле  не меняется.
5.  Если А(х) – формула, в которую предметная переменная х входит свободно, то слова  и  являются формулами, причем, предметная переменная входит в них связанно.
6.  Всякое слово, отличное от тех, которые названы формулами в пунктах 1 – 5, не является формулой.

Например, если Р(х) и Q(x,y) – одноместный и двухместный предикаты, а q, r – переменные высказывания, то формулами будут, например, слова (выражения):

.

Не является формулой, например, слово: . Здесь нарушено условие п.3, так как формулу  переменная х входит связанно, а в формулу Р(х) переменная х входит свободно.

Из определения формулы логики предикатов ясно, что всякая формула алгебры высказываний является формулой логики предикатов.

§5. Значение формулы логики предикатов.

О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество M, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики предикатов зависит от значений трех видов переменных: 1) значений входящих в формулу переменных высказываний, 2) значений свободных предметных переменных из множества М, 3) значений предикатных переменных.

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

В качестве примера рассмотрим формулу , (1) в которой двухместный предикат Р(x, y) определен на множестве MхM, где M={0,1,2,…,n,…}, т.е. MхM=NхN.

В формулу (1) входит переменный предикат P(x,y), предметные переменные x,y,z, две из которых y и z – связанные кванторами, а x – свободная.

Возьмем за конкретное значение предиката P(x,y) фиксированный предикат P0(x,y): “x<y”, а свободной переменной х придадим значение . Тогда при значениях y, меньших x0=5, предикат P0(x0,y) принимает значение “ложь”, а импликация  при всех  принимает значение “истина”, т.е. высказывание  имеет значение “истина”.

§6. Равносильные формулы логики предикатов.

Определение 1.

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

Определение 2.

Две формулы логики предикатов А и В называются равносильными, если они равносильны на всякой области.

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

Пусть А(х) и В(х) – переменные предикаты, а С – переменное высказывание (или формула, не содержащая х). Тогда имеют место равносильности:

1.              

2.

3.

4.

5.

1.  .
2.  
3.  
4.  
5.  
6.  
7.  
8.  
9.  
10.  

Равносильность 1 означает тот простой факт, что, если не для всех х истинно А(х), то существует х, при котором будет истиной .

Равносильность 2 означает тот простой факт, что, если не существует х, при котором истинно А(х), то для всех х будет истиной .

Равносильности 3 и 4 получаются из равносильностей 1 и 2, соответственно, если от обеих их частей взять отрицания и воспользоваться законом двойного отрицания.

ЗАКОНЫ ЛОГИЧЕСКИХ ОПЕРАЦИЙ.

(общезначимые формулы логики предикатов)

.  .  .  .  .  .  .  .  .  .  .  .  .  .       .

.       .  .  .  .  .  .  .  .

§7. Нормальные формы формул  логики предикатов.

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

Определение.

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

Пример 1.

.

Получили  приведенную нормальную форму исходной формулы.

Среди нормальных форм формул логики предикатов выделяют так называемую предваренную (префиксную, пренексную) нормальную форму (ПНФ). В ней кванторные операции либо полностью отсутствуют, либо они используются после всех операций алгебры логики, т.е. ПНФ формулы логике предикатов имеет вид

,

где под символом  понимается один из кванторов  или , а формула А кванторов не содержит.

Процедура получения (приведения) ПНФ. Состоит в следующем:

1.  Используя формулы 18, 19 (отнесенные к предикатам), заменить операции и ~ на .
2.  Используя формулы логики предикатов 31, 32, а также формулы логики высказываний 1, 16, 17, представить предикатную формулу таким образом, чтобы символы отрицания относились непосредственно к символам предикатов (и, таким образом, мы приводим исходную формулу к приведенной форме).
3.  Для формул, содержащих подформулы вида , вести новые переменные, позволяющие использовать соотношения 46, 47, 49, 50 или 53, 54.
4.  С помощью формул 35 – 38, 46, 47, 49, 50, 53, 54 получить формулу в виде ПНФ.

Пример 2.

 обозначим в предикате Q переменную y через z 

Пример 3.

обозначим в предикате Q переменную x через z

– ПНФ.

Пример 4.

последний предикат не зависит от переменной z 

два первых предиката не зависят от переменной u  - ПНФ.

Пример 5.

§8. Общезначимость и выполнимость формул. Проблема разрешимости.

Определение 1.

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

Определение 2.

Формула А логики предикатов называется выполнимой, если существует область, на которой эта формула выполнима.

Определение 3.

Формула А логики предикатов называется тождественно-истинной в области М (выполнимой), если она принимает истинные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.

Определение 4.

Формула А логики предикатов называется общезначимой, если она тождественна истинна на всякой области (на любой модели).

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

Это понятие является обобщением понятия тождественной истинности  формулы логики высказываний. Все логические законы, представленный в логике высказываний формулами (1 -30) являются общезначимыми формулами логики предикатов и выражают, как и другие общезначимые формулы, законы логики на языке логике предикатов.

Наиболее употребительные специфические законы логики предикатов, как было отмечено выше, представлены формулами (31 -54).

Общезначимость формулы логики предикатов, например, F обозначается ├F. Все общезначимые формулы могут быть источниками новых  ├ формул. Например, подставляя в (14) – закон исключенного третьего  – вместо х предикат Р(х1,…,хn), получаем общезначимую формулу Р(х1,…,хn)(х1,…,хn). При n=1 имеем общезначимую формулу , и, таким образом ,- общезначимая формула логики предикатов.

Из тождественно истинной  формулы логики высказываний (2)  подстановкой вместо х предиката Р(х, y), а вместо y- предиката Q(x,y) получаем общезначимую формулу  и т. д.

Определение 5.

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

Определение 6.

Формула А логики предикатов называется тождественно ложной (невыполнимой), если она  тождественно ложна на всякой области (на всякой модели).

Например, формула  является тождественно ложной (невыполнимой) формулой логики предикатов.

Из приведенных определений с очевидностью следует:

1.  Если формула А общезначима, то она и выполнима на всякой области (модели).
2.  Если формула А тождественно истинна в области М, то она и выполнима в этой области .
3.  Если формула А тождественно ложна в области М , то она не выполнима в этой  области .
4.  Если формула А не выполнима, то она  тождественно ложна на всякой области (на всякой  модели).
5.  Для того, чтобы формула А логики предикатов была общезначима, необходимо и достаточно, чтобы ее отрицание было не выполнимо.
6.  Для того, чтобы формула А логики предикатов была выполнимой, необходимо и достаточно, чтобы формула  была не общезначима.

Рассмотрим пример

Пример

Доказать равносильность (логическое тождество):

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

А=,

В= или обозначив первую и вторую предметные переменные через n1 и n2, соответственно:

А= В=

В этих обозначениях заданное для рассмотрения тождество будет выглядеть так: .

Произведя равносильные преобразования, можем убедиться в справедливости этого тождества:

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

Пример

Определить тип формулы .

Пусть Р(х) : “ Число х - четно –” предикат, определенный в М=N2.

Таким образом, рассматриваемая формула на данной модели представляет собой следующее утверждение: “ Среди натуральных чисел существуют как четные, так и нечетные ”. Очевидно, что это высказывание истинно и, таким образом, на данной модели формула F тождественно истинна.

Однако, если этот же предикат задать на множестве M=NхN,где N – множество четных чисел, то формула F  на такой модели  окажется тождественно ложной.

Учитывая изложенное, заключаем, что рассматриваемая формула F выполнима (но не общезначима).

Пример

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

Пусть Р(x, x, y): “x·x=y”, или иначе “x2=y” – предикат, определенный на множестве натуральных чисел, т.е. М=N. Тогда рассматриваемая формула выражает утверждение о существовании натурального квадрата натурального числа, что, очевидно, является истиной, т.е. на данной модели формула тождественно истинна, что и требовалось доказать.

Пример

Рассмотрим формулу . Это выполнимая формула. Действительно, если Р(х, y, x): “x+y=x” – предикат суммы, то на M=N существует подстановка вместо y соответствующего значения, дающего значение истинности данной формуле. Очевидно, это y=0, поскольку в этом случае получаем “х=х”.

Если же P(x, y, x): “xy=x” – предикат произведения, то таким значением y является y=1, так как при нем получаем истинное высказывание .

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

Пример

Является ли общезначимой формула:  ?

Пусть P(x, y) – предикат порядка (бинарного отношения ) “”, определенный на конечном множестве натуральных чисел M1. Тогда при подстановке в формулу вместо свободной переменной y величины  мы получим истинное утверждение, а при подстановке любой другой константы из множества М1 – ложное. Таким образом, рассматриваемая формула не является общезначимой.

Пример

Рассмотрим формулу . Покажем, что она невыполнима.

Допустим противное, т.е. что она выполнима. Это означает, что существует такое множество М и такой конкретный предикат  в нем, что когда , то данная формула превращается в такой конкретный предикат , который, в свою очередь, превращается в истинное высказывание при всякой подстановке вместо y элементов из множества М. Возьмем любое. Тогда высказывание  истинно, как мы только что установили. Следовательно, истинны высказывания  и .

Из истинности второго высказывания заключаем, что высказывание  истинно (поскольку “для всех предметных переменных”, как бы они ни обозначались). Но это противоречит истинности первого высказывания .

Таким образом, наше предположение о выполнимости формулы неверно.

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

§9. Применение языка логики предикатов для записи математических предложений, определений, построения отрицания предложений.

9.1 Запись математических предложений и определений в виде формул логики предикатов.

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

Пример 1.Определение предела “” функции ƒ(х), определенной в области E, в точке x0: . Используя трехмесиный предикат , запишем: ,

где .

Пример 2.

Определение непрерывности функции в точке.

Функция , определенная на множестве E, непрерывна в точке , если , где .

Пример 3.

Определение возрастающей функции.

Функция , определенная на множестве E возрастает на этом множестве, если .

Здесь использован двуместный предикат .

9.2. Построение противоположный утверждений.

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

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

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

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

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

Особый интерес представляет построение утверждения, отрицающего справедливость некоторой теоремы: . Это будет утверждение: .

9.3 Прямая, обратная и противоположная теоремы.

Рассмотрим четыре теоремы:

,          (1) ,          (2)

,           (3) .            (4)

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

Так, теоремы  (1)и (2), а также (3) и (4)- взаимно обратные теоремы. При этом, если одну из них называют прямой теоремой, то вторая называется обратной.

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

Так, теоремы (1) и (3), а также (2) и (4) являются взаимно противоположными теоремами.

Например, для теоремы “Если в четырехугольнике диагонали равны, то четырехугольник  является прямоугольником ” (1) обратной является теорема “Если  четырехугольник является прямоугольником, то его диагонали равны” (2). Для теоремы (1) противоположной является  теорема “Если в четырехугольнике диагонали  не равны, то четырехугольник  не является прямоугольником ” (3), а для теоремы (2) противоположной является теорема “Если  четырехугольник не  является прямоугольником, то его диагонали не равны ” (4).

В рассмотренном примере теоремы (1) и (4) являются одновременно ложными, а теоремы (2) и (3) одновременно истинными. Контрпримером к теореме (1) является равнобочная трапеция.

Ясно, что прямая и обратная теоремы , вообще говоря, не равносильны, т. е. одна из них может быть истинной, а другая – ложной. Однако легко показать, что теоремы (1) и (4), а также (2) и (3) всегда равносильны.

Действительно: .

Из этих равносильностей следует, что, если доказана теорема (1), то доказана и теорема (4), а если доказана теорема (2), то доказана и теорема (3).

9.4 Необходимые и достаточные условия.

Рассмотрим теорему

       (1)

Как отмечалось, множество истинности предиката  есть множество . Но тогда множеством ложности этого предиката будет . Последнее множество будет пустым лишь в случае, когда  (см. рисунок).

Итак, предикат  является истинным для всех   том и в только в том случае, когда множество истинности предиката Р(х) содержится в множестве истинности предиката Q(x). При этом говорят, что предикат Q(x) логически следует из предиката Р(х), и предикат Q(x) называют необходимым условием для предиката Р(х), а предикат Р(х) – достаточным условием для Q(x).

Так, в теореме “Если х – число натуральное, то оно целое ” предикат Q(x): “ х – число  целое ” логически следует из предиката Р(х): “х – число натуральное” , а предикат “х- число натуральное” является достаточным условием для предиката “ х – целое число”.

                                                  Часто встречается  ситуация, при которой истинны взаимно   

                                                  обратные теоремы  (1)            

                  Рис.  28                     .(2)

Это, очевидно, возможно при условии, что .

В таком случае из теоремы  (1)следует, что условия Р(х)являются достаточными для Q(x), а из  теоремы (2) следует, что  условие Р(х)является необходимым для Q(x).

Таким образом, если истинны теоремы (1) и (2), то условие Р(х) является и необходимым, и достаточным  для Q(x). Аналогично в этом случае условие Q(х)является необходимым и достаточным для Р(x).

Иногда вместо логической связки  “необходимо и достаточно ” употребляют  логическую связку “тогда и только тогда”.

Так как здесь истинны высказывания (1) и (2), то истинно высказывание

.

9.5. Доказательство теорем методом от противного.

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

         (1)

не верна, т. е. , существует такой объект  х, что условие Р(х) истинно, а заключение Q(x) – ложно. Если из этих предложений путем логических рассуждений приходят к противоречивому утверждению, то делают  вывод о том, что исходное предположение неверно, и верна теорема (1).

Покажем, что такой подход дает доказательство истинности теоремы (1).

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

Тестовые задания

Начало формы

Множества и операции над ними

№ п/п	Вопрос	Варианты ответов:
1	Укажите верное утверждение для всех A, B и C:	Если A B и B C, то A C    Если A B и B C, то A C    Если A B C и A C B, то A C = ;
2	Решить систему уравнений где A, B и C – данные множества и B A C.	X = ( C \ A ) B.   X=C B.   X=(C A) B.
3	Решить систему уравнений где A, B и C – данные множества и B A, A C = .	X = ( A \ B ) C.    X= ( A C) B.
4	Существуют ли такие множества A, B и C, что A B , A C = , (A B) \ C = ;	нет;    да.
5	Образуют ли бинарные отношения группу относительно операций

Конец формы

естовые задания

Начало формы

Алгебра логики 

№ п/п	Вопрос	Варианты ответов:
1	Какие из следующих предложений не являются высказываниями?	Треугольник ABC подобен треугольнику A`B`C`.    Студент физико-математического факультета педагогического института.    Москва – столица СССР.
2	Установите, какие из высказываний в следующих парах являются отрицаниями друг друга:	2<0, 2>0;    6<9, 6>9;    Функция f – четна, функция f – нечетна;    Треугольник ABC прямоугольный, а ABC – тупоугольный;
3	Пусть высказывание A B истинно. Что можно сказать о логическом значении высказывания ( A B ) ( A B ) ?	Истинно;    Ложно.
4	Существует ли три таких высказывания A, B и C, чтобы одновременно высказывание A B было истинным, высказывание A C и высказывание (A B) C – ложным?	Не существует;    Существует.
5	Применяя равносильные преобразования, приведите следующие формулы к возможно более простой форме: ( P Q ) ((P Q ) P) ;	P Q;    1;    P.
6	Следующую формулу преобразуйте равносильным образом так, чтобы она содержала только операции и : ( x y ) ( x z )	( x y z );   x y.
7	Определите, какая из последовательностей символов является формулой:	((P Q) R) S;   ((P ( Q R )) (( P R ) Q )).
8	Приведите к ДНФ: (x y) ( z T )	(x y z T) ( x y z T);    x y z.
9	Приведите к КНФ: ( x z ) (x y);	x z;    x z .
10	По данному набору значений переменных постройте дизъюнктивный одночлен, принимающий значение только на этом наборе значений переменных: ( ,)	x y;    x y;   x y z.

Конец формы

Тестовые задания

Начало формы

Исчисление высказываний 

№ п/п	Вопрос	Варианты ответов:
1	Укажите, видом какой формы и из каких посылок является следующая формула : A C, (A C) ((DC) (A B C)), (B C) (A B C), B C, A B C, A B, C	A C, B C, A B.    A C, B C, A B C.
2	Какие из следующих выражений являющиеся формулами исчисления высказываний :	((p1 p2) (p1 p2)) ;    (p1 (p2 p3)) p3;
3	Доказать, что: H = {A} B A	B A;    A, A (BA), BA;    B A C.
4	Доказать, что: H = {A C}	A C,(A C)( ), ;    (C).
5	Дана формула A = x1x2 x3 и набор значений переменных (0,0,1). Записать вывод формулы A или ее отрицание из соответствующей совокупности формул:	, , x3, x3 (x1x2x3), x1x3x3;    x2;
6	Пусть A = x1 & x3 и набор значений переменных (1, 0, 1). Тогда {x1,,x3} A. Записать вывод.	x1 & x2 x3;   H x1, , x3, x3 (x1 & x3), x1 & x3 A.

Конец формы

Тестовые задания Начало формы Логика и исчисление предикатов № п/п Вопрос Варианты ответов: 1 Указать область истинности предиката: X+5=1.    Ip={-2};    Ip={-4};    Ip={4}; 2 Указать область истинности предиката: X2-2X+1=0.   Ip={1};   Ip={2}; 3 Выяснить, какие из следующих предикатов являются тождественно истинными:    X2+Y2>=0;    X2+Y2>0;    X2+1>=(X+1)2. 4 Записать предикат, полученный в результате логических операций над предикатами P(x), Q(x) и R(x) , область истинности которого I заштрихована на рисунке    P(x) & R(x);    P(x) & Q(x) & R(x). 5 Даны предикаты P(x): X2+X+1>0 и Q(x) : X2-4X +3=0, определенные на множестве R. Установите , какие из следующих высказываний истинны:  x P(x); y P(x). 6 Укажите, какие из следующих выражений являются формулами логики предикатов:  x y P(x,y);  x,y P(x,y). 7 Пусть A(x) и B(x)- любые предикаты. Какие из следующих формул равносильны формуле: A(x) A(x)B(x); ; B(x); A(x); & B(x). 8 Записать предикат, полученный в результате логических операций над предикатами P(x) , Q(x) и R(x) , область истинности которых (I) заштрихована на следующем рисунке: P(x) & ; P(x) & Q(x). 9 Записать предикат, полученный в результате логических операций над предикатами P(x) ,Q(x) и R(x) , область истинности которых (I) заштрихована на следующем рисунке: P(x) & R(x); P(x) & Q(x). 10  Записать предикат, полученный в результате логических операций над предикатами P(x) ,Q(x) и R(x) , область истинности которых (I) заштрихована на следующем рисунке: P(x) & ; P(x) & & Q(x). 11  Записать предикат, полученный в результате логических операций над предикатами P(x) ,Q(x) и R(x) , область истинности которых (I) заштрихована на следующем рисунке:   P(x) Q(x);   P(x) Q(x);    .   Конец формы

Курс: Дискретная математика 

http://fkn.univer.omsk.su/kursi/disc/arithmet.htm

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

Содержание

0.1 Предмет математической логики 

0.2 Пример формальной системы 

0.3 Структура раздела 

1 Аксиоматический метод 

1.1 Аксиомы натуральных чисел 

1.2 Начальные задачи 

1.3 Сложение 

1.4 Порядок 

1.5 Наименьший элемент 

1.6 Умножение 

1.7 Системы Пеано 

2 Логика высказываний 

2.1 Объектный язык и метаязык 

2.2 Пропозициональные формулы 

2.3 Доказательство свойств формул по индукции 

2.4 Разбор формул 

2.5 Семантика 

2.6 Нормальные формы 

2.7 Выполнимость 

2.8 Логическое следование 

2.9 Пропозициональный вывод 

2.10 Правила для конъюнкции и импликации 

2.11 Правило введения посылки 

2.12 Корректность правил вывода 

2.13 Правила для отрицания и правила противоречия 

2.14 Правила для дизъюнкции 

2.15 Корректность и полнота логики высказываний 

3 Логика предикатов 

3.1 Язык логики предикатов 

3.2 Свободные и связанные переменные 

3.3 Представление предложений русского языка предикатными формулами 

3.4 Подстановка 

3.5 Семантика 

3.6 Выполнимость 

3.7 Логическое следование 

3.8 Выводы в логике предикатов 

3.9 Правила для кванторов всеобщности 

3.10 Правила для кванторов существования 

3.11 Корректность и полнота логики предикатов 

3.12 Функциональные символы и равенство: синтаксис 

3.13 Функциональные символы и равенство: семантика 

3.14 Выводы в логике первого порядка 

3.15 Теории первого порядка 

3.16 Пример: Теория линейного порядка 

3.17 Арифметика первого порядка 

3.18 Нестандартные модели арифметики 

3.19 Теорема неполноты Гёделя 

Введение

Предмет математической логики

Основная идея математической логики – формализация знаний и рассуждений. Известно, что наиболее легко формализуемые знания – математические. Таким образом, математическая логика, по-существу, – наука о математике, или метаматематика. Центральным понятием математической логики является ``математическое доказательство''. Действительно, ``доказательные'' (иначе говоря, дедуктивные) рассуждения – единственный вид признаваемых в математике рассуждений. Рассуждения в математической логике изучаются с точки зрения формы, а не смысла. По-существу, рассуждения моделируются чисто ``механическим'' процессом переписывания текста ( формул). Такой процесс называют выводом. Говорят еще, что математическая логика оперирует только синтаксическими понятиями.

Однако обычно всё же важно, как соотносятся рассуждения с действительностью (или нашими представлениями). Поэтому, надо всё же иметь в виду некоторый смысл формул и вывода. При этом используют термин семантика (синоном слова ``смысл'') и чётко разделяют синтаксис и семантику.

Когда же действительно интересуются только синтаксисом, часто используют термин ``формальная система''. Мы будем использовать синоним этого термина – ``исчисление'' (используются ещё термины ``формальная теория'' и ``аксиоматика'').

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

Формальная система определена, если:

1.  Задан алфавит (множество символов, используемых для построения формул).
2.  Определено, какие именно строки считать формулами (остальные строки считаются просто бессмысленными).
3.  Выделено множество формул, называемых аксиомами. Это – стартовые точки в выводах.
4.  Задано множество правил вывода, которые позволяют из некоторой формулы (или множества формул) получать новую формулу.

Пример формальной системы

Рассмотрим пример простой, ``игрушечной'' формальной системы.

Пример формальной системы. Популярная формальная система (DH) определяется следующим образом:

1.  Алфавит: {M,I,U}.
2.  Формулы: любая последовательность символов данного алфавита.
3.  Одна аксиома: MI.
4.  Правила вывода:
   •  правило 1: из формулы вида mI можно получить mIU.
   •  правило 2: из формулы вида Mm можно получить Mmm.
   •  правило 3: подстроку III можно заменить на U.
   •  правило 3: подстроку UU можно заменить на пустую строку.

символом m в первом и во втором правиле обозначается произвольное слово.

Приведём пример построения вывода:

MI (аксиома), MII (правило 2), MIIII (правило 2), MIIIIU (правило 1), MIUU (правило 3), MI (правило 4).

Определите, можно ли получить формулу MU с помощью правил вывода из аксиомы.



Структура раздела

Раздел ``математическая логика'' состоит из трёх частей: по неформальному аксиоматическому методу, по логике высказываний и по логике предикатов (первого порядка).

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

По поводу используемой нотации. Текст построен на последовательности задач. Большинство задач состоит в доказательстве некоторых утверждений. Для некоторых задач имеются указания для решения. Для отдельных приведено решение. Некоторые задачи служат для подготовки читателя к следующим задачам – для номеров таких вспомогательных задач используется курсив. В тексте мы часто используем шаблон ``для <объекты> : <свойство>''. Здесь ``:'' является сокращением слов ``выполняется следующее:''.

Следующая часть

Курс: Дискретная математика

Аксиоматический метод

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

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

Аксиомы натуральных чисел

Мы рассматриваем множество w объектов называемых натуральными числами. Одно из натуральных чисел называется нулём и обозначается 0 . Для любого натурального числа n одно из натуральных чисел называется следующим за числом n и обозначается n' .

Множество натуральных чисел таково, что удовлетворяет следующим аксиомам:

Аксиома 1. Для любого натурального числа n: n'№ 0.

Аксиома 2. Для любых натуральных чисел m и n: если m'=n', то m = n.

Аксиома 3. Пусть A является подмножеством множества w со следующими свойствами:

1.  0 О A;
2.  для любого натурального числа n: если n О A, то n' О A.

Тогда A = w.

Эти аксиомы были введены Джузеппе Пеано в 1889 году.

Начальные задачи

Определения. 1 = 0', 2 = 1', 3 = 2', 4 = 3' .

В каждой из следующих задач получите данное утверждение из аксиом.

1.1 2 № 4.

см. Решение

1.2 n' № n.

Решение. Рассмотрим множество A натуральных чисел n таких, что n' № n. Наша цель – показать, что A = w, и мы сделаем это, используя аксиому 3. Сначала нам надо проверить, что 0 О A, то есть 0' № 0. Это следует из аксиомы 1. Теперь возьмём любое натуральное число n и предположим, что n О A, то есть n' № n. Нам надо вывести из этого предположения, что n'О A – это значит, что n'' № n'. Предположим, что n''= n'. Тогда, по аксиоме 2, n'= n, а это противоречит тому, что n' № n.

Это доказательство, разумеется, ``доказательство по индукции''. Условия 1 и 2 аксиомы 3 являются ``базисом'' и ``индуктивным шагом''. Аксиома 3, которая служит для построения доказательств подобных этому, называется аксиомой индукции.

1.3 Если n № 0, то существует натуральное число m такое, что n = m'. см. Указания

1.4 Такое число m единственно.

Сложение

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

1.5 Существует функция f из натуральных чисел в натуральные числа такая, что

f(0) = 3,

f(n') = f (n)'.

см. Указания

1.6 Для любого m существует функция f из натуральных чисел в натуральные числа такая, что

f(0) = m,

f(n') = f(n)'.

1.7 Существует функция g из w ґ w в w такая, что

g(m, 0) = m,

g(m, n') = g(m, n).

1.8 Такая функция g единственна. см. Указания

Определение 1 (Сумма). Для этой функции g число g(m, n) называется суммой m и n и обозначается m + n .

Так, для любых натуральных чисел m и n:

m + 0 = m, m + n'= (m + n)'.

(1)

Корректность определения сложения была выведена из аксиом Пеано Лазло Кальмаром в 1929 году.

1.9 2 + 2 = 4.

1.10 n'= n + 1. см. Указания

1.11 (k + m) + n = k + (m + n). * см. Указания

1.12 0 + n = n. см. Указания

1.13 m'+ n = m + n'. см. Указания

1.14 m + n = n + m. * см. Указания

1.15 Если k + m = k + n, то m = n. * 

Порядок

Определение 2 (Порядок). Мы пишем m Ј n , если для некоторого k: n = m + k.

1.16 0 Ј n.

см. Решение

1.17 n Ј n. * 

1.18 n Ј n'.

1.19 n Ј 0 тогда и только тогда, когда n = 0. см. Указания

1.20 Если k Ј m и m Ј n, то k Ј n. * см. Указания

1.21 Если m Ј n и n Ј m, то m = n. * 

1.22 Если m Ј n и m № n, то m'Ј n.

1.23 Для любых m и n: m Ј n или n Ј m. * см. Указания

1.24 k + m Ј k + n тогда и только тогда, когда m Ј n.

Определение 3. Мы пишем m < n , если m Ј n и m № n.

1.25 2 < 4.

1.26 Любые натуральные числа m и n удовлетворяют по крайней мере одному из условий: m = n, m < n, n < m.

1.27 Любые натуральные числа m и n удовлетворяют в точности одному из этих условий.

1.28 Для любых натуральных чисел m и n, следующие условия эквивалентны:

1.  m Ј n,
2.  m < n или m = n,
3.  m < n'.

Наименьший элемент

Определение 4 (Наименьший элемент). Элемент n множества A натуральных чисел называется его наименьшим элементом, если для любого элемента m из A n Ј m.

1.29 Любое множество натуральных чисел имеет не более одного наименьшего элемента.

1.30 Для любого множества A натуральных чисел если 0 О A, то 0 является наименьшим элементом A.

1.31 Для любого множества A натуральных чисел если 1 О A, то A имеет наименьший элемент.

1.32 Любое непустое множество натуральных чисел имеет единственный наименьший элемент.

Умножение

1.33 Для любого m существует функция f из натуральных чисел в натуральные числа такая, что

f(0) = 0,

f(n + 1) = f(n) + m.

1.34 Существует функция g из w ґ w в w такая, что

g(m, 0) = 0,

g(m, n + 1) = g(m, n) + m.

1.35 Такая функция g единственна.

Определение 5 (Произведение). Для этой функции g число g(m, n) называется произведением m и n и обозначается m · n .

Так, для любых натуральных чисел m и n 

m · 0 = 0, m · (n + 1) = (m · n) + m.

(2)

1.36 2 · 2 = 4.

1.37 m · n = n · m. см. Указания

1.38 m · n = 0 тогда и только тогда, когда m = 0 или n = 0. см. Указания

Системы Пеано

Определение 6 (Система Пеано). Тройка <W, a, s> , где W – множество, a – элемент из W, а s – функция из W в W называется системой Пеано, если

•  для любого x О W: s(x) № a,
•  для любых x, y О W: если s(x) = s(y), то x = y,
•  для любого подмножества A множества W если
  1.  a О A и
  2.  s(x) О A всегда, когда x О A,

тогда A = W.

Используя это определение, аксиомы 1–3 можно сформулировать кратко, сказав, что тройка <w, 0, s0>, где s0 обозначает функцию следования*, является системой Пеано.

1.39 Определите систему Пеано <W, a, s> такую, что W = w \ {0}.

1.40 Найдите изоморфизм между системой Пеано <w, 0, s0> и системой Пеано, построенной в решении задачи 1.39.

1.41 Для любой системы Пеано <W, a, s> существует изоморфизм между <w, 0, s0> и <W, a, s>. см. Указания

Таким образом, любая система Пеано изоморфна системе натуральных чисел. В этом смысле аксиомы 1–3 дают полную характеризацию натуральных чисел*.

Следующая часть

Курс: Дискретная математика

Логика высказываний

Для понятия ``высказывание'' иногда используют термин ``пропозиция'', что является калькой с английского. Мы этот термин не используем, но говорим ``пропозициональный'' в смысле относящийся к логике высказываний. Центральными понятиями данной части являются пропозициональные формулы и пропозициональный вывод.

Объектный язык и метаязык

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

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

Пропозициональные формулы

Пропозициональная сигнатура – это множество символов, называемых атомами. Символы ¬ (отрицание), & (конъюнкция), Ъ (дизъюнкция) и Й (импликация) называются пропозициональными связками; ¬ – унарная связка, а другие – бинарные.

Возьмём непустую пропозициональную сигнатуру s , которая не содержит ни пропозициональных связок, ни скобки (, ). Алфавит пропозициональной логики состоит из атомов сигнатуры s, пропозициональных связок и скобок. Под строкой мы понимаем конечную последовательность (строку) символов в этом алфавите.

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

Определение 7. Множество X строк замкнуто относительно правил построения (для логики высказываний), если

•  каждый атом принадлежит X,
•  для любой строки F, если F принадлежит X, то ¬F тоже принадлежит,
•  для любых строк F, G и любой бинарной связки Д, если F и G принадлежат X, то также принадлежит (F Д G).

2.1 Укажите два примера множества строк: одно замкнутое, другое не замкнутое относительно правил построения.

Определение 8 (Формула). Строка F называется пропозициональной формулой, если F принадлежит всем множествам, которые замкнуты относительно правил построения.

2.2 Множество формул замкнуто относительно правил построения.

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

В двух следующих задачах мы предполагаем, что рассматриваемая сигнатура – это {p, q}.

2.3 Является ли формулой ¬(p & q)?

2.4 Является ли формулой (p)?

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

Доказательство свойств формул по индукции

Разбор формул

Семантика

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

Определение 10 (Интерпретация). Символы л,и (``ложь'', ``истина'') называются истиностными значениями. Интерпретация пропозициональной сигнатуры s есть функция из s в {л,и}.

Если s конечна, тогда интерпретация может быть определена таблицей её значений, например:

p q л  и

(3)

Семантика логики высказываний, которую мы собираемся ввести, определяет какие истиностные значения назначены формуле F интерпретацией I.

Прежде всего нам надо связать функцию с каждой пропозициональной связкой – функцию из {л,и} в {л,и} с унарной связкой ¬ и функцию из {л,и}ґ {л,и} в {л,и} с каждой бинарной связкой. Функции определяются следующими таблицами:

x ¬(x) л и и л

x y &(x, y) Ъ(x, y) Й(x, y) л л л л и л и л и и и л л и л и и и и и

* 

Для любой формулы F и любой интерпретации I истиностное значение FI , назначенное формуле F интерпретацией I, определяется как значение суперпозиции соответствующих булевых функций, а именно, следующим образом:

•  FI = I(F) если F – атом,
•  (¬F )I = ¬(FI),
•  (F Д G)I = Д(FI,GI) для каждой бинарной связки Д.

Заметим, что это определение рекурсивно: (¬F)I определяется через FI и (F Д G)I – через FI и GI.

Если FI = и, мы говорим, что формула F истинна при интерпретации I (символически I |= F ).

2.10 Найдите формулу F такую, что (3) – единственная интерпретация, при которой F истинна.

Если рассматриваемая сигнатура конечна, тогда множество интерпретаций тоже конечно, и значения FI для всех интерпретаций можно представить в виде конечной таблицы. Эта таблица называется таблицей истинности формулы F. Например, предыдущая задача может быть сформулирована следующим образом: найти формулу, таблицей истинности которой является

p	q
л	л	л
л	и	и
и	л	л
и	и	л

2.11 Для любых формул F1,...,Fn (n і 1) и любой интерпретации I

(F1 & ··· & Fn)I = и тогда и только тогда, когда FI1 = ··· = FIn = и.

2.12 Сформулируйте и докажите подобный факт для дизъюнкции F1 Ъ ··· Ъ Fn.

В двух следующих задачах мы предполагаем, что рассматриваемая сигнатура конечна: s = { p1, ..., pn}.

2.13 Для любой интерпретации I существует формула F такая, что I – единственная интерпретация, при которой F истинна.

2.14 Для любой функции a из интерпретаций в истинстные значения существует формула F такая, что для всех интерпретаций I: FI = a(I).

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

Нормальные формы

Определение 11 (Эквивалентность). Формула F эквивалентна формуле G, если FI = GI для любой интерпретации I.

В задачах 2.16, 2.18 и 2.20 мы вводим несколько ``нормальных форм'' таких, что любая пропозициональная формула может быть эквивалентно трансформирована в любую из этих форм.

2.15 Покажите, что для атомов p и q

•  каждая из формул p & q, p Й q эквивалентна формуле, не содержащей связок, кроме Ъ и ¬,
•  каждая из формул p Ъ q, p Й q эквивалентна формуле, не содержащей связок, кроме & и ¬,
•  каждая из формул p & q, p Ъ q эквивалентна формуле, не содержащей связок, кроме Й и ¬.

2.16 Любая формула эквивалентна

•  формуле, не содержащей связок, кроме Ъ и ¬,
•  формуле, не содержащей связок, кроме & и ¬,
•  формуле, не содержащей связок, кроме Й и ¬.

В сочетании с результатом задачи 2.14 этот факт показывает, что множества { Ъ, ¬ }, { &, ¬ } и { Й, ¬ } – ``полные'' множества связок – они достаточны для выражения любой таблицы истинности. С другой стороны, множество { Ъ, &, Й } не ``полное'':

2.17 Предполагая, что p – атом, покажите что любая формула, эквивалентная ¬p, содержит по крайней мере одно отрицание. см. Указания

Литерал – это атом или отрицание атома. Элементарная конъюнкция – это формула вида L1& ··· & Ln (n і 1), где L1,...,Ln – литералы. Будем говорить, что формула находится в дизъюнктивной нормальной форме, если она имеет вид C1 Ъ ··· Ъ Cm (m і 1), где C1, ..., Cm – элементарные конъюнкции.

2.18 Любая формула эквивалентна некоторой формуле в дизъюнктивной нормальной форме.

Элементарная дизъюнкция – это формула вида L1 Ъ ··· Ъ Ln (n і 1), где L1,...,Ln – литералы. Будем говорить. что формула находится в конъюнктивной нормальной форме, если она имеет вид D1 & ··· & Dm (m і 1), где D1, ..., Dm – элементарные дизъюнкции.

2.19 Пусть F – формула в дизъюнктивной нормальной форме. Покажите, что ¬F эквивалентно некоторой формуле в конъюнктивной нормальной форме.

2.20 Любая формула эквивалентна некоторой формуле в конъюнктивной нормальной форме.

Выполнимость

Определение 12 (Выполнимость). Если существует интерпретация, при которой формула F истинна, мы говорим, что F выполнима.

Эта терминология применима также к множествам формул: множество G формул выполнимо, если существует интерпретация, при которой истинны все формулы G.

2.21 Пусть G – множество литералов. Покажем, что G выполнимо тогда и только тогда, когда не существует атома A, для которого и A и ¬A принадлежат G.

Для любого атома A литералы A, ¬A называются дополнительными друг к другу. Так, утверждение последней задачи может быть выражено следующим образом: множество литералов выполнимо тогда и только тогда, когда оно не содержит дополнительных пар.

Логическое следование

Мы сейчас определим в контексте логики высказываний, когда формула F ``следует'' из множества формул G. Идея следования центральна в логике: в любой формальной аксиоматической теории ``теорема'' – это формула, которая следует из аксиом.

Определение 13 (Логическое следование). Формула F (логически) следует из множества формул G (или множество формул G влечёт формулу F, символически, G |= F ), если для каждой интерпретации, при которой все формулы G истинны, формула F также истинна.*

Про формулы, которые логически следуют из G будем говорить ``логическое следствие G''.

2.22 Предполагая, что p и q – атомы, определите

•  следует ли q из (множества состоящего из) p и p Й q,
•  следует ли ¬q из ¬p и p Й q.

2.23 G влечёт F тогда и только тогда, когда G И { ¬F } не выполнимо.

Определение 14 (Тавтология). Формула F называется тавтологией, или тождественно истинной формулой, если F истинно при любой интерпретации.*

Понятие тавтологии ``двойственно'' понятию выполнимой формулы: F – тавтология тогда и только тогда, когда ¬F не выполнима. Определение эквивалентных формул, данное выше, может быть переформулировано следующим образом: F эквивалентна G, если F є G – тавтология.

2.24 Определить, какие из следующих формул являются тавтологиями: (p Й q) Ъ (q Й p), ((p Й q) Й p) Й p, ((p є q) є r) є (p є (q є r)).

2.25 Для любых формул F, G1,...,Gn (n і 1) : F следует из { G1,..., Gn } тогда и только тогда, когда (G1 & ··· & Gn) Й F – тавтология.

Пропозициональный вывод

Существует другое определение следования, которое выглядит совершенно отличающимся от данного выше, но в действительности эквивалентное ему. В соответствие с этим определением, G влечёт F, если F может быть выведено из G с использованием определенного набора ``правил вывода''. Первое определение, основанное на интерпретации, – ``семантическое'', второе, основанное на понятии вывода – ``синтаксическое'' или ``дедуктивное''.

О корректности, полноте и разрешимости 

Выводы в логике высказываний – наш основной объект изучения до конца данной части.

Вывод строятся из конструкций, которые называются ``секвенциями''.

Определение 15 (Секвенция). Секвенция – это выражение вида G |– F (``F при посылках G'') или G |– ^ (``посылки G противоречивы''), где F – формула и G – конечное множество формул. * 

Мы определим, какие секвенции рассматриваются ``начальными'', и опишем несколько ``правил вывода'' для порождения новых секвенций из секвенций, порождённых ранее. Начальные секвенции называются аксиомами.

Определение 16 (Аксиомы). Аксиомы в исчислении высказываний имеют вид

{ F } |– F.

Мы определим 12 правил вывода, и удобно вводить их постепенно.

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

Определение 17 (Дерево доказательства). Дерево доказательства определим рекурсивно:

1.  Деревом доказательства является пустое дерево доказательства, состоящее только из корня – аксиомы.
2.  Пусть T1, ..., Tk – деревья доказательства с корнями R1, ..., Rk. Тогда

T1 ... Tk

S

1.  (где S – некоторая секвенция) – дерево доказательства, если S может быть получена из R1, ..., Rk с помощью одного из правил вывода. Корнем такого дерева является S.

Определение 18 (Доказуемая секвенция). Если существует дерево доказательства с корнем R, то R называют доказуемой секвенцией. Если этот корень имеет вид G |– F, то говорят о выводе формулы F из G.

В соответствие с дедуктивным определением следования говорят, что F следует из G, если существует вывод F из подмножества G.

Правила для конъюнкции и импликации

G |– F G |– G (В&) G |– F & G	G |– F & G (У&) G |– F G |– F & G G |– G
G И { F } |– G (ВЙ) G |– F Й G	G |– F G |– FЙ G (УЙ) G |– G

В каждом из этих пяти правил вывода, одно или два выражения над горизонтальной чертой представляют ``посылки'', к которым правило может быть применено, и выражение под чертой представляет ``заключение'' которое выводится по этому правилу. Правила В& и ВЙ – ``правила введения'' конъюнкции и импликации; У& и УЙ – ``правила удаления''. Подставляя конкретные формулы вместо метапеременных F и G и конкретные конечные множества формул вместо метапеременной G некоторое правило вывода, мы получаем пример этого правила. Например,

{q, r} |– p {p Ъ q, r} |– ¬q

{q, r, p Ъ q} |– p & ¬q

есть пример правила введения конъюнкции.

Пример простого вывода. . Выведем формулу q из посылки p & q. Этот вывод получается за один шаг с помощью второго правила удаления конъюнкции.

	{q} |– q
(У&)
	{p & q} |– q



2.26 Найдите вывод q & p из p & q.

см. Решение

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

2.27 (p & p) Й p.

2.28 (p & p) є p.

Правило введения посылки

Мы построили несколько примеров простых выводов. Однако, используя только правила для конъюнкции и импликации, мы не сможем построить вывод формулы p & q из множества посылок {p, q}. Действительно, формулу {p, q} |– p & q мы можем получить с помощью правила (В&) из формулу {p, q} |– p и формулу {p, q} |– q. Однако ``очевидные'' формулы {p, q} |– p и {p, q} |– q мы не сможем вывести. У нас нет правила, позволяющего выводить формулу из некоторого множества посылок, если она выводится из более узкого множества. Это правило вывода назовём правилом введения посылки.

	G |– F
(ВП)
	G И {G} |– F

Пример вывода. Мы приводим вывод p Й ((p Й q) Й (p & q)) из пустого множества посылок:

	{p} |– p (ВП) {p,p Й q} |– p {p} |– p (ВП) {p,p Й q} |– p {p Й q} |– p Й q (ВП) {p,p Й q} |– p Й q (УЙ) {p,p Й q} |– q
(В&)
	{p,p Й q} |– p & q (ВЙ) {p} |– (p Й q) Й (p & q) (ВЙ) Ж |– p Й ((p Й q) Й (p & q))



2.29 Найдите вывод p Й r из p Й q и q Й r.

2.30 Найдите вывод r из p & q и p Й (q Й r).

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

2.31 p Й (q Й p).

2.32 p Й ((p & q) є q).

2.33 ((p & q) Й r) є (p Й (q Й r)).

Корректность правил вывода

Определение 19 (Истинность секвенций). Секвенция G |– F тождественно истинна, если G влечёт F.*

Определение 20 (Корректность правил вывода). Правило вывода корректно, если для каждого примера этого правила посылки которого являются тождественно истинными, его заключение также тождественно истинно.

2.34 Правило введения посылки корректно.

2.35 Оба правила удаления конъюнкции корректны.

2.36 Правило введения конъюнкции корректно.

2.37 Правило удаления импликации корректно.

2.38 Правило введения импликации корректно.

Правила для отрицания и правила противоречия

Следующие четыре правила вывода – правила введения и удаления отрицания ``правило сведения к противоречию'' и ``правило противоречия''.

G И { F } |– ^ (В¬) G |– ¬F	G И { ¬F } |– ^ (У¬) G |– F
G |– F G |– ¬F (В^) G |– ^	G |– ^ (У^) G |– F

Выведите секвенции:

2.39 {¬¬p} |– p.

см. Решение

2.40 {p} |– ¬¬p.

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

2.41 ¬(p & ¬p).

2.42 (p & ¬p) Й q.

Определение 21 (Истинность секвенций). Секвенция G |– ^ тождественно истинна, если G не выполнимо.

2.43 Правило удаления отрицания корректно.

2.44 Правило введения отрицания корректно.

2.45 Правило противоречия корректно.

Правила для дизъюнкции

Оставшиеся три правила вывода – правила введения и удаления дизъюнкции:

G |– F (В Ъ) G |– F Ъ G

G |– G G |– F Ъ G

	G |– F Ъ G G И F |– C G И G |– C
(У Ъ)
	G |– C

Здесь F и G – формулы, и C – либо формула, либо ^.

Теперь описание системы вывода для логики высказываний завершено.* 

Мы рекомендуем строить деревья доказательства, начиная с корней (т.е. с формул, которые надо вывести) и постепенно нарашивая дерево, добиваясь, чтобы конечными формулами в дереве были аксиомы.

О том, как строить дерево доказательства. 

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

2.46 (p Ъ q) Й (q Ъ p).

2.47 (p Ъ p) є p.

2.48 ¬p Й ((p Ъ q) є q).

2.49 (p & (q Ъ r)) є ((p & q) Ъ (p & r)).

2.50 ¬¬p є p.

2.51 ¬(p Ъ q) є (¬p & ¬q).

2.52 Оба правила введения дизъюнкции корректны.

2.53 Правило удаления дизъюнкции корректно.

Корректность и полнота логики высказываний

Теорема корректности. Если существует вывод F из G, тогда G логически влечёт F.

Теорема полноты. Для любой формулы F и любого множества формул G, если G влечёт F, тогда существует вывод F из подмножества G.

Полнота логики высказываний (для другого множества правил вывода) была установлена Емилем Постом в 1921 году.

Следующая частьКурс: Дискретная математика

Логика предикатов

Понятие ``предикат'' обобщает понятие ``высказывание''. Неформально говоря, предикат – это высказывание, в которое можно подставлять аргументы. Если аргумент один – то предикат выражает свойство аргумента, если больше – то отношение между аргументами.

Пример предикатов. Возьмём высказывания: ``Сократ - человек'', ``Платон - человек''. Оба эти высказывания выражают свойство ``быть человеком''. Таким образом, мы можем рассматривать предикат ``быть человеком'' и говорить, что он выполняется для Сократа и Платона.

Возьмём высказывание: ``расстояние от Иркутска до Москвы 5 тысяч километров''. Вместо него мы можем записать предикат ``расстояние'' (означающий, что первый и второй аргумент этого предиката находятся на расстоянии, равном третьему аргументу) для аргументов ``Иркутск'', ``Москва'' и ``5 тысяч километров''.



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

Пример рассуждения, не выразимого в логике высказываний. Все люди смертны. Сократ - человек. Следовательно, Сократ смертен. 

Это рассуждение на языке логики высказываний можно записать тремя отдельными высказываниями. Однако никакой связи между ними установить не удастся. На языке логики предикатов эти предложения можно выразить с помощью двух предикатов: ``быть человеком'' и ``быть смертным''. Первое предложение устанавливает связь между этими предикатами.



Перейдём теперь к формальному изложению логики предикатов.

Язык логики предикатов

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

Предикатная сигнатура – это множество символов двух типов – объектные константы и предикатные константы – с неотрицательным целым числом, называемым арностью, назначенным каждой предикатной константе. Предикатную константу мы будем называть пропозициональной, если её арность равна 0. Пропозициональные константы являются аналогом атомов в логике высказываний. Предикатная константа унарна, если её арность равна 1, и бинарна, если её арность равна 2. Например, мы можем определить предикатную сигнатуру

{ a, P, Q }

(4)

объявляя a объектной константой, P – унарной предикатной константой, и Q – бинарной предикатной константой.

Возьмём предикатную сигнатуру s, которая включает по крайней мере одну предикатную константу и не включает ни одного из следующих символов:

•  объектные переменные x, y, z, x1, y1, z1, x2, y2, z2, ...,
•  пропозициональные связки,
•  квантор всеобщности " и квантор существования $,
•  скобки и запятая.

Алфавит логики предикатов состоит из элементов из s и четырёх групп дополнительных символов, указанных выше. Строка – это конечная последовательность символов из этого алфавита.

Терм – это объектная константа или объектная переменная. Строка называется атомарной формулой, если она является пропозициональной константой или имеет вид R(t1, ..., tn), где R – предикатная константа арности n (n > 0) и t1, ... , tn – термы. Например, если мы рассматриваем сигнатуру (4), то P(a) и Q(a, x) – атомарные формулы.

Множество X строк замкнуто относительно правил построения (для логики предикатов), если

•  каждая атомарная формула принадлежит X,
•  для любой строки F если F принадлежит X, то ¬F тоже принадлежит,
•  для любых строк F, G и любой бинарной связки Д, если F и G принадлежат X, то также принадлежит (F Д G),
•  для любого квантора K, любой переменной v и любой строки F если F принадлежит X, то также принадлежит Kv F.

Строка F является (предикатной) формулой, если F принадлежит всем множествам, которые замкнуты относительно правил построения.

Например, если рассматриваемая сигнатура есть (4), тогда

(¬P (a) Ъ $ x(P (x) & Q(x, y)))

– формула.

3.1 Является ли " x формулой?

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

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

•  каждая атомарная формула обладает этим свойством,
•  для любой формулы F, обладающей этим свойством, ¬F также обладает этим свойством,
•  для любых формул F, G, обладающих этим свойством, и любой бинарной связки Д, (F Д G) также обладает этим свойством,
•  для любого квантора K, любой переменной v и любой формулы F, обладающей этим свойством, Kv F также обладает этим свойством.

Тогда это свойство выполняется для всех формул.

3.2 Если формула содержит квантор, тогда она содержит переменную. Верно или нет ?

3.3 Если формула содержит квантор, тогда она содержит скобки. Верно или нет ?

При записи предикатных формул мы будем опускать некоторые скобки и применять другие сокращения, введённые в части 2. Строку вида

" v1 ··· " vn (n і 0)

будем писать как " v1 ··· vn, и подобным образом для квантора существования.

Свободные и связанные переменные

Множество свободных переменных* формулы F определяется рекурсивно, следующим образом:

Определение 22 (Свободные переменные).

•  Все переменные, входящие в атомарную формулу, являются свободными переменными этой формулы,
•  свободные переменные формулы F являются свободными переменными формулы ¬F,
•  переменные, являющиеся свободными для хотя бы одной из формул F или G, являются свободными переменными формулы (F Д G),
•  все свободные переменные формулы F кроме v являются свободными переменными формулы Kv F.

Определение 23 (Замкнутая формула). Формула без свободных переменных называется замкнутой формулой, или предложением.

Определение 24 (Связаная переменная). Переменная v связана в формуле F, если F содержит вхождение Kv, где K – квантор.

3.4 Найдите свободные переменные и связанные переменные формулы

$ y P(x, y) & ¬$ x P (x, x)

Представление предложений русского языка предикатными формулами

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

В этих упражнениях для перевода рассматривается сигнатура (4). Мы предполагаем, что объектные переменные служат для обозначения натуральных чисел и интерпретируем сигнатуру следующим образом:

•  a представляет число 10,
•  P(x) выражает условие ``x является простым числом'',
•  Q(x, y) выражает условие ``x меньше чем y''.

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

3.5 Все простые числа больше чем x.

Ответ: " y(P (y) Й Q(x, y)).

3.6 Существует простое число, которое меньше чем 10.

3.7 x равно 2. см. Указания

3.8 x равно 11. см. Указания

3.9 Существует бесконечно много простых чисел.

Подстановка

Определение 25 (Подстановка терма). Пусть F – формула и v – переменная. Результат подстановки терма t вместо v в F – формула, определённая рекурсивно следующим образом:

•  результат подстановки t вместо v в атомарную формулу F получается из F одновременной заменой всех вхождений v на t,
•  если результат подстановки t вместо v в F есть F' тогда результат подстановки t вместо v в ¬F есть ¬F',
•  если результат подстановки t вместо v в F и G есть F' и G' тогда результат подстановки t вместо v в (F Д G) есть (F'Д G'),
•  если результат подстановки t вместо v в F есть F' и w – переменная, отличающаяся от v, тогда результат подстановки t вместо v в Kw F есть Kw F',
•  результат подстановки t вместо v в Kv F есть Kv F.

3.10 Найдите результат подстановки константы a вместо x в формулу из задачи 3.4.

Когда мы намереваемся рассмотреть подстановки вместо переменной v в некоторую формулу, удобно обозначать эту формулу выражением F(v), и обозначать результат подстановки терма t вместо v в этой формуле через F(t) .

3.11 Если v не является свободной переменной F(v), тогда F(t) равно F(v).

Пусть F(x) обозначает формулу

" y (P(y) Й Q(x, y)),

предложенную выше как перевод условия ``все простые числа больше чем x'' (задача 3.5). Формула вида F(t), где t – терм, обыкновенно выражает то же условие применённое к значению t. Например, F(a) есть " y (P(y) Й Q(a, y)), что значит ``все простые числа больше чем 10'', F(z2) есть " y (P(y) Й Q(z2, y)), что значит ``все простые числа больше чем z2''. Существует, однако, одно исключение. Формула F(y), то есть, " y (P(y) Й Q(y, y)), выражает (неправильное) утверждение ``каждое простое число меньше чем оно само''. Проблема с этой подстановкой в том, что, когда мы подставляем переменную y вместо x в F(x), y ``захватывается'' квантором. Чтобы выразить утверждение ``все простые числа больше чем y'' предикатной формулой, мы будем использовать связанную переменную отличную от y и писать, например,

" z(P (z) Й Q(y, z))

Чтобы различать ``плохие'' подстановки, как в последнем примере, от ``хороших'', мы определим, когда терм t является подстановочным для переменной v в формуле F.* 

•  Если F – атомарная, тогда t является подстановочным для переменной v в F,
•  t является подстановочным для переменной v в ¬F тогда и только тогда, когда t является подстановочным для v в F,
•  t является подстановочным для v в (F Д G) тогда и только тогда, когда t является подстановочным для v и в F и в G,
•  t является подстановочным для v в Kw F тогда и только тогда, когда
  1.  t не содержит w и является подстановочным для v в F, или
  2.  v не является свободной переменной формулы Kw F.

3.12 Терм, не содержащий ни одной связанной переменной формулы F, является подстановочным в F для любой переменной.

Определение 26 (Универсальное замыкание). Универсальное замыкание формулы F – это предложение

" v1 ··· vn F,

где v1, ... , vn – все свободные переменные F.

Семантика

Выполнимость

Логическое следование

Выводы в логике предикатов

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

Правила для кванторов всеобщности

G |– F(v) (В") G |– " v F(v)	G |– " v F(v) (У") G |– F (t)
где v не является свободной	где t является
переменной для любой формулы в G	подстановочным для v в F(v)

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

3.19 (P(a) & " x (P(x) Й Q(x))) Й Q(a).

3.20 " xy P(x, y) Й " x P (x, x).

Правила для кванторов существования

G |– F(t) (В$) G |– $ v F(v)	G |– $ v F(v) G И { F(v) }|– C (У$) G |– C
где t – подстановочный	где для C и любой формулы из G
для v в F(v)	v не является свободной переменной

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

3.21 (P(a) Ъ P(b)) Й $ x P(x).

3.22 ¬$ x P(x) є " x ¬P(x).

Корректность и полнота логики предикатов

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

Теорема корректности. Если существует вывод замкнутой формулы F из множества формул G, тогда G влечёт F.

Теорема полноты. Для любой замкнутой формулы F и любого множества предложений G, если G влечёт F, то существует вывод F из некоторого подмножества G.

Полнота логики предикатов для случая счётного G и для другого множества правил вывода была доказана Куртом Гёделем в 1930 году.

Функциональные символы и равенство: синтаксис

Логика предикатов, определённая выше немного более ограничена, чем что обыкновенно называется ``логикой первого порядка'', и наша следующая цель – удалить эти ограничения. Во-первых, мы обобщим понятие терма. В дополнение к объектным константам и объектным переменным, мы разрешим построение термов с использованием символов для функций, ``функциональных констант''. Во-вторых, мы добавим к языку знак равенства, и уравнения будут включены как новый тип атомарных формул.

Наше наиболее общее понятие сигнатуры определяется следующим образом.

Определение 28 (Сигнатура,константы). Сигнатура – это множество символов двух типов – функциональных констант и предикатных констант – с неотрицательным целым числом, называемым арностью, связанным с каждым символом. Объектная константа – это функциональная константа арности 0. Функциональная константа унарна, если её арность равна 1, и бинарна, если её арность равна 2. Пропозициональная константы, так же как унарные и бинарные предикатные константы, определены как выше.

Определение 29 (Терм). Возьмём сигнатуру s, не включающую ни дополнительных символов, указанных в начале данной части, ни знака равенства. Множество X строк замкнуто относительно правил построения термов, если

•  каждая объектная константа принадлежит X,
•  каждая объектная переменная принадлежит X,
•  для каждой функциональной константы h арности n (n > 0) и любой строки t1, ... , tn, если t1, ... , tn принадлежит X, тогда также принадлежит h(t1, ... , tn).

Строка является термом, если она принадлежит все множествам, которые замкнуты относительно правил построения.*

3.23 Каждый терм содержит объектную константу или объектную переменную. Верно или нет ?

В логике первого порядка существуют три типа атомарных формул:

•  пропозициональные константы,
•  строки вида R(t1, ... , tn) где R – предикатная константа арности n (n > 0) и t1, ..., tn – термы,
•  строки вида (t1 = t2), где t1, t2 – термы.

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

Для любых термов t1 и t2, t1 № t2 обозначает формулу ¬(t1 = t2).

Функциональные символы и равенство: семантика

Выводы в логике первого порядка

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

Новые аксиомы выражают рефлексивность равенства и имеют вид Ж |– t = t , где t – произвольный терм. Новые правила вывода – правила замены:

G |– t1 = t2 G |– F(t1) (З=) G |– F(t2)

G |– t1 = t2 G |– F(t2) G |– F(t1)

где t1 и t2 свободные для v в F(v).* 

Для каждой из следующих формул найдите вывод из пустого множества посылок.

3.27 x = y Й f(x, y) = f(y, x).

см. Решение

3.28 " x $ y (y = f(x)).

3.29 $ y (x = y & y = z) Й x = z.

3.30 $ x (x = a & P (x)) є P (a).

Теории первого порядка

Теория первого порядка сигнатуры s определяется с помощью аксиом. Интерпретация, при которой истинны все аксиомы теории первого порядка G, называется моделью G. Если теория первого порядка G выполнима, мы также говорим что она непротиворечива. Логические следствия теории первого порядка называется её теоремами. Доказательство предложения F в теории первого порядка G есть вывод F из подмножества аксиом из G.

Теоремы корректности и полноты выполняются для логик предикатов с функциональными символами и равенством и могут быть сформулированы в рамках теорий первого порядка следующим образом. В соответствие с теоремой корректности, если существует доказательство предложения F в теории первого порядка G, тогда F является теоремой G. В соответствие с теоремой полноты Гёделя, обратное также верно: для любой теоремы F теории первого порядка G, существует доказательство F в G.

Однако, добавление правил вывода для кванторов второго порядка ведёт к формальной системе которая корректна, но не полна.

Пример: Теория линейного порядка

Арифметика первого порядка

Мы будем упрощать запись формул сигнатуры арифметики первого порядка (6) введением следующего обозначения: a будет записываться как 0, s(t) как t' , f(t1, t2) как t1+t2, и g(t1, t2) как t1 · t2. Аксиомы арифметики первого порядка являются универсальным замыканием следующих формул:

1.  x' № 0.
2.  x'= y'Й x = y.
3.  (F(0) & " v (F(v) Й F(v'))) Й " v F(v) для любой формулы F(v).
4.  x + 0 = x.
5.  x + y'= (x + y)'.
6.  x · 0 = 0.
7.  x · y'= x · y + x.

* 

Интерпретация (7) является моделью этой теории. Арифметика первого порядка имеет также другие модели, и некоторые из них совсем не похожи на систему натуральных чисел (задача 3.40).

В следующих формулах 1 обозначает терм 0', 2 – 0'', и 4 – 0''''. Через t1 Ј t2 мы обозначаем формулу $ v(t2 = t1 + v), где v – первая объектная переменная, которая не встречается в t1, t2.

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

3.34 2 № 4.

3.35 x' № x.

3.36 x'= x + 1.

3.37 x Ј x.

Нестандартные модели арифметики

Термы 0, 0', 0'', ... называются цифрами. Модель M арифметики первого порядка стандартна, если для каждого c О |M| существует цифра t такая, что tM = c.

3.38 Модель арифметики первого порядка (7) стандартна.

В соответствие с задачей 3.40, существуют модели арифметики первого порядка, которые не обладают этим свойством. Чтобы доказать существование такой модели, полезно рассмотреть следующую теорию первого порядка G. Сигнатура G получается из сигнатуры арифметики первого порядка добавлением буквы b в качестве новой объектной константы. Множество аксиом G получается из множества аксиом арифметики первого порядка добавлением формул b № 0, b № 0', b № 0'', ... в качестве новых аксиом.

3.39 G непротиворечива.

3.40 Арифметика первого порядка имеет нестандартную модель.

Существование нестандартных моделей арифметики следует из теоремы Сколема (1920), который обобщил раннюю работу Леопольда Лёвенхейма (1915). Возможность таких моделей резко контрастирует с результатом задачи 1.41. Разница связана с тем, что язык арифметики первого порядка является слишком ограниченным для выражения аксиомы индукции. ``Арифметика второго порядка'', в которой схема индукции заменяется по аксиоме (8), не имеет нестандартных моделей.

Теорема неполноты Гёделя

Пусть M – нестандартная модель арифметики первого порядка. Может случится что M ``не отличима'' от модели (7) в том смысле, что для любой замкнутой формулы F арифметики первого порядка F истинно при M тогда и только тогда, когда F истинно при (7). Но некоторые нестандартные модели не обладают этим свойством: может существовать предложение F такое, что при M предложение F истинно, а при (7) ¬F истинно. Так как и M и интерпретация (7) являются моделями арифметики первого порядка, значит ни F, ни ¬F не являются теоремами, а это означает, что арифметика первого порядка неполна. Этот факт, известный как теорема неполноты Гёделя, был доказан Куртом Гёделем в 1931 году.

Недоказуемые теоремы для диофантовых уравнений 

x	y	xy
1	1	1
1	0	1
0	1	1
0	0	0

x	y	xy
1	1	1
1	0	0
0	1	0
0	0	0

x
1	0
0	1

B

A

A

U

U

U

В

А

U

В

А

B

U

А

A=B

A\B=Ø

U

С=A=B

U

U

В

А

U

В

А

B

U

А

U

В

Р

А

U

В

Р=

А

Р=B

U

А

Р=A=B

U

u

А

рис.4

                               

             IQ

IP