Дискретная математика Тема:Формальные системы и умозаключения. Логика предикатов Преподаватель Белгородцева Н.А.

Цель лекции – познакомить студентов 1) с формальными системами; 2) с исчислением высказываний; 3) с логикой предикатов; 4) с умозаключениями как формой мышления.

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

Каждый элемент (символ) алфавита принято называть буквой, а совокупность символов – словом или выражением над алфавитом А. Например, слова ладья и лютый_мороз над алфавитом А={а, б, …, ю, я, 0, 1, …, «,», «.», «_»} имеют смысл в русском языке (т.е. принадлежат некоторому выделенному подмножеству F всего множества возможных слов над заданным алфавитом и называются формулами), а слова ълотс и 2йк,щ_ - не имеют смысла: ълотс F.

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

Полнота. Если высказывание x(f), которое сопоставлено формуле f, является истинным в смысле L – языка, с помощью которого интерпретируются формулы (т.е. ν (х(f))= 1 – семантическая характеристика высказывания x(f) ), то считают, что формула f выполняется в интерпретации х. Из аксиом должны следовать истинные высказывания, и, наоборот, для полноты нужно, чтобы все истинные высказывания модели выводились из аксиом. Требования, предъявляемые к формальным системам

Если L – модель формальной теории Т (х: F L), то Т называется полной, если всякому истинному высказыванию из L соответствует теорема из Т, т.е. Независимость. Независимой системой аксиом непротиворечивой формальной теории называется такая система, в которой любая аксиома не может быть выведена на основании всех остальных аксиом этой системы.

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

