Логика в информатике Решение уравнений. Логические основы ПЭВМ. - презентация

1 Логика в информатике Решение уравнений. Логические основы ПЭВМ.

2 Логическое уравнение Логическое уравнение – равенство двух высказываний, в котором присутствует логическая переменная, которая представляет некоторую логическую функцию. Пример: Где корень: X = F (A, B)

3 Решение уравнения 1.Перейти к префиксной форме записи уравнения, заменив обозначения отрицаний на ¬ 2.Построить заголовок таблицы истинности специального вида 3.Заполнить строки таблицы истинности для всех сочетаний А и В, подставляя вместо X - 0 или 1. 4.Сформировать таблицу истинности для X = F (А,B) 5.По таблице истинности определить вид функции X, при необходимости воспользовавшись методами построения СКНФ и СДНФ, которые будут рассмотрены ниже.

4 Переход к префиксной форме Обычная форма: Префиксная форма:

5 Построение таблицы истинности специального вида ¬((А+B)·(X A·B))=¬(B+¬(X A))

6 Таблица истинности X=F(A, B) ABX Соответствует отрицанию импликации В в А ОТВЕТ:

7 Комбинационные схемы логических устройств Базисные элементы (ГОСТ ): 1 А В Дизъюнкция А В Эквивалентность & А В Конъюнкция M2 А В XOR

8 Комбинационные схемы логических устройств Базисные элементы (ГОСТ ): 1 А В Импликация & А В Элемент Шеффера & А В Коимпликация 1 А В Элемент Вебба

9 Расшифровка элемента & А В Коимпликация Вход 1 Вход 2 Отрицание Действие Выход А · В

10 Пример схемы F 1 & 1 & & 1M2 B A

11 Решение схем 1 Вариант – преобразование схемы в сложное логическое выражение и затем – упрощение его по законам логики. 2 Вариант – построение таблицы истинности а затем, при необходимости, построение через СКНФ или СДНФ (см. ниже). Рассмотрим второй вариант, как более простой и понятный.

12 Построение таблицы истинности AB A + B + · B B · A + A B A + · ·

13 Таблица истинности F(A, B) ABX Соответствует отрицанию импликации В в А ОТВЕТ:

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

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

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

17 Пример построения СДНФ XY F(X,Y) Отметить единицы 2. Конъюнкции: X · Y 3. Дизъюнкция: X · Y + X · Y

18 Алгоритм получения СКНФ по таблице истинности 1.Отметить строки таблицы истинности в последнем столбце которых стоят 0. 2.Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение переменной в данной строке равно 0, то в конъюнкцию включать саму эту переменную, если равно 1, то ее отрицание. 3.Все полученные дизъюнкции связать в конъюнкцию.

19 Пример построения СKНФ XY F(X,Y) Отметить нули 2. Дизъюнкции: X + Y 3. Конъюнкция: (X + Y) · (X + Y)