Алгебра высказываний

1)Высказывания, операции над высказываниями.

Высказывание - связное повествовательное предложение о котором можно сказать, что оно ложно или истинно. Высказывания равносильны если они имеют одинаковые истинностные значения.

Логические операции над высказыванием.

Отрицание  — унарная операция над суждениями, результатом которой является суждение (в известном смысле) «противоположное» исходному. Обозначается знаком ¬ перед или чертой над суждением. Синоним: логическое "НЕ".

Конъюнкция /\ — логическая операция, по своему применению максимально приближённая к союзу "и". Синонимы: логическое "И", логическое умножение, иногда просто "И". Конъюнкцией к высказываниям а и в называется высказывание истинное в том единственном случае когда истины оба высказывания.

Дизъюнкция \/ — логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу». Синонимы: логическое «ИЛИ», включающее «ИЛИ», логическое сложение, иногда просто «ИЛИ». Дизъюнкцией называется высказывание ложное в том единственном случае когда ложны оба исходных высказываний.

Импликация -> -логическая операция, по своему применению максимально приближённая к высказыванию если а, то в. Импликация двух высказываний называется высказывание ложное в том единственном случае когда а(посылка) истино, а в(заключение) ложно.

Эквиваленция ~ - логическая операция, по своему применению максимально приближённая к высказыванию а эквивалентно(равносильно) в. Эквиваленцией называется высказывание истинным, когда оба высказывания принимают одинаковые истинностные значения.

2)Формулы алгебры высказываний.

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

Элементарные высказывания, символы логических переменных- формулы. Если F1 и F2 – формулы алгебры высказываний, то , (F1\/ F2), (F1/\ F2), (F1~F2), (F1->F2) – формулы алгебры высказываний. Других формул алгебры высказываний нет.

Теорема о фиксации значений в формуле.

Если F(x1,x2,..xn)-формула алгебры высказываний, где х1, х2,…хn- высказывательные переменные формулы, то при фиксации значений всех высказывательных переменных формула алгебры высказываний превращается в высказывание.

Теорема о подстановке формул в формулу.

Если F и f1 –формулы алгебры высказываний, то (f|yi<-fi)(x1,x2..xn)-формула алгебры высказываний. При этом говорят, что она получена из формул F подстановкой формул fi, вместо ее переменных.

Теорема о равносильной подстановке.

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

3) Принцип двойственности.

Пусть f(x1,x2…xn) –формула алгебры высказываний. Двойственной к ней называется формула f*(x1,x2…xn) определенную следующим: f*(x1,x2…xn)=! f(!x1,!x2…!xn)

Закон двойственности.

Формулы f1(x1,x2…xn) и f2(x1,x2…xn) равносильны тогда и только тогда когда равносильны f1*(x1,x2…xn) и f2*(x1,x2…xn)

Принцип двойственности для булевых формул

Двойственная к булевой формуле может быть получена заменой констант 0 на 1, 1 на 0, & на V, V на & и сохранения структуры формулы (т.е. соответствующего порядка действий).