1.2. Формулы логики высказываний.
Следование и равносильность формул
Пропозициональными переменными называются такие переменные, вместо которых можно подставлять конкретные высказывания.
Понятие формулы логики высказываний определяется следующим (индуктивным) образом:
всякая пропозициональная переменная есть формула;
если F1 и F2 – формулы, то выражения F, (F1F2), (F1F2), (F1F2), (F1F2) тоже являются формулами;
других формул, кроме построенных по правилам двух предыдущих пунктов, нет.
Обычно внешние скобки у формулы не пишут. Подформулой формулы называется всякая ее часть, которая сама является формулой.
Если F(X1, X2,…, Xn) – формула алгебры высказываний, содержащая пропозициональные переменные X1, X2,…, Xn, и A1, A2,…, An – некоторые конкретные высказывания, то, подставив последние в данную формулу вместо соответствующих пропозициональных переменных, получим составное высказывание F(A1, A2,…, An).
Формула F(X1, X2,…, Xn) называется выполнимой (опровержимой), если существует такой набор высказываний A1, A2,…, An, который обращает эту формулу в истинное (ложное) высказывание F(A1, A2,…, An).
Формула называется тождественно истинной, или тавтологией (тождественно ложной, или противоречием), если она обращается в истинное (ложное) высказывание при всех наборах значений переменных. Обозначение тавтологии: ⊨F(X1, X2,…, Xn).
Некоторые тавтологии играют большую роль в логике и поэтому называются законами: законы рефлексивности PP,исключенного третьего ¬PP, закон отрицания противоречия ¬(¬PP), закон двойного отрицания ¬¬PP, законы де-Моргана ¬(PQ)(PQ), ¬(PQ)(PQ) и другие.
Высказывания вместе с определенными для них операциями образуют алгебру высказываний.
На множестве формул логики высказываний можно определить семантические (смысловые) отношения следования и равносильности. Эти отношения играют важную практическую роль при упрощении логических выражений и построении корректных логических выводов.
Формула G(X1, X2,…, Xn) называется логическим следствием формул F1(X1, X2,…, Xn) , …, Fm(X1, X2,…, Xn) , если она обращается в истинное высказывание на всяком наборе значений переменных, для которых в истинное высказывание обращаются все формулы F1 , …,Fm. Это обозначается F1 , …,Fm⊨G.
Две формулы логики высказываний называются равносильными, если на всех одинаковых наборах переменных значения этих формул совпадают. Равносильность формул F и G будем обозначать следующим образом: F G. Для того чтобы установить равносильность формул, можно составить таблицы значений для каждой формулы и сравнить их. Для равносильных формул эти таблицы совпадают. Другой способ установления равносильности формул заключается в использовании некоторых установленных равносильностей формул логики высказываний.
Для любых формул P, Q, R справедливы следующие равносильности:
1. Коммутативность.
а) PQ QP (для конъюнкции);
б) PQ QP (для дизъюнкции).
2. Ассоциативность.
а) P(QR) (PR)R (для конъюнкции);
б) P(QR) (PQ)R (для дизъюнкции).
3. Дистрибутивность.
а) P(QR) (PQ)(PR) (для конъюнкции относительно дизъюнкции);
б) P(QR) (PQ)(PR) (для дизъюнкции относительно конъюнкции).
4. Закон де Моргана.
а) (PQ)PQ (отрицание конъюнкции есть дизъюнкция отрицаний);
б) (PQ) PQ (отрицание дизъюнкции есть конъюнкция отрицаний).
5. Идемпотентность.
а) PP P (для конъюнкции);
б) PP P (для дизъюнкции).
6. Поглощение.
а) P(PQ) P (1-й закон поглощения);
б) P(PQ) P (2-й закон поглощения).
7. Расщепление (склеивание).
а) (PQ)(PQ) P (1-й закон расщепления);
б) (PQ) (PQ) P (2-й закон расщепления).
8. Двойное отрицание.
(P) P.
9. Свойства констант.
а)P1 P; б) P0 0; в)P1 1;
г) P0 P; д) 0 1; е) 1 0.
10. Закон противоречия.
PP 0.
11. Закон исключенного третьего.
PP 1.
12. PQ PQ (PQ).
13. PQ (PQ)(QP) (PQ) (PQ) PQ)(PQ).
Каждая из перечисленных равносильностей может быть доказана с помощью таблиц значений функций, составленных для выражений, стоящих слева и справа от символа “”.
|
Скачать 0.58 Mb.