Алгебра логики

Элементарные функции алгебры логики
x1 и x2 обозначают названия столбцов, f – символ, обозначающий отображение.
Примечание. Функции f(x1,x2) и f(y1,y2) задают одно и то же отображение, и их таблицы отличаются только названиями столбцов

Пример

Пример

Классификация булевых функций
Нульарные
Унарные
бинарные
n-арные

Нульарные двоичные функции

Унарные функции

Классификация функций одной переменной

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

Классификация функций двух переменных

Классификация функций двух переменных

Классификация функций двух переменных

Классификация функций двух переменных

Стрелка Пирса и Штрих Шеффера

Существенные и несущественные переменные

Примеры

Примеры

Примеры
Необходимо выяснить, какие переменные функции f (x, y, z) = 01011010 являются существенными, а какие несущественными и выразить f (x, y, z) формулой, содержащей только существенные переменные.

Примеры

Представление логической функции. Таблица истинности.

Пример
Необходимо cоставить таблицу истинности
f (x, y) = (x → y) v (y → x).

Пример
Необходимо cоставить таблицу истинности
f (x, y) = (x → y) v (y → x).

Пример

Пример

Сложности на практике

Решение
В 1986 г. Было предложено использовать новые формы представления логических функций
Binary Decision Diagram (BDD)
Бинарные решающие диаграммы
Которые позволяют эффективно представлять логические функции

Представление логической функции. Геометрический способ.
Для функции n – независимых логических переменных – рассматривается единичный n-мерный куб. Вершины куба соответствуют наборам независимых переменных. Каждой вершине приписывают значение функции на соответствующем наборе. На рисунке единичные наборы помечают, например, кружками

Высказывание – повествовательное предложение, о котором можно сказать в данный момент, что оно истинно или ложно, но не то и другое одновременно. Логическим значением высказывания являются «истина» или «ложь».
«Истинность» или «ложность» предложения есть истинностное значение высказывания. Каждому высказыванию сопоставляется переменная, равная 1, если высказывание истинно, и равная 0, если высказывание ложно.
Примеры простых (элементарных) высказываний
«3 – это простое число» – истина; «3,14… – рациональное число» – ложь;
«Юго-восточный берег озера Виви является географическим центром России» – истина;
«Красноярск – столица России» – ложь; «Число 8 делится на 2 и на 4» – истина; «Сумма чисел 2 и 3 равна 8» – ложь.
Пример
1. Если A:= «3 – это простое число», то A = 1. (символ «:=» означает, что переменной, стоящей слева, необходимо присвоить значение высказывания, стоящего справа от символа)
2. Если B:= «Красноярск – столица России», то B = 0.
3. Если С:= «В прямоугольном треугольнике квадрат гипотенузы равен сумме квадратов катетов», то D = 1.
Следующие утверждения не являются высказываниями.
1. a + b = 2.
2. Математика – интересный предмет.
При формальном исследовании сложных текстов понятие «простые высказывания» замещают понятием «пропозициональные переменные», которое обозначают прописными буквами латинского алфавита «A», «B» и т. д.
Логические значения высказываний

Для обозначения грамматических связок вводят символы, которые называют логическими (или пропозициональными) связками.
Обычно рассматривают следующие логические связки:
отрицание (читается «НЕ», обозначается «¬»),
конъюнкция (читается «И», обозначается «∧»),
дизъюнкция (читается «ИЛИ», обозначается «∨»),
импликация (читается «ЕСЛИ… ТО…», обозначается «→»),
эквивалентность (читается «…ТОГДА И ТОЛЬКО ТОГДА, КОГДА…», обозначается «↔»).
Правила построения сложных высказываний в виде последовательности пропозициональных переменных, логических связок и вспомогательных символов определяют возможность формального описания любого текста. При этом высказывания, из которых делают вывод новых высказываний, называют посылками, а получаемое высказывание – заключением.
Для построения сложных пропозициональных высказываний используют вспомогательные символы «(»,«)» – скобки.
Высказывания, которые получаются из простых предложений с помощью грамматических связок «не», «и», «или», «если…, то…», «… тогда и только тогда, когда…» и т. п., называют сложными, или составными.
Множество пропозициональных переменных T = {A, B, C, …} с заданными над ними логическими операциями
F = {¬; ∧; ∨; →; ↔} формируют алгебру высказываний, т. е. Aв =
.
Логические связки

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

Пример

Пример

Пример

Пример
Решение

Повторим вкратце
Алгебра высказываний (Propositional logic)
Высказывание (Proposition) – осмысленное предложение(sentence), о котором можно говорить, что оно истинно (true) или ложно (false), но ни то, ни другое вместе
Основные логические операции АВ:
Конъюнкция (conjunction),
дизъюнкция (disjunction),
импликация (implication),
отрицание/инверсия (negation/inversion)
эквиваленция (equivalence)

