Изучать философию нужно, когда философия вам не нужна. Когда вы догадываетесь, что стулья в вашей гостиной и Млечный путь связаны между собою, и более тесным образом, чем причины и следствия, чем вы сами с вашими родственниками. И что общее у созвездий со стульями – бесчувственность, бесчеловечность.
Иосиф Бродский. Выступление в Сорбонне
Да, Поэт прав: всякая формализация основ нашей жизни - мышления, призвана утвердить на абстрактном уровне бесчувственность, бесчеловечность. Но это оправдано, если целью наших исследований является не паразитическое применение методов человеческого интеллекта во благо личности, а его развитие.
Казалось бы, после Лекции 1 возвращаться к основам математической логики нет смысла. Но ведь там был приведён только материал, позволивший построить новую теорию - математическую логику событий. Были ли при этом исчерпаны все построения, позволяющие в широком плане моделировать искусственный интеллект? Очевидно, нет. Кроме того, перед вами не монография, а учебное пособие, где в методическом плане разделы должны быть достаточно автономны и содержать допустимое повторение основ, в разных вариантах складывающихся в систему. В то же время, излишнее теоретизирование недопустимо.
Джордж Буль (1815 - 1864) - английский математик и логик. В статье "Математический анализ логики" (1847) им впервые были высказаны идеи применения символического метода к логике. Буль не считал логику разделом математики, но находил глубокую аналогию между символическим методом алгебры и символическим методом представления логических форм и силлогизмов. Он показал, что логические конструкции в такой символике можно решать с помощью аналогов операций алгебры. Таким образом, Д. Буль ввёл базовые операции математической логики и заложил основы булевых функций.
Булевой алгеброй будем называть множество конечноместных (с конечным числом переменных) булевых функций, рассматриваемое вместе с заданными на нём операциями отрицания $$\bar{ } \text{ (}\neg\text{, НЕ)}$$, дизъюнкции $$\vee \text{ (ИЛИ)}$$ и конъюнкции $$\wedge \text{(, И)}$$.
В общем случае булевы функции следует определять рекурсивно. Это следует из того, что аргументы могут быть или рассматриваться как булевы функции.
При композиции или рекомпозиции структура булевых функций выражается с помощью скобок.
Булевы функции и их композиции образуют формулы F. Одной из основных задач булевой алгебры является установление тождественных соотношений вида F1 = F2. Формулы являются тождественными, если при любом наборе значений переменных ИСТИНА (1) или ЛОЖЬ (0), их значения истинности совпадают.
Соблюдается ранжирование операций: первым при прочих равных условиях выполняется отрицание, затем конъюнкции, затем дизъюнкции. При необходимости выполнения действий в ином порядке употребляются скобки.
Для булевой алгебры известен базовый набор тождественных соотношений, определяющий правила эквивалентных преобразований для установления тождественности формул или для обслуживания технологических требований.
(В Лекции 1 утверждается, что любая система распознавания, управления или принятия решений, описанная в терминах булевой алгебры, сводится к построению однослойной логической нейронной сети; это сокращает трудоёмкость обработки, повышает достоверность выводов, и делает даже нецелесообразным изучение структурированных логических нейронных сетей.)
Подчеркнём ещё раз, что тождественность булевых функций устанавливается с помощью таблицы, где по каждому набору значений переменных рассчитываются значения функций. Должно соблюдаться полное соответствие.
Рассматривая буквы латинского алфавита в качестве независимых переменных, повторим здесь базовый набор тождественных соотношений, приведённый в Лекции 1:
Закон коммутативности: $$x\lor y = y\lor x;$$$$ x\land y = y\land x. $$
Закон ассоциативности: $$x\lor (y\lor z) = (x \lor y) \lor z; $$ $$x\land (y\land z) = (x\land y) \land z. $$
Закон дистрибутивности: $$x\land (y \lor z) = (x\land y) \lor (x\land z);$$ $$ x \lor (y\land z) = (x \lor y) \land (x \lor z). $$
Закон де Моргана: $$\overline{x \lor y} = \overline{x} \land \overline{y}$$; $$\overline{x \land y} = \overline{x} \lor \overline{y}$$
Закон идемпотенции: $$x \lor x = x; $$$$ x\land x = x. $$
Закон поглощения: $$x \lor (x\land y) = x; $$$$ x\land (x \lor y) = x. $$
Закон склеивания: $$(x\land y) \lor (\bar{x} \land y) = y; $$$$ (x \lor y)\land (\bar{x} \lor y) = y. $$
Операция переменной с инверсией: $$x \lor \bar{x} = 1; $$$$ x \land \bar{x} = 0. $$
Операция с константами: $$x\land 0 = 0, x\land 1 = x; $$$$ x \lor 0 = x, x \lor 1 = 1. $$
Двойное отрицание: $$\bar{\bar{x}} = x. $$
Применяя эквивалентные преобразования на основе приведённого базового набора, можно аналитически упростить формулу, сделать её короче, нагляднее. Это можно делать, например, раскрывая или вводя скобки, выделяя или формируя конструкции, попадающие под действия перечисленных выше законов и операций.
Например,
$$F(x_1, x_2) = \overline{x_2}\wedge (\overline{x_1}\vee x_1)\vee (x_1\wedge x_2) = \overline{x_2}\vee (x_1\wedge x_2)=(\overline{x_2}\vee x_1)\wedge (\overline{x_2}\vee x_2)=\overline{x_2}\vee x_1$$В данном случае функция F(x1, x2) нам задана. А можно ли сформировать вид этой функции, задав с помощью таблицы её значения для всех возможных наборов значений переменных?
Да, табличный метод задания булевой функции породил полную, стандартизованную и легко реализуемую, предельно "прозрачную" форму - совершенную дизъюнктивную нормальную форму (СДНФ).
Пусть задано табличное представление некоторой булевой функции четырёх переменных (табл. 3.1)
| x1 | x2 | x3 | x4 | F |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Запишем в общем виде, основанном не на строгом доказательстве, а на догадке, СДНФ для четырёх переменных:
$$\begin{eqnarray} F(x_1,x_2,x_3,x_4)=F(\overline{x_1},\overline{x_2},\overline{x_3},\overline{x_4})\wedge (\overline{x_1}\wedge\overline{x_2}\wedge\overline{x_3}\wedge\overline{x_4})\vee \nonumber\\ F(\overline{x_1},\overline{x_2},\overline{x_3},x_4)\wedge (\overline{x_1}\wedge\overline{x_2}\wedge\overline{x_3}\wedge x_4)\vee F(\overline{x_1},\overline{x_2},x_3,\overline{x_4})\wedge (\overline{x_1}\wedge\overline{x_2}\wedge x_3\wedge\overline{x_4})\vee \nonumber\\ F(\overline{x_1},\overline{x_2},x_3,x_4)\wedge (\overline{x_1}\wedge\overline{x_2}\wedge x_3\wedge x_4)\vee F(\overline{x_1},x_2,\overline{x_3},\overline{x_4})\wedge (\overline{x_1}\wedge x_2\wedge\overline{x_3}\wedge\overline{x_4}) \vee \nonumber\\ F(\overline{x_1},x_2,\overline{x_3},x_4)\wedge (\overline{x_1}\wedge x_2\wedge\overline{x_3}\wedge x_4)\vee F(\overline{x_1},x_2,x_3,\overline{x_4})\wedge (\overline{x_1}\wedge x_2\wedge x_3\wedge\overline{x_4})\vee \nonumber\\ F(\overline{x_1},x_2,x_3,x_4)\wedge (\overline{x_1}\wedge x_2\wedge x_3\wedge x_4)\vee F(x_1,\overline{x_2},\overline{x_3},\overline{x_4})\wedge (x_1\wedge\overline{x_2}\wedge\overline{x_3}\wedge\overline{x_4})\vee \nonumber\\ F(x_1,\overline{x_2},\overline{x_3},x_4)\wedge (x_1\wedge\overline{x_2}\wedge\overline{x_3}\wedge x_4)\vee F(x_1,\overline{x_2},x_3,\overline{x_4})\wedge (x_1\wedge\overline{x_2}\wedge x_3\wedge\overline{x_4})\vee \nonumber\\ F(x_1,\overline{x_2},x_3,x_4)\wedge (x_1\wedge\overline{x_2}\wedge x_3\wedge x_4)\vee F(x_1,x_2,\overline{x_3},\overline{x_4})\wedge (x_1\wedge x_2\wedge \overline{x_3}\wedge\overline{x_4})\vee \nonumber\\ F(x_1,x_2,\overline{x_3}, x_4)\wedge (x_1\wedge x_2\wedge \overline{x_3}\wedge x_4)\vee F(x_1,x_2,x_3, \overline{x_4}) \wedge (x_1 \wedge x_2 \wedge x_3 \wedge \overline{x_4})\vee \nonumber\\ F(x_1 ,x_2 ,x_3 ,x_4) \wedge (x_1 \wedge x_2 \wedge x_3 \wedge x_4) \end{eqnarray} $$После подстановки заданных значений функции F получим:
Не будем искать дальнейших упрощений, так как полученный вид функции достаточно регулярен и, несмотря на кажущуюся избыточность, достаточно легко реализуется схемотехнически самой короткой логической цепочкой. Необходимо на первом уровне выполнить инверсию (отрицание), на втором уровне - выполнить конъюнкции, а на третьем - дизъюнкцию. Это особенно важно при построении быстродействующих устройств суперкомпьютера и, как оказалось (см. Лекцию 1), - при построении однослойных логических нейронных сетей.
Как видим формула (3.20) получилась весьма длинной, и это всего лишь для четырёх булевых переменных! Можно ли записать короче для любого количества n переменных?
Пусть задан вектор X = {x0, x1, ..., xn-1}, где xj, j = 0, ..., n-1, - булевы переменные. Введём понятие индексной маски вектора ИМВ. Она представляет собой двоичный код длины n, принимающий 2n значений индекса i от равенства нулю до равенства единице всех разрядов. Пусть при данном применении единичные разряды ИМВ, образующие двоичное значение индекса i, указывают на те булевы переменные, которые используются в выражении (3.20) без знака отрицания. Такую i-ю выборку вектора Х обозначим ХИМВ=i. Функцию F от неё обозначим F(ХИМВ=i), а соответствующую ей конъюнкцию булевых переменных, с учётом того, что часть их фигурирует со знаком отрицания, обозначим
Тогда всю формулу СДНФ можно записать:
(3.21)
В рассмотренном выше примере для n = 4 не зря каждая следующая комбинация выбиралась по строкам таблицы условным сложением с единицей некоторой подразумеваемой маски. Эти комбинации образовали счётное множество с индексом i, пробегающим от нуля до единиц по всем четырём разрядам. Частный вид подтверждает общую формулу (3.21):
(3.22)
В данном случае надо помнить о специальном назначении маски, метящей булевы переменные, используемые без знака отрицания.
Маски векторов используются программистами весьма часто: для альтернативного выполнения векторных операций, для маскирования прерывания, для маскирования направлений обмена и пр.
Из СДНФ легко выводится СКНФ - совершенная конъюнктивная нормальная форма, представляющая собой "конъюнкцию дизъюнкций". Поскольку она практически не применяется, мы её рассматривать не будем.
Отметим, что табличная запись булевых функций не только достаточна, но практически всегда используется разработчиками цифровых электронных устройств. Более того, сложилась практика использования ассоциативной памяти (АП) для построения многих устройств компьютера, таких как: дешифратор, КЭШ в сверхоперативной памяти, механизм перевода математических адресов в физические, устройство хранения и выборки глобальных данных, арбитры коммутаторов и др.
Табличная запись значений одной или более булевых функций производится в строках - регистрах АП, разбитых на две части: в левой части указан набор значений переменных, а в правой - вектор значений булевых функций. В результате одновременного сравнения кода возникшей ситуации со всеми наборами переменных, мгновенно производится выбор вектора значений выходов устройства. То есть, устройство со многими входами и многими выходами записывается и работает с помощью модуля ассоциативной памяти, реализующего систему булевых функций.
Так решаются задачи обеспечения высокого быстродействия, стандартизации и унификации.
Требования стандартизации и унификации элементной базы и функциональных устройств электронной техники, в том числе нейросетевых технологий, выдвигает научную задачу синтеза сложных булевых функций на основе более простых базовых, стандартных. В этом случае функция с меньшим количеством булевых переменных "погружается" в более сложную булеву функцию, где добавляются новые переменные.
Существует теорема разложения, которую проиллюстрируем конкретным, легко обобщаемым примером:
$$F(x_1,x_2,x_3,x_4,x_5) = (\bar{x_1} \land \bar{x}_2 \land F(0,0,x_3,x_4,x_5)) \lor (\bar{x}_1 \land x_2 \land F(0,1,x_3,x_4,x_5)) \lor (x_1 \land \bar{x}_2 \land F(1,0,x_3,x_4,x_5)) \lor (x_1 \land x_2 \land F(1,1,x_3,x_4,x_5)) $$Предметом дальнейших исследований примем любое законченное утверждение на любом формальном или неформальном языке - высказывание, для которого имеет смысл говорить о его истинности или ложности. Это было уже объявлено в Лекции 1.
Основной задачей, которую ставит перед собой математическая логика, является формализация мыслительных процессов в широком смысле - в смысле доказательства или поиска истины, а также расширения знаний. Для этого надо сформулировать "правильное", непротиворечивое логическое исчисление, включающее:
Тождественно истинными являются высказывания, которые не требуют задания каких-либо дополнительных условий для проверки своей истинности на протяжении всего процесса логического вывода.
Например, высказывание "кислород является газом" имеет значение ИСТИНА (1) в тех условиях, в которых оно рассматривается. Ведь кислород может находиться не только в газообразном состоянии.
Высказывание "дважды два - одиннадцать" на первый взгляд представляется заведомо ложным. Однако если предположить, что вместо десятичной системы счисления используется троичная система, при условии сохранения привычных названий многозначных чисел, то данное высказывание становится истинным.
Поэтому обязательным условием правильности выводов и следствий является то, чтобы постоянное высказывание, подобно константе, не меняло значение истинности в процессе логического вывода.
В исчислении высказываний не интересуются внутренней смысловой структурой элементарных высказываний. Естественно поэтому для их обозначения использовать отдельные буквы некоторого алфавита (обычно латинского и готического). Отдельными буквами могут обозначаться и так называемые переменные высказывания, что означает, что вместо этой буквы всегда может быть подставлено любое конкретное постоянное высказывание, как истинное, так и ложное.
Высказывания, как постоянные, так и переменные, можно объединять в сложные высказывания, используя связки "и", "или", "если - то", "не" и т.п. Если в состав сложного высказывания входят переменные высказывания, представленные буквами, то при замене этих букв одними высказываниями сложное высказывание может оказаться истинным, а при замене другими - ложными. Например, сложное высказывание "А и В", где А и В - переменные высказывания, будет, очевидно, истинным в том и только том случае, если оба высказывания будут истинными.
Существуют и такие сложные высказывания, содержащие в своём составе переменные высказывания, которые остаются истинными при любых значениях переменных высказываний. Например, сложное высказывание "если неверно то, что высказывание А ложно, то высказывание А истинно" остаётся истинным, какое бы высказывание ни подставили на место переменного высказывания А. Такие высказывания называют тождественно истинными.
Например, возьмём высказывание "извозчик Петров - водитель кобылы". Если неверно то, что Петров не водитель кобылы, значит он водитель кобылы. Сложное высказывание истинно. Если же неверно, что Петров водитель кобылы, значит он не водитель кобылы. Сложное высказывание снова истинно, ибо соответствует правде и не содержит противоречий.
Задача выделения тождественно истинных высказываний во множестве всех возможных высказываний является важнейшей задачей любого логического исчисления.
После всех предварительных замечаний перейдём к построению собственно исчисления высказываний, или, как его ещё иногда называют, пропозиционного исчисления.
Введём базовые операции.
А и В истинны. В обычной речи этой операции соответствует связка "и".А или В. Однако, хотя мы уже применили связку "или", под ней понимается не разделительное "или", понимаемое в смысле "либо - либо", когда А и В не могут быть оба истинны. В данном определении высказывание $$А \lor В$$ истинно и при истинности обоих высказываний А и В.А истинно, а В ложно. А называется посылкой, а В - следствием. В обычной речи операция $$\to$$ (импликация) соответствует связке "если - то": "если А, то В". В определении математической логики это высказывание при ложном А всегда истинно, независимо от того, истинно или ложно высказывание В. Этот факт можно кратко сформулировать так: "из ложного следует всё что угодно". В обычной речи иногда подразумевается, что когда А ложно, то высказывание "если А, то В" не имеет смысла. (Порой кажется, что принятый формализм прямо-таки противоречит здравому смыслу. Например, высказывание "из того, что у льва есть когти, следует, что снег белый" формально истинно. Но так ли это в действительности, решать не математикам-логикам.)А истинно, и истинное, если А ложно.А и В оба истинны или оба ложны. Это высказывание называется эквивалентностью.Как и в булевой алгебре, значение ИСТИНА будем обозначать единицей, значение ЛОЖЬ - нулём.
В табл. 3.2 сведены соотношения истинности для базовых операций.
| А | В | $$А \land В$$ | $$А \lor В$$ | $$А \to В$$ | $$\neg А$$ | $$А \sim В$$ |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 |
Как и в булевой алгебре введём ранжирование операций: $$\neg, \land, \lor, \to, \sim$$.
Например, формула $$\neg А \lor В \land С \to В \lor С$$ понимается как $$((\neg А) \lor (В \land С) \to (В \lor С)$$. Формула $$А \sim В \to С$$ должна пониматься как $$(А) \sim ((В) \to (С))$$ и т.д.
Введённые определения решают лишь две части задачи построения исчисления высказываний: проблему формализации записи сложных высказываний.
Завершающая часть задачи - нахождение способа определения тождественной истинности высказываний - может быть решена двумя путями: содержательным и формальным.
При содержательном подходе необходимо помнить о содержательном смысле букв и связок. В то же время, нет необходимости помнить само высказывание, достаточно помнить функцию истинности этого высказывания: А = ИСТИНА, если высказывание, обозначенное этой буквой, истинно, и А = ЛОЖЬ, если высказывание ложно. Функция истинности отождествляется с самой буквой, которая теперь обозначает булеву переменную.
Тогда каждую формулу $$\Omega$$ исчисления высказываний можно интерпретировать как формулу в булевой алгебре с включённой в неё дополнительно операцией импликации $$\to$$. Входящие в формулу $$\Omega$$ постоянные высказывания должны быть заменены соответствующими булевыми константами (значениями их функций истинности). Символы, соответствующие переменным высказываниям, рассматриваются как аргументы булевой функции, представляемой формулой $$\Omega$$. Эта функция называется функцией истинности сложного высказывания, выражаемого формулой $$\Omega$$.
На содержательном уровне построения исчисления высказываний тождественно истинными считаются те, и только те формулы этого исчисления (сложные высказывания), функции истинности которых принимают значения ИСТИНА (1) при всех значениях переменных.
Представленный содержательный аспект исчисления высказываний позволяет сравнительно просто решить вопрос о тождественной истинности любого сложного высказывания: достаточно перебрать все возможные наборы значений истинности составляющих его переменных высказываний и проверить, на всех ли этих наборах функция истинности рассматриваемого сложного высказывания принимает значение ИСТИНА.
Например, рассмотрим формулу $$\Omega = А \land В \to А$$ и составим для неё таблицу истинности с учётом "промежуточного" результата $$А \land В$$:
| А | В | $$А \land В$$ | $$А \land В\to А$$ |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Видим, что при всех значениях переменных высказываний, сложное высказывание является истинным. Следовательно, рассмотренная формула $$\Omega$$ тождественно истинная.
Несмотря на простоту и "прозрачность", содержательный аспект исчисления высказываний имеет ряд недостатков:
При формальном подходе к установлению тождественной истинности пользуются эквивалентными преобразованиями булевой алгебры. Поскольку там нет импликации, исключим её согласно равенству:
$$(С \to D) = (\neg C \lor D).$$Проверим его справедливость с помощью таблицы истинности:
| С | D | $$C\to D$$ | $$\neg C \lor D$$ |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Рассмотрим тот же пример:
$$А \land В\to А = \neg (А \land В) \lor А = \neg А \lor \neg В \lor А = (\neg А \lor А) \lor \neg В = 1 \lor \neg В = 1.$$Эта цепочка доказывает тождественную истинность заданной формулы.
Таким образом, формальный аспект исчисления высказываний характеризуется тем, что полностью отвлекаются от содержательного смысла формул и рассматривают их как конечные последовательности символов, подлежащие эквивалентным преобразованиям.
Для этих преобразований, подобно и в дополнение базовому набору соотношений булевой алгебры, известна наиболее употребительная система аксиом С.К. Клини:
Первые десять аксиом представляют собой десять формул исчисления высказываний, объявленных тождественно истинными по определению. Они предполагают возможность подстановки вместо букв А, В, С любых формул исчисления высказываний (не обязательно истинных). Такая подстановка, по определению, не нарушает тождественной истинности аксиомы.
Одиннадцатая аксиома - это так называемое правило вывода, позволяющее, по определению, считать доказанной истинность формулы $$\Psi$$, если истинность формул $$\Omega$$ и $$\Omega \to \Psi$$ уже была установлена ранее. Если формулы $$\Omega$$ и $$\Omega \to \Psi$$ были при этом тождественно истинными. То тождественно истинной будет и формула $$\Psi$$. Предполагается по определению, что все тождественно истинные формулы (и только такие формулы) исчисления высказываний могут быть получены из аксиом в результате подстановок 1 - 10 и применения (возможно, многократного) правил вывода 11.
Формула $$\Psi$$ называется непосредственным следствием формул $$\Omega$$ и $$\Omega \to \Psi$$.
Формулы, тождественно истинные в содержательном смысле, для краткости будем называть просто содержательно истинными, противопоставляя их формально истинным, т.е. формально доказуемым.
Говорят, что формула $$\Theta$$ исчисления высказывания выводится из условно истинных формул (истинность которых предполагается на протяжении рассматриваемого вывода) $$\Omega1, \Omega_2, ..., \Omega_n$$, если она может быть получена из этих формул и аксиом 1 - 10 исчисления высказываний в результате применения конечного числа раз правил непосредственного следствия.
Более точно это означает последовательное использование трёх условий, лежащих в основе правил вывода:
Цепочка формул, получающихся в результате последовательного применения этих трёх правил, которая кончается формулой $$\Theta$$, называется формальным выводом этой формулы.
Для обозначения выводимости употребляется специальный символ \vdash (читается как "даёт"), слева от которого пишутся условно истинные формулы, а справа их следствия: $$\Omega_1, \Omega_2, ..., \Omega_n \to \Theta$$. Аксиомы здесь как бы включаются в символ $$\vdash$$. Тогда для любой формально истинной формулы $$\Theta$$, выводимой только лишь на основе аксиом 1 - 10, можно писать $$\vdash \Theta$$.
Приведём простейшие примеры формального вывода, нумеруя последовательные шаги.
Приведённая цепочка формул по определению является формальным доказательством формулы $$А \to А$$. Таким образом, эта формула принадлежит к числу формально истинных формул, и её можно записать
$$\vdash А \to А.$$Другим примером является получение следствий из трёх условно истинных формул $$А, В, А \to (В \to С)$$. За пять шагов из этих формул может быть получена формула С.
А (первая данная нам условно истинная формула).В (вторая данная нам формула).С (непосредственное следствие формул 2 и 4).Таким образом, формула С выводима из формул $$А, В, А \to (В \to С)$$ и мы можем записать $$А, В, А \to (В \to С) \vdash С$$.
Хотя условно истинные формулы и не обладают тождественной истинностью, легко видеть, что в окончательной записи (условной) выводимости любая буква может быть заменена произвольной формулой, если только такая замена производится как слева, так и справа от знака $$\vdash$$.
Подобным же способом можно доказать соотношения:
Обозначим $$\Gamma$$ произвольную конечную совокупность формул исчисления высказываний. Применяя более сложную технику доказательства (индукцию по длине вывода), можно доказать следующую теорему о дедукции.
Теорема 3.1. Если в исчислении высказываний формула В выводима из совокупности формул $$\Gamma$$ и А, то из $$\Gamma$$ выводима формула $$А \to В$$.
В теории доказательств часто применяются две общие схемы.
Легко проверить, что все аксиомы исчисления высказываний 1 - 10 представляют собой содержательно истинные формулы. Иначе говоря, соответствующие им функции истинности принимают при всех значениях переменных значение ИСТИНА. Это свойство, очевидно, сохраняется при подстановках любых формул исчисления высказываний вместо букв, входящих в аксиомы.
Из таблицы истинности для импликации $$\to$$ непосредственно следует, что из содержательной истинности формул $$\Omega$$ и $$\Omega \to \Psi$$ вытекает содержательная истинность формулы $$\Psi$$. Но тогда очевидно, что все доказуемые (формально истинные) формулы будут и содержательно истинными. Верно (хотя и гораздо сложнее доказуемо) также и обратное, что формулируется следующей теоремой.
Теорема 3.2. При формальном построении исчисления высказываний с помощью системы аксиом 1 - 11 формально доказуемыми (формально истинными) будут все те, и только те формулы этого исчисления, которые являются тождественно истинными в содержательном смысле.
Теорема 2 содержит в себе два утверждения относительно выбранной системы аксиом: эта система содержательно непротиворечива и эта система содержательно полна, т.е. нет ни одной содержательно истинной формулы исчисления высказываний, которую нельзя было бы доказать формально с помощью этой системы аксиом.
При этом, естественно называть систему аксиом формально непротиворечивой, если с её помощью нельзя вывести какую-нибудь формулу $$\Omega$$ вместе с её отрицанием $$\neg \Omega$$; в противном случае она формально противоречива.
Отметим, что хотя присоединение недоказуемых формул в качестве новых аксиом исчисления высказываний, нарушает свойство формальной непротиворечивости, ничто не мешает нам присоединить к системе аксиом формулы $$\Omega_1, ..., \Omega_n$$ в качестве не тождественно, а лишь условно истинных формул. (Это характерно, например, при переходе в мир грёз или сказок.) Противоречие возникает тогда и только тогда, когда конъюнкция $$\Omega_1 \land \Omega_2 \land ... \land \Omega_n $$ является тождественно ложной формулой.
Особенностью исчисления предикатов является наличие предметных переменных, пробегающих конечную или бесконечную область значений, называемую предметной областью. Отдельные значения этой области называются предметами или объектами.
Предикатом называют функцию предметных переменных P(x1, x2, ..., xn), представляющую собой переменное высказывание, истинность или ложность которого определяется наборами значений переменных x1, x2, ..., xn.
Если предикат Р не является тождественно истинным или тождественно ложным, то на одних наборах значений предметных переменных он принимает значение ИСТИНА (1), а на других - значение ЛОЖЬ (0).
Какова цель построения исчисления предикатов?
При построении теоретических основ логических нейронных сетей - математической логики событий - мы исходили из высказываний, вкладывая в них конкретный смысл на основе факторного пространства событий. Это пространство и отражало предметную область. Значит, до перехода к нечётким данным, мы пользовались расширением исчисления высказываний в сферу исчисления предикатов!
Действительно, ведь необходимо придать формальному языку логического вывода "человеческий", объектовый и событийный смысл. Чтобы видеть и подразумевать предметы и объекты, свойства и обстоятельства, о которых что-то говорится. Чтобы не были истинными такого рода высказывания, как "из-за того, что у льва когти, снег белый". Чтобы лев и снег действенно участвовали в поиске истины.
Введение понятия предметной области сразу же влечёт применение теоретико-множественного аппарата, подобно тому, что привлекался в силлогистике.
Мы подробно не останавливались и не будем останавливаться на анализе преемственности учения о силлогистике и о современной математической логике, но готовы высказаться в защиту тезиса о том, что "всё новое - хорошо забытое старое". Именно поэтому мы ввели в курс об искусственном интеллекте силлогистику Аристотеля.
Например, высказывание "четыре больше двух" в исчислении высказываний является неразложимым. Если же ввести предикат P(x, y) на множестве целых неотрицательных чисел в качестве предметной области, который является истинным тогда и только тогда, когда $$x > y$$, то приведённое высказывание запишется в форме Р(4, 2), которая даёт ясное представление о внутренней структуре высказывания.
Наличие предметных переменных позволяет ввести квантор общности \forall x и квантор существования $$\exists x$$.
Выражение $$\forall xP(x)$$ - условное обозначение высказывания "для всех х предикат Р(x) является истинным"; выражение $$\exists xP(x)$$ - условное обозначение высказывания "существует x, для которого предикат Р является истинным".
В теории доказательств эти кванторы связаны между собой:
$$\neg \forall xP(x) = \exists x\neg P(x)$$Например, высказывание "все солдаты карантинной роты стригутся наголо" в случае отрицания звучит: "не все солдаты карантинной роты стригутся наголо". Это, в свою очередь, может быть сформулировано: "существует солдат карантинной роты, постриженный не наголо".
Пусть Р(x) - функция "x стрижётся наголо". Тогда вышесказанная трансформация может быть изображена цепочкой:
Если предметная область состоит из конечного числа объектов x1, x2, ..., xk, подобных солдатам, то выражение $$\forall xP(x)$$ сводится к конъюнкции $$P(x_1 ) \land Р(x_2 ) \land ... \land Р(x_k )$$, а выражение $$\exists xР(x)$$ - к дизъюнкции $$P(x_1 ) \lor Р(x_2 ) \lor ... \lor Р(x_k )$$. В случае бесконечной предметной области подобное сведение оказывается невозможным, неконструктивной.
Возьмём более сложный пример. Вспомним определение непрерывности функции f(x) в точке x0: "Функция f(x) непрерывна в точке x0, если для любого $$\epsilon > 0$$ существует $$\delta > 0$$, что если $$|x - x_0 | < \delta $$, то $$| f(x) - f(x_0 )| < \epsilon $$". Сокращённо можно записать:
В случае нарушения непрерывности функции мы говорим: "не для всякого $$\epsilon > 0$$ существует $$\delta > 0$$, что если $$| x - x_0 | < \delta $$, то $$| f(x) - f(x_0 )| < \epsilon $$". Или: "существует $$\epsilon > 0$$, что для любого $$\delta > 0 \neg (| x - x_0 | < \delta \to | f(x) - f(x_0 )| < \epsilon )$$". Последний предикат можно записать формально:
$$ \exists \epsilon > 0\forall \delta > 0 \neg P(x, x_0 , f(x), f(x_0 ), \epsilon , \delta ), \text{ где } P(x, x_0 , f(x), f(x_0 ), \epsilon , \delta ) = (| x - x_0 | < \delta \to | f(x) - f(x_0 )| < \epsilon ). $$В выражениях $$\forall xP(x)$$ и $$\exists xР(x)$$ переменная x оказывается связанной соответствующим квантором, в отличие от свободных переменных. В формулах (3.47) и (3.48) переменные $$\epsilon $$ и $$\delta $$ связанные, а переменные x, x0, f(x), f(x0) - свободные.
Обычно используют узкое исчисление предикатов, которое разрешает связывать с помощью кванторов лишь предметные переменные. Входящие в формулу предикаты предполагаются при этом неизменными. В так называемом расширенном исчислении предикатов употребляются переменные предикаты и предикатные кванторы.
Как и в случае исчисления высказываний, при построении исчисления предикатов недостаточно указать лишь способ записи формул. Необходимо задать правила преобразования формул, выражаемые аксиомами.
В число аксиом исчисления предикатов включаются все 11 аксиом исчисления высказываний, (3.25) - (3.35).
Кроме них, вводятся четыре специфических постулата, которым присвоим номера от 12 до 15:
12. $$\frac{C \to P(x)}{C \to \forall xP(x)}$$
13. $$\forall xP(x) \to P(t)$$
14. $$P(t) \to \exists xP(x)$$
15. $$\frac{P(x) \to C}{\exists xP(x) \to C}$$
С помощью указанных аксиом - постулатов можно производить формальный вывод новых эквивалентных формул совершенно таким же способом, как и в исчислении высказываний.
Заметим, что выражения P(x) и P(t) в аксиомах 12 - 15 должны пониматься не только как элементарные одноместные предикаты, но и как произвольные формулы исчисления предикатов, содержащие буквы x и t в качестве свободных переменных.
При всех подстановках подразумевается, что свободные и связанные переменные в формулах, получаемых в результате подстановок, должны обозначаться различными буквами, как в (3.50) и (3.51). Такое условие позволяет избежать так называемой коллизии переменных, вызывающей непредвиденное связывание переменных, которые должны были бы остаться свободными.
При условии принятия мер во избежание коллизии переменных, в исчисление предикатов переносятся все результаты выводимости одних формул из других. Остаётся справедливой и теорема дедукции.
В частности, если формула $$\Psi$$ выводима в исчислении высказываний из формулы $$\Omega$$, то формула $$\Omega \to \Psi$$, при условии принятия мер против коллизии переменных, будет выводимой и в исчислении предикатов.
Из аксиом 12 - 15 легко образуются следующие правила выводимости:
Введение квантора общности ($$\forall $$-введение)
$$A(x) \vdash x \forall xA(x).$$(Значок переменной x, который пишется над символом выводимости $$\vdash$$, означает, что соответствующая переменная варьируется, превращаясь из свободной в связанную. Тогда свободные переменные, не варьирующиеся в процессе вывода, принято называть фиксированными.)
Введение квантора существования ($$\exists $$-введение)
$$A(t) \vdash \exists xA(x).$$Удаление квантора общности ($$\forall $$-удаление)
$$\forall xA(x) \vdash A(t). $$Удаление квантора существования по С.К. Клини:
$$\text{Если} \Gamma , A(x) \vdash C, \text{то} \Gamma , \exists xA(x) \vdash x C.$$(Напоминаем, что $$\Gamma$$ - произвольная конечная совокупность формул.)
Если имеет место выводимость $$\Gamma , А \vdash В$$, причём, в процессе вывода свободные переменные, входящие в формулу А, остаются фиксированными, то имеет место сводимость $$\Gamma \vdash А \to В$$.
Используя символ эквивалентности $$\sim$$ в том же смысле, что и в исчислении высказываний, и обозначая буквой А любую формулу, не содержащую свободной переменной х, можно легко вывести следующие соотношения:
Правила (3.58) и (3.59) показывают возможность изменения порядка применения одноимённых кванторов. Для разноимённых кванторов смена их порядка в соотношении (3.61) не имеет места. Теоретико-множественный анализ соотношения $$\vdash \forall x \exists yP(x, y) \to \exists y\forall xP(x, y)$$, двойственного (3.61), обнаруживает примеры его абсурдности. ("Отрицательный вывод не доказывается, а показывается" - важное правило теории доказательства; см. пример о непрерывности функции.)
Содержательная непротиворечивость исчисления предикатов, как и исчисления высказываний, понимается в том смысле, что выводимыми в этом исчислении могут быть лишь тождественно истинные формулы, т.е. такие формулы, которые остаются истинными для любой предметной области и для любой конкретной интерпретации входящих в них предикатов. Здесь кроется некоторая неконструктивность подхода, связанная с неявно предполагающейся возможностью перебора всех значений предметных переменных при определении тождественной истинности. В случае бесконечной предметной области это требует бесконечного числа шагов. Поэтому широко привлекается теоретико-множественный подход, основанный на смысловом анализе как предметной области, так и заданных на ней предикатов.
Подобным путём устанавливается и формальная непротиворечивость исчисления предикатов, как невозможность вывести в этом исчислении некоторую формулу вместе с её отрицанием.
В случае конечных предметных областей вопрос о содержательной полноте исчисления предикатов сводится к соответствующему вопросу для исчисления высказываний и потому решается конструктивно.
Возможность формального вывода в этом исчислении любой тождественно истинной формулы была решена К. Гёделем. Однако в случае бесконечных предметных областей установление содержательной полноты исчисления предикатов требует привлечения средств, выходящих за пределы конечной (финитной) математики.
В противоположность содержательной полноте, называемой также полнотой в широком смысле, полнота в узком смысле уже не имеет места в исчислении предикатов.
Действительно, к числу аксиом исчисления предикатов присоединим формулу $$\exists xР(x) \to \forall xР(x)$$, не выводимую в этом исчислении, но не приводящую к противоречию, если предметная область состоит из единственного объекта. Если предметная область состоит из двух объектов х и у, указанная аксиома превращается в формулу $$Р(x) \lor Р(у) \to Р(x) \land Р(у)$$, не являющуюся тождественно истинной и потому не выводимую из остальных аксиом.
Наряду с тождественно истинными формулами, в исчислении предикатов рассматривают так называемые выполнимые формулы.
Выполнимой будем называть такую формулу, которая может быть истинной при выборе подходящей предметной области и при должном определении заданных на ней предикатов.
При такой постановке обратной, в каком-то смысле, задачи первична формула, а вторичны условия, при которых она выполняется, становясь тождественно истинной, а не наоборот. Предполагается, что формула имеет общий вид и не содержит символов индивидуальных предметов и индивидуальных предикатов.
Каждая тождественно истинная формула является и выполнимой. Обратное в общем случае неверно. Примером выполнимой, но не тождественно истинной формулы может служить формула, рассмотренная выше, $$\exists xР(x) \to \forall xР(x)$$. Эта формула является тождественно истинной лишь на таких предметных областях, которые состоят из одного-единственного объекта.
Проблема разрешимости для исчисления предикатов состоит в том, чтобы указать единый эффективный алгоритм для определения выполнимости или невыполнимости любой заданной формулы исчисления предикатов на какой-либо предметной области.
В отличие от исчисления высказываний, проблема разрешимости в общем случае для исчисления предикатов, как показали Чёрч и Тьюринг, вообще не имеет решения. Иными словами, не существует единого конструктивного приёма для установления выполнимости или невыполнимости любой формулы исчисления предикатов.
Часто проблема разрешимости для исчисления предикатов формулируется несколько в иной форме: найти алгоритм для определения тождественной истинности любой данной формулы в этом исчислении.
Таким образом, в отношении проблемы разрешимости, исчисление предикатов коренным образом отличается от исчисления высказываний.
Если ограничиться частными видами формул, то разрешающий алгоритм может быть построен и в случае исчисления предикатов.
Такой алгоритм можно, например, построить для формул исчисления предикатов, содержащих лишь одноместные предикаты. Для установления выполнимости или невыполнимости формулы, содержащей n одноместных предикатов, достаточно ограничиться рассмотрением предметных областей, состоящих не более чем из 2n объектов. В результате проверка выполнимости (или тождественной истинности) предикатной формулы (после замены кванторов конъюнкциями или дизъюнкциями) сводится к проверке выполнимости (или, соответственно, тождественной истинности) полученной формулы исчисления высказываний.
В общем случае при решении вопроса о выполнимости или невыполнимости конкретной формулы существенную помощь может оказать предварительное приведение этой формулы к так называемой нормальной форме.
Различают два вида нормальных форм: предварённую форму и нормальную форму Сколема.
Предварённая форма отличается тем, что все кванторы, если они имеются, должны быть вынесены в самое начало формулы, а область действия каждого из них должна распространяться до конца этой формулы.
В нормальной форме Сколема требуется дополнительно, чтобы все кванторы существования предшествовали всем кванторам общности.
Если формула записана в предварённом виде, то её часть, стоящая после кванторов (бескванторная часть формулы), может рассматриваться как формула исчисления высказываний. Каждый предикат рассматривается при этом просто как переменное высказывание. Тогда в этой формуле можно исключить все знаки импликации, заменяя конструкции вида $$А \to В$$ через $$\neg А \lor В$$, а затем привести её к дизъюнктивной нормальной форме. Такое преобразование приводит исходную предикатную формулу к эквивалентной ей предикатной формуле.
Справедлива теорема:
Теорема 3.3. Для всякой формулы $$\Omega$$ (узкого) исчисления предикатов существует эквивалентная ей формула $$\Psi$$, записанная в предварённой форме. Существует единый алгоритм приведения произвольной предикатной формулы к предварённой форме.
Справедливость сформулированной теоремы вытекает из легко проверяемых соотношений:
$$\vdash \neg \forall xР(x) \sim \exists x\neg Р(x); $$ $$\vdash \neg \exists xР(x) \sim \forall x\neg Р(x);$$ $$\vdash Q \land \forall xP(x) \sim \forall x(Q \land P(x));$$ $$\vdash Q \land \exists xP(x) \sim \exists x(Q \land P(x));$$ $$\vdash Q \lor \forall xP(x) \sim \forall x(Q \lor P(x));$$ $$\vdash Q \lor \exists xP(x) \sim \exists x(Q \lor P(x));$$Поскольку импликация может быть заменена операциями дизъюнкции и отрицания, то с помощью выписанных формул при соблюдении условий, исключающих возможность возникновения коллизии переменных, можно производить последовательную перестановку кванторов со всеми составляющими формулу символами, отличными от кванторов, пока все кванторы не окажутся в левой части формулы.
Приведём пример подобного преобразования:
$$P(x) \lor \neg \forall yQ(x, y) \sim P(x) \lor \exists y\neg Q(x, y) \sim \exists y(P(x) \lor \neg Q(x, y)).$$Последняя формула соответствует требуемой предварённой форме исходной формулы.
Для нормальной формы Сколема прямого аналога теоремы 3.3 не существует: не для всякой формулы исчисления предикатов существует эквивалентная формула, имеющая нормальную форму Сколема.
Однако понятие эквивалентности может быть так обобщено, что любую формулу исчисления предикатов можно будет привести к нормальной форме Сколема.
Введём понятие дедуктивной эквивалентности.
Формула $$\Omega$$ называется дедуктивно эквивалентной формуле $$\Psi$$, если, присоединив формулу $$\Omega$$ к системе аксиом исчисления предикатов, получим возможность вывести формулу $$\Psi$$ из расширенной системы аксиом и наоборот, присоединив к системе аксиом формулу $$\Psi$$, получим возможность вывести формулу $$\Omega$$.
Это определение применимо не только к исчислению предикатов, но и к любому логическому исчислению, в том числе к исчислению высказываний.
Легко видеть по рассмотренному выше примеру, что обычная эквивалентность формул влечёт их дедуктивную эквивалентность.
Справедлива следующая теорема Сколема:
Теорема 3.4. Для всякой формулы узкого исчисления предикатов существует дедуктивно эквивалентная ей формула, записанная в нормальной форме Сколема. Существует алгоритм приведения любой формулы к дедуктивно эквивалентной ей сколемской форме.
Очевидно, что если две формулы дедуктивно эквивалентны, то из тождественной истинности одной следует тождественная истинность другой. То есть, приведя формулу к нормальной форме Сколема, следует решать проблему тождественной истинности относительно этой формы.
Это же обстоятельство может быть использовано при доказательстве содержательной полноты исчисления предикатов, поскольку для такого доказательства достаточно установить выводимость всех тождественно истинных формул, записанных в нормальной форме Сколема. Действительно, установив выводимость всех указанных формул, мы тем самым установим и выводимость всех дедуктивно эквивалентных им формул, т.е. всех тождественно истинных формул исчисления предикатов.
Известно большое количество классов формул, для которых проблема разрешимости решается положительно. Ограничения, с помощью которых выделяются указанные классы, касаются не только характера, числа и порядка расположения кванторов, но и вида бескванторных частей формул, записанных в предварённой нормальной форме.
Известны исследования возможности построения разрешающих процедур за пределами узкого исчисления предикатов, в частности, - процедур разрешения некоторых формул исчисления предикатов второй ступени. В этом исчислении используются не только предметные, но и предикатные кванторы ("для любого предиката Р", "существует такой предикат Р"). Однако предикаты могут зависеть только от предметных переменных и не могут быть включены в число предметов, составляющих предметную область.
Изучать философию нужно, когда философия вам не нужна. Когда вы догадываетесь, что стулья в вашей гостиной и Млечный путь связаны между собою, и более тесным образом, чем причины и следствия, чем вы сами с вашими родственниками. И что общее у созвездий со стульями – бесчувственность, бесчеловечность.
Иосиф Бродский. Выступление в Сорбонне
Да, Поэт прав: всякая формализация основ нашей жизни - мышления, призвана утвердить на абстрактном уровне бесчувственность, бесчеловечность. Но это оправдано, если целью наших исследований является не паразитическое применение методов человеческого интеллекта во благо личности, а его развитие.
Казалось бы, после Лекции 1 возвращаться к основам математической логики нет смысла. Но ведь там был приведён только материал, позволивший построить новую теорию - математическую логику событий. Были ли при этом исчерпаны все построения, позволяющие в широком плане моделировать искусственный интеллект? Очевидно, нет. Кроме того, перед вами не монография, а учебное пособие, где в методическом плане разделы должны быть достаточно автономны и содержать допустимое повторение основ, в разных вариантах складывающихся в систему. В то же время, излишнее теоретизирование недопустимо.
Джордж Буль (1815 - 1864) - английский математик и логик. В статье "Математический анализ логики" (1847) им впервые были высказаны идеи применения символического метода к логике. Буль не считал логику разделом математики, но находил глубокую аналогию между символическим методом алгебры и символическим методом представления логических форм и силлогизмов. Он показал, что логические конструкции в такой символике можно решать с помощью аналогов операций алгебры. Таким образом, Д. Буль ввёл базовые операции математической логики и заложил основы булевых функций.
Булевой алгеброй будем называть множество конечноместных (с конечным числом переменных) булевых функций, рассматриваемое вместе с заданными на нём операциями отрицания $$\bar{ } \text{ (}\neg\text{, НЕ)}$$, дизъюнкции $$\vee \text{ (ИЛИ)}$$ и конъюнкции $$\wedge \text{(, И)}$$.
В общем случае булевы функции следует определять рекурсивно. Это следует из того, что аргументы могут быть или рассматриваться как булевы функции.
При композиции или рекомпозиции структура булевых функций выражается с помощью скобок.
Булевы функции и их композиции образуют формулы F. Одной из основных задач булевой алгебры является установление тождественных соотношений вида F1 = F2. Формулы являются тождественными, если при любом наборе значений переменных ИСТИНА (1) или ЛОЖЬ (0), их значения истинности совпадают.
Соблюдается ранжирование операций: первым при прочих равных условиях выполняется отрицание, затем конъюнкции, затем дизъюнкции. При необходимости выполнения действий в ином порядке употребляются скобки.
Для булевой алгебры известен базовый набор тождественных соотношений, определяющий правила эквивалентных преобразований для установления тождественности формул или для обслуживания технологических требований.
(В Лекции 1 утверждается, что любая система распознавания, управления или принятия решений, описанная в терминах булевой алгебры, сводится к построению однослойной логической нейронной сети; это сокращает трудоёмкость обработки, повышает достоверность выводов, и делает даже нецелесообразным изучение структурированных логических нейронных сетей.)
Подчеркнём ещё раз, что тождественность булевых функций устанавливается с помощью таблицы, где по каждому набору значений переменных рассчитываются значения функций. Должно соблюдаться полное соответствие.
Рассматривая буквы латинского алфавита в качестве независимых переменных, повторим здесь базовый набор тождественных соотношений, приведённый в Лекции 1:
Закон коммутативности: $$x\lor y = y\lor x;$$$$ x\land y = y\land x. $$
Закон ассоциативности: $$x\lor (y\lor z) = (x \lor y) \lor z; $$ $$x\land (y\land z) = (x\land y) \land z. $$
Закон дистрибутивности: $$x\land (y \lor z) = (x\land y) \lor (x\land z);$$ $$ x \lor (y\land z) = (x \lor y) \land (x \lor z). $$
Закон де Моргана: $$\overline{x \lor y} = \overline{x} \land \overline{y}$$; $$\overline{x \land y} = \overline{x} \lor \overline{y}$$
Закон идемпотенции: $$x \lor x = x; $$$$ x\land x = x. $$
Закон поглощения: $$x \lor (x\land y) = x; $$$$ x\land (x \lor y) = x. $$
Закон склеивания: $$(x\land y) \lor (\bar{x} \land y) = y; $$$$ (x \lor y)\land (\bar{x} \lor y) = y. $$
Операция переменной с инверсией: $$x \lor \bar{x} = 1; $$$$ x \land \bar{x} = 0. $$
Операция с константами: $$x\land 0 = 0, x\land 1 = x; $$$$ x \lor 0 = x, x \lor 1 = 1. $$
Двойное отрицание: $$\bar{\bar{x}} = x. $$
Применяя эквивалентные преобразования на основе приведённого базового набора, можно аналитически упростить формулу, сделать её короче, нагляднее. Это можно делать, например, раскрывая или вводя скобки, выделяя или формируя конструкции, попадающие под действия перечисленных выше законов и операций.
Например,
$$F(x_1, x_2) = \overline{x_2}\wedge (\overline{x_1}\vee x_1)\vee (x_1\wedge x_2) = \overline{x_2}\vee (x_1\wedge x_2)=(\overline{x_2}\vee x_1)\wedge (\overline{x_2}\vee x_2)=\overline{x_2}\vee x_1$$В данном случае функция F(x1, x2) нам задана. А можно ли сформировать вид этой функции, задав с помощью таблицы её значения для всех возможных наборов значений переменных?
Да, табличный метод задания булевой функции породил полную, стандартизованную и легко реализуемую, предельно "прозрачную" форму - совершенную дизъюнктивную нормальную форму (СДНФ).
Пусть задано табличное представление некоторой булевой функции четырёх переменных (табл. 3.1)
| x1 | x2 | x3 | x4 | F |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Запишем в общем виде, основанном не на строгом доказательстве, а на догадке, СДНФ для четырёх переменных:
$$\begin{eqnarray} F(x_1,x_2,x_3,x_4)=F(\overline{x_1},\overline{x_2},\overline{x_3},\overline{x_4})\wedge (\overline{x_1}\wedge\overline{x_2}\wedge\overline{x_3}\wedge\overline{x_4})\vee \nonumber\\ F(\overline{x_1},\overline{x_2},\overline{x_3},x_4)\wedge (\overline{x_1}\wedge\overline{x_2}\wedge\overline{x_3}\wedge x_4)\vee F(\overline{x_1},\overline{x_2},x_3,\overline{x_4})\wedge (\overline{x_1}\wedge\overline{x_2}\wedge x_3\wedge\overline{x_4})\vee \nonumber\\ F(\overline{x_1},\overline{x_2},x_3,x_4)\wedge (\overline{x_1}\wedge\overline{x_2}\wedge x_3\wedge x_4)\vee F(\overline{x_1},x_2,\overline{x_3},\overline{x_4})\wedge (\overline{x_1}\wedge x_2\wedge\overline{x_3}\wedge\overline{x_4}) \vee \nonumber\\ F(\overline{x_1},x_2,\overline{x_3},x_4)\wedge (\overline{x_1}\wedge x_2\wedge\overline{x_3}\wedge x_4)\vee F(\overline{x_1},x_2,x_3,\overline{x_4})\wedge (\overline{x_1}\wedge x_2\wedge x_3\wedge\overline{x_4})\vee \nonumber\\ F(\overline{x_1},x_2,x_3,x_4)\wedge (\overline{x_1}\wedge x_2\wedge x_3\wedge x_4)\vee F(x_1,\overline{x_2},\overline{x_3},\overline{x_4})\wedge (x_1\wedge\overline{x_2}\wedge\overline{x_3}\wedge\overline{x_4})\vee \nonumber\\ F(x_1,\overline{x_2},\overline{x_3},x_4)\wedge (x_1\wedge\overline{x_2}\wedge\overline{x_3}\wedge x_4)\vee F(x_1,\overline{x_2},x_3,\overline{x_4})\wedge (x_1\wedge\overline{x_2}\wedge x_3\wedge\overline{x_4})\vee \nonumber\\ F(x_1,\overline{x_2},x_3,x_4)\wedge (x_1\wedge\overline{x_2}\wedge x_3\wedge x_4)\vee F(x_1,x_2,\overline{x_3},\overline{x_4})\wedge (x_1\wedge x_2\wedge \overline{x_3}\wedge\overline{x_4})\vee \nonumber\\ F(x_1,x_2,\overline{x_3}, x_4)\wedge (x_1\wedge x_2\wedge \overline{x_3}\wedge x_4)\vee F(x_1,x_2,x_3, \overline{x_4}) \wedge (x_1 \wedge x_2 \wedge x_3 \wedge \overline{x_4})\vee \nonumber\\ F(x_1 ,x_2 ,x_3 ,x_4) \wedge (x_1 \wedge x_2 \wedge x_3 \wedge x_4) \end{eqnarray} $$После подстановки заданных значений функции F получим:
Не будем искать дальнейших упрощений, так как полученный вид функции достаточно регулярен и, несмотря на кажущуюся избыточность, достаточно легко реализуется схемотехнически самой короткой логической цепочкой. Необходимо на первом уровне выполнить инверсию (отрицание), на втором уровне - выполнить конъюнкции, а на третьем - дизъюнкцию. Это особенно важно при построении быстродействующих устройств суперкомпьютера и, как оказалось (см. Лекцию 1), - при построении однослойных логических нейронных сетей.
Как видим формула (3.20) получилась весьма длинной, и это всего лишь для четырёх булевых переменных! Можно ли записать короче для любого количества n переменных?
Пусть задан вектор X = {x0, x1, ..., xn-1}, где xj, j = 0, ..., n-1, - булевы переменные. Введём понятие индексной маски вектора ИМВ. Она представляет собой двоичный код длины n, принимающий 2n значений индекса i от равенства нулю до равенства единице всех разрядов. Пусть при данном применении единичные разряды ИМВ, образующие двоичное значение индекса i, указывают на те булевы переменные, которые используются в выражении (3.20) без знака отрицания. Такую i-ю выборку вектора Х обозначим ХИМВ=i. Функцию F от неё обозначим F(ХИМВ=i), а соответствующую ей конъюнкцию булевых переменных, с учётом того, что часть их фигурирует со знаком отрицания, обозначим
Тогда всю формулу СДНФ можно записать:
(3.21)
В рассмотренном выше примере для n = 4 не зря каждая следующая комбинация выбиралась по строкам таблицы условным сложением с единицей некоторой подразумеваемой маски. Эти комбинации образовали счётное множество с индексом i, пробегающим от нуля до единиц по всем четырём разрядам. Частный вид подтверждает общую формулу (3.21):
(3.22)
В данном случае надо помнить о специальном назначении маски, метящей булевы переменные, используемые без знака отрицания.
Маски векторов используются программистами весьма часто: для альтернативного выполнения векторных операций, для маскирования прерывания, для маскирования направлений обмена и пр.
Из СДНФ легко выводится СКНФ - совершенная конъюнктивная нормальная форма, представляющая собой "конъюнкцию дизъюнкций". Поскольку она практически не применяется, мы её рассматривать не будем.
Отметим, что табличная запись булевых функций не только достаточна, но практически всегда используется разработчиками цифровых электронных устройств. Более того, сложилась практика использования ассоциативной памяти (АП) для построения многих устройств компьютера, таких как: дешифратор, КЭШ в сверхоперативной памяти, механизм перевода математических адресов в физические, устройство хранения и выборки глобальных данных, арбитры коммутаторов и др.
Табличная запись значений одной или более булевых функций производится в строках - регистрах АП, разбитых на две части: в левой части указан набор значений переменных, а в правой - вектор значений булевых функций. В результате одновременного сравнения кода возникшей ситуации со всеми наборами переменных, мгновенно производится выбор вектора значений выходов устройства. То есть, устройство со многими входами и многими выходами записывается и работает с помощью модуля ассоциативной памяти, реализующего систему булевых функций.
Так решаются задачи обеспечения высокого быстродействия, стандартизации и унификации.
Требования стандартизации и унификации элементной базы и функциональных устройств электронной техники, в том числе нейросетевых технологий, выдвигает научную задачу синтеза сложных булевых функций на основе более простых базовых, стандартных. В этом случае функция с меньшим количеством булевых переменных "погружается" в более сложную булеву функцию, где добавляются новые переменные.
Существует теорема разложения, которую проиллюстрируем конкретным, легко обобщаемым примером:
$$F(x_1,x_2,x_3,x_4,x_5) = (\bar{x_1} \land \bar{x}_2 \land F(0,0,x_3,x_4,x_5)) \lor (\bar{x}_1 \land x_2 \land F(0,1,x_3,x_4,x_5)) \lor (x_1 \land \bar{x}_2 \land F(1,0,x_3,x_4,x_5)) \lor (x_1 \land x_2 \land F(1,1,x_3,x_4,x_5)) $$Предметом дальнейших исследований примем любое законченное утверждение на любом формальном или неформальном языке - высказывание, для которого имеет смысл говорить о его истинности или ложности. Это было уже объявлено в Лекции 1.
Основной задачей, которую ставит перед собой математическая логика, является формализация мыслительных процессов в широком смысле - в смысле доказательства или поиска истины, а также расширения знаний. Для этого надо сформулировать "правильное", непротиворечивое логическое исчисление, включающее:
Тождественно истинными являются высказывания, которые не требуют задания каких-либо дополнительных условий для проверки своей истинности на протяжении всего процесса логического вывода.
Например, высказывание "кислород является газом" имеет значение ИСТИНА (1) в тех условиях, в которых оно рассматривается. Ведь кислород может находиться не только в газообразном состоянии.
Высказывание "дважды два - одиннадцать" на первый взгляд представляется заведомо ложным. Однако если предположить, что вместо десятичной системы счисления используется троичная система, при условии сохранения привычных названий многозначных чисел, то данное высказывание становится истинным.
Поэтому обязательным условием правильности выводов и следствий является то, чтобы постоянное высказывание, подобно константе, не меняло значение истинности в процессе логического вывода.
В исчислении высказываний не интересуются внутренней смысловой структурой элементарных высказываний. Естественно поэтому для их обозначения использовать отдельные буквы некоторого алфавита (обычно латинского и готического). Отдельными буквами могут обозначаться и так называемые переменные высказывания, что означает, что вместо этой буквы всегда может быть подставлено любое конкретное постоянное высказывание, как истинное, так и ложное.
Высказывания, как постоянные, так и переменные, можно объединять в сложные высказывания, используя связки "и", "или", "если - то", "не" и т.п. Если в состав сложного высказывания входят переменные высказывания, представленные буквами, то при замене этих букв одними высказываниями сложное высказывание может оказаться истинным, а при замене другими - ложными. Например, сложное высказывание "А и В", где А и В - переменные высказывания, будет, очевидно, истинным в том и только том случае, если оба высказывания будут истинными.
Существуют и такие сложные высказывания, содержащие в своём составе переменные высказывания, которые остаются истинными при любых значениях переменных высказываний. Например, сложное высказывание "если неверно то, что высказывание А ложно, то высказывание А истинно" остаётся истинным, какое бы высказывание ни подставили на место переменного высказывания А. Такие высказывания называют тождественно истинными.
Например, возьмём высказывание "извозчик Петров - водитель кобылы". Если неверно то, что Петров не водитель кобылы, значит он водитель кобылы. Сложное высказывание истинно. Если же неверно, что Петров водитель кобылы, значит он не водитель кобылы. Сложное высказывание снова истинно, ибо соответствует правде и не содержит противоречий.
Задача выделения тождественно истинных высказываний во множестве всех возможных высказываний является важнейшей задачей любого логического исчисления.
После всех предварительных замечаний перейдём к построению собственно исчисления высказываний, или, как его ещё иногда называют, пропозиционного исчисления.
Введём базовые операции.
А и В истинны. В обычной речи этой операции соответствует связка "и".А или В. Однако, хотя мы уже применили связку "или", под ней понимается не разделительное "или", понимаемое в смысле "либо - либо", когда А и В не могут быть оба истинны. В данном определении высказывание $$А \lor В$$ истинно и при истинности обоих высказываний А и В.А истинно, а В ложно. А называется посылкой, а В - следствием. В обычной речи операция $$\to$$ (импликация) соответствует связке "если - то": "если А, то В". В определении математической логики это высказывание при ложном А всегда истинно, независимо от того, истинно или ложно высказывание В. Этот факт можно кратко сформулировать так: "из ложного следует всё что угодно". В обычной речи иногда подразумевается, что когда А ложно, то высказывание "если А, то В" не имеет смысла. (Порой кажется, что принятый формализм прямо-таки противоречит здравому смыслу. Например, высказывание "из того, что у льва есть когти, следует, что снег белый" формально истинно. Но так ли это в действительности, решать не математикам-логикам.)А истинно, и истинное, если А ложно.А и В оба истинны или оба ложны. Это высказывание называется эквивалентностью.Как и в булевой алгебре, значение ИСТИНА будем обозначать единицей, значение ЛОЖЬ - нулём.
В табл. 3.2 сведены соотношения истинности для базовых операций.
| А | В | $$А \land В$$ | $$А \lor В$$ | $$А \to В$$ | $$\neg А$$ | $$А \sim В$$ |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 |
Как и в булевой алгебре введём ранжирование операций: $$\neg, \land, \lor, \to, \sim$$.
Например, формула $$\neg А \lor В \land С \to В \lor С$$ понимается как $$((\neg А) \lor (В \land С) \to (В \lor С)$$. Формула $$А \sim В \to С$$ должна пониматься как $$(А) \sim ((В) \to (С))$$ и т.д.
Введённые определения решают лишь две части задачи построения исчисления высказываний: проблему формализации записи сложных высказываний.
Завершающая часть задачи - нахождение способа определения тождественной истинности высказываний - может быть решена двумя путями: содержательным и формальным.
При содержательном подходе необходимо помнить о содержательном смысле букв и связок. В то же время, нет необходимости помнить само высказывание, достаточно помнить функцию истинности этого высказывания: А = ИСТИНА, если высказывание, обозначенное этой буквой, истинно, и А = ЛОЖЬ, если высказывание ложно. Функция истинности отождествляется с самой буквой, которая теперь обозначает булеву переменную.
Тогда каждую формулу $$\Omega$$ исчисления высказываний можно интерпретировать как формулу в булевой алгебре с включённой в неё дополнительно операцией импликации $$\to$$. Входящие в формулу $$\Omega$$ постоянные высказывания должны быть заменены соответствующими булевыми константами (значениями их функций истинности). Символы, соответствующие переменным высказываниям, рассматриваются как аргументы булевой функции, представляемой формулой $$\Omega$$. Эта функция называется функцией истинности сложного высказывания, выражаемого формулой $$\Omega$$.
На содержательном уровне построения исчисления высказываний тождественно истинными считаются те, и только те формулы этого исчисления (сложные высказывания), функции истинности которых принимают значения ИСТИНА (1) при всех значениях переменных.
Представленный содержательный аспект исчисления высказываний позволяет сравнительно просто решить вопрос о тождественной истинности любого сложного высказывания: достаточно перебрать все возможные наборы значений истинности составляющих его переменных высказываний и проверить, на всех ли этих наборах функция истинности рассматриваемого сложного высказывания принимает значение ИСТИНА.
Например, рассмотрим формулу $$\Omega = А \land В \to А$$ и составим для неё таблицу истинности с учётом "промежуточного" результата $$А \land В$$:
| А | В | $$А \land В$$ | $$А \land В\to А$$ |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Видим, что при всех значениях переменных высказываний, сложное высказывание является истинным. Следовательно, рассмотренная формула $$\Omega$$ тождественно истинная.
Несмотря на простоту и "прозрачность", содержательный аспект исчисления высказываний имеет ряд недостатков:
При формальном подходе к установлению тождественной истинности пользуются эквивалентными преобразованиями булевой алгебры. Поскольку там нет импликации, исключим её согласно равенству:
$$(С \to D) = (\neg C \lor D).$$Проверим его справедливость с помощью таблицы истинности:
| С | D | $$C\to D$$ | $$\neg C \lor D$$ |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Рассмотрим тот же пример:
$$А \land В\to А = \neg (А \land В) \lor А = \neg А \lor \neg В \lor А = (\neg А \lor А) \lor \neg В = 1 \lor \neg В = 1.$$Эта цепочка доказывает тождественную истинность заданной формулы.
Таким образом, формальный аспект исчисления высказываний характеризуется тем, что полностью отвлекаются от содержательного смысла формул и рассматривают их как конечные последовательности символов, подлежащие эквивалентным преобразованиям.
Для этих преобразований, подобно и в дополнение базовому набору соотношений булевой алгебры, известна наиболее употребительная система аксиом С.К. Клини:
Первые десять аксиом представляют собой десять формул исчисления высказываний, объявленных тождественно истинными по определению. Они предполагают возможность подстановки вместо букв А, В, С любых формул исчисления высказываний (не обязательно истинных). Такая подстановка, по определению, не нарушает тождественной истинности аксиомы.
Одиннадцатая аксиома - это так называемое правило вывода, позволяющее, по определению, считать доказанной истинность формулы $$\Psi$$, если истинность формул $$\Omega$$ и $$\Omega \to \Psi$$ уже была установлена ранее. Если формулы $$\Omega$$ и $$\Omega \to \Psi$$ были при этом тождественно истинными. То тождественно истинной будет и формула $$\Psi$$. Предполагается по определению, что все тождественно истинные формулы (и только такие формулы) исчисления высказываний могут быть получены из аксиом в результате подстановок 1 - 10 и применения (возможно, многократного) правил вывода 11.
Формула $$\Psi$$ называется непосредственным следствием формул $$\Omega$$ и $$\Omega \to \Psi$$.
Формулы, тождественно истинные в содержательном смысле, для краткости будем называть просто содержательно истинными, противопоставляя их формально истинным, т.е. формально доказуемым.
Говорят, что формула $$\Theta$$ исчисления высказывания выводится из условно истинных формул (истинность которых предполагается на протяжении рассматриваемого вывода) $$\Omega1, \Omega_2, ..., \Omega_n$$, если она может быть получена из этих формул и аксиом 1 - 10 исчисления высказываний в результате применения конечного числа раз правил непосредственного следствия.
Более точно это означает последовательное использование трёх условий, лежащих в основе правил вывода:
Цепочка формул, получающихся в результате последовательного применения этих трёх правил, которая кончается формулой $$\Theta$$, называется формальным выводом этой формулы.
Для обозначения выводимости употребляется специальный символ \vdash (читается как "даёт"), слева от которого пишутся условно истинные формулы, а справа их следствия: $$\Omega_1, \Omega_2, ..., \Omega_n \to \Theta$$. Аксиомы здесь как бы включаются в символ $$\vdash$$. Тогда для любой формально истинной формулы $$\Theta$$, выводимой только лишь на основе аксиом 1 - 10, можно писать $$\vdash \Theta$$.
Приведём простейшие примеры формального вывода, нумеруя последовательные шаги.
Приведённая цепочка формул по определению является формальным доказательством формулы $$А \to А$$. Таким образом, эта формула принадлежит к числу формально истинных формул, и её можно записать
$$\vdash А \to А.$$Другим примером является получение следствий из трёх условно истинных формул $$А, В, А \to (В \to С)$$. За пять шагов из этих формул может быть получена формула С.
А (первая данная нам условно истинная формула).В (вторая данная нам формула).С (непосредственное следствие формул 2 и 4).Таким образом, формула С выводима из формул $$А, В, А \to (В \to С)$$ и мы можем записать $$А, В, А \to (В \to С) \vdash С$$.
Хотя условно истинные формулы и не обладают тождественной истинностью, легко видеть, что в окончательной записи (условной) выводимости любая буква может быть заменена произвольной формулой, если только такая замена производится как слева, так и справа от знака $$\vdash$$.
Подобным же способом можно доказать соотношения:
Обозначим $$\Gamma$$ произвольную конечную совокупность формул исчисления высказываний. Применяя более сложную технику доказательства (индукцию по длине вывода), можно доказать следующую теорему о дедукции.
Теорема 3.1. Если в исчислении высказываний формула В выводима из совокупности формул $$\Gamma$$ и А, то из $$\Gamma$$ выводима формула $$А \to В$$.
В теории доказательств часто применяются две общие схемы.
Легко проверить, что все аксиомы исчисления высказываний 1 - 10 представляют собой содержательно истинные формулы. Иначе говоря, соответствующие им функции истинности принимают при всех значениях переменных значение ИСТИНА. Это свойство, очевидно, сохраняется при подстановках любых формул исчисления высказываний вместо букв, входящих в аксиомы.
Из таблицы истинности для импликации $$\to$$ непосредственно следует, что из содержательной истинности формул $$\Omega$$ и $$\Omega \to \Psi$$ вытекает содержательная истинность формулы $$\Psi$$. Но тогда очевидно, что все доказуемые (формально истинные) формулы будут и содержательно истинными. Верно (хотя и гораздо сложнее доказуемо) также и обратное, что формулируется следующей теоремой.
Теорема 3.2. При формальном построении исчисления высказываний с помощью системы аксиом 1 - 11 формально доказуемыми (формально истинными) будут все те, и только те формулы этого исчисления, которые являются тождественно истинными в содержательном смысле.
Теорема 2 содержит в себе два утверждения относительно выбранной системы аксиом: эта система содержательно непротиворечива и эта система содержательно полна, т.е. нет ни одной содержательно истинной формулы исчисления высказываний, которую нельзя было бы доказать формально с помощью этой системы аксиом.
При этом, естественно называть систему аксиом формально непротиворечивой, если с её помощью нельзя вывести какую-нибудь формулу $$\Omega$$ вместе с её отрицанием $$\neg \Omega$$; в противном случае она формально противоречива.
Отметим, что хотя присоединение недоказуемых формул в качестве новых аксиом исчисления высказываний, нарушает свойство формальной непротиворечивости, ничто не мешает нам присоединить к системе аксиом формулы $$\Omega_1, ..., \Omega_n$$ в качестве не тождественно, а лишь условно истинных формул. (Это характерно, например, при переходе в мир грёз или сказок.) Противоречие возникает тогда и только тогда, когда конъюнкция $$\Omega_1 \land \Omega_2 \land ... \land \Omega_n $$ является тождественно ложной формулой.
Особенностью исчисления предикатов является наличие предметных переменных, пробегающих конечную или бесконечную область значений, называемую предметной областью. Отдельные значения этой области называются предметами или объектами.
Предикатом называют функцию предметных переменных P(x1, x2, ..., xn), представляющую собой переменное высказывание, истинность или ложность которого определяется наборами значений переменных x1, x2, ..., xn.
Если предикат Р не является тождественно истинным или тождественно ложным, то на одних наборах значений предметных переменных он принимает значение ИСТИНА (1), а на других - значение ЛОЖЬ (0).
Какова цель построения исчисления предикатов?
При построении теоретических основ логических нейронных сетей - математической логики событий - мы исходили из высказываний, вкладывая в них конкретный смысл на основе факторного пространства событий. Это пространство и отражало предметную область. Значит, до перехода к нечётким данным, мы пользовались расширением исчисления высказываний в сферу исчисления предикатов!
Действительно, ведь необходимо придать формальному языку логического вывода "человеческий", объектовый и событийный смысл. Чтобы видеть и подразумевать предметы и объекты, свойства и обстоятельства, о которых что-то говорится. Чтобы не были истинными такого рода высказывания, как "из-за того, что у льва когти, снег белый". Чтобы лев и снег действенно участвовали в поиске истины.
Введение понятия предметной области сразу же влечёт применение теоретико-множественного аппарата, подобно тому, что привлекался в силлогистике.
Мы подробно не останавливались и не будем останавливаться на анализе преемственности учения о силлогистике и о современной математической логике, но готовы высказаться в защиту тезиса о том, что "всё новое - хорошо забытое старое". Именно поэтому мы ввели в курс об искусственном интеллекте силлогистику Аристотеля.
Например, высказывание "четыре больше двух" в исчислении высказываний является неразложимым. Если же ввести предикат P(x, y) на множестве целых неотрицательных чисел в качестве предметной области, который является истинным тогда и только тогда, когда $$x > y$$, то приведённое высказывание запишется в форме Р(4, 2), которая даёт ясное представление о внутренней структуре высказывания.
Наличие предметных переменных позволяет ввести квантор общности \forall x и квантор существования $$\exists x$$.
Выражение $$\forall xP(x)$$ - условное обозначение высказывания "для всех х предикат Р(x) является истинным"; выражение $$\exists xP(x)$$ - условное обозначение высказывания "существует x, для которого предикат Р является истинным".
В теории доказательств эти кванторы связаны между собой:
$$\neg \forall xP(x) = \exists x\neg P(x)$$Например, высказывание "все солдаты карантинной роты стригутся наголо" в случае отрицания звучит: "не все солдаты карантинной роты стригутся наголо". Это, в свою очередь, может быть сформулировано: "существует солдат карантинной роты, постриженный не наголо".
Пусть Р(x) - функция "x стрижётся наголо". Тогда вышесказанная трансформация может быть изображена цепочкой:
Если предметная область состоит из конечного числа объектов x1, x2, ..., xk, подобных солдатам, то выражение $$\forall xP(x)$$ сводится к конъюнкции $$P(x_1 ) \land Р(x_2 ) \land ... \land Р(x_k )$$, а выражение $$\exists xР(x)$$ - к дизъюнкции $$P(x_1 ) \lor Р(x_2 ) \lor ... \lor Р(x_k )$$. В случае бесконечной предметной области подобное сведение оказывается невозможным, неконструктивной.
Возьмём более сложный пример. Вспомним определение непрерывности функции f(x) в точке x0: "Функция f(x) непрерывна в точке x0, если для любого $$\epsilon > 0$$ существует $$\delta > 0$$, что если $$|x - x_0 | < \delta $$, то $$| f(x) - f(x_0 )| < \epsilon $$". Сокращённо можно записать:
В случае нарушения непрерывности функции мы говорим: "не для всякого $$\epsilon > 0$$ существует $$\delta > 0$$, что если $$| x - x_0 | < \delta $$, то $$| f(x) - f(x_0 )| < \epsilon $$". Или: "существует $$\epsilon > 0$$, что для любого $$\delta > 0 \neg (| x - x_0 | < \delta \to | f(x) - f(x_0 )| < \epsilon )$$". Последний предикат можно записать формально:
$$ \exists \epsilon > 0\forall \delta > 0 \neg P(x, x_0 , f(x), f(x_0 ), \epsilon , \delta ), \text{ где } P(x, x_0 , f(x), f(x_0 ), \epsilon , \delta ) = (| x - x_0 | < \delta \to | f(x) - f(x_0 )| < \epsilon ). $$В выражениях $$\forall xP(x)$$ и $$\exists xР(x)$$ переменная x оказывается связанной соответствующим квантором, в отличие от свободных переменных. В формулах (3.47) и (3.48) переменные $$\epsilon $$ и $$\delta $$ связанные, а переменные x, x0, f(x), f(x0) - свободные.
Обычно используют узкое исчисление предикатов, которое разрешает связывать с помощью кванторов лишь предметные переменные. Входящие в формулу предикаты предполагаются при этом неизменными. В так называемом расширенном исчислении предикатов употребляются переменные предикаты и предикатные кванторы.
Как и в случае исчисления высказываний, при построении исчисления предикатов недостаточно указать лишь способ записи формул. Необходимо задать правила преобразования формул, выражаемые аксиомами.
В число аксиом исчисления предикатов включаются все 11 аксиом исчисления высказываний, (3.25) - (3.35).
Кроме них, вводятся четыре специфических постулата, которым присвоим номера от 12 до 15:
12. $$\frac{C \to P(x)}{C \to \forall xP(x)}$$
13. $$\forall xP(x) \to P(t)$$
14. $$P(t) \to \exists xP(x)$$
15. $$\frac{P(x) \to C}{\exists xP(x) \to C}$$
С помощью указанных аксиом - постулатов можно производить формальный вывод новых эквивалентных формул совершенно таким же способом, как и в исчислении высказываний.
Заметим, что выражения P(x) и P(t) в аксиомах 12 - 15 должны пониматься не только как элементарные одноместные предикаты, но и как произвольные формулы исчисления предикатов, содержащие буквы x и t в качестве свободных переменных.
При всех подстановках подразумевается, что свободные и связанные переменные в формулах, получаемых в результате подстановок, должны обозначаться различными буквами, как в (3.50) и (3.51). Такое условие позволяет избежать так называемой коллизии переменных, вызывающей непредвиденное связывание переменных, которые должны были бы остаться свободными.
При условии принятия мер во избежание коллизии переменных, в исчисление предикатов переносятся все результаты выводимости одних формул из других. Остаётся справедливой и теорема дедукции.
В частности, если формула $$\Psi$$ выводима в исчислении высказываний из формулы $$\Omega$$, то формула $$\Omega \to \Psi$$, при условии принятия мер против коллизии переменных, будет выводимой и в исчислении предикатов.
Из аксиом 12 - 15 легко образуются следующие правила выводимости:
Введение квантора общности ($$\forall $$-введение)
$$A(x) \vdash x \forall xA(x).$$(Значок переменной x, который пишется над символом выводимости $$\vdash$$, означает, что соответствующая переменная варьируется, превращаясь из свободной в связанную. Тогда свободные переменные, не варьирующиеся в процессе вывода, принято называть фиксированными.)
Введение квантора существования ($$\exists $$-введение)
$$A(t) \vdash \exists xA(x).$$Удаление квантора общности ($$\forall $$-удаление)
$$\forall xA(x) \vdash A(t). $$Удаление квантора существования по С.К. Клини:
$$\text{Если} \Gamma , A(x) \vdash C, \text{то} \Gamma , \exists xA(x) \vdash x C.$$(Напоминаем, что $$\Gamma$$ - произвольная конечная совокупность формул.)
Если имеет место выводимость $$\Gamma , А \vdash В$$, причём, в процессе вывода свободные переменные, входящие в формулу А, остаются фиксированными, то имеет место сводимость $$\Gamma \vdash А \to В$$.
Используя символ эквивалентности $$\sim$$ в том же смысле, что и в исчислении высказываний, и обозначая буквой А любую формулу, не содержащую свободной переменной х, можно легко вывести следующие соотношения:
Правила (3.58) и (3.59) показывают возможность изменения порядка применения одноимённых кванторов. Для разноимённых кванторов смена их порядка в соотношении (3.61) не имеет места. Теоретико-множественный анализ соотношения $$\vdash \forall x \exists yP(x, y) \to \exists y\forall xP(x, y)$$, двойственного (3.61), обнаруживает примеры его абсурдности. ("Отрицательный вывод не доказывается, а показывается" - важное правило теории доказательства; см. пример о непрерывности функции.)
Содержательная непротиворечивость исчисления предикатов, как и исчисления высказываний, понимается в том смысле, что выводимыми в этом исчислении могут быть лишь тождественно истинные формулы, т.е. такие формулы, которые остаются истинными для любой предметной области и для любой конкретной интерпретации входящих в них предикатов. Здесь кроется некоторая неконструктивность подхода, связанная с неявно предполагающейся возможностью перебора всех значений предметных переменных при определении тождественной истинности. В случае бесконечной предметной области это требует бесконечного числа шагов. Поэтому широко привлекается теоретико-множественный подход, основанный на смысловом анализе как предметной области, так и заданных на ней предикатов.
Подобным путём устанавливается и формальная непротиворечивость исчисления предикатов, как невозможность вывести в этом исчислении некоторую формулу вместе с её отрицанием.
В случае конечных предметных областей вопрос о содержательной полноте исчисления предикатов сводится к соответствующему вопросу для исчисления высказываний и потому решается конструктивно.
Возможность формального вывода в этом исчислении любой тождественно истинной формулы была решена К. Гёделем. Однако в случае бесконечных предметных областей установление содержательной полноты исчисления предикатов требует привлечения средств, выходящих за пределы конечной (финитной) математики.
В противоположность содержательной полноте, называемой также полнотой в широком смысле, полнота в узком смысле уже не имеет места в исчислении предикатов.
Действительно, к числу аксиом исчисления предикатов присоединим формулу $$\exists xР(x) \to \forall xР(x)$$, не выводимую в этом исчислении, но не приводящую к противоречию, если предметная область состоит из единственного объекта. Если предметная область состоит из двух объектов х и у, указанная аксиома превращается в формулу $$Р(x) \lor Р(у) \to Р(x) \land Р(у)$$, не являющуюся тождественно истинной и потому не выводимую из остальных аксиом.
Наряду с тождественно истинными формулами, в исчислении предикатов рассматривают так называемые выполнимые формулы.
Выполнимой будем называть такую формулу, которая может быть истинной при выборе подходящей предметной области и при должном определении заданных на ней предикатов.
При такой постановке обратной, в каком-то смысле, задачи первична формула, а вторичны условия, при которых она выполняется, становясь тождественно истинной, а не наоборот. Предполагается, что формула имеет общий вид и не содержит символов индивидуальных предметов и индивидуальных предикатов.
Каждая тождественно истинная формула является и выполнимой. Обратное в общем случае неверно. Примером выполнимой, но не тождественно истинной формулы может служить формула, рассмотренная выше, $$\exists xР(x) \to \forall xР(x)$$. Эта формула является тождественно истинной лишь на таких предметных областях, которые состоят из одного-единственного объекта.
Проблема разрешимости для исчисления предикатов состоит в том, чтобы указать единый эффективный алгоритм для определения выполнимости или невыполнимости любой заданной формулы исчисления предикатов на какой-либо предметной области.
В отличие от исчисления высказываний, проблема разрешимости в общем случае для исчисления предикатов, как показали Чёрч и Тьюринг, вообще не имеет решения. Иными словами, не существует единого конструктивного приёма для установления выполнимости или невыполнимости любой формулы исчисления предикатов.
Часто проблема разрешимости для исчисления предикатов формулируется несколько в иной форме: найти алгоритм для определения тождественной истинности любой данной формулы в этом исчислении.
Таким образом, в отношении проблемы разрешимости, исчисление предикатов коренным образом отличается от исчисления высказываний.
Если ограничиться частными видами формул, то разрешающий алгоритм может быть построен и в случае исчисления предикатов.
Такой алгоритм можно, например, построить для формул исчисления предикатов, содержащих лишь одноместные предикаты. Для установления выполнимости или невыполнимости формулы, содержащей n одноместных предикатов, достаточно ограничиться рассмотрением предметных областей, состоящих не более чем из 2n объектов. В результате проверка выполнимости (или тождественной истинности) предикатной формулы (после замены кванторов конъюнкциями или дизъюнкциями) сводится к проверке выполнимости (или, соответственно, тождественной истинности) полученной формулы исчисления высказываний.
В общем случае при решении вопроса о выполнимости или невыполнимости конкретной формулы существенную помощь может оказать предварительное приведение этой формулы к так называемой нормальной форме.
Различают два вида нормальных форм: предварённую форму и нормальную форму Сколема.
Предварённая форма отличается тем, что все кванторы, если они имеются, должны быть вынесены в самое начало формулы, а область действия каждого из них должна распространяться до конца этой формулы.
В нормальной форме Сколема требуется дополнительно, чтобы все кванторы существования предшествовали всем кванторам общности.
Если формула записана в предварённом виде, то её часть, стоящая после кванторов (бескванторная часть формулы), может рассматриваться как формула исчисления высказываний. Каждый предикат рассматривается при этом просто как переменное высказывание. Тогда в этой формуле можно исключить все знаки импликации, заменяя конструкции вида $$А \to В$$ через $$\neg А \lor В$$, а затем привести её к дизъюнктивной нормальной форме. Такое преобразование приводит исходную предикатную формулу к эквивалентной ей предикатной формуле.
Справедлива теорема:
Теорема 3.3. Для всякой формулы $$\Omega$$ (узкого) исчисления предикатов существует эквивалентная ей формула $$\Psi$$, записанная в предварённой форме. Существует единый алгоритм приведения произвольной предикатной формулы к предварённой форме.
Справедливость сформулированной теоремы вытекает из легко проверяемых соотношений:
$$\vdash \neg \forall xР(x) \sim \exists x\neg Р(x); $$ $$\vdash \neg \exists xР(x) \sim \forall x\neg Р(x);$$ $$\vdash Q \land \forall xP(x) \sim \forall x(Q \land P(x));$$ $$\vdash Q \land \exists xP(x) \sim \exists x(Q \land P(x));$$ $$\vdash Q \lor \forall xP(x) \sim \forall x(Q \lor P(x));$$ $$\vdash Q \lor \exists xP(x) \sim \exists x(Q \lor P(x));$$Поскольку импликация может быть заменена операциями дизъюнкции и отрицания, то с помощью выписанных формул при соблюдении условий, исключающих возможность возникновения коллизии переменных, можно производить последовательную перестановку кванторов со всеми составляющими формулу символами, отличными от кванторов, пока все кванторы не окажутся в левой части формулы.
Приведём пример подобного преобразования:
$$P(x) \lor \neg \forall yQ(x, y) \sim P(x) \lor \exists y\neg Q(x, y) \sim \exists y(P(x) \lor \neg Q(x, y)).$$Последняя формула соответствует требуемой предварённой форме исходной формулы.
Для нормальной формы Сколема прямого аналога теоремы 3.3 не существует: не для всякой формулы исчисления предикатов существует эквивалентная формула, имеющая нормальную форму Сколема.
Однако понятие эквивалентности может быть так обобщено, что любую формулу исчисления предикатов можно будет привести к нормальной форме Сколема.
Введём понятие дедуктивной эквивалентности.
Формула $$\Omega$$ называется дедуктивно эквивалентной формуле $$\Psi$$, если, присоединив формулу $$\Omega$$ к системе аксиом исчисления предикатов, получим возможность вывести формулу $$\Psi$$ из расширенной системы аксиом и наоборот, присоединив к системе аксиом формулу $$\Psi$$, получим возможность вывести формулу $$\Omega$$.
Это определение применимо не только к исчислению предикатов, но и к любому логическому исчислению, в том числе к исчислению высказываний.
Легко видеть по рассмотренному выше примеру, что обычная эквивалентность формул влечёт их дедуктивную эквивалентность.
Справедлива следующая теорема Сколема:
Теорема 3.4. Для всякой формулы узкого исчисления предикатов существует дедуктивно эквивалентная ей формула, записанная в нормальной форме Сколема. Существует алгоритм приведения любой формулы к дедуктивно эквивалентной ей сколемской форме.
Очевидно, что если две формулы дедуктивно эквивалентны, то из тождественной истинности одной следует тождественная истинность другой. То есть, приведя формулу к нормальной форме Сколема, следует решать проблему тождественной истинности относительно этой формы.
Это же обстоятельство может быть использовано при доказательстве содержательной полноты исчисления предикатов, поскольку для такого доказательства достаточно установить выводимость всех тождественно истинных формул, записанных в нормальной форме Сколема. Действительно, установив выводимость всех указанных формул, мы тем самым установим и выводимость всех дедуктивно эквивалентных им формул, т.е. всех тождественно истинных формул исчисления предикатов.
Известно большое количество классов формул, для которых проблема разрешимости решается положительно. Ограничения, с помощью которых выделяются указанные классы, касаются не только характера, числа и порядка расположения кванторов, но и вида бескванторных частей формул, записанных в предварённой нормальной форме.
Известны исследования возможности построения разрешающих процедур за пределами узкого исчисления предикатов, в частности, - процедур разрешения некоторых формул исчисления предикатов второй ступени. В этом исчислении используются не только предметные, но и предикатные кванторы ("для любого предиката Р", "существует такой предикат Р"). Однако предикаты могут зависеть только от предметных переменных и не могут быть включены в число предметов, составляющих предметную область.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.