§ 1.3. Соответствие между диаграммами и формулами исчисления высказываний

Между диаграммами Венна в исчислении высказываний и формулами исчисления установим соответствие. Предварительно напомним некоторые наиболее часто встречающиеся понятия; подробное изложение исчисления высказываний содержится в литературе по математической логике, например [24, 25].

Определение формул исчисления. Рассматривается алфавит, состоящий из переменных: a₁,...,a_n, логических знаков: , &, ∨, ⊃ и скобок: ( , ).

Формулы определяются следующими правилами:

1. Если а - переменная, то а - формула.

2. Если Φ - формула, то - формула.

3. Если Φ₁ и Φ₂ -формулы, то (Φ₁ & Φ₂), (Φ₁ ∨ Φ₂) и (Φ₁ ⊃ Φ₂) - формулы.

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

С каждой формулой можно связать некоторую функцию, значения которой равны 1 или 0 и которая определена для всевозможных наборов значений аргументов, принимающих также два значения: 1 и 0; 1 обозначает "истину" или "да", 0 - "ложь" или "нет". Функции, связанные только с логическими знаками , &, ∨ и ⊃, называют элементарными. Элементарные функции определяются с помощью таблиц 1.1-1.4.

По этим таблицам для любого заданного набора значений независимых переменных (аргументов) можно найти соответствующее значение функции, заданной некоторой формулой. Легко видеть, что n независимых переменных принимают только 2ⁿ значений. Значения независимых переменных и соответствующие значения функции можно представить в виде таблицы, называемой таблицей истинности. Так как каждому набору значений аргументов сопоставляется только одно из чисел 1 или 0, то число всех различных функций, зависящих от n аргументов, равно 2²ⁿ.

Таблица 1.1

Таблица 1.2

Таблица 1.3

Таблица 1.4

Две формулы Φ₁ и Φ₂, составленные^* из одних и тех же переменных, называются эквивалентными- (записываем Φ₁ = Φ₂), если их таблицы истинности имеют один и тот же столбец значений.

^* (Формула Φ называется составленной из переменных a_i1....,a_ik, если никакая переменная, отличная от a_i1....,a_ik , не входит в Φ. Например (а₃ ∨(a₄⊃a₅)) есть формула, составленная из переменных а₁, а₃, а₄, а₅, a₈.)

