Образовательный блог – всё для учебы

Пусть A₁, A₂ – есть две формулы, x₁, x₂,…,x_n – есть полный список или множество их переменных. Формулы A₁, A₂ – называются равносильными или эквивалентными ?, если для любого набора значений аргументов x₁, x₂,…,x_n, они принимают одинаковые значения.

Замечание: В инженерной практике наиболее распространены представления функций формулами, построенными с помощью конъюнкции, дизъюнкции, отрицания и констант 0,1 т.е. формулами над F={x&y, x?y,¬x,0, 1}, такие формы называются Булевыми. Иногда в F включают импликацию. Примем соглашение об опускании скобок в соответствии со следующими приоритетами:
Пусть А,В,С – некоторые булевы формулы. Тогда справедливы следующие свойства:
1) A&A = A, A?A = A – идемпотентность.
2) A&B = B&A, A?B = B?A – коммуттативность
3) A&(B&C) = (A&B)&C, A?(B?C) = (A?B)?C – ассоциотивность
4) A&(A?B) = A, A?A&B = A – поглошение.
5) A&(B?C) = A&B ?A&C, A?B&C = (A?B)&(A?C) – дистрибутивность
6) ¬¬A = A – инволюция
7) Свойство констант: A&1 = A, A&0 = 0, A?1 = 1, A?0 = A
8) Закон исключения третьего и закон противоречия A?¬A = 1, A&¬A = 0
9) Правило де Моргана ¬(A&B) = ¬A ? ¬B, ¬(A?B) = ¬A & ¬B
Иногда к ним добавляют связь импликации и дизъюнкции
10) A?B = ¬A?B
Правило подстановки.

Теорема: Если А и В – булевы формулы и А = В, то с помощью булевых равенств 1-10 от формулы А можно перейти к формуле В за конечное число действий.

Замечание: Эта Теорема используется при упрощении формул.

1. Булевы решетки и булевы алгебры
2. Множества и операции над ними
3. Алгебра логики : правила построения и преобразования логических выражений
4. Функции и отношения, их свойства
5. Параллельное выполнение операций в БД
6. Описание целочисленных, вещественных, логических данных и операции над ними в Pascal
7. Линейные рекуррентные уравнения(ЛРУ) однородные и неоднородные с переменными коэффициентами
8. Класс самодвойственных функций и его замкнутость относительно суперпозиции. Критерий самодвойственности. Лемма о несамодвойственной функции.
9. Решетки
10. Оценки в случае непрерывного времени
11. Суперпозиция функций. Функционально замкнутые классы
12. СДНФ и СКНФ
13. Класс линейных функций и его замкнутость относительно суперпозиции
14. Верхняя и нижняя оценки для хроматического числа. Внутренне и внешне устойчивые множества вершин графа
15. Обзор логических и физических моделей
16. Теорема Поста о функциональной полноте
17. Раскрашивание планарных графов. Теорема о пяти красках. Теорема о четырех красках