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

1 Элементы математической логики

2 Высказывание Объект изучения – высказывание. Высказывание – предложение (сообщение) об объективно существующей действительности, содержание которого можно определить как истинное или ложное. Вопросительные и восклицательные предложения не могут быть высказываниями.

3 Алгебра логики 1. Инверсия 2. Конъюнкция А¬А¬А ЛИ ИЛ АВА&ВА&В ЛЛЛ ЛИЛ ИЛЛ ИИИ

4 3. Дизъюнкция АВАVВАVВ ЛЛЛ ЛИИ ИЛИ ИИИ

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

6 Логические элементы 1. Инвертор 2. Конъюнктор Схема «И» А¬А¬А АВА&ВА&В A B A

7 Логические элементы 3. Дизъюнктор Схемы «И», «ИЛИ», «НЕ» образуют функционально полную систему, т.е. с помощью этих схем может быть построено любое устройство ЭВМ. АВАVВАVВ A B

8 Цепочка из логических элементов, в которой выходы одних элементов являются входами других, называется логическим устройством Схема соединения логических элементов, реализующая логическую функцию, называется функциональной схемой. Формой описания функции, реализуемой логическим устройством, является структурная формула. Построение функциональных логических схем логических устройств

9 Задача 1. Дана структурная формула: F(X,Y)= (X v Y) & X Постройте соответствующую ей функциональную схему. Решение: Проверить, что эта функциональная схема соответствует заданной структурной формуле, можно, сравнив таблицы истинности для той и другой X Y 1 &

10 XYXX v Y F(X,Y) Таблица истинности для формулы F(X,Y)= (X v Y) & X

11 Опишем работу функциональной схемы с помощью таблицы истинности: XY Выход 1 Выход 2 Выход 3 Выход Совпадение значений последних столбцов двух таблиц свидетельствует о том, что функциональная схема построена верно.

12 Задача 2 Определите структурную формулу по заданной функциональной схеме: 1 X Y F(X,Y)

13 Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма На практике при конструировании различных электронных устройств часто возникает обратная задача от таблицы истинности перейти к формуле, чтобы на ее основе построить функциональную схему. Введем следующие определения. Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые. X & X ; X & Z; X & Y & Z, Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые. X V X, X V Z, X V Y V Z,

14 Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма Всякую дизъюнкцию элементарных конъюнкций назовем дизъюнктивной нормальной формой (ДНФ). X & X V X & Y & Z ; X & Y V Y V X & Z, Всякую конъюнкцию элементарных дизъюнкций назовем конъюнктивной нормальной формой (КНФ). (X V Y V X) & (X V Z) ; X & (X V Y) & (X V Z) ;

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

16 Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма Алгоритм получения СДНФ по таблице истинности. 1. Отметить те строки таблицы истинности, в последнем столбце которых стоят 1 : XУF(X,Y) * Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание: Х& У для 2-й строки; Х& У для 3-й строки. 3. Все полученные конъюнкции связать в дизъюнкцию: (Х & Y) V (Х & Y). X УЯ*, У) 00ь_ 0* *

17 Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма Алгоритм получения СКНФ по таблице истинности. 1. Отметить те строки таблицы истинности, в последнем столбце которых стоит 0: XYF(X,Y) 00 0 * Выписать для каждой отмеченной строки дизъюнкцию всех переменных cледующим образом: если значение некоторой переменной в данной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно 1, то ее отрицание: Х V Y для 1-й строки; Х V Y для 4-й строки. 3. Все полученные конъюнкции связать в дизъюнкцию: (Х V Y) &(Х V Y).

18

19 ЕГЭ 2007 A9 Для какого числа X истинно высказывание ((X>3) \/(X (X

20 ЕГЭ 2006 A9 Для какого из указанных значений числа X истинно высказывание: (X>4) \/ ((X>1) ->(X>4))? 1)12)23)34)4 A10 Какое логическое выражение равносильно выражению ¬ (¬A \/ B) \/ ¬C? 1)(A /\ ¬B) \/ ¬C2)¬A \/ B \/ ¬C3)A \/ ¬B \/ ¬C 4)(¬A /\ B) \/ ¬C A11 Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности : Какое выражение соответствует F? 1)¬X \/ ¬Y \/ ¬Z2)X /\ ¬Y /\ ¬Z3)X \/ Y \/ Z 4)X /\ Y /\ Z XYZF