Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


АЛГЕБРА ЛОГИКИ (СТЫД НЕ ЗНАТЬ ЧТО ЭТО..)



Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями[1]. Чаще всего предполагается, что высказывания могут быть только истинными или ложными, то есть используется так называемая бинарная или двоичная логика

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания.

Высказывания строятся над множеством {B, {\displaystyle \lnot } НЕ , ^ {\displaystyle \land }, V{\displaystyle \lor } , 0, 1}, где B — непустое множество, над элементами которого определены три операции:

{\displaystyle \lnot } НЕ(та самая легендарная инверсия… палка сверху..not – “не” с ингла) отрицание (унарная операция),

{\displaystyle \land }^ (И) конъюнкция (бинарная),

{\displaystyle \lor } v(ИЛИ) дизъюнкция (бинарная),

а логический ноль 0 и логическая единица 1 — константы.

Так же используются названия

Дизъю́нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например {\displaystyle x_{1}\lor \neg x_{2}\lor x_{4}}X V NOT A V B).

Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например {\displaystyle x_{1}\land \neg x_{2}\land x_{4}}F ^ not b ^ K).

Унарная операция отрицания в тексте формул оформляется либо в виде значка перед операндом ({\displaystyle \lnot x}не Х) либо в виде черты над операндом (то же самое просто Х с палкой вверху{\displaystyle {\bar {x}}}), что компактнее, но в целом менее заметно.

СВОЙСТВА ЛОГ ОПЕРАЦИЙ

Переместительный (коммутативный) закон:

· для логического умножения: 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)=A.

 

Обрати внимание!

Двойное отрицание исключает отрицание.

Закон исключённого третьего:

· для логического умножения: A^(НЕ A)=0;

· для логического сложения: A∨(НЕ A)=1.

 

Обрати внимание!

Из двух противоречивых высказываний об одном и том же предмете одно всегда истинно, а второе — ложно, третьего не дано.

Закон повторения:

· для логического умножения: A^A=A;

· для логического сложения: A∨A=A.

Законы операций с 0 и 1:

· для логического умножения: A^0=0; A^1=A;

· для логического сложения: A∨0=A; A∨1=1.

 

Законы общей инверсии:

· для логического умножения: НЕ(A^B) ('не' тут палка над всем выражением… ну вы поняли) = не A ∨ неB;

· для логического сложения: не(A∨B) = не(A^B).

 

Законы алгебры логики могут быть доказаны с помощью таблиц истинности. Докажем распределительный закон для логического сложения:
A∨(B^C)=(A∨B)^(A∨C).

 

A B C B^C A∨(B^C) A∨B A∨C (A∨B)^(A∨C)
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0
0 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1

_________________________________________________________________ДНФ

Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.[1] Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности.

Формулы в ДНФ:

Формулы не в ДНФ:

 

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

импликация

эквивалентность

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

3) Избавиться от знаков двойного отрицания.

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


Пример построения ДНФ

Приведем к ДНФ формулу :

Выразим логические операции → и ↓ через :

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

Используя закон дистрибутивности, приводим формулу к ДНФ:

КНФ

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

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

 

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

 

3) Избавиться от знаков двойного отрицания.

 

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

Пример построения КНФ

 

Приведем к КНФ формулу

Преобразуем формулу F к формуле не содержащей → :

 

 

В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

 

 

По закону дистрибутивности получим КНФ:

 

 

Приемы и способы, применяемые при упрощении логических формул:

Пример 1.


(законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами);

Пример 2.

(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией);

СДНФ И СКНФ

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

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

Среди нормальных форм выделяются совершенные нормальные формы (такие формы, в которых функции записываются единственным образом).


Поделиться:



Последнее изменение этой страницы: 2019-03-22; Просмотров: 271; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.024 с.)
Главная | Случайная страница | Обратная связь