Самостоятельная работа: Выпишите аналитический выражения функций 2-х переменных
Представление произвольной функции алгебры логики в виде формулы алгебры логики Пусть F(х1, х2 .....х n ) произвольная функция алгебры логики n переменных. Рассмотрим формулу
которая составлена следующим образом: каждое слагаемое этой логической суммы представляет собой конъюнкцию, в которой первый член является значением функции F при некоторых определенных значениях переменных х1 , х 2 ,..., х n , остальные же члены конъюнкции представляют собой переменные или их отрицания. При этом под знаком отрицания находятся те и только те переменные, которые в первом члене конъюнкции имеют значение 0. Вместе с тем формула содержит в виде логических слагаемых всевозможные конъюнкции указанноrо вида. Ясно, что формула полностью определяет функцию F(х1, х2 .....х n ). Иначе говоря, значения функции F и формулы совпадают на всех наборах значений переменных х1, х2 .....х n Вид этой формулы может быть значительно упрощен. если в ней отбросить те логические слагаемые, в которых первый член конъюнкции имеет значение 0 (и, следовательно. вся конъюнкция имеет значение 0). Если же в логическом слагаемом первый член конъюнкции имеет значение 1, то , этот член конъюнкции можно не выписывать. Таким образом, в результате получается формула , которая содержит только элементарные переменные высказывания и обладает следующими свойствами: 1) Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(х1, х2 .....х n ). 2) Все логические слагаемые формулы различны. 3) Ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание. 4) Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды. Перечисленные свойства будем называть свойствами совершенства или. коротко. свойствами (С).. Нормальные формы. Определение 1. Элементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний. Элементарная конъюнкция n переменных может быть записана в виде:
Определение 2. Дизъюнктивной нормальной формой (ДНФ) формулы А называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций. Для любой формулы алгебры логики путем равносильных преобразований можно получить ее ДНФ. причем не единственную. Среди многочисленных ДНФ А существует единственная ДНФ А, для которой выполняются перечисленные выше четыре свойства совершенства (свойства (С)). Такая ДНФ А называется совершенной дизъюнктивной нормальной формой формулы А (СДНФ А ). Способы приведения формулы к СДНФ. 1. СДНФ А может быть получена с помощью таблицы истинности. Пример1 . Пусть функция f(x1, x2, x3) задана таблицей истинности. Запишем ее в виде СДНФ.
Выберем наборы, на которых функция равна 1. Их три: (0, 1, 0), (1, 0, 0) и (1, 1, 1), поэтому f(x1, x2, x3)º &x2& Úx1& & Úx1&x2&x3. 2. Другой способ получения СДНФ формулы А основан на равносильных преобразованиях формулы и состоит в следующем: Алгоритм приведения формулы к СДНФ. 1. Путем равносильных преобразований формулы А получают одну из ДНФ А. 2. Если в полученной ДНФ А входящая в нее элементарная конъюнкция В не содержит переменную xi, то используя равносильность В&(хi Ú ) ºВ, элементарную конъюнкцию В заменяют на две элементарных конъюнкции (В& хi) и (В& ). каждая из которых содержит переменную хi. 3. Если в ДНФ А входят две одинаковых элементарных конъюнкции В, то лишнюю можно отбросить, пользуясь равносильностью В ÚВ º В . 4. Если некоторая элементарная конъюнкция В, входящая в ДНФ А. содержит переменную и ее отрицание , то элементарная конъюнкция В будет равна 0, и В можно исключить из ДНФ А, как нулевой член дизъюнкции. 5. Если некоторая элементарная конъюнкция, входящая в ДНФ А, содержит переменную Х; дважды, то одну переменную можно отбросить. Пример2:Следующую формулу привести к СДНФ, предварительно приведя её равносильными преобразованиями к ДНФ: А= Решение: Определение 3. Элементарной дизъюнкцией n переменных называется дизъюнкция переменных или их отрицаний. Элементарная дизъюнкция n переменных может быть записана в виде:
Определение 4. Конъюнктивной нормальной формой (КНФ) формулы А называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций. Для любой формулы алгебры логики путем равносильных преобразований можно получить ее КНФ, причем не единственную. Способы приведения формулы к СКНФ. 1. СКНФ может быть получена с помощью таблиц истинности. Пример3. Пусть f(x1, x2, x3) = x1 (x2 (x3 ~ x1)). Представим ее в виде КНФ, для этого получим таблицу истинности.
(Выберем наборы, на которых функция принимает значение 0). Функция равна нулю только на наборе (1, 1, 0), поэтому f(x1 x2 x3)= Ù Ù x3. 2. Другой способ получения СКНФ, использующий равносильные преобразования, состоит в следующем: Алгоритм приведения к СКНФ. 1. Путем равносильных преобразований формулы А получают одну из КНФ А . 2. Если в полученной КНФ А входящая в нее элементарная дизъюнкция В не содержит переменную хi то используя равносильность ВÚ (хi & ) ºВ. элементарную дизъюнкцию В заменяют на две элементарные дизъюнкции В Úхi и ВÚ . каждая из которых содержит переменную хi . 3. Если в КНФ А входят две одинаковых элементарных дизъюнкции В, то лишнюю можно отбросить, пользуясь равносильностью В& В º В . 4. Если не которая элементарная дизъюнкция, входящая в КНФ А. содержит переменную хi дважды, то лишнюю можно отбросить. пользуясь равносильностью xÚxºx ; . 5. Если некоторая элементарная дизъюнкция, входящая в КНФ А . содержит переменную и ее отрицание. то элементарная дизъюнкция имеет значение 1, а поэтому ее можно отбросить. как единичный член конъюнкции. Пример4: Следующую формулу привести к СКНФ, предварительно приведя её равносильными преобразованиями к КНФ: А= . Решение:
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (407)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |