Пусть 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 от формулы А можно перейти к формуле В за конечное число действий.

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

Комментарии запрещены.