🗊Презентация Математическая логика. (Тема 2)

Математическая логика Тема 2

Основные понятия Логика – это наука о способах доказательства Математическая логика представляет собой формальный математический аппарат, изучающий различные способы доказательства логических рассуждений Высказывание – предложение, относительно которого можно утверждать, истинно оно или ложно. Простейшую из формальных логических теорий называют алгеброй высказываний. Любое логическое рассуждение состоит из высказываний Будем обозначать элементарные высказывания латинскими буквами A, B, C, ... , X, Y, Z ...

Основные понятия Если высказывание истинно (ложно) в любой логической ситуации, то оно называется тождественно истинным (ложным), или логической константой, обозначаемой соответственно И(Л). Высказывания, истинные в одних логических ситуациях и ложные в других, называются переменными высказываниями. Высказыванию, истинному во всех логически возможных случаях, т.е. логической константе, обозначаемой 1 или И, будет соответствовать универсальное множество. Высказыванию, ложному во всех логически возможных случаях, т.е. логической константе, обозначаемой 0 или Л, будет соответствовать пустое множество. Операции алгебры высказываний образуют Булеву алгебру.

Логические операции Конъюнкция двух элементарных высказываний истинна тогда и только тогда, когда оба элементарных высказывания истинны. Обозначается AᴧB, A&B, AB. Читается: «A и B». Дизъюнкция двух элементарных высказываний является ложным высказыванием тогда и только тогда, когда оба высказывания, ее составляющие, ложны. Обозначается АᴠВ. Читается: «А или В». Разделительный смысл союза «или» исключается. Отрицание. Единственная логическая операция, относящаяся к одному высказыванию, – унарная, в отличие от остальных – бинарных. Обозначается: , ⌐А. Читается: «не А».

Логические операции Импликация ложна тогда и только тогда, когда посылка А истинна, а следствие В – ложь. Обозначается А→В. Читается: «если А, то В». При этом А называют посылкой, В – следствием. Двойная импликация является истинностным высказыванием тогда и только тогда, когда высказывания А и В, ее составляющие, принимают одинаковое значение истинности или ложности. Обозначается А↔В (А~В). Читается: «А тогда и только тогда, когда В».

Таблицы истинности логических операций

Пример А – «Этот четырехугольник – параллелограмм» В – «Этот четырехугольник – ромб» Конъюнкция А ᴧ В: «Этот четырехугольник есть параллелограмм и ромб». Дизъюнкция АᴠВ: «Этот четырехугольник есть параллелограмм или ромб». Импликация А→В: «Если этот четырехугольник есть параллелограмм, то он – ромб». Двойная импликация А↔В: «Этот четырехугольник есть параллелограмм тогда и только тогда, когда он – ромб». Отрицание : «Неверно, что этот четырехугольник есть параллелограмм» или «Этот четырехугольник не параллелограмм».

Пример Построим истинностную таблицу сложного высказывания

Формулы алгебры высказываний Отдельно стоящая буква A, B, C, ... , X, Y, Z ... – формула. Если А, В – формулы, то формулами являются и , , АᴧВ, АᴠВ, А→В, А↔В. Других формул нет. Две формулы алгебры высказываний называются равносильными, если на всех одинаковых наборах значений составляющих переменных высказываний они принимают одинаковые значения 1 или 0.

Основные равносильные формулы алгебры высказываний Идемпотентность. а) A ᴠ A = A; б) A ᴧ A = A. Коммутативность. а) A ᴠ B = B ᴠ A; б) A ᴧ B = B ᴧ A. Ассоциативность. а) A ᴠ (B ᴠ C) = (A ᴠ B) ᴠ C; б) A ᴧ (B ᴧ C) = (A ᴧ B) ᴧ C. Дистрибутивность. а) A ᴠ (B ᴧ C) = (A ᴠ B) (A ᴠ C); б) A ᴧ(B ᴠ C) = (A ᴧ B) ᴠ(A ᴧ C). Законы де Моргана. а) ᴧ ; б) .

Основные равносильные формулы алгебры высказываний Законы исключенного третьего и операции с истинными и ложными высказываниями. а) A ᴠ 1 = 1; б) A ᴠ 0 = A; в) A ᴧ 1 = A; г) A ᴧ 0 = 0; д) A ᴧ = 0; е) A ᴠ = 1; ж) = A; з) и)

