Совершенная конъюнктивная нормальная форма (СКНФ)

6 7 8 9 10 11 12

Элементарной дизъюнкцией n -переменных называется дизъюнкция переменных или их отрицаний.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция элементарных дизъюнкций.

КНФ, удовлетворяющая свойствам совершенства, называется совершенная конъюнктивная нормальная форма (СКНФ).

СКНФ можно находить с помощью СДНФ по формуле

СКНФА=

Пример:

Существует еще один способ нахождения СДНФ и СКНФ: по таблицам истинности. Для этого необходимо:

Находим СДНФ: строим таблицу истинности для формулы А, на наборах, где получилась «1», выписываем элементарную коньюнкцию по входящим x, у и z. Если, на наборе переменная «0», то пишем ее с отрицанием, если «1», то без отрицания. Далее записываем дизъюнкцию элементарных конъюнкций.

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

Пример: Четырем ученикам А, К, С и Д поручили убирать 7-ой, 8-ой, 9-ый и 10-ый классы. 10-ый класс оказался убран плохо. Ученики сообщили следующее:

1. А: «Я убирал 9-ый класс, а С 7-ой».

2. К: «Я убирал 9-ый класс, а А 8-ой».

3. С: «Я убирал 8-ой класс, а К 10-ый».

Д ушел домой. В дальнейшем выяснилось, что каждый ученик в одном из двух высказываний сказал правду в другом ложь. Какой класс убирал каждый ученик?:

Введем обозначения:

Х_y, где Х – имя ученика, y – класс, который он убирал. Так как в каждом сложном высказывание одно элементарное является истинным, а другое ложным, то истинной будет дизъюнкция этих высказываний.

1. А₉ С₇2. К₉ А₈3. С₈ К₁₀