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

Вопр. Равносильные преобразования формул



В отличие от табличного задания представление функции формулой не единственно. Например, две различные формулы

x 1V x 2 и (x 1& x 2)

реализуют одну функцию – штрих Шеффера.

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

Равносильность формул A и B будем обозначать следующтм образом: AB.

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

29 вопрос.Осн.равносильности Булевых формул. Коммутативность. Ассоциативность. Дистрибутивность.

1. Коммутативность.

а) A & B  B & A (для конъюнкции);

б) A V BB V A (для дизъюнкции).

2. Ассоциативность.

а) A &(B & C)  (A & C)& C (для конъюнкции);

б) A V(B V C)  (A V B)V C (для дизъюнкции).

3. Дистрибутивность.

а) A &(B V C)  A & B V A & C (для конъюнкции относительно дизъюнкции);

б) A V(B & C)  (A V B)&(A V C) (для дизъюнкции относительно конъюнкции).

30 вопр.Осн.равносильности булевых формул.Закон де-моргана, Идемпотентность

4. Закон де Моргана.

а) (A & B) A V B (отрицание конъюнкции есть дизъюнкция отрицаний);

б) (A V B)  A & B (отрицание дизъюнкции есть конъюнкция отрицаний).

5. Идемпотентность.

а) A & AA (для конъюнкции);

б) A V AA (для дизъюнкции).





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



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