Повторим вкратце
Правильно построенная формула (ППФ) АВ (Well-formed formula)
Индуктивное определение
Атом/элементарная формула (высказывательная переменная, логическая константа) – формула АВ
Если G – формула АВ, то ¬G –формула АВ
Если G, H – формулы АВ, то (G ∧ H), (G ∨ H), (G → H), (G ↔H) – формулы АВ
Никаких формул, кроме порожденных применением указанных выше правил, нет, т.е. всякое выражение является формулой алгебры высказываний, если оно получено с помощью пунктов 1–3

Повторим вкратце
Приоритет логических операций
¬, ∧, ∨, →, ↔

Логическое следствие

Логическое следствие

Логическое следствие

Логическое следствие

Алгоритм проверки на логическое следствие
Значение формулы H в строке равно 0?
Строка последняя?
ДА
ДА
ДА
НЕТ
НЕТ
НЕТ

Алгоритм проверки на логическое следствие

Пример 1

Пример 1

Пример 2

Пример 2

Эквивалентные формулы

Эквивалентные формулы

Пример

Пример

Классы логических формул

Классы логических формул

Классы логических формул

Классы логических формул

Формула F называется выполнимой (опровержимой), если существует интерпретация, при которой формула F истинна (ложна). Эта терминология применима также к множествам формул: множество Q формул выполнимо, если существует интерпретация, при которой истинны все формулы Q.
Классы логических формул

Классы логических формул

Классы логических формул

Классы логических формул

Классы логических формул

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

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

Правила упрощения булевых функций
Правила, применяемые для упрощения логических функций

Правила упрощения булевых функций
Алгоритм упрощения булевой функции

Пример

Пример

Нормальные формы формул алгебры логики
Дизъюнктивная нормальная форма
Элементарной конъюнкцией, или конъюнктивным одночленом от переменных A, B, C, … называется конъюнкция каких-либо из этих переменных или их отрицаний.

Нормальные формы формул алгебры логики
Конъюнктивная нормальная форма

Алгоритм приведения к нормальной форме
Шаг 2. Продвинуть отрицание до элементарной формулы (пропозициональной переменной) по законам де Моргана и двойного отрицания.

Пример

Пример
Решение

Пример

Пример
Решение

Пример

Пример

Практический пример

Теорема об эквивалентной формуле с тесными отрицаниями
Для любой ППФ алгебры высказываний существует эквивалентная ей формула с тесными отрицаниями.

Теорема об эквивалентной формуле с тесными отрицаниями
Доказательство:
Доказательство индукцией по числу логических связок, входящих в ППФ A.
n = 0 (A - пропозициональная переменная), теорема верна.
n = 1, A имеет одну из следующих форм: ¬a, (a∧b), (a∨b), (a→b)
В первых трех случаях утверждение теоремы, очевидно, верно.
В последнем случае по эквивалентности (таблицы основных эквивалентностей) имеем (a→b)≡(¬a∨b).

Теорема об эквивалентной формуле с тесными отрицаниями
Доказательство:
n ≤ N,N ∈ ℕ
n = N + 1. ППФ A с N + 1 связкой может быть получена, лишь в виде
A≡¬B, либо A≡(B∧C), либо A≡(B∨C), либо A≡(B→C), где B, C- п.п. имеющие каждая не более N связок и, согласно предположению индукции, имеющие каждая эквивалентную формулу с тесными отрицаниями.
Если A≡(B∧C), либо A≡(B∨C), то утверждение теоремы, очевидно, верно.

Теорема об эквивалентной формуле с тесными отрицаниями
Доказательство:
Если A≡¬B, то возможны следующие случаи:
B≡ ¬D, тогда A=¬¬D≡ D, где Dсодержит не более чем N связок, и, таким образом, утверждение теоремы верно в силу предположения индукции.
B≡(D∧R), тогда A≡ ¬(D∧R)≡(¬D∨ ¬R), где ¬D и ¬R содержат каждая не более чем N связок, и, таким образом, утверждение теоремы верно и в этом случае.
B≡(D∨R), тогда A≡ ¬(D∨R)≡(¬D∧ ¬R), где ¬D и ¬R содержат каждая не более чем N связок, и, таким образом, утверждение теоремы верно и в этом случае.
B≡(D→R), тогда A≡ ¬(D→R)≡(¬D∧¬R), где D и ¬R содержат каждая не более чем N связок, и, таким образом, утверждение теоремы верно и в этом случае.

Теорема об эквивалентной формуле с тесными отрицаниями
Доказательство:
Таким образом, утверждение теоремы доказано в случае A≡¬B. Если, наконец, A≡(B→C), то A≡(¬B∨C), где B и C содержат каждая не более чем N связок. Заметим, что возможен случай, когда ¬B содержит N + 1связку (тогда C - пропозициональная переменная), но, согласно предыдущему рассмотренному случаю, A≡ ¬B имеет эквивалентную формулу с тесными отрицаниями. Формула C имеет эквивалентную формулу с тесными отрицаниями согласно предположению индукции. Следовательно, утверждение теоремы верно и в этом случае. Таким образом, утверждение теоремы доказано полностью.

Теорема о существовании эквивалентной ДНФ
Для любой ППФ АВ существует эквивалентная ей ДНФ.
Доказательство. Согласно теореме об эквивалентной формуле с тесными отрицаниями, для любой ППФ АВ существует эквивалентная ей формула с тесными отрицаниями. Поэтому теорема о существовании эквивалентной ДНФ будет доказана, если будет доказано существование эквивалентной ДНФ для любой формулы с тесными отрицаниями.

