Практическое занятие №9-10. «Нормальные формы для формул алгебры высказываний (ч.1-2)»

Введем дополнительные (неэлементарные) логические операции:

• 
  Штрих Шеффера или антиконъюнкция
  
• 
  Стрелка Пирса (штрих Лукасевича) или антидизъюнкция
  
• 
  Сумма по модулю два (сумма Жегалкина) антиэквивалентность
  

Таблица истинности для всевозможных булевых функций от двух переменных:

		0															1
0	0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
0	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	0	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1

---

В формулах действует следующий порядок старшинства операций: отрицание «–» (если оно относится к одному высказыванию, например ), штрих Шеффера «| », стрелка Пирса « », конъюнкция « », дизъюнкция « », сумма по модулю два « », импликация « », эквивалентность « ».Определение. 1. Нормальная форма логической формулы – это такакя форма записи логической формулы, при которой не содержится знаков импликации, эквивалентности и отрицания неэлементарных формул. Существует в двух видах:

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

Определение. 2. Совершенная конъюнктивная нормальная форма (СКНФ) -- это КНФ, удовлетворяющая трем условиям:

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

Замечание. Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.Правила построения СКНФ по таблице истинности:Для каждого набора переменных, при котором функция равна 0, записывается сумма, причем переменные, которые имеют значение 1, берутся с отрицанием.Определение. 3. Совершенная дизъюнктивная нормальная форма (СДНФ) -- это ДНФ, удовлетворяющая трем условиям:

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

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

---

Для каждого набора переменных, при котором функция равна 1, записывается произведение, причем переменные.Определение. 4. Карты Карно (схемы Вейча) это наглядное представление логической функции в виде карты, которая удобна для оптимизации.Карты Карно представляют сбой определённую таблицу истинности обычно для двух, трёх и четырёх переменных и отличаются друг от друга способом обозначения строк и столбцов таблиц истинности.Расположение групп переменных x не имеет значения, необходимо лишь, чтобы каждая клетка отличалась от любой соседней лишь на одну переменную. Число клеток карты равно числу всевозможных интерпретаций переменных и в каждую клетку записывается значение формулы, соответствующее данной интерпретации переменных. Если какая-то из возможных комбинаций присутствует в СДНФ, то в соответствующей клетке ставится «1», в противном случае – « 0».Логические схемы. Устройства, реализующие элементарные булевы функции, называют логическими элементами. Их входы соответствуют булевым переменным, а выход -- реализуемой функции.В технике для обозначения логических элементов используют различные графические символы и названия, которые учитывают свойства и специфические особенности конкретных элементов. В теории принимаются упрощённые изображения в виде прямоугольников или других фигур, внутри которых помещаются условные названия или символы соответствующей функции (табл.1). Таблица 1Логические элементы, реализующие элементарные булевы функции

Функция	Нормальная форма	Контактная схема	Графическое изображение элемента	Название элемента
Отрицание				Инвертор
Конъюнкция				Совпадение
Дизъюнкция				Разделение
Импликация				Разделение с запретом
Эквивалентность				Равнозначность
Отрицание импликации				Совпадение с запретом
Сумма по модулю 2				Неравнозначность
Штрих Шеффера				Разделение с двумя запретами
Стрелка Пирса				Совпадение с двумя запретами

---

Например, на рис. 1a показана схема, реализующая функцию , которая имеет три входных, один выходной и три внутренних узла. Обычно для упрощения узлы на схемах не изображаются и во избежание излишних пересечений входы рассредоточиваются с указанием связанных с ними переменных (рис.1.b). Рис. 1a Рис. 1bКорректно построенные схемы должны удовлетворять следующим условиям:

• 
  не допускать замкнутых контуров, которые могут привести к неоднозначности сигналов на входах элементов;
  
• 
  любой вход элемента должен быть связан только с одним входом схемы или выходом другого элемента;
  
• 
  выходы элементов, не являющиеся выходами схемы и не связанные со входами других элементов, считаются лишними и исключаются из схемы.
  

1. 
   Выражая через конъюнкцию, дизъюнкцию и инверсию остальные связки, цепочкой равносильных преобразований заданную булеву формулу привести:
   a) к дизъюнктивной нормальной форме (ДНФ), по возможности сокращая количество литералов.
   b) к конъюнктивной нормальной форме (КНФ) также используя закон:
   .
   

Решение. a) Для начала, используя основные равносильности и приоритет операций избавимся от , Получим: ДНФ: b) В полученной ДНФ раскроем скобки и сгруппируем так, чтобы получить КНФ: Вынесем общий множитель за скобки, поучим: Раскроем скобки относительно дизъюнкции:

---

Так как 1 не влияет на конъюнкцию, то лишние множители можно опустить.КНФ: Ответ. а) ДНФ: b) КНФ:

2. 
   Для заданной булевой формулы необходимо:
   

1. 
   построить таблицу истинности;
   
2. 
   вектору значений построить СДНФ и СКНФ;
   
3. 
   упростить выражение для СДНФ и СКНФ, используя карту Карно;
   
4. 
   составить схему устройства, реализующего заданную СДНФ и СКНФ после упрощения.
   

Решение.

1. 
   Построим таблицу истинности:
   

0	0	0	1	1	0	1	1	0
0	0	1	1	1	0	0	0	1
0	1	0	1	0	0	1	1	0
0	1	1	1	0	1	1	1	0
1	0	0	0	1	0	1	0	1
1	0	1	0	1	0	0	1	0
1	1	0	0	1	0	1	0	1
1	1	1	0	1	0	1	0	1

---

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

• Классный час Государственные символы Российской Федерации.docx

• Открытый социальноэкономический колледж (ано по Открытый социальноэкономический колледж) Дисциплина безопасность жизнедеятельности.docx

• 3 Выполнен Баллов 1,00 из 1,00 Отметить вопрос Текст вопроса Выберите основную жалобу при болезнях желудка b. Тошнота, рвота Вопрос 4.docx

• Ооо мтц технология безопасности.doc

• Англия как главный спонсор нацистского режима.docx