Пример 3

Преобразовать логическую функцию

1. 
   по формуле 11
   
2. 
   по формуле 14
   
3. 
   по формуле 15
   

4.



А+А=А



=

Принцип двойственности
Представленные законы (пары: (1) и (2), (3) и (4), (6) и (7), (9) и (10), (14) и (15), (19)# и (20), (21) и (22)) показывают, что между формулами, запи­санными слева и справа, существует вполне определенная зависимость. Если в любой формуле дизъюнкцию заменить конъюнкцией, конъюнкцию заменить дизъ­юнкцией, 0 заменить 1,1 заменить 0, а отрицание сохранить без изменения, то формула с нечетным номером (например, (9) перейдет в формулу с четким номе­ром (10), и наоборот). Значит, с помощью указанных замен можно из одних равносильностей получить другие. Эта закономерность называется законом или принципом двойственности. Этот закон справедлив вообще для всех формул ал­гебры логики. Дело в том, что приведенных равносильностей вполне достаточ­но, чтобы с их помощью доказать любую другую равносильность. Поэтому ус­тановленная закономерность сохраняется и по отношению к любым другим равносильностям, если только соответствующие формулы не содержат импли­кацию. В связи с этим говорят, что операция конъюнкции двойственна опера­ции дизъюнкции и наоборот, а формулы F₁и F₂называют двойственными, если одна получается из другой, как указано выше, заменой каждой операции на двойственную операцию.

Иллюстрацией сказанного является следующий пример.

---

Пример. Дана формула . Получить двойственную ей формулу.

Решение.

Преобразуем исходную формулу в равносильную.



=

Составим теперь двойственную равносильность



Эту равносильность можно доказать с помощью формулы (10).

Обобщая вышеприведенное правило получения двойственной формулы, в математической логике доказано, что если есть некоторая формула F(A,B,...,Z) и к ней двойственна логическая формула Ф(А,В,...Z) то они удовлетворяют тождествам

или .

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

Справедлив также принцип двойственности; Если две логические форму­лы F₁(A,B,...,Z) и F₂(A,B,...,Z) равносильны, то сеть

F₁(A,B,...,Z) = F₂(A,B,...,Z) и каждая из них имеет двойственную формулу Ф₁(A,B,...,Z) и Ф₂(A,B,...,Z), то рав­носильны и двойственные формулы

F₁(A,B,...,Z) = F₂(A,B,...,Z)
Тема 1.6 Переключательные функции

1. 
   Переключательные функции
   

В логике не требуется знания абсолютного значения величины, поэтому физическая величина, подвергаемая логическим преобразованиям, называется переменной, или аргументом, и представляется ее положительная (Н) или менее положительная (L). Этим Значениям, называемым логическими уровнями, условно приравнивая значения 1 и 0, или наоборот 0 и 1, в зависимости от го соглашения.

Логические переменные могут подвергаться различным преобразованиям с использованием логических элементов. Такие преобразования описываются с помощью переключательных функций в которых используются различные буквы латинского алфавита: А, В, С, D, X, Y, x₁, x₂, х_з и т.д.

Функция от входных переменных называется переключательной если она так же, как ее аргументы, принимает два значения: лог ческой единице (лог. 1) или логического нуля (лог. 0).

---

2. 
   Основные базисы.
   

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

Базис — это функционально полный набор элементов, с помо­щью которого можно реализовать сколь угодно сложную переклю­чательную функцию. Их может быть несколько. Базис из логичес­ких элементов И, ИЛИ, НЕ называется основным.

Пример:

Представить логическую функцию в базисе И-НЕ

= = .
Задания для самостоятельной работы

Представить заданные логические функции в заданном базисе

Номер	Логические функции	Базис
1		И-НЕ
2		И-НЕ
3	, , ;	И-НЕ
4	, , ;	ИЛИ-НЕ
5	, , ;	ИЛИ-НЕ
6	, , .	ИЛИ-НЕ

---

Тема 1.7 Минимизация переключательных функций

1. 
   Совершенные нормальные формы
   

С помощью эквивалентных преобразований логической функции можно получить различные формы ее представления. Одной из основных задач по преобразованию логических формул является получение равносильных формул в. так называемой, нормальной форме, и установления типа заданной форму­лы алгебры высказываний. Формула имеет нормальную форму, если в пси пу­тем равносильных замен устранены операции эквиваленции, импликации, исклю­чающей дизъюнкции, двойного отрицания, и при этом знаки отрицания находятся только при переменных. Таким образом, формула имеет нормальную форму, ес­ли она записана с помощью конъюнкции и дизъюнкции, действующих на со­вокупность переменных, и отрицания, действующего на отдельные перемен­ные. Такие нормальные формулы называются дизъюнктивно-нормальную и конъюнктивно-нормальную формы.

Они являются наиболее удобными для опре­деления тождественной истинности и тождественной ложности формул.

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

Основная (элементарная) конъюнкция - это конъюнкция основных высказываний или их отрицаний. Например,

Основная (элементарная) дизъюнкция - это дизъюнкция основных выска­зываний иди их отрицаний. Например, .

Основная конъюнкция и дизъюнкция характеризуются рангом (поряд­ком), который определяется количеством логических переменных в конъюнк­ции и дизъюнкции. С помощью основной конъюнкции и основной дизъюнк­ции можно определить дизъюнктивно-нормальную и конъюнктивно-нормальную формы.

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

Дизъюнктивно-нормальной формой (ДНФ)данной формулы называется формула, равносильная данной, и прсдставимая в виде дизъюнкций основных

---

конъюнкций. Например, АВС+ ВС + С + АС.

Алгоритм получения нормальной формы.

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

Для представления логической формулы в форме КНФ (ДНФ) необхо­димо:

• 
  С помощью законов инфолюции представить формулу в базисе - { }
  
• 
  С помощью законов де Моргана исключить отрицание над логическими опера­циями, а по закону двойного отрицания удалить двойные знаки отрицания.
  
• 
  С помощью второго (первого) дистрибутивного закона удалить все суммы про­изведений (все произведения сумм) и произвести поглощение.
  

Рассмотрим несколько примеров преобразования логических формул и получения их нормальных форм.


Пример 1.

Привести к конъюнктивно-нормальной форме логиче­скую формулу.



Решение.

В соответствии с предложенной методикой, получим эквива­лентную ей формулу в базисе { }. Для этого с помощью законов инфо­люции исключим операцию эквиваленции, и используя закон двойного отри­цания и закона де Моргана, получим

=

Пример 2.

Привести к ДНФ логическую формулу:

Решение

=

Пример 3.

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

F=

Решение

1. 
   Исключить операцию эквиваленнции
   
2. 
   Исключить операцию импликации
   
3. 
   Исключить общие отрицания и раскрыть скобки, выполнить преобразования.
   

F=

---

Смотрите также файлы

• Программа по учебному курсу Химия Класс 8 Программу составила Киревичева Н. В 20202012 уч г 8 класс.doc

• Коммерциялы емес ашы акционерлік оам марбек дукеев атындаЫ.docx

• Контрольная работа по дисциплине Введение в профессиональную деятельность.docx

• П. А. Сивкова подпись, дата И. О. Фамилия.docx

• Самостоятельная работа по теме Цель занятия приобретение и закрепление знаний оюридической ответственности предприятий, загрязняющих окружающую среду, формирование умения применять их.docx