4.2. Исчисление высказываний Формализуем систему высказываний, придавая им семантическую характеристику. Исчисление высказываний есть формальная теория Т, в которой заданы: алфавит А: связки ¬ (или ¯), ; (дополнительно можно ввести связки или Λ: (, ) – служебные символы, позволяющие определить порядок выполнения связок; D, B, …, A 1, B 1, … - переменные высказывания;

формулы F: переменные есть формулы; если А, В – формулы, то и- формулы; аксиомы Р: Р 1 : Р 2 : Р 3 : правило modus ponens (mp): - правило заключения (от лат. modus – способ; ponens – отделение, заключение).

Составное высказывание В является логическим следствием составных высказываний А 1, А 2, …, А n, если при всех значениях элементарных высказываний, при которых все А 1, А 2, …, А n истинны (в любой интерпретации), будет истинным и высказывание В. Символическая запись логического следования В из А 1, А 2, …, А n имеет вид А 1, А 2, …, А n В и читается так: «Если (выполнены) А 1, А 2, …, А n, то (выполнено) В».

Некоторые теоремы и правила используемые в исчислении высказываний: 1. Ф, А В Ф А В – теорема дедукции. 2. А В А В – следствие из теоремы дедукции (при Ф = Ø, где Ф – список формул, А и В – отдельные формулы ). Правило подстановки ( ms ). Если Е – выводимая формула, содержащая символ А ( т. е. Е ( А )), то выводима формула Е ( В ), полученная из Е заменой всех вхождений А на произвольную формулу В : т. е.

Правило modus ponens (mp). Если набор формул А, В, С является частным случаем набора формул А, А В, то формула С является непосредственно выводимой из формул А и В. Правило - Общие свойства символа - непосредственная выводимость ( - выводимость). При n > 1 А 1, А 2, …, А n А 1 ; А 1, А 2, …, А n А 2 ; …, А 1, А 2, …, А n А n – из набора формул непосредственно выводима каждая.

Если А 1, А 2, …, А n С, то А 1, А 2, …, А n, В 1, …, В m С, т.е. добавление лишних формул при сохранении непротиворечивости не влияет на выводимость. Те же свойства справедливы для выводимости. Правило введения отрицания. и Существуют и другие аксиоматизации исчисления высказываний.

Аксиоматизация исчисления высказываний Гильберт, Аккерман (1938) А: Основные:, ¬; дополнительные: Р: R: modus ponens

Клини (1952) А: ¬, Λ,, Р: R: modus ponens

Россер (1953) А: Основные: ¬, Λ; дополнительные: Р: R: modus ponens

4.2. Логика предикатов О высказывательной форме «Он получил специальность программиста» нельзя сказать, истинна она или ложна, пока не произведена замена местоимения «он» на существительное: «М.А.Иванов стал программистом» (истинно), «Дом стал программистом» (ложно).

В логике предикатов (Р: M n B) используются обозначения: х 0, у 0, z 0 … - значения предметных переменных х, у, z, т.е. предметные постоянные (константы); Если предметы (имена) не содержат дополнительной информации о себе, то они называются собственными (простыми), например, «земля», «студент» и др. p, q, r – переменные высказывания, принимающие два значения: 1 (истина) и 0 (ложь);

Для установления взаимно-однозначного соответствия между n-местной (n2) высказывательной формой и соответствующим предикатом принято устанавливать для предметных переменных определённый порядок. Принято одноместный предикат называть предикатом-свойством, n-местный (для n>1, n N) – предикатом-отношением, 0-местный предикат – высказыванием. Полный прообраз единицы (1) при Р называется множеством истинности Т(Р) предиката Р (от англ. truth – истина): Т(Р) = Р -1 (1) = {x | x M n, P(x) = 1}.

Логические операции (связки) над предикатами Отрицанием предиката называется предикат, также определённый на множестве D и истинный при тех значениях переменной х, при которых ложен, т.е.. T(P) D\T(P) D Множество истинности предиката

Пример. Предикат «х – составное (целое) число», определённый на Z, будет отрицанием предиката Р(х): «х – простое число», т.е., а его областью истинности будет множество всех целых составных чисел (имеющих три и более делителей):

Конъюнкция предикатов иесть новый предикат, определённый на множестве D и истинный при тех значениях переменной х, при которых истинны одновременно оба предиката и, поэтому T(P(x)) T(Q(x)) T(P Λ Q) Множество истинности конъюнкции предикатов

Пример. Система означает конъюнкцию высказываний, а ответ является пересечением Т(Р 1 ) и Т(Р 2 ), т.е. интервалом 58 х Графическое решение системы неравенств

Т(Р Q) = T(P) U T(Q) При решении уравнений (неравенств), левая часть которых есть произведение нескольких множителей, а правая – нуль, они разбиваются на совокупность уравнений (неравенств). Например, х 2 - 8х – 20 = 0 (х - 10)( х + 2) = 0 х – 10 = 0 (Р 1 ) или х + 2 = 0 (Р 2 ). T(P)T(Q) Т(Р v Q) Множество истинности дизъюнкции предикатов

В соответствии с формулой алгебры логики имеем и Т(Р) Т(Q) Т(PQ) D Множество истинности импликации предикатов

Следование Пример 1. Из двух высказывательных форм – уравнений (х - 2)(х - 3) = 0 (Q 1 ) и х – 3 = 0 (Q 2 ) – из х – 3 = 0 следует, что (х - 2)(х - 3) = 0, т.е. верна запись Q 2 Q 1, потому что T(Q 2 ) T(Q 1 ). Пример 2. В случае D(Q)=N, Q 1 : «х 9», Q 2 : «8 х < 12», Т(Q 2 ) = {8, 9, 10, 11}, а T(Q 1 ) = {9, 10, 11, 12, 13, 14, …}, отношение T(Q 2 ) T(Q 1 ) не выполняется, поскольку 8 T(Q 1 ), следовательно, из Q 2 не следует Q 1..

Кванторы Для количественных характеристик обычно используют понятия «все», «некоторые», «существуют» и др., которые называют кванторами (от лат. quantum – сколько). Запишем с помощью формул логики предикатов утверждение: «Для лечения любого известного компьютерного вируса имеются программы. Существуют новые (неизвестные) компьютерные вирусы, для лечения которых программы ещё не разработаны».

Если обозначить А(х) – «известен компьютерный вирус х», В(х) – «для лечения вируса х существует программа», то с помощью логических связок и кванторов получим формулы: - против вируса х нет программы; - любой вирус известен; - существуют новые (неизвестные) вирусы; - если вирус давно известен, то имеется программа для его лечения; - существуют (появились) новые вирусы, для лечения которых программы ещё не разработаны.

Примеры высказываний. «Все металлы (М) – плавятся (П). Цинк (Ц) – металл. Значит, цинк плавится». «Все студенты (С) проходят практику (П). Некоторые студенты работают в фирме (Ф), значит, некоторые работающие в фирме студенты – проходят практику».

Эквиваленция Для эквиваленции справедливо: Две высказывательные формы Q 1 и Q 2 истинны или ложны (Q 1 Q 2 ) одновременно с высказыванием

Квантификация многоместных высказывательных форм В процессе квантификации высказывательной формы Q(x 1, x 2, x i, …, x n ) по переменной x i эта i-я переменная связывается одним из кванторов, а n-местная высказывательная форма превраща- ется в (n-1)-местную. Пример. Произведём квантификацию по переменной у («навесим» квантор общности) двухместной высказывательной формы х–у

Если кванторы одноимённы (1 – 4), то их порядок не играет роли и полученные высказывания эквивалентны: 1)2) 3) 4) Если кванторы разноимённы (5 – 6), то их порядок в полученном высказывании принципиально важен: 5)6) 7) 8)

Правила вывода исчисления предикатов: Правило заключения (modus ponens) – правило, аналогичное тому, которое введено в исчислении высказываний. Правило обобщения ( -введения, ug-правило) R 2 : где G(x) содержит свободные вхождения х, тогда как F не содержит свободных х. Правило -введения (eg-правило) R 3 : Правило -удаления, или es-правило (правило выбора):

