Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

Формулы φ(x1,..., xn) и ψ(x1,..., xn) называются эквивалентными (φ ~ ψ), если совпадают их таблицы истинности, т. е. совпадают представляемые этими формулами функции fφ(x1,..., xn) и fψ(x1,..., xn)

Пример 1. Проверка на эквивалентность следующих формул и . Построим таблицы истинности формул и ,

x y
       
       
       
       

убеждаемся в том, что ~ . Действительно это отношение ~ является отношением эквивалентности, т. е. оно рефлексивно (φ ~ φ), симметрично (φ ~ ψ) => (ψ ~ φ) и транзитивно (φ ~ ψ, ψ ~ χ => φ ~ χ).

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

1. ~ ; ~ - (ассоциативность и ).

2. ~ ; ~ - (коммутативность и ).

3. ~ φ; ~ φ - (идемпотентность и ).

4. ~ ; ~ - (законы дистрибутивности и ).

5. ~ φ; ~ φ - (законы поглощения и ).

6. ~ ; ~ - (законы де Моргана).

7. ~ φ; - (закон двойного отрицания - инволютивность).

8. ~ ;

9. ~ ;

10. ~ ; ~ ;

11. ~ φψ; ~ φψ.

11. Закон склеивания: .

12. Для функций: конъюнкция, дизъюнкция и сумма по модулю два справедливы следующие тождества:

; ; ;

; ; ;

; ; ;

; ; ;

13. Для функций конъюнкция и дизъюнкция справедливы тожде­ства:

;

;

Для доказательства справедливости любых из приведенных тождеств нужно составить таблицы истинности для булевых функций.

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

Формула φ(x1,..., xn) называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула принимает значение 1 (соответственно 0).

Пример 1. Формула х у является одновременно выполнимой и опровержимой, поскольку 0 0 = 0, а 1 1 = 1.

Формула φ(x1,..., xn) называется тождественно истинной, общезначимой или тавтологией, если эта формула принимает значение 1 при всех наборах значений переменных, т. е. функция f является константой 1.

Пример 2. Формула является тождественно истинной, одновременно выполнимой 0 1 = 1, 1 1 = 1.

Формула φ(x1,..., xn) называется тождественно ложной или противоречием, если эта формула принимает значение 0 при всех наборах значений переменных, т. е. функция f является константой 0.

Пример 3. Формула является тождественно опровержимой, поскольку 0 0 = 0, а 0 1 = 0.

Если φ - тождественно истинная формула, то будем писать |= φ Пример.|= . В противном случае пишем | φ. Пример | .

Очевидным является следующее





Дата публикования: 2014-11-04; Прочитано: 1603 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.008 с)...