Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Стандартные формы функций алгебры логики

Функции алгебры логики (ФАЛ) одного | Аргумента | Константа 0 | Функции двух аргументов | ФАЛ конъюнкция | ФАЛ дизъюнкция | Тождества алгебры логики | Законы алгебры логики | Теорема разложения в ряд функции алгебры | Аналитический метод минимизации ФАЛ |


Читайте также:
  1. I этап реформы банковской системы относится к 1988-1990 гг.
  2. I. Задания закрытой формы с одним правильным ответом. Обведите букву правильного ответа.
  3. II. НАСЛЕДСТВЕННЫЕ ФОРМЫ ПАТОЛОГИИ
  4. Study the table below and learn the appropriate be-verb forms in relation to personal pronouns. (Изучите нижеследующую таблицу и запомните формы глагола.)
  5. V. Конструирование предметов круглой формы
  6. V. Структура функций.
  7. VI. Существительные, употребляемые в единственном или во множественном числе (по смыслу), не меняя формы.

 

К стандартным формам функций алгебры логики относятся:

- дизъюнктивная нормальная форма (ДНФ),

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

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

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

Наибольшее применение при синтезе и анализе дискретных устройств находят стандартные формы ДНФ и СДНФ. К этим формам предъявляются следующие требования:

1. Формы должны быть такими, чтобы ими можно было представить любую ФАЛ.

2. Алгоритм представления ФАЛ в этих формах не должен быть сложным.

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

Дизъюнктивная нормальная форма представляет собой дизъюнкцию элементарных конъюнкций аргументов, например

.

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

Любая функция алгебры логики может быть представлена в виде ДНФ согласно следующего алгоритма:

1. Путем преобразований (используя таблицу 1.6.) в заданном логическом выражении оставить только операции «И», «ИЛИ», «НЕ».

2. Опустить знаки отрицания непосредственно на аргументы.

3. Раскрыть скобки, если они имеют место.

4. Отбросить лишние аргументы в конъюнкциях согласно закону повторения.

5. Если имеют место одинаковые элементарные конъюнкции, то лишние отбросить.

 

~
Пример 2.6. . Представить заданное логическое выражение в ДНФ.

Решается согласно алгоритма

1. Необходимо избавиться от операции равнозначности, используя таблицу 1.6.

.

2. Опускаются знаки отрицания непосредственно на аргументы

.

3. Раскрываются скобки

.

 

Лишних аргументов в конъюнкциях и повторяющихся конъюнкций нет.

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

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

в данном случае функция зависит от трех аргументов х 1 х 2 х 3.

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

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

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

 

Пример 2.7. Преобразовать ДНФ в СДНФ.

Отсюда следует, что для преобразования ДНФ в СДНФ необходимо:

1. Все элементарные конъюнкции ДНФ умножить на тождества с недостающими аргументами.

2. Раскрыть скобки.

3. Отбросить лишние слагаемые (конституэнты единицы).

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

 

Пример 2.8. Представить функцию алгебры логики в СДНФ табличным способом (функция та же, что и в примере 2.7).


Таблица 2.4.

Таблица истинности заданной функции

Наборы аргументов х 1 х 2 Конституэнты единицы
х 1 х 2 х 3
0 0 0          
0 0 1          
0 1 0          
0 1 1          
1 0 0          
1 0 1          
1 1 0          
1 1 1          

 

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

.

Полученная СДНФ совпадает с СДНФ примера 5.2.

 

Контрольные вопросы

 

1. Представить и пояснить тождества алгебры логики.

2. Представить и пояснить законы алгебры логики.

3. Доказать закон склеивания.

4. Доказать соотношения, вытекающие из теоремы разложения.

5. Что представляет собой функционально-полный набор функций алгебры логики?

6. Назвать возможные функционально-полные наборы (базисы) ФАЛ.

7. Дать определение ДНФ.

8. Что представляет собой элементарная конъюнкция?

9. Дать определение СДНФ.

10. Что представляет собой конституента единицы?

11. Какие существуют способы представления ДНФ в СДНФ?

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

13. Решить пример представления заданных ФАЛ функционильно-полными наборами «И», «ИЛИ», «НЕ»; «И-НЕ»; «ИЛИ-НЕ»

14. Решить примеры представления заданных функций сначала в виде ДНФ, а затем в виде СДНФ


Дата добавления: 2015-07-25; просмотров: 130 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Алгебры логики| Некоторые понятия и определения

mybiblioteka.su - 2015-2024 год. (0.01 сек.)