§4 Равносильность формул алгебры высказываний.
Две формулы алгебры высказываний F(X1, X2, …, Xn) и G(X1,X2,…, Xn) называются равносильными, если для любых наборов значений переменных X1, X2, …, Xn они принимают одинаковые логические значения. Т.е. равносильные формулы имеют одинаковые таблицы истинности. В этом случае будем писать: F(X1 , X2, …, Xn)G(X1, X2, …, Xn) и читать: «Формула F(X1, X2, …, Xn) равносильна формуле G(X1, X2, …, Xn)».
Из определения следует, что если F(X1, X2, …, Xn) есть тавтология, то F(X1, X2, …, Xn)1, и если F(X1, X2, …, Xn) есть противоречие, то F(X1, X2, …, Xn)0.
Понятия “равносильность” и “тавтология” связаны между собой следующим образом.
Теорема1: FG тогда и только тогда, когда ╞FG.
Перечислим основные равносильности, где P, Q, R есть любые формулы алгебры высказываний:
PP1, PP0;
P0P, P11;
P0P, P1P;
PP;
PQQP;
PQQP;
(PQ)RP(QR);
(PQ)RP(QR);
P(QR)(PQ)(PR);
P(QR)(PQ)(PR);
PPP;
PPP;
P(QP)P;
P(QP)P;
P→QPQ;
PQ(P→Q)(Q→P);
PQ(PQ)(PQ);
(PQ)PQ;
(PQ)PQ;
A→BC(A→B)(A→C);
AB→CA→(B→C);
A→BB→A;
- Хакасский государственный университет им. Н.Ф.Катанова математическая логика
- Содержание
- Литература.
- Введение.
- Алгебра высказываний.
- §1. Высказывания и операции над ними.
- Упражнения.
- §2. Формулы алгебры высказываний. Виды формул.
- Упражнения.
- §3 Логическое следствие
- Основные методы установления верности логического следствия:
- Упражнения
- §4 Равносильность формул алгебры высказываний.
- Упражнения
- §5 Нормальные формы для формул алгебры высказываний.
- Отыскание нормальных форм Упражнения.
- Применение нормальных форм.
- Нахождение следствий из посылок.
- Нахождение посылок для данных следствий.
- § 6. Булевы функции (функции алгебры логики).
- Классы булевых функций.
- Упражнения.
- §7. Алгебра логики и релейно-контактные схемы.
- Анализ релейно-контактных схем. Упражнения.
- Синтез релейно-контактных схем.
- §8. Особые методы минимизации.
- Графический метод.
- М атрица Карно.
- Метод неопределенных коэффициентов.
- М етод минимизирующих карт.
- М етод Квайна.
- Упражнения.
- Примерные варианты контрольных работ.