3. Основные направления и понятия символической (математической) логики	39

3.8. Логические отношения между формулами

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

Установить отношения между конкретным числом формул возможно посредством построения для этих формул совместной таблицы истинности.

При установлении логических отношений между формулами учитывается следующее:

1)формулы совместимы по истинности, если в совместной таблице имеется по крайней мере одна строка, в которой каждая формула принимает значение «истина»; формулы несовместимы по истинности, если строка, в которой формулы одновременно истинны, отсутствует;

2)формулы совместимы по ложности, если в совместной таблице имеется по крайней мере одна строка, в которой каждая формула принимает значение «ложь». Формулы несовместимы по ложности, если строка, в которой формулы одновременно ложны, отсутствует.

П р и м е р: построим совместную таблицу истинности для формул p q, q r, p r.

	p		q	r	p q	q r	p r
	È		È	È	È	È	È
	È		È	Ë	È	Ë	È
	È		Ë	È	È	È	È
	È		Ë	Ë	È	È	È
	Ë		È	È	È	È	È
	Ë		È	Ë	È	Ë	Ë
	Ë		Ë	È	Ë	È	Ë
	Ë		Ë	Ë	Ë	È	Ë
Формулы: p q, q r,			p r:

•совместимы по истинности (имеется строка (1, 3, 4, 5), в которой каждая формула принимает значение «И»);

•несовместимы по ложности (отсутствует строка, в которой формулы одновременно ложны);

•p r логически следует из p q и q r (отсутствует строка, в которой p q и q r принимают значение И, а p r – значение Л);

•p q не следует логически из q r и p r (седьмая строка таблицы,

âкоторой q r и p r истинны, а p q ложна);

•q r не следует логически из p q и p r (вторая строка таблицы,

âкоторой p q и p r истинны, а q r ложна).

40I. Пропедевтика: предмет логики. Основные понятия и структура логики

3.9.Виды логических отношений

между формулами

На основе фундаментальных (базисных) логических отношений — совместимости по истинности, совместимости по ложности и логического следования — определяют другие виды отношений по истинности и ложности между формулами. Приведем наиболее употребимые отношения между формулами.

1.Отношение логической эквивалентности. Формулы А и В находятся в отношении эквивалентности, если и только если они совместимы по ложности, из А логически следует В и из В логически следует А. Иными словами, формулы А и В эквивалентны, если всегда принимают одинаковые истинностные значения.

2.Отношение логического подчинения. Формулы А и В находятся в отношении логического подчинения, если и только если они совместимы по истинности, совместимы по ложности, и при этом из А логически следует В, но не наоборот, т.е. формула В логически подчиняется формуле А.

3.Отношение субконтрарности. Формулы А и В находятся в отношении субконтрарности, если и только если они совместимы по истинности, но несовместимы по ложности, и нет логического следования ни от А к В, ни от В к А.

4.Отношение противоречия (контрадикторность). Формулы А и В находятся

âотношении противоречия, если и только если они несовместимы ни по истинности, ни по ложности, и нет логического следования ни в одну сторону.

5.Отношение противоположности (контрарность). Формулы А и В находятся

âотношении противоположности, если и только если они несовместимы по истинности, но совместимы по ложности и нет логического следования ни в одну сторону.

Перечисленные отношения можно проиллюстрировать в виде таблицы.

Эквива-

Подчинение

Субконт-

Противо-

Противопо-

лентность

рарность

речие

ложность

À

Â

À

Â

À

Â

À

Â

À

Â

À

Â

È

È

È

È

È

È

È

È

È

Ë

È

Ë

È

Ë

È

Ë

Ë

È

Ë

È

Ë

È

Ë

È

Ë

Ë

Ë

Ë

Ë

Ë

Ë

Ë

3. Основные направления и понятия символической (математической) логики	41

3.10. Способ приведения формулы к нормальной форме

Приведение формул к КНФ и ДНФ

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

Формула имеет нормальную форму, если она не содержит никаких логи- ческих констант, кроме , , &.

Конъюнктивной нормальной формой (КНФ) формулы F называется равносильная ей формула F ′, представляющая собой конъюнкцию элементарных дизъюнкций. Элементарной называется дизъюнкция, каждый дизъюнкт которой – либо пропозициональная переменная, либо ее отрицание. Согласно закону исключенного третьего (А А) элементарная дизъюнкция является тождественноистинной, если и только если она содержит, по крайней мере, одну пропозициональную переменную со знаком отрицания и без него. Например, следующая элементарная дизъюнкция является тождественно-истинной: (р q p s).

Дизъюнктивной нормальной формой (ДНФ) формулы F называется равносильная ей формула F ′, представляющая собой дизъюнкцию элементарных конъюнкций. Элементарной называется конъюнкция, каждый конъюнкт которой — либо пропозициональная переменная, либо ее отрицание. Согласно закону противоре- чия (А & А) элементарная конъюнкция является тождественно-ложной, если и только если она содержит, по крайней мере, одну пропозициональную переменную со знаком отрицания и без него. Например, следующая элементарная конъюнкция является тождественно-ложной: (q & q & p & s).

Приведение к конъюнктивной нормальной форме (КНФ) и дизъюнктивной нормальной форме (ДНФ) осуществляется посредством замены одних формул другими до получения искомого результата. Такая замена должна производиться с учетом смысла выражения, т.е. формула должна замещаться другой, но равносильной ей.

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

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

42I. Пропедевтика: предмет логики. Основные понятия и структура логики

3.11.Равносильные формулы

Основные исходные эквивалентности

1.А равнозначно А — закон двойного отрицания.

2.(А & В) равнозначно (В & А) — коммутативность конъюнкции.

3.(А В) равнозначно (В А) — коммутативность дизъюнкции.

4.((А & В) & С) равнозначно (А & (В & С)) — ассоциативность конъюнкции.

5.((А В) С) равнозначно (А (В С)) — ассоциативность дизъюнкции.

6.(А (В & С)) равнозначно ((А В) & (А С)) — дистрибутивность дизъюнкции относительно конъюнкции.

7.(А & (В С)) равнозначно ((А & В) (А & С)) — дистрибутивность конъюнкции относительно дизъюнкции.

8.(А & А) равнозначно А — идемпотентность конъюнкции.

9.(А А) равнозначно А — идемпотентность дизъюнкции.

10.(А & В) равнозначно ( А В) — закон де Моргана.

11.(А В) равнозначно ( А & В) — закон де Моргана.

12.(А В) равнозначно (А & В).

13.(А В) равнозначно ( А В).

14.(А & В) равнозначно (А В).

15.(А & В) равнозначно ( А В).

16.(А В) равнозначно ( А & В).

17.(А ≡ В) равнозначно ((А В) & (В А)).

18.(А ≡ В) равнозначно ((А В) & ( В А)).

19.(А ≡ В) равнозначно (( А В) & (А В)).

20.(А ≡ В) равнозначно ((А В) & ( А В)).

21.(А В) равнозначно ( В А).

22.((А В) & ( А В) равнозначно В — закон исключения.

23.(А & (А В)) равнозначно А — закон поглощения.

24.(А (А & В)) равнозначно А — закон поглощения.

25.((А С) & (В С)) равнозначно ((А С) & (В С) & (А В)).

26.((А & С)(В & С)) равнозначно ((А & С) (В & С) (А & В)).

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

схемы тождественно-истинных формул.