Студопедия Главная Случайная страница Задать вопрос

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Эквивалентные формулы алгебры высказываний





Как показано в примере 1, различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие эквивалентности формул.

Формулы φ и ψ АВ называются эквивалентными (обозначается φ ≡ ψ), если φ ψ или ψ , т.е. совпадают их таблицы истинности.

Примαр 7. Построив таблицы истинности формул x→y и y→x, убеждаемся, что (х→y) ≡ (y→x).

Легко видеть, что отношение ≡ является отношением эк­вивалентности на множестве формул АВ, т. е. оно рефлексивно (φ≡φ), симметрично (если φ≡ψ, то ψ≡φ), транзитивно (если φ≡ψ и ψ≡χ, то φ≡ χ), где φ,ψ,χ – произвольные формулы АВ.

Отметим основные эквивалентности между формулами АВ:

1) φ∧ φ≡φ, φ∨ φ≡φ (законы идемпотентности);

2) φ∧ ψ≡ψ∧ φ, φ∨ ψ≡ψ∨ φ (законы коммутативности);

3) (φ∧ψ)∧χ≡φ∧(ψ∧χ), (φ∨ψ)∨χ≡φ∨(ψ∨χ) (законы ассоциативности);

4) φ∧(ψ∨χ)≡(φ∧ψ)∨(φ∧χ), φ∨(ψ∧χ)≡(φ∨ψ)∧(φ∨χ) (законы дистрибутивности)

5) (φ∧ψ)≡φ∨ψ, (φ∨ψ)≡φ∧ψ (законы де Моргана);

6) φ≡φ (закон двойного отрицания);

7) φ→ψ≡φ∨ψ;

8) φ∧(φ∨ψ)≡φ, φ∨(φ∧ψ)≡φ (законы поглощения);

9) φ∨(φ∧ψ)≡φ∨ψ, φ∨(φ∧ψ)≡φ∨ψ;

10) φ∧(φ∨ψ)≡φ∧ψ, φ∧(φ∨ψ)≡φ∧ψ.

К перечисленным ранее соглашениям, пользуясь законами ассоциативности, добавляем следующее: в формулах вида (φ∧ψ)∧χ, φ∧(ψ∧χ), (φ∨ψ)∨χ и φ∨(ψ∨χ) скобки можно опускать.

Утверждение 1. Если формула φ1 тождественно истинна, φ0тождественно ложна, то для любых формул φ и ψ справедливы следующие эквивалентности:

1) φ∧ φ1≡φ; φ∨ φ0≡φ;

2) φ∧φ0≡φ0; φ∨φ1≡φ1;

3) φ∧φ≡φ0; φφ≡φ1.

 






Дата добавления: 2014-11-10; просмотров: 564. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.025 сек.) русская версия | украинская версия