§ 7. Проблема установления вида формул алгебры высказываний.

Табличный способ установления вида формул алгебры высказываний при числе переменных n5 является громоздким, поэтому в математической логике был разработан другой способ установления вида формул алгебры высказываний, основанный на следующих двух теоремах - критериях.

Критерий 1. Формула алгебры высказываний F(x₁, x₂, ..., x_n) тогда будет ТИ, когда каждая дизъюнкция ее КН формы содержит хотя бы одну переменную с ее отрицанием, то есть имеет вид .

Доказательство. Пусть FИ и F^k ее КН форма, то есть , где есть ДО.

Так как FИ, то и F^kИ, что возможно в том случае, когда каждый ДО является истинным. То теореме 1 § 6 ДО будет ТИ только тогда, когда он содержит хотя бы одну дизъюнкцию вида .

Критерий 2. Формула алгебры высказываний F(x₁, x₂, ..., x_n) тогда будет ТЛ, когда каждая конъюнкция ее ДН формы содержит хотя бы одну переменную с ее отрицанием, то есть имеет вид .

Доказательство (аналогично критерию 1).

Пусть F  Л, и F^д - ее ДН форма, то есть , где есть КО.

Так как F  Л, то и F^д  Л, что возможно в том случае, когда каждый КО является ложным. По теореме 2 § 6 КО будет ТЛ тогда и только тогда, когда он содержит хотя бы одну конъюнкцию вида .

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

1. Преобразуем данную формулу алгебры высказываний какой-либо равносильной ей КН форме, если она не задана в этом виде.

2. Если данная дизъюнкция этой формы имеет вид , то данная формула является ТИ.

3. Если второй шаг не выполняется, то преобразуем данную формулу к какой-либо равносильной ей ДН форме.

4. Если каждая конъюнкция этой формы имеет вид , то данная формула ТЛ.

5. Если четвертый шаг не выполняется, то данная формула является и выполнимой и опровержимой.

§ 8. Совершенные конъюнктивные и дизъюнктивные нормальные формы формул алгебры высказываний.

Определение 1, 2. Дизъюнктивный (конъюнктивный) одночлен от n переменных высказываний x₁, x₂, ..., x_n называется совершенным, если каждая переменная входит в него ровно один раз: либо сама, либо своим отрицанием.

Из этих определений следует, что совершенный одночлен от n переменных высказываний состоит точно из n членов.

Примеры.

1) СКО от двух переменных:

2) CДО от трех переменных: , .

Определение 3. Совершенной дизъюнктивной нормальной формой формулы алгебры высказываний называется такая ДН форма этой формулы, в которой каждый ее конъюнктивный одночлен является совершенным.

Пример. СДНФ формулы от двух переменных .

Определение 4. Совершенной конъюнктивной нормальной формой формулы алгебры высказываний называется такая КН форма этой формулы, в которой каждый ее ДО является совершенным.

Пример. СКНФ формулы от трех переменных .

Из этих определений и доказанных выше теорем вытекают следующие принципиально важные следствия.

Следствия 1, 2. Для всякой формулы алгебры высказываний, не являющейся ТИ (ТЛ) существует равносильная ей СКН форма (СДН форма) и притом единственная.

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

1. Приводим данную формулу F алгебры высказываний к равносильной ей формуле F₁ относительно первых трех логических операций.

2. Приводим полученную формулу F₁ к равносильной ей нормальной форме: конъюнктивной или дизъюнктивной.

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

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

5. Если в полученной нормальной форме имеется одночлен, содержащий переменную x_i с ее отрицанием , то все такие одночлены отбрасывают.

6. Если какой-либо одночлен F_j от n переменных не содержит некоторой переменной x_i, то он заменяется двумя одночленами вида для случая ДН форм и двумя одночленами вида для случая КН форм.