Основные равносильные формулы алгебры высказываний A→B = A ↔ B = AB ᴠ A ↔ B = ( ᴠ B ) ᴧ (A ) Для того, чтобы убедиться в равносильности двух формул, можно построить их истинностные таблицы и убедиться в их совпадении. Равносильность формул можно установить также, убедившись в совпадении множеств истинности рассматриваемых высказываний. Установить равносильность формул можно также путем их преобразования.

Пример Проверить равносильность двух формул Преобразуем формулы, заменив импликацию равносильной формулой

Пример По обвинению в ограблении перед судом предстали Иванов, Петров, Сидоров. Следствием установлено следующее: 1) Если Иванов не виновен или Петров виновен, то Сидоров виновен. 2) Если Иванов не виновен, то Сидоров не виновен. Виновен ли Иванов?

Решение А – Иванов виновен, В – Петров виновен, С – Сидоров виновен. Установленные факты с помощью логических связок примут вид: 1) 2)

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

Варианты импликации «А достаточное условие для В» выражается формулой: А→В, «А необходимое условие для В» – выражается формулой В→А (конверсия импликации) Достаточное условие А→В может быть выражено формулой , называемой контропозицией Необходимое условие может быть выражено формулой В→А, называемой конверсией контропозиции «А достаточно для В»: А→В=, «А только, если В»; «А необходимо для В»: В→А =. Необходимое и достаточное условие выражается двойной импликацией А ↔ В = ( ᴠ В)(А ᴠ )

Пример Написать формулы следующих высказываний. S1: дифференцируемая функция непрерывна; S2: функция дифференцируема только в случае ее непрерывности; S3: функция непрерывна только в случае ее дифференцируемости; S4: дифференцируемость функции есть необходимое условие ее непрерывности; S5: дифференцируемость функции есть достаточное условие ее непрерывности; S6: дифференцируемость функции есть необходимое и достаточное условие ее непрерывности.

Решение Введем обозначения: А – данная функция дифференцируема, В – данная функция непрерывна. Очевидно: S1=А→В; S2: «А только, если В», т.е. «Если , то », т.е. →=А→В; S3: «В только, если А», т.е.→= В→А ; S4=В→А; S5=А→В; S6=А↔В. Высказывания S1, S2, S5 выражают достаточность А для В, а высказывания S3, S4 – необходимость.

Функции алгебры высказываний Будем рассматривать функции, аргументы (переменные) которых определены на множестве E={0,1}, и такие, что значения эти функции принимают на том же множестве E={0,1}, т.е. при (i=1, 2, …, n). Эти функции будем называть функциями алгебры логики или булевыми функциями. Пусть логическая функция зависит от n аргументов. Различных наборов значений истинности и ложности аргументов существует 2n (строки истинностной таблицы). Число логических функций, зависящих от n аргументов

Основные функции алгебры логики

Основные функции алгебры логики

Основные функции алгебры логики

Истинностные таблицы основных функций логики

Фиктивные и существенные переменные Если переменная xi – фиктивная, то функцию f(x1, ... xi-1, xi, xi+1, ... xn) можно свести к равной ей функции g (x1, ... xi-1, xi+1, ... xn) от (n-1)-ой переменной. Для этого нужно в таблице функции f вычеркнуть все строки, где xi=1 (или xi=0), и столбец, соответствующий переменной xi.

Пример Рассмотрим функцию f(x1, x2), заданную таблицей Содержит ли f(x1, x2) фиктивные переменные? Если да, требуется свести функцию «f» к равной ей функции «g» от одной переменной.

Решение Проверим переменную x1. Рассмотрим наборы σ1=(0, 0), 1=(1, 0); f(σ1)=1, f(1)=0, т.е. f(σ1)≠ f(1). Рассмотрим наборы σ2=(0, 1), 2=(1, 1); f(σ2)=1, f()=0, т.е. f(σ2)≠ f(2). x1 – существенная переменная. Проверим переменную x2. Рассмотрим наборы σ1=(0, 0), 1=(0, 1); f(σ1)=1, f(1)=1, т.е. f(σ1)= f(1). Рассмотрим наборы σ2=(1, 0), 2=(1, 1); f(σ2)=0, f(2)=0, т.е. f(σ2)= f(2). x2 – фиктивная переменная.

