Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

1-й сем-ДМ-слайды-ДГТУ / Функции алг. лог.,дополн

..doc
Скачиваний:
54
Добавлен:
19.05.2015
Размер:
225.28 Кб
Скачать

Функции алгебры логики. Проблемы разрешимости. Булева алгебра. Представление произвольной функции алгебры логики в виде формулы алгебры логики.

Пусть F()- произвольная функция алгебры логики n переменных.

Рассмотрим формулу

F (1, 1, 1)

F (1, 1, 1, 0)

(1) F (1, 1, 1, 0, 1)

… F (0, 0, 0, 0)

Ясно, что (1) определение функции F(), те значения F и формулы (1) совпадают на всех наборах значений переменных .

Свойства:

  1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F()

  2. Все логические слагаемые формулы различны.

  3. Ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание.

  4. Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

Свойства 3, 4 – свойства совершенства им свойства (С).

Для каждого набора значений переменных, на котором функция F() принимает значение 1, заменим конъюнкцию элементарных переменных высказываний, взяв за конъюнкции ,если значения на указанном наборе значений есть 1 и отриц. . Если значение лишь 0. Дизъюнкция всех записанных конъюнкций и будет формулой.

Пусть, например, функция F() имеет следующую таблицу истинности:

f ()

1

1

1

0

1

1

0

1

1

0

1

1

1

0

0

0

0

1

1

0

0

1

0

1

0

0

1

0

0

0

0

1

Для набора значений переменных (1,1,0), (1,0,1), (0,1,0), (0,0,0), на которых функция принимает значение 1, занятом конъюнкции , , , , а формула обладающая свойствами (С), имеет вид:

.

Закон двойственности.

Пусть формула содержит операции конъюнкции, дизъюнкции и отрицания.

Назовем операцию конъюнкции двойственной операцией дизъюнкции, а операцию дизъюнкции - двойственной операцией конъюнкции

Определение: формулы и назовем двойственными, если формула получается из формулы путем замены в ней операции на двойственную. Например, для формулы , двойственной формулой будет формула

Теорема: Если формулы и равносильны, то равносильны и их двойственные формулы, то есть .

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

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

Элементарная конъюнкция переменных может быть записана в виде:

, где

Определение 2:Дизъюнктивной нормальной формой (ДНФ) формулы называется равносильная ей формула, представляющая собой дизъюнкцией элементарных конъюнкций.

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

Например, для формулы имея: , та ДНФ , ДНФ

Единственная ДНФ , для которой 4 свойства совершенства (С).

СДНФ формулы - получается из таблиц истинности.

Другой способ: - из равносильных преобразований формулы состоящих в следующем:

  1. Пути равносильных преобразований формулы получает одну из ДНФ .

  2. Если в ДНФ , конъюнкция не содержит переменную ,то, используя , заменить на и , каждая из которых содержит .

  3. Если в ДНФ входят 2 одинаковых элементарные конъюнкции , то 1 из них можно отбросить, т. е

  4. Если некоторые элементарные конъюнкции входят в ДНФ содержит и , то и испомогается из ДНФ , как нулевой член дизъюнкции.

  5. Если некоторые элементарные конъюнкции, входящие в ДНФ содержат переменную дважды, то одну из них можно отбросить,

→СДНФ

Например, для ДНФ не содержит , то , деля на 2 элементарные конъюнкции и . Получим ДНФ .

Лишнее отбросим, используя, . Имея, получим, ДНФ, , то получим окончательно.

СДНФ .

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

Определение 1: Элементарной дизъюнкцией n переменных называется дизъюнкция переменных или их отрицаний: , где

Определение 2: Конъюнктивной нормальной формой (КНФ) формулы называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.

Для любой формулы алгебры логики измененной равносильных преобразований можно получить ее КНФ причем не единственную.

Пример.

Но ; ; ; , то КНФ , но ; , то КНФ .

Определение 3: КНФ - совершенная КНФ формулы (СКНФ ), если для нее выполняются условия:

  1. Все элементарные дизъюнкции, входящие в КНФ ,различны.

  2. Все элементарные дизъюнкции, входящие в КНФ , содержат не переменные.

  3. Каждая элементарная дизъюнкция, входящая в КНФ , не содержит 2 одинаковые переменные

  4. Каждая элементарная дизъюнкция, входящая в КНФ . Не содержит переменную и ее отрицание.

Способ получения СКНФ:

Используем таблицу истинности для , получим СДНФ , получим СКНФ , взяв отрицание СДНФ , т. Е СКНФ СДНФ .

Другой способ:

  1. Из формулы получим одну из КНФ .

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

  3. Если в КНФ входят 2 одинаковые элементарные дизъюнкции , то лишнее можно отбросить, т. е .

  4. Если переменная содержится дважды, то лишнее можно отбросить используя

  5. Если элементарные дизъюнкции. Входящие в КНФ , содержат переменную и ее отбросить, то и все дизъюнкции1,ее можно отбросить, как

единственный член конъюнкции получим СКНФ .

Пример.

.

Проблема Разрешимости.

Все формулы могут разделяться на 3 класса:

  1. Тождественно истинные

  2. Тождественно ложные

  3. Высказывания

Формулу называют высказыванием, если она принимает значение истины хотя бы на 1 добора переменных, входящих в нее переменных n не является тождественно истинной.

К какому классу относить формулы?

Формулы приводящие к КНФ и ДНФ.

Теорема 1:Для того, чтобы элементарная дизъюнкция была тождественно истинной. Необходимо и достаточно, чтобы в ней содержались переменная и ее отрицание.

Теорема 2: Для того, чтобы формула алгебры логики была тождественно истиной, необходимо, чтобы любая элементарная дизъюнкция , входящие в КНФ . Содержала переменную и ее отрицание.

Теорема 3: Для того, чтобы элементарная конъюнкция было тождественно ложной, необходимо и достаточно, чтобы в ней содержались ее переменная и ее отрицание.

Теорема 4:Для того, чтобы формула алгебры логики была тождественно ложной, необходимо и достаточно, чтобы любая конъюнкция , входящая в ДНФ , содержала переменную и ее отрицание.