Формулы логики высказываний

Основная задача логики высказываний состоит в изучении логических форм составных высказываний с помощью логичес­ких операций.

Понятие логической формы составного высказывания уточня­ется с помощью вводимого понятия формулы логики высказываний.

Понятие формул логики высказываний определяется следующим образом:

1.           Элементарные формулы – атомы – являются формулами логики высказываний.

2.           Если  A, B – формулы, то -A, (A/\B), (AVB), (A→B),  (AВ) также являются формулами логики высказываний.

3.           только те выражения являются формулами логики высказываний, для которых это следует из 1, 2.

Согласно определения, всякая формула либо атом, ли­бо образуется из атомов в результате применения 2.

Число скобок в формулах можно уменьшить, если опустить внешнюю пару скобок и упорядочить знаки логических опера­ций по старшинству:  , →, V, /\, -.

Знак  имеет самую большую область действия, знак -  самую маленькую.

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

Например, формула (A V –A) всегда тождественно истинна.

Определение. Формулы логики, принимающие всегда ложное значение, называются тождественно ложными (или противоречиями).

Например, формула(A /\ –A)   - противоречие.

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

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

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

Запись Р=(трижды)Q означает, что формулы Р и Q равносильны.

17 Равносильность формул.

Основные равносильности булевых формул.

Для любых формул A, B, C справедливы следующие равносильности:

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

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

б) AVB  BVA (для дизъюнкции).

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

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

б) AV(BVC)  (AVB)VC (для дизъюнкции).

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

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

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

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

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

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

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

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

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

6. Поглощение.

а) A&(AVB)  A (1–й закон поглощения);

б) AVA&B  A (2–й закон поглощения).

7. Расщепление (склеивание).

а) A&B V A&(B)  A (1–й закон расщепления);

б) (AVB) & (AVB)  A (2–й закон расщепления).

8. Двойное отрицание.

(A)  A.

9. Свойства констант.

а) A&1  A;

б) A&0  0;

в) AV1  1;

г) AV0  A;

д) 0 1;

е) 1 0.

10. Закон противоречия.

A&A  0.

11. Закон “исключенного третьего”.

AVA  1.