Решение Вычеркиваем в таблицы истинности первую и третью строки: (0,0) и (1,0), где x2=0 (или вторую и четвертую: (0,1) (1,1), где x2=1) и столбец, соответствующий фиктивной переменной x2, получим функцию переменной x1: g(x1)= f(x1, x2).

Формулы алгебры логики Пусть B – некоторое подмножество функций из множества E всех логических функций. Каждая функция f(x1,x2, ..., xn) из B называется формулой над B. Пусть f(x1,x2, ..., xn) – функция из B и A1, A2, . . ., An – выражения, являющиеся либо формулами над B, либо символами переменных. Тогда выражение f(A1,A2, ..., An) называется формулой над B. Тавтологией называют всегда истинное логическое выражение, какое бы при этом значение не принимала переменная x ( ). Противоречие, напротив, всегда ложное выражение ( ).

Формулы алгебры логики Каждой формуле над B соответствует функция алгебры логики, причем различным формулам могут соответствовать равные функции, т.е. функции, принимающие равные значения на одинаковых наборах переменных. Формулы U и V над B называются эквивалентными, если соответствующие им функции fU и fV равны, т.е. fU = fV. Запись U=V будет означать, что формулы U и V эквивалентны.

Основные законы логики Буля

Основные законы логики Буля Законы склеивания

Принцип двойственности Булева функция f*(x1,x2, ..., xn) называется двойственной к функции f(x1,x2, ..., xn), если f*(x1,x2, ..., xn) = . Например, функция является двойственной к функции

Принцип двойственности Две булевы функции равны тогда и только тогда, когда равны двойственные им функции.

Пример Пусть , . Доказать, что функции равны, т.е. Построим двойственные функции. Т.к. , то , т.е. .

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

Пример Проиллюстрировать полноту связок на примерах: Преобразуем S1: Преобразуем S2:

Логические отношения Отношение следствия. Говорят, что из высказывания Р следует высказывание Q, если Q истинно всякий раз, когда истинно Р. Из Q не следует P, так как в третьей строке таблицы Q принимает значение 1, в то время как P=0. Но из P следует Q, так как Q принимает значение 1 в первой и четвертой строках таблицы, т. е. тогда, когда истинно P.

Пример Между какими парами высказываний, приведенных ниже, существует отношение следствия? S1: Если прямая перпендикулярна радиусу окружности и проходит через точку пересечения радиуса с окружностью, то она – касательная к окружности. S2: Прямая есть касательная к окружности тогда и только тогда, когда она перпендикулярна к радиусу окружности и проходит через точку пересечения радиуса с окружностью. S3: Если прямая перпендикулярна к радиусу окружности, но не проходит через точку пересечения радиуса с окружностью, то она не является касательной к окружности. S4: Если прямая проходит через точку пересечения радиуса с окружностью, но не является касательной, то прямая не перпендикулярна к радиусу окружности.

Решение Введем элементарные высказывания: A: Прямая перпендикулярна к радиусу окружности. B: Прямая проходит через точку пересечения радиуса с окружностью. C: Прямая – касательная к окружности. Запишем формулы приведенных высказываний.

Таблицы истинности полученных высказываний Из высказывания S2 следует S1 и S4, т. к. при истинностных значениях «1» в первой, четвертой, шестой и восьмой строках высказывания S2 те же значения «1» имеем в указанных строках высказываний S1 и S4 и импликации S2→S1, S2 → S4 становятся тождественно истинными высказываниями S2 → S1≡1, S2 → S4 ≡ 1.

Логические отношения Отношение эквивалентности. Отношение эквивалентности сопряжено со связкой двойной импликацией Р тогда и только тогда, когда Q, т.е. Р ↔Q и имеет место только в том случае, когда Р ↔ Q ≡ 1.

Логические отношения Несовместимость. Два высказывания называются несовместимыми, если не существует логической возможности, при которой оба высказывания были бы одновременно истинными, т.е. при истинном значении одного из них другое обязательно ложно. Это понятие распространяется на любое число высказываний. Чтобы установить совместимость высказываний, нужно построить их истинностные таблицы. Если найдется хотя бы одна строка, в которой все высказывания принимают значения «истинно», данные высказывания будут совместимы, в противном случае – нет. Совместимы те высказывания, когда существует хотя бы одна логическая возможность, когда высказывания совместимы, т.е. P˄Q≠0

