Математическая логика и теория алгоритмов

Федеральное агентство по образованию ГОУ ВПО “Воронежская государственная технологическая академия” Кафедра информационных технологий, моделирования и управления Ю.В. БУГАЕВ, И.Ю. ШУРУПОВА КУРС ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ ” МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ” Воронеж 2011 Высказывания и операции над ними. Формулы Высказыванием называется всякое утверждение, о котором можно вполне определенно и объективно сказать истинно оно или ложно. Например, утверждение "2 > 0" является высказыванием и оно истинно, а утверждение "2 < 0" - ложно, утверждение "x2+y2=z2" высказыванием не является, так как оно может быть, как истинным, так и ложным при различных значениях переменных x, y, z. Высказывание полностью определяется своим истинностным значением, условимся значение истинности высказывания обозначать буквой "И", если высказывание истинно, и буквой "Л", если высказывание ложно. Различают высказывания простые и сложные, высказывание называется простым, если никакая его часть не является высказыванием. Простые высказывания будем обозначать начальными заглавными буквами латинского алфавита A, B, C или A1, A2, . . .. Сложные высказывания характеризуются тем, что образованы из нескольких простых высказываний с помощью логических операций, т.е. являются формулами алгебры высказываний. Обозначим B = {И, Л}. Определим операции на множестве B. Отрицанием высказывания A называется высказывание, которое принимает значение истина, если A ложно, и наоборот. Отрицание обозначается (А) и является унарной операцией. Пусть А и В - некоторые элементарные высказывания, введем бинарные операции над ними. Конъюнкцией высказываний A и B называется высказывание, которое принимает значение истина тогда и только тогда, когда истинны оба высказывания A и B. Обозначается конъюнкция - AB (АВ). Дизъюнкцией высказываний A и B называется высказывание, которое принимает значение истина, если истинно хотя бы одно из высказываний A или B. Обозначается дизъюнкция - AB. Импликацией высказываний A и B называется высказывание, которое принимает значение ложь тогда и только тогда, когда A истинно, а B ложно. Обозначается АВ. Эквиваленцией высказываний A и B называется высказывание, которое принимает значение истина тогда и только тогда, когда высказывания A и B имеют одинаковые значения. Обозначение операции - АВ (АВ). Логические операции определяются, также, с помощью таблиц, называемых таблицами истинности. Приведем сводную таблицу истинности для всех введенных логических операций. A B A AB AB AB AB л л и и Л И Л и и и л л л л л и л и и и и и л и и л л и Пропозициональной (высказывательной) переменной называется переменная, значениями которой являются простые высказывания. Обозначим высказывательные переменные через X1, X2, . . . , Xn. Понятие формулы алгебры высказываний вводится по индукции. Формулами алгебры высказываний являются: 1) И, Л; 2) пропозициональные переменные; 3) если А и В формулы, то каждое из выражений А, (А  В), (А  В), (А  В), (А ~ В) есть формула; 4) других формул, кроме построенных по пп. 1) - 3), нет. Обозначим через M – множество всех формул алгебры высказываний, M является замкнутым относительно логических операций. Для формулы построенной по п. 3 формулы A и B называются подформулами. Порядок выполнения операций в формуле определяется их приоритетом. Список логических операций в порядке убывания приоритета: ~. Изменение порядка выполнения операций, как и в алгебраических операциях, производится с помощью круглых скобок. В соответствии с таблицами истинности операций можно построить таблицу истинности формулы. Для этого необходимо: 1. Пронумеровать простые высказывания в алфавитном порядке. 2. Для каждого элементарного высказывания рассмотреть все возможные наборы значений истинности. Всего возможно 2n комбинаций, где n - число элементарных высказываний. Это количество строк в таблице. 3. Пронумеровать сложные высказывания, содержащие одну логическую операцию, затем сложные высказывания, содержащие две логических операции, и т.д., увеличивая сложность высказываний в соответствии с порядком выполнения операций. 4. Вычислить значения истинности всех сложных высказываний. Столбец с последним номером будет содержать значение истинности для всей логической формулы. Задание. Построить таблицу истинности формулы (АВ)  АС. Решение. 1. Пронумеруем простые высказывания в алфавитном порядке А-1, В-2, С-3. 2. Каждый набор значений истинности элементарных высказываний изобразится набором ИИИ, ИИЛ, ИЛИ и т. д. Для нашего примера число комбинаций равно 8-ми, то есть таблица истинности будет содержать 8 строк. 3. Пронумеруем сложные высказывания формулы: АВ - 4; ( - 5;  - 6; С - 7; конечная операция  - 8. 4. Вычислим последовательно значения истинности сложных высказываний.   (   B     С 5 1 4 2 8 6 1 7 3 Л Л И И И И И И и и и и л л л л И И Л Л Л Л Л Л и и л л и и л л И И И Л И И И И л л л л и и и и и и и и л л л л и л и л и и и и и л и л и л и л Формулы А и В называются эквивалентными (обозначается А  В), если при любых значениях высказывательных переменных значение формулы А совпадает со значением формулы В. Формула называется выполнимой, если существует такой набор значений переменных, при которых эта формула принимает значение И. Формула называется опровержимой, если существует такой набор значений переменных, при которых эта формула принимает значение Л. Формула называется тождественно истинной (ТИ-формулой) или тавтологией, если эта формула принимает значение И при всех наборах значений переменных. Формула называется тождественно ложной (ТЛ-формулой) или противоречием, если эта формула принимает значение л при всех наборах значений переменных. Так как логические формулы используются в операторах языков программирования и языков баз данных, то актуальными являются задачи определения эквивалентности, выполнимости, опровержимости, тождественной истинности и ложности формул. Такие задачи могут решаться с помощью построения таблиц истинности, однако существуют менее громоздкие способы решения этих задач, которые будут обсуждаться в параграфах 3,4. Булевы функции Любую формулу алгебры логики можно рассматривать как функцию, определенную на множестве B={1, 0}, где 1 соответствует значению “и”, а 0 – значению “л”. Функцией алгебры логики (логической функцией) или булевой функцией f(x1,x2,...,xn) называется отображение f : B nB, определенное на множестве упорядоченных наборов элементов множества B и принимающее значения из этого множества. Обозначим через Pn - множество булевых функций n переменных. Логическую функцию n переменных f(x1,x2,...,xn) можно задать таблицей, в левой части которой перечислены все 2n наборов значений переменных, а в правой части - значения функции на этих наборах. x1 x2 . . . хn-1 xn f(x1, x2 , . . . хn-1 , xn) 0 0 . . . 0 0 0 0 . . . 0 1 0 0 . . . 1 0 . . . . . . . . . . . . . . . . 1 1 . . . 1 0 1 1 . . . 1 1 f(0,0, . . . ,0,0) f(0,0, . . . ,0,1) f(0,0, . . . ,1,0) . . . . . . . . f(1,1, . . . ,1,0) f(1,1, . . . ,1,1) При любом фиксированном упорядочении наборов булева функция n переменных полностью определяется вектор-столбцом своих значений, размерность которого равна числу наборов значений функции, то есть 2n . Поэтому число различных функций n переменных равно числу различных двоичных векторов длины 2n, то есть , т.е. || = . Нулем (единицей) булевой функции назовем упорядоченный набор значений переменных, на котором значение функции равно 0 (1). Пусть F={} – множество булевых функций, называемое базисом. Формулой над базисом F (обозначается [F]) называется выражение вида [F]=, где F. Таким образом, всякая формула является суперпозицией базисных функций, для ее представления обычно применяется инфиксная форма записи с логическими операциями ~. Каждой формуле однозначно соответствует некоторая булева функция f, в этом случае говорят, что формула реализует функцию f, однако, как будет показано ниже, такая реализация не единственна. Приведем примеры логических функций одной и двух переменных и их реализаций в виде формул. Логических функций одной переменной четыре: две нуль-местные (0(х), 3(х)) - константы 0 и 1, значения которых не зависят от значения переменной, и две одноместные функции - тождественная и отрицание. Х 0 1 2 3 1 1 1 1 1 Тождественная функция "повторяет" значение х: 1(х)=х. Функция отрицание возвращает значение, противоположное значению х: 2(х)=¬х. Логических функций двух переменных шестнадцать: х1 Х2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Рассмотрим подробнее все эти функции. *0 0(х1,х2)0 и 15 (х1,х2)1. *1 1(х1,х2) = х1  х2 . Эта функция называется ещё логическим умножением и обозначается, также, х1х2. *2 2(х1.х2) =  (х1х2). *3 3(х1,х2) = х1. *4 4(х1.х2) =  (х2х1). *5 5(х1,х2) = х2. *6 6(х1,х2) = (х1~х2) называются неравнозначностью, разделительной дизъюнкцией или сложением по модулю 2 и обозначается еще как х1 х2. *7 7(х1.х2) = х1 х2 . *8 8(х1.х2) = (х1х2) – антидизъюнкция, которая называется, также, стрелка Пирса и обозначается х1х2. *9 9(х1.х2) = х1~х2 . Эту функцию называют еще равнозначностью и обозначают х1х2 . *10 10(х1.х2) = . *11 11(х1.х2) = х2х1. *12 12(х1.х2) = . *13 13(х1.х2) = х1х2. *14 14(х1.х2) = (х1х2) – антиконъюнкция, которая называется еще штрих Шеффера и обозначается х1 | х2. Можно определить логические операции, соответствующие функциям 6, 8, 14, построив для них таблицы истинности. Фиктивной переменной (несущественной) функции f(x1, . . . , xn) называется переменная хi, изменение значения которой не меняет значения функции, то есть f(x1, . . . , хi-1, 1, xi+1, . . . , xn)= f(x1, . . . , хi-1, 0, xi+1, . . . , xn). Например, в функциях 3 и 12 переменная х2 фиктивна, а в функциях 5 и 10 фиктивна переменная х1. Функция f(x1, . . . , xn), имеющая фиктивную переменную xi, по существу зависит от (n-1)-й переменной, т.е. представляет собой функцию g(x1, . . . , хi-1, xi+1, . . . , xn). Говорят, что функция g получена из функции f удалением фиктивной переменной, а функция f получена из функции g введением фиктивной переменной, причём эти функции считаются равными. Эквивалентность и преобразование формул Введем на множестве M отношения следования и эквивалентности. Формула B следует из формулы A (обозначается AB), если она истинна на всех наборах высказывательных переменных, на которых истинна формула A. Формула A эквивалентна формуле B (обозначается A~B), если они следуют друг из друга, то есть AB и BA. Легко показать, что это определение эквивалентно определению, введенному в п.1. Теорема 3.1. Формула B следует из формулы A тогда и только тогда, когда тождественно истинна формула AB. Теорема 3.2. Формула A эквивалентна формуле B тогда и только тогда, когда тождественно истинна формула A~B. Эквивалентность формул является отношением эквивалентности, поэтому множество M можно разбить на классы эквивалентности, включив в один класс эквивалентные между собой формулы. Каждой формуле U соответствует класс эквивалентности, который обозначается [U]. Теорема 3.3. Если A есть некоторая подформула формулы U и A эквивалентна формуле B, то формула, полученная заменой A в формуле U на B, эквивалентна U. Иными словами, если A~B, то U(A) ~ U(B). Например, так как AB ~ , то (AB)C ~ C. Следствие. Если U~A и V~B, то: 1) UV ~ AB; 2) UV ~ AB; 3) UV ~ AB; 4) (U~V) ~ (A~B); 5) U ~ A. Теорема 3.3 и ее следствие позволяют преобразовывать формулы, упрощая их, и доказывать эквивалентность формул. Приведем список основных тавтологий, выражающих свойства логических операций. 1. Коммутативность: X Y ~ Y X, X Y ~ YX. 2. Ассоциативность: (X Y)Z ~ X (YZ), (XY)Z ~ X(YZ). 3. Идемпотентность: XX ~ X, XX ~ X. 4. Законы поглощения: XXY ~ X, X(XY) ~ X. 5. Взаимная дистрибутивность конъюнкции и дизъюнкции: X (YZ) ~ (X Y)(X Z), X (YZ) ~ (XY)(XZ). 6. Свойства констант: XЛ ~ Л, XИ ~ X, XИ ~ И, XЛ ~ X. 7. Законы де Моргана: , . 8. Закон двойного отрицания: . 9. Закон противоречия:  Л. 10. Закон исключенного третьего:  И. Тождественная истинность всех формул (кроме законов поглощения) уже доказана непосредственно построением таблиц истинности. Задание. Доказать 1-й из законов поглощения. Решение. . Приведем еще несколько эквивалентностей, имеющих широкое применение. 11. . 12. . 13. Склеивание: , . Формула называется приведенной, если она содержит операции конъюнкции, дизъюнкции и операцию отрицания, относящуюся к высказывательным переменным. Теорема 3.4. Каждый класс эквивалентности [U] может быть представлен приведенной формулой, т.е. для любой формулы U M существует приведенная формула V. Приведенная формула для данного класса эквивалентности не является единственной. Определим порядок построения приведенной формулы. 1. Удаляются операции импликация и эквиваленция по формулам 11, 12. 2. Операции отрицания спускаются до высказывательных переменных с помощью законов де Моргана и двойного отрицания. 3. Если это возможно, то полученная приведенная формула упрощается с помощью свойств 3, 4, 5, 6, 9, 10. Таким образом, проверить эквивалентность формул, тождественную истинность и ложность формулы или упростить ее можно с помощью этого алгоритма. Задание. Упростить формулу . Решение. () ~ ~ () ~ () ~ A. Формула U* называется двойственной к приведенной формуле U, если она получена заменой операций конъюнкции на дизъюнкции и наоборот. Теорема 3.5 (принцип двойственности). Пусть U() – приведенная формула, тогда U*() ~ U(). В автоматическом управлении и при эксплуатации вычислительных ма­шин приходится иметь дело с переключательными схемами (релейно-контакт­ными, полупроводниковыми), состоящие из сотен реле, полупроводников, маг­нитных элементов. Переключательная схема состоит из переключателей (на­пример, кнопочные устройства, электромагнитные реле, полупроводниковые элементы и т.п.) и соединяющих их проводников. При конструировании таких схем существенную помощь может оказать алгебра высказываний: можно по­строить схему, выполняющую требуемые функции (синтезирование схемы) или изучить действие построенной схемы и возможно ее упростить (анализ схемы). Каждой схеме ставится в соответствие формула алгебры высказываний, и каждая формула реализуется с помощью некоторой схемы. Покажем, как уста­новить такое соответствие. Каждому переключателю P ставится в соответствие высказывательная переменная P, которая истинна тогда и только тогда, когда переключатель P замкнут. Схеме с последовательным соединением переключа­телей P и Q соответствует формула, являющаяся конъюнкцией высказаватель­ных переменных, соответствующих этим переключателям, . Схеме с параллель­ным соединением переключателей P и Q соответствует формула, являющаяся дизъюнкцией высказавательных переменных, соответствующих этим переклю­чателям, . Два переключателя P и могут быть связаны так, что когда P замкнут, то разомкнут. Тогда переключателю ставится в соответствие переменная , являющаяся отрицанием P. Задание. Упростить схему Решение. Запишем формулу, соответствующую схеме, по приведенным выше правилам U = . Преобразуем эту формулу, используя соответствующие эквивалентности U ~ ~ ~ . Изобразим схему, соответствующую заключительной формуле Нормальные формы Данный параграф посвящен решению проблемы выполнимости и опровержимости формул. Для этого используются нормальные формы, определим их. Элементарной конъюнкцией называется конъюнкция, в которой участвуют высказывательные переменные или их отрицания. Элементарной дизъюнкцией называется дизъюнкция, в которой участвуют высказывательные переменные или их отрицания. Дизьюнктивной нормальной формой называется формула, имеющая вид дизъюнкции элементарных конъюнкций. Коньюнктивной нормальной формой называется формула, имеющая вид конъюнкции элементарных дизъюнкций. Теорема 4.1. Для всякой формулы U существуют эквивалентные ей КН-форма и ДН-форма. ДНФ и КНФ не единственны. Существуют формулы, к которым можно привести любую логическую формулу, но единственным образом с точностью до порядка элементарных дизъюнкций или конъюнкций и элементов в них. Такими формулами являются совершенные нормальные формы. Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ в каждой конъюнкции которой содержатся точно одно вхождение всех переменных или их отрицаний. Такие конъюнкции называются полными. Совершенной конъюнктивной нормальной формой (СКНФ) называется КНФ в каждой дизъюнкции которой содержатся точно одно вхождение всех переменных или их отрицаний. Такие дизъюнкции называются полными. Теорема 4.2. 1) Всякая элементарная дизъюнкция высказывательных переменных , не являющаяся ТИ-формулой, эквивалентна некоторой СКН-форме от этих высказывательных переменных. 2) Всякая элементарная конъюнкция высказывательных переменных , не являющаяся ТЛ-формулой, эквивалентна некоторой СДН-форме от этих высказывательных переменных. Следствие. Для всякой формулы, образованных из высказывательных переменных не являющейся тождественно истинной и тождественно ложной, существуют эквивалентные им СКН-форма и СДН-форма . Алгоритм построения совершенных нормальных форм. 1. Преобразовать формулу к приведенному виду (см. п.3). 2. Если полученная формула не является нормальной, то преобразовать ее к требуемой нормальной форме (если она существует) с помощью свойства взаимной дистрибутивности операций конъюнкции и дизъюнкции. 3. Если нормальная форма не является совершенной, то расщепить конъюнкции (дизъюнкции), которые содержат не все переменные, по свойству 13. Задание. Построить совершенные нормальные формы формулы . Решение. Преобразуем формулу к приведенному виду и затем упростим ее. ()~() ~ ~ () ~ () ~ ~ () ~ () Полученная формула является КН- и ДН-формой, однако обе формы не являются совершенными. Приведем ее к совершенному виду. () ~ () – СКН-форма. () ~ () ~ ) – СДН-форма. Сформулируем изложенные выше утверждения для булевых функций. Для этого введем, предварительно, следующие обозначения. Обозначим . Теорема 4.3 (о разложении булевых функций). Любую булеву функцию можно представить в виде где дизъюнкции берутся по всем возможным наборам (). Из этой теоремы непосредственно следует представление булевой функции в виде СДН-формы. Теорема 4.4. Всякая булева функция (кроме 0) имеет единственную СДН-форму . С помощью принципа двойственности легко доказать представление функции СКН-формой. Теорема 4.5. Всякая булева функция (кроме 1) имеет единственную СКН-форму . Возможно построение совершенных нормальных форм булевой функции, заданной таблицей. Нули функции определяют полные элементарные дизъюнкции, входящие в СКН-форму функции. Такая дизъюнкция строится так, чтобы все составляющие ее переменные или их отрицания обращались в нуль. Соответственно, по единицам булевой функции можно построить ее СДН-форму. Например, функция f переменных x1, x2, x3, заданная в таблице x1 x2 x3 f g h 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Таблица 1. имеет следующие совершенные нормальные формы: - СКН-форма; - СДН-форма. Упростив любую из этих формул, можно получить простейшую формулу, реализующую данную функцию. С помощью совершенных нормальных форм можно решить проблему выполнимости или опровержимости формулы. Для того, чтобы найти при каких значениях высказывательных переменных формула является выполнимой, необходимо получить ее СДН-форму и найти значения переменных, при которых элементарные конъюнкции истинны. Аналогично, для решения задачи опровержимости строится СКН-форма. Полные системы операций. Алгебра Жегалкина Система операций  называется полной, если любая логическая операция может быть представлена формулой над . Так как всякая формула может быть представлена приведенной формулой, то система 0 = {, , } - полна. Полной будет и любая система , через операции которой можно выразить конъюнкцию, дизъюнкцию и отрицание. Если все операции полной системы * представимы формулами над системой , то  полна, в этом случае говорят, что  сводится к *. Алгебра над множеством логических функций с двумя операциями  и  называется алгеброй Жегалкина. В алгебре Жегалкина выполняются следующие соотношения: , , , , а также ассоциативность, коммутативность, идемпотентность конъюнкции и свойства констант. Задание. Доказать полноту системы 5 = {, }. Решение. Сведем систему 5 к полной системе 0. . Доказательство неполноты системы операций необходимо проводить в терминах булевых функций. Система булевых функций F называется полной, если любая функция может быть реализована формулой над F. Замыканием множества F (обозначается [F]) называется множество всех булевых функций, реализуемых формулами над F. Класс функций называется замкнутым, если [F] = F. Примеры замкнутых классов. 1. Класс функций, сохраняющих 0. . 2. Класс функций, сохраняющих 1. . 3. Класс самодвойственных функций. . 4. Класс монотонных функций. , где . 5. Класс линейных функций. . Теорема 5.1 (Поста). Система булевых функций полна тогда и только тогда, когда она содержит хотя бы одну функцию, не сохраняющую 0, хотя бы одну функцию, не сохраняющую 1, хотя бы одну несамодвойственную функцию, хотя бы одну немонотонную функцию и хотя бы одну нелинейную функцию. Если в произвольной формуле алгебры Жегалкина, реализующей булеву функцию f, раскрыть скобки и произвести все возможные упрощения, то получится формула, имеющая вид суммы произведений, то есть полинома по mod 2. Такая формула называется полиномом Жегалкина для данной функции. Таким образом, линейной называется функция, полином Жегалкина которой линеен. Задание. Представить формулу (x1  x2)( x1x3) в виде полинома Жегалкина. Решение. (x1  x2)( x1x3) = ( x1x2 x1 x2)( x1x3 x1x3) = = x1 (x2  1) x3  x1 x2 x3  x1 x3  x1 x2 x3  x1 (x2  1) = = x1 x2 x3  x1 x2  x1 Теорема 5.2. Для всякой логической функции существует полином Жегалкина, и притом единственный. Выводимость Пусть задано множество формул от высказывательных переменных (), (), . . . , (). (1) Это множество формул назовем системой посылок. Определение. Формула () называется выводимой из системы формул (1) в алгебре высказываний, что обозначается , . . , , тогда и только тогда, когда формула (2) является ТИ-высказыванием, т.е.  . Из определения следует, что если конъюнкция (3) тождественно истинна, то из такой системы посылок (1) выводимы только тождественно истинные формулы, которые выводимы из любой системы посылок. Если же конъюнкция (3) тождественно ложна, то из системы посылок (1) выводима любая формула. Если формула выводима из системы формул (1), то из истинности всех формул системы при некоторых значениях высказывательных переменных следует истинность формулы при тех же значениях переменных. Нетрудно доказать следующие свойства выводимости. 1. Если  и  то  . 2. Если  и ~, то . Проверка выводимости формулы из системы посылок (1) непосредственно по определению, т.е. путем доказательства тождественной истинности формулы (2), достаточно громоздко. Рассмотрим более простой способ доказательства выводимости формулы из системы посылок (1), для которых конъюнкция (3) не является ни ТИ-высказыванием, ни ТЛ-высказыванием. Теорема 1.1. Формула () тогда и только тогда выводима из системы формул (1), когда все полные элементарные дизъюнкции формулы входят в СКН-форму , эквивалентную формуле (3) относительно высказывательных переменных . Так как теорема 1 формулирует необходимое и достаточное условие выводимости формулы, то на основе нее можно сформулировать алгоритм доказательства выводимости формулы. 1. Из системы посылок (1) строится конъюнкция (3). 2. Находим СКН-форму от высказывательных переменных для формулы (3). 3. Строим СКН-форму для формулы и проверяем вхождение полных элементарных дизъюнкций СКН-формы для формулы в СКН-форму для формулы (3). Задание 1. Доказать выводимость . Решение. 1. Обозначим = X, =. Строим их конъюнкцию . 2. Найдем СКН-форму эквивалентную этой конъюнкции. V 3. Получим СКН-форму для формулы B. Так как обе дизъюнкции входят в СКН-форму , то выводимость доказана. Замечание. Выводимость формулы можно получить и без нахождения ее СКН-формы. Для этого нужно преобразовать с помощью известных эквивалентностей формулу (3) или даже конъюнкцию некоторых полных дизъюнкций из этой СКН-формы. Например, конъюнкция 1-ой и 3-ей полных дизъюнкций формулы из задания 1 преобразуется с помощью формулы склеивания к искомой формуле. Кроме того, воспользовавшись теоремой 1, можно построить все СКН-формы выводимые из данной системы посылок. Для этого требуется небольшая модификация алгоритма доказательства выводимости формулы. После построения СКН-формы для формулы (3) необходимо 3. Из полных элементарных дизъюнкций полученной СКН-формы строим различные комбинации конъюнкций. Эти конъюнкции и будут исчерпывать все СКН-формы, выводимые из системы посылок (1). Задание 2. Найти все формулы, выводимые из системы посылок задания 1. Решение. Построим различные комбинации полных элементарных дизъюнкций формулы . 1. 2. 3. 4. 5. 6. 7. Как легко видеть, при построении всех СКН-форм, выводимых из данной системы посылок, мы получили, как частный случай, формулу . Следует заметить, что на понятии выводимости основан способ доказательства утверждений методом приведения к абсурду. При использовании этого метода для доказательства истинности утверждения строится его отрицание , а затем показывается, что из этого утверждения могут быть выведены некоторые противоречащие друг другу утверждения и , т.е. доказываются выводимости  и . После этого делается заключение, что утверждение истинно, так как формула является ТИ-высказыванием. В силу определения выводимости, это означает, что формула выводима из формул и . Алгебра предикатов Алгебра предикатов является развитием алгебры высказываний. Кроме простых и составных высказываний она вводит в рассмотрение высказывания, отнесенные к переменным из некоторого множества M, которое в дальнейшем будем называть предметным множеством, а его элементы – предметными переменными. Неформально предикат можно определить как некоторое высказывание, значение которого зависит от значений предметных переменных из множества M, на котором определен предикат. Примеры: a) P(x) – “x есть простое число”; b) Q(x) – “x есть нечетное число”; c) D(x,y) – “x нацело делится на y”; d) R(x,y) – “x > y”. В качестве предметного множества для этих примеров можно рассматривать любые числовые множества, в частности, в примерах a) – c) – M = , а в d) – M = . Более строго предикат можно определить как отображение n-ной степени множества M, называемой местностью или арностью предиката в двухэлементное множество B = {И, Л} . При подстановке в предикат вместо предметных переменных набора значений получим логическое высказывание. Таким образом, предикат представляет собой переменное высказывание (или систему высказываний), истинность которого определяется подстановкой различных значений предметных переменных. Так как предикаты принимают значения из множества B, то для них определены логические операции ~. Кроме того, для предикатов вводятся операции утверждения общности и утверждения существования. Операция утверждение общности ставит в соответствие высказывательной форме P(x) высказывание (читается как, P(x) истинно для всех x из множества M, на котором определен предикат). Высказывание истинно тогда и только тогда, когда высказывание P(a) истинно для любого элемента . Операция утверждение существования ставит в соответствие высказывательной форме P(x) высказывание (читается как, существует такой x из множества M, для которого высказывание P(x) истинно). Высказывание истинно тогда и только тогда, когда высказывание P(a) истинно хотя бы для одного элемента . Знаки  и  называются кванторами общности и существование (квантор в переводе с латинского – определение количества). Переход от высказывательной формы P(x) к высказываниям или называется навешиванием квантора или связыванием переменной x (иногда – квантификацией переменной x). Переменная, на которую навешен квантор, называется связанной, несвязанная переменная называется свободной. Смысл связанных и свободных переменных в предикатных выражениях различен. Свободная переменная – это обычная переменная, которая может принимать различные значения из M, а выражение P(x) – переменное высказывание, зависящее от значения x. Выражения и не зависят от переменной x и при фиксированных P и M имеют вполне определенное значение. Переменные, являющиеся по существу связанными, встречаются не только в математической логике. Например, в выражениях или переменная x связана, при фиксированной f первое выражение равно определенному числу, а второе является функцией от a и b. Таким образом, в высказываниях и говорится не о свойствах отдельных элементов множества M, а о свойствах самого множества M. Истинность или ложность этих высказываний не зависит от того, как обозначена предметная переменная, входящая в них, и ее можно заменить любой другой предметной переменной, например y, и получить высказывания и , имеющие тот же самый смысл и те же самые значения истинности, что и исходные высказывания. В общем случае для n-арного предиката, если , операции утверждения общности или существования можно выполнять k раз (порядок выбора переменных, по которым происходит навешивание квантора, может быть любым, исключая их повторение) и получить выражение , () где обозначает квантор общности или существования. Переменные в высказывательной форме () являются связанными, а – свободными. Высказывательная форма () при замене переменных элементами множества M обращается в истинное или ложное высказывание. При k = n высказывательная форма () становится высказыванием. Изменение порядка следования кванторов, в общем случае, изменяет смысл высказывания, а, следовательно, и его истинностное значение. Например, для предиката делимости D(x,y): a) высказывание читается, как “для любого x существует y, такое, что x делится на y”, и является истинным высказыванием; b) высказывание читается, как “существует y, на который делится любой x ”, и является истинным высказыванием; c) высказывание читается, как “существует x, который делится на любое y”, и является ложным высказыванием; d) высказывание читается, как “для любого y существует такой y, что x делится на y”, и является истинным высказыванием. Ряд важнейших понятий алгебры предикатов основывается на понятии модели. Моделью  называется любое множество M с заданными на нем предикатами :  = < M ; >. Множество M называется основным множеством модели , предикаты – основными предикатами модели , и их набор  = <> называется сигнатурой модели . Натуральные числа k1,  , kn обозначают арности соответствующих предикатов, а их набор  = < k1,  , kn > называется типом модели. Примеры. 1. N – множество натуральных чисел, E, S, P – определенные на множестве N равенства, сложения и умножения. Модель  = < N; E, S, P > является арифметикой натуральных чисел. Ее сигнатура  = < E, S, P > и тип  = < 2, 3, 3 >. 2. Любое множество моделей с одной и той же сигнатурой  называется классом K моделей сигнатуры . Определим формулу алгебры предикатов сигнатуры . Так же как и в алгебре высказываний, такое определение является индуктивным. 1. Если и – предметные переменные, то выражение есть формула. Такая формула называется атомарной, в ней все вхождения предметных переменных называются свободными. 2. Если U есть формула, в которой имеются свободные вхождения переменной xi, то выражения xi (U) и  xi (U) – формулы, в которых все вхождения xi являются связанными, а все вхождения остальных предметных переменных такие же, какими они были в формуле U. При этом формула U называется областью действия соответствующего квантора общности или существования. 3. Если U есть формула, то  U – также формула, и все свободные и связанные вхождения предметных переменных в формулу U являются соответственно свободными и связанными вхождениями в формуле  U. 4. Если U и V есть формулы, то выражения (U)  (V), (U)  (V), (U)  (V), (U) ~ (V) также являются формулами, причем все вхождения предметных переменных в этих формулах такие же, как и в формулах U и V. 5. Формулы могут быть образованы только с помощью правил 1 – 4. Число скобок в формуле можно уменьшить, если условиться: a) не заключать в скобки атомарные формулы и формулы, над которыми записан знак отрицания; b) вместо записи , где – некоторые кванторы, допускать запись ; c) не использовать скобки, если порядок выполнения операций соответствует приоритету операций, причем приоритет операций утверждения общности и существования наивысший, для остальных операций такой же, как и в алгебре высказываний; d) не заключать в скобки подформулы, обозначенные буквами; e) не указывать явно с помощью верхнего индекса местность предиката. Если формула U не содержит свободных вхождений предметных переменных, то используя определения операций, можно вычислить ее логическое значение. В общем случае, если в формуле U есть свободные вхождения предметных переменных, то она не является высказыванием. Но при каждой замене в этой формуле всех свободных вхождений предметных переменных элементами множества M она становится высказыванием, значение которого вычисляется так же, как и в первом случае. Формула называется выполнимой на модели , если для некоторой системы элементов модели  сигнатуры  значение формулы сигнатуры , т.е. высказывание , является истинным. Формула U сигнатуры  называется выполнимой, если существует модель сигнатуры , на которой выполнима формула U. Если высказывание является истинным для любой системы значений , то формула U называется истинной на модели . Если формула не выполнима на модели , то она называется ложной на модели . Если формула U истинна на любой модели класса K , то она называется истинной на классе K . Определение. Полная система предикатов на конечном множестве – такая система, что любой предикат над выражается через предикаты системы (с помощью четырех основных операций, приведенных выше). Очевидно, всего предикатов на . Теорема. - полная система для любых и из , таких что , найдется предикат, который принимает разные значения на и : . Доказательство. ) от противного. Пусть все предикаты принимают равные значения на и . Тогда любая формула над этой системой обладает тем же свойством, а следовательно, нельзя получить, например, предикат, который равен 1 на и 0 во всех остальных точках, в том числе . ) Пусть . Пусть , будем иметь для всех . Пусть теперь , очевидно, , потому что, если , найдется такой , что , откуда . Построим аналог СДНФ. Если , то . Если и - все элементы , на которых равно 1 (), то . Конец доказательства. Рассмотрим еще некоторые логические конструкции: навешивание кванторов. Пусть у нас есть предикат . Навешиванием квантора общности называется получение из этого предиката предикат , значение которого на каждом определяется следующим образом: рассмотрим все пары , ( фиксировано, пробегает все , не обязательно конечно). Если для всех таких пар , то считаем . Если же есть хотя бы одна пара, на которой принимает значение 0, то . Навешивание квантора существования – операция получения предиката , который равен 1 в точке в том и только в том случае, если существует такая пара , что . Кванторы суть обобщения записей и , имеющих смысл только в конечных множествах . Предикаты друг в друга подставляться не будут. Определение. Формула – это 1) – формула. - множество свободных переменных; - множество связанных переменных. 2) Если и - формулы, а и соответственно множества свободных и связанных переменных первой и и соответственно множества свободных и связанных переменных второй формулы, причем выполнены условия и , то , - тоже формулы, множества свободных и связанных переменных равны соответственно и . При этом вычисление происходит по правилам и . Также является формулой со множеством свободных переменных и множеством связанных переменных . . 3) Дальше, если - формула, а и - множества свободных и связанных переменных ее, , то навешиванием квантора общности получаем формулу (обозначим ), , . Отсюда видно, что связанные переменные возникают вследствие навешивания кванторов. Пусть . Рассмотрим все наборы , где , , фиксированы, а пробегает все множество . Если для любого , то полагаем . В противном случае, если существует такое, что , то . На формулу можно навесить квантор существования аналогичным образом. Строим формулу (обозначим ) с и , равную 1 на наборе если существует такое , что , и 0, если такого нет. Определение. Формула истинна в модели, если для любого набора значений свободных переменных она принимает значение 1 (истину). Примеры. - предикаты делимости соответственно на 2, 3, 6. Тогда формула (функция) истинна в модели . - предикаты делимости на индекс. Тогда формула не является истинной на всех . Определение. Формула истинна на множестве, если она истинна в любой модели, заданной на этом множестве (само множество фиксировано, а формула верна для любых предикатов). Примеры. . - не всегда верна (можно получить ), но эта формула верна на одноэлементном множестве. Определение. Тождественно истинная формула – формула, истинная для любого множества. Также есть понятие эквивалентности формул (в модели, на множестве, тождественно); рассмотрим несколько примеров. и эквивалентные формулы. и эквивалентны на . и эквивалентны на любой модели. Оказывается, что Теорема. Существует исчисление, содержащее конечное число аксиом и правило вывода , в котором все выводимые формулы тождественно истинны, а также все тождественно истинны формулы выводимы. Займемся эквивалентными формулами. Рассмотрим правила их преобразования, которые позволяют получить эквивалентную формулу, возможно, более удобного вида. Правило №1. В любой формуле при замене связанной переменной на другую переменную, так чтобы сохранялись ограничения, наложенные при построении формулы, получим эквивалентную формулу. Пример. и эквивалентны. Здесь в первой формуле связана , во второй - . В обеих формулах свободными являются . Группа правил №2. Формула эквивалентна формуле . Эта утверждение – аналог закона Де-Моргана для многих переменных: . Доказательство. Пусть - все свободные переменные в формуле . Зададимся произвольным набором и рассмотрим все наборы . Первый случай. Для любого . Тогда , . Но если для любого , то , откуда . Второй случай. Существует , для которого . Имеем , . С другой стороны, существует , для которого , а значит, и , следовательно, . Аналогично можно получить, что эквивалентно . Правила №3. Рассмотрим формулу и навесим на нее квантор общности , при предположении, что входит в число свободных переменных и не входит в вообще. Тогда эта формула эквивалентна . Доказательство. Пусть - все свободные переменные в и (каждая встречается хотя бы в одной как свободная). Возьмем произвольный набор . Возможно, . Тогда для любого , а значит, . Но в то же время . Если же , то для любого (т.к. не входит в ), откуда при любом , следовательно, на данном (произвольном) наборе равно , равное , что указывает на эквивалентность формул. При тех же условиях эквивалентны следующие пары формул: и и и . Зная это, можно показать, что любая формула приводима к специальному виду: Теорема. Для любой формулы существует эквивалентная ей формула, такая что сначала идут все кванторы, а затем остальные формулы, без кванторов: . Доказательство. Сначала все отрицания переносим на формулы через все кванторы (для этого у нас есть два правила аналога законов Де-Моргана), а затем делаем все кванторы по разным переменным (т.е. замену связанной переменной на новую при ее повторении в каком-нибудь еще месте). Пример. переводим в . Наконец применяем правила из предыдущего утверждения и выносим все кванторы наружу, после чего формула принимает нормальный вид. Пример. эквивалентно эквивалентно эквивалентно . Логические исчисления Логическим исчислением принято называть синтаксическую (т.е. формализованную аксиоматическую) теорию математической логики. Описание всякого исчисления включает: 1) описание алфавита, т.е. множества символов, используемых для построения формул теории; 2) описание языка, т.е. правил построения допустимых последовательностей символов (слов) в алфавите, называемых формулами; 3) задание системы аксиом – некоторого множества истинных формул, называемых аксиомами; 4) определение правил вывода, позволяющих из одних истинных формул получать другие формулы рассматриваемой синтаксической теории. Указанием аксиом и правил вывода мы полностью определили понятие истинной, или выводимой в исчислении высказываний, формулы. Пользуясь правилами вывода, мы можем, исходя из аксиом, конструировать новые истинные формулы и получать, таким образом, каждую истинную формулу. Формула B называется доказуемой (теоремой в исчислении высказываний), если существует конечная последовательность формул B1, B2, . . . , Bt , (4) в которой каждая из формул Bi является либо аксиомой, либо, получена по правилам вывода из некоторых предыдущих формул последовательности (4). Эта последовательность называется доказательством формулы (теоремы). Рассмотрим примеры таких доказательств. Как легко видеть, вывод истинной в исчислении высказываний формулы непосредственно из аксиом с использованием правил вывода является достаточно громоздкой процедурой, которую хотелось бы упростить. Для этого определим понятие выводимости и производные правила вывода, ключевым среди которых является теорема дедукции, которые позволят нам устанавливать выводимость различных формул без непосредственного вывода этих формул. Мы будем говорить, что формула B выводима из формул U1, U2, . . . ,Un в исчислении высказываний, если формулу B можно вывести только путем правила заключения, приняв за исходные формулы U1, U2, . . . ,Un и все истинные в исчислении высказываний формулы. Точное определение выводимости формулы в исчислении высказываний имеет вид: формула B выводима из формул U1, U2, . . . ,Un, называемых исходными, что записывается символически как U1, U2, . . . ,Un B, если существует такая конечная последовательность формул (4), что Bt есть B и для каждой формулы Bi выполнено одно из условий: 1) Bi есть посылка или теорема исчисления высказываний; 2) Bi получена из некоторых предыдущих формул последовательности (4) по правилу заключения. Последовательность (4) называется в этом случае выводом формулы B из системы посылок U1, U2, . . . ,Un. Рассмотрим пример вывода формулы. Задание 2. Доказать, что A. Решение. Для данного примера система посылок содержит 1 формулу U1=A, а выводимая формула B =. Построим вывод этой формулы. 1) B1 = A 2) B2 = - аксиома 1 3) B3 = B = - получено из B1 и B2 в силу правила заключения. Заметим, что если посылки являются аксиомами или теоремами исчисления высказываний, то класс выводимых из них формул совпадает с классом всех истинных формул, выводимых из любой системы посылок. Часто для записи правил вывода используют сокращенную схему, они выражаются в следующих терминах. “Если формулы U, B, . . . истинны, то формулы M, N, . . . также истинны”. Такие утверждения записываются в виде схемы: . Так, правило заключения запишется как . В виде аналогичной схемы можно записывать правило получения выводимости из некоторой системы посылок. Обозначим через – систему посылок . Выражение вида U1 , . . . ,  Un   B назовем допустимым в исчислении высказываний правилом, если в исчислении высказываний из U1 , . . . ,  Un следует  B. При выводе формул широко используются свойства монотонности конъюнкции, дизъюнкции и импликации. Теорема 2.1. Имеют место следующие выводимости: 1) ,; 2) ,; 3) ,. Следствие. Если  и , то: 1) ; 2) ; 3) . Исчисление высказываний Исчисление высказываний – это аксиоматическая логическая система, адекватная алгебре высказываний. Опишем это исчисление. В качестве алфавита исчисления высказываний возьмем следующее множество символов: 1) счетное множество высказывательных переменных, обозначаемых прописными латинскими буквами с индексами и без них; 1) символы логических операций ; 2) скобки ( , ). Вместе с символами алфавита будем использовать и метасимволы: латинские буквы жирного шрифта для обозначения формул и знак = для обозначения формул метасимволами. Множество формул обычно задается индуктивным определением. Допустимыми последовательностями символов или словами в языке исчисления высказываний являются формулы алгебры высказываний. Пункты 1 и 2 этого определения (см. методические указания “Алгебра высказываний. Булевы функции”) определяют элементарные формулы, а п. 3 – механизм образования новых формул. Следует заметить, что в исчислении высказываний не разрешается опускать скобки для операций с большим приоритетом, что допустимо в алгебре высказываний. Так, например, формула алгебры высказываний не является формулой исчисления высказываний, ее следует записать, как , в дальнейшем изложении мы будем опускать лишь внешние скобки. Следующим шагом в описании исчисления высказываний будет выделение класса формул, которые будем называть истинными или доказуемыми в исчислении высказываний. Это определение имеет такой же рекуррентный характер, как и определение формулы. Сначала определим исходные истинные формулы, называемые аксиомами. В качестве системы аксиом примем следующие формулы (аксиоматика П.С.Новикова). 1. 1. 2. 3. 4. 5. 6. 7. 8. 9. После этого определим правила, позволяющие из истинных формул образовывать новые. Эти правила, мы будем называть правилами вывода. Образование истинной формулы из исходных истинных формул или аксиом путем применения правил вывода будем называть выводом данной формулы из аксиом. Определим правила вывода, которые являются отношениями на множестве формул. 1. Правило подстановки. Пусть U – формула, содержащая высказывательную переменную A. Тогда если U – истинная формула в исчислении высказываний, то, заменяя в ней переменную A всюду, куда она входит, произвольной формулой B, мы также получим истинную формулу. 1. Правило заключения (modus ponens). Если U и U®B истинные формулы в исчислении высказываний, то B также истинная формула. Выводимость формулы из системы посылок отличается от доказательства теоремы в исчислении высказываний тем, что здесь допускается использование только правила заключения. Но при выводе формулы разрешается использовать любую теорему исчисления высказываний, для получения которой может применяться правило подстановки. Из каждой формулы U с помощью правила подстановки, производящего замену высказывательных переменных в этой формуле любыми формулами, может быть получено бесконечное множество формул. Это множество формул называется схемой формулы U и обозначается выражением, полученным заменой в формуле U всех входящих в нее высказывательных переменных метасимволами . Например, из формулы возникает схема формул . (5) Этой схеме принадлежит формула . Новые схемы формул можно получить заменой ее метасимволов схемами формул. Эти схемы выделяют некоторое подмножество формул из множества формул, принадлежащих исходной схеме. Например, из схемы (5) можно получить схему формул . (6) Формула принадлежит как схеме формул (5), так и (6). Для формул, являющимися аксиомами или теоремами, схемы формул называются соответственно схемами аксиом или схемами теорем. Схемами аксиом являются: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Таким образом, при выводе формулы из системы посылок (которая может быть и пустой) будут использоваться схемы аксиом и правило заключения, правило подстановки применяется неявно в схеме аксиом. Наряду с правилом заключения, мы будем использовать и другие правила образования истинных и выводимых формул. Эти правила являются производными от основных и используются для сокращения многократного применения основных правил. Перечислим основные из производных правил вывода. Как и прежде, метасимволы являются произвольными формулами, а через T обозначим конечное множество формул (возможно пустое). 1. Правило повторения посылки. T, 2. Правило введения посылки. Если T, то T, . 3. Правило удаления посылки. Если T, и T, то T. 4. Правило силлогизма. Если T, . . . , T и , то T. 5. Правило введения импликации. Если T,, то T. Это весьма важное свойство называют еще теоремой дедукции. Учитывая, что - конечное множество формул, свойство 5 можно сформулировать в следующем виде: Теорема дедукции. Если  B, то . 6. Правило удаления импликации. Если T, то T,. 7. Правило введения конъюнкции. T, . 8. Правило удаления конъюнкции. T, , T, . 9. Правило введения дизъюнкции. T, , T, . 10. Правило удаления дизъюнкции. Если T, и T, , то T, . 11. Правило введения отрицания. Если T, и T, , то T. 12. Правило удаления отрицания. T,  13. Правило контрапозиции. Если T, , то T,  . Правила 1-13 называют обычно правилами естественного вывода, а вывод формулы из системы посылок, при котором используются эти правила, - естественным выводом. Метатеория исчисления высказываний Исчисление высказываний, как синтаксическая теория, ставит своей задачей доказать все формулы, являющиеся теоремами исчисления высказываний. Но все это имеет смысл, если само исчисление высказываний является состоятельным, как синтаксическая теория, то есть положительно решены проблемы непротиворечивости, полноты, разрешимости, наличия связи с алгеброй высказываний и др. Решением подобного рода вопросов и занимается метатеория соответствующей синтаксической теории. Определение 1. Синтаксическая теория, содержащая знак операции отрицания, называется непротиворечивой, если ни для какой формулы этой теории формулы и не могут одновременно быть теоремами этой теории. В противном случае, теория называется противоречивой. Понятию же непротиворечивости можно дать и другое, эквивалентное первому определение. Определение 2. Синтаксическая теория называется непротиворечивой, если существует формула, не являющаяся ее теоремой. Покажем, что эти определения для исчисления высказываний эквивалентны. Пусть исчисление высказываний непротиворечиво по первому определению. Предположим противное, что исчисление высказываний противоречиво, в смысле второго определения. Тогда в нем доказуема любая формула, а, следовательно, и формула . В силу правила 8 исчисления высказываний, получим, что  и , т. е. как , так и были бы теоремами в этой теории, что противоречит условию. Следовательно, исчисление высказываний непротиворечиво в смысле второго определения. Покажем, теперь обратное, что из непротиворечивости исчисления высказываний по второму определению следует его непротиворечивость в смысле первого определения. Если бы исчисление высказываний было противоречиво, в смысле первого определения, то в нем были бы доказуемы, например, формулы и . Тогда, по теореме эквивалентности из схемы аксиом 6 и свойства отношения эквивалентности 12 следует, что . Применяя к последней формуле правило 6, получим , , где - любая формула. Следовательно, исчисление высказываний противоречиво и во втором смысле. Противоречивая синтаксическая теория никакой ценности не имеет, так как в ней выводимы любые формулы, и любая теорема одновременно и истинна, и ложна. При доказательстве непротиворечивости исчисления высказываний мы будем использовать следующее утверждение. Теорема 4.1. Всякая формула, являющаяся теоремой в исчислении высказываний, является ТИ-высказыванием в алгебре высказываний. Непротиворечивость исчисления высказываний является непосредственным следствием этой теоремы. Действительно, в алгебре высказываний формулы и не могут быть одновременно ТИ-высказываниями. Следовательно, и одновременно не могут быть теоремами исчисления высказываний, что означает ее непротиворечивость. Утверждение, обратное теореме 4.1, означает полноту исчисления высказываний относительно алгебры высказываний. Теорема 4.2. В исчислении высказываний доказуема всякая формула, которая, как формула алгебры высказываний, является ТИ-высказываний. По существу, эта теорема утверждает, что логических средств, т. е. аксиом и правил вывода, исчисления высказываний вполне достаточно для доказательства всех тождественно истинных формул алгебры высказываний. Теоремы 4.1 и 4.2 формулируют необходимое и достаточное условия доказуемости формулы в исчислении высказываний. Следствие 1. Для того чтобы формулы и были эквивалентны в исчислении высказываний, необходимо и достаточно, чтобы они были эквивалентны в алгебре высказываний. Следствие 2. Формула выводима в исчислении высказываний из системы посылок , тогда и только тогда, когда она выводима из этой системы посылок в алгебре высказываний. Таким образом, можно утверждать, что данные теории - алгебра высказываний и исчисление высказываний, являются адекватными, однако, они существенно отличаются по способу построения. Алгебра высказываний является семантической теорией, в ней все формулы понимаются содержательно, как функции на множестве . Исчисление высказываний, как мы уже говорили, является синтаксической теорией, в ней формулы – это определенные наборы символов, среди которых различаются лишь теоремы и не теоремы. Кроме понятия полноты, названного относительной полнотой, существуют и другие понятия полноты. Определение 3. Непротиворечивая синтаксическая теория называется полной, если из любых двух формул вида и , записанных на языке этой теории, одна является ее теоремой (или, как говорят, средств теории достаточно, чтобы доказать или опровергнуть любое утверждение, сформулированное на языке этой теории). Определение 4. Непротиворечивая синтаксическая теория называется полной в узком смысле, если добавление к ее аксиомам любой недоказуемой в ней формулы приводит к противоречивой теории. Из теоремы 4.1 следует, что исчисление высказываний неполно в смысле определения 3, так как в алгебре высказываний существуют формулы, не являющиеся ни тождественно истинными, ни тождественно ложными. Теорема 4.3. Исчисление высказываний полно в узком смысле. Из теоремы 4.3 следует, что выбор аксиом исчисления высказываний был сделан корректно. Рассмотрим теперь вопрос о разрешимости исчисления высказываний. Синтаксическая теория называется разрешимой, если существует алгоритм, который для любой формулы позволяет сделать вывод, является ли она теоремой этой синтаксической теории. Для того чтобы решить вопрос, доказуема ли в исчислении высказываний формула , достаточно определить (в силу теорем 4.1 и 4.2) является ли она ТИ-высказыванием алгебры высказываний. НЕЧЕТКАЯ И ЛИНГВИСТИЧЕСКАЯ ПЕРЕМЕННЫЕ Понятие нечеткой и лингвистической переменных используется при описании объектов и явлений с помощью нечетких множеств. Нечеткая переменная характеризуется тройкой <, X, A>, где  - наименование переменной, X - универсальное множество (область определения ), A - нечеткое множество на X, описывающее ограничения (т.е.  A(x)) на значения нечеткой переменной . Лингвистической переменной называется набор < ,T,X,G,M>, где  - наименование лингвистической переменной; Т - множество ее значений (терм-множество), представляющих собой наименования нечетких переменных, областью определения каждой из которых является множество X. Множество T называется базовым терм-множеством лингвистической переменной; G - синтаксическая процедура, позволяющая оперировать элементами терм-множества T, в частности, генерировать новые термы (значения). Множество T G(T), где G(T) - множество сгенерированных термов, называется расширенным терм-множеством лингвистической переменной; М - семантическая процедура, позволяющая превратить каждое новое значение лингвистической переменной, образуемое процедурой G, в нечеткую переменную, т.е. сформировать соответствующее нечеткое множество. Замечание. Чтобы избежать большого количества символов • символ  используют как для названия самой переменной, так и для всех ее значений; • пользуются одним и тем же символом для обозначения нечеткого множества и его названия, например терм "молодой", являющийся значением лингвистической переменной  = "возраст", одновременно есть и нечеткое множество М ("молодой"). Присвоение нескольких значений символам предполагает, что контекст позволяет разрешить возможные неопределенности. Пример: Пусть эксперт определяет толщину выпускаемого изделия с помощью понятий "малая толщина", "средняя толщина" и "большая толщина", при этом минимальная толщина равна 10 мм, а максимальная - 80 мм. Формализация такого описания может быть проведена с помощью следующей лингвистической переменной <, T, X, G, M>, где  - толщина изделия; T - {"малая толщина", "средняя толщина", "большая толщина"}; X - [10, 80]; G - процедура образования новых термов с помощью связок "и", "или" и модификаторов типа "очень", "не", "слегка" и др. Например: "малая или средняя толщина", "очень малая толщина" и др.; М - процедура задания на X = [10, 80] нечетких подмножеств А1="малая толщина", А2 = "средняя толщина", А3="большая толщина", а также нечетких множеств для термов из G(T) в соответствии с правилами трансляции нечетких связок и модификаторов "и", "или", "не", "очень", "слегка" и др. операции над нечеткими множествами вида: А  В, А В, , CON А = А2 , DIL А = А0,5 и др. Замечание. Наряду с рассмотренными выше базовыми значениями лингвистической переменной "толщина" (Т={"малая толщина", "средняя толщина", "большая толщина"}) возможны значения, зависящие от области определения Х. В данном случае значения лингвистической переменной "толщина изделия" могут быть определены как "около 20 мм", "около 50 мм", "около 70 мм", т.е. в виде нечетких чисел. Продолжение примера: Функции принадлежности нечетких множеств: "малая толщина" = А1 , "средняя толщина"= А2, " большая толщина"= А3 . Функция принадлежности: нечеткое множество "малая или средняя толщина" = А1А1. Нечеткие числа Нечеткие числа - нечеткие переменные, определенные на числовой оси, т.е. нечеткое число определяется как нечеткое множество А на множестве действительных чисел R с функцией принадлежности A(x)[0,1], где x - действительное число, т.е. xR. Нечеткое число А нормально, если A(x)=1, выпуклое, если для любых xyz выполняется A(x)A(y)A(z). Множество  - уровня нечеткого числа А определяется как А = {x/ A(x)}. Подмножество SAR называется носителем нечеткого числа А, если S = {x/A(x)>0}. Нечеткое число А унимодально, если условие A(x) = 1 справедливо только для одной точки действительной оси. Выпуклое нечеткое число А называется нечетким нулем, если A(0) = (A(x)). Нечеткое число А положительно, если xSA, x>0 и отрицательно, если xSA, x<0. НЕЧЕТКИЕ ВЫСКАЗЫВАНИЯ И НЕЧЕТКИЕ МОДЕЛИ СИСТЕМ Нечеткими высказываниями будем называть высказывания следующего вида: 1. Высказывание < есть '>, где  - наименование лингвистической переменной, ' - ее значение, которому соответствует нечеткое множество на универсальном множестве Х. Например высказывание <давление большое> предполагает, что лингвистической переменной "давление" придается значение "большое", для которого на универсальном множестве Х переменной "давление" определено соответствующее данному значению "большое" нечеткое множество. 2. Высказывание < есть m'>, где m - модификатор, которому соответствуют слова "ОЧЕНЬ", "БОЛЕЕ ИЛИ МЕНЕЕ", "МНОГО БОЛЬШЕ" и др. Например: <давление очень большое>, <скорость много больше средней> и др. 3. Составные высказывания, образованные из высказываний видов 1. и 2. и союзов "И", "ИЛИ", "ЕСЛИ.., ТО...", "ЕСЛИ.., ТО.., ИНАЧЕ". Высказывания на множестве значений фиксированной лингвистической переменной То, что значения фиксированной лингвистической переменной соответствуют нечетким множествам одного и того же универсального множества Х, позволяет отождествлять модификаторы "очень" или "не" с операциями "CON" и "дополнение", а союзы "И", "ИЛИ" с операциями "пересечение" и "объединение" над нечеткими множествами . Для иллюстрации понятия лингвистической переменной мы в качестве примера рассматривали лингвистическую переменную "толщина изделия" с базовым терм-множеством Т = {"малая", "средняя", "большая"}. При этом на Х = [10, 80] мы определили нечеткие множества А1, А2, А3, соответствующие базовым значениям: "малая", "средняя", "большая". В этом случае высказыванию <толщина изделия очень малая> соответствует нечеткое множество CONA = A2; высказыванию <толщина изделия не большая или средняя> - нечеткое множество А2 высказыванию <толщина изделия не малая и не большая> А1. Высказывания <толщина изделия много больше средней> или <толщина изделия близка к средней> требуют использования нечетких отношений R ("много больше,чем") и R ("близко к"), заданных на ХХ. Тогда этим высказываниям будут соответствовать нечеткие множества AR1 и AR2, индуцированные нечеткими отношениями R1 и R2. Случай двух и более лингвистических переменных Пусть <, T, X, G, M> и <, T, Y, G, M> - лингвистические переменные, и высказываниям < есть '>, < есть  '> соответствуют нечеткие множества А и В заданные на X и Y. Составные нечеткие высказывания вида 3, связывающие значения лингвистических переменных  и , можно привести к высказываниям вида 1, введя лингвистическую переменную (, ), значениям которой будут соответствовать нечеткие множества на XY. Напомним, что нечеткие множества А и В, заданные на X и Y, порождают на XY нечеткие множества и , называемые цилиндрическими продолжениями, с функциями принадлежности: (x,y) = A(x) при любом y, (x,y) = B(y) при любом x, где (x,y) XY. Нечеткие множества, соответствующие составным высказываниям < есть ' и  есть '> и < есть ' или  есть '>, определяются по следующим правилам (преобразования к виду 1), справедливым при условии невзаимодействия переменных, т.е. множества X и Y таковы, что их элементы не связаны какой-либо функциональной зависимостью. Правила преобразований нечетких высказываний Правило преобразования конъюнктивной формы Справедливо выражение: < есть ' и  есть '><(, ) есть ('')>. Здесь  - знак подстановки, '' - значение лингвистической переменной (, ), соответствующее исходному высказыванию < есть ' и  есть '>, которому на XY ставится в соответствие нечеткое множество  c функцией принадлежности (x,y) = (x,y)(x,y) = A(x)B(y). Правило преобразования дизъюнктивной формы Справедливо выражение: < есть ' или  есть '><(,) есть ('')>, где значению ('') лингвистической переменной (, ) соответствует нечеткое множество , с функцией принадлежности (x,y) = (x,y)V(x,y) = A(x)VB(y). Замечание 1. Правила справедливы также для переменных вида <, T1, X, G1,M1> и <, T2, Y, G2, M2>, когда в форме значений лингвистических переменных формализованы невзаимодействующие характеристики одного и того же объекта. Например, для построения нечеткого множества высказывания <ночь теплая и очень темная> нужно использовать правило конъюнктивной формы, а для высказывания <ночь теплая или очень темная> - правило дизъюнктивной формы. Замечание 2. Если задана совокупность лингвистических переменных {<i, Ti, Xi, Gi, Mi>}, i = 1, 2, .., n, то любое составное высказывание, полученное из высказываний < есть '> с использованием модификаторов "очень", "не", "более или менее" и др. и связок "и", "или", можно привести к виду < есть '>, где  - составная лингвистическая переменная (1,2,..,n ), ' - ее значение, определяемое (как и функция принадлежности) в соответствии с вышеуказанными правилами. Правило преобразования высказываний импликативной формы Справедливо выражение: <если  есть ', то  есть '> <(, ) есть ('')>, где значению ('') лингвистической переменной (, ) соответствует нечеткое отношение XRY на XY. Функция принадлежности R(x,y) зависит от выбранного способа задания нечеткой импликации. Способы определения нечеткой импликации Будем считать, что заданы универсальные множества X и Y, содержащие конечное число элементов. Под способом определения нечеткой импликации "если А, то В" (где А и В нечеткие множества на X и Y соответственно) будем понимать способ задания нечеткого отношения R на XY, соответствующего данному высказыванию. С целью обоснованного выбора определения нечеткой импликации, японскими математиками Мидзумото, Танака и Фуками было проведено исследование всех известных по литературе определений (плюс предложенные авторами). Рассмотренные определения задавали следующие нечеткие отношения для высказывания "если А, то В": 1. Rm = (AB)(Y) Rm(x,y) = (A(x) B(y)) V (1 - A(x)); 2. Ra = (Y)(XB) Ra(x,y) = 1  (1-A(x) + B(y)); 3. Rc = AB Rc(x,y) = A(x) B(y); 4. Rs = AYXB Rs(x,y) = ; 5. Rg = AYXB Rg(x,y) = ; 6. Rsg = ( AYXB )  ( ) ; 7. Rgg = ( AYXB)  () ; 8. Rgs = ( AYXB)  () ; 9. Rss = ( AYXB)  () ; 10. Rb = (Y)(XB) Rb(x,y) = (1-A(x))  B(y); 11. R = AYXB ; 12. R = AYXB 13. R* = AYXB R*(x,y) = 1 - A(x)+ A(x) B(y); 14. R# = AYXB R#(x,y)=( A(x) B(y)) ((1 - A(x)) (1 - B(y)) (B(y) (1 - A (x)); 15. R = AYXB Правилом вывода являлось композиционное правило вывода с использованием (max-min)-композиции. В качестве значений на входе системы рассматривались: A' = A; A' = "очень А"= А2 , A0,5(x) = A(x)2 ; A' = "более или менее А" = А0,5 A0,5(x)= A(x)0,5; A' = A(x)0,5, (x) = 1 - A (x). Приведем таблицу итогов исследования. В ней символ "0" означает выполнение соответствующей схемы вход-выход, символ "x" - невыполнение. Следствие "неизвестно" (Н) соответствует утверждению: "если x=A, то нельзя получить никакой информации об y". В данной таблице первая графа -"Посылка", вторая -"Следствие". 1 2 Rm Ra Rc Rs Rg Rsg Rgg Rgs Rss Rb R R R* R# R A B x x x x x x x x A2 B2 x x x x x x x x x x x x A2 B x x x x x x x x x x x A0,5 B0,5 x x x x x x x x x A0,5 B x x x x x x x x x x x x x x Н x x x x x x x A B x x x x x x x x x x x Кроме ответа о выполнении соответствующей схемы (0 или х),авторами исследованы явные выражения для функций принадлежности следствий по каждому из вариантов определения нечеткой импликации, на основе чего ими был сформулирован вывод: - Rm и Ra не могут быть использованы; - Rc может использоваться частично; - Rs , Rg , Rsg , Rgg , Rgs , Rss рекомендованы к использованию; - Rb , R, R, R* , R# , R не рекомендованы к использованию. АЛГОРИТМЫ Определение. Алгоритм – это процедура, которая позволяет преобразовывать информацию: • она четко описана • приводит к результату. Точные формулировки алгоритмов возникли в тридцатые годы двадцатого века. Описание любой эффективной процедуры можно найти в терминах машины Тьюринга. Возьмем автомат , образуем , получим, что автомат на ленте работает так: . В середине изображена головка, передвигающаяся по ячейкам и содержащая информацию о состоянии в данный момент. Она считывает содержимое ячейки напротив, берет его в качестве очередной входной буквы, а на его место записывает выходную букву. Обобщим несколько ленту, а именно, будем считать, что двигаться можно не только вправо, но и влево, а также можно стоять на месте (а лента бесконечна в обе стороны). После этого получится машина Тьюринга. Команды будем задавать в следующем виде: , что расшифровывается так: в состоянии подается буква , на выходе получается буква , новое состояние – , обозначает направление движения ( – сдвиг влево, – вправо, – отсутствие сдвига). У каждой машины имеется конечный набор команд. Условимся всегда обозначать начальное состояние как , конечное как (когда получается состояние , машина останавливается; если оно никогда не получается, то машина не останавливается и называется неприменимой к ). Рассмотрим . Эта машина стоит на месте, поэтому заключительного состояния никогда не получится. А вот машина является тождественной функцией: она оставляет букву, которая до ее применения была на исходном месте на ленте, остается на месте и сразу завершает свою работу, переходя в конечное состояние. Удобно рассматривать числовые функции. Препятствием является то, что чисел бесконечно много, а алфавит конечен. В такой ситуации применяют кодировку чисел. Число кодируется массивом длины из единиц, набор как . Рассмотрим машину: и ее действие на массиве . Она сначала дойдет до конца единичек, обнаружив 0, поставит туда 1 и пойдет обратно, пока не найдет 0, расположенный в начале числа, когда и остановится. Таким образом машина превратит массив из 1 в массив из единички, т.е. из кода сделает код : . Если взять два числа и , то в качестве результата получим : (после работы машины количество 1 будет – код числа ). А если взять , то машина поставит одну 1 и сдвинется влево – напишет код нуля, исходя от пустого множества (на ленте оно задается сплошными нулями, нулевой лентой): . Вычислительная сложность алгоритма Вычислительная сложность алгоритма, называемая еще временной сложностью, является одной из важнейших характеристик алгоритма, которая определяет затраты машинного времени на его реализацию. Кроме вычислительной сложности алгоритма анализируется еще и сложность по памяти. Вычислительной сложностью алгоритма (или просто сложностью) назовем количество шагов выполняемых алгоритмом в худшем случае. Она является функцией от размерности задачи, представленной входными данными. Например, для графа, задаваемого списками инцидентности, размерность задачи представляется как пара (n,m). Сложность алгоритма определяется, как функция f, такая, что f (n,m) равно числу шагов алгоритма для произвольного графа с n вершинами и m ребрами. Под шагом алгоритма понимается машинная команда, и при таком определении шага вычислительная сложность зависит от конкретной системы команд и способа трансляции. Нас же будет в дальнейшем интересовать не точная сложность алгоритма, вычисление которой практически невозможно, а асимптотическая сложность, которая определяется скоростью роста числа шагов алгоритма при неограниченном увеличении размерности задачи. Кроме того, вычислительная сложность алгоритма, вычисленная при различных системах команд или способах трансляции, отличаются друг от друга в p раз, где p – вещественная константа, а их скорость роста одинакова. Для сравнения скорости роста двух функций и будем использовать обозначения или . Будем говорить, что функция имеет порядок роста не более, чем функция , что обозначается , тогда и только тогда, когда существуют и , такие, что Будем говорить, что функция имеет порядок роста не менее, чем функция , что обозначается , тогда и только тогда, когда существуют и , такие, что Например, для функции в силу принятых обозначений, можно записать, что или . В общем случае, если - многочлен степени: , то Непосредственно из определения вытекают следующие свойства: ; ; .