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

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

Высказывания простые сложные 5 > 3 истина x * x < 0 ложь Получаются путём объединения простых высказываний связками- союзами И, ИЛИ, НЕ. При этом значение истинности сложных высказываний зависит от истинности входящих в них простых высказываний и объединяющих их связок Значение истинности или ложности простого высказывания определяется однозначно! (x >2) and (x < -5)

Алгебра логики (алгебра высказываний, булева алгебра) – раздел математической логики, изучающий строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов. Простые высказывания называют в алгебре логики логическими переменными и обозначают буквами латинского алфавита. Сложные высказывания называют логическими функциями (или логическими выражениями). Логические переменные и функции определены на множестве двух значений {0,1} или {true, false}

Логические операции 1. Инверсия А¬А¬А ЛИ ИЛ АВА&ВА&В ЛЛЛ ЛИЛ ИЛЛ ИИИ a not a не a - логическое отрицание - логическое умножение a и b a b a. b a AND b 2. Конъюнкция

3. Дизъюнкция (нестрогая) АВАVВАVВ ЛЛЛ ЛИИ ИЛИ ИИИ - логическое сложение a или b a b a or b

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

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

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

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

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

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

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

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

ЕГЭ 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

ЕГЭ 2007 A9 Для какого числа X истинно высказывание ((X>3) \/(X (X<1) 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: Какое выражение соответствует F? 1)¬X \/ Y \/ ¬Z2)X /\ Y /\ ¬Z3)¬X /\ ¬Y /\ Z 4)X \/ ¬Y \/ Z XYZF

ЕГЭ 2007 A9 Для какого числа X истинно высказывание ((X>3) \/(X (X<1) 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: Какое выражение соответствует F? 1)¬X \/ Y \/ ¬Z2)X /\ Y /\ ¬Z3)¬X /\ ¬Y /\ Z 4)X \/ ¬Y \/ Z XYZF