Проверка правильности рассуждений Рассуждение – это утверждение того, что некоторое высказывание (заключение) следует из других высказываний (посылок). Рассуждение считается правильным только в том случае, если из конъюнкции посылок следует заключение, т.е. между конъюнкцией посылок и заключением установлено отношение следствия. Если P1, P2, ... , Pn – посылки, а Q – заключение, то рассуждение правильно, если между высказыванием P1 ˄ P2 ˄ ... ˄ Pn и Q установлено отношение следствия. Тогда P1 ˄ P2 ˄... ˄ Pn → Q ≡ 1. При большом числе посылок установить тот факт, что является тавтологией, удобнее с помощью преобразований высказывания к равносильной ему формуле, являющейся тавтологией.

Проверка правильности рассуждений Метод «от противного» заключается в предположении, что заключение ложно, и установление того факта, что при этом конъюнкция P1 ˄ P2 ˄... ˄ Pn – ложна (что имеет место в том случае, если хотя бы одна из посылок Pi ( i = 1, n ) принимает значение «ложно»). Если это выполняется, то рассуждение верно, в противном случае – нет. Таким образом, в случае правильного рассуждения мы убеждаемся в том, что импликация S= P1 ˄ P2 ˄... ˄ Pn → Q ≡ 1, т. к. отсутствует логическая возможность, соответствующая P= P1 ˄ P2 ˄... ˄ Pn =1, Q=0, где импликация P → Q принимает значение ложно.

Пример Проверить правильность следующего рассуждения «Если функция непрерывна на данном интервале и имеет разные знаки на его концах, то внутри интервала функция обращается в нуль. Функция не обращается в нуль внутри данного интервала, но на концах интервала имеет разные знаки. Следовательно, функция разрывна».

Решение Посылки и заключения в данном рассуждении состоят из следующих элементарных высказываний: A – «функция непрерывна на данном интервале», B – «функция имеет разные знаки на концах интервала», C – «функция обращается в нуль внутри данного интервала». Если P1ᴧP2→Q≡1, то данное рассуждение верно.

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

Доказательство методом от противного Предположим, что заключение Q ложно. Покажем, что в этом случае конъюнкция посылок P1ᴧP2 ложна, т. е. P →Q тождественно истинна. В самом деле, если Q= ложно, то A истинно. Пусть P2= ᴧ B истина, тогда B – истинно, – истинно т. е. C – ложно, но в этом случае посылка принимает значение ложно, т.к. P1=А ᴧ В→С принимает значение ложно, так как A ᴧ B=1, а С=0, что и требовалось проверить.

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

Нормальные формы формул алгебры логики Пусть x – булева переменная. Обозначим , где параметр Тогда т.е. Формулы алгебры логики вида: и называются соответственно элементарной конъюнкцией (э.к.) и элементарной дизъюнкцией (э.д.) на множестве булевых переменных Число множителей в э.к. и логических слагаемых в э.д. называется рангом э.к. и э.д. соответственно. - э.к. 4-го ранга; - э.д. 3-го ранга.

Нормальные формы Дизъюнктивной нормальной формой (ДНФ) называется формула, равносильная данной формуле алгебры высказываний и являющаяся произвольной дизъюнкцией различных элементарных конъюнкций, т.е. формулы вида: . Число s называется длиной ДНФ. Конъюнктивной нормальной формой (КНФ) называется формула, равносильная данной формуле алгебры высказываний и являющаяся произвольной конъюнкцией различных элементарных дизъюнкций, т.е. формулы вида: . Число s называется длиной КНФ.

