ФОРМУЛОЙ АВ называется выражение, составленное по определенным правилам из пропозиционных переменных, логических связок и скобок. ФОРМУЛА: 1)пропозиционная переменная - формула 2)А - формула => отрицание А - тоже формула 3) А иВ - формулы => (A&B), (A\/B), (A->B) - тоже формулы.
РАВНОСИЛЬНОСТЬ ФОРМУЛ: a(альфа) и b(бета) - формулы. a(X1, X2, X3, ..., Xn) = b(X1, X2, X3, ..., Xn) равносильны при любых значениях X1, X2, X3, ..., Xn, где X1, X2, X3, ..., Xn - совокупность всех перменных, входящих в a и b, формулы a и b принимают одинаковые значения.
Важнейшие примеры равносильных формул: 1)A=A закон тождества 2)A&(not A)=0 закон непротиворечия 3)A\/(not A)=1 закон исключенного третьего 4)A=(not(not A)) закон двойного отрицания 5) A\/A=A, A&A=A законы идемпотентности 6)A\/B=B\/A, A&B=B&A законы коммутативности 7)A\/(B\/C)=(A\/B)\/C), A&(B&C)=(A&B)&C законы ассоциативности 8)A&(B\/C)=(A&B)\/(A&C), A\/(B&C)=(A\/B)&(A\/C) законы дистрибутивности 9)A\/(A&B)=A, A&(A\/B)=A законы поглощения 10)(not (A\/B))=(not A)&(not B), (not (A&B))=(not A)\/(not B) законы де Моргана. Сюда же можно добавить список логических констант: 11)(not 0)=1, (not 1)=0 отрицание лжи, отрицание истины 12)A\/0=A, A\/1=1 прибавление логической константы 0, прибавление логической константы 1 13) A&0=0, A&1=A умножение на логическую константу 0, умножение на логическую константу 1 14)A->B=(not A)\/B. 15)X\/((not X)&Y)=X\/Y. 16)(not X)\/X&Y=(not X)\/Y. 17)X&((not X)\/Y)=X&Y 18)(not X)&(X\/Y)=(not X)&Y. Система элементов, на которой определены действия сложения, умнождения и отрицания, удовлетворяющие этим формулам называется АЛГЕБРОЙ БУЛЯ.