Пример 1.6. Формулы Φ((а₂∨a₃) & (a₁⊃a₂), Φ₁((а₁∨а₂)& а₃) эквивалентны, так как их таблицы истинности имеют один и тот же столбец значений (в табл. 1.5 и 1.6 последние столбцы совпадают).

Формулу Φ называют дизъюнктивной нормальной (ДНФ), если Φ есть дизъюнкция конъюнкций, членами которых являются переменные и отрицания переменных.

Если Φ₁ - формула, Φ₂ - дизъюнктивная нормальная формула и формулы Φ₁, Φ₂ эквивалентны, Φ₁ ≡ Φ₂, то Φ₂ называют дизъюнктивной нормальной формой формулы Φ₁.

Дизъюнктивную нормальную формулу Φ называют совершенной (СДНФ), если в каждый ее дизъюнктивный член входят все различные переменные (быть может с отрицанием) формулы Φ, при этом каждая переменная может входить только один раз.

Построение формул по диаграммам Венна. Дана диаграмма D^τ(a₁,..., а_n).

Пусть β₁,..., β_h - все различные ячейки, в которых на D^τ(a₁, ..., а_n) находятся точки. Ячейка β_i есть ãⁱ₁... ãⁱ_n, где

Ячейке β_ш поставим в соответствие формулу^*

^* (Некоторые скобки в формулах опускаем в силу ассоциативности как конъюнкции, так и дизъюнкции.)

где

Λ - обозначение пустого слова j = 1,....,n, i = 1,...,h.

Диаграмме D^τ (a₁,....,a_n) поставим в соответствие СДНФ (Φ₁∨Φ₂∨...∨Φ_h). Формулу, соответствующую диаграмме D^τ, будем обозначать Φ[D^τ].

Пример 1.1 (продолжение). По диаграмме D^τ(a₁, a₂, a₃) (рис. 1.16) построим формулу^*

Φ[D^τ(a₁, a₂, a₃)(a₁ā₂ā₃∨a₁a₂a₃)

^* (В СДНФ будем заменять a_i на ā_i, опускать & и все скобки, кроме внешних.)

Если диаграмма D^τ(a₁,..., а_n) не содержит точек, то в соответствие ей ставим тождественно ложную формулу, например (a₁ &a₁).

Таблица 1.5

Таблица 1.6

Если на диаграмме число ячеек, занятых точками, больше числа пустых ячеек, то для уменьшения логической длины^* удобнее начинать построение с пустых ячеек диаграммы и в соответствие диаграмме D^τ (a₁,..., а_n) ставить формулу (Φ_h+1∨....∨Φ_2ⁿ) не являющуюся ДНФ. При этом используется эквивалентность

^* (Логической длиной формулы называется число всех вхождений логических знаков в эту формулу.)

(1.1)

Для примера возьмем диаграмму D^τ(а₁, а₂, а₃), расположенную справа от знака на рис. 1.21. Логическая длина формулы (Φ₁ ∨... ...∨Φ_h) (а̄₁а̄₂а̄₃ ∨ а̄₁а₂а̄₃ ∨ a₁ā₂ā₃ ∨ а₁а̄₂а₃ ∨ a₁a₂a₃) равна 22, а логическая длина формулы (Φ_h+1 ∨...∨Φ_2ⁿ) (а̄₁а̄₂а̄₃ ∨ а̄₁а₂а₃ ∨ а₁а₂а̄₃) равна 12. Поэтому

Построение диаграмм по данным формулам. Пусть, наоборот, дана не диаграмма Венна, а формула Φ исчисления высказываний, составленная из переменных а₁,...,а_n. Требуется построить диаграмму Венна, соответствующую формуле Φ. Диаграмму, соответствующую данной формуле Φ, будем обозначать D^τ[Φ].

Определение диаграммы, соответствующей данной формуле Φ:

а) каждой переменной а_i формулы Φ поставим в соответствие следующую диаграмму Венна:

Построим символ Венна n переменных. Во всех ячейках i-той фигуры, и только в них, поставим по одной точке. Получим диаграмму, соответствующую переменной а_i, D^τ[a_i];

б) каждому логическому знаку формулы Φ поставим в соответствие операции (одну или две) над диаграммами Венна:

1. Предположим, что Φ₁ - подформула^* формулы Φ и что диаграмма D^τ[Φ₁] построена. Построим диаграмму D^τ[Φ₁].

^* (Понятие "подформулы" данной формулы определяется следующим образом:

Диаграмму D^τ [Φ₁] определим как результат операции отрицания диаграммы D^τ[Φ₁], записываем

(1.2)

где ↔ - знак, обозначающий равенство по определению.

1) если Φ - формула, то Φ является подформулой формулы Φ;

2) если Φ - формула, то подформулы формулы Φ являются подформулами формулы Φ;

3) если Φ₁ и Φ₂ - формулы, то подформулы формул Φ₁ и Φ₂ являются подформулами формул (Φ₁ & Φ₂), (Φ₁ ∨ Φ₂) и (Φ₁ ⊃ Φ₂).)