Основные теоремы Элементарная конъюнкция является тождественно ложной тогда и только тогда, когда она содержит пару сомножителей, один из которых является элементарным высказыванием, а другой – его отрицанием. Элементарная сумма является тождественно истинной тогда и только тогда, когда она содержит хотя бы одну пару слагаемых, из которых одно является элементарным высказыванием, а другое – его отрицанием. Формула алгебры высказываний является тождественно истинной тогда и только тогда, когда каждый множитель ее КНФ содержит пару слагаемых, одно из которых является элементарным высказыванием, а другое – его отрицанием. Формула алгебры высказываний является тождественно ложной тогда и только тогда, когда каждое слагаемое (т.е. каждое элементарное произведение) ее ДНФ содержит пару сомножителей, один из которых есть элементарное высказывание, другой – его отрицание. Для каждой булевой функции , отличной от тождественного нуля, существует ДНФ D, такая, что Для каждой булевой функции , отличной от тождественной единицы, существует КНФ K, такая, что

Способы построения ДНФ и КНФ 1 способ (Метод эквивалентных преобразований). Пусть булева функция задана формулой. Алгоритм построения ДНФ и КНФ состоит в следующем: Формулу преобразовать так, чтобы в ней были только операции Добиться с помощью законов де Моргана, чтобы знак отрицания стоял лишь над отдельными переменными. Для построения ДНФ раскрыть скобки по первому дистрибутивному закону: Для построения КНФ раскрыть скобки по второму дистрибутивному закону:

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

Пример 1 Построить ДНФ и КНФ для функции Построим ДНФ Построим КНФ. Применим 2-ой дистрибутивный закон к построенной ДНФ

Пример 2 Построить ДНФ и КНФ для функции Построим таблицу истинности для данной функции Построим ДНФ: Т.к. , то можно получить и другие ДНФ

Пример 2 Построим КНФ: Применяя различные равносильные преобразования, можно получить различные нормальные формы, реализующие одну и ту же функцию

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

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

Пример Для функции f=(11101100) построить несколько ДНФ. Указать кратчайшую и минимальную среди них. Построив таблицу истинности для функции f и применяя преобразования, получим следующие ДНФ: Кратчайшей ДНФ является D5, у нее число логических слагаемых, т.е. длина ДНФ s=2 – наименьшее. Минимальной ДНФ является D5, т.к.

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

Правила построения СДНФ и СКНФ с помощью таблицы истинности Для составления формулы, реализующей СДНФ заданной функции, необходимо в таблице истинности этой функции выбрать наборы (строки) переменных (σ1, σ2, …, σn), на которых данная функция равна единице, т.е. f (σ1, σ2, …, σn)=1; для каждой такой строки необходимо образовать логическое произведение и затем все полученные конъюнкции соединить знаком дизъюнкции. Для составления формулы, реализующей СКНФ заданной функции, необходимо в таблице истинности этой функции выбрать наборы (строки) переменных (σ1, σ2, …, σn), на которых данная функция равна нулю, т.е. f (σ1, σ2, …, σn)=0; для каждой такой строки необходимо образовать логическую сумму и затем все полученные дизъюнкции соединить знаком конъюнкции.

Правила построения СДНФ и СКНФ с помощью равносильных преобразований Для получения СДНФ реализуемой формулой функции f (x1, x2,…, xn)≠0 нужно построить ДНФ этой функции. Затем, если какая-нибудь э.к. ДНФ не содержит переменной xi, заменить ее парой конъюнкций Kj: Замену производить до тех пор, пока каждое слагаемое ДНФ не будет содержать все переменные x1, x2,…, xn (их отрицаний или их самих) Для получения СКНФ реализуемой формулой функции f (x1, x2,…, xn)≠1 нужно построить КНФ этой функции. Затем, если какая-нибудь э.д. КНФ не содержит переменной xi, заменить ее парой дизъюнкций Dj:

Пример Для функции построить СДНФ и СКНФ. Сначала построим ДНФ и КНФ.

Решение В первом слагаемом ДНФ не достает переменной y, во втором – z, в третьем – x. Согласно получим В первом слагаемом КНФ не достает переменной y, во втором – z. Согласно получим

Моделирование алгебры высказываний с помощью релейно-контактных схем Релейно-контактная схема представляет собой устройство из проводников и контактов, связывающих полюса источника тока. Каждому реле можно поставить в соответствие значение 1, если оно находится под током, и 0, если нет. Все замыкающие контакты, подключенные к реле х, будем обозначать x1, ...xn, а размыкающие – , ..., . Всей схеме также можно поставить функцию, принимающую одно из двух значений 1, если схема проводит ток, и 0, если не проводит. Эту логическую функцию называют функцией проводимости.

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

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