Свойства отношения классификации Высказывательной форме «5х

Если на множестве U заданы два свойства Р и Q, то появляется классификация множества U, которая с помощью логических операций записывается в виде: Во всех n-местных предикатах (n 2) устанавливаются некоторые отношения между переменными.

Отрицания в исчислении предикатов Для построения отрицания высказываний, содержащих квантор общности (суще- ствования ), достаточно заменить его на другой квантор существования (общности ) и взять отрицание выражения, на которое этот квантор был «навешан». Для сложных высказываний, состоящих из простых, разделённых операциями конъюнкции и дизъюнкции, отрицание строится следующим образом: нужно все кванторы заменить на, и наоборот; все связки и ( ) заменить на или ( ), и наоборот; взять отрицание утверждения.

Примеры. 1.Заявленный концерт струнного квартета состоится (К), если все исполнители (M i ) будут здоровы (Н – множество здоровых людей) и помещение будет соответствовать проти- вопожарным нормам (событие ).

Заявленный концерт симфонического оркестра состоится (К), если будет здоров дирижёр (D), все исполнители (M i ) (80 чел.) будут здоровы (Н – множество здоровых людей) и помещение будет соответствовать противопожарным нормам (событие ), но если заболеет не более 7 чел., то им есть замена (S i ).

4.1. Умозаключения как форма мышления. Взяв за основу истинные суждения (посылки), мы делаем выводы (умозаключения) о тех понятиях, которые фигурировали в суждениях. Связь между ними наглядно можно представить в виде схемы. Реальный мир Язык Мышление А В С Предметы Знания о предметах Взаимосвязи предметов Слова Предложения Связи между предложениями АיАי ВיВי СיСי Понятия Суждения Умозаключения Аיי Вיי Сיי

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

Непосредственные умозаключения по логическому квадрату Изобразим классификацию суждений по количеству и качеству в виде логического квадрата. Противоположность Подчинение АЕ О J A – общеутвердительные, Е – общеотрицательные, J – частно утвердительные, О – частно отрицательные

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

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

А: «Все местоимения - сказуемые» (л), но О: «Некоторые местоимения не являются сказуемыми» (и), А л О и. Е: «Ни одна окружность не является многоугольником» (и), но J: «Некоторые окружности являются многоугольниками» (л), Е и J л. А: «Все союзы - сказуемые» (л), Е: «Ни один союз не является сказуемым» (и),.

Суждение «Ни один воспитанный человек не совершает аморальных поступков» является общеотрицательным суждением (Е). «Все воспитанные люди совершают аморальные поступки (А)». Это суждение ложное, значит, истинно исходное (отношение противоположности). Соответствующее частноотрицательное суждение О: «Некоторые воспитанные люди не совершают аморальных поступков» - истинное, значит, исходное тоже истинное Е О (отношение подчинения).

Классифицируем непосредственные умозак- лючения в зависимости от правил выводов. Превращения Формула: или Правила выводов: S сохраняется; Р – противоречивое; Связка – противоположная; А Е, Е А, J О, О J – перенос «не» со связки на предикат, и наоборот Противопоказания: нет

Примеры Общеутвердительные А: Все металлы – проводники электричества. Ни один металл не является неэлектро- проводным. Общеотрицательные Е: Ни один хищник не является пернатым. Все хищники являются не пернатыми.

Частноутвердительные J: Некоторые вещества – проводники. Некоторые вещества не являются не проводниками (диэлектриками). Частноотрицательные О: Некоторые подлежащие не являются существительными. Некоторые подлежащие являются не существительными

Обращения Формула: или Правила выводов: S, P сохраняются; Связка все сохраняется, если V S = V P, Связка, если V S < V P Противопоказания: Не выполняется для О

Примеры Общеутвердительные А: Все квадраты – ромбы. Некоторые ромбы – квадраты. Все квадраты – равносторонние прямоугольники. Все равносторонние прямоугольники – квадраты. Общеотрицательные Е: Ни один кит не является парнокопытным. Ни одно парнокопытное не является китом. Частноутвердительные J: Некоторые поэты – гениальные. Некоторые гениальные люди – поэты.

Противопоставления предикату Формула: или Правила выводов: Превращаем Обращаем Противопоказания: Не выполняется для J

Примеры Общеутвердительные А: Все директора являются руководителями предприятия. Ни один не руководитель предприятия не является директором. Все львы – хищники. Некоторые нехищники – не львы.

Общеотрицательные Е: Ни один ядовитый гриб не является съедобным. Все несъедобные грибы являются ядовитыми. Частноотрицательные О: Некоторые высказывания не являются верными суждениями. Некоторые ложные суждения являются высказываниями.