Теорема о существовании эквивалентной КНФ
Для любой ППФ АВ существует эквивалентная ей КНФ.

Теорема о виде тождественно ложной ДНФ
Если A – тождественно ложная ДНФ, то любая ее элементарная конъюнкция содержит некоторую пропозициональную переменную вместе с тесным отрицанием этой же пропозициональной переменной

Правила получения тавтологий
Правило заключения (modus ponens)
Правило подстановки

Правило заключения (modus ponens)
Также называется правилом отделения
Теорема: Если формулы F и F→H являются тавтологиями, то формула H так же тавтология.
из ⊨F, и ⊨F→H следует ⊨H

Правило заключения (modus ponens)

Правило подстановки

Алфавит - любое непустое не более чем счетное множество, элементы которого будем называть символами (буквами).
Слово (цепочка) в данном алфавите – произвольная конечная последовательность символов данного алфавита; эта последовательность может не содержать ни одного символа (пустое слово).
Произведением (конкатенацией) слов α и β назовем слово αβ. Если α=βγδ, то βγδ - подслова (подцепочки) слова α.

Алфавит - любое непустое не более чем счетное множество, элементы которого будем называть символами (буквами).
Слово (цепочка) в данном алфавите – произвольная конечная последовательность символов данного алфавита; эта последовательность может не содержать ни одного символа (пустое слово).
Произведением (конкатенацией) слов α и β назовем слово αβ. Если α=βγδ, то βγδ - подслова (подцепочки) слова α.
Результат замены данного вхождения подслова γ в слове βγδ на слово – с лово βδ.
Результат подстановки Saβαв слово α вместо символаaсловаβ- слово, полученное изαодновременной заменой всех вхожденийсимволаaна словоβ.Введем в рассмотрение алфавит, состоящий из следующихтрех множеств символов:

Совершенные нормальные формулы
Основные способы задания булевых функций:
Аналитический
Истинностные таблицы
Как перейти от ТИ к формуле?

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

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

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

Совершенные нормальные формы
Алгоритм преобразования ДНФ к виду СДНФ

Совершенные нормальные формы
Пример

Решение
Совершенные нормальные формы
Пример

Совершенные нормальные формы
Алгоритм преобразования KНФ к виду СKНФ

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

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

Совершенные нормальные формы. Таблицы истинности
Элементарные конъюнкции СДНФ формируются для значений формулы 1. Число элементарных конъюнкций равно числу истинных значений формулы. Пропозициональные переменные, входящие в элементарную конъюнкцию, записываются без изменений, если их значение равно 1, и с логической связкой отрицание – если их значение равно 0.
СДНФ для всякой логической функции единственна. Для тождественно ложной функции СДНФ не существует.
Элементарные дизъюнкции СКНФ формируются для значений формулы 0. Число элементарных дизъюнкций равно числу ложных значений формулы. Пропозициональные переменные, входящие в элементарную дизъюнкцию, записываются без изменений, если их значение равно 0, и с логической связкой отрицание – если их значение равно 1.
СКНФ для всякой логической функции единственна. Для тождественно истинной функции СКНФ не существует.

Совершенные нормальные формы. Таблицы истинности
Необходимо записать СДНФ и СКНФ для функции, заданной таблицей истинности.
Пример:

Совершенные нормальные формы. Таблицы истинности
Необходимо записать СДНФ и СКНФ для функции, заданной таблицей истинности.
Пример:

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

Теорема о виде тождественно ложной ДНФ

Теорема о виде тождественно истинной КНФ

Условия существования с.д.н.ф., с.к.н.ф
Теорема 2. Для любой опровержимой п.п.ф. существует эквивалентная с.к.н.ф. Кроме доказанных теорем 1 и 2, справедливы следуюшие утверждения.
Теорема 3. Для тождественно ложной п.п.ф. не существует эквиваленти ей с.д.н.ф.
Теорема 4. Для тождественно истинной п.п.ф. не существует эквивалентной й с.к.н.ф.

Условия существования с.д.н.ф., с.к.н.ф

Понятие логического высказывания в АВ

Понятие логического высказывания в АВ

Понятие логического высказывания в АВ

Понятие логического высказывания в АВ
Пример

Непротиворечивые (выполнимые) и противоречивые (невыполнимые) множества посылок

Непротиворечивые (выполнимые) и противоречивые (невыполнимые) множества посылок

Установление факта логического следствия из данного множества посылок

Установление факта логического следствия из данного множества посылок

Установление факта логического следствия из данного множества посылок

Основные теоремы о логическом следствии

Основные теоремы о логическом следствии

Основные теоремы о логическом следствии

Основные теоремы о логическом следствии

Основные теоремы о логическом следствии

Основные теоремы о логическом следствии

Основные теоремы о логическом следствии

Основные теоремы о логическом следствии

Основные теоремы о логическом следствии

Основные теоремы о логическом следствии

Основные теоремы о логическом следствии