Презентация к уроку "Нормальные формы для формул алгебры логики"
презентация к уроку

Слайд 1

Элементы математической логики Раздел 2. Логика (алгебра) высказываний

Слайд 2

Нормальные формы для формул алгебры высказываний Лекция 4

Слайд 3

2.1. Нормальные формы для формул алгебры высказываний Одна и та же логическая формула может быть записана различным образом. Например, функция F ( A , B ) может быть записана следующими эквивалентными выражениями: Эквивалентность этих формул легко проверить по таблицам истинности или выполнив необходимые преобразования.

Слайд 4

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

Слайд 5

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

Слайд 6

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

Слайд 7

Алгоритм приведения к НФ Для приведения формулы к нормальной форме используют законы логики и правила логических преобразований по следующему алгоритму: Устранить «↔» и «→ ». Продвинуть отрицание до пропозициональной переменной. Применить закон дистрибутивности. Постоянно избавляться от двойных отрицаний.

Слайд 8

Примеры : Преобразовать формулу к виду ДНФ F=F1 ˄(F2∨¬F2)∨F2˄(F1∨¬F1)

Слайд 9

Примеры : Преобразовать формулу к виду КНФ F=F1˄( F1∨F2)∨¬F2˄(F1∨F2)

Слайд 10

Примеры : Преобразовать формулу к виду КНФ F=((F1→(F2∨¬F3))→F4)

Слайд 11

Примеры : Преобразовать формулу к виду ДНФ F=¬(F1˄F2)˄(F1∨F2)

Слайд 12

Совершенные НФ Использование нормальных форм не устраняет полностью неоднозначности записи логических функций, например Поэтому среди нормальных форм выделяют такие, в которых функции записываются единственным образом. Их называют совершенными. Применяются совершенная дизъюнктивная и совершенная конъюнктивная формы (СДНФ и СКНФ ) .

Слайд 13

СДНФ Совершенная дизъюнктивная нормальная форма (СДНФ) - ДНФ, удовлетворяющая условиям: Все элементарные конъюнкции различны . Нет нулевых конъюнкций . Ни одна из элементарных конъюнкций не повторяется. Каждая элементарная конъюнкция содержит все переменные или их отрицания. Примеры СДНФ: ( X  Y) (XY) (XY) (XYZ)  (X Y Z) (X Y Z ) (X YZ) (XYZ) (X 1 X 2 X 3 X 4 )  (X 1 X 2 X 3 X 4 ) (X 1 X 2 X 3 X 4 )

Слайд 14

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

Слайд 15

Теорема 2.4.1 (о представлении формулы алгебры высказываний совершенными дизъюнктивными нормальными формами). Каждая не тождественно ложная формула алгебры высказываний от n аргументов имеет единственную (с точностью до перестановки дизъюнктивных членов) СДНФ. Теорема 2.4.2 (о представлении формулы алгебры высказываний совершенными конъюнктивными нормальными формами). Каждая не являющаяся тавтологией формула алгебры высказываний от n аргументов имеет единственную (с точностью до перестановки конъюнктивных членов) СКНФ. Единственность совершенных нормальных форм у выполнимой ПФ обуславливает их использование для доказательства равносильностей , идея которого состоит в следующем: если у двух ПФ их СДНФ (СКНФ) совпадают, то они равносильны .

Слайд 16

2. 5 . Приведение формулы алгебры высказываний к совершенной нормальной форме Способы приведения формул к совершенным формам следуют из способов задания формул алгебры высказываний – либо с помощью таблицы , либо аналитически .

Слайд 17

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

Слайд 18

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

Слайд 19

Пример Пусть ПФ, содержащая переменные X , Y , Z , имеет ДНФ вида Используя аналитический способ привести к СДНФ. Решение: В соответствии с процедурой приведения к СДНФ умножим первую и вторую конъюнкции на 1

Слайд 20

Табличный способ приведения к совершенным формам Табличный способ приведения к СДНФ Составить таблицу истинности данной формулы. Рассмотреть те строки, в которых формула принимает истинностное значение 1. Каждой такой строке поставить в соответствие элементарную конъюнкцию, причем переменная, принимающая значение 1, входит в нее без отрицания, а 0 – с отрицанием. Образовать дизъюнкцию всех полученных элементарных конъюнкций, которая и составит СДНФ. Табличный способ приведения к СКНФ Составить таблицу истинности данной булевой функции. Рассмотреть те строки, в которых формула принимает истинностное значение 0. Каждой такой строке поставить в соответствие элементарную дизъюнкцию, причем переменная, принимающая значение 1, входит в нее с отрицанием, а 0 – без отрицания. Образовать конъюнкцию всех полученных элементарных дизъюнкций, которая и составит СКНФ.

Слайд 21

Пример Найти СКНФ и СДНФ для формулы Решение: Построим таблицу истинности и на ее основе составим СДНФ и СКНФ X Y Z Элементарные конъюнкции Элементарные дизъюнкции 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1

Слайд 22

Критерии тождественной истинности и тождественной ложности формул алгебры высказываний Теорема 2.6.1 (признак тождественной истинности формулы). Формула алгебры высказываний тождественно истинна тогда и только тогда, когда в каждой элементарной дизъюнкции её КНФ имеется, по меньшей мере, одна пропозициональная переменная, входящая в этот одночлен вместе со своим отрицанием. Теорема 2.6.2 (признак тождественной ложности формулы). Формула алгебры высказываний тождественно ложна тогда и только тогда, когда в каждой элементарной конъюнкции её ДНФ имеется, по меньшей мере, одна пропозициональная переменная, входящая в этот одночлен вместе со своим отрицанием.

Слайд 23

Примеры : Показать, что формула ( P  ( P  Q ))  Q - тавтология ( P  ( P  Q ))  Q   ( P  (  P  Q ))  Q   P  (  P  Q )  Q   P  ( P  Q )  Q  (  P  P  Q )  (  P  Q  Q ). По теорем 2.6.1 формула тождественно истинна.

Слайд 24

Примеры : 2. Показать , что формула P  (  Q  (  P  Q )) – тождественно ложна P  (  Q  (  P  Q))  (P   Q  P)  ( (P  Q  Q). По теорем 2.6.2 формула тождественно ложна.

Слайд 25

Задания для закрепления 5. Построить простейшую логическую формулу по заданной таблице истинности, которая имеет нулевые значения при следующих наборах переменных A , B , C : (001), (010), (011), (110 ).

Слайд 26

5. Построить простейшую логическую формулу по заданной таблице истинности, которая принимает значение 1 при следующих наборах переменных A , B , C : (010), (101), (111). Домашнее задание

Слайд 27

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