Аналитические способы представления ФАЛ.

Вводя алгебру логики: , где , ;

Мы получаем возможность описания некоторой логической функции (ФАЛ) бесконечным количеством формул.

Возникает вопрос, нельзя ли указать такой способ записи или представления ФАЛ, который суживал бы число логических операций. Если мы называем базисом логических операций, то переходя к термину базис можно вышеуказанный вопрос сформировать следующим образом: нельзя ли сформировать такой минимальный базис, который обеспечивал бы описание ФАЛ.

Ответом на этот вопрос является результат полученный Яблонским и Постом.

Они получили следующий результат:

1. - базис.

2. или

3. или

Рассмотрим аналитические способы получения канонической (стандартной) формы ФАЛ:

1. СДНФ – совершенная дизъюнктивная нормальная форма.

2. СКНФ – совершенная конъюнктивная нормальная форма.

Df1. Конъюнктивной нормальной формой (КНФ) представления некоторых ФАЛ называется выражение вида: где .

Df2. Дизъюнктивной нормальной формой (ДНФ) представления некоторых ФАЛ называется выражение вида:

Пример:

Df3. Совершенная дизъюнктивной нормальной формой (СДНФ) называется выражение вида:

1.

2.

, где

, где , γ _j = 1-ε _i

В определении 3 сделано обобщение определения 2 и это обобщение называется совершенным. Сравнивая Df2 и Df3, можно заметить следующее:

1. В СДНФ все элементарные конъюнкции имеют одинаковое число членов (одинаковый ранг):

2. В элементарной конъюнкции ранга n не могут встречаться выражения вида . Эти 2 ограничения позволяют назвать ДНФ совершенно нормальной формой. Алгоритм нахождения СДНФ исходной ФАЛ.

1. Исходную ФАЛ необходимо представить в виде таблицы истинности, т.е. указать ее конкретные численные значения (см. выше: способ вычисления ФАЛ).

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

3. Каждое истинное значение функции выразить в виде элементарной конъюнкции (ранга n) соответствующих логических переменных.

4. Логически сложить (V) элементарные конъюнкции (ранга n), полученные на предыдущем этапе.

Пример:

Пусть указана в виде таблицы истинности любая функция 3^х переменных.

№	Р1	Р2	Р3	φ 1 (Р1, Р2, Р3)
	И	И	И	И	р1& р2& р3
	И	И	Л	И
	И	Л	И	Л	V
	И	Л	Л	Л	V
	Л	И	И	Л	V
	Л	И	Л	И
	Л	Л	И	И
	Л	Л	Л	Л	V

1)

2)

6)

7)

Проверяем на совершенство:

1 условие выполнено,

2 условие выполнено.

Существует аналитический способ нахождения СДНФ некоторой ФАЛ, заданной в ДНФ.

Рассмотрим этот способ на примере.

1. Элементарная конъюнкция отвечает условиям СДНФ.

2. Элементарная конъюнкция доводим до СДНФ следующим образом

(мы имеем право это сделать ввиду того, что а ничего не меняется)

Из этого примера вытекает следующий алгоритм получения СДНФ некоторой ФАЛ при ее задании в ДНФ

1 шаг. В заданной ДНФ выделить неполные элементы конъюнкции, т.е. число логических переменных в ней неполное, участвуют не все логические переменные.

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

3 шаг. Если от умножения на предыдущем этапе элементарные конъюнкции снова оказываются неполными, то необходимо умножить, как и в пункте 2 на отсутствующую логическую переменную. Следует подчеркнуть, что нужно производить перемножение последовательно.

Рассмотрим представленные функции в СКНФ.

Df4. СКНФ некоторой ФАЛ называется выражение вида 2.

2.

если , если

,

Из определения СКНФ вытекает следующий алгоритм ее получения:

1 шаг. Исходная ФАЛ должна быть представлена в виде таблицы истинности.

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

3 шаг. Каждое из ложных значений функции необходимо представить в виде элементарной дизъюнкции ранга n, соответствующих логических перемещенных.

4 шаг. Полученные на предыдущем шаге элементарные дизъюнкции соединить знаком конъюнкции, т.е. логически перемножить. Окончательное выражение и есть СКНФ заданной ФАЛ.

Рассмотрим тот же пример

3)

4)

5)

8)

В СКНФ нет:

1) 2)

3) все элементы дизъюнкции имеют n логических переменных.

Когда какую из СКНФ или СДНФ удобно применять?

Во-первых, любая ФАЛ (кроме тождественно ложной) может быть представлена в СДНФ, т.е. в СДНФ функция представляется по ее истинным значениям. Во-вторых, любая ФАЛ (кроме тождественно истинной) может быть представлена в СКНФ, т.е. в СКНФ функция представляется по ее ложным значениям.

Вывод: Если в таблице истинности функция содержит больше своих истинных значений нежели ложных, то удобнее представлять в СКНФ, если наоборот, то удобнее в СДНФ.

Пример:

φ ₁ удобнее представлять в СКНФ

φ ₂ удобнее представлять в СДНФ

φ ₁(Р₁, Р₂)_СКНФ =

φ ₂(Р₁, Р₂)_СДНФ =

При указании СКНФ аналитический способ нахождения некоторой ФАЛ по ее КНФ. Он заключается в следующем: в неполной элементарной дизъюнкции (не все логические переменные исходной ФАЛ участвуют) необходимо произвести логическое сложение с выражением , где i – номер отсутствующих логических переменных.

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

.