2. Предположим, что (Φ₁ & Φ₂), (Φ₁v∨vΦ₂) и (Φ₁ ⊃ Φ₂) - подформулы формулы Φ и что диаграммы D^τ[Φ₁] и D^τ[Φ₂] построены. Построим диаграммы D^τ[(Φ₁&Φ₂),D^τ[(Φ₁∨Φ₂)] и D^τ[Φ₁⊃Φ₂]^*:

(1.3)

(1.4)

(1.5)

^* (В дальнейшем в аналогичных выражениях для краткости внешние круглые скобки формул будем опускать.)

Описанный способ определения диаграммы, соответствующей данной формуле Φ, имеет вид индуктивного построения. На первом шаге (пункт "а") строятся диаграммы, соответствующие всем графически различным переменным формулы Φ. Индукция ведется по шагам построения формулы Φ (пункт "б").

Нетрудно доказать, что для любой формулы Φ₁ не являющейся тождественно ложной, формул Φ₂ [D^τ[Φ₁]] есть совершенная дизъюнктивная нормальная форма формулы Φ₁ (при этом формулы пишутся по ячейкам, занятым точками).

Пример 1.6. (продолжение). Построим диаграмму Венна формулы

В данную формулу входят три графически различных переменных a₁, а₂, а₃. Поэтому чертим символ Венна не менее трех переменных. Например, возьмем символ Венна трех переменных (рис. 1.6). Диаграммы Венна будем представлять в линейной форме.

Прежде всего построим диаграммы, соответствующие переменным а₁, а₂ и а₃:

Построим диаграмму, соответствующую a₃.

Построим диаграмму, соответствующую (a₂∨а₃):

Построим диаграмму, соответствующую (a₂∨a₃):

Построим диаграмму, соответствующую (а₁ ⊃ а₂):

Наконец, построим диаграмму формулы Φ:

Построим формулу, соответствующую D^τ[Ф], - (а₁ & а₂ & а₃). Эта формула является совершенной дизъюнктивной нормальной формой исходной формулы Φ и также формулы Φ₁ Z((a₁ ∨ а₂) & а₃) (см. начало этого примера).

В силу установленного соответствия между диаграммами Венна и формулами исчисления высказываний можно говорить о геометрическом (диаграммном) построении исчисления высказываний.

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

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

Проблема разрешения. Нетрудно доказать, что формула Φ универсально общезначима (тождественно истинна) тогда и только тогда, когда в каждой ячейке диаграммы D^τ[Φ] находится по одной точке.

Например, формула Φ((а ⊃(b ⊃ с)) ⊃ ((а & b) ⊃ c)) универсально общезначима, так как D^τ [Φ](⋅,⋅,⋅,⋅,⋅,⋅,⋅,⋅).

Вывод логических следствий.

Определение. Формулу Ψ называют логическим следствием из посылок Φ₁, . . . , Φ_m тогда и только тогда, когда ((Φ₁ & ... & Φ_m) ⊃ Ψ) есть тождественно истинная формула.

Покажем, что формула Ψ будет логическим следствием посылок Φ₁, ..... , Φ_m тогда и только тогда, когда на диаграмме D^τ[Ψ] n переменных, где n - число графически неравных переменных формулы (Φ₁ & ... & Φ_m), во всех ячейках, в которых на диаграмме D^τ[Ф₁ & ... & Φ_m] n переменных есть точки, содержатся точки.

1. Пусть Ψ есть логическое следствие формул Φ₁, . . . , Φ_m. Докажем, что все точки диаграммы D^τ[Φ₁ & ... & Φ_m] перенесены на диаграмму D^τ[Ψ] в те же ячейки.

Предположим, что в ячейках α₁, . . . , α_k на D^τ[Φ₁ & ... & Φ_m] есть точки, а на D^τ[Ψ] - нет. Тогда и на диаграмме D^τ[(Φ₁ ... & Φ^m) ⊃ Ψ] n переменных ячейки α₁, . . . ,α_k пусты, но ((Φ₁ & ... & Φ_m) ⊃ Ψ) есть тождественно истинная формула. Следовательно, если Ψ логическое следствие посылок Φ₁, . . . , Φ_m, то все точки диаграммы D^τ[Φ₁ &. . . . . . & Φ_m] содержатся на диаграмме D^τ[Ψ] в тех же ячейках, что и на D^τ[Φ₁ & ... & Φ₁].

2. Пусть все точки диаграммы [Φ₁ & ... & Φ_m] перенесены на некоторую диаграмму D^τ(n), тогда формула Ψ, соответствующая получившейся из D^τ(n) диаграмме, есть логическое следствие из формул Φ₁, . . . , Φ_m, так как в каждой ячейке диаграммы D^τ[(Φ₁ & ... & Φ_m) ⊃ Ψ] n переменных содержится по одной точке.

Таким образом, для получения логического следствия из посылок Φ₁, . . . , Φ_m, составленного из δ переменных, где δ>n, n - число графически неравных переменных формулы (Φ₁ & . .. ... & Φ_m), надо построить диаграмму D^τ[Φ₁ & . . . . .. . & Φ_m] n переменных, в некоторых из пустых ячеек диаграммы D^τ[Φ₁& ... & Φ_m] поставить по одной точке, написать формулу, соответствующую полученной диаграмме, которая и будет логическим следствием посылок Φ₁, . . . , Φ_m.

Проставляя точки в различных пустых ячейках диаграммы D^τ[Φ₁& ... & Φ_m], будем получать различные логические следствия из Φ₁,. . . , Φ_m. Перебирая все возможные комбинации пустых ячеек диаграммы D^τ[Φ₁& ... &Φ_m], получим все возможные попарно неэквивалентные следствия из Φ₁, . . . , Φ_m, составленные из 6 переменных.

Простые логические следствия. Среди всех логических следствий посылок Φ₁,. . . , Φ_m выделим простые следствия.

Определение. Логическое следствие Ψ посылок Φ₁,....,Φ_m называют простым, если Ψ есть дизъюнкция переменных (может быть с отрицанием), не поглощаемая никаким другим логическим следствием того же вида.

Конъюнкцию всех простых логических следствий посылок Φ₁, ..... .... , Φ_m называют силлогистическим многочленом формулы (Φ₁ & ... & Φ_m).

Пусть а₁, . . . , а_n - все графически неравные переменные формулы (Φ₁ & ... & Φ_m).

1. Если на диаграмме D^τ[Φ₁ & . . . & Φ_m] n переменных находится только одна точка, то ε₁a₁, . . . , ε_na_n - все простые логические следствия посылок Φ₁ . . . , Φ_m (где ε₁ - пустое слово или ; ε_iΛ , если точка лежит в ячейке, принадлежащей фигуре a_i;ε_i если точка лежит в ячейке, принадлежащей дополнению фигуры а_i) и (ε₁a₁ & ε₂a₂ & ... & ε_na_n) - силлогистический многочлен формулы (Φ₁ & ... & Φ_m).

2. Пусть на диаграмме D^τ[Φ₁. . . &Φ_m] находится больше, чем одна точка. Пусть Ψ - логическое следствие посылок Φ₁, . . . , Φ_m.

Если на диаграмме Dτ[Ψ] точки находятся только во всех ячейках фигуры aγβ1β1∪........∪aγβkβk (где γβk - одно из чисел 2, 3: γβi3, если точки лежат во всех ячейках, принадлежащих фигуре aβi; γβi 2, если точки лежат во всех ячейках, принадлежащих дополнению фигуры aβi) формула Ψ эквивалентна формуле (εβ1aβ1∨....∨εβkaβk), где εβkΛ если γβi3; εβi если γβi2, и (εβ1aβ1∨..........∨εβkaβk) - логическое следствие посылок Φ1, . . . , Φm, состоящее из k переменных.

3. Если Ψ₁, Ψ₂ - такие логические следствия посылок Φ₁, . . . , Φ_m, что D^τ[Ψ₁] ∈ D^τ[Ψ₂], то формула Ψ₂ поглощается формулой Ψ₁ где D^τ[Ψ₁], D^τ[Ψ₂] - диаграммы одинакового числа переменных.

4. Если Ψ₁,.......,Ψ_r - все возможные графически различные (т. е. имеющие различные диаграммы Венна n переменных, а следовательно, попарно неэквивалентные) простые логические следствия посылок Φ₁, . . . , Φ_m, то (D^τ[Ψ₁] & . . . &D^τ [Ψ_r]) D^τ[Φ₁&. . .& Φ₂], (Ψ₁ & ... & Ψ_r) - силлогистический многочлен формулы (Φ₁ & ... & Φ_m).

5. Сформулируем способ нахождения простых логических следствий посылок Φ₁, .. . , Φ_m.

Берутся Ψ₁,. . . , Ψ_l - все возможные графически различные простые логические следствия из Φ₁,. . . , Φ_m, составленные из одной переменной.

Если (D^τ[Ψ₁]& . . . & D^τ [Ψ_l]) D^τ [Φ₁ & ... & Φ_m], то (Ψ₁ & ... & Ψ_l) - силлогистический многочлен формулы (Φ₁ &...& Φ_m).

Если (D^τ[Ψ₁] & . . . &D^τ[Ψ_l] отлична от D^τ[Φ₁ & ... & Φ_m] (при этом рассматриваются диаграммы одинакового числа переменных), то берутся Ψ_l+1,. . . , Ψ_l1 - всевозможные графически различные следствия из Φ₁, . . . , Φ_m, составленные из двух переменных, такие, что для любого i (i = 1, ..., l) и для любого j (j = l + 1,.....,l₁) D^τ[Ψ_i] ∉ D^τ[Ψ_j].

Если (D^τ[Ψ₁]& ... & D^τ[Ψ_l1]) D^τ[Φ₁,.....,Φ_m], то (Ψ₁&......&Ψ_l1) - силлогистический многочлен формулы (Φ₁&... &Φ_m).

Если (D^τ[Ψ₁]&...&D^τ [Ψ_l1]) отлична от D^τ [Φ₁&... & Φ_m], то берутся Ψ_l1+1,......,Ψ_l2 - все различные логические следствия из Φ₁,..., Φ_m, составленные из трех переменных, такие, что для любого i (i = 1,..., l₁) и для любого j(j = l₁ + 1,..., l₂) D^τ[Ψ_i]∉D^τ[Ψ_j], и т. д., пока не найдется такое k, что (D^τ[Ψ_i] &... ... & D^τ[Ψ_k])D^τ [Φ₁&... &Φ_m], тогда Ψ₁,...,Ψ_k - силлогистический многочлен формулы (Φ₁&... &Φ_m).

Примеры:

1.7. Пусть D^τ [Φ₁&...&Φ_m](-,⋅,⋅,-).

а) Все логические следствия: (-, ⋅, ⋅,-), (-, ⋅, ⋅, ⋅), (⋅, ⋅, ⋅, -), (⋅, ⋅, ⋅, ⋅).

б) Простые логические следствия: (-,-, ⋅, ⋅) соответствует формула (а₁ ∨ а₂), (⋅,⋅,⋅,-) - (а₁ ∨ a₂)

