Нормальные формы в математической логике Подготовил: Шинкарёв Г. Г. ГИП-104. - презентация

1 Нормальные формы в математической логике Подготовил: Шинкарёв Г. Г. ГИП-104

2 Математическая логика это раздел математики изучающий понятие истинности высказываний. Высказыванием называется всякое предложение, о котором можно определённо сказать истинно оно или ложно.

3 Пример: Волга – это река (Выражение истинно). Собака – это мебель(Ложь).

4 Операции над логическими переменными: 1. Отрицание (инверсия). 2. Конъюнкция (логическое умножение). 3. Дизъюнкция (логическое сложение).

5 Отрицание _ Обозначение: х, x Например: кто-то сказал: "Тоска зеленая" (Высказывание А). Тогда фраза: " Тоска НЕ зеленая" Или: " Неверно, что тоска зеленая" (Обозначим В) будет отрицанием высказывания А.

6 Конъюнкция Обозначение: a&b, a b, ab, a b Пример: возьмем два высказывания: "У кота есть хвост" (А), "У зайца есть хвост" (В). Сложное высказывание "У кота есть хвост и у зайца есть хвост" истинно, т.к. истинны оба высказывания А и В.

7 Дизъюнкция Обозначение: a b Пример: возьмем два высказывания: "Мел черный." (А), "Доска черная." (В). Высказывание "Мел черный или доска черная" будет истинным, т.к. одно из исходных высказываний (В) истинно.

8 Выражения Выражения - Переменные, знакооперации, соединенные вместе при возможном наличии скобок для задания порядка выполнения операций.

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

10 Формы задания Булевой функции 1. Аналитическая (в виде логического выражения) 2. Табличная (в виде таблицы истинности) 3. Графическая 4. Таблично-графическая (в виде карты Карно) 5. Числовая 6. Символическая форма

11 Аналитическая _ _ y=(x1 x2) x3 _ _ _ _ _ _ y=x1 x2 x3 x1 x2 x3 x1 x2 x3

12 Табличная x1x1 x2x2 x3x3 _ x 1 x 2 y

13 Основные законы (тождества) 1) Коммутативный: ab=ba a b=b a 2) Ассоциативный: a(bc)=(ab)c 3) Дистрибутивный: a(b c)=ab ac a (bc)=(a b)(a c) 4) Закон двойного отрицания: = a=a

14 Основные законы (тождества) 5) Тавтологии: aa=a 6) Законы нулевого элемента: a0=0 a 0=a 7) Законы единичного элемента: а1=а а 1=1 8) Законы дополнительного элемента:

15 Основные законы (тождества) 9) Двойственности (деМоргана): __ _ _ __ _ _ a b=a b ab=a b Cледствия: ab=a b; a b=a b 10) Поглощения: a ab=a a(a b)=a 11) Сокращения: _ _ а аb=a b a(a b)=ab _ _ _ _ Cледствия: a ab=a b; a(a b)=ab 12) Склеивания: _ _ ab ab=a; (a b)(a b)=a

16 Нормальные формы Булевых функций Нормальные формы - это особый класс аналитических выражений, используемых при решении задачи минимизации Булевых функций и для перехода от табличной формы задания к аналитической. Нормальные формы строятся на основании операций конъюнкции, дизъюнкции и отрицания, причем отрицание только единственной переменной.

17 Элементарная конъюнкция 1. Определение: Элементарной конъюнкцией (дизъюнкцией) называется конъюнкция (дизъюнкция) конечного числа попарно различимых переменных или их отрицаний. 2. Примеры элементарных конъюнкций: _ _ x1, x2, x1x3, x2x4x5 (элементарная) ___ _ x1x2, x1x2x3 (не элементарная) 3.Рангом элементарной конъюнкции называется количество букв входящих в него.

18 Каноническая нормальная форма Конституентой единицы (нуля) называется элементарная конъюнкция (дизъюнкция) максимального ранга. Свойство конституенты: Конституента единицы (нуля) принимает значение единицы (нуля) на одном и только одном наборе аргументов. Пример: _ _ n=4 x1x2x3x4 (1010)=1 _ _ _ x1 x2 x3 x4=0 Дизъюнктивная (конъюнктивная) нормальная форма называется канонической, если все ее элементарные конъюнкции (дизъюнкции) представляют собой конституенты единицы (нуля).

19 Пример получения канонических форм y=x1 x2 КДНФ - каноническая дизъюнктивная нормальная форма: _ _ y=x1x2 x1x2 ККНФ - каноническая конъюнктивная нормальная форма: _ _ y=(x1 x2)(x1 x2) x1x1 x2x2 yКонституента единицы Конституенты нуля 000- x 1 x x21x x

20 Общие положения: 1) С помощью канонических форм наиболее просто осуществляется переход от табличной формы задания Булевой функции к аналитической. 2) Любая Булева функция за исключением логического нуля и логической единицы имеет единственные КДНФ и ККНФ. Логическую единицу можно представить в виде КДНФ и логический ноль в виде ККНФ. 3) КДНФ и ККНФ представляют собой две различные, но эквивалентные аналитические формы булевой функции. Это означает, что из одной формы можно получить другую, используя законы Булевой алгебры. _ _ _ _ _ _ _ _ _ _ y=(x1 x2)(x1 x2)=x1x1 x1x2 x2x1 x2x2=x1x2 x2x1=x1x2 x1x2 (КДНФ)

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