1.8. Пусть D^τ [Φ₁ &... &Φ_m] (-, -, ⋅,-, -, -,-).

Простые логические следствия:

Отметим, что силлогистический многочлен формулы Φ не является минимальным по логической длине среди конъюнктивных нормальных форм формулы Φ. Так, в последнем примере формула (Φ₁& ... & Φ_m) эквивалентна формуле ((а₁∨a₂) & (а₂∨a₃)& ...... & (a₁∨a₃)), если брать первые три диаграммы; формула (Φ₁&......&Φ_m) (эквивалентна формуле ((a₁ ∨ а₃) & (а₂ ∨ а₃) &( а₁ ∨ а₂)), если брать последние три диаграммы.

Рис. 1.22

Иногда при решении задач нет необходимости рассматривать все 2ⁿ ячеек символа Венна.

Для примера возьмем задачу.

При составлении расписания уроков на определенный день преподаватели высказали пожелания, чтобы их уроки были: по математике - первым или вторым, по истории - первым или третьим, по литературе - вторым или третьим. Можно ли удовлетворить пожелания всех трех учителей?

Пусть М₁ и М₂ - пожелания математика, И₁ и И₃ - пожелания историка, Л₂ и Л₃ - пожелания литератора. Тогда в силу несовместности некоторых из переменных можно ограничиться только 18 ячейками из 64. Соответствующая диаграмма Венна приведена на рис. 1.22. Из диаграммы видно, что пожелания учителей можно удовлетворить, расположив уроки в следующем порядке: математика, литература, история или история, математика, литература.